數(shù)據(jù)結(jié)構(gòu)常見題型整合

數(shù)據(jù)結(jié)構(gòu)常見題型整合數(shù)據(jù)結(jié)構(gòu)常見題型整合數(shù)據(jù)結(jié)構(gòu)常見題型整合數(shù)據(jù)結(jié)構(gòu)常見題型整合編制僅供參考審核批準生效日期地址：電話：傳真:郵編:數(shù)據(jù)結(jié)構(gòu)常見題型整合1、設(shè)棧的輸入序列是1，2，3，4,則（）不可能是其出棧序列。A.1，2，4，3，B.2，1，3，4，C.1，4，3，2，D.4，3，1，2，3、順序存儲的棧和隊列中已經(jīng)各有N個結(jié)點，要刪除一個結(jié)點分別需要移動數(shù)據(jù)（）次和（）次。A.N/2,NB.N,N/2C.0,ND.N,0設(shè)有三個元素X，Y，Z順序進棧（進的過程中允許出棧），下列得不到的出棧排列是()。A．XYZB.YZXC.ZXYD.ZYX一個遞歸算法必須包括（）。A.遞歸部分B.終止條件和遞歸部分C.迭代部分D.終止條件和迭代部分6、如下四個選項中，那個選項是能夠正確判斷循環(huán)隊列是否排滿元素的操作（其中MAXQSIZE表示隊列的容量）（）：A．if==… B．if==+MAXQSIZE))C．if==+1)%MAXQSIZE)D．if==+1)%MAXQSIZE)假設(shè)以數(shù)組A[m]存放循環(huán)隊列的元素，其頭尾指針分別為front和rear，則當前隊列中的元素個數(shù)為（）。A．(rear-front+m)%mB．rear-front+1C．(front-rear+m)%mD．(rear-front)%m若用一個大小為6的數(shù)組來實現(xiàn)循環(huán)隊列，且當前rear和front的值分別為0和3，當從隊列中刪除一個元素，再加入兩個元素后，rear和front的值分別為多少()A.1和5B.2和4C.4和2D.5和19、利用棧進行十進制數(shù)1348轉(zhuǎn)換成八進制數(shù)，則入棧的數(shù)依次是（）。A.1,3,4,8B.8,4,3,1C.2,5,0,4D.4,0,5,2最大容量為n的循環(huán)隊列，隊尾指針是rear，隊頭是front，則隊空的條件是（）。A.(rear+1)MODn=frontB.rear=frontC．rear+1=frontD.(rear-l)MODn=front棧和隊列的共同點是（）。A.都是先進先出B.都是先進后出C.只允許在端點處插入和刪除元素D.沒有共同點棧是___操作受限（或限定僅在表尾進行插入和刪除操作）的線性表，其運算遵循___后進先出____的原則。，其特點是__先進先出__。用S表示入棧操作，X表示出棧操作，若元素入棧的順序為1234，為了得到1342出棧順序，相應(yīng)的S和X的操作串為___S×SS×S××__。表達式求值是___棧____應(yīng)用的一個典型例子。5、棧和隊列在本質(zhì)上都是同一種基本數(shù)據(jù)結(jié)構(gòu)的特例，這種基本的數(shù)據(jù)結(jié)構(gòu)就是線性表。在作進棧運算時，應(yīng)先判別棧是否.滿，在作退棧運算時應(yīng)先判別棧是否空。當棧中元素為n個，作進棧運算時發(fā)生上溢，則說明該棧的最大容量為n。12、在二叉樹的第I層(I≥1)上最多含有結(jié)點數(shù)為（）A.2IB.2I-1-1C.2I-1D.2I-113、深度為6的二叉樹最多有()個結(jié)點A．6414、一棵樹高為K的完全二叉樹至少有()個結(jié)點–1–1k15、有關(guān)二叉樹下列說法正確的是（）A.二叉樹的度為2B.一棵二叉樹的度可以小于2C.二叉樹中至少有一個結(jié)點的度為2D.二叉樹中任何一個結(jié)點的度都為216、n個結(jié)點的線索二叉樹上含有的線索數(shù)為（）A.2nB.n－lC.n＋lD.n17、線性表和樹的結(jié)構(gòu)區(qū)別在于（）A．前驅(qū)數(shù)量不同，后繼數(shù)量相同 B．前驅(qū)數(shù)量相同，后繼數(shù)量不同C．前驅(qū)和后繼的數(shù)量都相同 D．前驅(qū)和后繼的數(shù)量都不同18、已知一算術(shù)表達式的中綴形式為A+B*C-D/E，后綴形式為ABC*+DE/-，則其前綴形式為()A．-A+B*C/DEB.-A+B*CD/EC．-+*ABC/DED.-+A*BC/DE19、設(shè)有一表示算術(shù)表達式的二叉樹（見下圖），EEFDGAB/++*-C*它所表示的算術(shù)表達式是（）A.A*B+C/(D*E)+(F-G)B.(A*B+C)/(D*E)+(F-G)C.(A*B+C)/(D*E+（F-G）)D.A*B+C/D*E+F-G20、一棵具有n個結(jié)點的完全二叉樹的樹高度（深度）(符號表示取不大于x的最大整數(shù))是（）A.B.C.D.21、利用二叉鏈表存儲樹，則根結(jié)點的右指針是（）。A．指向最左孩子B．指向最右孩子C．空D．非空22、已知一棵二叉樹的前序遍歷結(jié)果為ABCDEF，中序遍歷結(jié)果為CBAEDF，則后序遍歷的結(jié)果為（）。A．CBEFDAB．FEDCBAC．CBEDFAD．不定23、若前序遍歷二叉樹的結(jié)果為序列A、B、C，則有_________棵不同的二叉樹可以得到這一結(jié)果。A.3 B.4 C.5 D.624、線索二叉樹是一種（）結(jié)構(gòu)。A．邏輯B．邏輯和存儲C．物理D．線性二、填空題7、對于任意一棵二叉樹，如果其葉子結(jié)點數(shù)為N0，度為1的結(jié)點數(shù)為N1，度為2的結(jié)點數(shù)為N2，則N0=___N2+1_________。8、具有256個結(jié)點的完全二叉樹的深度為___9___。9、一個深度為4的二叉樹，其結(jié)點至少有4個，至多有15個：10、深度為H的完全二叉樹至少有_2H-1__個結(jié)點；至多有2H-1_個結(jié)點；H和結(jié)點總數(shù)N之間的關(guān)系是H=log2N+1。11、若用鏈表存儲一棵二叉樹時，每個結(jié)點除數(shù)據(jù)域外，還有指向左孩子和右孩子的兩個指針。在這種存儲結(jié)構(gòu)中，N個結(jié)點的二叉樹共有__2N__個指針域，其中有_N-1__個指針域是存放了地址，有__N+1_____個指針是空指針。12、設(shè)一棵赫夫曼樹有6個葉子結(jié)點，權(quán)值分別為3、4、7、14、15、20，則根結(jié)點的權(quán)值是__63____13、對一棵完全二叉樹，設(shè)一個結(jié)點的編號為i，若它的左孩子結(jié)點存在，則其編號為2i；若右孩子結(jié)點存在，則其編號為2i+1；而雙親結(jié)點的編號為。14、赫夫曼樹是帶權(quán)路徑長度最小的二叉樹，又稱最優(yōu)二叉樹，路徑上權(quán)值較大的結(jié)點離根較近。15、structnode*rchildT=NULL16、二叉樹由_根結(jié)點__，__左子樹_，_右子樹__三個基本單元組成。17、樹的鏈表存儲結(jié)構(gòu)常用的有三種，其中，雙親表示法——以一組連續(xù)空間存儲樹的結(jié)點，在每個結(jié)點中設(shè)一個指示器指示雙親結(jié)點的位置。孩子表示法——每個結(jié)點的孩子以單鏈表的形式存儲，n個結(jié)點有n個孩子鏈表，n個頭指針又組成一個線性表，并以順序存儲結(jié)構(gòu)存儲。孩子兄弟表示法——以二叉鏈表作為樹的存儲結(jié)構(gòu)，鏈表中的結(jié)點的兩個指針分別指向該結(jié)點的第一個孩子結(jié)點和下一個兄弟結(jié)點。鄰接表法存儲圖，占用的存儲空間大小只與圖中邊數(shù)有關(guān)，而與結(jié)點個數(shù)無關(guān)。B.用鄰接表法存儲圖，占用的存儲空間大小與圖中邊數(shù)和結(jié)點個數(shù)都有關(guān)。C.用鄰接矩陣法存儲圖，占用的存儲空間大小與圖中結(jié)點個數(shù)和邊數(shù)都有關(guān)。D.用鄰接矩陣法存儲圖，占用的存儲空間大小只與圖中邊數(shù)有關(guān)，而與結(jié)點個數(shù)無關(guān)27、在圖的鄰接表存儲結(jié)構(gòu)上執(zhí)行深度優(yōu)先搜索遍歷類似于二叉樹上的（）A.先根遍歷B.中根遍歷C.后根遍歷D.按層次遍歷28、圖的廣度優(yōu)先遍歷算法類似于樹的（）。A.中根遍歷 B.先根遍歷 C.后根遍歷 D.按層次遍歷29、設(shè)無向圖的頂點個數(shù)為n，則該圖最多有（）條邊。A．n-1B．n(n-1)/2C．n(n+1)/2D．030、設(shè)有n個結(jié)點的無向圖，該圖至少應(yīng)有()條邊才能確保是一個連通圖。A．n-1B．nC．n+1D．nlogn；31、一個含有n個頂點的非連通圖，則（）：A．它的邊一定不大于n-1 B．它的邊一定不大于nC．它的邊一定小于n-1 D．它的邊一定大于032、要連通具有n個頂點的有向圖，至少需要（）條邊。A．n-lB．nC．n+lD．2n33、下列說法不正確的是（）。A．圖的遍歷是從給定的源點出發(fā)每一個頂點僅被訪問一次B．遍歷的基本算法有兩種：深度遍歷和廣度遍歷C．圖的深度遍歷不適用于有向圖D．圖的深度遍歷是一個遞歸過程34、無向圖G=(V,E),其中：V={a,b,c,d,e,f},E={(a,b),(a,e),(a,c),(b,e),(c,f),(f,d),(e,d)}，對該圖進行深度優(yōu)先遍歷，得到的頂點序列正確的是（）。A．a(chǎn),b,e,c,d,fB．a(chǎn),c,f,e,b,dC．a(chǎn),e,b,c,f,dD．a(chǎn),e,d,f,c,b35、若一個連通圖有n個頂點,則它的生成樹有（）條邊。A.n B.n-1 C.n+1 D.n(n-1)/2二、填空題22、鄰接多重表適于表示稀疏無向圖，鄰接表、逆鄰接表和十字鏈表適于表示稀疏有向圖。23、設(shè)有向圖的頂點個數(shù)為n，則該圖最多有n(n-1)條弧。24、右圖中頂點D的出度是3。25、8層完全二叉樹至少有_128(第七層滿，加第八層１個)_個結(jié)點，擁有100個結(jié)點的完全二叉樹的最大層數(shù)為__7__。26、求圖的最小生成樹有兩種算法：_普里姆（Prim）算法和克魯斯卡爾（Kruskal）算法。其中，_克魯斯卡爾____算法適合于求_邊稀疏___的稀疏圖的最小生成樹。普里姆算法適用于求邊稠密的網(wǎng)的最小生成樹。27、對于含n個頂點e條邊的無向連通圖，利用普里姆算法生成最小代價生成樹其時間復(fù)雜度為__O(n2）_，利用克魯斯卡爾算法生成最小代價生成樹其時間復(fù)雜度為_O(eloge)__。28、在無向圖的深度優(yōu)先遍歷算法中，DFS（從某個頂點出發(fā)深度優(yōu)先遍歷圖的算法）被調(diào)用了幾次就說明該圖有幾個聯(lián)通分量。29、一個有n個結(jié)點的圖，最少有1個連通分量，最多有n個連通分量。30、判斷一個無向圖是一棵樹的條件是_有n個頂點，n-1條邊的無向連通圖。31、有向圖G的強連通分量是指__有向圖的極大強連通子圖____。32、右圖中的強連通分量的個數(shù)為3個。33、一個連通圖的__生成樹____是一個極小連通子圖。34、若用n表示圖中頂點數(shù)目，則有___n(n-1)/2___條邊的無向圖成為完全圖。35、已知一無向圖G=（V，E），其中V={a,b,c,d,e}E={(a,b),(a,d),(a,c),(d,c),(b,e)}現(xiàn)用某一種圖遍歷方法從頂點a開始遍歷圖，得到的序列為abecd，則采用的是__深度優(yōu)先_遍歷方法。36、為實現(xiàn)圖的廣度優(yōu)先搜索，除了一個標志數(shù)組標志已訪問的圖的結(jié)點外，還需_隊列__存放被訪問的結(jié)點以實現(xiàn)遍歷。37、設(shè)無向圖G有n個頂點，m條邊。閱讀下面用鄰接表存儲該圖的算法。（設(shè)頂點值用1～n或0～n-1編號），并在畫線處完成填空。voidCreatGraph(AdjListg)ertex);g[i].firstarc=null;}for(k=1;k<=m;k++)irstarc;g[i].firstarc=p;irstarc; g[j].frstarc=p;}}三、簡答題4、已知一個無向網(wǎng)的頂點集為{a,b,c,d,e}，其鄰接矩陣如下所示(1)畫出該無向網(wǎng)圖形；(2)根據(jù)鄰接矩陣從頂點a出發(fā)進行深度優(yōu)先遍歷和廣度優(yōu)先遍歷，寫出相應(yīng)的遍歷序列。答案：(1)該無向網(wǎng)圖形如下：dd1aebc54362深度優(yōu)先序列為：abcde；廣度優(yōu)先序列為：abdce36、適用于折半查找的表的存儲方式及元素排列要求為()A．鏈接方式存儲，元素無序B．鏈接方式存儲，元素有序C．順序方式存儲，元素無序D．順序方式存儲，元素有序37、對有18個元素的有序表A作折半查找，則查找A[3]的比較序列的下標為（），2，3，5，2，3，5，3，4，2，338、對有14個數(shù)據(jù)元素的有序表R進行折半搜索，搜索到R[3]的關(guān)鍵字等于給定值，查找過程中元素比較的順序依次為（）。A.R[6],R[2],R[4],R[3] B.R[6],R[4],R[2],R[3]C.R[0],R[1],R[2],R[3] D.R[0],R[13],R[2],R[3]39、對N個元素的表做順序查找時，若查找每個元素的概率相同，則平均查找長度為()A．（N+1）/2B.N/2C.ND.[（1+N）*N]/240、有一個長度為12的有序表，按二分查找法對該表進行查找，在表內(nèi)各元素等概率情況下查找成功所需的平均比較次數(shù)為（）。A．35/1212121241、當在一個有序的順序存儲表上查找一個數(shù)據(jù)時，即可用折半查找，也可用順序查找，但前者比后者的查找速度()A．必定快B.不一定C.在大部分情況下要快D.取決于表遞增還是遞減42、設(shè)有序表的關(guān)鍵字序列為{1，4，6，10，18，35，42，53，67，71，78，84，92，99}，當用二分查找法查找健值為84的結(jié)點時，經(jīng)（）次比較后查找成功。B.3C.443、在查找過程中，只完成查找操作，這種查找稱為（）A.靜態(tài)查找 B.動態(tài)查找 C.內(nèi)部查找 D.外部查找44、分別以下列序列構(gòu)造二叉排序樹，與用其它三個序列所構(gòu)造的結(jié)果不同的是()A．（100，80，90，60，120，110，130）B.（100，120，110，130，80，60，90）C.（100，60，80，90，120，110，130）D.(100，80，60，90，120，130，110)二、填空題對大小均為n的有序表和無序表分別進行順序查找，在等概率查找的情況下，對于查找失敗，它們的平均查找長度是不同的，對于查找成功,他們的平均查找長度是相同的。執(zhí)行順序查找時，儲存方式可以是__順序存儲或鏈式存儲__，二分法查找時，要求線性表__順序存儲且有序__。40、在數(shù)據(jù)結(jié)構(gòu)中一般采用平均查找長度衡量查找算法時間性能，而對于排序算法一班通過統(tǒng)計記錄的比較次數(shù)和移動次數(shù)衡量排序算法的時間性能。二叉查找樹的查找效率與二叉樹的樹型有關(guān),在呈單枝樹時其查找效率最低。若表中元素個數(shù)為n，則順序查找該表中的元素，若查找成功，則比較關(guān)鍵字的次數(shù)最多為__n__次，平均比較次數(shù)為(n+1)/2；若進行折半查找，則最大比較次數(shù)是__㏒2n」+1。44、給定一個主關(guān)鍵字，在長為n的有序表中進行折半查找，則最多經(jīng)過log2n+1次比較即可確定該關(guān)鍵字是否在表中，至少經(jīng)過1次比較即可確定該關(guān)鍵字在表中。在順序表（8,11,15,19,25,26,30,33,42,48,50）中，用二分（折半）法查找關(guān)鍵碼值20，需做的關(guān)鍵碼比較次數(shù)為__4__。在有序表A[1..12]中，采用二分查找算法查等于A[12]的元素，所比較的元素下標依次為_6,9,11,12。己知有序表為(12,18,24,35,47,50,62,83,90,115，134)當用二分法查找90時，需____2______次查找成功，47時_____4_____成功，查100時，需______3____次才能確定不成功。假定查找有序表A[1..12]中每個元素的概率相等，則進行二分查找時的平均查找長度為___37/12____。49、在查找中，能夠唯一標識一個記錄的關(guān)鍵字稱之為主關(guān)鍵字，能夠標識若干記錄的關(guān)鍵字稱之為次關(guān)鍵詞。動態(tài)查找表和靜態(tài)查找表的重要區(qū)別在于前者包含有__插入__和_刪除_運算，而后者不包含這兩種運算。已知二叉排序樹的左右子樹均不為空，則____左子樹______上所有結(jié)點的值均小于它的根結(jié)點值，_____右子樹_____上所有結(jié)點的值均大于它的根結(jié)點的值。三、簡答題5、設(shè)有序表為(a,b,c,d,e,f,g,h,i,j,k,p,q)，請分別畫出對給定值a,g和n進行折半查找的過程?！敬鸢浮浚?）查找a的過程如下(圓括號表示當前比較的關(guān)鍵字)，經(jīng)過三次比較，查找成功。（2）g的查找過程如下，一次比較成功。

