數(shù)據(jù)結(jié)構(gòu)導(dǎo)論2015年4月真題及答案解析（02142）

數(shù)據(jù)結(jié)構(gòu)導(dǎo)論2015年4月真題及答案解析（02142），該試卷為數(shù)據(jù)結(jié)構(gòu)導(dǎo)論自考?xì)v年真題試卷，包含答案及詳細(xì)解析。

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

1.設(shè)某個(gè)算法的計(jì)算量是問題規(guī)模n的函數(shù)：T(n)=anc+blog2n+cn+d，則該算法的時(shí)間復(fù)度可表示成(　　)

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

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

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

3.為解決計(jì)算機(jī)與打印機(jī)之間速度不匹配的問題，通常設(shè)置一個(gè)打印數(shù)據(jù)緩沖區(qū)，主機(jī)將要輸出的數(shù)據(jù)依次寫入該緩沖區(qū)，而打印機(jī)則依次從該緩沖區(qū)中取出數(shù)據(jù)。該緩沖區(qū)的邏輯結(jié)構(gòu)應(yīng)該是(　　)

A.棧
B.隊(duì)列
C.樹
D.圖

4.對于n(n≥0)個(gè)元素構(gòu)成的線性表L，適合采用鏈?zhǔn)酱鎯Y(jié)構(gòu)的操作是(　　)

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

5.判斷一個(gè)帶有頭結(jié)點(diǎn)的鏈隊(duì)列為空隊(duì)列Q的條件是(　　)

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

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

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

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

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

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

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

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

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

10.已知一個(gè)圖如題10圖所示，若從頂點(diǎn)a出發(fā)進(jìn)行廣度優(yōu)先遍歷，則可能得到的廣度優(yōu)先搜索(　　)

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

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

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

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

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

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

A.順序方式存儲，且元素按關(guān)鍵字有序
B.鏈?zhǔn)椒绞酱鎯Γ以匕搓P(guān)鍵字有序
C.順序方式存儲，且元素按關(guān)鍵字無序
D.鏈?zhǔn)椒绞酱鎯Γ以匕搓P(guān)鍵字無序

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

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

15.對于n個(gè)元素的關(guān)鍵字序列{k₁，k₂….，k_n)，當(dāng)且僅當(dāng)滿足關(guā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.數(shù)據(jù)結(jié)構(gòu)研究的主要內(nèi)容包括數(shù)據(jù)的邏輯結(jié)構(gòu)、______、以及對數(shù)據(jù)及其關(guān)系的操作運(yùn)算。

12.根據(jù)數(shù)據(jù)元素之間的關(guān)系，通常有四類基本的邏輯結(jié)構(gòu)：集合、線性結(jié)構(gòu)、樹形結(jié)構(gòu)、______.

13.在表長為n的順序表中插入一個(gè)數(shù)據(jù)元素，平均需要移動(dòng)約______個(gè)數(shù)據(jù)元素。

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

15.棧的特點(diǎn)是先進(jìn)后出或后進(jìn)先出，隊(duì)列的特點(diǎn)是______。

16.若一棵二叉樹中度為1和度為2的結(jié)點(diǎn)個(gè)數(shù)均是3，則該二叉樹葉子結(jié)點(diǎn)的個(gè)數(shù)是_____.

17.高度(深度)為h的完全二叉樹最少的結(jié)點(diǎn)個(gè)數(shù)是______。

18.根據(jù)圖的定義，圖中頂點(diǎn)的最少數(shù)目是______。

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

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

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

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

113.用冒泡排序算法對n個(gè)帶有鍵值的數(shù)據(jù)元素進(jìn)行排序，排序結(jié)束后所可能歷經(jīng)的最少趟數(shù)為______。

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

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

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

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

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

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

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

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

32.統(tǒng)計(jì)出一棵二叉樹中結(jié)點(diǎn)數(shù)據(jù)域的值不小于m的所有結(jié)點(diǎn)個(gè)數(shù)。設(shè)二叉樹的存儲結(jié)構(gòu)為：typedef struct btnode{      int data;      struct btnode *lchild, *rchile;}BTNode, *BTree;