數(shù)據(jù)結(jié)構(gòu)考研復(fù)習(xí)2

單選題練習(xí)

1、以下關(guān)于線性表的敘述，正確的是

Ⅰ線性表的每一個元素都有一個直接前驅(qū)和一個直接后繼

Ⅱ線性表中所有元素的排列必須有序

Ⅲ線性表的順序存儲結(jié)構(gòu)優(yōu)于鏈?zhǔn)酱鎯Y(jié)構(gòu)

Ⅳ線性表是一個有限序列，可以為空A．Ⅰ、Ⅱ、ⅢB.Ⅱ、Ⅲ、ⅣC.僅ⅠD.

僅Ⅳ數(shù)據(jù)結(jié)構(gòu)練習(xí)題2、采用順序存儲結(jié)構(gòu)的線性表的插入算法中，當(dāng)n個空間已滿時，可申請再增加分配m個空間。若申請失敗，說明系統(tǒng)可分配的存儲空間沒有

A．m個

B.m個連續(xù)的

C.n+m個

D.n+m個連續(xù)的數(shù)據(jù)結(jié)構(gòu)練習(xí)題

1、以下屬于邏輯結(jié)構(gòu)的數(shù)據(jù)結(jié)構(gòu)是

A．順序表

B.哈希表

C.有序表

D.單鏈表數(shù)據(jù)結(jié)構(gòu)練習(xí)題2、有六個元素6，5，4，3，2，1的順序進(jìn)棧，問下列哪一個不是合法的出棧序列

A.543612B.453126C.346521D.234156數(shù)據(jù)結(jié)構(gòu)練習(xí)題3、若一個棧以向量V[1..n]存儲，初始棧頂指針top為n+1，則下面x進(jìn)棧的正確操作是

A．top=top+1;V[top]=xB.V[top]=x;top=top+1C.top=top-1;V[top]=xD.V[top]=x;top=top-1數(shù)據(jù)結(jié)構(gòu)練習(xí)題4、若棧采用順序存儲方式存儲，現(xiàn)兩棧共享空間V[1..m]，top[i]代表第i個棧(i=1,2)棧頂，棧1的底在v[1]，棧2的底在V[m]，則棧滿的條件是

A.|top[2]-top[1]|=0

B.top[1]+1=top[2]C.top[1]+top[2]=mD.top[1]=top[2]數(shù)據(jù)結(jié)構(gòu)練習(xí)題5、用鏈接方式存儲的隊列，在進(jìn)行刪除運算時

A.僅修改頭指針

B.僅修改尾指針

C.頭、尾指針都要修改

D.

頭、尾指針可能都要修改數(shù)據(jù)結(jié)構(gòu)練習(xí)題6、假設(shè)以數(shù)組A[m]存放循環(huán)隊列的元素,其頭尾指針分別為front和rear，則當(dāng)前隊列中的元素個數(shù)為

A．(rear-front+m)%mB．rear-front+1C．(front-rear+m)%mD．(rear-front)%m數(shù)據(jù)結(jié)構(gòu)練習(xí)題7、已知輸入序列為abcd經(jīng)過輸出受限的雙向隊列后能得到的輸出序列有

A.dacb

B.cadbC.dbcaD.以上答案都不對數(shù)據(jù)結(jié)構(gòu)練習(xí)題8、若以1234作為雙端隊列的輸入序列，則既不能由輸入受限的雙端隊列得到，也不能由輸出受限的雙端隊列得到的輸出序列是

A.1234B.4132

C.4231D.4213數(shù)據(jù)結(jié)構(gòu)練習(xí)題9、將一個A[1..100，1..100]的三對角矩陣，按行優(yōu)先存入一維數(shù)組B[1‥298]中，A中元素A6665（即該元素下標(biāo)i=66，j=65），在B數(shù)組中的位置K為

A.198

B.195C.197D.199數(shù)據(jù)結(jié)構(gòu)練習(xí)題10、若對n階對稱矩陣A以行序為主序方式將其下三角形的元素(包括主對角線上所有元素)依次存放于一維數(shù)組B［1..(n(n+1))/2］中，則在B中確定aij（i<j）的位置k的關(guān)系為A.i*(i-1)/2+jB.j*(j-1)/2+iC.i*(i+1)/2+jD.j*(j+1)/2+i數(shù)據(jù)結(jié)構(gòu)練習(xí)題11、設(shè)A是n*n的對稱矩陣，將A的對角線及對角線上方的元素以列為主的次序存放在一維數(shù)組B[1..n(n+1)/2]中，對上述任一元素aij(1≤i，j≤n，且i≤j)在B中的位置為A.i(i-l)/2+jB.j(j-l)/2+iC.j(j-l)/2+i-1D.i(i-l)/2+j-1數(shù)據(jù)結(jié)構(gòu)練習(xí)題12、有一個100*90的稀疏矩陣，非0元素有10個，設(shè)每個整型數(shù)占2字節(jié)，則用三元組表示該矩陣時，所需的字節(jié)數(shù)是

