1、數(shù)據(jù)結(jié)構(gòu)（本）期末綜合練習(xí)2015年11月綜合練習(xí)一一、單項(xiàng)選擇題 1.對(duì)稀疏矩陣進(jìn)行壓縮存儲(chǔ),可采用三元組表，一個(gè)10 行8列的稀疏矩陣A共有73 個(gè)零元素，其相應(yīng)的三元組表共有( C )個(gè)元素。 A8 B80 C7 D10 2. 對(duì)稀疏矩陣進(jìn)行壓縮存儲(chǔ),可采用三元組表，一個(gè)10 行8列的稀疏矩陣A，其相應(yīng)的 三元組表共有6個(gè)元素，矩陣A共有( C )個(gè)零元素。 A8 B72 C74 D10 3.字符串( A )是“abcd321ABCD”的子串。A. “21AB” B. “abcD” C. “aBCD” D. “321a” 4. 程序段 char a =“abdcacdef”; char

2、*p=a; int n=0; while( *p!=0) n+; p+; 結(jié)果中,n的值是（ D ）。 A. 6 B.8 C. 7 D.9 5.棧和隊(duì)列的共同特點(diǎn)是（ A ）。 A都是操作受限的線(xiàn)性結(jié)構(gòu) B元素都可以隨機(jī)進(jìn)出 C都是先進(jìn)后出 D都是先進(jìn)先出 6. 10,6,2,1按順序依次進(jìn)棧，該隊(duì)列的可能輸出序列是（ A ）。 (進(jìn)棧出?？梢越惶孢M(jìn)行）。 A6,10,1,2 B2,10,6,1 C6,1,10,1 D1,6,10,27. 在一個(gè)鏈隊(duì)中，假設(shè)f和r分別為隊(duì)頭和隊(duì)尾指針，p指向一個(gè)新結(jié)點(diǎn),要為結(jié)點(diǎn)p 所指結(jié)點(diǎn)賦值x,并入隊(duì)的運(yùn)算為p-data=x; p-next=NULL;（ B

3、 ）。 A. f-next=p; f=p; B r-next=p;r=p; C r=p; p-next=r; D p-next=f;f=p; 8. 對(duì)一個(gè)棧頂指針為top的鏈棧進(jìn)行出棧操作，用變量e保存棧頂元素的值 ，則執(zhí)行 ( B ）。 Ae= top-next; top-data=e; Be=top-data; top=top-next; Ctop=top-next; e=top-data; Dtop=top-next; e=data; 9. 數(shù)據(jù)結(jié)構(gòu)中，與所使用的計(jì)算機(jī)無(wú)關(guān)的是數(shù)據(jù)的( A ) 結(jié)構(gòu)。A.邏輯 B.存儲(chǔ) C.邏輯與存儲(chǔ) D.物理 10. 算法的時(shí)間復(fù)雜度與( A )有關(guān)。

4、 A. 算法本身 B. 所使用的計(jì)算機(jī) C. 算法的程序設(shè)計(jì) D. 數(shù)據(jù)結(jié)構(gòu)11順序表所具備的特點(diǎn)之一是（ A ）。 A可以隨機(jī)訪(fǎng)問(wèn)任一結(jié)點(diǎn) B不需要占用連續(xù)的存儲(chǔ)空間 C插入元素的操作不需要移動(dòng)元素 D刪除元素的操作不需要移動(dòng)元素12在一個(gè)單向鏈表中,在p所指結(jié)點(diǎn)之后插入一個(gè)s所指的結(jié)點(diǎn)時(shí)，可執(zhí)行 s-next=p-next; 和（ D ）。 Ap= s; B p-next=s-next; Cp=s-next D p-next=s; 13. 數(shù)據(jù)元素是數(shù)據(jù)的基本單位，它（ C ）。 A只能有一個(gè)數(shù)據(jù)項(xiàng)組成 B至少有二個(gè)數(shù)據(jù)項(xiàng)組成 C可以是一個(gè)數(shù)據(jù)項(xiàng)也可以由若干個(gè)數(shù)據(jù)項(xiàng)組成 D至少有一個(gè)數(shù)據(jù)項(xiàng)

5、為指針類(lèi)型 14. 一種邏輯結(jié)構(gòu)在存儲(chǔ)時(shí) （ C）。 A只要存儲(chǔ)數(shù)據(jù)元素間的關(guān)系 B只能采用一種存儲(chǔ)結(jié)構(gòu) C可采用不同的存儲(chǔ)結(jié)構(gòu) D只要存儲(chǔ)數(shù)據(jù)元素的值 15設(shè)有頭指針為head的非空的單向鏈表, 指針p指向其尾結(jié)點(diǎn), 要使該單向鏈表成為單向循環(huán)鏈表,則可利用下述語(yǔ)句（C ）。 Ap =head; Bp=NULL; Cp-next =head; Dhead=p; 16.單向鏈表所具備的特點(diǎn)是( C )。A.可以隨機(jī)訪(fǎng)問(wèn)任一結(jié)點(diǎn) B.占用連續(xù)的存儲(chǔ)空間 C.插入刪除不需要移動(dòng)元素 D.可以通過(guò)某結(jié)點(diǎn)的指針域訪(fǎng)問(wèn)其前驅(qū)結(jié)點(diǎn) 17. 在線(xiàn)性表的順序結(jié)構(gòu)中，以下說(shuō)法正確的是（C ）。 A邏輯上相鄰的元

6、素在物理位置上不一定相鄰 B數(shù)據(jù)元素是不能隨機(jī)訪(fǎng)問(wèn)的 C邏輯上相鄰的元素在物理位置上也相鄰 D進(jìn)行數(shù)據(jù)元素的插入、刪除效率較高 18.數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)內(nèi)存中的表示是指 ( B ) 。 A數(shù)據(jù)元素之間的關(guān)系 B數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu) C數(shù)據(jù)元素的類(lèi)型 D數(shù)據(jù)的邏輯結(jié)構(gòu)19.對(duì)鏈表, 以下敘述中正確的是（ A ）。 A不能隨機(jī)訪(fǎng)問(wèn)任一結(jié)點(diǎn) B結(jié)點(diǎn)占用的存儲(chǔ)空間是連續(xù)的 C插入刪除元素的操作一定要要移動(dòng)結(jié)點(diǎn) D可以通過(guò)下標(biāo)對(duì)鏈表進(jìn)行直接訪(fǎng)問(wèn) 20.下面關(guān)于線(xiàn)性表的敘述中,錯(cuò)誤的是( B )。 A . 線(xiàn)性表采用順序存儲(chǔ),必須占用一片連續(xù)的存儲(chǔ)空間。 B. 線(xiàn)性表采用順序存儲(chǔ),進(jìn)行插入和刪除操作,不需要進(jìn)行數(shù)

