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

1、數(shù)據(jù)結(jié)構(gòu)期末綜合練習(xí)2018年 12月期末練習(xí)一一、單項(xiàng)選擇題1. 一種邏輯結(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ù)元素的值2同一種邏輯結(jié)構(gòu)（）。A.只能有唯一的存儲(chǔ)結(jié)構(gòu)B.可以有不同的存儲(chǔ)結(jié)構(gòu)C 只能表示某一種數(shù)據(jù)元素之間的關(guān)系D 以上三種說(shuō)法均不正確3 . 對(duì)鏈表 , 以下敘述中正確的是（）。A.不能隨機(jī)訪問(wèn)任一結(jié)點(diǎn)B .結(jié)點(diǎn)占用的存儲(chǔ)空間是連續(xù)的C.插入刪除元素的操作一定要要移動(dòng)結(jié)點(diǎn)D .可以通過(guò)下標(biāo)對(duì)鏈表進(jìn)行直接訪問(wèn)4鏈表所具備的特點(diǎn)是（）。A.可以隨機(jī)訪問(wèn)任一結(jié)點(diǎn)B .占用連續(xù)的存儲(chǔ)空間C.插入刪除元素的操作不需

2、要移動(dòng)元素結(jié)點(diǎn)D .可以通過(guò)下標(biāo)對(duì)鏈表進(jìn)行直接訪問(wèn)5線性表在存儲(chǔ)后, 如果相關(guān)操作是: 要求已知第i 個(gè)結(jié)點(diǎn)的位置訪問(wèn)該結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)，則采用（）存儲(chǔ)方式是不可行的。A.單鏈表 B ,雙鏈表 C ,單循環(huán)鏈表 D .順序表6數(shù)據(jù)的物理結(jié)構(gòu)（）。A 與數(shù)據(jù)的邏輯結(jié)構(gòu)無(wú)關(guān)B 僅僅包括數(shù)據(jù)元素的表示C.只包括數(shù)據(jù)元素間關(guān)系的表示 D .包括數(shù)據(jù)元素的表示和關(guān)系的表示7棧和隊(duì)列的共同特點(diǎn)是（）。A.都是先進(jìn)后出 B.元素都可以隨機(jī)進(jìn)出C.只容許在端點(diǎn)處插入和刪除元素D .都是先進(jìn)先出8線性結(jié)構(gòu)中數(shù)據(jù)元素的位置之間存在（）的關(guān)系。A 一對(duì)一B 一對(duì)多9元素2， 4， 6， 8 按順序依次進(jìn)棧，按該棧的的

3、可能輸出序列依次入隊(duì)列，該隊(duì)列的可能輸出序列是（）（進(jìn)棧出棧可以交替進(jìn)行）。A 8， 6，2，4 B 8，4，2，6C 6，2， 4， 8D 8，6，4，210以下表中可以隨機(jī)訪問(wèn)的是（）。A 單向鏈表B 雙向鏈表C.單向循環(huán)鏈表D.順序表11 在一個(gè)不帶頭結(jié)點(diǎn)的鏈隊(duì)中，假設(shè)f 和 r 分別為隊(duì)頭和隊(duì)尾指針，則從該對(duì)列中刪除一個(gè)結(jié)點(diǎn)并把結(jié)點(diǎn)的值保存在變量x 中的運(yùn)算為（）。A x=rdata ；r=rnext 。B r=r next 。 x=r dataC x=fdata ；f=fnext 。D f=f next 。 x=f data12算法的時(shí)間復(fù)雜度與（）有關(guān)。A.所使用的計(jì)算機(jī)B .與計(jì)

4、算機(jī)的操作系統(tǒng)C.與算法本身D .與數(shù)據(jù)結(jié)構(gòu)13.設(shè)有一個(gè)20階的對(duì)稱矩陣 A,采用壓縮存儲(chǔ)的方式，將其下三角部分以行序?yàn)橹餍虼鎯?chǔ)到一維數(shù)組B 中（數(shù)組下標(biāo)從1 開始），則數(shù)組中第38 號(hào)元素對(duì)應(yīng)于矩陣中的元素是（）。A a10,8B a7,6C a9,2D a8,514設(shè)有一個(gè)長(zhǎng)度為n 的順序表，要?jiǎng)h除第i 個(gè)元素需移動(dòng)元素的個(gè)數(shù)為（）。A n-i+1 B n-i C n-i-1 D i15.在C語(yǔ)言中，分別存儲(chǔ)“S"和's',各需要占用（）字節(jié)。A 一個(gè)和兩個(gè)B 兩個(gè)C 一個(gè)D 兩個(gè)和一個(gè)16在一個(gè)單鏈表中，p、 q 分別指向表中兩個(gè)相鄰的結(jié)點(diǎn)，且q 所指結(jié)點(diǎn)是p

5、 所指結(jié)點(diǎn)的直接后繼，現(xiàn)要?jiǎng)h除q 所指結(jié)點(diǎn)，可用的語(yǔ)句是（）。A p=q->next B p->next=q C p->next=q next D q->next=NULL17 一棵有n 個(gè)結(jié)點(diǎn)，采用鏈?zhǔn)酱鎯?chǔ)的二叉樹中，共有（）個(gè)指針域被有效使用（即指針域?yàn)榉强眨 n+1 B n C n-1 D n-218從一個(gè)棧頂指針為top 的鏈棧中刪除一個(gè)結(jié)點(diǎn)時(shí)，用變量x 保存被刪結(jié)點(diǎn)的值，則執(zhí)行（）。A x=top->data 。top=top->next。Bx=top->data 。Ctop=top->next。 x=top->data。Dt

6、op=top->next。 x=data 。19 在一棵二叉樹中，若編號(hào)為i 的結(jié)點(diǎn)存在雙親結(jié)點(diǎn)，則雙親結(jié)點(diǎn)的順序編號(hào)為（）。A i/2.0B i/2 向下取整C 2i+1 D i+220在一個(gè)鏈隊(duì)中，假設(shè)f 和 r 分別為隊(duì)頭和隊(duì)尾指針，則刪除一個(gè)結(jié)點(diǎn)的運(yùn)算為（）。A r=f->next。 B r=r->next。 C f=f->next 。 D f=r->next 。21設(shè)一棵哈夫曼樹共有2n+1 個(gè)結(jié)點(diǎn)，則該樹有（）個(gè)非葉結(jié)點(diǎn)。A n Bn+1C n-1 D2n22. 一個(gè)棧的進(jìn)棧序列是a, b, c, d, e,則棧的不可能輸出序列是（）（進(jìn)棧出?？梢越惶?/p>

