?數據結構導論2016年10月真題（02142）

數據結構導論2016年10月真題及答案解析（02142）

數據結構導論2016年10月真題及答案解析（02142），該試卷為數據結構導論自考歷年真題試卷，包含答案及詳細解析。

一、單項選擇題(本大題共10小題，每小題2分，共30分)在每小題列出的四個備選項中只有一個是符合題目要求的，請將其選出并將“答題卡”的相應代碼涂黑。錯涂、多涂或未涂均無分。

1.已知問題規(guī)模為n，則下列程序片段的時間復雜度是(　　)i=1; j=0;while(i+j<=n) i="">j) j++; else i++; }

A.O(n^C)
B.O(log₂n)
C.O(n)
D.O(2n)

2.若用計算機來模擬銀行客戶排隊等待辦理業(yè)務的情形，則所應該采用的數據結構是(　　)

A.棧
B.隊列
C.樹
D.圖

3.若線性表采用鏈式存儲結構，則適用的查找方法為(　　)

A.隨機查找
B.散列查找
C.二分查找
D.順序查找

4.已知指針p和q分別指向某單鏈表中第一個結點和最后一個結點，假設指針s指向另一個單鏈表中某個結點，則在s所指結點之后插入上述單鏈表應執(zhí)行的語句為(　　)

A.q->next=s->next; s->next=p;
B.s->next=P; q->next=s->next;
C.p->next=s->next; s->next=q;
D.s->next=q; p->next=s->next;

5.棧的運算特點是先進后出，元素a、b、c、d依次入棧，則不能得到的出棧序列是(　　)

A.abcd
B.dcba
C.cabd
D.bcda

6.在實現隊列的鏈表結構中，其時間復雜度最優(yōu)的是(　　)

A.僅設置頭指針的單循環(huán)鏈表
B.僅設置尾指針的單循環(huán)鏈表
C.僅設置頭指針的雙向鏈表
D.僅設置尾指針的雙向鏈表

7.任意一棵二叉樹的前序和后序遍歷的結果序列中，各葉子結點之間的相對次序關系是(　　)

A.不一定相同
B.都相同
C.都不相同
D.互為逆序

8.若某棵樹的存儲結構采用雙親表示法，如題8圖所示，則該樹的高度是(　　)

A.2
B.3
C.4
D.5

9.無向圖的鄰接矩陣一定是(　　)

A.對稱矩陣
B.對角矩陣
C.稀疏矩陣
D.三角矩陣

10.根據連通圖的深度優(yōu)先搜索的基本思想，如題10圖所示的連通圖的一個深度優(yōu)先搜索的結果序列是(　　)

A.123456
B.123465
C.126345
D.162543

11.用順序查找方法對含有n個數據元素的順序表按從后向前查找次序進行查找，現假設查找其中每個數據元素的概率不相等，那么(　　)

A.該順序表按查找概率由低到高的順序來存儲數據元素，其ASL最小
B.該順序表按查找概率由高到低的順序來存儲數據元素，其ASL最小
C.ASL的大小與數據元素在該順序表中的位置次序無關
D.ASL的大小與查找每個數據元素的概率無關

12.已知散列表的存儲空間為T[0，…，16]，散列函數為H(k)=k mod 17，用二次探測法解決沖突。散列表中已插入下列關鍵字：T[5]=39、T[6]=57和T[7]=7，則下一個關鍵字值23在該散列表中插入的位置是(　　)

A.T[2]
B.T[4]
C.T[8]
D.T[10]

13.對關鍵字序列{eSC，tab，ah，con，brk，del}進行排序時，若關鍵字序列的變化情況如下;①esc，tab，ah，con，brk，del ②ah，tab，eSC，con，brk，del ③alt，brk，esc，con，tab，del ④alt，brk，con，esc，tab，del ⑤ah，brk，con，del，tab，esc ⑥ah，brk，con，del，esc，tab。則所用的排序方法是(　　)

A.直接插入排序
B.直接選擇排序
C.堆排序
D.冒泡排序

14.滿足最小堆定義的是(　　)

A.{21，25，55，23，51，63}
B.{21，51，55，63，25，23}
C.{21，63，55，25，51，23}
D.{21，51，23，63，55，25}

15.設有兩個長度分別為m、n的降序有序序列{a₁，a₂，…，a_m}、{b₁，b₂，…，b_n}，采用二路歸并方法將它們合并成長度為m+12的降序有序序列，則歸并過程中元素比較次數最少的條件一定是(　　)

