自考02142《數(shù)據(jù)結(jié)構(gòu)導(dǎo)論》真題（2022.4）-2

精品文檔-下載后可編輯自考02142《數(shù)據(jù)結(jié)構(gòu)導(dǎo)論》真題及（2022.4）自考02142《數(shù)據(jù)結(jié)構(gòu)導(dǎo)論》真題及答案解析（2022.4）

1.[單選題]下列幾種時間復(fù)雜度中，階數(shù)最小的是（）

A.O(log2n)

B.O(n)

C.O(n2)

D.O(1)

2.[單選題]棧和隊列的共同特點是（）

A.都是線性表

B.先進(jìn)先出

C.后進(jìn)先出

D.只能插入操作

3.[單選題]假設(shè)一個10x10的上三角矩陣A按照列優(yōu)先順序壓縮在一維數(shù)組B中，則B數(shù)組的大小應(yīng)為（）

A.50

B.55

C.100

D.101

4.[單選題]一個棧的入棧序列是a，b，c，d，e，則棧可能的輸出序列是（）

A.edcab

B.deabc

C.abcde

D.dceab

5.[單選題]假定一個順序存儲的循環(huán)隊列的隊頭和隊尾指針分別為f和r，則判斷隊空的條件為（）

A.f==NULL

B.f==r

C.r+1==f

D.f+1==r

6.[單選題]如果結(jié)點A有2個兄弟結(jié)點，結(jié)點B為A的雙親，則結(jié)點B的度為（）

A.2

B.3

C.4

D.5

7.[單選題]二叉樹的中序遍歷中，結(jié)點P排在結(jié)點Q之前的條件是在二叉樹中（）

A.P在Q的左邊

B.P在Q的右邊

C.P是Q的祖先

D.P是Q的子孫

8.[單選題]二又樹的第k層的結(jié)點數(shù)最多為（）

A.2k-1

B.2k+1

C.2k-1

D.2k+1

9.[單選題]A是7X4的二維數(shù)組，按行優(yōu)先方式順序存儲元素A[0][0]的存儲地址為1000，若每個元素占2個字節(jié)，則元素A[3][3]的存儲地址為（）

A.1026

B.1028

C.1030

D.1032

10.[單選題]在表長為n的順序表上做刪除運算，其平均時間復(fù)雜度為（）

A.O(1)

B.O(n)

C.O(nlog2n)

D.O(n/2)

11.[單選題]在含n個頂點和e條邊的無向圖的鄰接矩陣中，零元素的個數(shù)為（）

A.e

B.2e

C.n2-e

D.n2-2e

12.[單選題]設(shè)順序表的長度為n，則插入算法的平均移動次數(shù)約為（）

A.n

B.n/2

C.n-1

D.(n-1)/2

13.[單選題]設(shè)一組初始記錄關(guān)鍵字序列為(13，18，24，35，47，50，62，83，90，115，134)，則用二分查找算法查找關(guān)鍵字90需要比較的關(guān)鍵字個數(shù)為（）

A.1

B.2

C.3

D.4

14.[單選題]以下排序方法中，穩(wěn)定的是（）

A.直接插入排序和快速排序

B.快速排序和冒泡排序

C.直接選擇排序和冒泡排序

D.冒泡排序和直接插入排序

15.[單選題]對n個記錄的文件進(jìn)行快速排序，所需要的輔助存儲空間的空間復(fù)雜度為（）

A.O(1)

B.O(n)

C.O(1og2n)

D.O(n2)

16.[填空題]1976年瑞士計算機科學(xué)家NiklausWirth曾提出一個著名公式：程序=數(shù)據(jù)結(jié)構(gòu)+____。

17.[填空題]簡單地說，數(shù)據(jù)結(jié)構(gòu)是計算機____數(shù)據(jù)和存儲數(shù)據(jù)的方式。

18.[填空題]線性表中結(jié)點個數(shù)n稱為____。

19.[填空題]線性表上的插入和刪除運算限定在表的某一端進(jìn)行的數(shù)損結(jié)構(gòu)是____。

20.[填空題]對稀疏矩陣進(jìn)行壓縮存儲的目的是節(jié)省____。

21.[填空題]一個具有n個頂點的有向完全圖的弧數(shù)為=____.

22.[填空題]構(gòu)造最小生成樹的算法有兩種:Prim算法和____算法。

23.[填空題]一棵樹的結(jié)點個數(shù)最少為____。

24.[填空題]有K個葉子結(jié)點的哈夫曼樹，其結(jié)點的總數(shù)為____。

25.[填空題]由二又樹的后序序列和____序列，可以唯一確定一棵二又樹。

26.[填空題]二分查找算法的平均時間復(fù)雜度為____。

27.[填空題]若待排序的序列中存在多個記錄具有相同的健值，經(jīng)過排序，這些記錄的相對次序仍然保持不變，則稱這種排序方法是____的。

28.[填空題]在最壞情況下，即對幾乎已是排好序的輸入序列，快速排序算法的效率較低，此時其時間復(fù)雜度近似為____。

29.[案例題]有一個整數(shù)序列。其輸入順序為20，30，90，-10，45，78，試?yán)脳⑵漭敵鲂蛄懈淖優(yōu)?0，-10，45，90，78，20，寫出該整數(shù)序列進(jìn)棧和出棧的操作步驟。（用push(x)表示x進(jìn)棧，pop(x)表示x出棧）

30.[案例題]分別寫出題30圖所示的二叉樹的先序遍歷、中序遍歷和后序遍歷三種訪問方式的結(jié)點訪問序列。

31.[案例題]設(shè)有字符集{A，B，C，D，E，F(xiàn))，各字符使用頻率對應(yīng)為(2，4，5，13，9，18)，試畫出哈夫曼樹（要求任一結(jié)點的左孩子權(quán)值小于右孩子）。

32.[案例題]已知散列表的長度為11，散列函數(shù)H(key)=key%11，采用線性探測法解決沖突，試用關(guān)鍵字值的序列：75，25，80，35，60，46，50，55建立散列表。

33.[案例題]試用冒泡法對數(shù)列(45，73，12，23，52，5，38)進(jìn)行遞增排序，