7、進(jìn)行）。A dceab B edcba C decba D abcde23一棵完全二叉樹共有4 層，且第4 層上有 2 個(gè)結(jié)點(diǎn)，該樹共有（）個(gè)非葉子結(jié)點(diǎn)（ 根為第一層） 。A 5B 4C 3D 924有一個(gè)長(zhǎng)度為10 的有序表，按折半查找對(duì)該表進(jìn)行查找，在等概率情況下查找成功的平均比較次數(shù)為（）。A 26/10 B 29/10 C 29/9 D 31/1025如圖1 所示的一個(gè)圖，若從頂點(diǎn)a 出發(fā)，按廣度優(yōu)先搜索法進(jìn)行遍歷，則可能得到的一種頂點(diǎn)序列為（）。A abedfc B acfebd C aebcdf D aebcfd26 .排序算法中，從未排序序列中依次取出元素與已排序序列（初始為空）

8、中的元素進(jìn)行比較（要求比較次數(shù)盡量少），然后將其放入已排序序列的正確位置的方法是（）。A.冒泡 B.直接插入C.折半插入 D.選擇排序27 . 一組記錄的關(guān)鍵字序列為（56, 30,89 , 66, 48, 50, 94,87,100 ）,利用快速排序，以第一個(gè)關(guān)鍵字為分割元素，經(jīng)過(guò)一次劃分后結(jié)果為（）。A . 30, 50,48 , 56, 66, 89, 94,100,87B , 50, 30,48 , 56, 66, 89, 94,87,100C. 48, 30,50 , 56, 66, 89, 94,87,100D . 50, 30,48 , 66, 56, 89, 94,87,100

9、28 .設(shè)有一個(gè)10階的對(duì)稱矩陣 A,采用壓縮存儲(chǔ)的方式，將其下三角部分以行序?yàn)橹鞔鎯?chǔ)到一維數(shù)組 B中（數(shù)組下標(biāo)從1開始），則矩陣中元素A8,5在一維數(shù)組 B中的下標(biāo)是（ ）。A. 33 B . 32 C. 85 D . 4129 .線性表以（）方式存儲(chǔ)，能進(jìn)行折半查找。A .關(guān)鍵字有序的鏈接B.順序C.關(guān)鍵字有序的順序 D.數(shù)組C.多對(duì)多D .每一個(gè)元素都有一個(gè)直接前驅(qū)和一個(gè)直接后繼30 .在一個(gè)無(wú)向圖中，所有頂點(diǎn)的度數(shù)之和等于邊數(shù)的（）倍。A. 3 B . 2.5 C . 1.5 D . 2二、填空題1 .數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)中的表示稱為 結(jié)構(gòu)。2 .棧和隊(duì)列的操作特點(diǎn)分別是 和 _o3

10、 .求兩個(gè)n階矩陣的乘積，算法的基本操作為 ，時(shí)間復(fù)雜度為 。4 .結(jié)構(gòu)中的數(shù)據(jù)元素存在多對(duì)多的關(guān)系稱為 結(jié)構(gòu)。5 . 設(shè)有一個(gè)長(zhǎng)度為25的順序表，第8號(hào)元素到第25號(hào)元素依次存放的值為 8,9,10,11, 25,某人想要在第 8個(gè)元素前插入1個(gè)元素7 （也就是插入元素作為新表的第8個(gè)元素），他的做法是從第8號(hào)元素開始，直到第25號(hào)元素依次向后移動(dòng) 1個(gè)位置，然后把7存放在8號(hào)位置，其結(jié)果是新表中第25號(hào)元素的值為 。6 .根據(jù)數(shù)據(jù)元素間關(guān)系的不同特性，通常可分為集合、線性、四類基本結(jié)構(gòu)。7 .在雙向鏈表中，要在p所指的結(jié)后插入q所指的結(jié)點(diǎn)（設(shè)q所指的結(jié)點(diǎn)已賦值），其中所用的一條語(yǔ)句（p-&

11、gt;next） ->prior=q ;的功能是使 P所指結(jié)點(diǎn)的 指向q。8 .要求在n個(gè)數(shù)據(jù)元素中找其中值最大的元素，設(shè)基本操作為元素間的比較。則比較的次數(shù)和算法的時(shí)間復(fù)雜度分別為 和。9 .設(shè)有一個(gè)帶頭結(jié)點(diǎn)的，頭指針為head的單向鏈表，p指向表中某一個(gè)結(jié)點(diǎn)，且有p->next= =NULL,現(xiàn)要?jiǎng)h除頭結(jié)點(diǎn)，并使該單向鏈表構(gòu)造成單向循環(huán)鏈表，通過(guò) 操彳head=head->next。 。10 .在一個(gè)單向鏈表中 p所指結(jié)點(diǎn)之后插入一個(gè)s所指向的結(jié)點(diǎn)時(shí)，應(yīng)執(zhí)行 和p->next=s。的操作。11 .從一個(gè)棧頂指針為top的鏈棧中刪除一個(gè)結(jié)點(diǎn)時(shí)，用d保存被刪結(jié)點(diǎn)的值，可

12、執(zhí)行。（結(jié)點(diǎn)的指針域?yàn)閚ext,數(shù)據(jù)域?yàn)閐ata）12 .在二叉樹的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中，通常每個(gè)結(jié)點(diǎn)中設(shè)置三個(gè)域，它們是值域、13循環(huán)鏈隊(duì)列中，設(shè) front和rear分別為隊(duì)頭和隊(duì)尾指針，（最多元素為 MaxSize,采用少用一 個(gè)元素的模式工判斷循環(huán)鏈隊(duì)列為滿的條件為 。14 . 一棵二叉樹中順序編號(hào)為i的結(jié)點(diǎn)，若它存在左、右孩子，則左、右孩子編號(hào)分別為15 .對(duì)稀疏矩陣進(jìn)行壓縮存儲(chǔ)，可采用三元組表，一個(gè) 6行7列的稀疏矩陣A相應(yīng)的三元組表共有8個(gè)元素，則矩陣A共有 個(gè)零元素。16 .向一個(gè)棧頂指針為 h的鏈棧中插入一個(gè) s所指結(jié)點(diǎn)時(shí)，可執(zhí)行 s->next=h。和。17 .一棵有20個(gè)

