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

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

1、西北工業(yè)大學21秋《數(shù)據(jù)結(jié)構(gòu)》復習考核試題庫答案參考 1. 在以單鏈表為存儲結(jié)構(gòu)的線性表中，數(shù)據(jù)元素之間的邏輯關系用( )。 A.數(shù)據(jù)元素的相鄰地址表示 B.數(shù)據(jù)元素在表中的序號表示 C.指向后繼元素的指針表示 D.數(shù)據(jù)元素的值表示 參考答案：C 2. 結(jié)構(gòu)的存儲密度定義為數(shù)據(jù)本身所占的存儲量與整個結(jié)構(gòu)所占的存儲量之比。( ) A.正確 B.錯誤 參考答案：A 3. 一個隊列的入隊序列是1、2、3、4，則隊列的首次輸出元素是( )。 A.1 B.2 C.3 D.4 參考答案：A 4. 隊列的隊尾位置通常是隨著入隊操

2、作而變化的。( ) A、錯誤 B、正確 參考答案：B 5. 設棧S和隊列Q的初始狀態(tài)為空，元素e1，e2，e3，e4，e5和e6依次通過棧S，一個元素出棧后即進隊列Q，若6個元素出隊的序列是e2，e4，e3，e6，e5，e1則棧S的容量至少應該是( )。 A.6 B.4 C.3 D.2 參考答案：C 6. 在指定結(jié)點之后插入新結(jié)點時，雙鏈表比單鏈表更方便。( ) A.正確 B.錯誤 參考答案：B 7. 最佳二叉排序樹是AVL樹(平衡二叉排序樹)。( ) A.正確 B.錯誤 參考答案：A 8. 在下列各種

3、文件中，不能進行順序查找的文件是( )。 A.順序文件 B.索引文件 C.散列文件 D.多重表文件 參考答案：C 9. 若進棧序列為1，2，3，4，5，6，且進棧和出?？梢源┎暹M行，則可能出現(xiàn)的出棧序列為( )。 A、3，2，6，1，4，5 B、3，4，2，1，6，5 C、1，2，5，3，4，6 D、5，6，4，2，3，1 參考答案：B 10. 如果在數(shù)據(jù)結(jié)構(gòu)中每個數(shù)據(jù)元素只可能有一個直接前驅(qū)，但可以有多個直接后繼，則該結(jié)構(gòu)是( )。 A.棧 B.隊列 C.樹 D.圖 參考答案：C 11. 設有100個關鍵字，用折半

4、查找法進行查找時，最大比較次數(shù)為( )。 A.7 B.6 C.50 D.25 參考答案：A 12. 設某算法的問題規(guī)模函數(shù)f(n)=300n2+8000n+900，則它的漸進時間復雜度為( ) A.O(n3) B.O(n2) C.O(n) D.O(1) 參考答案：B 13. 滿二叉樹一定是完全二叉樹，完全二叉樹不一定是滿二叉樹。( ) A.正確 B.錯誤 參考答案：A 14. 下列四種排序中( )的空間復雜度最大。 A.插入排序 B.冒泡排序 C.堆排序 D.歸并排序 參考答案：C 15. 可以用隊

5、列實現(xiàn)數(shù)值轉(zhuǎn)換算法。( ) A.正確 B.錯誤 參考答案：A 16. 若采用鄰接矩陣法存儲一個n個頂點的無向圖，則該鄰接矩陣是一個( )。 A.上三角矩陣 B.稀疏矩陣 C.對角矩陣 D.對稱矩陣 參考答案：D 17. 在一個單鏈表中，若刪除*p結(jié)點的后繼結(jié)點，則執(zhí)行操作( )。 A.q=p->next; p->next=q->next; free(q) B.p=p->next; p->next=p->next->next; free(p) C.p->next=q->next; free(p->next) D.p=p->next->ne

