02142數(shù)據(jù)結(jié)構(gòu)導(dǎo)論復(fù)習(xí)題

1、數(shù)據(jù)結(jié)構(gòu)導(dǎo)論模擬試題一、考試題型及分值分布：1、單項(xiàng)選擇題(本大題共15小題，每小題2分，共30分)2、填空題(本大題共13小題，每小題2分，共26分)3、應(yīng)用題(本大題共5小題，每小題6分，共30分)4、算法設(shè)計(jì)題(本大題共2小題，每小題7分，共14分)二、單項(xiàng)選擇題和填空題樣題參考(一)單項(xiàng)選擇題1 .在二維數(shù)組中，每個(gè)數(shù)組元素同時(shí)處于()個(gè)向量中。A.0B.1C.2D.n2 .已知單鏈表A長(zhǎng)度為m,單鏈表B長(zhǎng)度為n,它們分別由表頭指針?biāo)赶?，若將B整體連接到A的末尾，其時(shí)間復(fù)雜度應(yīng)為()。A.O(1)B.O(m)C.O(n)D.O(m+n)3 .假定一個(gè)鏈?zhǔn)疥?duì)列的隊(duì)頭和隊(duì)尾指針?lè)謩e為fr

2、ont和rear,則判斷隊(duì)空的條件為()。A.front=rearB.front!=NULLC.rear!=NULLD.front=NULL4 .若讓元素1,2,3依次進(jìn)棧，則出棧次序不可能出現(xiàn)()種情況。A.3,2,1B.2,1,3C.3,1,2D.1,3,25 .圖的廣度優(yōu)先搜索類(lèi)似于樹(shù)的()遍歷。A.先根B.中根C.后根D.層次6 .下面程序段的時(shí)間復(fù)雜度為()。for(inti=0;i<m;i+)for(intj=0;j<n;j+)aij=i*j;A.O(m2)B.O(n2)C.O(m*n)D.O(m+n)7 .設(shè)有兩個(gè)串t和p,求p在t中首次出現(xiàn)的位置的運(yùn)算叫做()。A.

3、求子串B.模式匹配C.串替換D.串連接8利用雙向鏈表作線性表的存儲(chǔ)結(jié)構(gòu)的優(yōu)點(diǎn)是()。A.便于單向進(jìn)行插入和刪除的操作B.便于雙向進(jìn)行插入和刪除的操作C.節(jié)省空間D.便于銷(xiāo)毀結(jié)構(gòu)釋放空間9 .設(shè)鏈?zhǔn)綏Ｖ薪Y(jié)點(diǎn)的結(jié)構(gòu)為(data,link),且top是指向棧頂?shù)闹羔槨Ｈ粝朐阪準(zhǔn)綏５臈ｍ敳迦胍粋€(gè)由指針s所指的結(jié)點(diǎn)，則應(yīng)執(zhí)行()操作。A.top->link=s;B.s->link=top->link;top->link=s;C.s->link=top;top=s;D.s->link=top;top=top->link;10 .一棵具有35個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的高度