7、據(jù)元素間的移動(dòng)。 C. 線(xiàn)性表采用鏈?zhǔn)酱鎯?chǔ)，不必占用連續(xù)的存儲(chǔ)空間。 D. 線(xiàn)性表采用鏈?zhǔn)酱鎯?chǔ)，進(jìn)行插入刪除操作，不需要移動(dòng)元素21 .設(shè)有一個(gè)長(zhǎng)度為35的順序表，要在第5個(gè)元素之前插入1個(gè)元素（也就是插入元素 作為新表的第5個(gè)元素），則移動(dòng)元素個(gè)數(shù)為（B ）。 A30 B31 C. 5 D6 22 .設(shè)有一個(gè)長(zhǎng)度為18的順序表，要在第5個(gè)元素之前插入1個(gè)元素（也就是插入元素作為新表的第5個(gè)元素），則移動(dòng)元素個(gè)數(shù)為（B ）。 A15 B14 C. 5 D6 23設(shè)有一個(gè)長(zhǎng)度為40的順序表，要?jiǎng)h除第10個(gè)元素(下標(biāo)從1開(kāi)始)需移動(dòng)元素的個(gè)數(shù)為（ C ）。 A11 B10 C30 D31 24設(shè)有

8、一個(gè)長(zhǎng)度為25的順序表，要?jiǎng)h除第10個(gè)元素(下標(biāo)從1開(kāi)始)需移動(dòng)元素的個(gè)數(shù)為（ C ）。 A10 B17 C15 D16 25設(shè)有一個(gè)25階的對(duì)稱(chēng)矩陣A，采用壓縮存儲(chǔ)的方式，將其下三角部分以行序?yàn)橹餍虼鎯?chǔ)到一維數(shù)組B中（數(shù)組下標(biāo)從1開(kāi)始），則矩陣中元素a7,5在一維數(shù)組B中的下標(biāo)是（ C ）。A25 B24 C26 D27 26設(shè)有一個(gè)18階的對(duì)稱(chēng)矩陣A，采用壓縮存儲(chǔ)的方式，將其下三角部分以行序?yàn)橹餍虼鎯?chǔ)到一維數(shù)組B中（數(shù)組下標(biāo)從1開(kāi)始），則矩陣中元素a10,8在一維數(shù)組B中的下標(biāo)是（ D ）。A62, B63 C51 D53 27線(xiàn)性表在存儲(chǔ)后,如果相關(guān)操作中有要求:利用已知的指向某結(jié)點(diǎn)的指

