數(shù)據(jù)結(jié)構(gòu)本期末綜合練習(xí)

1、數(shù)據(jù)結(jié)構(gòu)期末綜合練習(xí)2014年12月期末綜合練習(xí)一一、單項選擇題1 .單向鏈表所具備的特點(diǎn)是（）。A.可以隨機(jī)訪問任一結(jié)點(diǎn)B.占用連續(xù)的存儲空間C.插入刪除不需要移動元素D.可以通過某結(jié)點(diǎn)的指針域訪問其前驅(qū)結(jié)點(diǎn)2 .頭指針為head的帶頭結(jié)點(diǎn)的單向鏈表為空的判定條件是（）為真。A.head二二NULLB.head->next=NULLC.head->next=NULL;D.head->next!=NULL3 .設(shè)有一個長度為18的順序表，要在第6個元素之前插入一個元素（也就是插入元素作為新表的第6個元素），則移動元素個數(shù)為C.134 .設(shè)有一個長度為32 的順序表，要刪除第8

2、個元素需移動元素的個數(shù)為（25. 245 .棧和隊列的共同特點(diǎn)是A .都是線性結(jié)構(gòu).元素都可以隨機(jī)進(jìn)出C.都是先進(jìn)后出.都是先進(jìn)先出6 . 一個棧的進(jìn)棧序列是2,4, 6,8,10,則棧的不可能輸出序列是（）（進(jìn)棧出?？梢越惶孢M(jìn)行）oA. 2, 4, 6, 8, 10. 8, 6, 10, 2, 4C. 8, 10, 6, 4, 2. 10, 8, 6, 4, 27 .元素1,3,5,7按順序依次入隊列，按該隊列的出隊序列進(jìn)棧，該棧的可能輸出序列是）（進(jìn)棧出?？梢越惶孢M(jìn)行）。A.7,5,1,3.7,3,1,5C.5,1,3,7,7,5,3,18 .一個隊列的入隊序列是a,b,c,d,按該隊列的

3、可能輸出序列使各元素依次入棧，該棧的可能輸出序列是）。（進(jìn)棧出?？梢越惶孢M(jìn)行）。 c, a, b, d d, a, b, cA.d,c,b,aC.d,b,a,c9 .在一個不帶頭結(jié)點(diǎn)的鏈隊中，假設(shè)f和r分別為隊頭和隊尾指針，則對該隊列進(jìn)行出隊操作中并把結(jié)點(diǎn)的值保存在變量e中，其運(yùn)算為e二fdata;和（）。next;rnext=r; f next=f;Cf=fnext;D10 .在一個鏈隊中，假設(shè)f和r分別為隊頭和隊尾指針，P指向一個已生成的結(jié)點(diǎn)，現(xiàn)要為該結(jié)點(diǎn)的數(shù)據(jù)域賦值e,并使結(jié)點(diǎn)入隊的運(yùn)算為p->data=e;p->next二NULL;和（）。A.f->next=p;f=

4、p;B.r->next=p;r=p;C.p->next=r;r=p;D.p->next=f;f=p;11 設(shè)有一個對稱矩陣A,采用壓縮存儲的方式，將其下三角部分以行序?yàn)橹餍虼鎯Φ揭痪S數(shù)組B中（數(shù)組下標(biāo)從1開始），B數(shù)組共有45個元素，則該矩陣是（）階的對稱矩陣。A.15B.11C.10D.9ai,i），將其12設(shè)有一個24階的對稱矩陣A,采用壓縮存儲的方式（矩陣的第一個元素為三角部分以行序?yàn)橹餍虼鎯Φ揭痪S數(shù)組B中（數(shù)組下標(biāo)從1開始），則數(shù)組中第30號元素對應(yīng)于矩陣中的元素是（）A. aio.s B .&9,213 . F 列是 C 語言中" abcd321A