4、為()。假定空樹(shù)的高度為-1。A.5B.6C.7D.811 .一個(gè)有n個(gè)頂點(diǎn)和n條邊的無(wú)向圖一定是()的。A連通B.不連通C.無(wú)回路D.有回路12 .在一個(gè)長(zhǎng)度為n的順序表的任一位置插入一個(gè)新元素的時(shí)間復(fù)雜度為()。A.O(n)B.O(n/2)C.O(1)D.O(n2)13 .已知廣義表為A(a,b,c),(d,e,f)，從A中取出原子e的運(yùn)算是()。Head(Tail(A)ATail(Head(A)CHead(Tail(Head(Tail(A)D.Head(Head(Tail(Tail(A)14 .在一棵樹(shù)的靜態(tài)雙親表示中，每個(gè)存儲(chǔ)結(jié)點(diǎn)包含()個(gè)域。A1B2C3D415 .有向圖中的一個(gè)頂點(diǎn)

5、的度數(shù)等于該頂點(diǎn)的()。A入度B.出度C.入度與出度之和D.(入度+出度)/216 .與鄰接矩陣相比，鄰接表更適合于存儲(chǔ)()。A無(wú)向圖B.連通圖C.稀疏圖D.稠密圖17 .較快的數(shù)據(jù)搜索方法是()搜索方法。A.順序B.折半C.單鏈D.散列18 .在閉散列表中，散列到同一個(gè)地址而引起的“堆積”問(wèn)題是由于()引起的。A.同義詞之間發(fā)生沖突B.非同義詞之間發(fā)生沖突C.同義詞之間或非同義詞之間發(fā)生沖突D.散列表“溢出”19 .根據(jù)n個(gè)元素建立一個(gè)有序單鏈表的時(shí)間復(fù)雜度為()。A.O(1)B.O(n)C.O(n2)D.O(nlog2n)20 .假定一個(gè)順序存儲(chǔ)的循環(huán)隊(duì)列的隊(duì)頭和隊(duì)尾指針?lè)謩e為front和

6、rear,則判斷隊(duì)空的條件為()。A.front+1=rearB.rear+1=frontC.front=0D.front=rear21 .假定一棵二叉樹(shù)的第i層上有3i個(gè)結(jié)點(diǎn)，則第i+1層上最多有()個(gè)結(jié)點(diǎn)。A.3iB.6iC.9iD.2i22 .對(duì)于具有e條邊的無(wú)向圖，它的鄰接表中共有()個(gè)邊結(jié)點(diǎn)。Ae-1B.e+1C.2eD.3e23 .圖的深度優(yōu)先搜索遍歷類(lèi)似于樹(shù)的()次序遍歷。A.先根B.中根C.后根D.層次24 .棧S最多能容納4個(gè)元素。現(xiàn)有6個(gè)元素按A、BC、DE、F的順序進(jìn)棧，問(wèn)下列哪一個(gè)序列是可能的出棧序列?()A. E、DCBA、FB.B、CE、F、A、DC.CBEDAFD

7、.ADFEBC25 .將一棵有100個(gè)結(jié)點(diǎn)的完全二叉樹(shù)從根這一層開(kāi)始，每一層從左到右依次對(duì)結(jié)點(diǎn)進(jìn)行編號(hào)，根結(jié)點(diǎn)編號(hào)為1,則編號(hào)為49的結(jié)點(diǎn)的左孩子的編號(hào)為：()A.98B.99C.50D.4826 .對(duì)下列關(guān)鍵字序列用快速排序法進(jìn)行排序時(shí)，速度最快的情形是：()A. 21、255、17、9、23、30B. 25、23、30、17、21、5、9B. 219173025235D.59172123253027 .對(duì)于只在表的首、尾進(jìn)行插入操作的線性表，宜采用的存儲(chǔ)結(jié)構(gòu)為()A.順序表B.用頭指針表示的單循環(huán)鏈表C.用尾指針表示的單循環(huán)鏈表D.單鏈表28 .假設(shè)以第一個(gè)元素為分界元素，對(duì)字符序列(Q,

8、H,C,Y,P,A,M,S,R,D,F,X)進(jìn)行快速排序，則第一次劃分的結(jié)果是：()A. (A,C,D,F,H,M,P,Q,R,S,X,Y)B. (A,F,H,C,D,P,M,Q,R,S,Y,X)C. (F,H,C,D,P,A,M,Q,R,S,Y,X)D. (P,A,M,F,H,C,D,Q,S,Y,R,X)29 .下面是三個(gè)關(guān)于有向圖運(yùn)算的敘述：()（1）求有向圖結(jié)點(diǎn)的拓?fù)湫蛄?，其結(jié)果必定是唯一的（2）求兩個(gè)指向結(jié)點(diǎn)間的最短路徑，其結(jié)果必定是唯一的（3）求AOE網(wǎng)的關(guān)鍵路徑，其結(jié)果必定是唯一的其中哪個(gè)（些）是正確的？A.只有（1）B.（1）和（2）C,都正確D.都不正確30 .若進(jìn)棧序列為a,

9、b,c,則通過(guò)入出棧操作可能得到的a,b,c的不同排列個(gè)數(shù)為（）A.4B.5C.6D.731 .以下關(guān)于廣義表的敘述中，正確的是：（）A.廣義表是由0個(gè)或多個(gè)單元素或子表構(gòu)成的有限序列B.廣義表至少有一個(gè)元素是子表C.廣義表不能遞歸定義D）廣義表不能為空表32 .排序時(shí)掃描待排序記錄序列，順次比較相鄰的兩個(gè)元素的大小，逆序時(shí)就交換位置。這是哪種排序方法的基本思想？（）C. 快速排序D.冒泡排序要?jiǎng)h除所有從第i個(gè)結(jié)點(diǎn)發(fā)出的邊，應(yīng)該：（）B.將鄰接矩陣的第i行元素全部置為0D. 將鄰接矩陣的第i列元素全部置為0頭指針為head,則其為空的條件是：（）A.堆排序B.直接插入排序33 .已知一個(gè)有向圖

10、的鄰接矩陣表示,A.將鄰接矩陣的第i行刪除C.將鄰接矩陣的第i列刪除34.有一個(gè)含頭結(jié)點(diǎn)的雙向循環(huán)鏈表,A.head->priro=NULLB.head->next=NULLC.head->next=headD.head->next->priro=NULL35 .在順序表（3,6,8,10,12,15,16,18,21,25,30）中，用折半法查找關(guān)鍵碼值11,所需的關(guān)鍵碼比較次數(shù)為：（）A.2B.3C.4D.536 .以下哪一個(gè)不是隊(duì)列的基本運(yùn)算？（）A.從隊(duì)尾插入一個(gè)新元素B.從隊(duì)列中刪除第i個(gè)元素C.判斷一個(gè)隊(duì)列是否為空D.讀取隊(duì)頭元素的值37 .對(duì)包含n個(gè)

11、元素的哈希表進(jìn)行查找，平均查找長(zhǎng)度為：（）A.O（log2n）B.O（n）C.O（nlog2n）D不直接依賴(lài)于n38 .將一棵有100個(gè)結(jié)點(diǎn)的完全二叉樹(shù)從根這一層開(kāi)始，每一層從左到右依次對(duì)結(jié)點(diǎn)進(jìn)行編號(hào)，根結(jié)點(diǎn)編號(hào)為1,則編號(hào)最大的非葉結(jié)點(diǎn)的編號(hào)為：（）A.48B.49C.50D.5139 .某二叉樹(shù)結(jié)點(diǎn)的中序序列為A、B、C、DE、F、G后序序列為B、D、CA、FGE,則其左子樹(shù)中結(jié)點(diǎn)數(shù)目為：（）A.3B.2C.4D.540 .下面是順序存儲(chǔ)結(jié)構(gòu)的優(yōu)點(diǎn)。A.存儲(chǔ)密度大B.插入運(yùn)算方便C.查找方便D.適合各種邏輯結(jié)構(gòu)的存儲(chǔ)表示41 .下面關(guān)于串的敘述中，是不正確的。A.串是字符的有限序列B.空串

12、是由空格構(gòu)成的串C.模式匹配是串的一種重要運(yùn)算D.串既可以采用順序存儲(chǔ)，也可以采用鏈?zhǔn)酱鎯?chǔ)42 .的鄰接矩陣是對(duì)稱(chēng)矩陣。A.有向圖B.無(wú)向圖C.AOV網(wǎng)D.AOE網(wǎng)43 .用鏈?zhǔn)椒绞酱鎯?chǔ)的隊(duì)列，在進(jìn)行刪除運(yùn)算時(shí)，。僅修改尾指針頭、尾指針可能都要修改A.僅修改頭指針B.C.頭、尾指針都要修改D.44 .二叉樹(shù)的先序遍歷和中序遍歷如下，則該二叉樹(shù)右子樹(shù)的樹(shù)根是.先序序列：EFHIGJK中序序列：HFIEJKGA.EB.FC.GD.H45 .下面方法可以判斷出一個(gè)有向圖中是否有環(huán)。A.深度優(yōu)先遍歷B.拓樸排序C.求最短路徑D.求關(guān)鍵路徑46 .從未排序序列中依次取出一個(gè)元素與已排序序列中的元素依次進(jìn)

13、行比較，然后將其放在已排序序列的合適位置，該排序方法稱(chēng)為排序法。A.插入B.選擇C.冒泡D.都不是47 .一個(gè)棧的入棧序列是a,b,c,d,e,則棧的不可能的輸出序列是。A.edcbaB.decbaC.dceabD.abcde48 .n個(gè)節(jié)點(diǎn)的完全二叉樹(shù)，編號(hào)為i的節(jié)點(diǎn)是葉子結(jié)點(diǎn)的條件是。A.i<nB.2*i<=nC.2*i+1>nD.2*i>n49 .向一個(gè)有128個(gè)元素的順序表中插入一個(gè)新元素并保持原來(lái)順序不變，平均要移動(dòng)個(gè)元素。A.64.5B.64C.63D.6550 .在一個(gè)單鏈表HL中，若要在指針q所指結(jié)點(diǎn)的后面插入一個(gè)由指針p所指向的結(jié)點(diǎn)，則執(zhí)行。A.q-&

14、gt;next=p->next;p->next=q;B.p->next=q->next;q=p;C.p->next=p->next;q->next=q;D.p->next=q->next;q->nxet=p;51 .對(duì)一個(gè)滿(mǎn)二叉樹(shù)，m個(gè)樹(shù)葉，n個(gè)結(jié)點(diǎn)，深度為h,則有。A.n=h+mB.h+m=2nC.m=h-1D.n=2h-152 .在所有排序方法中，關(guān)鍵字比較的次數(shù)與記錄的初始排列次序無(wú)關(guān)的是A.選擇排序B.冒泡排序C.插入排序D.希爾排序53 .用鏈?zhǔn)椒绞酱鎯?chǔ)的隊(duì)列，在進(jìn)行插入運(yùn)算時(shí)，。A.僅修改頭指針B.僅修改尾指針C.頭、尾指

