數(shù)據(jù)結(jié)構(gòu)題目

1、數(shù)據(jù)結(jié)構(gòu)題目,設(shè)有一組初始記錄關(guān)鍵字序列( K1,K2,，Kn),要求設(shè)計(jì)一個(gè)算法能夠在 O(n)的時(shí)間復(fù)雜度內(nèi)將線性 表劃分成兩部分，其中左半部分的每個(gè)關(guān)鍵字均小于 Ki,右半部分的 每個(gè)關(guān)鍵字均大于等于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è)單鏈表中有僅三類字符的數(shù)據(jù)元素(大寫字母、數(shù)字和其它字符)， 要求利用原單鏈表中結(jié)點(diǎn)空間設(shè)計(jì)出三個(gè)單鏈表的算法，使每個(gè)單鏈表只包含同類字符。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.已知由一個(gè)線性鏈表表示的線性表中含有3類字符的數(shù)據(jù)元素(如，字母、數(shù)字和其他字符)，試編寫算法將該線性表分割為 3個(gè)循環(huán)鏈表，其中每個(gè)循環(huán)鏈表表示的線性表中均只含一類字符? Status LinkList_Divide ( LinkList L, CiList &A,CiList &B,CiList &C)? 把單鏈表L的元素按類型分為三個(gè)循環(huán)鏈表.CiList為帶頭結(jié)點(diǎn)的單循環(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;?/建立頭結(jié)點(diǎn)? 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、寫一個(gè)利用層次遍歷方法遍歷任意一棵用二叉鏈表存儲(chǔ)的二叉樹 的算法。算法思想：設(shè)存儲(chǔ)于二叉鏈表的二叉樹T,并設(shè)置循環(huán)隊(duì)列Q。若T非空則根結(jié)點(diǎn)進(jìn)隊(duì)。從T的根結(jié)點(diǎn)開始，反復(fù)做：當(dāng)隊(duì)列非空，則出 隊(duì)訪問(wèn)該結(jié)點(diǎn)*p。若*p有左子樹，則*p的左子結(jié)點(diǎn)進(jìn)隊(duì)，若*p有右 子樹，則*p的右子結(jié)點(diǎn)進(jìn)隊(duì)。算法：設(shè)置指針變量p指向當(dāng)前處理的結(jié)點(diǎn)，Q為循環(huán)隊(duì)列。void lever( BrTree T)SQueue Q;if(T) EnQueue(Q, T); /T不空，則根結(jié)點(diǎn)進(jìn)隊(duì)p=T;while(!Empty(Q) 當(dāng)Q不空反復(fù)做下列操作DeQueue(Q, p); /隊(duì)首元素出隊(duì)存

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

9、帶權(quán)圖，則為權(quán)值類型InfoType *info;/該弧相關(guān)信息的指針ArcCell,*AdjMatrix;typedef struct(VertexType *vexs;/ 頂點(diǎn)向量AdjMatrix arcs;/ 鄰接矩陣int vexnum,arcnum;圖的當(dāng)前頂點(diǎn)數(shù)和弧數(shù)MGraph;2、設(shè)有5個(gè)數(shù)據(jù)do,for,if,repeat,while排在一個(gè)有序表中，其查找概率分別為 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)試分別畫出對(duì)該有序表采用順序查找和折半查找時(shí)的判定樹(2)分別計(jì)算順序查找和折半查找時(shí)查找成功和不成功的平均概率。圖鑒原圖?順序查找成功的平均概率：(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、應(yīng)用直接插入排序算法，對(duì)鍵值序列49, 38, 65, 97, 76, 13,27, 59從小到大進(jìn)行排序，試寫出每趟排序的結(jié)果。解：第一趟：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、設(shè)待排序記錄的關(guān)鍵字分別為28, 13, 72, 85, 39, 41, 6, 20按二分法插入排序已使前七個(gè)記錄有序，中間結(jié)果如下:613283941728520?1 =1m=4r=7試在此基礎(chǔ)上，沿用上述表達(dá)方式，給出繼續(xù)采用二分法插入第8個(gè) 記錄的比較過(guò)程。解：(6132839417285 )20?l =1m=4r=7(6132839417285 )20?l =1m=2r=3

13、(6132839417285 )20?l =3m=3r=3(6132839417285 )20r=2l=33、有一隨機(jī)數(shù)序列25, 84, 21, 46, 13, 27, 68, 35, 20,現(xiàn)采用某種方法對(duì)它們進(jìn)行排序，其每趟排序的結(jié)果如下，該排序方法是 什么？初 始：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、若對(duì)序列(tang,deng,an, wan, shi, bai, fang

14、, liu)按字典順序進(jìn)行排序，分別給出：(1)冒泡排序第一趟的結(jié)果(2)初始步長(zhǎng)為4的希爾排序第一趟的結(jié)果(3)以第一個(gè)元素為分界元素的快速排序第一趟的結(jié)果(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、給出關(guān)鍵字序列29,18,25,47,58,12,51,10汾別寫出按下列各種排序方法進(jìn)行排序時(shí)的變化過(guò)程(

15、1)歸并排序：每歸并一次寫一個(gè)序列(2)快速排序：每劃分一次寫一個(gè)序列(3)堆排序：先建成一個(gè)堆，然后每次從堆頂取下一個(gè)元素后將堆調(diào)整一次(4)基數(shù)排序的分配和收集過(guò)程解：(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第一趟分配：隊(duì)列01234567891051122547182958第一趟收集：10, 51, 12, 25, 47, 18, 58, 29第二趟分配：隊(duì)列012347891025475112295818第二趟收集：10, 12, 18, 25, 29, 47, 51,58二叉樹先序遍歷算法如下:void Preorder (BiTree T,void( *visit)(TElemType& e) /先序遍歷二叉樹if (T) if(visit(T->data);/ 訪問(wèn)結(jié)點(diǎn)if(Preorder(T->lchild, visit); / 遍歷左子樹 if(Preorder(T->rchild, visit);/ 遍歷右子樹 return error;else return ok;已知n為大于等于零的整數(shù)，試寫出技術(shù)下列遞歸函數(shù)f(n)的遞歸和非遞歸算法#include <stdio.h>遞歸：int