6、xt; free(p->next) 參考答案：A 18. 在存儲數(shù)據(jù)時，通常不僅要存儲各數(shù)據(jù)元素的值，而且還要存儲( )。 A.數(shù)據(jù)的處理方法 B.數(shù)據(jù)元素的類型 C.數(shù)據(jù)元素之間的關系 D.數(shù)據(jù)的存儲方法 參考答案：C 19. 數(shù)據(jù)結(jié)構(gòu)中的任一數(shù)據(jù)元素至多只有一個前驅(qū)和一個后繼，該數(shù)據(jù)結(jié)構(gòu)是( )。 A.線性表 B.樹形結(jié)構(gòu) C.廣義表 D.圖結(jié)構(gòu) 參考答案：A 20. 在數(shù)據(jù)結(jié)構(gòu)中，數(shù)據(jù)的邏輯結(jié)構(gòu)可以分成( )。 A、內(nèi)部結(jié)構(gòu)和外部結(jié)構(gòu) B、線性結(jié)構(gòu)和非線性結(jié)構(gòu) C、緊湊結(jié)構(gòu)和非緊揍結(jié)構(gòu) D、動態(tài)結(jié)構(gòu)和靜態(tài)結(jié)構(gòu)

7、 參考答案：C 21. 引入二叉線索樹的目的是( )。 A.加快查找結(jié)點的前驅(qū)或后繼的速度 B.使二叉樹的遍歷結(jié)果唯一 C.為了能方便的找到雙親 D.為了能在二叉樹中方便的進行插入與刪除 參考答案：A 22. 向二叉搜索樹中插入一個元素時，其時間復雜度大致為( ) A.O(log2n) B.O(n) C.O(1) D.O(2n) 參考答案：A 23. 下面說法錯誤的是( )。 (1)算法原地工作的含義是指不需要任何額外的輔助空間; (2)在相同的規(guī)模n下，復雜度O(n)的算法在時間上總是優(yōu)于復雜度O(2n)的算法; (3)所謂

8、時間復雜度是指最壞情況下，估算算法執(zhí)行時間的一個上界; (4)同一個算法，實現(xiàn)語言的級別越高，執(zhí)行效率就越低。 A.(1) B.(1)，(2) C.(1)，(4) D.(3) 參考答案：C 24. 設根結(jié)點層次為1，某二叉樹的結(jié)點前序序列和后序序列正好相反，則該二叉樹一定是( )。 A.高度等于其結(jié)點數(shù) B.空或只有一個結(jié)點 C.任一結(jié)點無左子女 D.任一結(jié)點無右子女 參考答案：A 25. 取順序表的第i個元素的時間與i的大小無關。( ) A.正確 B.錯誤 參考答案：A 26. 隊列的修改是按先進先出的原則進行的。(

9、) A、錯誤 B、正確 參考答案：B 27. 用DFS遍歷一個無環(huán)有向圖，并在DFS算法退棧返回時打印相應的頂點，則輸出的頂點序列是( )。 A.逆拓撲有序 B.拓撲有序 C.無序的 D.A和B 參考答案：A 28. 一組記錄的關鍵字經(jīng)一趟二路歸并排序后得到含有5個長度為2的有序表如下：[25，48]，[16，35]，[79，82]，[23，40]，[36，72]，在此基礎上按二路歸并排序方法再對該序列進行一趟歸并后的結(jié)果為( ) A.16，25，35，48，23，40，79，82，36，72 B.16，25，35，48，23，40，79，8

10、2，72，36 C.16，25，48，35，79，82，23，36，40，72 D.16，25，35，48，79，23，36，40，72，82 參考答案：D 29. 線性表中的所有元素都有一個前驅(qū)元素和后繼元素。( ) A.正確 B.錯誤 參考答案：A 30. 如果最常用的操作是取第i個結(jié)點及其前驅(qū)，則采用( )存儲方式最節(jié)省時間。 A.單鏈表 B.雙鏈表 C.單循環(huán)鏈表 D.順序表 參考答案：D 31. 在任意一棵二叉樹的前序序列和后序序列中，各葉子之間的相對次序關系( )。 A.不一定相同 B.都相同 C.都不相同

