數(shù)據結構隨堂測驗

數(shù)據結構隨堂測驗

學號：［填空題］*

您的姓名：［填空題］*

1.判斷：線性表中的所有元素都有一個前驅元素和一個后繼元素。*［判斷題］*

對

錯（正確答案）

2.判斷：單鏈表中一定要有頭指針和頭結點。*［判斷題］*

對

錯（正確答案）

3.判斷：設計算法判斷表達式括號是否匹配，應采用棧數(shù)據結構實現(xiàn)。*［判斷題］

*

對（正確答案）

錯

4.不論是入隊操作還是入棧操作，在順序存儲結構上都需要考慮“溢出”情況。*

［判斷題］*

對（正確答案）

錯

5.判斷：在一個圖中所有頂點的度數(shù)之和等于圖的邊數(shù)的2倍。*［判斷題］*

對

錯

6.哈夫曼樹中沒有度為1的結點。*［判斷題］*

對（正確答案）

錯

7.數(shù)據的最小單位是（）。*［單選題］*

數(shù)據項

數(shù)據對象

數(shù)據元素

數(shù)據變量

8.下面關于線性表的敘述錯誤的是（）*［單選題］*

D.線性表采用順序存儲便于插入和刪除操作的實現(xiàn)

A.線性表采用順序存儲必須占用一片連續(xù)的存儲空間

C.線性表采用鏈式存儲便于插入和刪除操作的實現(xiàn)

B.線性表采用鏈式存儲不必占用一片連續(xù)的存儲空間

9.設一條單鏈表的頭指針變量為head,如果該單鏈表有頭結點則其判空條件為

0,如果無頭結點則其判空條件為0O*［單選題］*

head==NULL;head->next==head;

head->next==head；head==NULL;

head->next==NULL；head==NULL;

head==NULL；head->next==NULL;

10.向一個有125個元素的順序表中插入一個新元素并保持原來順序不變，平均要

移動的元素個數(shù)為（）*［單選題］*

62.5(正確答案)

63.5

62

63

11.設輸入序列為1、2、3、4、5、6,則通過棧的作用后可以得到的輸出序列為

()*［單選題］*

1,5,4,6,2,3

3,1,2,5,4,6

3,2,5,6,4,1

5,3,4,6,1,2E確答案)

12.隊列是一種()的線性表。*［單選題］*

先進先出

先進后出

只能插入

只能刪除

13.數(shù)組作為循環(huán)隊列的存儲空間，大小為n,即data［n］,front為隊頭指針，rear為

隊尾指針，則執(zhí)行出隊操作后其頭指針front值為()，執(zhí)行入隊操作其尾指針

rear值為()。*［單選題］*

front=(front+1)%(n-l);rear=(rear+l)%(n-l);

front=(front-1)%n;rear=(rear-l)%n;

front=firont+2;rear=rear+1;

front=(front+1)%n；rear=(rear+l)%n；(正確答案)

14.二叉樹的第k層最多有多少個結點()。*［單選題］*

2的k-1次方

2的k次方-1

2k+l

2k-1

15.n個結點的完全無向圖含有邊的數(shù)目（）o*［單選題］*

n*（n-l）

n*n

n*（n?l）/2（正確答案）

n*（n+l）

16.設某無向圖中有n個頂點e條邊，則該無向圖中所有頂點的度之和為（）。*

［單選題］*

n

e

2n

2e（正確答案）

17.n個頂點的連通圖，至少有（）條邊。*［單選題］*

n

n-l（正確答案）

n+1

2n

18.圖的深度優(yōu)先遍歷類似于樹的（），圖的廣度優(yōu)先遍歷類似于樹的（）。*［單選題］

*

層序遍歷,先序遍歷

中序遍歷；層序遍歷

先序遍歷；層序遍歷

層序遍歷；中序遍歷

19.設用鄰接矩陣A表示有向圖G的存儲結構，則有向圖G中頂點i的入度為（）*

［單選題］*

第i列0元素的個數(shù)之和

第i行非。元素的個數(shù)之和

第i列非0元素的個數(shù)之和

第i行0元素的個數(shù)之和

20.請寫出上圖所示二叉樹的先序遍歷結果中序遍歷結果

,后序遍歷結果,層序遍歷結果

［填空題］*

空1答案：ABCDEGF

空2答案:CBEDAGF

空3答案：CEDBFGA

空4答案：ABGCDFE

011100.

100010.

100010.

100001.

011000.

000100.

21.已知圖中包含頂點A、B、