5、BCDA. 21ABCB.C. abcD14 .字符串a(chǎn)l= )oA. alC. a315.字符串a(chǎn)l= ).A. alC. a316.程序段chara=while( *!=m. 6D.BEIJING” , a2 =B. a2D. a4BEIJING” , a2 =B. a2D. a4English ”O(jiān)') n+; p+;B. 8aD . as ,58,2的子串的選項是()abcABCD"0321a"BEI , a3= BEFANGBEF , a3= BEFANG;char *p=a; intn=0;結(jié)果中,n的值是(C. 5D. 717 .一棵有20個結(jié)點(diǎn)采用鏈

6、式存儲的二叉樹中，共有（個指針域?yàn)榭铡?0. 1818 .在一棵二叉樹中，若編號為5的結(jié)點(diǎn)存在左孩子，則左孩子的順序編號為（）.10 C . 1119 .設(shè)一棵哈夫曼樹共有18個葉結(jié)點(diǎn)，則該樹有（. 12）個非葉結(jié)點(diǎn)。2,該樹結(jié)點(diǎn)中共有2020.設(shè)一棵采用鏈?zhǔn)酱鎯Φ亩鏄洌~結(jié)點(diǎn)外每個結(jié)點(diǎn)度數(shù)都為個指針域?yàn)榭?。則該樹有（）個葉結(jié)點(diǎn)。A.21.22C.9.1021如圖1所示的一個圖，若從頂點(diǎn)g出發(fā)，按深度優(yōu)先搜索法進(jìn)行遍歷，則可能得到的一種頂點(diǎn)序列為（）.gaebcfd D . gaedfcb22已知如圖2所示的一個圖,的一種頂點(diǎn)序列為（）若從頂點(diǎn)a出 發(fā)，按廣度優(yōu)先搜索法進(jìn)行遍歷，則可能得到

7、圖223線性表以（）方式存儲，能進(jìn)行折半查.關(guān)鍵字有序的找。B.關(guān)鍵字有序的順序.順序24 在有序表（10,23,32, 36, 53, 66, 68, 76,87, 90, 101, 120)中，用折半查找值 53時，經(jīng)（）次比較后查找成功。25.有一個長度為8的有序表，按折半查找對該表進(jìn)行查找，在等概率情況下查找成功的平均比較次數(shù)為（A.22/8.20/8.23/8D.21/826.有一個長度為11的有序表，按折半查找對該表進(jìn)行查找，在等概率情況下查找成功的平均比較次數(shù)為（）。A.29/11B.33/11C.26/11D.30/1127.排序算法中，從尚未排序序列中依次取出元素與已排序序列

8、（初始為空）中的元素進(jìn)行比較（要求比較次數(shù)盡量少），然后將其放入已排序序列的正確位置的方法是（）。A.折半插入排序B.直接插入排序C.歸并排序D.選擇排序28.設(shè)已有m個元素有序，在未排好序的序列中挑選第m+1個元素，并且只經(jīng)過一次元素的交換就使第m+1個元素排序到位，該方法是（）。A.堆排序B.簡單選擇排序C.快速排序D.歸并排序29.排序方法中，從未排序序列中挑選兀素，并將其依次放入已排序序列（初始為空）的一一端的方法，稱為（）排序。A.堆B.冒泡C.選擇D.快速30.一組記錄的關(guān)鍵字序列為（32,65,42,24,26,80），利用快速排序，以第一個關(guān)鍵字為分割元素，經(jīng)過一次劃分后結(jié)果為

9、（）。A.26,24,32,42,65,80BC.26,24,32,65,42,80D24,26,32,42,65,8026,24,32,80,42,65二、填空題1.廣義表(a,(a,b),d,e,(i,j),k)的長度是o2結(jié)構(gòu)中的數(shù)據(jù)元素存在一對多的關(guān)系稱為結(jié)構(gòu)。3.廣義表的(c,a,(a,b),d,e,(i,j),k)深度是。4棧的操作特點(diǎn)是o5.設(shè)順序隊列的類型為typedefstructElemTypedataFMaxSise;intfront,rear;Squeue;Squeue*sq;sq為指向順序隊列的指針變量，要進(jìn)行新元素x的入隊操作，按教課書約定，可用語句sq->d

10、atasq->rear=x;。6 .廣義表的（a,（a,b）,d,e,（i,j）,k）深度是。7 .序列4,2,5,3,8,6,采用冒泡排序算法，經(jīng)一趟冒泡后，序列的結(jié)果是。（按由小到大順序）8 .廣義表（a,b）,d,e,（i,j）,k）的長度是。9 .在對一組記錄（50,34,92,19,11,68,56,41,79）進(jìn)行直接插入排序（由小到大排序），當(dāng)把第7個記錄56插入到有序表時，為尋找插入位置需比較次。10.設(shè)順序隊列的類型為typedefstructElemTypedataMaxSise;intfront,rear;Squeue;Squeue*sq;sq為指向順序隊列的指針變

