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

1、數(shù)據(jù)結(jié)構(gòu)（本）期末綜合練習(xí)2016年6月練習(xí)一一、單項(xiàng)選擇題 1下面關(guān)于線性表的敘述錯(cuò)誤的是（ ）。 A. 線性表采用順序存儲(chǔ)必須占用一片連續(xù)的存儲(chǔ)空間 B. 線性表采用鏈?zhǔn)酱鎯?chǔ)不必占用一片連續(xù)的存儲(chǔ)空間 C. 線性表采用鏈?zhǔn)酱鎯?chǔ)便于插入和刪除操作的實(shí)現(xiàn) D. 線性表采用順序存儲(chǔ)便于插入和刪除操作的實(shí)現(xiàn) 2.數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)包括數(shù)據(jù)元素的表示和（ ）。 A . 數(shù)據(jù)處理的方法 B. 數(shù)據(jù)元素的類型 C . 相關(guān)算法 D. 數(shù)據(jù)元素間的關(guān)系的表示3.以下數(shù)據(jù)結(jié)構(gòu)中是非線性結(jié)構(gòu)的是( )。 A. 隊(duì)列 B. 棧 C. 線性表 D. 二叉樹(shù) 4樹(shù)狀結(jié)構(gòu)中數(shù)據(jù)元素的位置之間存在（ ）的關(guān)系。 A每一個(gè)元

2、素都有一個(gè)直接前驅(qū)和一個(gè)直接后繼 B一對(duì)一 C多對(duì)多 D一對(duì)多5設(shè)有一個(gè)長(zhǎng)度為18的順序表，要?jiǎng)h除第7個(gè)元素需移動(dòng)元素的個(gè)數(shù)為（ ）。 A13 B12 C11 D10 6設(shè)有一個(gè)長(zhǎng)度為26的順序表，要插入一個(gè)元素,并使它成為新表的第6個(gè)元素,需移動(dòng)元素的個(gè)數(shù)為（ ）。 A21 B22 C20 D197. 兩個(gè)字符串相等的充要條件是（ ）。 A. 兩個(gè)字符串的長(zhǎng)度相等 B. 同時(shí)具備(A)和(C)兩個(gè)條件 C. 兩個(gè)字符串中對(duì)應(yīng)位置上的字符相等 D. 以上答案都不對(duì) 8頭指針為head的帶頭結(jié)點(diǎn)的單向循環(huán)鏈表，p所指向尾結(jié)點(diǎn)，要使該鏈表成為不帶頭結(jié)點(diǎn)的單向循環(huán)鏈表, 可執(zhí)行head=head-&

3、gt;nex;和（ ）。 Ap= head->next B head->next=p Chead->next=p->next D p->next=head;9. 設(shè)某鏈表中最常用的操作是在鏈表的尾部插入或刪除元素，在已知尾指針的條件 下,選用下列（ ）存儲(chǔ)方式最節(jié)省運(yùn)算時(shí)間。 A. 單向鏈表B. 單向循環(huán)鏈表 C. 雙向鏈表 D. 雙向循環(huán)鏈表 10元素111，113，115，117按順序依次進(jìn)棧，則該棧的不可能輸出序列是（ ）（進(jìn)棧出棧可以交替進(jìn)行）。 A117，115，113，111 B111，113，115，117 C117，115，111，113 D113

4、，111，117，115 11元素13，15，19，20順序依次進(jìn)棧，則該棧的不可能輸出序列是（ ）。 進(jìn)棧出?？梢越惶孢M(jìn)行）。 A20，19，15，13 B13，15，19，20 C19，13，15，20 D15，13，20，19 12以下說(shuō)法正確的是（ ）。 A棧的特點(diǎn)是先進(jìn)先出 B棧的特點(diǎn)是先進(jìn)后出 C隊(duì)列的特點(diǎn)是先進(jìn)后出 D. 棧和隊(duì)列的特點(diǎn)都是后進(jìn)后出 13設(shè)指針q指向單鏈表中結(jié)點(diǎn)A，指針p指向單鏈表中結(jié)點(diǎn)A的后繼結(jié)點(diǎn)B，則在 表中刪除結(jié)點(diǎn)B的操作為（ ）。 A. p->next； =q；B. q->next=p->next； C. p->next=q->

