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

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

02142201810

1、【單選題】具有分支、層次特性，上層的結(jié)點(diǎn)可以和下層多個(gè)結(jié)點(diǎn)相鄰接,但下層結(jié)點(diǎn)只

能和上層的一個(gè)結(jié)點(diǎn)相鄰接，這種組織形式稱為

集合

線性結(jié)構(gòu)

A:

樹形結(jié)構(gòu)

B:

圖結(jié)構(gòu)

C:

答D:案：C

解析：本題考核的是數(shù)據(jù)結(jié)構(gòu)中樹形結(jié)構(gòu)的定義。

2、【單選題】下面幾種算法時(shí)間復(fù)雜度階數(shù)中，最大的是

O(logn)

O(n)

A:?

O(n2)

B:

O(nlogn)

C:

?

答D:案：C

解析：算法時(shí)間復(fù)雜度階數(shù)從小到大：O(logn)、O(n)、O(nlogn)、O(n2)。

??

3、【單選題】設(shè)順序表的表長(zhǎng)為10,則執(zhí)行插入算法的元素平均移動(dòng)次數(shù)約為

4.

5

A:

6

B:

7

C:

答D:案：B

解析：在插入位置等概率情況下，平均移動(dòng)元素的個(gè)數(shù)為：（n+（n-1）+（n-2）

+…+2+1+0）/（n+1）=n/2。當(dāng)n=10時(shí)，n/2=5

4、【單選題】在帶頭結(jié)點(diǎn)的單鏈表L中，第一個(gè)數(shù)據(jù)元素結(jié)點(diǎn)的指針為

L->prior

L->next

A:

L

B:

C:

L->rear

答D:案：B

解析：在帶頭結(jié)點(diǎn)的單鏈表L中，頭結(jié)點(diǎn)的指針為L(zhǎng),第一個(gè)數(shù)據(jù)元素結(jié)點(diǎn)的指針為L(zhǎng)-

>next。

5、【單選題】棧初始化時(shí)一般將棧頂下標(biāo)值top設(shè)置為

0

NULL

A:

1

B:

-1

C:

答D:案：A

解析：當(dāng)棧頂下標(biāo)值top==0時(shí)是棧空，棧初始化時(shí)一般將棧頂下標(biāo)值top設(shè)置為0。

6、【單選題】設(shè)輸入序列為ABC,輸出為ABC,則經(jīng)過的棧操作為

push,pop,push,push,pop,pop

push,push,pop,pop,push,pop

A:

push,pash,push,pop,pop,pop

B:

push,pop,push,pop,push,pop

C:

答D:案：D

解析：輸入序列為ABC,輸出為ABC，操作順序只能是push,pop,push,pop,push,pop。

7、【單選題】設(shè)有一循環(huán)隊(duì)列CQ，隊(duì)列的長(zhǎng)度為maxsize，則該循環(huán)隊(duì)列滿的條件為

(CQ.rear+l)%maxsize==CQ.front

CQ.rear==CQ.front

A:

(CQ.rear+l)%maxsize=CQ.rear

B:

CQ.rear==NULL

C:

答D:案：A

解析：循環(huán)隊(duì)列隊(duì)滿的條件：(CQ.rear+1)%maxsize==CQ.front；，隊(duì)空的條件是：CQ.

rear==CQ.front。

8、【單選題】樹的相關(guān)術(shù)語(yǔ)中，兄弟指

祖先相同的結(jié)點(diǎn)

根相同的結(jié)點(diǎn)

A:

B:

度數(shù)相同的結(jié)點(diǎn)

父結(jié)點(diǎn)相同的結(jié)點(diǎn)

C:

答D:案：D

解析：樹的相關(guān)術(shù)語(yǔ)中，兄弟指父結(jié)點(diǎn)相同的結(jié)點(diǎn)。

9、【單選題】執(zhí)行進(jìn)棧操作，在元素x進(jìn)棧前需要進(jìn)行的操作是

判斷棧是否滿，若棧未滿，top值加1

判斷棧是否空，若棧未空，top值加1

A:

判斷棧是否滿，若棧未滿，top值減1

B:

判斷棧是否空，若棧未空，top值減1

C:

答D:案：A

解析：執(zhí)行進(jìn)棧操作，在元素x進(jìn)棧前需要判斷棧是否滿，若棧未滿，top值加1。執(zhí)行

出棧操作，出棧前判斷棧是否空，若棧未空，top值減1。

10、【單選題】森林有兩種遍歷方法，分別是

先序遍歷森林和中序遍歷森林

先序遍歷森林和后序遍歷森林

A:

中序遍歷森林和層次遍歷森林

B:

后序遍歷森林和層次遍歷森林

