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

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

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

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

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

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

5、列實(shí)現(xiàn)數(shù)值轉(zhuǎn)換算法。( ) A.正確 B.錯(cuò)誤 參考答案：A 16. 若采用鄰接矩陣法存儲一個(gè)n個(gè)頂點(diǎn)的無向圖，則該鄰接矩陣是一個(gè)( )。 A.上三角矩陣 B.稀疏矩陣 C.對角矩陣 D.對稱矩陣 參考答案：D 17. 在一個(gè)單鏈表中，若刪除*p結(jié)點(diǎn)的后繼結(jié)點(diǎn)，則執(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í)，通常不僅要存儲各數(shù)據(jù)元素的值，而且還要存儲( )。 A.數(shù)據(jù)的處理方法 B.數(shù)據(jù)元素的類型 C.數(shù)據(jù)元素之間的關(guān)系 D.數(shù)據(jù)的存儲方法 參考答案：C 19. 數(shù)據(jù)結(jié)構(gòu)中的任一數(shù)據(jù)元素至多只有一個(gè)前驅(qū)和一個(gè)后繼，該數(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é)點(diǎn)的前驅(qū)或后繼的速度 B.使二叉樹的遍歷結(jié)果唯一 C.為了能方便的找到雙親 D.為了能在二叉樹中方便的進(jìn)行插入與刪除 參考答案：A 22. 向二叉搜索樹中插入一個(gè)元素時(shí)，其時(shí)間復(fù)雜度大致為( ) A.O(log2n) B.O(n) C.O(1) D.O(2n) 參考答案：A 23. 下面說法錯(cuò)誤的是( )。 (1)算法原地工作的含義是指不需要任何額外的輔助空間; (2)在相同的規(guī)模n下，復(fù)雜度O(n)的算法在時(shí)間上總是優(yōu)于復(fù)雜度O(2n)的算法; (3)所謂

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

9、) A、錯(cuò)誤 B、正確 參考答案：B 27. 用DFS遍歷一個(gè)無環(huán)有向圖，并在DFS算法退棧返回時(shí)打印相應(yīng)的頂點(diǎn)，則輸出的頂點(diǎn)序列是( )。 A.逆拓?fù)溆行? B.拓?fù)溆行? C.無序的 D.A和B 參考答案：A 28. 一組記錄的關(guān)鍵字經(jīng)一趟二路歸并排序后得到含有5個(gè)長度為2的有序表如下：[25，48]，[16，35]，[79，82]，[23，40]，[36，72]，在此基礎(chǔ)上按二路歸并排序方法再對該序列進(jìn)行一趟歸并后的結(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. 線性表中的所有元素都有一個(gè)前驅(qū)元素和后繼元素。( ) A.正確 B.錯(cuò)誤 參考答案：A 30. 如果最常用的操作是取第i個(gè)結(jié)點(diǎn)及其前驅(qū)，則采用( )存儲方式最節(jié)省時(shí)間。 A.單鏈表 B.雙鏈表 C.單循環(huán)鏈表 D.順序表 參考答案：D 31. 在任意一棵二叉樹的前序序列和后序序列中，各葉子之間的相對次序關(guān)系( )。 A.不一定相同 B.都相同 C.都不相同

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

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

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

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

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