A.a₁>b₁
B.a_m>b_n
C.a₁<b_n
D.a_m<b₁

二、填空題(本大題共13小題，每小題2分，共26分)

11.從宏觀上看，數據、數據元素和______ 反映了數據組織的三個層次。

12.在表長為n的順序表中插入或刪除一個元素，則需移動元素的具體個數與表長和____有關。

13.非空的單循環(huán)鏈表的頭指針為head，尾指針為rear，則rear->next=_______。

14.設以數組Q[m]存放循環(huán)隊列的元素，變量rear和queuelen分別表示循環(huán)隊列中隊尾元素的下標位置和元素的個數。則計算該隊列中隊頭元素下標位置的公式是________。

15.二維數組A[8][9]按行優(yōu)先順序存儲，若數組元素A[2][3]的存儲地址為1087，A[4][7]的存儲地址為1153，則每個數組元素占用的存儲單元的個數是________。

16.設一個完全二叉樹共含有196個結點，則該完全二叉樹中含有葉結點的個數是________。

17.假設高度為h二叉樹中只有度為2和度為0這兩種類型的結點，則該類二叉樹中結點個數至多為2^h-1、至少為________。

18.若以數據集{34，5，12，23，8，18}為葉結點的權值構造一棵哈夫曼(HUffman)樹，那么該Huffman樹的帶權路徑長度WPL______。

19.設有散列函數H(k)和鍵值k₁、k₂(k₁≠k₂)，若H(k₁)=H (k₂)，則這種現象稱為“沖突”，且稱鍵值k₁和k₂互為______。

110.一個圖的最小生成樹是滿足一定條件的生成樹，即一個圖的最小生成樹是指該圖的所有生成樹中______的生成樹。

111.對長度為n的有序順序表進行二分查找，則查找表中的任意一個元素時，無論查找成功與失敗，最多與表中______個元素進行比較。

112.排序方法中，從未排序序列中依次取出元素與已排序序列(初始時為空)中的元素按序進行比較，將其插入已排序序列的正確位置上的方法稱為______。

113.一般情況下，時闖復雜度是O(nlog₂n)且其空間復雜度最優(yōu)的排序方法是______。

三、應用題(本大題共5小題，每小題6分，共30分)

21.借助于隊列能夠將含有n個數據元素的棧逆置，比如棧S中的元素為{a，b，C}逆置后變成{C，b，a}。試簡述你的解決方案。

22.為便于表示二叉樹的某些基本運算，則深度為k.的二叉樹的順序存儲結構中的數組的大小為多少?畫出如題30圖所示的二叉樹的順序存儲結構示意圖，并說明對一般形態(tài)的二叉樹不太適合使用順序存儲結構來表示的原因。

23.先序遍歷、中序遍歷一個森林分別等同于先序、中序遍歷該森林所對應的二叉樹?，F已知一個森林的先序序列和中序序列分別為ABCDEFIGJH和BDCAIFJGHE，試畫出該森林。

24.設有一組關鍵字值序列{e，b，d，f，a，g，C}現要求：(1)根據二叉排序樹的創(chuàng)建方法構造出相應的二叉排序樹(關鍵字值的大小按字母表順序計);(2)計算等概率情況下在該二叉排序樹上查找成功的平均查找長度ASL。

25.若采用二路歸并排序方法對關鍵字序列{25，9，78，6，65，15，58，18，45，20}進行升序排序，寫出其每趟排序結束后的關鍵字序列。

四、算法設計題(本大題共2小題，每小題7分，共14分)

31.某電商有關手機的庫存信息，按其價格從低到高存儲在一個帶有頭結點的單循環(huán)鏈表中，鏈表中的結點由品牌型號(nametype)、價格(price)、數量(quantity)和指針(next)四個域組成?，F新到in臺、價格為c、品牌型號為x的新款手機需入庫，寫出相應的存儲結構和實現該要求的算法。

32.寫出向存儲結構為鄰接矩陣的無向圖G中插入一條邊(x,y)的算法。算法的頭函數為： void AddEdgetoGraph(Graph*G, VertexType X, VertexType y>，無向圖G的存儲結構為：#define MaxVertex numtypedef char VertexType;typedef int EdgeType;typedef struct graph{   int n, e;     //圖的實際頂點數和邊數   EdgeType edge[MaxVertex][MaxVertex];   VertexType vertex[MaxVertex];    //頂點表}Graph;