C:

答D:案：A

解析：森林的遍歷有先序遍歷和中序遍歷兩種方式。先序遍歷的定義為：（1）訪問森林

中第一棵樹的根結(jié)點(diǎn)；（2）前序遍歷第一棵樹的根結(jié)點(diǎn)的子樹；（3）前序遍歷去掉第一

棵樹后的子森林。中序遍歷的定義為：（1）中序遍歷第一棵樹的根結(jié)點(diǎn)的子樹；（2）訪

問森林中第一棵樹的根結(jié)點(diǎn)；（3）中序遍歷去掉第一棵樹后的子森林。樹遍歷有三種方

法：先根遍歷、后根遍歷和層次遍歷。

11、【單選題】有向圖中某頂點(diǎn)v的入度為2,出度為3,則該頂點(diǎn)的度為

3

4

A:

5

B:

6

C:

答D:案：C

解析：有向圖頂點(diǎn)的度等于其入度和出度之和。

12、【單選題】無向圖的鄰接矩陣為

對(duì)角矩陣

對(duì)稱矩陣

A:

稀疏矩陣

B:

一般矩陣

C:

答D:案：B

解析：無向圖的鄰接矩陣為對(duì)稱矩陣。有向圖的矩陣一般為稀疏矩陣。

13、【單選題】對(duì)升序表進(jìn)行二分査找，用給定值key與處在中間位置的數(shù)據(jù)元素

T.elem[mid]的鍵值T.elem[mid].key進(jìn)行比較，當(dāng)key<T.elem[mid].key時(shí)，說明

查找失敗

查找成功，T.elem[mid]即為待查元素

A:

待查元素若在表中，則一定排在T.elem[mid]之前

B:

待查元素若在表中，則一定排在T.elem[mid]之后

C:

答D:案：C

解析：key=T.elem[mid].key，查找成功，T.elemEmid]即為待查元素；

key<t.elem[mid].key,說明若待查元素若在表中，則一定排在t.elem[mid]=""之前；

key>T.elem[mid].key,說明若待查元素若在表中，則一定排在T.elem[mid]之后。

14、【單選題】利用散列表進(jìn)行査找的基本出發(fā)點(diǎn)是

減少査找過程中的比較次數(shù)

增加查找過程中的比較次數(shù)

A:

查找過程中不再需要比較操作

B:

節(jié)省存儲(chǔ)空間

C:

答D:案：A

解析：利用散列表進(jìn)行査找的基本出發(fā)點(diǎn)是減少査找過程中的比較次數(shù)。

15、【單選題】快速排序?qū)儆?/p>

插入排序

交換排序

A:

選擇排序

B:

歸并排序

C:

答D:案：B

解析：快速排序?qū)儆诮粨Q排序，快速排序方法的排序過程是一個(gè)遞歸過程。

16、【問答題】鏈?zhǔn)酱鎯?chǔ)的特點(diǎn)是利用指針來表示數(shù)據(jù)元素之間的__________關(guān)系。

答案：邏輯

解析：鏈?zhǔn)酱鎯?chǔ)的特點(diǎn)是利用指針來表示數(shù)據(jù)元素之間的邏輯關(guān)系，順序存儲(chǔ)的特點(diǎn)是利

用存儲(chǔ)的位置來表示數(shù)據(jù)元素之間的邏輯關(guān)系

17、【問答題】單鏈表的每個(gè)結(jié)點(diǎn)包括__________和指針域。

答案：數(shù)據(jù)域

解析：?jiǎn)捂湵淼拿總€(gè)結(jié)點(diǎn)包括數(shù)據(jù)域和指針域，數(shù)據(jù)域存儲(chǔ)數(shù)據(jù)，指針域存儲(chǔ)下一個(gè)結(jié)點(diǎn)

的地址。

18、【問答題】設(shè)有一個(gè)單鏈表，若結(jié)點(diǎn)的指針域?yàn)閚ext，則指針P所指的結(jié)點(diǎn)為最后一個(gè)

結(jié)點(diǎn)的條件是__________.

答案：p->next==NULL

解析：?jiǎn)捂湵淼淖詈笠粋€(gè)結(jié)點(diǎn)的指針域存儲(chǔ)的是空指針NULL。

19、【問答題】設(shè)棧的輸入序列為1、2、3,若輸出的第一個(gè)元素為3,則第二個(gè)輸出的元素

為__________。

答案：2

解析：輸出的第一個(gè)元素為3，一定是1、2、3都入棧后，第一個(gè)出棧的是3，第二個(gè)出

棧的是2。