5、;next；D. q->next=p； 14. 設(shè)有一個(gè)20階的對(duì)稱矩陣A(第一個(gè)元素為a1,1)，采用壓縮存儲(chǔ)的方式，將其下三角部分以行序?yàn)橹餍虼鎯?chǔ)到一維數(shù)組B中（數(shù)組下標(biāo)從1開(kāi)始）， 則矩陣元素a6,2 在一維數(shù)組B中的下標(biāo)是（ ）。 A21 B17 C28 D23 15.棧和隊(duì)列的共同特點(diǎn)之一是( )。 A. 都是先進(jìn)后出 B. .都是先進(jìn)先出C. 沒(méi)有共同點(diǎn) D. 只允許在端點(diǎn)處插入和刪除元素16設(shè)有串p1=”ABADF”,P2=”ABAFD”，P3=”ABADFA”,P4=”ABAF”,以下四個(gè)串中最大的是( )。 A p3 B p2 C p1 D p417.用鏈接方式存儲(chǔ)的隊(duì)

6、列，在進(jìn)行插入運(yùn)算時(shí)( )。 A. 需修改頭指針 B. 頭、尾指針都需要修改 C. 需修改尾指針 D. 頭、尾指針都不需要修改 18.數(shù)組a經(jīng)初始化 char a =“English”; a7中存放的是（ ）。 A. 字符串的結(jié)束符 B. 字符h C. h D. 變量h19.字符串 a1=“AEIJING“，a2 =AEI“，a3=AEFANGa4=”AEFI“中最大的是（ ）。 A. a1 B. a2 C. a3 D. a4 20.設(shè)主串為“ABcCDABcdEFaBc”，以下模式串能與主串成功匹配的是（ ）。 A. Bcd B. BCd C. ABC D. Abc 21設(shè)有一個(gè)20階的對(duì)稱

7、矩陣A(第一個(gè)元素為a1,1)，采用壓縮存儲(chǔ)的方式，將其 下三角部分以行序?yàn)橹餍虼鎯?chǔ)到一維數(shù)組B中（數(shù)組下標(biāo)從1開(kāi)始），則矩陣中元 素a6,2在一維數(shù)組B中的下標(biāo)是（ ）。 A23 B17 C21 D1822在一棵二叉樹(shù)中，若編號(hào)為i的結(jié)點(diǎn)存在左孩子，則左孩子的順序編號(hào)為（ ）。 A2i+1 B2i-1 C2i D2i+2 23. 以下說(shuō)法正確的是( )。 A. 若二叉樹(shù)中左子樹(shù)上所有結(jié)點(diǎn)的值均小于根結(jié)點(diǎn)的值，右子樹(shù)上所有結(jié)點(diǎn)的值 均大于根結(jié)點(diǎn)的值。則該樹(shù)為二叉排序樹(shù)。B. 二叉樹(shù)中任意一個(gè)非葉結(jié)點(diǎn)的值都大于其左子樹(shù)上所有結(jié)點(diǎn)的值,小于其右子 樹(shù)上所有結(jié)點(diǎn)的值,則該樹(shù)為二叉排序樹(shù)。C. 二叉樹(shù)

8、中任意一個(gè)結(jié)點(diǎn)的值均大于其左孩子的值，小于其右孩子的值。則該樹(shù) 為二叉排序樹(shù)。D.前序遍歷二叉排序樹(shù)可得到一個(gè)有序序列。24如圖1所示，若從頂點(diǎn)a出發(fā)，按圖的廣度優(yōu)先搜索法進(jìn)行遍歷，則可能得 到的一種頂點(diǎn)序列為（ ）。 Aabecdf Baecbdf Caebcfd Daedfcb bdfeca圖1 25.二叉樹(shù)的第k層的結(jié)點(diǎn)數(shù)最多為( )。 A.2K-1 B.2K+1 C.2k-1 D.2k-1 26線性表以（ ）方式存儲(chǔ)，能進(jìn)行折半查找。 A鏈接 B順序 C關(guān)鍵字有序的順序 D二叉樹(shù) 27. 如圖2所示，若從頂點(diǎn)6出發(fā)，按深度優(yōu)先搜索法進(jìn)行遍歷，則可能得到的一種頂點(diǎn)序列為（ ）。 A6,9

9、,3,2,8,7,4 B6,9,2,3,7,8,4 C6,2,7,9,8,4,3 D6,2,8,7,9,3,43289674圖2 28一棵具有38個(gè)結(jié)點(diǎn)的完全二叉樹(shù)，最后一層有（ ）個(gè)結(jié)點(diǎn)。 A7 B5 C6 D8 29. 如圖3所示，若從頂點(diǎn)a出發(fā)，按廣度優(yōu)先搜索法進(jìn)行遍歷，則可能得 到的一種頂點(diǎn)序列為（ ）。 Aabcfegd Babcdfge Cacbfedg Dabcfgde gfabdec圖330.圖4的拓?fù)湫蛄惺? )。 A5 2 3 4 6 B2 3 6 4 5 C5 6 2 3 4 D. 2 3 5 6 4 234543465圖4 31. 對(duì)稀疏矩陣進(jìn)行壓縮存儲(chǔ),可采用三元組表

