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

數(shù)據(jù)結(jié)構(gòu)導(dǎo)論年月真題

0214220164

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)是

線性表

隊(duì)列

A:

樹

B:

圖

C:

答D:案：C

2、【單選題】計(jì)算n!(整數(shù)n≥0)的遞歸算法是：intFactorial(intn){if(n==o)return

l；elsereturnn*Factorial(n--1)；}其時(shí)闖復(fù)雜度為

0(n)

0(log2n)

A:

O(n0)

B:

O(n2)

C:

答D:案：A

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

p=q；

p--：>next=q；

A:

q一>next=p--：>next；p-->next=q；

B:

p一>next—q；q-->next—p--：>next；

C:

答D:案：C

4、【單選題】設(shè)初始棧為空，s表示入棧操作，x表示出棧操作，則合法的操作序列是

sxxssxxs

ssxsxxxs

A:

ssxxxssx

B:

sssxxxsx

C:

答D:案：D

5、【單選題】將遞歸形式描述的算法改寫為功能等價(jià)的非遞歸形式描述的算法，通常應(yīng)設(shè)置

的輔助結(jié)構(gòu)是

順序表

單鏈表

A:

棧

B:

隊(duì)列

C:

答D:案：C

6、【單選題】設(shè)長(zhǎng)度為n的隊(duì)列用單循環(huán)鏈表表示(假設(shè)表尾結(jié)點(diǎn)為當(dāng)前隊(duì)列的隊(duì)尾元素)，

若只設(shè)頭指針，則入隊(duì)操作、出隊(duì)操作的時(shí)間復(fù)雜度分別為

O(n)、O(1)

O(1)、O(1)

A:

O(1)、O(n)

B:

0(n)、0(n)

C:

答D:案：A

7、【單選題】若采用順序存儲(chǔ)(一維數(shù)組)結(jié)構(gòu)存儲(chǔ)一棵如題7圖所示的二叉樹，根結(jié)點(diǎn)

1的下標(biāo)為l，剝結(jié)點(diǎn)4的下標(biāo)為

4

A:

5

6

B:

7

C:

答D:案：C

8、【單選題】按層序(自頂向下、從左到右)遍歷二叉樹時(shí)需借助隊(duì)列作輔助結(jié)構(gòu)。對(duì)高度為

3的滿二叉樹進(jìn)行層序遍歷時(shí)，隊(duì)列中所出現(xiàn)的元素個(gè)數(shù)最多是

1

2

A:

3

B:

4

C:

答D:案：D

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

個(gè)元素的存儲(chǔ)地址是

120

110

A:

108

B:

100

C:

答D:案：C

10、【單選題】已知含6個(gè)頂點(diǎn)(v0，v1，v2，v3，v4，v5)的無向圖的鄰接矩陣如題10

圖所示，則從頂點(diǎn)V0出發(fā)進(jìn)行深度優(yōu)先搜索可能得到的頂點(diǎn)訪問序列為

{v0，v1，v2，v5，v4，v3}

{v0，v1，v2，v3，v4，v5}

A:

{v0，v1，v5，v2，v3，v4}

B:

{v0，v1，v4，v5，v2，v3}

C:

答D:案：A

11、【單選題】“在旅游時(shí)從某地出發(fā)要去某個(gè)目的地，如何選擇線路才能使得路程最

短”，從圖的應(yīng)用角度．最合理的解決方案是

深度優(yōu)先搜索

最小生成樹

A:

拓?fù)渑判?/p>

B:

最短路徑

C:

答D:案：D

12、【單選題】二分查找算法的時(shí)間復(fù)雜度是

O(n2)

O(nlog2n)

A:

O(n)

B:

O(log2n)

C:

答D:案：D

13、【單選題】已知一個(gè)散列表如題13圖所示，其散列函數(shù)為H(key)=keymod11，采用

線性探測(cè)法處理沖突，則下一個(gè)進(jìn)入散列表的關(guān)鍵字49的地址為