13、結(jié)點(diǎn)的4度的樹，其中3度結(jié)1個(gè)，2度結(jié)1個(gè)，1度結(jié)2個(gè)，則該樹共有 個(gè)葉結(jié)點(diǎn)。18 .在一個(gè)鏈隊(duì)中，設(shè) f和r分別為隊(duì)頭和隊(duì)尾指針，則插入s所指結(jié)點(diǎn)的操作為 和r=s。（結(jié)點(diǎn)的指針域?yàn)閚ext）19 . 一棵有18個(gè)結(jié)點(diǎn)的二叉樹，其 2度結(jié)點(diǎn)數(shù)的個(gè)數(shù)為 8,則該樹共有 個(gè)1度結(jié)點(diǎn)20 .設(shè)有一棵深度為 4的完全二叉樹，第四層上有5個(gè)結(jié)點(diǎn)，該樹共有 個(gè)結(jié)點(diǎn)。（根所在結(jié)點(diǎn)為第1層）21 .如圖2所示的二叉樹，其先序遍歷序列為 。圖222 .對(duì)稀疏矩陣進(jìn)行壓縮存儲(chǔ)，矩陣中每個(gè)非零元素對(duì)應(yīng)的三元組包括該元素的、 和 三項(xiàng)信息。23 .在查找表中，通過(guò)記錄的某關(guān)鍵字能唯一地確定一個(gè)記錄，該關(guān)鍵字稱為24

14、 .在對(duì)一組記錄（55,39,97,22,16,73,65,47,88）進(jìn)行直接插入排序時(shí)，當(dāng)把第 7個(gè)記錄65 插入到有序表時(shí)，為尋找插入位置需比較 次。三、綜合題1. (1)對(duì)給定權(quán)值3, 1 , 4, 4, 5, 6,構(gòu)造深度為5的哈夫曼樹。(設(shè)根為第1層) (2)求樹的帶權(quán)路徑長(zhǎng)度。(3)鏈接存儲(chǔ)上述哈夫曼樹，結(jié)點(diǎn)中共有多少個(gè)個(gè)指針域?yàn)榭?，說(shuō)明理由.2.(1)以2, 3, 4, 7, 8, 9作為葉結(jié)點(diǎn)的權(quán)，構(gòu)造一棵哈夫曼樹(要求每個(gè)結(jié)點(diǎn)的左子樹根結(jié)點(diǎn)的權(quán)小于等于右子樹根結(jié)點(diǎn)的權(quán))，給出相應(yīng)權(quán)重值葉結(jié)點(diǎn)的哈夫曼編碼。(2) 一棵哈夫曼樹有n個(gè)葉結(jié)點(diǎn)，它一共有多少個(gè)結(jié)點(diǎn)？簡(jiǎn)述理由？3.

15、(1)如下的一棵樹，給出先序遍歷序列(2)把1,2,3,4,5,6,7,8,9填人，使它成為一棵二叉排序樹提示：設(shè)圖中的樹是二叉排序樹，找出中序遍歷序列與1, 2,9的對(duì)應(yīng)關(guān)系(3)請(qǐng)?jiān)谠摌渲性俨迦胍粋€(gè)結(jié)點(diǎn)3.5作為葉結(jié)點(diǎn)，并使它仍然是一棵二叉排序樹。4. 一組記錄的關(guān)鍵字序列為( 46, 79, 56, 38, 40, 84)(1)利用快速排序的方法，給出以第一個(gè)記錄為基準(zhǔn)得到的一次劃分結(jié)果(給出逐次交 換元素的過(guò)程，要求以升序排列)5. )對(duì)上述序列用堆排序的方法建立大根堆，要求以二叉樹逐次描述建堆過(guò)程。5設(shè)查找表為(5,6,7,8,9,10,11,12,13,14)( 1 )畫出對(duì)上述有

16、序表進(jìn)行折半查找所對(duì)應(yīng)的判定樹(要求以數(shù)據(jù)元素作為樹結(jié)點(diǎn))(2) 給出二叉排序樹的定義, 針對(duì)上述折半查找所對(duì)應(yīng)的判定樹的構(gòu)造過(guò)程,說(shuō)明判定樹是否是二叉排序樹(設(shè)樹中沒(méi)有相同結(jié)點(diǎn))？(3)為了查找元素5.5，經(jīng)過(guò)多少次元素間的比較才能確定不能查到？6設(shè)查找表為(50,60,75,85,96,98,105,110,120,130)1 1) 說(shuō)出進(jìn)行折半查找成功查找到元素120 需要進(jìn)行多少次元素間的比較？(2)為了折半查找元素95，經(jīng)過(guò)多少次元素間的比較才能確定不能查到？3)畫出對(duì)上述有序表進(jìn)行折半查找所對(duì)應(yīng)的判定樹(要求以數(shù)據(jù)元素作為樹結(jié)點(diǎn))四、程序填空題2 .以下函數(shù)為直接選擇排序算法，對(duì)

17、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)。3 .以下是用尾插法建立帶頭結(jié)點(diǎn)且有n個(gè)結(jié)點(diǎn)的單向鏈表的程序，結(jié)點(diǎn)中的數(shù)據(jù)域從前向后依次為1,2,3,n,完成程序中空格部分。NODE *create(n)