11、量，要進(jìn)行元素的出隊操作，并把元素賦給邊量X,按教科書約定，可用語句x=sq-datasq->front;和。11 .數(shù)據(jù)結(jié)構(gòu)中，可以由一個或多個數(shù)據(jù)項組成。12 .設(shè)順序隊列的類型為typedefstructElemTypedataLMaxSise;intfront,rear;Squeue;Squeue*sq;sq為指向順序隊列的指針變量，要進(jìn)行新元素x的入隊操作，按教課書約定，可用語句sq->datasq->rear=x;禾口。13 .循環(huán)隊列中，設(shè)front和rear分別為隊頭和隊尾指針，（最多元素為MaxSize,采用少用一個元素的模式），判斷循環(huán)隊列為滿的條件為為真

12、。14 .序列14,12,15,13,18,16,采用冒泡排序算法，經(jīng)一趟冒泡后，序列的結(jié)果是。（由小到大排序）15 .排序算法中，從尚未排序序列中依次取出元素與已排序序列（初始為空）中的元素依次進(jìn)行比較，然后將其放入已排序序列的正確位置的方法是o16 .數(shù)據(jù)結(jié)構(gòu)中，之間的抽象關(guān)系稱為邏輯結(jié)構(gòu)。17 .對稀疏矩陣進(jìn)行壓縮存儲，可采用三元組表，一個6行7列的稀疏矩陣A共有34個零元素，其相應(yīng)的三元組表共有個元素。18 .循環(huán)隊列中，設(shè)front和rear分別為隊頭和隊尾指針，（最多元素為MaxSize,），判斷循環(huán)隊列為空的條件為為真。19 .在雙向鏈表中，要刪除p所指的結(jié)點(diǎn)，可以先用語句（p-

13、>prior）->next=p->next;然后再用語句（p_>next）>prior=。20 .排序算法中，從尚未排序序列中依次取出元素與已排序序列（初始為空）中的元素進(jìn)行比較（要求比較次數(shù)盡量少），然后將其放入已排序序列的正確位置的方法是o21 .在雙向鏈表中，每個結(jié)點(diǎn)有兩個指針域，一個指向結(jié)點(diǎn)的直接后繼，另一個指向22 .對稀疏矩陣進(jìn)行壓縮存儲，可采用三元組表，矩陣元素cb,4對應(yīng)的三元組為o23 .把數(shù)據(jù)存儲到計算機(jī)中，并具體體現(xiàn)數(shù)據(jù)之間的邏輯結(jié)構(gòu)稱為結(jié)構(gòu)。24 .在雙向鏈表中，要刪除p所指的結(jié)點(diǎn)，其中所用的一條語句（p->next）->pri

14、or=p->prior;的功能是：使P所指結(jié)點(diǎn)的直接后繼的左指針指向o三、綜合題1 .設(shè)數(shù)據(jù)集合a=l,12,5,8,3,10,7,13,9）（1）依次取a中各數(shù)據(jù)，構(gòu)造一棵二叉排序樹。（2）說明如何依據(jù)此二叉樹得到a的有序序列。（3）對該二叉樹進(jìn)行查找，成功查找到7要進(jìn)行多少次元素間的比較？（4）給出對該二叉樹后序遍歷的序列。2 .設(shè)數(shù)據(jù)集合a二62,74,30,15,56,481）依次取a中各數(shù)據(jù)，構(gòu)造一棵二叉排序樹。2）為了成功查找到48需要進(jìn)行多少次元素間的比較3）給出對該二叉樹后序遍歷的序列。3 .設(shè)有序表為（2,5,11,12,30,48,58,70,78,79,90）,元素