2

3

A:

8

B:

9

C:

答D:案：C

14、【單選題】用冒泡排序方法對(duì)n個(gè)待排序的鍵值進(jìn)行排序，則整個(gè)排序過程所歷經(jīng)的趟

數(shù)是

1

n—1

A:

rl

B:

至少為l、至多為n—l

C:

答D:案：D

15、【單選題】現(xiàn)對(duì)關(guān)鍵字序列{6，1，4，3，7，2，8，5)進(jìn)行快速排序，那么以第1個(gè)元

素6為工作基準(zhǔn)的第一趟快速排序結(jié)束的結(jié)果序列為

{5，1，4，3，2，6，8，7)

{5，1，4，3，2，6，7，8)

A:

{5，1，4，3，6，2，8，7)

B:

{8，7，6，5，4，3，2，1)

C:

答D:案：A

16、【問答題】如題29圖所示，利用同一循環(huán)向量空間實(shí)現(xiàn)兩個(gè)隊(duì)列，其類型Queue2定

義如下：typedefstruct{DataTypedata[MaxSize]；int：[ront[2]，

length[2]；)Queue2；對(duì)于i=0或l，front[i]和length[i-]分別為第i個(gè)隊(duì)列的隊(duì)頭

位置和實(shí)際長(zhǎng)度。分別寫出這兩個(gè)隊(duì)列滿的條件。

答案：

17、【問答題】將如題30圖所示的含有3棵樹的森林轉(zhuǎn)換成相應(yīng)的二又樹，并分別給出

該森林先序、中序遍歷的結(jié)果序列和相應(yīng)的二叉樹的先序、中序遍歷結(jié)果序列，根據(jù)所得

到的遍歷結(jié)果序列你會(huì)得到什么結(jié)論?

答案：

18、【問答題】對(duì)一個(gè)圖G，按順序輸入頂點(diǎn)對(duì)<1，3>、<1，2>、<2，4>、<2，3>、<4，

3>、<4，2>、<4，l>，根據(jù)建立圖的鄰接表的算法畫出相應(yīng)的鄰接表，并寫出在該鄰接表

上，從頂點(diǎn)2開始搜索得到的一個(gè)深度優(yōu)先搜索序列和廣度優(yōu)先搜索序列。

答案：

19、【問答題】設(shè)順序存儲(chǔ)的線性表共有100個(gè)元素，按分塊查找(索引查找)的要求等分成

5塊。若對(duì)索引表采用二分查找來確定塊，并在確定的塊中進(jìn)行順序查找，則在概率相等的情

況下，分塊查找成功時(shí)的平均查找長(zhǎng)度是多少(要求利甩∑PiCi來計(jì)算并給出詳細(xì)算式)?

答案：分塊查找成功時(shí)的平均查找長(zhǎng)度由對(duì)索引表和對(duì)塊內(nèi)查找兩部分組成。其中對(duì)索引

表查找的ASL=(1×1+2×2+2×3)/5=2.2,對(duì)順序表查找的ASL=(1+2+…+20)/20=10.5。所

以,分塊查找成功時(shí)的平均查找長(zhǎng)度ASL=2.2+10.5=12.7

20、【問答題】若采用堆排序方法對(duì)關(guān)鍵字序列{265，301，751，129，937，863，742，

694，076，438}進(jìn)行升序排序，寫出其每趟排序結(jié)束后的關(guān)鍵字序列。

答案：用“最大堆”的排序結(jié)果為升序列。初始態(tài):[265301751129937863742

694076438]建立初始堆:[937694863265438751742129076301]第一次排序

重建堆:[863694751765438301742129076]937第二次排序重建堆:[751694742

265438301076129]863937第三次排序重建堆:[742694301265438129076]751

863937第四次排序重建堆:[694438301265076129]742751863937第五次排序

重建堆:[438265301129076]694742751863937第六次排序重建堆:[301265076

129]438694742751863937第七次排序重建堆:[265129076]301438694742751

863937第八次排序重建堆:[129076]265301438694742751863937第九次排序

重建堆:076129265301438694742751863937

21、【問答題】假設(shè)以帶頭結(jié)點(diǎn)的單鏈表表示線性表，單鏈表的類型定義如下：typedef

structnode{intdata；structnode*next；)LinkedNode，*LinkedList，；編寫算法，刪

除值無序的線性表中值最大的元素(設(shè)表中各元素的值互不相同)。編寫算法

答案：

22、【問答題】假設(shè)樹的存儲(chǔ)結(jié)構(gòu)采用孩子兄弟表示法，寫出樹的先序遍歷算法。該算法的

函數(shù)頭為：voidPreOrderTree(TNode*root，void(*Visit)())，樹的孩子兄弟表示法數(shù)據(jù)類

型定義為：typede{structtnode{DataTypedata；structtnode*firstchilcl，

*nextsibling；}TNode，*Tree；假設(shè)樹的存儲(chǔ)結(jié)構(gòu)采用孩子兄弟表示法，寫出樹的先序遍

歷算法。

答案：

23、【填空題】計(jì)算機(jī)圖靈獎(jiǎng)獲得者N．Wirth曾提出一個(gè)著名公式：算法+________=程

序。

答案：數(shù)據(jù)結(jié)構(gòu)

24、【填空題】“即使輸入非法數(shù)據(jù)，算法也能適當(dāng)?shù)刈龀龇磻?yīng)或進(jìn)行處理，不會(huì)產(chǎn)生預(yù)料