A.60

B.66C.18000D.33數(shù)據(jù)結(jié)構(gòu)練習(xí)題13、算術(shù)表達(dá)式a+b*（c+d/e）轉(zhuǎn)為后綴表達(dá)式后為（）

A．a(chǎn)b+cde/*

B．a(chǎn)bcde/+*+C．a(chǎn)bcde/*++D．a(chǎn)bcde*/++數(shù)據(jù)結(jié)構(gòu)練習(xí)題14、設(shè)樹T的度為4，其中度為1，2，3和4的結(jié)點個數(shù)分別為4，2，1，1則T中的葉子數(shù)為

A．5B．6C．7

D．8數(shù)據(jù)結(jié)構(gòu)練習(xí)題15、設(shè)森林F對應(yīng)的二叉樹為B，它有m個結(jié)點，B的根為p,p的右子樹結(jié)點個數(shù)為n,森林F中第1棵樹的結(jié)點個數(shù)是

A．m-nB．m-n-1C．n+1D．條件不足，無法確定數(shù)據(jù)結(jié)構(gòu)練習(xí)題16、一棵完全二叉樹上有1001個結(jié)點，其中葉子結(jié)點的個數(shù)是

A．250B．500C．254

D．以上答案都不對數(shù)據(jù)結(jié)構(gòu)練習(xí)題17、若度為m的哈夫曼樹中，其葉結(jié)點個數(shù)為n，則非葉結(jié)點的個數(shù)為

A．n-1B．n/m-1

C．(n-1)/(m-1)

D．n/(m-1)-1數(shù)據(jù)結(jié)構(gòu)練習(xí)題18、一個具有1025個結(jié)點的二叉樹的高h(yuǎn)為

A．11B．10C．11至1025之間

D．10至1024之間數(shù)據(jù)結(jié)構(gòu)練習(xí)題19、將有關(guān)二叉樹的概念推廣到三叉樹，則一棵有244個結(jié)點的完全三叉樹的高度

A．4B．5

C．6D．7數(shù)據(jù)結(jié)構(gòu)練習(xí)題20、某二叉樹中序序列為A,B,C,D,E,F,G，后序序列為B,D,C,A,F,G,E則該二叉樹對應(yīng)的森林包括樹為

A．l

B．2C．3D．概念上是錯誤的數(shù)據(jù)結(jié)構(gòu)練習(xí)題21、若X是二叉中序線索樹中一個有左孩子的結(jié)點，且X不為根，則X的前驅(qū)為

A.X的雙親

B.X的右子樹中最左的結(jié)點

C.X的左子樹中最右結(jié)點

D.X的左子樹中最右葉結(jié)點數(shù)據(jù)結(jié)構(gòu)練習(xí)題22、設(shè)F是一個森林，B是由F變換得的二叉樹。若F中有n個非終端結(jié)點，則B中右指針域為空的結(jié)點的個數(shù)為

A．n-1B．n

C．n+1D．n+2數(shù)據(jù)結(jié)構(gòu)練習(xí)題23、下述編碼中哪一個不是前綴碼

A．（00，01，10，11）

B．（0，1，00，11）

C．（0，10，110，111）

D．（1，01，000，001）數(shù)據(jù)結(jié)構(gòu)練習(xí)題24、分別以下列序列構(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)數(shù)據(jù)結(jié)構(gòu)練習(xí)題25、有n個結(jié)點并且其高度為n的二叉樹的數(shù)目是個。

A．2n-1B．2n-1

C．2n-1

D．2n+1數(shù)據(jù)結(jié)構(gòu)練習(xí)題26、設(shè)無向圖的頂點個數(shù)為n，則該圖最多的邊為

A．n-1

B．n(n-1)/2C．n(n+1)/2D．n2數(shù)據(jù)結(jié)構(gòu)練習(xí)題27、一個n個頂點的連通無向圖，其邊的個數(shù)至少為

A．n-1B．nC．n+1D．nlogn數(shù)據(jù)結(jié)構(gòu)練習(xí)題28、要連通具有n個頂點的有向圖，至少需要（）條邊。

A．n-l

B．nC．n+lD．2n數(shù)據(jù)結(jié)構(gòu)練習(xí)題29、用DFS遍歷一個無環(huán)有向圖，并在DFS算法退棧返回時打印相應(yīng)的頂點，則輸出的頂點序列是

A．逆拓?fù)溆行?/p>

B．拓?fù)溆行?/p>

C．無序的

D．有序的數(shù)據(jù)結(jié)構(gòu)練習(xí)題30、設(shè)圖如下所示，在下面的5個序列中，符合深度優(yōu)先遍歷的序列有多少？aebdfcacfdebaedfcbaefdcbaefdbc