18、NODE *head , *p, *q 。int i。p=(NODE*)malloc(sizeof(NODE)。head= (1)。(2)。p next=NULL 。 /* 建立頭結(jié)點(diǎn) */for(i=1 。 i<=n。 i+) p= (3)。p data=i。p next=NULL 。q next= (4)。(5)。return(head)。3 .設(shè)有一個(gè)頭指針為 head的不帶頭結(jié)點(diǎn)單向鏈表，且p、q是指向鏈表中結(jié)點(diǎn)類型的指 針變量，p指向鏈表中某結(jié)點(diǎn) a (設(shè)鏈表中沒(méi)有結(jié)點(diǎn)的數(shù)據(jù)域與結(jié)點(diǎn)a的數(shù)據(jù)域相同)寫出相關(guān)語(yǔ)句(1).使該單向鏈表成為單向循環(huán)鏈表(2)刪去a結(jié)點(diǎn)q=p。x=p-

19、>data。while (q->next!=NULL ) q=q->next。q=p。 p=p->next。 while(p->data!=x) q=p。_(2),4.以下程序是中序遍歷二叉樹的遞歸算法的程序，完成程序中空格部分(樹結(jié)構(gòu)中 左、右指針域分別為left和right,數(shù)據(jù)域data為字符型，BT指向根結(jié)點(diǎn))。void Inorder (struct BTreeNode *BT) if(BT!=NULL)7 / 36圖4期末復(fù)習(xí)一答案一、單項(xiàng)選擇題1 . C 2 . B3 . A4 . C5 . A 6 .D7 . C8 . A9 . D10 . D 1

20、1 . C9 / 3613. C14. B15. D16. C17. C 18A19. B 20 . C21. A22. A 23 . B24, B25.26. C27. B 28 . A29. C 30 . D二、填空題1. .物理(存儲(chǔ))2. 后進(jìn)先出、先進(jìn)先出3. 乘法 O(n3)4. 圖狀(網(wǎng)狀)5. 86. 樹形圖狀7. 直接前驅(qū)的左指針8. n-1,O(n)、9. p->next= head。10. s->next=p->next 。11. d=top->data。 top=top->next。12. 左指針右指針13. front= =(rear+1

21、)%MaxSize14. 2i 2i+115. 3416. h=s。17. 1318. r->next=s 。19. 120. 1221, 21534789622. 行下標(biāo)、列下標(biāo)、非零元素值23. 主關(guān)鍵字24. 3三、綜合應(yīng)用題1. (1)(2) WPL=3*4+1*4+4*3+6*2+4*2+5*2=58(3)共11個(gè)結(jié)點(diǎn),22個(gè)指針域，除根結(jié)點(diǎn)外，每個(gè)結(jié)點(diǎn)對(duì)應(yīng)一個(gè)指針域.，共10個(gè)指針域非空，故 有 22-10=12個(gè)空指針域，2.圖52: 11103: 11114: 1107: 008: 019: 102 2) 2n-1個(gè)，因?yàn)榉侨~結(jié)點(diǎn)數(shù)比葉結(jié)點(diǎn)數(shù)少一個(gè)。3 .(1) A1 A

22、2 A4 A7 A8 A5 A9 A3 A6(2)610 / 3612134.(1)初始序列46,79,56,38,40,8440,79,56,38,40,8440,79,56,38,79,8440,38,56,38,79,8440,38,56,56,79,8440,38,46,56,79,845.(1)圖7(2)二叉排序樹或者是一棵空樹，或者是一棵具有下列性質(zhì)的二叉排：若它的左子樹 非空，則左子樹的所有結(jié)點(diǎn)的值都小于它的根結(jié)點(diǎn)的值；若它的右子樹非空，則右子 樹的所有結(jié)點(diǎn)的值都大于(若允許結(jié)點(diǎn)有相同的值，則大于等于)它的根結(jié)點(diǎn)的值。 左，右子樹也是一棵二叉排序樹，按定義判定樹是二叉排序樹。3次

23、6.(1)3 次(2)4 次圖8四、程序填空題(1) n-1(2) n(3) k=j(4) ai=ak(5) a止temp11 / 36216 / 36head）?，F(xiàn)要?jiǎng)h除（進(jìn)棧出?？稍摋５目?) p2) q=p3) (NODE*)malloc(sizeof(NODE)4) p5) q=p3(1) q->next=head 。(2) p=p->next 。(3) q->next=p->next 。41) Inorder(BT->left)2) printf( “ %c” ,BT->data)3) Inorder(BT->right)期末練習(xí)二一、單項(xiàng)選

24、擇題1 . 結(jié)構(gòu)中的元素之間存在一對(duì)多的關(guān)系是（）。A.集合B.線性結(jié)構(gòu)C 樹形結(jié)構(gòu)D 圖狀結(jié)構(gòu)2 .在C語(yǔ)言中，順序存儲(chǔ)長(zhǎng)度為3的字符串，需要占用（）個(gè)字節(jié)。A 4 B 3 C 6 D 123 . 對(duì)不帶頭結(jié)點(diǎn)的單向鏈表, 判斷是否為空的條件是（）（設(shè)頭指針為A head=NULL B head->next= =NULLC head->next= =head D head =NULL4串函數(shù)StrCat （ a,b ）的功能是進(jìn)行串（）。A比較B .復(fù)制 C .賦值D .連接5. 在一個(gè)不帶頭結(jié)點(diǎn)的單循環(huán)鏈表中，p、 q 分別指向表中第一個(gè)結(jié)點(diǎn)和尾結(jié)點(diǎn)，現(xiàn)要?jiǎng)h除第一個(gè)結(jié)點(diǎn)，可用的

25、語(yǔ)句是（）。A p=q->next 。 p=p->next 。B p->next=q。 p=p->next。C p->next=q->next 。 q=p。D p=p->next。 q->next=p 。6一棵有n 個(gè)結(jié)點(diǎn)采用鏈?zhǔn)酱鎯?chǔ)的二叉樹中，共有（）個(gè)指針域?yàn)榭?。A n+1 B n C n-1 D n-27一個(gè)棧的進(jìn)棧序列是1 ， 2， 3， 4， 5，則棧的不可能輸出序列是（）（進(jìn)棧出?？梢越惶孢M(jìn)行）。A 12345 B 43512 C 45321 D 543218設(shè)一棵哈夫曼樹共有n 個(gè)非葉結(jié)點(diǎn)，則該樹有（）個(gè)葉結(jié)點(diǎn)。A n B n+1

