西北工業(yè)大學(xué)21秋《數(shù)據(jù)結(jié)構(gòu)》復(fù)習(xí)考核試題庫答案參考套卷59

《西北工業(yè)大學(xué)21秋《數(shù)據(jù)結(jié)構(gòu)》復(fù)習(xí)考核試題庫答案參考套卷59》由會員分享，可在線閱讀，更多相關(guān)《西北工業(yè)大學(xué)21秋《數(shù)據(jù)結(jié)構(gòu)》復(fù)習(xí)考核試題庫答案參考套卷59（11頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、西北工業(yè)大學(xué)21秋《數(shù)據(jù)結(jié)構(gòu)》復(fù)習(xí)考核試題庫答案參考 1. 高度為5的完全二叉樹中含有的結(jié)點數(shù)至少為( )。 A、16 B、17 C、31 D、32 參考答案：A 2. B+樹應(yīng)用在( )文件系統(tǒng)中。 A.順序 B.散列 C.VSAM D.ISAM 參考答案：C 3. 依次在初始為空的隊列中插入元素X，Y，Z，W以后，緊接著作了兩次刪除操作，此時的隊頭元素是( ) A.X B.Y C.Z D.W 參考答案：C 4. 下面關(guān)于線性表的敘述錯誤的是( )。 A.線性表采用順序存儲必須占用一片連續(xù)的存儲空間 B

2、.線性表采用鏈?zhǔn)酱鎯Σ槐卣加靡黄B續(xù)的存儲空間 C.線性表采用鏈?zhǔn)酱鎯Ρ阌诓迦牒蛣h除操作的實現(xiàn) D.線性表采用順序存儲便于插入和刪除操作的實現(xiàn) 參考答案：D 5. 在隊列中，允許進(jìn)行刪除操作的一端稱為隊尾。( ) A、錯誤 B、正確 參考答案：B 6. 若一個有向圖的鄰接距陣中，主對角線以下的元素均為零，則該圖的拓?fù)溆行蛐蛄? )。 A.一定存在 B.一定不存在 C.不一定存在 D.不確定 參考答案：A 7. 若進(jìn)棧序列為a，b，c，且進(jìn)棧和出?？梢源┎暹M(jìn)行，則可能出現(xiàn)6個不同的出棧序列。( ) A、錯誤 B、正確

3、 參考答案：A 8. 二維數(shù)組A的每個元素是由6個字符組成的串，其行下標(biāo)i=0，1，…，8，列下標(biāo)為j=1，2，…，10。設(shè)每個字符占一個字節(jié)，若按行先存儲，元素A[8，5]的起始地址與A按列存儲時起始地址相同的元素是( )。 A.A[8，5] B.A[3，10] C.A[5，8] D.A[0，9] 參考答案：B 9. 棧下溢是指在?？諘r進(jìn)行出棧操作。( ) A、錯誤 B、正確 參考答案：B 10. 在指定結(jié)點之后插入新結(jié)點時，雙鏈表比單鏈表更方便。( ) A.正確 B.錯誤 參考答案：B 11. 四個元素進(jìn)入隊列

4、QU的順序是U、V、X、Y，進(jìn)行DeQueue(QU，x)操作后，隊頭元素是( )。 A.Y B.X C.V D.U 參考答案：C 12. 隊列的修改是按先進(jìn)先出的原則進(jìn)行的。( ) A、錯誤 B、正確 參考答案：B 13. 已知函數(shù)Sub(s,I,j)的功能是返回串s中從第i個字符起長度為j的子串，函數(shù)Scopy(s,t)的功能為復(fù)制串t到s。若字符串S=″SCIENCESTUDY″，則調(diào)用函數(shù)Scopy(P,Sub(S,1,7))后得到( )。 A、P=″SCIENCE″ B、P=″STUDY″ C、S=″SCIENCE″ D、S=

