02142數據結構導論復習題

1、數據結構導論模擬試題一、考試題型及分值分布：1、單項選擇題(本大題共15小題，每小題2分，共30分)2、填空題(本大題共13小題，每小題2分，共26分)3、應用題(本大題共5小題，每小題6分，共30分)4、算法設計題(本大題共2小題，每小題7分，共14分)二、單項選擇題和填空題樣題參考(一)單項選擇題1 .在二維數組中，每個數組元素同時處于()個向量中。A.0B.1C.2D.n2 .已知單鏈表A長度為m,單鏈表B長度為n,它們分別由表頭指針所指向，若將B整體連接到A的末尾，其時間復雜度應為()。A.O(1)B.O(m)C.O(n)D.O(m+n)3 .假定一個鏈式隊列的隊頭和隊尾指針分別為fr

2、ont和rear,則判斷隊空的條件為()。A.front=rearB.front!=NULLC.rear!=NULLD.front=NULL4 .若讓元素1,2,3依次進棧，則出棧次序不可能出現()種情況。A.3,2,1B.2,1,3C.3,1,2D.1,3,25 .圖的廣度優(yōu)先搜索類似于樹的()遍歷。A.先根B.中根C.后根D.層次6 .下面程序段的時間復雜度為()。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 .設有兩個串t和p,求p在t中首次出現的位置的運算叫做()。A.

3、求子串B.模式匹配C.串替換D.串連接8利用雙向鏈表作線性表的存儲結構的優(yōu)點是()。A.便于單向進行插入和刪除的操作B.便于雙向進行插入和刪除的操作C.節(jié)省空間D.便于銷毀結構釋放空間9 .設鏈式棧中結點的結構為(data,link),且top是指向棧頂的指針。若想在鏈式棧的棧頂插入一個由指針s所指的結點，則應執(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個結點的完全二叉樹的高度

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

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

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

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

8、H,C,Y,P,A,M,S,R,D,F,X)進行快速排序，則第一次劃分的結果是：()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 .下面是三個關于有向圖運算的敘述：()（1）求有向圖結點的拓撲序列，其結果必定是唯一的（2）求兩個指向結點間的最短路徑，其結果必定是唯一的（3）求AOE網的關鍵路徑，其結果必定是唯一的其中哪個（些）是正確的？A.只有（1）B.（1）和（2）C,都正確D.都不正確30 .若進棧序列為a,

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

10、的鄰接矩陣表示,A.將鄰接矩陣的第i行刪除C.將鄰接矩陣的第i列刪除34.有一個含頭結點的雙向循環(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）中，用折半法查找關鍵碼值11,所需的關鍵碼比較次數為：（）A.2B.3C.4D.536 .以下哪一個不是隊列的基本運算？（）A.從隊尾插入一個新元素B.從隊列中刪除第i個元素C.判斷一個隊列是否為空D.讀取隊頭元素的值37 .對包含n個

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

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

13、行比較，然后將其放在已排序序列的合適位置，該排序方法稱為排序法。A.插入B.選擇C.冒泡D.都不是47 .一個棧的入棧序列是a,b,c,d,e,則棧的不可能的輸出序列是。A.edcbaB.decbaC.dceabD.abcde48 .n個節(jié)點的完全二叉樹，編號為i的節(jié)點是葉子結點的條件是。A.i<nB.2*i<=nC.2*i+1>nD.2*i>n49 .向一個有128個元素的順序表中插入一個新元素并保持原來順序不變，平均要移動個元素。A.64.5B.64C.63D.6550 .在一個單鏈表HL中，若要在指針q所指結點的后面插入一個由指針p所指向的結點，則執(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 .對一個滿二叉樹，m個樹葉，n個結點，深度為h,則有。A.n=h+mB.h+m=2nC.m=h-1D.n=2h-152 .在所有排序方法中，關鍵字比較的次數與記錄的初始排列次序無關的是A.選擇排序B.冒泡排序C.插入排序D.希爾排序53 .用鏈式方式存儲的隊列，在進行插入運算時，。A.僅修改頭指針B.僅修改尾指針C.頭、尾指

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

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

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

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

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

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

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

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

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

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

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

26、1、 下列算法實現在順序散列表中查找值為x的關鍵字，請在下劃線處填上正確的語句。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、 下列算法實現在二叉排序樹上查找關鍵值k,請在下劃線處填上正確的語句。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、 設有n個無序的記錄關鍵字，則直接插入排序的時間復雜度為，快速排序的平均時間復雜度為。54、 設指針變量p指向雙向循環(huán)鏈表中的結點X,則刪除結點X需要執(zhí)行的語句序列為(設結點中的兩個指針域分別為llink和rlink)。根據初始關鍵字序列(19,22,01,38,10)建立的二叉排序樹的高度為3。55、 深度為k的完全二叉樹中最少有2k-1個結點。56、 設初始記錄關鍵字序列為(K1,K2,Kn),則用篩選法思想建堆必須從第_n/2_個元素開始進行篩選。59、設哈夫曼樹中共有99個結點，則該樹中有個葉子結點；若采用二叉鏈表作為存儲結構，則該樹中有個空指針域。60、設有一個順序循環(huán)隊列中有M個存儲單