26、C n-1 D 2n9一個(gè)隊(duì)列的入隊(duì)序列是2， 4， 6， 8，按該隊(duì)列的輸出序列使各元素依次入棧，該棧的可能輸出序列是（）。A. 8, 6, 4, 2 B . 6, 2, 4, 8C. 8, 4, 2, 6D. 8, 2, 4, 610.從一個(gè)棧頂指針為top的鏈棧中刪除一個(gè)結(jié)點(diǎn)時(shí)，用變量 x保存被刪結(jié)點(diǎn)的值，則執(zhí)行 （ ）。A. x=top->data 。 top=top next。 B . x=top->data 。C. top=top->next 。 x=top->data 。 D . top=top->next 。 x=data 。11.在一個(gè)鏈隊(duì)中，假

27、設(shè)f和r分別為隊(duì)頭和隊(duì)尾指針，已生成一個(gè)結(jié)點(diǎn)p,要為結(jié)點(diǎn)p賦值x,并入隊(duì)的運(yùn)算為（）。A . p->data=x 。 p->next=NULL 。 f->next=p 。 f=p 。B. p->data=x 。 p->next=NULL 。 r->next=p 。 r=p。C . p->data=x 。 p->next=r 。 r=s。D. p->data=x 。 p->next=f 。 f=s 。12. 一棵完全二叉樹共有5層，且第5層上有六個(gè)結(jié)點(diǎn)，該樹共有（）個(gè)結(jié)點(diǎn)。A. 30 B . 20 C. 21 D . 2337,6在一維

28、數(shù)組.27）倍。B中的下標(biāo)是13 .設(shè)有一個(gè)25階的對(duì)稱矩陣 A,采用壓縮存儲(chǔ)的方式，將其下三角部分以行序?yàn)橹餍虼?儲(chǔ)到一維數(shù)組 B中（數(shù)組下標(biāo)從 1開始），則矩陣中元素.（ ）。A. 34 B . 14 C . 26 D14 .在一個(gè)無(wú)向圖中，所有頂點(diǎn)的度數(shù)之和等于邊數(shù)的（A . 3 B . 2.5 C . 1.5 D . 215 .以下程序段的結(jié)果是c的值為()。char a5=" 1236789"，int *p=a, int c=0。while(*p+)c+ 。A . 8,B , 7 C . 10 D . 1216 .已知如圖1所示的一個(gè)圖，若從頂點(diǎn) V1出發(fā)，按深度

29、優(yōu)先搜索法進(jìn)行遍歷，則可能得到的一種頂點(diǎn)序列為（）。A MV2V4V8V5V3V6WBC. V1V2V4V8V3V5V6V7,MV2 V4V5V8V3 V6”D . V1V3V6V7V2V4V5V8圖117 . 一棵有23個(gè)結(jié)點(diǎn)，采用鏈?zhǔn)酱鎯?chǔ)的二叉樹中，共有（）個(gè)指針域?yàn)榭铡 . 24B. 25C. 23D. 4518 .已知如圖2所示的一個(gè)圖，若從頂點(diǎn)a出發(fā)，按廣度優(yōu)先搜索法進(jìn)行遍歷，則可能得到的一種頂點(diǎn)序列為（）。A.abcedf B. abcefd C. aebcfd D. acfdeb圖219 .在一棵二叉樹中，若編號(hào)為i的結(jié)點(diǎn)是其雙親結(jié)點(diǎn)的左孩子，則雙親結(jié)點(diǎn)的順序編號(hào)為（）。A .

30、 i/2B . 2i-1 C . 2i+1 D . i/2-120 .對(duì)二叉排序樹進(jìn)行（）遍歷，可以使遍歷所得到的序列是有序序列。.按層次B .后序 C .中序D .前序21 .設(shè)一棵哈夫曼樹共有2n+1個(gè)葉結(jié)點(diǎn)，則該樹有（）個(gè)葉結(jié)點(diǎn)。A . n-1 B . n C , n+1 D . 2n22 .在有序表2, 4, 7, 14, 34, 43, 47, 64, 75, 80, 90, 97, 120中，用折半查找法 查找值80時(shí)，經(jīng)（）次比較后查找成功。A 4 B . 2C. 3 D. 523 .已知如圖3所示的一個(gè)圖，若從頂點(diǎn) a出發(fā)，按深度優(yōu)先搜索法進(jìn)行遍歷，則可能得到 的一種頂點(diǎn)序列為

31、（）。A . abecdf B . acfebd C . aebcfd D . aedbfc24 .有一個(gè)長(zhǎng)度為 9的有序表，按折半查找對(duì)該表進(jìn)行查找，在等概率情況下查找成功的平均比較次數(shù)為（）。A. 25/10 B . 25/9 C . 20/9 D .17/925.已知如圖4所示的一個(gè)圖，若從頂點(diǎn) 種頂點(diǎn)序列為（）。A.BADEHCFGB.ADEHCGFC.BADECHFGB出發(fā)，按廣度優(yōu)先法進(jìn)行遍歷，則可能得到的一D.BADEHCFG圖426 .排序算法中，從未排序序列中依次取出元素與已排序序列（初始為空）中的元素進(jìn) 行比較（要求比較次數(shù)盡量少），然后將其放入已排序序列的正確位置的方法是

32、（）。A冒泡 B .直接插入C .折半插入 D .選擇排序27 , 一組記錄的關(guān)鍵字序列為（46, 38, 56, 40, 79, 84）,利用快速排序，以第一個(gè)關(guān)鍵字為分割元素，經(jīng)過(guò)一次劃分后結(jié)果為（）。A . 40, 38, 46, 79, 56, 84 B , 40, 38, 46, 56, 79, 84C. 40, 38, 46, 84, 56, 79 D , 38, 40, 46, 56, 79, 8428 , 一組記錄的關(guān)鍵字序列為（46, 79, 56, 38, 40, 84）,利用快速排序，以第一個(gè)關(guān)鍵字為分割元素，經(jīng)過(guò)一次劃分后結(jié)果為（）。A . 40, 38,46,79,5

