數(shù)據(jù)結構題目

1、數(shù)據(jù)結構題目,設有一組初始記錄關鍵字序列( K1,K2,，Kn),要求設計一個算法能夠在 O(n)的時間復雜度內(nèi)將線性 表劃分成兩部分，其中左半部分的每個關鍵字均小于 Ki,右半部分的 每個關鍵字均大于等于Ki。void quickpass(int r, int s, int t)(int i=s, j=t, x=rs;while(i<j)while (i<j && rj>x) j=j-1; if (i<j) ri=rj;i=i+1;while (i<j &&

2、ri<x) i=i+1; if (i<j) rj=ri;j=j-1; ri=x;設單鏈表中有僅三類字符的數(shù)據(jù)元素(大寫字母、數(shù)字和其它字符)， 要求利用原單鏈表中結點空間設計出三個單鏈表的算法，使每個單鏈表只包含同類字符。typedef char datatype;typedef struct node datatype data; struct node *next;lklist;void split(lklist *head,lklist *&ha,lklist *&hb,lklist *&hc) (lklist

3、*p; ha=0,hb=0,hc=0;for(p=head;p!=0;p=head) (head=p->next; p->next=0;if(p->data>='A'&&p->data<='Z') p->next=ha; ha=p;else if (p->data>='0' &&p->data&am

4、p;lt;='9') p->next=hb; hb=p; elsep->next=hc; hc=p;? 7.已知由一個線性鏈表表示的線性表中含有3類字符的數(shù)據(jù)元素(如，字母、數(shù)字和其他字符)，試編寫算法將該線性表分割為 3個循環(huán)鏈表，其中每個循環(huán)鏈表表示的線性表中均只含一類字符? Status LinkList_Divide ( LinkList L, CiList &A,CiList &B,CiList &C)? 把單鏈表L的元素按類型分為三個循環(huán)鏈表.CiList為帶頭結點的單循環(huán)鏈

5、表類型? s=L->next;?A=(CiList*)malloc(sizeof(CiLNode);p=A;?B=(CiList*)malloc(sizeof(CiLNode);q=B;?C=(CiList*)malloc(sizeof(CiLNode);r=C;?/建立頭結點? while(s) if( 'a' <=s->data&& s->data <= 'z' |?'A' <=s->data&&a

6、mp;amp; s->data<= 2 )? p->next=s;p=s; else if( '0' <=s->data && s->data <= '9' )? q->next=s; q=s;else r->next=s; r=s;?s=s->next; /whilep->next=A;q->next=B;r->next=C;?/完成循環(huán)鏈表? Li

7、nkList_Divide6、寫一個利用層次遍歷方法遍歷任意一棵用二叉鏈表存儲的二叉樹 的算法。算法思想：設存儲于二叉鏈表的二叉樹T,并設置循環(huán)隊列Q。若T非空則根結點進隊。從T的根結點開始，反復做：當隊列非空，則出 隊訪問該結點*p。若*p有左子樹，則*p的左子結點進隊，若*p有右 子樹，則*p的右子結點進隊。算法：設置指針變量p指向當前處理的結點，Q為循環(huán)隊列。void lever( BrTree T)SQueue Q;if(T) EnQueue(Q, T); /T不空，則根結點進隊p=T;while(!Empty(Q) 當Q不空反復做下列操作DeQueue(Q, p); /隊首元素出隊存

8、于pprintf(*p); / 訪問結點 *pif (p->llink) EnQueue(Q,p->llink); 若*p 有左子樹，貝U *p 的左子 結點進隊if (p->rlink) EnQueue(Q,p->rlink);/ 若*p有右子樹，則*p的右子結點進隊試寫一個算法，在以鄰接矩陣方式存儲的有向圖G中求頂點i到頂點j的不含回路的、長度為k的路徑數(shù)。數(shù)據(jù)結構如下typedef int VRType;typedef struct ArcCell(VRType adj;/VRType是頂點關系類型，對無權圖，用1或0表示相鄰否；對

9、帶權圖，則為權值類型InfoType *info;/該弧相關信息的指針ArcCell,*AdjMatrix;typedef struct(VertexType *vexs;/ 頂點向量AdjMatrix arcs;/ 鄰接矩陣int vexnum,arcnum;圖的當前頂點數(shù)和弧數(shù)MGraph;2、設有5個數(shù)據(jù)do,for,if,repeat,while排在一個有序表中，其查找概率分別為 p1=0.2,p2=0.15,p3=0.1,p4=0.03,p5=0.01而查找它們之間不存 在 數(shù) 據(jù) 的 概 率 分 別 為q0=0.2,q1=0.15,q2=0.1,q3=0.03,q4=0.02,q5

10、=0.01doforifrepeat whileq0 p1 q1 p2 q2 p3 q3 p4 q4 p5q5(1)試分別畫出對該有序表采用順序查找和折半查找時的判定樹(2)分別計算順序查找和折半查找時查找成功和不成功的平均概率。圖鑒原圖?順序查找成功的平均概率：(0.2x 1+0.15X 2+0.1 x 3+0.03X 4+0.01 X 5) /(1+2+3+4+5)=0.97/15=0.06失敗的平均概率：(0.2X 1+0.15X 2+0.1 x 3+0.03X 4+0.02X 5+0.01 X 5)/(1+2+3+4+5+5)= 1.07/20=0.05?折半查找成功的平均概率：(0.

11、2X 2+0.15X 3+0.1 x 1+0.03X 2+0.01X3) /(1+2+2+3+3)=1.04/11=0.09失敗的平均概率：(0.2X 2+0.15X 3+0.1 x 3+0.03X 2+0.02X 3+0.01 X 3) /(2+2+3+3+3+3) =1.30/16=0.081、應用直接插入排序算法，對鍵值序列49, 38, 65, 97, 76, 13,27, 59從小到大進行排序，試寫出每趟排序的結果。解：第一趟：38,49,65,97,76,13,27,59第二趟：38,49,65,97,76,13,27,59第三趟：38,49,65,97,76,13,27,59第四

12、趟：38,49,65,76,97,13,27,59第五趟：13,38,49,65,76,97,27,59第六趟：13,27,38,49,65,76,97,59第七趟：13,27,38,49,59,65,76,972、設待排序記錄的關鍵字分別為28, 13, 72, 85, 39, 41, 6, 20按二分法插入排序已使前七個記錄有序，中間結果如下:613283941728520?1 =1m=4r=7試在此基礎上，沿用上述表達方式，給出繼續(xù)采用二分法插入第8個 記錄的比較過程。解：(6132839417285 )20?l =1m=4r=7(6132839417285 )20?l =1m=2r=3

13、(6132839417285 )20?l =3m=3r=3(6132839417285 )20r=2l=33、有一隨機數(shù)序列25, 84, 21, 46, 13, 27, 68, 35, 20,現(xiàn)采用某種方法對它們進行排序，其每趟排序的結果如下，該排序方法是 什么？初 始：25,84,21,46,13,27,68,35,20第一趟：20,13,21,25,46,27,68,35,84第二趟：13,20,21,25,35,27,46,68,84第三趟：13,20,21,25,27,35,46,68,84答：是快速排序4、若對序列(tang,deng,an, wan, shi, bai, fang

14、, liu)按字典順序進行排序，分別給出：(1)冒泡排序第一趟的結果(2)初始步長為4的希爾排序第一趟的結果(3)以第一個元素為分界元素的快速排序第一趟的結果(4)堆排序的初始堆解：(1) deng an tang shi bai fang liu wan2 2) shi bai an liu tang deng fang wan(3)( liu deng an fang shi bai ) tang (wan)(4)an deng bai liu shi tang fang wan5、給出關鍵字序列29,18,25,47,58,12,51,10汾別寫出按下列各種排序方法進行排序時的變化過程(

15、1)歸并排序：每歸并一次寫一個序列(2)快速排序：每劃分一次寫一個序列(3)堆排序：先建成一個堆，然后每次從堆頂取下一個元素后將堆調(diào)整一次(4)基數(shù)排序的分配和收集過程解：(1)歸并初始：29,18,25,47,58,12,51,10第一趟歸并：18,29,25,47,12,58,10,51第二趟歸并：18,25,29,47,10,12,51,58第三趟歸并：10,12,18,25,29,47,51,58(2)快速初始：29,18,25,47,58,12,51,10第一趟：10,18,25,12,29,58,51,47x:29第二趟：10,18,25,12,29,47,51,58x:10和58

16、第三趟：10,12,18,25,29,47,51,58x:18和47(3)堆(最小)初始：29,18,25,47,58,12,51,10建堆：10,18,12,29,58,25,51,47取堆頂 10,調(diào)整：12,18,25,29,58,47,51,10取堆頂 12,調(diào)整：18,29,25,51,58,47,12,10取堆頂 18,調(diào)整：25,29,47,51,58,18,12,10取堆頂 25,調(diào)整：29,51,47,58,25,18,12,10取堆頂 29,調(diào)整：47,51,58,29,25,18,12,10取堆頂 47,調(diào)整：51,58,47,29,25,18,12,10取堆頂 51,調(diào)

17、整：58,51,47,29,25,18,12,10取堆頂 58:58,51,47,29,25,18,12,10(3)堆(最大)初始：29,18,25,47,58,12,51,10建堆：58,47,51,29,18,12,25,10取堆頂 58,調(diào)整：51,47,25,29,18,12,10,58取堆頂 51,調(diào)整：47,29,25,10,18,12,51,58取堆頂 47,調(diào)整：29,18,25,10,12,47,51,58取堆頂 29,調(diào)整：25,18,12,10,29,47,51,58取堆頂 25,調(diào)整：18,10,12,25,29,47,51,58取堆頂 18,調(diào)整：12,10,18,2

18、5,29,47,51,58取堆頂 12,調(diào)整：10,12,18,25,29,47,51,58(4)基數(shù)初始：29,18,25,47,58,12,51,10第一趟分配：隊列01234567891051122547182958第一趟收集：10, 51, 12, 25, 47, 18, 58, 29第二趟分配：隊列012347891025475112295818第二趟收集：10, 12, 18, 25, 29, 47, 51,58二叉樹先序遍歷算法如下:void Preorder (BiTree T,void( *visit)(TElemType& e) /先序遍歷二叉樹if (T) if(visit(T->data);/ 訪問結點if(Preorder(T->lchild, visit); / 遍歷左子樹 if(Preorder(T->rchild, visit);/ 遍歷右子樹 return error;else return ok;已知n為大于等于零的整數(shù)，試寫出技術下列遞歸函數(shù)f(n)的遞歸和非遞歸算法#include <stdio.h>遞歸：int