15、的序號依次為1,2,3,11.（1）畫出對上述查找表進(jìn)行折半查找所對應(yīng)的判定樹（樹中結(jié)點(diǎn)用序號表示）（2）說明成功查找到元素2需要經(jīng)過多少次比較？（3） 說明不成功查找元素75需要經(jīng)過多少次比較？（4） 給出中序遍歷該折半查找判定樹的序列4.設(shè)有序表為（3,9,15,26,38,41,53,74,81,96,97,99）,元素的序號依次為1,2,12o（1）畫出對上述有序表進(jìn)行折半查找所對應(yīng)的判定樹（樹結(jié)點(diǎn)用序號表示）。（2）設(shè)查找5號元素（38）,需要進(jìn)行多少次元素間的比較才能確定不能查到，依次和哪些元素進(jìn)行了比較？（要求寫出具體元素）。（3）給出后序遍歷該二叉樹的序列。（4）給出中序遍歷該

16、二叉樹的序列。四、程序填空題1.設(shè)有一個不帶頭結(jié)點(diǎn)的單向鏈表，頭指針為head,p、prep是指向結(jié)點(diǎn)類型的指針，該鏈表在輸入信息時不慎把相鄰兩個結(jié)點(diǎn)的信息重復(fù)輸入，以下程序段是在該單向鏈表中查找這相鄰兩個結(jié)點(diǎn)，把該結(jié)點(diǎn)的數(shù)據(jù)域data打印出來，并把其中之一從鏈表中刪除，填寫程序中的空格。prep二head;p=prep->next;while（p->data!=prep->data）prep=p;（1）printf("min=%d",(2);prep->next=(3)2.學(xué)生信息存放在結(jié)構(gòu)數(shù)組中，每個數(shù)組元素存放一個學(xué)生的信息，下標(biāo)從0到n-lo

17、數(shù)組元素按學(xué)號num由小到大有序排列，以下函數(shù)在a0到an-l中，用折半查找算法查找關(guān)鍵字num等于k的記錄，查找成功返回該記錄的下標(biāo)(數(shù)組元素的下標(biāo))。失敗時返回-1,完成程序中的空格。typedefstructcharsex;intnum;INODE;intBinary_Search(NODEa,intn,intk)intlow,mid,high;low=0;high=n-l;while(1)(mid二(low+high)/2;if(amid,num=二k)return(2)elseif(3)low=mid+l;else(4);)return_1;3.以下程序是折半插入排序的算法(按記錄中

18、關(guān)鍵字key排序)設(shè)待排序的記錄序列存放在a中，以a0作為輔助工作單元，以下程序是要把a(bǔ)i插入到已經(jīng)有序的序列al,倉ij中。voidbinsort(NODEa,intn)intx,i,j,s,k,m;for(i=2;i=(1);i+)a0=ai;x=ai.key;s=l;j=i-l;while(s=j)m=_(2)if(x<am.key)(3)else(4)for(k=i-l;k=j+1;k)(5)=ak;aj+l=a0;4.以下函數(shù)是二叉排序樹的查找算法，若二叉樹為空，則返回根結(jié)點(diǎn)的指針，否則，返回值是指向樹結(jié)點(diǎn)的結(jié)構(gòu)指針p(查找成功p指向查找到的樹結(jié)點(diǎn)，不成功，則p指向?yàn)镹ULL)

19、,完成程序中的空格。structbnodeintkey;structbnode*left;structbnodebright;);typedefstructbnodeBnodeBnode*BSearch(Bnode*bt,intk)/*bt用于接收二叉排序樹的根結(jié)點(diǎn)的指針，k用以接收要查找的關(guān)鍵字*/Bnode*p;if(bt=NULL)return(bt);while(p->key!=_)if(k<p->key)；else(4);if(p=NULL)break;returnp;期末綜合練習(xí)一答案一、單項選擇題1. C2.B3.C4.D5.A6.B7.D8.A9.C10.B1

20、1.D12.C13.A14.A15.B16.D17.A18.B19.C20.D21.D22.B23.B24.D25.D26.B27.A28.B29.C30.A二、填空題1.52. 樹形3. 34. 先進(jìn)后出5. sq->rear+;6. 37. 2,4,3,5,6,88. 49. 310. sq->fronf+;11. 數(shù)據(jù)元素12. sq->rear+;13. front=(rear+l)%MaxSize14. 12,14,13,15,16,1815. 直接插入排序16. 數(shù)據(jù)元素17.818. front=rear19. p->prior；20. 折半插入排序21.