9、針或序號(hào),訪(fǎng)問(wèn)該結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)，則采用（A ）的存儲(chǔ)方式是不可行的。 A單向鏈表 B雙向鏈表 C單向循環(huán)鏈表 D順序表 28在一個(gè)尾指針為rear的不帶頭結(jié)點(diǎn)的單循環(huán)鏈表中,插入一個(gè)s所指的結(jié)點(diǎn),并作為第一個(gè)結(jié)點(diǎn)，可執(zhí)行snext=rearnext ;和（ D ）。 A rearnext= snext; B rear =snext; C rear=s; D rearnext=s; 29在一棵二叉樹(shù)中，若編號(hào)為i的結(jié)點(diǎn)存在左孩子,i結(jié)點(diǎn)的左孩子的順序編號(hào)為（ B ）。 Ai/2.0 B2*i C2*i+1 Di+2 30在一棵二叉樹(shù)中，若編號(hào)為15的結(jié)點(diǎn)是其雙親結(jié)點(diǎn)的右孩子，則雙親結(jié)點(diǎn)的順序編號(hào)

10、為（D ）。 A30 B8 C31 D7 二、填空題1. 廣義表( ( b,a,c) ,c ,d , f , e , ( (i , j ) , k ) ) 的長(zhǎng)度是_ 6_。 2. 結(jié)構(gòu)中的元素之間存在一對(duì)多的關(guān)系是_樹(shù)形_結(jié)構(gòu)。3. 數(shù)據(jù)結(jié)構(gòu)中，數(shù)據(jù)元素之間的抽象關(guān)系稱(chēng)為_(kāi)邏輯_結(jié)構(gòu)。 4. 結(jié)構(gòu)中的元素之間存在多對(duì)多的關(guān)系是 _圖狀_結(jié)構(gòu) 。5. 棧的操作特點(diǎn)是后進(jìn)_先出_ 。 6. 循環(huán)隊(duì)列的最大存儲(chǔ)空間為MaxSize ,若隊(duì)頭指針front，隊(duì)尾指針rear，采用少用一個(gè) 存儲(chǔ)空間以有效地判斷?？栈驐M(mǎn)，隊(duì)空的判定條件為_(kāi) rear=front為真_ 。7. 廣義表( b,a,c)

11、,c ,d , f , e ,( (i , j ) , k ) ) 的表頭是_（b,a,c）_。 8. 廣義表( ( b,a,c) ,c ,d , f , e , ( (i , j ) , k ) ) 的長(zhǎng)度是_ 6_。 9. 設(shè)有一個(gè)長(zhǎng)度為18的順序表 , 第8號(hào)元素到第18號(hào)元素依次存放的值為8,9,18. 某人想要?jiǎng)h除第8號(hào)元素，程序中他的做法是用語(yǔ)句for(i=18;i=9;i-)ai-1=ai; 即從第18號(hào)元素開(kāi)始, 直到第9號(hào)元素,每個(gè)元素依次向前(左)移動(dòng)1個(gè)位置.事實(shí)上這 樣做是錯(cuò)誤的.其結(jié)果新表中第9號(hào)元素的值為_(kāi) 18 _。 10要求在n個(gè)數(shù)據(jù)元素中找值最大的元素，其基本

12、操作為元素間的比較。算法的時(shí)間復(fù)雜 度為_(kāi) O(n)_ 。11. 一棵二叉樹(shù),有1個(gè)2度結(jié)點(diǎn),，2個(gè)1度結(jié)點(diǎn)，則該樹(shù)共有 _ 5_個(gè)結(jié)點(diǎn)。12一棵有8個(gè)葉結(jié)點(diǎn)的二叉樹(shù)，其1度結(jié)點(diǎn)的個(gè)數(shù)為3，則該樹(shù)共有 _ 18_個(gè)結(jié)點(diǎn)。13設(shè)有一棵深度為5的完全二叉樹(shù)，該樹(shù)共有21個(gè)結(jié)點(diǎn),第5層上有 6 個(gè)結(jié)點(diǎn)。 （根所在結(jié)點(diǎn)為第1層） 14.對(duì)于一棵具有n個(gè)結(jié)點(diǎn)的二叉樹(shù)，其相應(yīng)的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中共有_ n+1_個(gè)指針域?yàn)榭铡?15中序遍歷_二叉排序樹(shù) _樹(shù)可得到一個(gè)有序序列。 16. 對(duì)一組記錄（5，8，9，2，12，7，56，44，39）進(jìn)行直接插入排序(由小到大排序) ，當(dāng)把第6個(gè)記錄7插入有序表，為尋找