不到的運(yùn)行結(jié)果?！边@種評(píng)價(jià)算法好壞的因素稱為________。

答案：健壯性

25、【填空題】設(shè)某非空雙向鏈表，其結(jié)點(diǎn)結(jié)構(gòu)為

，若要?jiǎng)h除指針q所指向的結(jié)

點(diǎn)，則需執(zhí)行如下兩條關(guān)鍵語句：q一>priort>next=q-->next；_________。

答案：q—>next—>prior=q—>prior;

26、【填空題】大小為MaxSize的循環(huán)隊(duì)列中，若front與rear分別表示隊(duì)頭元素和隊(duì)尾

元素的位置，則判斷該循環(huán)隊(duì)列為空的條件表達(dá)式是________。

答案：rear==front

27、【填空題】對(duì)稀疏矩陣進(jìn)行壓縮存儲(chǔ)的一種方法是________。

答案：三元組表示法

28、【填空題】若一棵二又樹中只有葉結(jié)點(diǎn)和左右子樹皆非空的結(jié)點(diǎn)，設(shè)二叉樹葉結(jié)點(diǎn)個(gè)數(shù)

為s，則左右子樹皆非空的結(jié)點(diǎn)個(gè)數(shù)是________。

答案：s-1

29、【填空題】若一棵二叉樹的前序、中序、后序遍歷的結(jié)果序列均相同，則該二叉樹一定

是________或是只有一個(gè)根結(jié)點(diǎn)的二叉樹。

答案：空二叉樹

30、【填空題】采用鄰接表表示一有向圖，若圖中某頂點(diǎn)的入度和出度分別為D1和D2，則

該頂點(diǎn)所對(duì)應(yīng)的單鏈表的結(jié)點(diǎn)個(gè)數(shù)為________。

答案：D2

31、【填空題】對(duì)有序順序表(07，12，15，18，27，32，46，65，83)用二分法查找，若查

找成功，則查找所需比較次數(shù)最多的鍵值是________。

答案：18,83

32、【填空題】由n個(gè)鍵值構(gòu)造的二叉排序樹，在等概率查找的假設(shè)下，查找成功的平均查

找長(zhǎng)度的最大值可能達(dá)到________。

答案：(n+1)/2

33、【填空題】對(duì)關(guān)鍵字序列{26,36，41，38，44，15，68，l2，06，51}，設(shè)

HashSize=13，H(key)=keymo