?數據結構導論2015年4月真題（02142）

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

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

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

1.設某個算法的計算量是問題規模n的函數：T(n)=anc+blog2n+cn+d，則該算法的時間復度可表示成(　　)

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

2.將長度為n的單鏈表鏈接在長度為m的單鏈表之后的算法時間復雜度為(　　)

A.O(n)
B.O(m)
C.O(n+m)
D.O(n×m)

3.為解決計算機與打印機之間速度不匹配的問題，通常設置一個打印數據緩沖區，主機將要輸出的數據依次寫入該緩沖區，而打印機則依次從該緩沖區中取出數據。該緩沖區的邏輯結構應該是(　　)

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

4.對于n(n≥0)個元素構成的線性表L，適合采用鏈式存儲結構的操作是(　　)

A.需要頻繁修改L中元素的值
B.需要頻繁地對L進行隨機查找
C.需要頻繁地對L進行插入和刪除操作
D.要求L存儲密度高

5.判斷一個帶有頭結點的鏈隊列為空隊列Q的條件是(　　)

A.Q.front==NULL
B.Q.front==Q.rear
C.Q.front!=Q.rear
D.Q.rear==NULL

6.在一個單鏈表中，已知指針q指向指針p所指結點的前驅結點，則刪除* p結點的操作語句是(　　)

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

7.把特殊矩陣A[10][10]的下三角矩陣壓縮存儲到一個一維數組M中，則A中元素a[4][3]在M中所對應的下標位置是(　　)

A.8
B.12
C.13
D.55

8.若一棵具有n(n>0)個結點的二叉樹的先序序列與后序序列正好相反，則該二叉樹一定是(　　)

A.結點均無左孩子的二叉樹
B.結點均無右孩子的二叉樹
C.存在度為2的結點的二叉樹
D.高度為n的二叉樹

9.對關鍵字序列{0，2，4，8，16，32，64，128}進行二分查找，則第一個被查找到的關鍵字是(　　)

A.0
B.8
C.16
D.128

10.已知一個圖如題10圖所示，若從頂點a出發進行廣度優先遍歷，則可能得到的廣度優先搜索(　　)

A.acefbd
B.acbdfe
C.acbdef
D.acdbfe

11.若某二叉樹按后序遍歷得到的結果為c、b、a，則可以得到該結果的二叉樹有(　　)

A.1種
B.2種
C.3種
D.5種

12.下列有關哈夫曼(Huffman)樹的描述，不正確的是(　　)

A.哈夫曼樹的樹形唯一，且其WPL值最小
B.哈夫曼樹的樹形不一定唯一，但其WPL值最小且相等
C.哈夫曼字符編碼不一定唯一，但總碼長最短
D.哈夫曼樹沒有嚴格要求區別左右子樹權重次序

13.能夠使用二分查找算法進行查找的條件是必須以(　　)

A.順序方式存儲，且元素按關鍵字有序
B.鏈式方式存儲，且元素按關鍵字有序
C.順序方式存儲，且元素按關鍵字無序
D.鏈式方式存儲，且元素按關鍵字無序

14.下列排序方法中不穩定的是(　　)

A.直接插入排序
B.堆排序
C.冒泡排序
D.二路歸并排序

15.對于n個元素的關鍵字序列{k₁，k₂….，k_n)，當且僅當滿足關系k_i≤k_2i且ki≤k_2i+1(2i≤n，2i+1≤n)稱其為最小堆，反之則為最大堆。以下序列中不符合最小堆或最大堆定義的是(　　)

A.{4，10，15，72，39，23，18}
B.{58，27，36，12，8，23，9}
C.{4，10，18，72，39，23，15}
D.{58，36，27，12，8，23，9}

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

11.數據結構研究的主要內容包括數據的邏輯結構、______、以及對數據及其關系的操作運算。

12.根據數據元素之間的關系，通常有四類基本的邏輯結構：集合、線性結構、樹形結構、______.

13.在表長為n的順序表中插入一個數據元素，平均需要移動約______個數據元素。

14.設有二維數組A[8][ 10]，按行序優先存儲，且每個元素占用2個存儲單元，若第一個元素的存儲起始位置為b，則存儲位置為b+20處的元素為______。

15.棧的特點是先進后出或后進先出，隊列的特點是______。

16.若一棵二叉樹中度為1和度為2的結點個數均是3，則該二叉樹葉子結點的個數是_____.

17.高度(深度)為h的完全二叉樹最少的結點個數是______。

18.根據圖的定義，圖中頂點的最少數目是______。

19.高度為3、含有5個結點(編號1～5)的二叉樹，其順序存儲結構為，則編號為4的結點的雙親結點的編號為______。

110.對如題25圖所示的含有3棵樹的森林進行先序遍歷，得到的結果序列是______。

111.按關鍵字的輸入序列{30，22，42，7，25}所生成的二又排序樹中，其左子樹上的關鍵字有______。

112.插入、選擇、冒泡及堆等四種排序方法在各自排序過程中其鍵值比較的次數與數據元素的初始排列次序無關的有______和堆排序。

113.用冒泡排序算法對n個帶有鍵值的數據元素進行排序，排序結束后所可能歷經的最少趟數為______。

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

21.字符a.b、c、d依次通過一個棧，按出棧的先后次序組成字符串，至多可以組成多少個不同的字符串?并分別寫出它們。

22.已知某棵二叉樹的先序遍歷和中序遍歷的結果序列分別為ABCDEFGHI和BCAEDGHFI。試構造出該二叉樹，并給出該二叉樹的后序遍歷結果序列。

23.帶權圖(權值非負，表示邊連接的兩頂點間的距離)的最短路徑問題是找出從初始頂點到目標頂點之間的一條最短路徑。假定從初始頂點到目標頂點之間存在路徑，現有一種解決該問題的方法：①設最短路徑初始時僅包含初始頂點，令當前頂點u為初始頂點;②選擇離u最近且尚未在最短路徑中的一個頂點v，加入到最短路徑中，修改當前頂點u=v;③重復步驟②，直到u是目標頂點時為止。現問上述方法能否求得最短路徑?若該方法可行，試證明之;否則，舉例說明。

24.將關鍵字序列{7，8，30，11，18，9，14}散列存儲到一個散列表中，設該散列表的存儲空間是一個下標從0開始、大小(HashSize)為10的一維數組，散列函數為H(key)=(key×3)MOD HashSize，處理沖突采用線性探測法。現要求：(1)畫出所構造的散列表;(2)計算出等概率情況下查找成功的平均查找長度。

25.若采用冒泡排序方法對關鍵字序列{265，301，751，129，937，863，742，694，076，438}進行升序排序，寫出其每趟排序結束后的關鍵字序列。

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

31.寫出一個將線性表的順序表存儲方式(數組a、表長為n)改成單鏈表存儲方式(其頭結點由頭指針head指向)的算法。設函數頭為：Node * CreateLinkedList(DataType a[], int n)

32.統計出一棵二叉樹中結點數據域的值不小于m的所有結點個數。設二叉樹的存儲結構為：typedef struct btnode{      int data;      struct btnode *lchild, *rchile;}BTNode, *BTree;