21、 結(jié)點(diǎn)的直接前驅(qū)22. (3,4,a3,4)23. 存儲24. P所指結(jié)點(diǎn)的直接前驅(qū)三、綜合應(yīng)用題1.(1)圖3中序遍歷1,3,5,7,8,9,10,12,13(3)5次(4)3,7,9,10,8,5,13,12,1圖4(4) 4次(5) 15,48,56,30,74,62(1)圖53次4次(4)1,2,3,4,5,6,7,8,9,10,11(序號)圖I6(2) 4次41,15,26,38(3) 2(9),1(3),5(38),4(26),3(15),8(74),7(53),10(96),12(99),11(97),9(81),6(41)(4) 1(3),2(9),3(15),4(26),5(

22、38),6(41),7(53),8(74),9(81),10(96),11(97),12(99)四、程序填空題1.(1) p=p->next;(2) p->data或prep->data(3) p->next;(l)low<=highmid(4) amid.num<k(5) high=mid-1;3.(1) n(s+j)/2;j=m-l;(4) s=m+l;ak+lp二bt;(2) k(3) p=p->left(4) p=p->right期末綜合練習(xí)二一、單項選擇題1 .數(shù)據(jù)的存儲結(jié)構(gòu)包括數(shù)據(jù)元素的表示和（）。A.數(shù)據(jù)處理的方法B.數(shù)據(jù)元素間的關(guān)

23、系的表示C.相關(guān)算法D.數(shù)據(jù)元素的類型2 .下面關(guān)于線性表的敘述中，錯誤的是（）A.線性表采用順序存儲，必須占用一片連續(xù)的存儲空間B.線性表采用順序存儲，進(jìn)行插入和刪除操作，不需要進(jìn)行數(shù)據(jù)元素間的移動C.線性表采用鏈?zhǔn)酱鎯?，不必占用連續(xù)的存儲空間D.線性表采用鏈?zhǔn)酱鎯?，進(jìn)行插入刪除操作，不需要移動元素3 .設(shè)有一個長度為22的順序表，要刪除第8個元素需移動元素的個數(shù)為（）。A.15B.22C.14D.234 .設(shè)有一個長度為28的順序表，要在第12個元素之前插入一個元素（也就是插入元素作為新表的第12個元素），則移動元素個數(shù)為（）。A.12B.17C.13D.115 .元素2,6,10,14按

24、順序依次進(jìn)棧，按該棧的可能輸出序列依次入隊列，該隊列的不可能輸出序列是是（）。（進(jìn)棧出?？梢越惶孢M(jìn)行）。A.14,10,6,2.2,6,10,14C.14,10,2,6.6,2,14,106.元素2,4,6,8按順序依次進(jìn)棧，則該棧的不可能輸出序列是（）（進(jìn)棧出?？梢越惶孢M(jìn)行）。A.8,6,4,2.2,4,6,8C.4,2,8,6top的鏈棧進(jìn)行進(jìn)棧操.8,6,2,4作，設(shè)P為指向待7,對一個棧頂指針為進(jìn)棧的結(jié)點(diǎn)的指針，把e的值賦值給該結(jié)點(diǎn)的數(shù)據(jù)域，然后使該結(jié)點(diǎn)進(jìn)棧，則執(zhí)行（）。Ap->data=e;p=top->next;top二topnext;Bp->data=e;p-&

25、gt;next=top;top=p;C.p->data=e;top二p;D-p->data=e;p->next=top->next;top二p;8.對一個棧頂指針為top的鏈棧進(jìn)行出棧操作，用變量e保存棧頂元素的值，則執(zhí)行（）。A.e二top->next;top->data=e;Be=top->data;top=top->next;C.top=top->next;e=top->data;Dtop=top->next;e=data;9.對不帶頭結(jié)點(diǎn)的單向鏈表，判斷是否為空的條件是（）（設(shè)頭指針為head）oA.head=NULLB