10、，一個(gè)10 行8列的稀疏矩陣A，其相應(yīng)的三元組表共有6個(gè)元素，矩陣A共有( )個(gè)零元素。 A8 B72 C74 D10 32. 10,6,2,1按順序依次進(jìn)棧，該隊(duì)列的可能輸出序列是（ ）。 (進(jìn)棧出棧可以交替進(jìn)行）。 A6,10,1,2 B2,10,6,1 C6,1,10,1 D1,6,10,2 33. 算法的時(shí)間復(fù)雜度與( )有關(guān) A. 算法本身 B. 所使用的計(jì)算機(jī) C. 算法的程序設(shè)計(jì) D. 數(shù)據(jù)結(jié)構(gòu) 34. 一種邏輯結(jié)構(gòu)在存儲(chǔ)時(shí) （ ）。 A只要存儲(chǔ)數(shù)據(jù)元素間的關(guān)系 B只能采用一種存儲(chǔ)結(jié)構(gòu) C可采用不同的存儲(chǔ)結(jié)構(gòu) D只要存儲(chǔ)數(shù)據(jù)元素的值 35.數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)內(nèi)存中的表示是指 ( )

11、 。 A數(shù)據(jù)元素之間的關(guān)系 B數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu) C數(shù)據(jù)元素的類型 D數(shù)據(jù)的邏輯結(jié)構(gòu) 二、填空題1. 設(shè)：char a =“AEIJING“;該字符串在計(jì)算機(jī)中存儲(chǔ)時(shí)占_個(gè)字節(jié)。 2結(jié)構(gòu)中的數(shù)據(jù)元素存在多對(duì)多的關(guān)系稱為_(kāi)結(jié)構(gòu)。3結(jié)構(gòu)中的數(shù)據(jù)元素存在多對(duì)多的關(guān)系稱為_(kāi)結(jié)構(gòu)。 4. n個(gè)元素進(jìn)行冒泡法排序， 第j趟冒泡要進(jìn)行_ _次元素間的比較。5. 對(duì)稀疏矩陣進(jìn)行壓縮存儲(chǔ),可采用三元組表，一個(gè)有8 行的稀疏矩陣A共有92個(gè) 零元素，其相應(yīng)的三元組表共有4個(gè)元素。該矩陣A有_ 列。 6中序遍歷_樹(shù)可得到一個(gè)有序序列。7. 循環(huán)鏈隊(duì)列中，設(shè)front和rear分別為隊(duì)頭和隊(duì)尾指針，最大存儲(chǔ)空間元素為Ma

12、xSize, 采用少用一個(gè)存儲(chǔ)空間的模式，則判斷循環(huán)鏈隊(duì)列為空的條件是_ _ _ 為真。 8. 待排序的序列為8,3,4,1,2,5,9, 采用直接選擇排序算法,當(dāng)進(jìn)行了兩趟選擇后,結(jié)果序列為( )。 9. n個(gè)元素進(jìn)行冒泡法排序，第j趟冒泡要進(jìn)行_ _次元素間的比較。 10. 廣義表( (a ,b) , d , e ,( (i ,j ) ,k ) )的長(zhǎng)度是_ 。 11設(shè)有一棵深度為4的完全二叉樹(shù)，第四層上有5個(gè)結(jié)點(diǎn)，該樹(shù)共有_個(gè)結(jié)點(diǎn)。 （根所在結(jié)點(diǎn)為第1層） 12. 廣義表的( c， a , (a ,b) , d , e ,( (i ,j ) ,k ) )深度是_。 13中序遍歷一棵_ 樹(shù)

13、可得到一個(gè)有序序列。 14. 對(duì)稀疏矩陣進(jìn)行壓縮存儲(chǔ),可采用三元組表，一個(gè)有10 行10列的稀疏矩陣A共有95個(gè)零元素，其相應(yīng)的三元組表共有 個(gè)元素。15.待排序的序列為9,4,5,1,2,6,10, 采用直接選擇排序算法,當(dāng)進(jìn)行了兩趟選擇后,結(jié)果序列為_(kāi) 。 16在對(duì)一組記錄(50, 49, 97, 22, 16, 73, 65, 47, 88)進(jìn)行直接插入排序時(shí)，當(dāng)把第7個(gè)記錄65 插入到有序表時(shí)，為尋找插入位置需比較_次。17.廣義表( (a ,b) , d , e ,( (i ,j ) ,k ) )的長(zhǎng)度是_ 。18. 一棵有5個(gè)葉結(jié)點(diǎn)的哈夫曼樹(shù),該樹(shù)中總共有 _ 個(gè)結(jié)點(diǎn)。19.廣義表