13、插入位置需比較_ 4_次。 17. 序列12,10,13,11,16,14,采用冒泡排序算法,經(jīng)一趟冒泡后,序列的結(jié)果是_ 10，12，11，13，14，16_。 （按升序排序） 18設(shè)有一棵深度為6的完全二叉樹(shù)，第6層上有3個(gè)結(jié)點(diǎn)，該樹(shù)共有_ 34_個(gè)結(jié)點(diǎn)。（根所在結(jié)點(diǎn)為第1層） 19. 對(duì)16個(gè)元素的序列用冒泡排序法進(jìn)行排序，共需要進(jìn)行_ 15_趟冒泡。 20一棵有16個(gè)葉結(jié)點(diǎn)的哈夫曼樹(shù)，則該樹(shù)共有_ 31_個(gè)結(jié)點(diǎn)。 21. 一棵有16個(gè)葉結(jié)點(diǎn)的哈夫曼樹(shù)，則該樹(shù)共有_ 15_個(gè)非葉結(jié)點(diǎn)。 22. 20個(gè)元素進(jìn)行冒泡法排序，通常第6趟冒泡要進(jìn)行_ _ 14_次元素間的比較。 23. 在對(duì)一組

14、記錄（40，24，82，9，1，78，46，31，69）進(jìn)行直接插入排序(由小到大排 序) ，當(dāng)把第7個(gè)記錄46插入到有序表時(shí)，為尋找插入位置需比較_3_次。24對(duì)稀疏矩陣進(jìn)行壓縮存儲(chǔ),可采用三元組表，一個(gè)6行7列的稀疏矩陣A共有38個(gè)零 元素，其相應(yīng)的三元組表共有_4_個(gè)元素。 三、綜合題1設(shè)有序表為(5, 8, 14, 15, 33, 51, 61, 73, 81, 82, 93) ,元素的序號(hào)依次為 1,2,3,，11. （1）畫(huà)出對(duì)上述查找表進(jìn)行折半查找所對(duì)應(yīng)的判定樹(shù)（樹(shù)中結(jié)點(diǎn)可用序號(hào)表示） （2）說(shuō)明成功查找到元素33需要經(jīng)過(guò)多少次比較？ (3) 在等概率條件下, 給出成功查找的平均

15、查找長(zhǎng)度（1）圖4 51 14 81 5 15 61 82 8 33 73 93 (2) 4次 (3) ( 1+2*2+3*4+4*4)/11=33/11=32.設(shè)數(shù)據(jù)集合a=1,5,8,3,10,7,13,9（1）依次取a中各數(shù)據(jù)，構(gòu)造一棵二叉排序樹(shù)。（2）對(duì)該二叉樹(shù)進(jìn)行查找，成功查找到7要進(jìn)行多少次元素間的比較？（3）給出對(duì)該二叉樹(shù)中序遍歷的序列。 (1) 圖5 (2) 4次 (3) 中序遍歷 1, 3 , 5 ,7 , 8 , 9 , 10 , 13 3dceabfhe圖1(1)如圖1所示,若從頂點(diǎn)a出發(fā)，首先經(jīng)過(guò)c按圖的深度優(yōu)先搜索法進(jìn)行遍歷，給出可能得到的一種頂點(diǎn)序列。 (1) ac

16、dbfeh (2) 或 或 (2)設(shè)有向圖如圖2所示下，寫(xiě)出首先刪除頂點(diǎn)1的1種拓?fù)湫蛄?234543465圖2 4設(shè)有序表為(30, 48, 58, 70, 78, 79, 90) ,元素的序號(hào)依次為 1,2,3,，7.（1） 畫(huà)出對(duì)上述查找表進(jìn)行折半查找所對(duì)應(yīng)的判定樹(shù)（樹(shù)中結(jié)點(diǎn)用序號(hào)表示）（2） 給出有序表中經(jīng)3次比較成功查找到的所有元素(3) 說(shuō)明不成功查找元素59需要經(jīng)過(guò)多少次比較？（1）圖6 70 48 79 30 58 78 90 (2) 30 58 78 90 (3) 3次5.(1) 設(shè)數(shù)據(jù)集合a=7,4,9,8,6,5,3,依次取a中各數(shù)據(jù)，構(gòu)造一棵二叉排序樹(shù)。 (2)對(duì)該二叉