20、【問答題】線性表中如果結(jié)點(diǎn)數(shù)不為零，則除起始結(jié)點(diǎn)沒有直接前驅(qū)外，其他每個(gè)結(jié)點(diǎn)

有且僅有__________個(gè)直接前驅(qū)。

答案：1

解析：線性表中如果結(jié)點(diǎn)數(shù)不為零，則除起始結(jié)點(diǎn)沒有直接前驅(qū)外，其他每個(gè)結(jié)點(diǎn)有且僅

有1個(gè)直接前驅(qū)，則除終端結(jié)點(diǎn)沒有直接后繼外，其他每個(gè)結(jié)點(diǎn)有且僅有1個(gè)直接后繼。

21、【問答題】由于鏈接實(shí)現(xiàn)需要__________，故鏈隊(duì)列在一定范圍內(nèi)不會(huì)出現(xiàn)隊(duì)列滿的情

況。

答案：動(dòng)態(tài)申請(qǐng)空間

解析：鏈接實(shí)現(xiàn)是動(dòng)態(tài)申請(qǐng)空間，只要內(nèi)存夠用，鏈隊(duì)列就不會(huì)出現(xiàn)隊(duì)列滿的情況。

22、【問答題】二叉樹的__________存儲(chǔ)結(jié)構(gòu)可以用一維數(shù)組來實(shí)現(xiàn)。

答案：順序

解析：二叉樹的的順序存儲(chǔ)結(jié)構(gòu)可以用一維數(shù)組來實(shí)現(xiàn)。

23、【問答題】含有10個(gè)葉子結(jié)點(diǎn)的哈夫曼樹，其結(jié)點(diǎn)的總數(shù)為__________。

答案：19

解析：對(duì)于10個(gè)葉子結(jié)點(diǎn)的哈夫曼樹，其10個(gè)權(quán)值分量，經(jīng)過10-1次合并又產(chǎn)生10-1

個(gè)新結(jié)點(diǎn)，從而組成的10+10-1=2*10-1=19個(gè)結(jié)點(diǎn)的哈夫曼樹。

24、【問答題】圖的廣度優(yōu)先搜索遍歷類似于樹的按__________遍歷的過程。

答案：層次

解析：圖的廣度優(yōu)先搜索遍歷類似于樹的按層次遍歷的過程，圖的深度優(yōu)先搜索遍歷類

似于樹的先根遍歷的過程。

25、【問答題】如果以圖中的頂點(diǎn)來表示活動(dòng)，有向邊表示活動(dòng)之間的優(yōu)先關(guān)系，這種用頂

點(diǎn)表示活動(dòng)的有向圖稱為__________。

答案：AOV網(wǎng)

解析：本題考核AOV網(wǎng)的概念。

26、【問答題】用數(shù)據(jù)元素的__________通過散列函數(shù)獲取存儲(chǔ)位置的存儲(chǔ)方式構(gòu)造的存儲(chǔ)

結(jié)構(gòu)稱為散列表。

答案：鍵值

解析：用數(shù)據(jù)元素的鍵值通過散列函數(shù)獲取存儲(chǔ)位置的存儲(chǔ)方式構(gòu)造的存儲(chǔ)結(jié)構(gòu)稱為散列

表。

27、【問答題】靜態(tài)查找表是以具有相同特性的數(shù)據(jù)元素集合為邏輯結(jié)構(gòu)，包括建表、

__________、讀表中元素三種基本運(yùn)算。

答案：查找

解析：靜態(tài)查找表的概念和基本運(yùn)算

28、【問答題】若待排序的序列中存在多個(gè)記錄具有相同的鍵值，經(jīng)過排序，這些記錄的相

對(duì)次序仍然保持不變，則稱這種排序方法是__________的。

答案：穩(wěn)定

解析：本題考核排序穩(wěn)定性的概念。

29、【問答題】高度為h的滿二叉樹，如果按層次自上而下，同層從左到右的次序從1開始

編號(hào)，試問：（1）該樹上有多少個(gè)結(jié)點(diǎn)？（2）編號(hào)為i的結(jié)點(diǎn)的左孩子和右孩子（若存

在）的編號(hào)分別是多少？

答案：（1）2h-1（2）左孩子的編號(hào)為2*i，右孩子的編號(hào)為2*i+1

30、【問答題】假設(shè)用于通訊的電文僅由6個(gè)字母A，B，C，D，E，F(xiàn)組成，各個(gè)字母在電

文中出現(xiàn)的頻率分別為6，3,12,10,7,5,試為這6個(gè)字母設(shè)計(jì)哈夫曼樹。（構(gòu)建新二叉樹

時(shí)，要求新二叉樹的左子樹根的權(quán)值小于等于右子樹根的權(quán)值。）

答案：

