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

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

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

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

1.一個(gè)公司的組織機(jī)構(gòu)是1名公司經(jīng)理領(lǐng)導(dǎo)若于名部門負(fù)責(zé)人、每個(gè)部門負(fù)責(zé)人領(lǐng)導(dǎo)若干名部門員工，則適合于描述該公司組織機(jī)構(gòu)的邏輯結(jié)構(gòu)是(　　)

A.線性表
B.隊(duì)列
C.樹(shù)
D.圖

2.計(jì)算n!(整數(shù)n≥0)的遞歸算法是：int Factorial(int n) { if(n==0) return 1; else return n*Factorial(n-1); }其時(shí)間復(fù)雜度為(　　)

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

3.將一個(gè)由指針q指向的結(jié)點(diǎn)插在單鏈表中由指針p所指向的結(jié)點(diǎn)之后的操作是(　　)

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

4. 設(shè)初始棧為空，s表示入棧操作，x表示出棧操作，則合法的操作序列是(　　)

A.sxxssxxs
B.ssxsxxxs
C.ssxxxssx
D.sssxxxsx

5.將遞歸形式描述的算法改寫(xiě)為功能等價(jià)的非遞歸形式描述的算法，通常應(yīng)設(shè)置的輔助結(jié)構(gòu)是(　　)

A.順序表
B.單鏈表
C.棧
D.隊(duì)列

6.設(shè)長(zhǎng)度為n的隊(duì)列用單循環(huán)鏈表表示(假設(shè)表尾結(jié)點(diǎn)為當(dāng)前隊(duì)列的隊(duì)尾元素)，若只設(shè)頭指針，則入隊(duì)操作、出隊(duì)操作的時(shí)間復(fù)雜度分別為(　　)

A.O(n)、O(1)
B.O(1)、O(1)
C.O(1)、O(n)
D.O(n)、O(n)

7.若采用順序存儲(chǔ)(一維數(shù)組)結(jié)構(gòu)存儲(chǔ)一棵如題7圖所示的二叉樹(shù)，根結(jié)點(diǎn)1的下標(biāo)為1，則結(jié)點(diǎn)4的下標(biāo)為(　　)

A.4
B.5
C.6
D.7

8.按層序(自頂向下、從左到右)遍歷二叉樹(shù)時(shí)需借助隊(duì)列作輔助結(jié)構(gòu)。對(duì)高度為3的滿二叉樹(shù)進(jìn)行層序遍歷時(shí)，隊(duì)列中所出現(xiàn)的元素個(gè)數(shù)最多是(　　)

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

9.一個(gè)數(shù)組的第一個(gè)元素的存儲(chǔ)地址是100，每個(gè)元素占2個(gè)存儲(chǔ)單元，則第5個(gè)元素的存儲(chǔ)地址是(　　)

A.120
B.110
C.108
D.100

10.已知含6個(gè)頂點(diǎn)(v0，v1，v2，v3，v4，v5)的無(wú)向圖的鄰接矩陣如題10圖所示，則從頂點(diǎn)V0出發(fā)進(jìn)行深度優(yōu)先搜索可能得到的頂點(diǎn)訪問(wèn)序列為(　　)

A.{v₀，v₁，v₂，v₅，v₄，v₃}
B.{v₀，v₁，v₂，v₃，v₄，v₅}
C.{v₀，v₁，v₅，v₂，v₃，v₄}
D.{v₀，v₁，v₄，v₅，v₂，v₃}

11.“在旅游時(shí)從某地出發(fā)要去某個(gè)目的地，如何選擇線路才能使得路程最短”，從圖的應(yīng)用角度，最合理的解決方案是(　　)

A.深度優(yōu)先搜索
B.最小生成樹(shù)
C.拓?fù)渑判?br/>D.最短路徑

12.二分查找算法的時(shí)間復(fù)雜度是(　　)

A.O(n²)
B.O(n log₂n)
C.O(n)
D.O(log₂n)

13.已知一個(gè)散列表如題13圖所示，其散列函數(shù)為H(key)=key mod11，采用線性探測(cè)法處理沖突，則下一個(gè)進(jìn)入散列表的關(guān)鍵字49的地址為(　　)

A.2
B.3
C.8
D.9

14.用冒泡排序方法對(duì)n個(gè)待排序的鍵值進(jìn)行排序，則整個(gè)排序過(guò)程所歷經(jīng)的趟數(shù)是(　　)

A.1
B.n-1
C.n
D.至少為1、至多為n-1

15.現(xiàn)對(duì)關(guān)鍵字序列{6，1，4，3，7，2，8，5}進(jìn)行快速排序，那么以第1個(gè)元素6為工作基準(zhǔn)的第一趟快速排序結(jié)束的結(jié)果序列為(　　)

A.{5，1，4，3，2，6，8，7}
B.{5，1，4，3，2，6，7，8}
C.{5，1，4，3，6，2，8，7}
D.{8，7，6，5，4，3，2，1}

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

11.計(jì)算機(jī)圖靈獎(jiǎng)獲得者N.Wirth曾提出一個(gè)著名公式：算法+________=程序。

12.“即使輸入非法數(shù)據(jù)，算法也能適當(dāng)?shù)刈龀龇磻?yīng)或進(jìn)行處理，不會(huì)產(chǎn)生預(yù)料不到的運(yùn)行結(jié)果?！边@種評(píng)價(jià)算法好壞的因素稱為_(kāi)_______。