15、針都要修改D.頭、尾指針可能都要修改54 .在一個(gè)長(zhǎng)度為n的順序存儲(chǔ)的線性表中，向第i個(gè)元素（1WiWn+1）插入一個(gè)新元素時(shí)，需要從后向前依次后移個(gè)元素。A.n-iB.n-i-1C.n-i+1D.i55 .一個(gè)棧的入棧序列是12345,則棧的不可能的輸出序列是。A.23415B.54132C.23145D.1543256 .5個(gè)頂點(diǎn)的有向圖最多有條弧。A.5B.20C.4D.2557 .假定一個(gè)鏈隊(duì)的隊(duì)首和隊(duì)尾指針?lè)謩e為front和rear,則判斷隊(duì)空的條件為。A.front=rearB.front!=NULLC.rear!=NULLD.front=NULL58 .若某線性表中最常用的操作是

16、提取第i個(gè)元素及找第i個(gè)元素的前驅(qū)元素，則采用（）存儲(chǔ)方式最省時(shí)間。A.單鏈表B.雙鏈表C.單向循環(huán)鏈表D.順序表59 .將含有100個(gè)結(jié)點(diǎn)的完全二叉樹(shù)從根開(kāi)始自上向下，每層從左到右依次編號(hào)，且設(shè)根結(jié)點(diǎn)的編號(hào)為1,則編號(hào)69的結(jié)點(diǎn)的雙親的編號(hào)為（）。A.34B.35C.33D.無(wú)法確定60 .單循環(huán)鏈表的主要優(yōu)點(diǎn)是（）。A.不再需要頭指針了B.已知某結(jié)點(diǎn)的位置后，很容易找到其前驅(qū)C.在進(jìn)行插入、刪除運(yùn)算時(shí)，能更好地保證鏈表不斷開(kāi)D.從表中任一結(jié)點(diǎn)出發(fā)都能掃描到整個(gè)鏈表61 .一個(gè)棧的入棧順序是1、2、3、4、5,則此棧不可能的輸出順序?yàn)椋ǎ?。A.5、4、3、2、1B.4、5、3、2、1C.4、