33、6,84B , 40, 38, 46, 56, 79, 84C. 40, 38,46,84,56,79D , 38, 40, 46, 56, 79, 8429 .在有序表21 ,23,28,33,43,45, 46, 73, 77, 78, 89, 99,106中，用折半查找值43時(shí)，經(jīng)（）次比較后查找成功。A. 6 B.3 C.8 D . 430.排序方法中，從尚未排序序列中挑選元素，并將其依次放入已排序序列（初始為空）的 一端的方法，稱為（）排序。A .歸并B .插入C .快速D .選擇二、填空題1 .本書中介紹的樹形結(jié)構(gòu)和 屬非線性結(jié)構(gòu)。2 .在二叉樹的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中，通常每個(gè)結(jié)點(diǎn)中設(shè)置

34、三個(gè)域，它們是 、 右指針。3 .設(shè)有一個(gè)長(zhǎng)度為 18的順序表，要在第 4個(gè)元素之前插入 2個(gè)元素（也就是插入元素作 為新表的第5個(gè)和第4個(gè)元素），則最少要移動(dòng)元素的個(gè)數(shù)為（）。4 . 一棵二叉樹中順序編號(hào)為i的結(jié)點(diǎn)，若它存在左、右孩子，則左、右孩子編號(hào)分別為5 .在雙向鏈表中，要?jiǎng)h除 p所指的結(jié)點(diǎn)，可以先用語(yǔ)句（p->prior） ->next=p->next ;然 再用語(yǔ)句。6 .串的兩種最基本的存儲(chǔ)方式是 和。7 .在一個(gè)單向鏈表中 p所指結(jié)點(diǎn)之后插入一個(gè)s所指向的結(jié)點(diǎn)時(shí)，應(yīng)執(zhí)行 s->next=p->next。和 的操作.8 . 一棵有2n-1個(gè)結(jié)點(diǎn)的二叉

35、樹，其每一個(gè)非葉結(jié)點(diǎn)的度數(shù)都為2,則該樹共有 個(gè)葉結(jié)點(diǎn)。9 . 一個(gè)棧和一個(gè)隊(duì)列的輸入序列都為abcdefg ,它們可能有相同的輸出序列嗎？（若沒(méi)有則回答沒(méi)有，若有則寫出序列，進(jìn)棧出?？梢越惶孢M(jìn)行）。10 .對(duì)于一棵具有 n個(gè)結(jié)點(diǎn)的二叉樹，其相應(yīng)的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中共有 個(gè)指針域?yàn)?空。11 .從一個(gè)棧頂指針為top的鏈棧中取棧頂元素，用d保存棧頂元素的值，可執(zhí)行。（結(jié)點(diǎn)的數(shù)據(jù)域?yàn)?data）12 . 遍歷二叉排序樹可得到一個(gè)有序序列。13 .循環(huán)鏈隊(duì)列中，設(shè)front和rear分別為隊(duì)頭和隊(duì)尾指針，（最多元素為 MaxSize,）,判斷循環(huán) 鏈隊(duì)列為空的條件是 為真。14 .如圖5所示的二叉樹，

36、其后序遍歷序列為。15 .對(duì)稀疏矩陣進(jìn)彳T壓縮存儲(chǔ)，可采用三元組表，設(shè)a是稀疏矩陣A相應(yīng)的三元組表類型（結(jié)構(gòu)體類型）變量，a中的一個(gè)成員項(xiàng)是三元組類型的結(jié)構(gòu)體數(shù)組data,按書中定義，若a.data0.i=2。a.data0.j=3。a.data0.v=16。它提供的 A 數(shù)組的相關(guān)信息有 16 .如圖6所示的二叉樹，其先序遍歷序列為 。圖617 .設(shè)有一棵深度為 5的完全二叉樹，該樹共有 20個(gè)結(jié)點(diǎn)，第五層上有個(gè)葉結(jié)點(diǎn)。（根所在結(jié)點(diǎn)為第1層）18 .圖的深度優(yōu)先搜索和廣度優(yōu)先搜索序列不一定是唯一的。此斷言是的。（回答正確或不正確）19 .中序遍歷 樹可得到一個(gè)有序序列。20 .二叉樹為二叉排

37、序的充分必要條件是其任一結(jié)點(diǎn)的值均大于其左孩子的值、小于其右孩子的值。這種說(shuō)法是 的。（回答正確或不正確）21 .如圖7所示的二叉樹，其后序遍歷序列為 。22 .對(duì)記錄序列排序是指按記錄的某個(gè)關(guān)鍵字排序，記錄序列按 排序結(jié)果是唯一 的。23 .給定一組權(quán)重值，構(gòu)造哈夫曼樹，哈夫曼樹的高度一定是唯一的， 這種說(shuō)法是 的。（回答正確或不正確）24 .按某關(guān)鍵字對(duì)記錄序列排序，若在排序前和排序后仍保持它們的前后關(guān)系，則排序算法 是穩(wěn)定的，否則是不穩(wěn)定的。三、綜合題1. （1）說(shuō)明什么是頂點(diǎn)活動(dòng)網(wǎng)（AOV網(wǎng)）和拓?fù)湫蛄校?）設(shè)有向圖G如下，寫出3種拓?fù)湫蛄?，?）在圖G中增加一條邊，使圖 G僅有一條拓

38、撲序列a圖82.設(shè)查找表為(16,15,20,53,64,7),(1)用冒泡法對(duì)該表進(jìn)行排序(要求升序排列)，寫出每一趟的排序過(guò)程，通常對(duì)n個(gè)元素進(jìn)行冒泡排序要進(jìn)行多少趟冒泡？第 j趟要進(jìn)行多少次元素間的比較？(2)在排序后的有序表的基礎(chǔ)上，畫出對(duì)其進(jìn)行折半查找所對(duì)應(yīng)的判定樹.(要求以數(shù)據(jù)元素作為吉點(diǎn))3.如下是一棵二叉排序樹，A1,A2,A9代表1, 2, 3,9中各個(gè)不同數(shù)字，(1)給出對(duì)該樹中序遍歷的結(jié)果(2) A3,A5,A7的值各為多少？(3)請(qǐng)?jiān)谠摌渲性俨迦胍粋€(gè)結(jié)點(diǎn)9 .5作為葉結(jié)點(diǎn)，并使它仍然是一棵二叉排序樹4(1)設(shè)有查找表5,14,2,6,18,7,4,16,3,依次取表中數(shù)