[a

b

c

d

e

f

(g)

h

i

j

k

p

q

]（3）n的查找過程如下，

經(jīng)過四次比較，查找失敗。6、構(gòu)造有12個元素的二分查找的判定樹，并求解下列問題：（1）各元素的查找長度最大是多少（2）查找長度為1、2、3、4的元素各有多少具體是哪些元素（3）查找第5個元素依次要比較哪些元素（4）試求解在等概率情況下，查找成功情況下二分查找的平均查找長度?！敬鸢浮?2個元素的二叉判斷樹如下圖所示：

（1）最大查找長度是樹的深度4。（2）查找長度為1的元素有1個，為第6個，查找長度為2的元素有2個，為第3個和第9個，查找長度為3的元素有4個，為第1、4、7、11個，查找長度為4的元素有5個，為第2、5、8、10、12個。（3）查找第五個元素依次比較6，3，4，5。（4）根據(jù),平均查找長度ASL=（1+2*2+4*3+5*4）/12=37/127、設(shè)有一個輸入數(shù)據(jù)的序列是{46,25,78,62,12,80},試畫出從空樹起，逐個輸入各個數(shù)據(jù)而生成的二叉排序樹。答案：8、已知序列40，30，50，24，28，46，60，10。試畫出由該輸入序列構(gòu)成的二叉排序樹，并分別給出依次執(zhí)行下列操作后的二叉排序樹（共畫四棵樹）（1）插入數(shù)據(jù)42和80；（2）刪除數(shù)據(jù)30；（3）刪除數(shù)據(jù)50。答案：45、n個記錄進行直接插入排序時，記錄最小的比較次數(shù)是()A.(n-1) C.(n+3)(n-2)/2 246、對n個記錄進行希爾排序，所需要的輔助存儲空間為（）。（1og2n）（n）（1）（n2）就平均性能而言，目前最好的內(nèi)排序方法是()排序法。A.冒泡B.希爾插入C.交換D.快速直接插入排序在最好情況下的時間復(fù)雜度為（）A．O(logn)B．O(n)C．O(n*logn)D．O(n2)49、以下算法思路分別出自什么排序算法：取當前最小的數(shù)，插入到已經(jīng)排好序的數(shù)據(jù)末尾：（）；取當前要排序的數(shù)，插入到已經(jīng)排好序的數(shù)據(jù)中適當位置：（）；相鄰兩個數(shù)比較，如果大小順序顛倒就把兩者交換過來：（）。A.插入排序、選擇排序、起泡排序 B.選擇排序、插入排序、起泡排序C.插入排序、選擇排序、快速排序 D.選擇排序、插入排序、快速排序51、下列四種排序算法中，哪一個需要采用遞歸調(diào)用的方式實現(xiàn)A、直接插入排序 B、快速排序 C、冒泡排序 D、折半插入排序從未排序序列中依次取出一個元素與已排序序列中的元素依次進行比較，然后將其放在已排序序列的合適位置，該排序方法稱為()排序法。A.插入B.選擇C.希爾D.快速快速排序方法在（）情況下最不利于發(fā)揮其長處。A.要排序的數(shù)據(jù)量太大B.要排序的數(shù)據(jù)中含有多個相同值C.要排序的數(shù)據(jù)個數(shù)為奇數(shù)D.要排序的數(shù)據(jù)已基本有序?qū)σ唤M數(shù)據(jù)（84，47，25，15，21）排序，數(shù)據(jù)的排列次序在排序的過程中的變化為（1）8447251521（2）1547258421（3）1521258447（4）1521254784則采用的排序是()。A.選擇B.冒泡C.快速D.插入55、在希爾排序算法中，需要借助（）實現(xiàn)A、直接插入排序 B、快速排序 C、冒泡排序 D、折半插入排序若用冒泡排序方法對序列{10,14,26,29,41,52}從大到小排序，需進行（）次比較。A.3B.10C.15D.25在下列排序算法中，哪一個算法的時間復(fù)雜度與初始排序無關(guān)（）。A.直接插入排序B.起泡排序C.快速排序D.選擇排序?qū)ο铝兴姆N排序方法，在排序中關(guān)鍵字比較次數(shù)同記錄初始排列無關(guān)的是()。A．直接插入B.起泡排序C.快速排序D.二分法插入若采用希爾排序法對序列{12,36,21,7,2,19,6,31,49,13,27,38,5}進行排序，增量分別為5、3、1。那么當增量為3時，排序結(jié)束后的序列是哪一個A.{5,2,19,6,27,21,7,31,38,12,36,49,13}B.{12,6,5,7,2,19,36,21,49,13,27,38,31}C.{7,2,5,12,6,19,13,21,38,31,27,49,