17、3、5、1、2D.1、2、3、4、562 .串是一種特殊的線性表，其特殊性表現(xiàn)在（）。A.可以順序存儲(chǔ)B.數(shù)據(jù)元素是一個(gè)字符C可以鏈?zhǔn)酱鎯?chǔ)D.數(shù)據(jù)元素是多個(gè)字符63 .n個(gè)頂點(diǎn)的無(wú)向圖中最多有（）條邊。A.n（n-1）/2B.n（n-1）C.n（n+1）D.n（n+1）/264 .6個(gè)頂點(diǎn)的無(wú)向圖中，至少有（）條邊才能保證是一個(gè)連通圖。A.5B.6C.7D.865 .若某線性表中最常用的操作是刪除第1個(gè)元素，則不宜采用（）存儲(chǔ)方式。A.單鏈表B.雙鏈表C.單向循環(huán)鏈表D.順序表66 .在一棵完全二叉樹(shù)的順序存儲(chǔ)方式中，若編號(hào)i的結(jié)點(diǎn)有右孩子，則其右孩子的編號(hào)為（）。A.2iB.2i-1C.2i

18、+1D.i/267 .按照二叉樹(shù)的定義，具有3個(gè)結(jié)點(diǎn)的二叉樹(shù)有（）種不同形態(tài)。A.3B.4C.5D.668 .在長(zhǎng)為n的順序表中，刪除第i個(gè)元素（1wiwn+1）需要向前移動(dòng)（）個(gè)元素。A.n-iB.n-i+1C.n-i-1D.i69 .一個(gè)隊(duì)的入隊(duì)順序是1、2、3、4、5,則此隊(duì)的出隊(duì)順序?yàn)椋ǎ?。A.5、4、3、2、1B.4、5、3、2、1C.4、3、5、1、2D.1、2、3、4、570 .棧是一種特殊的線性表，其特殊性表現(xiàn)在（）。A.可以順序存儲(chǔ)B.只能從端點(diǎn)進(jìn)行插入和刪除C.可以鏈?zhǔn)酱鎯?chǔ)D.可以在任何位置進(jìn)行插入和刪除71 .一棵二叉樹(shù)中，第k層上最多有（）個(gè)結(jié)點(diǎn)。A.2kB.2k-1C