17、樹(shù)進(jìn)行查找，成功查找到5要進(jìn)行多少次元素間的比較？(3) 給出對(duì)上述二叉排序樹(shù)進(jìn)行中序遍歷的序列 (1) 圖7 (2) 4(3) 3,4,5,6,7,8,9 6(1) 如圖3所示，若從頂點(diǎn)a出發(fā)，首先經(jīng)過(guò)c按廣度優(yōu)先搜索法進(jìn)行遍歷，給出可能得 到的一種頂點(diǎn)序列。 （2）同圖3所示, 若從頂點(diǎn)h出發(fā)，按深度優(yōu)先搜索法進(jìn)行遍歷，給出可能得到的2種頂點(diǎn) 序列。a阿decfhecdeccdeceec圖3 (3) 一組記錄的關(guān)鍵字序列為（75，63，95，80，53，45，38，20），利用堆排序的方法建立小根堆(堆頂元素是最小元素）,給出按篩選法建立的的初始堆。 (1) acefdh (2) hdea

18、cf hdfcae （3） 20, 53，38，63，75，45，95，80 四、程序填空題1以下函數(shù)在a0到an-1中，用折半查找算法查找關(guān)鍵字等于k的記錄，查找成功返回該記錄的下標(biāo)，失敗時(shí)返回-1，完成程序中的空格typedef struct int key;NODE;int Binary_Search(NODE a,int n, int k) int low,mid,high; low=0; high=n-1; while(_(1)_) mid=(low+high)/2; if(amid.key=k) return _(2)_; else if(_(3)_) low=mid+1; els

19、e _(4)_; _(5)_; (1) low=high (2) mid (3) amid.key k (4) high=mid -1 (5) return -12以下函數(shù)為直接選擇排序算法，對(duì)a1,a2,an中的記錄進(jìn)行直接選擇排序 ，完成程序中的空格typedef struct int key; NODE; void selsort(NODE a ,int n) int i,j,k; NODE temp; for(i=1;i= _(1)_;i+) k=i; for(j=i+1; _(2)_; j+) if(aj.keyak.key) _(3)_; if(i!=k) temp=ai;_(4)

20、_; _(5)_; (1) n-1 (2) jdata=x; _ (2)_; _(3)_; (1) sizeof(struct node)(2) pnext=top (3) top=p4.以下函數(shù)為鏈隊(duì)列的入隊(duì)操作，x為要入隊(duì)的結(jié)點(diǎn)的數(shù)據(jù)域的值，front、 rear分別是鏈隊(duì)列的隊(duì)頭、隊(duì)尾指針struct node ElemType data;struct node *next;struct node *front，*rear; void InQueue(ElemType x) struct node *p; p= (struct node*) _(1)_; p-data=x; p-next

21、=NULL; _(2)_; ; rear= _(3)_; (1) malloc(sizeof(struct node) (2) rear-next=p; (3) rear=p;綜合練習(xí)二一、單項(xiàng)選擇題 1. 對(duì)稀疏矩陣進(jìn)行壓縮存儲(chǔ),可采用三元組表，一個(gè)有10 行的稀疏矩陣A共有97個(gè)零元素，其相應(yīng)的三元組表共有3個(gè)元素。該矩陣A有( D )列。 A8 B9 C7 D10 2 .單向鏈表所具備的特點(diǎn)是( C )。A.可以隨機(jī)訪(fǎng)問(wèn)任一結(jié)點(diǎn) B.占用連續(xù)的存儲(chǔ)空間 C.插入刪除不需要移動(dòng)元素 D.可以通過(guò)某結(jié)點(diǎn)的指針域訪(fǎng)問(wèn)其前驅(qū)結(jié)點(diǎn) 3. 子串“acd”在主串 “abdcacdefac”中的位置是(

22、 B ) 。 A3 B5 C7 D1 4 .設(shè)有一個(gè)長(zhǎng)度為18的順序表，要在第6個(gè)元素之前插入一個(gè)元素（也就是插入元素作為新表的第6個(gè)元素），則移動(dòng)元素個(gè)數(shù)為（ C ）。 A12 B5 C. 13 D6 5. 序列12,16,8,4按順序依次進(jìn)棧，按該棧的可能輸出序列依次入隊(duì)列，該隊(duì)列的不可能輸出序列是（ B ）。 (進(jìn)棧、出棧可以交替進(jìn)行）。 A16,12,8,4 B4,8,12,16 C8,4,16,12 D16,12,4,8 6棧和隊(duì)列的共同特點(diǎn)是（ A ）。 A都是線(xiàn)性結(jié)構(gòu) B元素都可以隨機(jī)進(jìn)出C都是先進(jìn)后出 D都是先進(jìn)先出 7. 在一個(gè)不帶頭結(jié)點(diǎn)的鏈隊(duì)中，假設(shè)f和r分別為隊(duì)頭和隊(duì)尾指

23、針，對(duì)該隊(duì)列進(jìn)行出隊(duì) 操作,并把結(jié)點(diǎn)的值保存在變量e中,其運(yùn)算為（ C ）。 Ae=f-data；r=r-next; Be=f-data；r-next=r; Ce=f-data；f=f-next; De=f-data；f-next=f; 8元素1，3，5，7按順序依次入隊(duì)列，按該隊(duì)列的出隊(duì)序列進(jìn)棧，該棧的可能輸出序列是（ D ）（進(jìn)棧出棧可以交替進(jìn)行）。 A7，5，1，3 B7，3，1，5 C5，1，3，7 D7，5，3，1 9. 數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)內(nèi)存中的表示是( B )。 A.給相關(guān)變量分配存儲(chǔ)單元 B.數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu) C.數(shù)據(jù)的邏輯結(jié)構(gòu) D.算法的具體體現(xiàn) 10在一個(gè)不帶頭結(jié)點(diǎn)的鏈隊(duì)

24、中，假設(shè)f和r分別為隊(duì)頭和隊(duì)尾指針，則對(duì)該隊(duì)列進(jìn)行出隊(duì)操作中并把結(jié)點(diǎn)的值保存在變量e中,其運(yùn)算為e=fdata；和（ C ）。 Ar=rnext; Brnext=r;Cf=fnext; Dfnext=f 11. 以下說(shuō)法正確的是( B )。 A. 線(xiàn)性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)必須占用連續(xù)的存儲(chǔ)空間 B. 一種邏輯結(jié)構(gòu)可以有不同的存儲(chǔ)結(jié)構(gòu) C一種邏輯結(jié)構(gòu)只能有唯一的存儲(chǔ)結(jié)構(gòu) D線(xiàn)性表的順序存儲(chǔ)結(jié)構(gòu)不必占用連續(xù)的存儲(chǔ)空間 12設(shè)有一個(gè)對(duì)稱(chēng)矩陣A，采用壓縮存儲(chǔ)的方式，將其下三角部分以行序?yàn)橹餍虼鎯?chǔ)到一維數(shù)組B中（數(shù)組下標(biāo)從1開(kāi)始），B數(shù)組共有45個(gè)元素,則該矩陣是（ D ）階的對(duì)稱(chēng)矩陣。A15 B11 C1