26、head->next=NULLC. head->next= =head10.在一個尾指針為 rear一個結(jié)點(diǎn)，可執(zhí)行（. head =NULLA . rear next= s; snext=rear next B . rear next=snext;C. rear=s next11.設(shè)有一個25階的對稱矩陣A （矩陣的第一個元素為s next=rear心人next ; rear next=s;采用壓縮存儲的方式，將其F三角部分以行序?yàn)橹餍虼鎯Φ揭痪S數(shù)組B中Q.i, i ） （數(shù)組下標(biāo)從1開始），則矩陣中元素a7,5在一維數(shù)組B中的下標(biāo)是（A. 34. 1412.設(shè)有一個28階的對稱

27、矩陣A （矩陣的第一個元素為采用壓縮存儲的方式，將其三角部分以行序?yàn)橹餍虼鎯Φ揭痪S數(shù)組中（數(shù)組下標(biāo)從1開始），則數(shù)組中第40的不帶頭結(jié)點(diǎn)的單循環(huán)鏈表中，插入一個S所指的結(jié)點(diǎn)，并作為第）。號元素對應(yīng)于矩陣中的元素是（A. Si0,813.數(shù)組a經(jīng)初始化char a=ag,4EnglishC. 39,5a7中存放的是De5(as,A.字符串的結(jié)束符B.字符hC. '' hD.14.數(shù)組a經(jīng)初始化char a=al中存放的是shA.字符nB.“ Engli字符ED.C.n15.設(shè)主串為"ABcCDABcdEFaB”以下模式串能與主串成功匹配的是（A. aBcB.BCdC.A

28、BC16.程序段char a=while( *p !=English ” ; char *p=a; int n=0;0, ) n+; P+;結(jié)果中,P指向(A.字符hB. a17.c.字符串的結(jié)束符D. 7設(shè)一棵哈夫曼樹共有11個非葉結(jié)點(diǎn)，則該樹有（）個葉結(jié)點(diǎn)。A.22o10.1118 .在一棵二叉樹中，編號為17的結(jié)點(diǎn)的雙親結(jié)點(diǎn)的的順序編號為（A.34.7C.9.819 .一棵具有38個結(jié)點(diǎn)的完全二叉樹，最后一層有（）個結(jié)點(diǎn)。.5.62該樹結(jié)點(diǎn)中共有2020 .設(shè)一棵采用鏈?zhǔn)酱鎯Φ亩鏄?，除葉結(jié)點(diǎn)外每個結(jié)點(diǎn)度數(shù)都為個指針域?yàn)榭?。則該樹共有（）個非葉子結(jié)點(diǎn)C.9D.10A.21B.22a網(wǎng).一

29、V出發(fā)，按廣度優(yōu)先搜索法進(jìn)行遍歷，則可能21 .已知如圖1所不得的一個圖，若從頂點(diǎn)到的一種頂點(diǎn)序列為（)OA . V0V1V2WV7V1V5V8B.V0V1V2V3V4V5V8V6V.V0V1V2V3V4V8V5V6MC . V0V1V2V3V4V5V6MVSD22 .已知如圖1所示的一個圖，若從頂點(diǎn)V0出發(fā)，按深度優(yōu)先法進(jìn)行遍歷，則可能得到的一種頂點(diǎn)序列為（）。A.V0V1V2VVV5V3V6V7B.W1W4V5V3V3V6V7C-VoViV2V4V8V3V5V5V7D.VO'VbV5V7V2V45V323 .在有序表（10,14,34,43,47,64,75,80,90）中，用折半

30、查找法查找值80時，經(jīng)（）次比較后查找成功。A.4B.2C.3D.524 .對（）進(jìn)行中序遍歷，可以使遍歷所得到的序列是有序序列。A.完全二叉樹B.二叉排序樹C.滿二叉樹排D.哈夫曼樹25 .排序算法中，從尚未排序序列中依次取出元素與已排序序列（初始為空）中的元素進(jìn)行比較，然后將其放入已排序序列的正確位置的方法是（）。A.冒泡排序B.直接插入排序C.歸并排序D.選擇排序26 .有一個長度為7的有序表，按折半查找對該表進(jìn)行查找，在等概率情況下查找成功的平均比較次數(shù)為（）。A.17/7B.18/7C.21/7D.20/727.一組記錄的關(guān)鍵字序列為（22,55,32,14,16,60），利用快速排