19、.2kD.2k-172 .一棵有18個(gè)結(jié)點(diǎn)的二叉樹(shù)，其高度最小為（）層。A.4B.5C.6D.1873 .有向圖中，所有頂點(diǎn)入度和是所有頂點(diǎn)出度和的（）倍。A.0.5B.1C.2D.4（二）填空題1 .數(shù)據(jù)元素之間存在的相互關(guān)系稱(chēng)為。2 .數(shù)據(jù)結(jié)構(gòu)從邏輯上分為結(jié)構(gòu)和結(jié)構(gòu)。3 .線性表的順序存儲(chǔ)結(jié)構(gòu)稱(chēng)為。4 .所有插入在表的一端進(jìn)行，而所有刪除在表的另一端進(jìn)行的線性表稱(chēng)為5 .深度為h的二叉樹(shù)，最少有個(gè)結(jié)點(diǎn)。6 .折半查找要求待查表為表。7 .n個(gè)記錄按其關(guān)鍵字大小遞增或遞減的次序排列起來(lái)的過(guò)程稱(chēng)為8 .存儲(chǔ)數(shù)據(jù)時(shí)，不僅要存儲(chǔ)數(shù)據(jù)元素的,還要存儲(chǔ)元素之間的相互。9 .將一棵有100個(gè)結(jié)點(diǎn)的完全二

20、叉樹(shù)按層編號(hào)，則編號(hào)為49的結(jié)點(diǎn)X,其雙親PARENRX)的編號(hào)為。10、一個(gè)字符串相等的充要條件是和。11、在有向圖的鄰接表和逆鄰接表表示中，每個(gè)頂點(diǎn)的邊鏈表中分別鏈接著該頂點(diǎn)的所有和結(jié)點(diǎn)。11、在一個(gè)長(zhǎng)度為n的順序表中向第i個(gè)元素(0<iwn+1)之前插入一個(gè)新元素時(shí)，需要向后移動(dòng)個(gè)元素。12、是只允許在表的一端進(jìn)行插入，而在另一端進(jìn)行刪除的線性表。13、設(shè)主串T="abxxyxyxxbaa:模式串P="xyxx”則第次匹配成功。14、在一棵二叉樹(shù)中，第5層上的結(jié)點(diǎn)數(shù)最多為。(根的層次為1)15、假設(shè)一個(gè)9階的上三角矩陣A按列優(yōu)先順序壓縮存儲(chǔ)在一維數(shù)組中，其中B0