14、的 ( c， a , (a ,b) , d , e ,( (i ,j ) ,k ) )深度是_ 。 20. 設(shè)有一棵深度為4的完全二叉樹(shù)，第四層上有5個(gè)結(jié)點(diǎn)，該樹(shù)共有_個(gè)結(jié)點(diǎn)。 （ 根所在結(jié)點(diǎn)為第1層）。21.線性表用_方式存儲(chǔ)需要占用連續(xù)的存儲(chǔ)空間 。 22設(shè)有一個(gè)長(zhǎng)度為40的順序表，要?jiǎng)h除第8個(gè)元素需移動(dòng)元素的個(gè)數(shù)為_(kāi)。 23. 線性表用關(guān)鍵字_的順序方式存儲(chǔ)，可以用二分法排序 。 24. 有以下程序段 char a =“English”; char *p=a; int n=0; 三、綜合題1 （1）設(shè)有數(shù)據(jù)集合40，29，7，73，101，4，55，2，81，92，39，依次取集合中各數(shù)

15、據(jù)構(gòu)造一棵二叉排序樹(shù)。 (2) 在上述二叉排序樹(shù)上進(jìn)行查找，給出成功查找到元素92的查找路徑,其中共經(jīng)過(guò)了多少次元素間的的比較。(3)有一個(gè)長(zhǎng)度為10的有序表，按折半查找對(duì)該表進(jìn)行查找，給出在等概率情況下查 找成功的平均比較次數(shù)為。2有一個(gè)長(zhǎng)度為11的有序表(1, 2, 11, 15, 24, 28, 30, 56, 69, 70, 80) , 元素的下標(biāo)依次為 1,2,3,11，按折半查找對(duì)該表進(jìn)行查找。 (1）畫出對(duì)上述查找表進(jìn)行折半查找所對(duì)應(yīng)的判定樹(shù)。 （2）說(shuō)出成功查找到元素56,需要依次經(jīng)過(guò)與哪些元素的比較？ （3）說(shuō)出不成功查找元素72,需要進(jìn)行元素比較的次數(shù)？3. (1) 以2，

16、3，4，7，8，9作為葉結(jié)點(diǎn)的權(quán)，構(gòu)造一棵哈夫曼樹(shù)， (2) 給出相應(yīng)權(quán)重值葉結(jié)點(diǎn)的哈夫曼編碼。 (3) 一組記錄的關(guān)鍵字序列為（47，80，57，39，41，46），利用堆排序的方法建立的 初始堆（堆頂元素是最小元素,以樹(shù)的形式給出）。4. (1)一組記錄的關(guān)鍵字序列為（57，90，67，50，51，56），利用堆排序（堆頂元素是 最小元素）的方法建立初始堆（要求以完全二叉樹(shù)描述 ）。 (2)對(duì)關(guān)鍵字序列(56,51,71,54,46,106)利用快速排序，以第一個(gè)關(guān)鍵字為分割元素， 給出經(jīng)過(guò)一次劃分后結(jié)果。 (3) 一組記錄的關(guān)鍵字序列為（ 60,47，80，57，39，41，46,30）

17、，利用歸并排序的 方法,分別給出(1,1) 歸并、(2,2) 歸并、(4,4) 歸并的結(jié)果序列。四、程序填空題1.設(shè)線性表為（1,3,7,5），以下程序用說(shuō)明結(jié)構(gòu)變量的方法建立單向鏈表，并輸出鏈表中各結(jié)點(diǎn)中的數(shù)據(jù)。 struct node int data;struct node *next;typedef struct node NODE; #define NULL 0 void main( ) NODE a,b,c,d,*head,*p;a.data=6;b.data=10;c.data=16;d.data=4; /*d是尾結(jié)點(diǎn)*/head= （1） ;a.next=&b;b.ne

18、xt=&c;c.next=&d; （2） ; /*以上結(jié)束建表過(guò)程*/p=head; /*p為工作指針，準(zhǔn)備輸出鏈表*/do printf(“%dn”, （3） ); （4） ; while(p!=NULL); 畫出按該程序建立的單向鏈表的示意圖，說(shuō)明程序運(yùn)行結(jié)束后p的指向。（5） 2.設(shè)線性表為（16，20，26，24），以不帶頭結(jié)點(diǎn)的單向鏈表存儲(chǔ)，鏈表頭指針為head,以下程序的功能是輸出鏈表中各結(jié)點(diǎn)中的數(shù)據(jù)域data。 struct node int data; struct node *next; ; typedef struct node NODE; #define

19、NULL 0 void main( ) NODE *head ,*p ; p=head; /*p為工作指針*/ do printf(“%dn”, _(1)_); _(2)_ ; while(_(3)_); 3以下是先序遍歷二叉樹(shù)的遞歸算法程序，完成空格部分（樹(shù)結(jié)構(gòu)中左、 右指針域分 別為left和right，數(shù)據(jù)域data為字符型，BT指向根結(jié)點(diǎn)）。 efabcd圖5 void Inorder (struct BTreeNode *BT) if( （1） ) （2） ;Inorder(BT->leftt); Inorder(BT->right); 利用上述程序?qū)τ覉D進(jìn)行遍歷，結(jié)果是

