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

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

02142201810

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

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

集合

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

A:

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

B:

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

C:

答D:案：C

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

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

O(logn)

O(n)

A:?

O(n2)

B:

O(nlogn)

C:

?

答D:案：C

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

??

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

4.

5

A:

6

B:

7

C:

答D:案：B

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

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

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

L->prior

L->next

A:

L

B:

C:

L->rear

答D:案：B

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

>next。

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

0

NULL

A:

1

B:

-1

C:

答D:案：A

解析：當(dāng)棧頂下標(biāo)值top==0時是?？?，棧初始化時一般將棧頂下標(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)隊列CQ，隊列的長度為maxsize，則該循環(huán)隊列滿的條件為

(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)隊列隊滿的條件：(CQ.rear+1)%maxsize==CQ.front；，隊空的條件是：CQ.

rear==CQ.front。

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

祖先相同的結(jié)點

根相同的結(jié)點

A:

B:

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

父結(jié)點相同的結(jié)點

C:

答D:案：D

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

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é)點；（2）前序遍歷第一棵樹的根結(jié)點的子樹；（3）前序遍歷去掉第一

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

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

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

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

3

4

A:

5

B:

6

C:

答D:案：C

解析：有向圖頂點的度等于其入度和出度之和。

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

對角矩陣

對稱矩陣

A:

稀疏矩陣

B:

一般矩陣

C:

答D:案：B

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

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

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

查找失敗

查找成功，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ā)點是

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

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

A:

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

B:

節(jié)省存儲空間

C:

答D:案：A

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

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

插入排序

交換排序

A:

選擇排序

B:

歸并排序

C:

答D:案：B

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

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

答案：邏輯

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

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

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

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

解析：單鏈表的每個結(jié)點包括數(shù)據(jù)域和指針域，數(shù)據(jù)域存儲數(shù)據(jù)，指針域存儲下一個結(jié)點

的地址。

18、【問答題】設(shè)有一個單鏈表，若結(jié)點的指針域為next，則指針P所指的結(jié)點為最后一個

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

答案：p->next==NULL

解析：單鏈表的最后一個結(jié)點的指針域存儲的是空指針NULL。

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

為__________。

答案：2

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

棧的是2。

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

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

答案：1

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

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

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

況。

答案：動態(tài)申請空間

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

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

答案：順序

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

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

答案：19

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

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

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

答案：層次

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

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

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

點表示活動的有向圖稱為__________。

答案：AOV網(wǎng)

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

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

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

答案：鍵值

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

表。

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

__________、讀表中元素三種基本運算。

答案：查找

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

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

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

答案：穩(wěn)定

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

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

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

在）的編號分別是多少？

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

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

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

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

答案：

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

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

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

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

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

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

成一棵哈夫曼樹。

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

答案：

解析：本題考核有向圖的鄰接矩陣和拓?fù)渑判颉Ｍ負(fù)渑判蜻^程是：①從有向圖中選擇一

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

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

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

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

答案：

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

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

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

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

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

子樹中。

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

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

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

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

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

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

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

（nlog<>2n）。空間復(fù)雜度為O（log<>2n）?？焖倥判蚍椒ū徽J(rèn)為是排序時間效率非常高

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

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

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

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

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

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

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