21、存儲(chǔ)矩陣中第1個(gè)元素a1,1,則B31中存放的元素是。16、有n個(gè)結(jié)點(diǎn)的二叉鏈表中，其中空的指針域?yàn)閚+1,指向孩子的指針個(gè)數(shù)為。17、二叉樹(shù)后序遍歷的順序是ABCDE則該二叉樹(shù)的根結(jié)點(diǎn)是。18、對(duì)于一個(gè)具有n個(gè)頂點(diǎn)和e條邊的無(wú)向圖，若采用鄰接表表示，則整個(gè)鄰接表中的結(jié)點(diǎn)總數(shù)是。19、在單鏈表上難以實(shí)現(xiàn)的排序方法有和。20、查找法的平均查找長(zhǎng)度與元素個(gè)數(shù)n無(wú)關(guān)。21、在有n個(gè)元素的順序表的任意位置插入一個(gè)元素所需移動(dòng)結(jié)點(diǎn)的平均次數(shù)為22、是插入和刪除元素都在表的同一端進(jìn)行的線性表。23、廣義表L=(a,b,c,L)，則其長(zhǎng)度為。24、在樹(shù)中，除跟結(jié)點(diǎn)外，其他結(jié)點(diǎn)都有且只有一個(gè)結(jié)點(diǎn)。26、在串s

22、="structure"中，以t為首字符的子串有個(gè)。27、廣度優(yōu)先搜索遍歷類(lèi)似于樹(shù)的按遍歷的過(guò)程。28、已知一棵完全二叉樹(shù)中共有768個(gè)結(jié)點(diǎn)為，則該樹(shù)中共有個(gè)葉子結(jié)點(diǎn)。29、在有序表(12,24,36,48,60,72,84)中二分查找關(guān)鍵字72時(shí)所需進(jìn)行的關(guān)鍵字比較次數(shù)為。30、兩個(gè)長(zhǎng)度分別m和n(m>n)的排好序的表歸并成一個(gè)排好序的表，至少要進(jìn)行次鍵值比較。通常從四個(gè)方面評(píng)價(jià)算法的質(zhì)量：、和。31、 一個(gè)算法的時(shí)間復(fù)雜度為(n3+n210g2n+14n)/n2,其數(shù)量級(jí)表示為。32、 若用鏈表存儲(chǔ)一棵二叉樹(shù)時(shí)，每個(gè)結(jié)點(diǎn)除數(shù)據(jù)域外，還有指向左孩子和右孩子的兩個(gè)指針

23、。在這種存儲(chǔ)結(jié)構(gòu)中，n個(gè)結(jié)點(diǎn)的二叉樹(shù)共有個(gè)指針域，其中有個(gè)指針域是存放了地址，有個(gè)指針是空指針。33、 對(duì)于一個(gè)具有n個(gè)頂點(diǎn)和e條邊的有向圖和無(wú)向圖，在其對(duì)應(yīng)的鄰接表中，所含邊結(jié)點(diǎn)分別有個(gè)和個(gè)。34、 在一個(gè)具有n個(gè)頂點(diǎn)的無(wú)向完全圖中，包含有條邊，在一個(gè)具有n個(gè)頂點(diǎn)的有向完全圖中，包含有條邊。35、 36.在快速排序、堆排序、歸并排序中，排序是穩(wěn)定的。36、 37.中序遍歷二叉排序樹(shù)所得到的序列是序列。38 .快速排序的最壞時(shí)間復(fù)雜度為,平均時(shí)間復(fù)雜度為。39 .設(shè)一組初始記錄關(guān)鍵字序列為(55,63,44,38,75,80,31,56),則利用篩選法建立的初始堆為。40 .數(shù)據(jù)的物理結(jié)構(gòu)主要