11、 D.互為逆序 參考答案：B 32. 在圖G的最小生成樹T中，可能會有某條邊的權(quán)值超過未選邊的權(quán)值。( ) A.正確 B.錯誤 參考答案：A 33. 用有向無環(huán)圖描述表達式(A+B)*(A+B)/A)，至少需要頂點的數(shù)目為( )。 A.5 B.6 C.8 D.9 參考答案：A 34. 無向圖的鄰接矩陣可用一維數(shù)組存儲。( ) A.正確 B.錯誤 參考答案：A 35. 二叉樹中的葉子結(jié)點就是二叉樹中沒有左右子樹的結(jié)點。( ) A、錯誤 B、正確 參考答案：B 36. 向一個有127個元素

12、原順序表中插入一個新元素并保存原來順序不變，平均要移動( )個元素。 A.8 B.63.5 C.63 D.7 參考答案：B 37. 若用n表示圖中頂點數(shù)目，則有( )條邊的無向圖成為完全圖。 A.n B.n-1 C.n(n-1)2 D.n(n+1)2 參考答案：C 38. 已知一個散列表如圖所示，其散列函數(shù)為H(key)=key%11，采用二次探查法處理沖突，則下一個插入的關鍵字49的地址為( )。 A.2 B.3 C.8 D.9 參考答案：C 39. 用鏈表表示線性表的優(yōu)點是( ) A.便于隨機存取 B.花費

13、的存儲空間比順序表少 C.便于插入與刪除 D.數(shù)據(jù)元素的物理順序與邏輯順序相同 參考答案：C 40. 在鏈表的結(jié)點中，數(shù)據(jù)元素所占的存儲量和整個結(jié)點所占的存儲量之比稱作存儲密度。( ) A、錯誤 B、正確 參考答案：B 41. 若查找每個記錄的概率均等，則在具有n個記錄的連續(xù)順序文件中采用順序查找法查找一個記錄，其平均查找長度ASL為( )。 A.(n-1)2 B.n2 C.(n+1)2 D.n 參考答案：C 42. 在有向圖中，以頂點v為終點的邊的數(shù)目稱為v的入度。( ) A、錯誤 B、正確 參考答案：B

14、 43. 以下關于線性表的說法不正確的是( )。 A.線性表中的數(shù)據(jù)元素可以是數(shù)字、字符、記錄等不同類型 B.線性表中包含的數(shù)據(jù)元素個數(shù)不是任意的 C.線性表中的每個結(jié)點都有且只有一個直接前趨和直接后繼 D.存在這樣的線性表：表中各結(jié)點都沒有直接前趨和直接后繼 參考答案：C 44. 按層次次序?qū)⒁活w有n個結(jié)點的完全二叉樹的所有結(jié)點從1到n編號，當iA.2i-1 B.2i C.2i+1 D.不確定 參考答案：B 45. 散列函數(shù)有一個共同的性質(zhì)，即函數(shù)值應當以下面的哪一項來取其值域的每個值?( ) A.最小概率 B.最大概率 C.平均概率

15、 D.同等概率 參考答案：D 46. 已知循環(huán)隊列的存儲空間為數(shù)組data[21]，且當前隊列的頭指針和尾指針的值分別為8和3，則該隊列的當前長度為( )。 A.5 B.6 C.16 D.17 參考答案：C 47. 在圖采用鄰接表存儲時，求最小生成樹的Prim算法的時間復雜度為( )。 A.O(n) B.O(n+e) C.O(n2) D.O(n3) 參考答案：B 48. 鏈式棧與順序棧相比，一個比較明顯的優(yōu)點是( ) A.插入操作更加方便 B.通常不會出現(xiàn)棧滿的情況 C.不會出現(xiàn)棧空的情況 D.刪除操作更加方便 參考答案：B 49. 算法分析的兩個主要方面是( )。 A.空間復雜度和時間復雜度 B.正確性和簡明性 C.可讀性和文檔性 D.數(shù)據(jù)復雜性和程序復雜性 參考答案：A 50. 向順序棧中壓入新元素時，應當( ) A.先移動棧頂位置，再存入元素 B.先存入元素，再移動棧頂位置 C.先后 次序無關緊要 D.同時進行 參考答案：A