25、0 D9 13在一個(gè)單鏈表中要?jiǎng)h除p所指結(jié)點(diǎn)的后繼結(jié)點(diǎn)，可執(zhí)行q=p-next; 和（ A ）。 Ap-next=q-next ; Bp=q-next; Cp-next=q; Dp-next=q; 14. 下列是C語(yǔ)言中abcd321ABCD的子串的選項(xiàng)是（ A ）。 A. 21ABC B.abcABCD C. abcD D. 321a 15. 在數(shù)據(jù)結(jié)構(gòu)和算法中，與所使用的計(jì)算機(jī)有關(guān)的是 （ B ）。 A數(shù)據(jù)元數(shù)間的抽象關(guān)系 B數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu) C算法的時(shí)間復(fù)雜度 D數(shù)據(jù)的邏輯結(jié)構(gòu) 16. 字符串a(chǎn)1=BEIJING, a2 =BEF , a3= BEFANG, a4=“BEFI最小的是（ B

26、 ）.A. a1 B. a2 C. a3 D. a4 17. 以下表中可以隨機(jī)訪(fǎng)問(wèn)的是（ D ）。 A單向鏈表 B雙向鏈表 C單向循環(huán)鏈表 D順序表 18一棵有20個(gè)結(jié)點(diǎn)采用鏈?zhǔn)酱鎯?chǔ)的二叉樹(shù)中，共有（ A ）個(gè)指針域?yàn)榭铡?A21 B20 C19 D18 19.頭指針為head的不帶頭結(jié)點(diǎn)的單向鏈表為空的判定條件是邏輯表達(dá)式( A )為真。 A. head= =NULL B. head-next= =NULL C. head-next=NULL D. head-next!= NULL 20設(shè)一棵哈夫曼樹(shù)共有18個(gè)葉結(jié)點(diǎn)，則該樹(shù)有（ C ）個(gè)非葉結(jié)點(diǎn)。 A18 B19 C17 D16 21 .設(shè)

27、有一個(gè)長(zhǎng)度為32的順序表，要在第5個(gè)元素之前插入1個(gè)元素（也就是插入元素 作為新表的第5個(gè)元素），需移動(dòng)元素個(gè)數(shù)為（ B ）。 A25 B28 C. 5 D6 22如圖1所示的一個(gè)圖，若從頂點(diǎn)g出發(fā)，按深度優(yōu)先搜索法進(jìn)行遍歷，則可能得到的一種頂點(diǎn)序列為（D ）。 Agabecdf Bgacfebd Cgaebcfd Dgaedfcb bdfeCag 圖1 23設(shè)有一個(gè)長(zhǎng)度為33的順序表，要?jiǎng)h除第10個(gè)元素(下標(biāo)從1開(kāi)始)需移動(dòng)元素的個(gè)數(shù) 為（ C ）。 A11 B10 C23 D14 24線(xiàn)性表以（ B ）方式存儲(chǔ)，能進(jìn)行折半查找。 A關(guān)鍵字有序的 B關(guān)鍵字有序的順序 C鏈接 D順序 25設(shè)有