20、 （3） ; 4.以下函數(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;j<= (2)_ _ _; j+) if(aj.key<ak.key) (3)_ _; if( i!=k) temp=ai;(4)_ _;(5)_ _;練習(xí)一答案一、單項(xiàng)選擇題1D 2D 3D 4D 5C 6A 7B 8D 9C 10C 11

21、C 12 B 13 B 14B 15 D 16B 17C 18A 19A 20A 21B 22C 23 B 24B 25C 26C 27A 28A 29B 30 C 31C 32A 33A 34B 35C 二、填空題18 2圖狀 3圖狀 4n-j 512 6二叉排序樹(shù) 7front= =rear 81，2，4，8，3，5，9 9n-j104111212313二叉排序樹(shù) 145 151，2，5，9，4，6，1016317. 418919. 320. 1221順序 2232 23有序 39559281410172407329圖6 247 三、綜合題1(1) (2)40,73,101,81,92。共

22、5個(gè)元素比較 (3) 29/10 30158056662427011169286圖72(1) (2)28,69,30,56 (3)4次397589243331518圖8 (1) (2) 2：00003 00014 0017 108 119 01394146478057圖9 (3) 4505156579067圖10 (1) (2) 46,51,54,56,71,106 (3) (47 , 60 ) ( 57 , 80 ) ( 39 , 41 ) ( 30 , 46 )(47, 57, 60, 80 ) ( 30,39,41,46 ) ( 30,39,41,46,47,57,60,80) 四、程序

23、填空題1 （1）&a（2）d->next=NULL（3）p->data（4）p=p->next（5）P指向NULL610164headNULLLL2 （1）p->data（2）p=p->next（3）p!=NULL3 （1） if(BT!=NULL)（2） printf(“%c”,BT->data);（3） a,b,d,e,f,c4 （1）n-1（2）n（3）k=j（4）ai=ak (5) ak=temp 練習(xí)二一、單項(xiàng)選擇題1棧和隊(duì)列的共同特點(diǎn)是（ ）。A. 元素都可以隨機(jī)進(jìn)出 B. 都是操作受限的線性結(jié)構(gòu) C. 都是先進(jìn)后出 D. 都是先進(jìn)先出