5、″STUDY″ 參考答案：A 14. 如果求一個連通圖中以某個頂點為根的高度最小的生成樹，應(yīng)采用( )。 A.深度優(yōu)先搜索算法 B.廣度優(yōu)先搜索算法 C.求最小生成樹的prim算法 D.拓?fù)渑判蛩惴? 參考答案：B 15. 若進(jìn)棧序列為a，b，c，則通過入出棧操作可能得到的a，b，c的不同排列個數(shù)為( )。 A、4 B、5 C、6 D、7 參考答案：B 16. 二叉樹中必有度為2的結(jié)點。( ) A、錯誤 B、正確 參考答案：A 17. 線性表是具有n個( )的有限序列。 A.字符 B.數(shù)據(jù)元素 C.

6、數(shù)據(jù)項 D.表元素 參考答案：B 18. 線性表(a1，a2，...，an)以鏈?zhǔn)椒绞酱鎯?，訪問第i位置元素的時間復(fù)雜度為( )。 A.O(0) B.O(1) C.O(n) D.O(n2) 參考答案：C 19. 對于只在表的首、尾兩端進(jìn)行插入操作的線性表，宜采用的存儲結(jié)構(gòu)為( )。 A.順序表 B.用頭指針表示的循環(huán)單鏈表 C.用尾指針表示的循環(huán)單鏈表 D.單鏈表 參考答案：C 20. 在計算機內(nèi)實現(xiàn)遞歸算法時所需的輔助數(shù)據(jù)結(jié)構(gòu)是( )。 A、棧 B、隊列 C、樹 D、圖 參考答案：A 21. 設(shè)根

7、結(jié)點層次為1，某二叉樹的結(jié)點前序序列和后序序列正好相反，則該二叉樹一定是( )。 A.高度等于其結(jié)點數(shù) B.空或只有一個結(jié)點 C.任一結(jié)點無左子女 D.任一結(jié)點無右子女 參考答案：A 22. 用二叉鏈表表示具有n個結(jié)點的二叉樹時，值為空的指針域的個數(shù)為( )。 A.n-1 B.n C.n+l D.2n 參考答案：C 23. 在一個長度為n的單鏈表L中，刪除鏈表中*p的前驅(qū)結(jié)點的時間復(fù)雜度為O(n)。( ) A、錯誤 B、正確 參考答案：B 24. 設(shè)二維數(shù)組A[0..m-1][0..n-1]按行優(yōu)先順序存儲且每個元素占c

8、個單元，則元素A[i][j]的地址為( )。 A.LOC(A[0][0])+(j*m+i)*c B.LOC(A[0][0])+[(j-1)*m+i-1]*c C.LOC(A[0][0])+(i*n+j)*c D.LOC(A[0][0])+[(i-1)*n+j-1]*c 參考答案：C 25. 在最好和最壞情況下的時間復(fù)雜度均為O(nlogn)且穩(wěn)定的排序方法是堆排序。( ) A、錯誤 B、正確 參考答案：A 26. 按排序過程中依據(jù)的原則分類，快速排序?qū)儆? )。 A.插入類的排序方法 B.選擇類的排序方法 C.交換類的排序方法 D.歸并

9、類的排序方法 參考答案：C 27. 某二叉樹的先序序列和后序序列正好相反，則該二叉樹的特點一定是( )。 A.空或只有一個結(jié)點 B.高度等于其結(jié)點數(shù) C.任一結(jié)點無左孩子 D.任一結(jié)點無右孩子 參考答案：B 28. 對長度為n的關(guān)鍵字序列進(jìn)行堆排序的空間復(fù)雜度為( )。 A.O(log2n) B.O(1) C.O(n) D.O(n*log2n) 參考答案：B 29. 歸并排序是一種穩(wěn)定的排序方法。( ) A.正確 B.錯誤 參考答案：A 30. 隊列允許在隊尾刪除，在隊頭插入。( ) A.正確 B.