28、一個(gè)28階的對(duì)稱(chēng)矩陣A，采用壓縮存儲(chǔ)的方式，將其下三角部分以行序?yàn)橹餍?存儲(chǔ)到一維數(shù)組B中（數(shù)組下標(biāo)從1開(kāi)始），則數(shù)組中第26號(hào)元素對(duì)應(yīng)于矩陣中的元素是（ A ）。 Aa7,5 , Ba7,6 Ca6,5 Da7,4 26有一個(gè)長(zhǎng)度為8的有序表，按折半查找對(duì)該表進(jìn)行查找，在等概率情況下查找成功的平均比較次數(shù)為（ D ）。A22/8 B20/8 C23/8 D21/8 27. 在一個(gè)不帶頭結(jié)點(diǎn)的單循環(huán)鏈表中，p、q分別指向表中第一個(gè)結(jié)點(diǎn)和尾結(jié)點(diǎn)，現(xiàn)要 刪除第一個(gè)結(jié)點(diǎn)，且p、q仍然分別指向新表中第一個(gè)結(jié)點(diǎn)和尾結(jié)點(diǎn)。可用的語(yǔ)句是 p=p-next;和（ D ）。 Ap=q-next; Bp-next

29、=q ; C q=p; D q-next=p; 28. 排序算法中，從尚未排序序列中依次取出元素與已排序序列（初始為空）中的元素進(jìn)行比較（要求比較次數(shù)盡量少），然后將其放入已排序序列的正確位置的方法是（A ）。 A折半插入排序 B直接插入排序 C歸并排序 D選擇排序 29在一棵二叉樹(shù)中，若編號(hào)為16的結(jié)點(diǎn)是其雙親結(jié)點(diǎn)的左孩子，則他的雙親結(jié)點(diǎn)的順序編號(hào) 為（ B ）。 A7 B8 C32 D33 30排序方法中，從未排序序列中挑選元素，并將其依次放入已排序序列（初始為空）的一端的方法，稱(chēng)為（ C ）排序。 A堆 B冒泡 C選擇 D快速 二、填空題1.數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)中的表示稱(chēng)為_(kāi)物理 (存

30、儲(chǔ))_結(jié)構(gòu)。 2.結(jié)構(gòu)中的數(shù)據(jù)元素存在一對(duì)多的關(guān)系稱(chēng)為_(kāi)樹(shù)形_結(jié)構(gòu)。3.四類(lèi)基本結(jié)構(gòu)分別為_(kāi) 集合 線(xiàn)性 樹(shù)形 圖狀 _結(jié)構(gòu)。 4.棧的操作特點(diǎn)是_先進(jìn)后出_。5.隊(duì)列的操作特點(diǎn)是先進(jìn)_先出_。 6.廣義表的( a , (a ,b) , d , e ,( (i ,j ) ,k ) )深度是_ 3 _。7.廣義表( (b,a,c) , c,d ,( e ,i ,j ,k ) )的表尾是_ (c,d,(e,i,j,k)_。 8.廣義表( (a ,b) , d , e ,( (i ,j ) ,k ) )的長(zhǎng)度是_ 4 _。 9.設(shè)有一個(gè)長(zhǎng)度為20的順序表 , 第8號(hào)元素到第20號(hào)元素依次存放的值為8

31、,9,20。 某人想要在第8號(hào)元素前插入1個(gè)元素7（也就是插入元素作為新表的第8個(gè)元素），程 序中他的做法是用語(yǔ)句for(i=8;idatasq-front;和_ sq-fronf+;_ 。 11設(shè)有一棵有38個(gè)結(jié)點(diǎn)的完全二叉樹(shù)，該樹(shù)共有_ 6 _層。（根所在結(jié)點(diǎn)為第1層）12. 設(shè)順序隊(duì)列的類(lèi)型為typedef struct ElemType dataMaxSise; int front,rear;Squeue;Squeue *sq; sq為指向順序隊(duì)列的指針變量，要進(jìn)行新元素x的入隊(duì)操作，按教課書(shū)約定,可用語(yǔ)句sq-datasq-rear=x;和_ sq-rear+;_。 13 一棵有18

32、個(gè)結(jié)點(diǎn)的二叉樹(shù)，其2度結(jié)點(diǎn)數(shù)的個(gè)數(shù)為8，則該樹(shù)共有 _ 1_個(gè)1度結(jié)點(diǎn)。 14. 序列14,12,15,13,18,16,采用冒泡排序算法,經(jīng)一趟冒泡后,序列的結(jié)果是_ 12,14,13,15,16,18_。（由小到大排序）15. 對(duì)一組記錄（1，3，9，2，12，7，5，4，6）進(jìn)行直接插入排序(由小到大排序) ，當(dāng)把第6個(gè)記錄7插入有序表，為尋找插入位置需比較_ 3_次。 16. 數(shù)據(jù)結(jié)構(gòu)中, _數(shù)據(jù)元素_ 之間的抽象關(guān)系稱(chēng)為邏輯結(jié)構(gòu)。 17. 序列5,3,8,4,7,6,采用冒泡排序算法,經(jīng)一趟冒泡后,序列的結(jié)果是_ 3,5,4,7,6,8_。(按升序排序) 18. 循環(huán)隊(duì)列中，設(shè)fro

33、nt和rear分別為隊(duì)頭和隊(duì)尾指針，(最多元素為MaxSize,),判斷循環(huán)隊(duì)列為空的條件為_(kāi) front= =rear_為真。19. 廣義表(b,a , (c ,b) , f , e ,( (i ,j ) ,k ) )的長(zhǎng)度是_ 6_ 。 20. 排序算法中，從尚未排序序列中依次取出元素與已排序序列（初始為空）中的元素進(jìn)行比較（要求比較次數(shù)盡量少），然后將其放入已排序序列的正確位置的方法是 折半插入排序 。21 一棵有18個(gè)葉結(jié)點(diǎn)的哈夫曼樹(shù)，則該樹(shù)共有_ 17_個(gè)非葉結(jié)點(diǎn)。 22. 對(duì)稀疏矩陣進(jìn)行壓縮存儲(chǔ),可采用三元組表,矩陣元素a3,4 對(duì)應(yīng)的三元組為_(kāi) (3,4, a3,4)_ 。23對(duì)

34、稀疏矩陣進(jìn)行壓縮存儲(chǔ),可采用三元組表，一個(gè)8行7列的稀疏矩陣A共有51個(gè)零元 素，其相應(yīng)的三元組表共有_ 5_個(gè)元素 24在雙向鏈表中，要?jiǎng)h除p所指的結(jié)點(diǎn)，其中所用的一條語(yǔ)句（p-next）-prior=p-prior; 的功能是：使P所指結(jié)點(diǎn)的直接后繼的左指針指向_ P所指結(jié)點(diǎn)的直接前驅(qū)_。 三、 綜合題1.設(shè)數(shù)據(jù)集合a=6,17,10,13,8,15,12,18,14 （1）依次取a中各數(shù)據(jù)，構(gòu)造一棵二叉排序樹(shù)。 （2）給出對(duì)該二叉樹(shù)中序遍歷的序列 （3）對(duì)該二叉樹(shù)進(jìn)行查找，成功查找到14要進(jìn)行多少次元素間的比較？圖2(2)中序遍歷 6 , 8 ,10,12 , 13 , 14 , 15

35、, 17 , 18 (3) 6次2.設(shè)數(shù)據(jù)集合a=62,74,30,15,56,48（1）依次取a中各數(shù)據(jù)，構(gòu)造一棵二叉排序樹(shù)。（2）對(duì)該二叉樹(shù)進(jìn)行查找，不成功查找有多少種可能？畫(huà)出不成功查找樹(shù)的示意圖。（3）不成功查找的平均查找長(zhǎng)度是多少?（4）為了成功查找到48需要進(jìn)行多少次元素間的比較?（5）給出對(duì)該二叉樹(shù)后序遍歷的序列。(1)圖3 (2)圖4 7種可能 (3)(2*2+3*3+4*2)/7=21/7 (4)4次 (5)15,48,56,30,74,62 3設(shè)有序表為(2, 5, 11, 12, 30, 48, 58) ,元素的序號(hào)依次為 1,2,3,，7. （1）畫(huà)出對(duì)上述查找表進(jìn)行折半查找所對(duì)應(yīng)的判定樹(shù)（樹(shù)中結(jié)點(diǎn)用序號(hào)表示） （2）說(shuō)明成功查找到元素11需要經(jīng)過(guò)多少次比較？ (3) 在等概率條件下, 給出成功查找的平均查找長(zhǎng)度 （1）圖5 (2) 3次 (3) ( 1+2*2+3*4)/7=17/74