24、2設(shè)有頭指針為head的不帶頭結(jié)點(diǎn)的非空的單向循環(huán)鏈表, 指針p指向其尾結(jié)點(diǎn), 要 刪除第一個(gè)結(jié)點(diǎn),則可利用下述語(yǔ)句 head=head->next;和（ ）。 Ap =head; Bp=NULL; Cp->next =head; Dhead=p;3.對(duì)一個(gè)棧頂指針為top的鏈棧進(jìn)行入棧操作，通過(guò)指針變量 p生成入棧結(jié)點(diǎn)，則執(zhí) 行：p=(struct node *)malloc(sizeof(struct node); p->data=a; 和（ ）。 A. p->nex=top; top=p; B. top->next=p; p=top; C. top=top-

25、>next; p=top; D. p->next=top; p=top; 4. 以下說(shuō)法正確的是( )。 A. 線性表的鏈?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線性表的順序存儲(chǔ)結(jié)構(gòu)不必占用連續(xù)的存儲(chǔ)空間5.設(shè)頭指針為head的非空的單向鏈表, 指針p指向尾結(jié)點(diǎn),則通過(guò)以下操作( ) 可使其成為單向循環(huán)鏈表。 Ap->next = NULL ; Bhead = p; Cp->next=head ; Dp=head; 6把數(shù)據(jù)存儲(chǔ)到計(jì)算機(jī)中，并具體體現(xiàn)( )稱為物理結(jié)構(gòu)。 A數(shù)據(jù)的處理方法 B數(shù)據(jù)的性

26、質(zhì) C數(shù)據(jù)的運(yùn)算 D. 數(shù)據(jù)元素間的邏輯關(guān)系7一種邏輯結(jié)構(gòu)（ ）。 A只能有唯一的存儲(chǔ)結(jié)構(gòu) B可以有不同的存儲(chǔ)結(jié)構(gòu) C與存儲(chǔ)該邏輯結(jié)構(gòu)的計(jì)算機(jī)相關(guān) D是指某一種數(shù)據(jù)元素的性質(zhì) 8順序表所具備的特點(diǎn)之一是（ ）。 A可以隨機(jī)訪問(wèn)任一結(jié)點(diǎn) B不需要占用連續(xù)的存儲(chǔ)空間 C插入元素的操作不需要移動(dòng)元素 D刪除元素的操作不需要移動(dòng)元素9把數(shù)據(jù)存儲(chǔ)到計(jì)算機(jī)中，并具體體現(xiàn)數(shù)據(jù)元素間的邏輯結(jié)構(gòu)稱為（ ）。 A存儲(chǔ)結(jié)構(gòu) B邏輯結(jié)構(gòu) C數(shù)據(jù)元素的存儲(chǔ) D. 給數(shù)據(jù)元素分配存儲(chǔ)空間 10圖狀結(jié)構(gòu)中數(shù)據(jù)元素的位置之間存在（ ）的關(guān)系。 A一對(duì)一 B一對(duì)多 C多對(duì)多 D每一個(gè)元素都有一個(gè)直接前驅(qū)和一個(gè)直接后繼11圖狀結(jié)

27、構(gòu)中數(shù)據(jù)元素的位置之間存在（ ）的關(guān)系。 A一對(duì)一 B一對(duì)多 C多對(duì)多 D每一個(gè)元素都有一個(gè)且只有一個(gè)直接前驅(qū)和一個(gè)直接后繼 12元素20，14，16，18按順序依次進(jìn)棧，則該棧的不可能輸出序列是（ ）（進(jìn)棧出?？梢越惶孢M(jìn)行）。 A18，16，14，20 B20，14，16，18 C18，16，20，14 D14，20，18，16 13一個(gè)單鏈表中,在p所指結(jié)點(diǎn)之后插入一個(gè)s所指的結(jié)點(diǎn)時(shí)，可執(zhí)行: s->next=p->next;和（ ）。 As= p->next ; Bp->next=s->next; Cp=s->next ; Dp->next=s;

28、 14設(shè)有一個(gè)12階的對(duì)稱矩陣A(左上角第一個(gè)元素為a1,1)，采用壓縮存儲(chǔ)的方式，將其下三角部分以行序?yàn)橹餍虼鎯?chǔ)到一維數(shù)組B中（數(shù)組下標(biāo)從1開(kāi)始），則矩陣中元素a5,4在一維數(shù)組B中的下標(biāo)是（ ）。 A14 B12 C13 D11 15元素12，14，16，18順序依次進(jìn)棧，則該棧的不可能輸出序列是（ ）。 （進(jìn)棧出棧可以交替進(jìn)行）。 A18，16，14，12 B12，14，16，18 C18，16，12，14 D14，12，18，16 16設(shè)有一個(gè)長(zhǎng)度為22的順序表，要?jiǎng)h除第8個(gè)元素需移動(dòng)元素的個(gè)數(shù)為（ ）。 A25 B14 C15 D23 17設(shè)有一個(gè)30階的對(duì)稱矩陣A(第一個(gè)元素為a1

29、,1)，采用壓縮存儲(chǔ)的方式，將其 下三角部分以行序?yàn)橹餍虼鎯?chǔ)到一維數(shù)組B中（數(shù)組下標(biāo)從1開(kāi)始），則矩陣中元 素a9,2在一維數(shù)組B中的下標(biāo)是（ ）。 A41 B32 C18 D38 18在一棵二叉樹(shù)中，若編號(hào)為5的結(jié)點(diǎn)存在右孩子，則右孩子的順序編號(hào)為（ ）。 A12 B9 C11 D10 19設(shè)有一個(gè)長(zhǎng)度為32的順序表，要?jiǎng)h除第8個(gè)元素需移動(dòng)元素的個(gè)數(shù)為（ ）。 A15 B22 C14 D24 20一棵具有5層的完全二叉樹(shù)，最后一層有4個(gè)結(jié)點(diǎn)，則該樹(shù)總共有（ ）個(gè)結(jié)點(diǎn)。 A14 B15 C19 D18 21.在一棵二叉樹(shù)中，若編號(hào)為i的結(jié)點(diǎn)存在右孩子，則右孩子的順序編號(hào)為（ ）。 A2i B2