A．4個B．3個

C．2個D．1個數(shù)據(jù)結(jié)構(gòu)練習(xí)題31、BFS算法可用來解決單源最短路徑問題，僅當(dāng)各邊上的權(quán)值

A．均相等

B．均互不相等

C．不一定相等

D．任意數(shù)據(jù)結(jié)構(gòu)練習(xí)題32、下列關(guān)于AOE網(wǎng)的敘述中，不正確的是A．關(guān)鍵活動不按期完成就會影響整個工程的完成時間B．任何一個關(guān)鍵活動提前完成，那么整個工程將會提前完成C．所有的關(guān)鍵活動提前完成，那么整個工程將會提前完成D．某些關(guān)鍵活動提前完成，那么整個工程將會提前完成數(shù)據(jù)結(jié)構(gòu)練習(xí)題33、下列說法正確的是A．若一個有向圖的鄰接矩陣對角線以下元素均為零，則該圖的拓?fù)溆行蛐蛄斜囟ù嬖贐．既使有向無環(huán)圖的拓?fù)湫蛄形ㄒ?，也不能唯一確定該圖的特征C．廣度遍歷生成樹描述了從起點到各頂點的最短路徑D．用鄰接矩陣法存儲一個圖所需的存儲單元數(shù)目與圖的邊數(shù)有關(guān)數(shù)據(jù)結(jié)構(gòu)練習(xí)題34、G是一個非連通無向圖，共有28條邊，則該圖至少的頂點數(shù)為

A.7B.8

C.9D.10數(shù)據(jù)結(jié)構(gòu)練習(xí)題35、N個頂點的連通圖用鄰接矩陣表示時,該矩陣至少的非零元素為

A.NB.2(N-1)

C.N-1D.2N-1數(shù)據(jù)結(jié)構(gòu)練習(xí)題36、若查找每個記錄的概率均等，則在具有n個記錄的連續(xù)順序文件中采用順序查找法查找一個記錄，其平均查找長度ASL為

A．(n-1)/2B.n/2

C.(n+1)/2D.n數(shù)據(jù)結(jié)構(gòu)練習(xí)題37、假定N為線性表中結(jié)點數(shù)，且每次查找都是成功的。順序查找法適用于查找順序存儲或鏈?zhǔn)酱鎯Φ木€性表，平均比較次數(shù)為

A.N+1B.2logNC.logN

D.N/2數(shù)據(jù)結(jié)構(gòu)練習(xí)題38、二分法查找只適用于查找順序存儲的有序表，假定N為線性表中結(jié)點數(shù)，且每次查找都是成功的，則平均比較次數(shù)為

A.N+1B.2logN

C.logND.N/2數(shù)據(jù)結(jié)構(gòu)練習(xí)題39、具有12個關(guān)鍵字的有序表，折半查找的平均查找長度為

A.3.1B.4C.2.5D.5數(shù)據(jù)結(jié)構(gòu)練習(xí)題40、設(shè)有一組記錄的關(guān)鍵字為{19，14，23，1，68，20，84，27，55，11，10，79}，用鏈地址法構(gòu)造散列表，散列函數(shù)為H（key）=keyMOD13,散列地址為1的鏈中的記錄數(shù)為

A．1B.2C.3

D.4數(shù)據(jù)結(jié)構(gòu)練習(xí)題41、假定有k個關(guān)鍵字互為同義詞，若用線性探測法把這k個關(guān)鍵字存入散列表中，至少要進(jìn)行探測的次數(shù)為

A．k-1次

B.k次

C.k+1次

D.k（k+1）/2次數(shù)據(jù)結(jié)構(gòu)練習(xí)題42、下列排序算法中，穩(wěn)定的排序是

A.堆排序，冒泡排序

B.快速排序，堆排序

C.直接選擇排序，歸并排序

D.歸并排序，冒泡排序數(shù)據(jù)結(jié)構(gòu)練習(xí)題43、若需在O(nlogn)的時間內(nèi)完成對數(shù)組的排序，且要求排序是穩(wěn)定的，則可選擇

A.快速排序

B.堆排序

C.歸并排序

D.直接插入排序數(shù)據(jù)結(jié)構(gòu)練習(xí)題44、下面給出的排序方法中，排序過程中的比較次數(shù)與排序方法無關(guān)的是

A．選擇排序法

B.插入排序法

C.快速排序法

D.堆排序法數(shù)據(jù)結(jié)構(gòu)練習(xí)題45、數(shù)據(jù)序列（8，9，10，4，5，6，20，1，2）只能是下列的兩趟排序后的結(jié)果是

A．選擇排序

B.冒泡排序

C.插入排序

D.堆排序數(shù)據(jù)結(jié)構(gòu)練習(xí)題46、數(shù)據(jù)序列（2，1，4，