31、序，以第一個關(guān)鍵字A.16,14,22,55,32,60B.16,14,22,32,55,60C.16,14,22,60,32,55D.14,16,22,32,55,6028.排序方法中，從未排序序列中挑選兀素，并將其依次放入已排序序列（初始為空）的一一端的方法，稱為（）排序。A.堆B.冒泡C.選擇D.快速29一組記錄的關(guān)鍵字序列為（80,57,41,39,46,47），利用堆排序（堆頂元素是最小元素）的方法建立的初始堆為（80, 41, 57A.39,46,41,57,80,47B.39,47,46,C. 41, 39, 46, 47, 57, 80 D30. 一組記錄的關(guān)鍵字序列為(12,

32、45,分割兀素，經(jīng)過一次劃分后結(jié)果為(A . 6, 4, 12, 45, 22, 50BC. 6, 4, 12, 50, 22, 45D.39,80,46,47,41,5722,4,6,50),利用快速排序，以第一個關(guān)鍵字為)O.6,4,12,22,45,50.4,6,12,22,45,50二、填空題1把數(shù)據(jù)存儲到計算機(jī)中，并具體體現(xiàn)數(shù)據(jù)之間的邏輯結(jié)構(gòu)稱為結(jié)構(gòu)。2結(jié)構(gòu)中的數(shù)據(jù)元素存在一對一的關(guān)系稱為結(jié)構(gòu)。3從一個棧頂指針為h的鏈棧中刪除一個結(jié)點(diǎn)時，用x保存被刪結(jié)點(diǎn)的值，可執(zhí)行x=h->data;和。（結(jié)點(diǎn)的指針域?yàn)閚ext）o4向一個棧頂指針為h的鏈棧中插入一個s所指結(jié)點(diǎn)時，可執(zhí)行和h=

33、s;操作。（結(jié)點(diǎn)的指針域?yàn)閚ext）5.廣義表的（a,d,e,（i,j）,k）表尾是。6廣義表的（a,a,b,d,e,（i,j）,k）表頭是。7廣義表的（a,c）,a,b,d,e,（I,j）,k）表頭是。8 .廣義表的（a,c）,d,（e,i,j,k）表尾是。9 .設(shè)順序隊列的類型為typedefstructElemTypedataMaxSise;intfront,rear;Squeue;Squeue*sq;sq為指向順序隊列的指針變量，要進(jìn)行元素的出隊操作，并把元素賦給變量X,按教課書約定，可用語句x二sq->datasq-front;和。10 .設(shè)順序隊列的類型為typedefstr

34、uctElemTypedataMaxSise;intfront,rear;Squeue;Squeue*sq;sq為指向順序隊列的指針變量，要進(jìn)行新元素x的入隊操作，按教科書約定，可用語句sq->datasq->rear=x;禾口。11,對20個元素的序列用冒泡排法進(jìn)行排序，第5趟冒泡共需要進(jìn)行次元素間的比較。在對一組記錄（由小到大排序），當(dāng)12.對16個元素的序列用冒泡排法進(jìn)行排序，共需要進(jìn)行趟冒泡。13.(5,7,3,1,2,6,4,10,9,8,16,13,18,17)進(jìn)行直接插入排序?yàn)榉指钤?，?jīng)過一次劃分后結(jié)果為（)O把第10個記錄8插入到有序表時，為尋找插入位置需比較次。

35、14 .在對一組記錄(50,34,92,19,11,68,56,41,79)進(jìn)行直接插入排序(由小到大排序)，當(dāng)把第8個記錄41插入到有序表時，為尋找插入位置需比較次。15 .從數(shù)據(jù)結(jié)構(gòu)的角度，城市間的交通線路的關(guān)系屬于結(jié)構(gòu)。16 .數(shù)據(jù)的在計算機(jī)中的表示稱為物理結(jié)構(gòu)。17 .循環(huán)隊列用a0,a7的一維數(shù)組存放隊列元素，(采用少用一個元素的模式),設(shè)front和rear分別為隊頭和隊尾指針，且front和rear的值分別為2和7,當(dāng)前隊列中的元素個數(shù)是18 .循環(huán)隊列用a0,a5的一維數(shù)組存放隊列元素，(采用少用一個元素的模式),設(shè)front和rear分別為隊頭和隊尾指針，且front和rea