30、i-1 C2i+1 D2i+2 22 .如圖1所示，若從頂點(diǎn)a出發(fā)，按圖的廣度優(yōu)先搜索法進(jìn)行遍歷，則可能得到的一種頂點(diǎn)序列為（ ）。 Aabcdfge Babcedfg Cacbfedg Dabcfgde gfabdec圖1 23一棵具有16個(gè)結(jié)點(diǎn)的完全二叉樹(shù)，共有（ ）層。(設(shè)根結(jié)點(diǎn)在第一層) A7 B5 C6 D4 24.字符串a(chǎn)bcd321ABCD的子串是（ ）。 A. 21ABC B.abcABCD C. abcD D. 321a25如圖2所示，若從頂點(diǎn)a出發(fā)，按圖的深度優(yōu)先搜索法進(jìn)行遍歷，則可能得 到的一種頂點(diǎn)序列為（ ）。 Aabecdfg Bacfebgd Caebcfgd Da

31、edfcgb bdfecag圖2 26.數(shù)組a經(jīng)初始化char a =“English”; a1中存放的是（ ）。 A. 字符n B. 字符E C. n D. E27.字符串“DABcdabcd321ABC” 的子串是( )。 A. “cd32” B. “ABcD” C. “aBcd” D. “321a” 28如圖3所示，若從頂點(diǎn)a出發(fā)，按圖的深度優(yōu)先搜索法進(jìn)行遍歷，則可能得 到的一種頂點(diǎn)序列為（ ）。 Aabecdf Bacfebd Caebcfd Daedfcb bdfeca圖329.如圖4所示，若從頂點(diǎn)a出發(fā)，按廣度優(yōu)先搜索法進(jìn)行遍歷，則可 能得到的一種頂點(diǎn)序列為（ ）。 Aabcdfg

32、e Babcdfeg Cacbfedg Dabcfgde gfabdec圖430.下圖5的拓?fù)湫蛄惺? )。 A5 2 3 4 6 B5 2 3 6 4 C5 6 4 2 3 D. 2 3 4 5 6234543465圖531 .設(shè)有一個(gè)長(zhǎng)度為18的順序表，要在第5個(gè)元素之前插入1個(gè)元素（也就是插入元素作 為新表的第5個(gè)元素），則移動(dòng)元素個(gè)數(shù)為（ ）。 A15 B14 C. 5 D6 32設(shè)有一個(gè)長(zhǎng)度為25的順序表，要?jiǎng)h除第10個(gè)元素(下標(biāo)從1開(kāi)始)需移動(dòng)元素的個(gè)數(shù) 為（ ）。 A10 B17 C15 D16 33設(shè)有一個(gè)18階的對(duì)稱矩陣A，采用壓縮存儲(chǔ)的方式，將其下三角部分以行序?yàn)橹餍虼?儲(chǔ)

33、到一維數(shù)組B中（數(shù)組下標(biāo)從1開(kāi)始），則矩陣中元素a10,8在一維數(shù)組B中的下標(biāo) 是（ ）。A62, B63 C51 D53 34在一個(gè)尾指針為rear的不帶頭結(jié)點(diǎn)的單循環(huán)鏈表中,插入一個(gè)s所指的結(jié)點(diǎn),并作為第 一個(gè)結(jié)點(diǎn)，可執(zhí)行sànext=rearànext ;和（ ）。 A rearànext= sànext; B rear =sànext; C rear=s; D rearànext=s; 35在一棵二叉樹(shù)中，若編號(hào)為15的結(jié)點(diǎn)是其雙親結(jié)點(diǎn)的右孩子，則雙親結(jié)點(diǎn)的順序編號(hào)為（ ）。 A30 B8 C31 D7 二、填空題 1. 對(duì)稀