24、包括和兩種情況。41 .設(shè)一棵完全二叉樹(shù)中有500個(gè)結(jié)點(diǎn)，則該二叉樹(shù)的深度為;若用二叉鏈表作為該完全二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)，則共有個(gè)空指針域。42、設(shè)輸入序列為1、2、3,則經(jīng)過(guò)棧的作用后可以得到種不同的輸出序列。43、設(shè)有向圖G用鄰接矩陣Ann作為存儲(chǔ)結(jié)構(gòu)，則該鄰接矩陣中第i行上所有元素之和等于頂點(diǎn)i的，第i列上所有元素之和等于頂點(diǎn)i的。設(shè)哈夫曼樹(shù)中共有n個(gè)結(jié)點(diǎn),則該哈夫曼樹(shù)中有個(gè)度數(shù)為1的結(jié)點(diǎn)。44、 設(shè)有向圖G中有n個(gè)頂點(diǎn)e條有向邊，所有的頂點(diǎn)入度數(shù)之和為d,則e和d的關(guān)系為45、 遍歷二叉排序樹(shù)中的結(jié)點(diǎn)可以得到一個(gè)遞增的關(guān)鍵字序列(填先序、中序或后序)。46、 設(shè)查找表中有100個(gè)元素，如果

25、用二分法查找方法查找數(shù)據(jù)元素X,則最多需要比較次就可以斷定數(shù)據(jù)元素X是否在查找表中。47、 不論是順序存儲(chǔ)結(jié)構(gòu)的棧還是鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的棧，其入棧和出棧操作的時(shí)間復(fù)雜度均為48、 設(shè)有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)，如果按照從自上到下、從左到右從1開(kāi)始順序編號(hào)，則第i個(gè)結(jié)點(diǎn)的雙親結(jié)點(diǎn)編號(hào)為,右孩子結(jié)點(diǎn)的編號(hào)為。49、 設(shè)一組初始記錄關(guān)鍵字為(72,73,71,23,94,16,5),則以記錄關(guān)鍵字72為基準(zhǔn)的一趟快速排序結(jié)果為。50、 設(shè)有向圖G中有向邊的集合E=<1,2>,<2,3>,<1,4>,<4,2>,<4,3>,則該圖的一種拓?fù)湫蛄袨椤?

26、1、 下列算法實(shí)現(xiàn)在順序散列表中查找值為x的關(guān)鍵字，請(qǐng)?jiān)谙聞澗€處填上正確的語(yǔ)句。structrecordintkey;intothers;inthashsqsearch(structrecordhashtable,intk)inti,j;j=i=k%p;while(hashtablej.key!=k&&hashtablej.flag!=0)j=()%m;if(i=j)return(-1);if()return(j);elsereturn(-1);j+1,hashtablej.key=k52、 下列算法實(shí)現(xiàn)在二叉排序樹(shù)上查找關(guān)鍵值k,請(qǐng)?jiān)谙聞澗€處填上正確的語(yǔ)句。typedefst

27、ructnodeintkey;structnode*lchild;structnode*rchild;bitree;bitree*bstsearch(bitree*t,intk)if(t=0)return(0);elsewhile(t!=0)if(t->key=k);elseif(t->key>k)t=t->lchild;else;return(t),t=t->rchild53、 設(shè)有n個(gè)無(wú)序的記錄關(guān)鍵字，則直接插入排序的時(shí)間復(fù)雜度為，快速排序的平均時(shí)間復(fù)雜度為。54、 設(shè)指針變量p指向雙向循環(huán)鏈表中的結(jié)點(diǎn)X,則刪除結(jié)點(diǎn)X需要執(zhí)行的語(yǔ)句序列為(設(shè)結(jié)點(diǎn)中的兩個(gè)指針域分別為llink和rlink)。根據(jù)初始關(guān)鍵字序列(19,22,01,38,10)建立的二叉排序樹(shù)的高度為3。55、 深度為k的完全二叉樹(shù)中最少有2k-1個(gè)結(jié)點(diǎn)。56、 設(shè)初始記錄關(guān)鍵字序列為(K1,K2,Kn),則用篩選法思想建堆必須從第_n/2_個(gè)元素開(kāi)始進(jìn)行篩選。59、設(shè)哈夫曼樹(shù)中共有99個(gè)結(jié)點(diǎn)，則該樹(shù)中有個(gè)葉子結(jié)點(diǎn)；若采用二叉鏈表作為存儲(chǔ)結(jié)構(gòu)，則該樹(shù)中有個(gè)空指針域。60、設(shè)有一個(gè)順序循環(huán)隊(duì)列中有M個(gè)存儲(chǔ)單