39、據(jù)，構(gòu)造一棵二叉排序樹。(2)說(shuō)明如何由序列的二叉排序樹得到相應(yīng)序列的排序結(jié)果，對(duì)上述二叉排序給出中 序遍歷的結(jié)果。5(1) 設(shè)有查找表17， 26， 14， 16， 15， 30， 18， 19， 28，依次取表中數(shù)據(jù)構(gòu)造一棵二叉排序樹 .(2) 對(duì)上述二叉樹給出后序遍歷的結(jié)果(3) . 對(duì)上述二叉樹給出中后序遍歷的結(jié)果(4)在上述二叉樹中查找元素15共要進(jìn)行多少次元素的比較?6(1 )對(duì)給定權(quán)值2， 1 ， 3， 3， 4， 5，構(gòu)造哈夫曼樹。( 2)同樣用上述權(quán)值構(gòu)造另一棵哈夫曼樹，使兩棵哈夫曼樹有不同的高度，并分別求兩棵樹的帶權(quán)路徑長(zhǎng)度。四、程序填空題1以下函數(shù)是二叉排序樹的查找算法，

40、若二叉樹為空，則返回根結(jié)點(diǎn)的指針，否則，返回值是指向樹結(jié)點(diǎn)的結(jié)構(gòu)指針 p (查找成功p指向查到的樹結(jié)點(diǎn)，不成功 p指向?yàn)?NULL完成程序中的空格typedef struct Bnode int key 。struct Bnode *left 。struct Bnode *right 。 Bnode。Bnode *BSearch(Bnode *bt, int k)/* bt用于接收二叉排序樹的根結(jié)點(diǎn)的指針，k用以接收要查找的關(guān)鍵字*/ Bnode *p 。if(bt=_(1)return (bt)。p=bt 。while(p->key!=_(2) if(k<p->key)_(

41、3)。else_(4)。if(p=NULL) break。return( _(5) 。3 . 設(shè)有一個(gè)頭指針為head 的不帶頭結(jié)點(diǎn)單向鏈表，p、 q 是指向鏈表中結(jié)點(diǎn)類型的指針變量， p 指向鏈表中結(jié)點(diǎn)a, (設(shè)鏈表中沒(méi)有結(jié)點(diǎn)的數(shù)據(jù)域與結(jié)點(diǎn)a 的數(shù)據(jù)域相同),寫出相關(guān)語(yǔ)句(1) .使該單向鏈表成為單向循環(huán)鏈表(2)插入結(jié)點(diǎn)s,使它成為a結(jié)點(diǎn)的直接前驅(qū)q=p。 x=p->data。while ( _(1)_ ) q=q->next。q->next=head。q=p。 p=p->next。 while(p->data!=x) q=p 。_(2)_s->next

42、=p 。 _(3)_答案一、單項(xiàng)選擇題1 C2A 3A 4D5D 6A 7B8B9A 10 A11B12 C13D14D 15 B16 A 17 A 18 B 19A 20C 21 C22A23D24B 25C 26C27 B 28B 29 B30 D二、填空題1 圖狀結(jié)構(gòu)2值域左指針3 154 2i 和 2i+15(p->next) ->prior=p->prior ；6順序存儲(chǔ)鏈?zhǔn)酱鎯?chǔ)7 p->next=s。8 n9 abcdefg10 n+111 d=top->data。12中序13 front= =rear14 gdbeihfca15 A 的第一個(gè)非零元素

43、的下標(biāo)為2， 3 ，元素為1616 abdefcg17 518正確19二叉排序20不正確21 51987643222 .主關(guān)鍵字23 .不正確24 .關(guān)鍵字相等的記錄三、綜合應(yīng)用題1 .(1)原序列 16 15 20 53 64 715 16 20 53 7 64n-1 趟15 16 20 7 53 64n-j 次15 16 7 20 53 6415 7 16 20 53 647 15 16 20 53 6423 / 36(2)圖102.原序列16 15 20 53 64 715 16 20 53 7 64 n-1 趟15 16 20 7 53 64 n-j 次15 16 7 20 53 64

44、15 7 16 20 53 647 15 16 20 53 64(2)圖11(3)平均查找長(zhǎng)度 =(1*1+2*2+3*3 ) /6=14/63.圖12(2)中序遍歷中序2, 3, 4,5, 6, 7, 14, 16, 184.圖13(2)中序遍歷中序2, 3, 4,5, 6, 7, 14, 16,185.(122 / 3621wpl1=4530 / 36(2)圖15wpl2=456.(1)答wpl1=45四、程序填空題(1) . (1) NULL(2) k(3) p=p->left(4) p=p->right(5) p(1) &a(2) d ne

45、xt=NULL(3) p->data(4) p=p->next(5) p!=NULL3.q->next!=NULL(2) p=p->next 。(3)q->next=s。4.(1) Postorder(BT->left)(2) Postorder(BT->right)(3) printf( " d ,BT->data)期末練習(xí)三一、單項(xiàng)選擇題1 .數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)內(nèi)存中的表示是指（）。A.數(shù)據(jù)元素之間的關(guān)系B .數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)C .數(shù)據(jù)元素的類型D .數(shù)據(jù)的邏輯結(jié)構(gòu)2 .在數(shù)據(jù)結(jié)構(gòu)和算法中，與所使用的計(jì)算機(jī)有關(guān)的是（）。A .數(shù)據(jù)元數(shù)間

46、的抽象關(guān)系B .數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)C .算法的時(shí)間復(fù)雜度 D.數(shù)據(jù)的邏輯結(jié)構(gòu)3 .結(jié)構(gòu)中的元素之間存在多對(duì)多的關(guān)系是（）。A.集合B.線性結(jié)構(gòu)C .樹形結(jié)構(gòu) D .圖狀結(jié)構(gòu)4 .對(duì)順序表，以下敘述中正確的是 （）。A.用一組地址連續(xù)的存儲(chǔ)單元依次存放線性表的數(shù)據(jù)元素B.各個(gè)數(shù)據(jù)元素的首地址是連續(xù)的C .數(shù)據(jù)元素不能隨機(jī)訪問(wèn)D.插入操作不需要移動(dòng)元素5 .設(shè)有一個(gè)長(zhǎng)度為 20的順序表，要在第 5個(gè)元素之前插入1個(gè)元素（也就是插入元素作為 新表的第5個(gè)元素），則移動(dòng)元素個(gè)數(shù)為（）。A . 15 B .16C.5 D . 46 .設(shè)有一個(gè)長(zhǎng)度為 25的順序表，要?jiǎng)h除第 10個(gè)元素（下標(biāo)從1開始），需移動(dòng)

47、元素的個(gè)數(shù)為 （ ）。A . 9 B . 10 C . 15 D . 167 .在一個(gè)尾指針為rear的不帶頭結(jié)點(diǎn)的單循環(huán)鏈表中，插入一個(gè)s所指的結(jié)點(diǎn)，并作為第一）。個(gè)結(jié)點(diǎn)，可執(zhí)行（A rear next= s 。 s next=rear next B rear next=s next 。C rear=s next D s next=rear next 。 rear next=s 。8 .設(shè)單向鏈表中，指針p指向結(jié)點(diǎn) A,若要?jiǎng)h除 A的直接后繼，則所需修改指針的操作為（）。A.p->next=p->next->next 。B.p=p->next 。C.p=p->n