34、疏矩陣進(jìn)行壓縮存儲(chǔ),可采用三元組表，一個(gè)有10行的稀疏矩陣A共有97個(gè) 零元素，其相應(yīng)的三元組表共有3個(gè)元素。該矩陣A有 列。2. 棧的特點(diǎn)之一是：元素進(jìn)、出棧的次序是:先進(jìn)_。 3在單向鏈表中，q指向p所指結(jié)點(diǎn)的直接后繼結(jié)點(diǎn) ，要?jiǎng)h除q所指結(jié)點(diǎn)，可以用 操作_= q->next; 。 4對(duì)稀疏矩陣進(jìn)行壓縮存儲(chǔ)，矩陣中每個(gè)非零元素對(duì)應(yīng)的三元組包括該元素的三項(xiàng)信息是_ _。 5. 對(duì)稀疏矩陣進(jìn)行壓縮存儲(chǔ)，矩陣中每個(gè)非零元素對(duì)應(yīng)的三元組包括該元素的行下 標(biāo)、列下標(biāo)和_ _三項(xiàng)信息。 6在對(duì)10個(gè)記錄的序列(9，35,19, 77 ,2, 10 ,53, 45,27,68)進(jìn)行直接插入排序時(shí)，

35、當(dāng)把第 6個(gè)記錄10 插入到有序表時(shí)，為尋找插入位置，元素間需比較_次。 （按升序排序） 7. 隊(duì)列的操作特點(diǎn)是后進(jìn)_。 8. 字符串a(chǎn)1=beijing, a2 =bef , a3= beifang, a4=“befi最小的 是 _。9n個(gè)元素進(jìn)行冒泡法排序，通常需要進(jìn)行_ _趟冒泡。 1010個(gè)元素進(jìn)行冒泡法排序，,其中第5趟冒泡共需要進(jìn)行_ _次元素間的比較。 11 中序遍歷二叉排序樹(shù)可得到一個(gè)_的序列。 12_遍歷一棵二叉排序樹(shù)可得到一個(gè)有序序列。 13. 廣義表( c , a , (a ,b) , d , e ,( (i ,j ) ,k ) )的長(zhǎng)度是_ 。 14. 廣義表( c ,

36、 (a ,b,c) , ( d , e ,f ) , ( (i ,j ) ,k ) )的長(zhǎng)度是_ . 15. 廣義表的( c , a , (a ,b) , d , e ,( (i ,j ) ,k ) )深度是_ 。 16. 廣義表的( c , (b,a ,b) , f , e ,( (i ,j ) ,k ) )深度是_ . 17. 循環(huán)隊(duì)列在規(guī)定少用一個(gè)存儲(chǔ)空間的情況下，隊(duì)空的判定條件為_(kāi)。18. 序列4 , 2 , 5 , 3 ,8, 6,采用冒泡排序算法(升序),經(jīng)一趟冒泡后, 結(jié)果序列是 _。19.c語(yǔ)言中,字符串“E”存儲(chǔ)時(shí)占 個(gè)字節(jié) 。 20. 待排序的序列為8,3,4,1,2,5,

37、9, 采用直接選擇排序算法,當(dāng)進(jìn)行了兩趟選擇后,結(jié)果序列 為_(kāi)。21一棵二叉樹(shù)中有n個(gè)非葉結(jié)點(diǎn)，每一個(gè)非葉結(jié)點(diǎn)的度數(shù)都為2，則該樹(shù)共有_ 個(gè)葉結(jié)點(diǎn)。 22. 線性表用_方式存儲(chǔ)可以隨機(jī)訪問(wèn) 。 23在對(duì)一組記錄(55,39,97,22,16,73,65,47,88)進(jìn)行直接插入排序時(shí)，當(dāng)把第7個(gè)記錄65 插 入到有序表時(shí)，為尋找插入位置需比較_次。 24. 順序表,6，5，1, 2, 4, 3, 8，7經(jīng)過(guò)一趟(1,1)歸并后的結(jié)果序列為_(kāi)。 25. 對(duì)一組記錄（5，8，9，2，12，7，56，44，39）進(jìn)行直接插入排序(由小到大排序) ，當(dāng)把第6個(gè)記錄7插入有序表，為尋找插入位置需比較_次。 26設(shè)有一棵深度為6的完全二叉樹(shù)，第6層上有3個(gè)結(jié)點(diǎn)，該樹(shù)共有_個(gè)結(jié)點(diǎn)。（根所在結(jié)點(diǎn)為第1層） 27一棵有16個(gè)葉結(jié)點(diǎn)的哈夫曼樹(shù)，則該樹(shù)共有_個(gè)結(jié)點(diǎn)。 28.20個(gè)元素進(jìn)行冒泡法排序，通常第6趟冒泡要進(jìn)行_ _次元素間的比較。 29對(duì)稀疏矩陣進(jìn)行壓縮存儲(chǔ),可采用三元組表，一個(gè)6行7列的稀疏矩陣A共有38個(gè)零元素，其相應(yīng)的三元組表共有_個(gè)元素。 while( *p!=0) n+; p+; 結(jié)果中，n的值是_。三、綜合題1設(shè)查找表為(1,10,11,14,23,2