36、r的值分別為3和0,當(dāng)前隊列中的元素個數(shù)是o19 .對n個整數(shù)用冒泡法進(jìn)行排序，某趟冒泡中未進(jìn)行元素間的，說明n個元素已排好序。20 .設(shè)已有m個元素有序，在未排好序的序列中挑選第m+1個元素，并且只經(jīng)過一次元素的交換就使第m+1個元素排序到位，該方法是。21 .對稀疏矩陣進(jìn)行壓縮存儲，可采用三元組表，每個非零元素對應(yīng)的三元組包括的三項信息是行下標(biāo)、列下標(biāo)和o22 .對稀疏矩陣進(jìn)行壓縮存儲，可采用三元組表，一個6行7列的稀疏矩陣A相應(yīng)的三元組表共有8個元素,則矩陣A共有個零元素。23 .在雙向鏈表中，要刪除p所指的結(jié)點(diǎn)，其中所用的一條語句(p->prior)->next=p->

37、;next;的功能是：使P所指結(jié)點(diǎn)的直接前驅(qū)的右指針指向o24 .在雙向鏈表中，要刪除p所指的結(jié)點(diǎn)，可以先用語句(p->next)->prior=(p->prior);然后再用語句(p->prior)->next=。三、綜合題1設(shè)數(shù)據(jù)集合a=52,20,46,38,5,64,40)(1)依次取a中各數(shù)據(jù)，構(gòu)造一棵二叉排序樹。(2)對該二叉樹進(jìn)行查找，成功查找到38,和46各要進(jìn)行多少次元素間的比較?(3)給出按后序遍歷該二叉排序樹的序列。2對給定的數(shù)列b=6,15,3,7,19,8,5,17,4)(1)依次取b中各數(shù)據(jù)，構(gòu)造一棵二叉排序樹(2)給出按中序遍歷該二叉

38、排序樹的序列(3)給出按后序遍歷二叉排序樹的序列(4)畫出在二叉樹中刪除結(jié)點(diǎn)3后的樹結(jié)構(gòu)3. (1)設(shè)根為第1層，對給定權(quán)值1,3,4,4,5,6,構(gòu)造深度為5的哈夫曼樹。提示：構(gòu)造中當(dāng)出現(xiàn)被選的結(jié)點(diǎn)值有多個相等時，可嘗試不同組合，以得到要求的樹的深度。求樹的帶權(quán)路徑長度。給出對上述哈夫曼樹中序遍歷得到的的序列(4) 一棵哈夫曼樹有n個非葉結(jié)點(diǎn)，構(gòu)造該樹共有多少個權(quán)重值？簡述理由？4. (1)以4,5,6,13,11,12作為葉結(jié)點(diǎn)的權(quán)，構(gòu)造一棵哈夫曼樹。(2)給出相應(yīng)權(quán)重值葉結(jié)點(diǎn)的哈夫曼編碼。(3) 一棵哈夫曼樹有n個葉結(jié)點(diǎn)，該樹共有多少個結(jié)點(diǎn)？簡述理由？(4) 給出對上述哈夫曼樹中序遍歷的

39、序列。四、程序填空題1 .職工體檢表存放在結(jié)構(gòu)數(shù)組中，要求以工資號num為關(guān)鍵字進(jìn)行排序，以下函數(shù)用直接選擇排序算法，對an中的記錄進(jìn)行排序，完成程序中的空格。typedefstructintage;intnum;charsex;NODE;voidseisort(NODEa,intn)inti,j,k;NODEtemp;for(i=l;i<=n-1;i+)k=i;for(j=i+l;j<=(1);j+)if(aj.num<_(2)k=j;if(i!=k)temp=ai;；(4)2 .職工信息存放在結(jié)構(gòu)數(shù)組中，每個數(shù)組元素存放一個學(xué)生的信息，下標(biāo)從1到n,以a0作為輔助工作單元?，F(xiàn)要以職工的工資號num為關(guān)鍵字進(jìn)行排序，采用折半插入排序的算法，以下程序是要把a(bǔ)i插入到已經(jīng)有序的序列al,-ai-l中，(i=2,3,4,n)。typedefstructcharsex;intnum;NODE;voidbinsort(NODEa,intn)intx,i,j,s,k,m;for(i=2;i<=(1).j+)a0=ai：x=ai.num;s=1;j=