48、ext->next 。 D.p->next=p 。9元素a， b， c,d 按順序依次進(jìn)棧，則該棧的可能輸出序列是（）（進(jìn)棧出?？梢越惶孢M(jìn)行）。A c,a,b ， dB d， b， c,aCa,c ，b，dDd，c，a,b10元素 1，3，5，7 按順序依次進(jìn)棧，按該棧的可能輸出序列依次入隊(duì)列，該隊(duì)列的可能輸出序列是（）。（進(jìn)棧出棧可以交替進(jìn)行）。A 7，5，3， 1B 7， 3，1,5C 7，5，1，3D 5,1， 3， 711從一個(gè)棧頂指針為top 的鏈棧中取棧頂元素，用變量x 保存該元素的值，則執(zhí)行（）。A x=top->data 。 top=top next 。 B

49、x=top->data 。C top=top->next 。 x=top->data 。 D top=top->next 。 x=data 。12 對(duì)一個(gè)棧頂指針為top 的鏈棧進(jìn)行進(jìn)棧操作，設(shè)P 為待進(jìn)棧的結(jié)點(diǎn)，則執(zhí)行（）。A p=top->next 。 top=top next 。 B p->next=top 。C p->next=top 。 top=p 。 D top=p 。13 .設(shè)有一個(gè)對(duì)稱矩陣A,采用壓縮存儲(chǔ)的方式，將其下三角部分以行序?yàn)橹餍虼鎯?chǔ)到一維數(shù)組 B 中（數(shù)組下標(biāo)從1 開始），B 數(shù)組共有55 個(gè)元素 , 則該矩陣是（）階的對(duì)稱矩

50、陣。A 5 B 20 C 10 D 1514 .設(shè)有一個(gè)18階的對(duì)稱矩陣 A,采用壓縮存儲(chǔ)的方式，將其下三角部分以行序?yàn)橹餍虼鎯?chǔ)到一維數(shù)組B 中（數(shù)組下標(biāo)從1 開始），則數(shù)組中第33 號(hào)元素對(duì)應(yīng)于矩陣中的元素是（）。B a7,6A a10,8 C a9,2 D a8,515 .設(shè)有一個(gè)18階的對(duì)稱矩陣 A,采用壓縮存儲(chǔ)的方式，將其下三角部分以行序?yàn)橹餍虼鎯?chǔ)到一維數(shù)組B 中（數(shù)組下標(biāo)從1 開始），則數(shù)組中第53 號(hào)元素對(duì)應(yīng)于矩陣中的元素是（）。A a8,5 ,B a10,8C a8,1,D a7,616 .設(shè)有一個(gè)17階的對(duì)稱矩陣 A,采用壓縮存儲(chǔ)的方式，將其下三角部分以行序?yàn)橹餍虼鎯?chǔ)到一維數(shù)組

51、 b中（數(shù)組下標(biāo)從1開始），則矩陣中元素&6在一維數(shù)組b中的下標(biāo)是（）。A 45,B 18 C 51 D 5317 . 以下程序段的結(jié)果是c 的值為（）。char * a5=“ 12378” ,“ 1237” ,“ 1236789” ,“ 1237” , “ 123708” 。int i,c=0。for（i=0 。 i<5:i+）if（StrCmp（ai,“1237”）=0）c+ 。A. 2,B .5 C .0 D . 123718 .串函數(shù) StrCmp （ " ABCd' , " ABCD ）的值為（）。A . 0 B . -1 C .1 D .

52、319 . 一棵采用鏈?zhǔn)酱鎯?chǔ)的二叉樹中，共有 n個(gè)指針域被有效使用（即指針域?yàn)榉强眨?。該?叉樹有（）個(gè)結(jié)點(diǎn)。A. n+1 B . n C . n-1 D . n-220 . 一棵采用鏈?zhǔn)酱鎯?chǔ)的二叉樹中有n個(gè)指針域?yàn)榭眨摱鏄涔灿校ǎ﹤€(gè)結(jié)點(diǎn)。A . n+1 B . n C . n-1 D . n-221 .在一棵二叉樹中，若編號(hào)為 i的結(jié)點(diǎn)是其雙親結(jié)點(diǎn)的右孩子，則雙親結(jié)點(diǎn)的順序編號(hào)為 （）。A. i/2.0B . i/2+1C , 2i+1 D . i/2 向下取整22 .設(shè)一棵哈夫曼樹共有n個(gè)非葉結(jié)點(diǎn)，則該樹有（）個(gè)結(jié)點(diǎn)。A. 2nB. 2n+2 C . 2n-1 D . 2n+123 .設(shè)一棵采用鏈?zhǔn)酱鎯?chǔ)的二叉樹，除葉結(jié)點(diǎn)外每個(gè)結(jié)點(diǎn)度數(shù)都為2,該樹結(jié)點(diǎn)中共有 2n個(gè)指針域?yàn)榭铡t該樹有（）個(gè)葉結(jié)點(diǎn)。A. 2nB. 2n+1 C . 2n+2 D . n24 . 一棵結(jié)點(diǎn)數(shù)31<n<40的完全二叉樹，最后一層有