13.設(shè)某非空雙向鏈表，其結(jié)點(diǎn)結(jié)構(gòu)為，若要?jiǎng)h除指針q所指向的結(jié)點(diǎn)，則需執(zhí)行如下兩條關(guān)鍵語(yǔ)句：q->prior->next=q->next; _________。

14.大小為MaxSize的循環(huán)隊(duì)列中，若front與rear分別表示隊(duì)頭元素和隊(duì)尾元素的位置，則判斷該循環(huán)隊(duì)列為空的條件表達(dá)式是________。

15.對(duì)稀疏矩陣進(jìn)行壓縮存儲(chǔ)的一種方法是________。

16.若一棵二又樹(shù)中只有葉結(jié)點(diǎn)和左右子樹(shù)皆非空的結(jié)點(diǎn)，設(shè)二叉樹(shù)葉結(jié)點(diǎn)個(gè)數(shù)為s，則左右子樹(shù)皆非空的結(jié)點(diǎn)個(gè)數(shù)是________。

17.若一棵二叉樹(shù)的前序、中序、后序遍歷的結(jié)果序列均相同，則該二叉樹(shù)一定是________或是只有一個(gè)根結(jié)點(diǎn)的二叉樹(shù)。

18.采用鄰接表表示一有向圖，若圖中某頂點(diǎn)的入度和出度分別為D₁和D₂，則該頂點(diǎn)所對(duì)應(yīng)的單鏈表的結(jié)點(diǎn)個(gè)數(shù)為_(kāi)_______。

19.對(duì)有序順序表(07，12，15，18，27，32，46，65，83)用二分法查找，若查找成功，則查找所需比較次數(shù)最多的鍵值是________。

110.由n個(gè)鍵值構(gòu)造的二叉排序樹(shù)，在等概率查找的假設(shè)下，查找成功的平均查找長(zhǎng)度的最大值可能達(dá)到________。

111.對(duì)關(guān)鍵字序列{26，36，41，38，44，15，68，12，06，51}，設(shè)HashSize=13，H(key)=key mod HashSize，并用鏈地址法解決沖突，則構(gòu)造得到的散列表中的指針HP[________]所指向的一個(gè)單鏈表(同義詞子表)最長(zhǎng)。

112.在直接選擇、直接插入、冒泡、快速等四種排序方法中，經(jīng)一趟排序后，任一元素都不能確定其最終位最的排序方法是________。

113.若采用直接選擇排序方法對(duì)初始關(guān)鍵字序列{5，3，5，1}進(jìn)行升序排序(其中包括2個(gè)值相同的關(guān)鍵字，均為5)，則排序結(jié)束后的關(guān)鍵字序列是________。

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

21.如題29圖所示，利用同一循環(huán)向量空間實(shí)現(xiàn)兩個(gè)隊(duì)列，其類型Queue2定義如下： typedef struct{ DataType data[MaxSize]; int front[2], length[2]; }Queue2; 對(duì)于i=0或1，front[i]和length[i]分別為第i個(gè)隊(duì)列的隊(duì)頭位置和實(shí)際長(zhǎng)度。分別寫(xiě)出 這兩個(gè)隊(duì)列滿的條件。

22.將如題30圖所示的含有3棵樹(shù)的森林轉(zhuǎn)換成相應(yīng)的二又樹(shù)，并分別給出該森林先序、中序遍歷的結(jié)果序列和相應(yīng)的二叉樹(shù)的先序、中序遍歷結(jié)果序列，根據(jù)所得到的遍歷結(jié)果序列你會(huì)得到什么結(jié)論?

23.對(duì)一個(gè)圖G，按順序輸入頂點(diǎn)對(duì)<1，3>、<1，2>、<2，4>、<2，3>、<4，3>、<4，2>、<4，1>，根據(jù)建立圖的鄰接表的算法畫(huà)出相應(yīng)的鄰接表，并寫(xiě)出在該鄰接表上，從頂點(diǎn)2開(kāi)始搜索得到的一個(gè)深度優(yōu)先搜索序列和廣度優(yōu)先搜索序列。

24.設(shè)順序存儲(chǔ)的線性表共有100個(gè)元素，按分塊查找(索引查找)的要求等分成5塊。若對(duì)索引表采用二分查找來(lái)確定塊，并在確定的塊中進(jìn)行順序查找，則在概率相等的情況下，分塊查找成功時(shí)的平均查找長(zhǎng)度是多少(要求利甩∑PiCi來(lái)計(jì)算并給出詳細(xì)算式)?

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

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

31.假設(shè)以帶頭結(jié)點(diǎn)的單鏈表表示線性表，單鏈表的類型定義如下：typedef struct node{ int data;    struct node*next; } LinkedNode，*LinkedList;編寫(xiě)算法，刪除值無(wú)序的線性表中值最大的元素(表中各元素的值互不相同)。

32.假設(shè)樹(shù)的存儲(chǔ)結(jié)構(gòu)采用孩子兄弟表示法，寫(xiě)出樹(shù)的先序遍歷算法。該算法的函數(shù)頭為： void PreOrderTree(TNode*root, void(*Visit)( ))，樹(shù)的孩子兄弟表示法數(shù)據(jù)類型定義為：typedef struct tnode {       DataType data;       struct tnode *firstchild, *nextsibling;} TNode, *Tree;