?數(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)論自考歷年真題試卷，包含答案及詳細解析。

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

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

A.線性表
B.隊列
C.樹
D.圖

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

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

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

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.將遞歸形式描述的算法改寫為功能等價的非遞歸形式描述的算法，通常應(yīng)設(shè)置的輔助結(jié)構(gòu)是(　　)

A.順序表
B.單鏈表
C.棧
D.隊列

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

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

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

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

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

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

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

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

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

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.“在旅游時從某地出發(fā)要去某個目的地，如何選擇線路才能使得路程最短”，從圖的應(yīng)用角度，最合理的解決方案是(　　)

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

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

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

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

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

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

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

15.現(xiàn)對關(guān)鍵字序列{6，1，4，3，7，2，8，5}進行快速排序，那么以第1個元素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.計算機圖靈獎獲得者N.Wirth曾提出一個著名公式：算法+________=程序。

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

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

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

15.對稀疏矩陣進行壓縮存儲的一種方法是________。

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

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

18.采用鄰接表表示一有向圖，若圖中某頂點的入度和出度分別為D₁和D₂，則該頂點所對應(yīng)的單鏈表的結(jié)點個數(shù)為________。

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

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

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

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

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

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

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

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

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

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

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

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

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

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