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

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

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

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

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

4、QU的順序是U、V、X、Y，進(jìn)行DeQueue(QU，x)操作后，隊(duì)頭元素是( )。 A.Y B.X C.V D.U 參考答案：C 12. 隊(duì)列的修改是按先進(jìn)先出的原則進(jìn)行的。( ) A、錯(cuò)誤 B、正確 參考答案：B 13. 已知函數(shù)Sub(s,I,j)的功能是返回串s中從第i個(gè)字符起長(zhǎng)度為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. 如果求一個(gè)連通圖中以某個(gè)頂點(diǎn)為根的高度最小的生成樹(shù)，應(yīng)采用( )。 A.深度優(yōu)先搜索算法 B.廣度優(yōu)先搜索算法 C.求最小生成樹(shù)的prim算法 D.拓?fù)渑判蛩惴? 參考答案：B 15. 若進(jìn)棧序列為a，b，c，則通過(guò)入出棧操作可能得到的a，b，c的不同排列個(gè)數(shù)為( )。 A、4 B、5 C、6 D、7 參考答案：B 16. 二叉樹(shù)中必有度為2的結(jié)點(diǎn)。( ) A、錯(cuò)誤 B、正確 參考答案：A 17. 線性表是具有n個(gè)( )的有限序列。 A.字符 B.數(shù)據(jù)元素 C.

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

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

8、個(gè)單元，則元素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. 在最好和最壞情況下的時(shí)間復(fù)雜度均為O(nlogn)且穩(wěn)定的排序方法是堆排序。( ) A、錯(cuò)誤 B、正確 參考答案：A 26. 按排序過(guò)程中依據(jù)的原則分類，快速排序?qū)儆? )。 A.插入類的排序方法 B.選擇類的排序方法 C.交換類的排序方法 D.歸并

9、類的排序方法 參考答案：C 27. 某二叉樹(shù)的先序序列和后序序列正好相反，則該二叉樹(shù)的特點(diǎn)一定是( )。 A.空或只有一個(gè)結(jié)點(diǎn) B.高度等于其結(jié)點(diǎn)數(shù) C.任一結(jié)點(diǎn)無(wú)左孩子 D.任一結(jié)點(diǎn)無(wú)右孩子 參考答案：B 28. 對(duì)長(zhǎng)度為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.錯(cuò)誤 參考答案：A 30. 隊(duì)列允許在隊(duì)尾刪除，在隊(duì)頭插入。( ) A.正確 B.

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

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

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

13、接插入排序 C.快速排序 D.堆排序 參考答案：C 43. 最小生成樹(shù)問(wèn)題是構(gòu)造帶權(quán)連通圖(網(wǎng))的最小代價(jià)生成樹(shù)。( ) A.正確 B.錯(cuò)誤 參考答案：A 44. 對(duì)某二叉樹(shù)進(jìn)行前序遍歷的結(jié)果為ABDEFC，中序遍歷的結(jié)果為DBFEAC，則后序遍歷的結(jié)果為( ) A.DBFEAC B.DFEBCA C.BDFECA D.BDEFAC 參考答案：B 45. 數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)存儲(chǔ)器內(nèi)的表示，稱為數(shù)據(jù)的邏輯結(jié)構(gòu)。( ) A、錯(cuò)誤 B、正確 參考答案：A 46. 深度為h的滿m叉樹(shù)的第k層的結(jié)點(diǎn)(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”中，對(duì)模式串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是一個(gè)森林，B是由F轉(zhuǎn)換得到的二叉樹(shù)，F(xiàn)中有n個(gè)非葉結(jié)點(diǎn)，則B中右指針域?yàn)榭盏慕Y(jié)點(diǎn)有( ) A.n-1 B.n C.n+1 D.n+2 參考答案：B