解析：構(gòu)造哈夫曼樹的方法：①將給定的權(quán)值按照從小到大排列成｛W1，W2，…，

Wm｝，并且構(gòu)造出樹林F=｛Tl，T2，…，Tm｝。此時(shí)，其中的每棵樹Ti(1≤i≤m）為

左、右子樹均為空的二叉樹，二叉樹的根結(jié)點(diǎn)的權(quán)值為Wi。②把F中樹根結(jié)點(diǎn)的權(quán)值最

小的兩棵二叉樹T1和T2合并為一棵新的二叉樹T（T的左子樹為T1，右子樹為T2），并

令T的根結(jié)點(diǎn)的權(quán)值為T1和T2的根結(jié)點(diǎn)的權(quán)值之和，然后將T按其根結(jié)點(diǎn)的權(quán)值大小依

次加入到樹林F中。同時(shí)，從F中刪去T1和T2這兩棵二叉樹。③重復(fù)步驟②，直到構(gòu)造

成一棵哈夫曼樹。

31、【問答題】寫出如題31圖所示的有向圖鄰接矩陣表示和所有拓?fù)渑判蛐蛄小?/p>

答案：

解析：本題考核有向圖的鄰接矩陣和拓?fù)渑判?。拓?fù)渑判蜻^程是：①?gòu)挠邢驁D中選擇一

個(gè)入度為0的頂點(diǎn)；②從有向圖中將該頂點(diǎn)以及由該頂點(diǎn)發(fā)出的所有弧全部刪除；③重

復(fù)上述過程，直到剩余的網(wǎng)中不再存在入度為0的頂點(diǎn)。

32、【問答題】給定數(shù)據(jù)序列{46,25,78,62,12,80}，試按元素在序列中的次序?qū)⑺?/p>

們依次插入一棵初始為空的二叉排序樹，畫出插入完成后的二叉排序樹。

答案：

解析：通常采用逐點(diǎn)插入結(jié)點(diǎn)的方法來構(gòu)造二叉排序樹，其方法表述如下：設(shè)K=｛kl，

k2，k3，…，kn｝為數(shù)據(jù)元素序列。從k1開始依次取序列中的元素，每取出一個(gè)數(shù)據(jù)元

素ki按下列原則建立二叉排序樹的一個(gè)結(jié)點(diǎn)：①若二叉排序樹為空，則ki就是該二叉排

序樹的根結(jié)點(diǎn)。②若二叉排序樹非空，則將ki與該二叉排序樹的根結(jié)點(diǎn)的值進(jìn)行比較。

若ki小于根結(jié)點(diǎn)的值，則將ki插入到根結(jié)點(diǎn)的左子樹中，否則將ki插入到根結(jié)點(diǎn)的右

子樹中。

33、【問答題】對(duì)鍵值序列（61，87，12，3，8，70）以位于最左位置的鍵值為基準(zhǔn)進(jìn)行由

小到大的快速排序，請(qǐng)寫出第一趟排序后的結(jié)果，并給出快速排序算法在平均情況和最壞情

況下的時(shí)間復(fù)雜度。

答案：（1）第一趟排序后的結(jié)果:[8312]61[8770]（2）快速排序算法在平均情況下

的時(shí)間復(fù)雜度為O(nlog<>2n),在最壞情況下的時(shí)間復(fù)雜度為O(n<>2)。

解析：根據(jù)快速排序的算法，第一趟排序后的結(jié)果:[8312]61[8770]?？焖倥判蚍椒?/p>

的排序過程是一個(gè)遞歸過程?？焖倥判蚍椒ㄊ且环N不穩(wěn)定的排序方法，其時(shí)間復(fù)雜度為O

（nlog<>2n）?？臻g復(fù)雜度為O（log<>2n）。快速排序方法被認(rèn)為是排序時(shí)間效率非常高

的一種方法，但是，當(dāng)參加排序的原始序列已經(jīng)是一個(gè)按值有序的序列時(shí)，快速排序方法

的時(shí)間效率將降到最低，這種情況下其時(shí)間復(fù)雜度為O（n<>2）

34、【問答題】假設(shè)線性表的數(shù)據(jù)元素的類型為DataType，順序表的結(jié)構(gòu)定義如下：

設(shè)計(jì)算法實(shí)現(xiàn)順序表的插入運(yùn)

算InsertSeqlist（SeqListL,DataTypex，inti）。該算法是指在順序表的第i（l≤i

≤n+1）個(gè)元素之前，插入一個(gè)新元素x。使長(zhǎng)度為n的線性表（a1，a2，…，ai-1，

ai，…，an）變?yōu)殚L(zhǎng)度為n+1的線性表（a1，a2，…，ai