10、錯誤 參考答案：A 31. 隊列的修改是按照先進(jìn)先出的原則進(jìn)行的。( ) A、錯誤 B、正確 參考答案：B 32. 設(shè)有向圖有n個頂點和e條邊，采用領(lǐng)接表作為其存儲表示，在進(jìn)行拓?fù)渑判驎r，總的計算時間為( ) A.O(nlog2e) B.O(n+e) C.O(ne) D.O(n2) 參考答案：B 33. 一棵左右子樹均不空的二叉樹在前序線索化后，其中空的鏈域的個數(shù)是( )。 A.不確定 B.2 C.1 D.0 參考答案：C 34. 基數(shù)排序需要進(jìn)行關(guān)鍵字的比較。( ) A.正確 B.錯誤 參考

11、答案：B 35. 對線性表進(jìn)行二分查找時，要求線性表必須( )。 A.以順序方式存儲 B.以鏈接方式存儲 C.以順序方式存儲，且結(jié)點按關(guān)鍵字有序排列 D.以鏈接方式存儲，且結(jié)點按關(guān)鍵字有序排列 參考答案：C 36. 一個有向圖的鄰接表和逆鄰接表中結(jié)點的個數(shù)可能不等。( ) A.正確 B.錯誤 參考答案：B 37. 設(shè)某棵二叉樹中有2000個結(jié)點，則該二叉樹的最小高度為( )。 A.9 B.10 C.11 D.12 參考答案：C 38. 中序遍歷二叉排序樹可以得到一個有序的序列。( ) A.正確 B.錯誤

12、 參考答案：A 39. 稀疏矩陣常用的壓縮存儲方法有兩種，它們是( )。 A.散列和十字鏈表 B.二維數(shù)組和三維數(shù)組 C.三元組和散列 D.三元組和十字鏈表 參考答案：D 40. 插入、刪除只能在同一端進(jìn)行的線性表，稱為( )。 A.隊列 B.棧 C.循環(huán)隊列 D.循環(huán)棧 參考答案：B 41. 對無序表用折半查找比順序查找快。( ) A.正確 B.錯誤 參考答案：B 42. 下列排序算法中，在每一趟都能選出一個元素放到其最終位置上，并且其時間性能受數(shù)據(jù)初始特性影響的是( )。 A.直接選擇排序 B.直

13、接插入排序 C.快速排序 D.堆排序 參考答案：C 43. 最小生成樹問題是構(gòu)造帶權(quán)連通圖(網(wǎng))的最小代價生成樹。( ) A.正確 B.錯誤 參考答案：A 44. 對某二叉樹進(jìn)行前序遍歷的結(jié)果為ABDEFC，中序遍歷的結(jié)果為DBFEAC，則后序遍歷的結(jié)果為( ) A.DBFEAC B.DFEBCA C.BDFECA D.BDEFAC 參考答案：B 45. 數(shù)據(jù)的邏輯結(jié)構(gòu)在計算機存儲器內(nèi)的表示，稱為數(shù)據(jù)的邏輯結(jié)構(gòu)。( ) A、錯誤 B、正確 參考答案：A 46. 深度為h的滿m叉樹的第k層的結(jié)點(1=A.m

14、k-1 B.mk-1 C.mh-1 D.mh-1 參考答案：A 47. 棧的插入和刪除操作在( )進(jìn)行。 A.棧頂 B.棧底 C.任意位置 D.指定位置 參考答案：A 48. 在目標(biāo)串T[0..n-1]=“xwxxyxy”中，對模式串P[0..m-1]=“xy”進(jìn)行子串定位操作的結(jié)果是( )。 A.1 B.2 C.3 D.5 參考答案：C 49. 設(shè)有以下四種排序方法，則( )的空間復(fù)雜度最大。 A.冒泡排序 B.快速排序 C.堆排序 D.希爾排序 參考答案：B 50. 設(shè)F是一個森林，B是由F轉(zhuǎn)換得到的二叉樹，F(xiàn)中有n個非葉結(jié)點，則B中右指針域為空的結(jié)點有( ) A.n-1 B.n C.n+1 D.n+2 參考答案：B