?數(shù)據(jù)結(jié)構(gòu)導(dǎo)論2016年10月真題（02142）

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

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

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

1.已知問題規(guī)模為n，則下列程序片段的時(shí)間復(fù)雜度是(　　)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.若用計(jì)算機(jī)來模擬銀行客戶排隊(duì)等待辦理業(yè)務(wù)的情形，則所應(yīng)該采用的數(shù)據(jù)結(jié)構(gòu)是(　　)

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

3.若線性表采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，則適用的查找方法為(　　)

A.隨機(jī)查找
B.散列查找
C.二分查找
D.順序查找

4.已知指針p和q分別指向某單鏈表中第一個(gè)結(jié)點(diǎn)和最后一個(gè)結(jié)點(diǎn)，假設(shè)指針s指向另一個(gè)單鏈表中某個(gè)結(jié)點(diǎn)，則在s所指結(jié)點(diǎn)之后插入上述單鏈表應(yīng)執(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.棧的運(yùn)算特點(diǎn)是先進(jìn)后出，元素a、b、c、d依次入棧，則不能得到的出棧序列是(　　)

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

6.在實(shí)現(xiàn)隊(duì)列的鏈表結(jié)構(gòu)中，其時(shí)間復(fù)雜度最優(yōu)的是(　　)

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

7.任意一棵二叉樹的前序和后序遍歷的結(jié)果序列中，各葉子結(jié)點(diǎn)之間的相對(duì)次序關(guān)系是(　　)

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

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

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

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

A.對(duì)稱矩陣
B.對(duì)角矩陣
C.稀疏矩陣
D.三角矩陣

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

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

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

A.該順序表按查找概率由低到高的順序來存儲(chǔ)數(shù)據(jù)元素，其ASL最小
B.該順序表按查找概率由高到低的順序來存儲(chǔ)數(shù)據(jù)元素，其ASL最小
C.ASL的大小與數(shù)據(jù)元素在該順序表中的位置次序無關(guān)
D.ASL的大小與查找每個(gè)數(shù)據(jù)元素的概率無關(guān)

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

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

13.對(duì)關(guān)鍵字序列{eSC，tab，ah，con，brk，del}進(jìn)行排序時(shí)，若關(guān)鍵字序列的變化情況如下;①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.設(shè)有兩個(gè)長(zhǎng)度分別為m、n的降序有序序列{a₁，a₂，…，a_m}、{b₁，b₂，…，b_n}，采用二路歸并方法將它們合并成長(zhǎng)度為m+12的降序有序序列，則歸并過程中元素比較次數(shù)最少的條件一定是(　　)

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

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

11.從宏觀上看，數(shù)據(jù)、數(shù)據(jù)元素和______ 反映了數(shù)據(jù)組織的三個(gè)層次。

12.在表長(zhǎng)為n的順序表中插入或刪除一個(gè)元素，則需移動(dòng)元素的具體個(gè)數(shù)與表長(zhǎng)和____有關(guān)。

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

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

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

16.設(shè)一個(gè)完全二叉樹共含有196個(gè)結(jié)點(diǎn)，則該完全二叉樹中含有葉結(jié)點(diǎn)的個(gè)數(shù)是________。

17.假設(shè)高度為h二叉樹中只有度為2和度為0這兩種類型的結(jié)點(diǎn)，則該類二叉樹中結(jié)點(diǎn)個(gè)數(shù)至多為2^h-1、至少為________。

18.若以數(shù)據(jù)集{34，5，12，23，8，18}為葉結(jié)點(diǎn)的權(quán)值構(gòu)造一棵哈夫曼(HUffman)樹，那么該Huffman樹的帶權(quán)路徑長(zhǎng)度WPL______。

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

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

111.對(duì)長(zhǎng)度為n的有序順序表進(jìn)行二分查找，則查找表中的任意一個(gè)元素時(shí)，無論查找成功與失敗，最多與表中______個(gè)元素進(jìn)行比較。

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

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

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

21.借助于隊(duì)列能夠?qū)⒑衝個(gè)數(shù)據(jù)元素的棧逆置，比如棧S中的元素為{a，b，C}逆置后變成{C，b，a}。試簡(jiǎn)述你的解決方案。

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

23.先序遍歷、中序遍歷一個(gè)森林分別等同于先序、中序遍歷該森林所對(duì)應(yīng)的二叉樹。現(xiàn)已知一個(gè)森林的先序序列和中序序列分別為ABCDEFIGJH和BDCAIFJGHE，試畫出該森林。

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

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

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

31.某電商有關(guān)手機(jī)的庫(kù)存信息，按其價(jià)格從低到高存儲(chǔ)在一個(gè)帶有頭結(jié)點(diǎn)的單循環(huán)鏈表中，鏈表中的結(jié)點(diǎn)由品牌型號(hào)(nametype)、價(jià)格(price)、數(shù)量(quantity)和指針(next)四個(gè)域組成?，F(xiàn)新到in臺(tái)、價(jià)格為c、品牌型號(hào)為x的新款手機(jī)需入庫(kù)，寫出相應(yīng)的存儲(chǔ)結(jié)構(gòu)和實(shí)現(xiàn)該要求的算法。

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