數(shù)據(jù)結(jié)構結(jié)課試卷

數(shù)據(jù)結(jié)構結(jié)課試卷

您的姓名：［填空題］*

1.數(shù)據(jù)結(jié)構是相互之間存在一種或多種特定關系的數(shù)據(jù)元素的結(jié)合［判斷題］*

對

錯

2.二叉樹在邏輯上算線性，圖在邏輯上算非線性［判斷題］*

對

錯（正確答案）

3.順序存儲不要求邏輯上相鄰的數(shù)據(jù)元素在物理上也相鄰［判斷題］*

對

錯（正確答案）

4.順序線性表中有n個元素，刪除第i個元素需要移動i個元素的位置［判斷題］*

對

錯（正確答案）

5.當棧未滿，入棧時，棧頂指針先加1,再送值到棧頂元素［判斷題］*

對（正確答案）

錯

6.隊列的插入、刪除都只能在對頭進行［判斷題］*

對

錯（正確答案）

7.在循環(huán)隊列中判斷隊滿的公式為：Q.front==Q.rear［判斷題］*

對

錯（正確答案）

8.在C語言中，字符串的結(jié)尾符號是空格［判斷題］*

對

錯（正確答案）

9.對稱矩陣的壓縮過程中只需要存儲其中n（n-l）/2個元素［判斷題］*

對

錯（正確答案）

10.廣義表氏（a,（b,（c））,E）的深度為3［判斷題］*

對

錯（正確答案）

11.樹特別適用于表達數(shù)據(jù)元素之間的層次關系，且樹都有左右之分［判斷題］*

對

錯（正確答案）

12.構造好的一棵哈夫曼樹共有29個結(jié)點，其中度為2的結(jié)點個數(shù)為14［判斷題］

對（正確答案）

錯

13.無向圖的鄰接矩陣是一個對稱矩陣［判斷題］*

對

錯

14.廣度優(yōu)先搜素時，“先被訪問的頂點的鄰接點”后于“后被訪問的頂點的鄰接點”

被訪問［判斷題］*

對

錯（正確答案）

15.Prim構造最小生成樹時，采用的方法是在邊集選擇代價最小的邊，若該邊依附

的頂點落在樹中不同的連通分量上，則將此邊加入到樹中［判斷題］*

對

錯（正確答案）

16.折半查找在最壞情況下查找成功的比較次數(shù)不會超過判定樹的深度［判斷題］*

對

錯

17.最小生成樹不是唯一的，最小生成樹的邊的權值之和也是不唯一的「判斷題］*

對

錯（正確答案）

18.堆中左子樹的值一定小于堆頂?shù)闹担易訕涞闹狄欢ù笥诙秧數(shù)闹担叟袛囝}］*

對

錯（正確答案）

19.在執(zhí)行冒泡排序時，不需要借助輔助空間［判斷題］*

對

錯（正確答案）

20.堆是一個特殊的完全二叉樹，其根要么比左右子樹都小，要么比左右子樹都大

［判斷題］*

對

錯

21.快速排序每一次不一定能確定一個元素的最終位置［判斷題］*

對

錯(正確答案)

22.算法的基本要求不包括如下()方面的內(nèi)容［單選題］*

A.健壯性和可讀性

B.并行性

C.正確性

D.高效性

23.在帶有頭結(jié)點的單鏈表HL中，要向表頭插入一個由指針p指向的結(jié)點，則執(zhí)

行()［單選題］*

A.p->next=HL->next;HL->next=p;

B.p->next=HL;HL=p;

C.p->next=HL;p=HL;

D.HL=p;p->next=HL;

24.對線性表，在下列哪種情況下應當采用鏈表表示？()［單選題］*

A.經(jīng)常需要隨機地存取元素

B.經(jīng)常需要進行插入和刪除操作

C.表中元素需要占據(jù)一片連續(xù)的存儲空間

D.表中元素的個數(shù)不變

25.一個棧的輸入序列為123,則下列序列中不可能是棧的輸出序列的是()［單選

題］*

A.231

B.321

C.312（正確答案）

D.123

26.二叉樹的第k層的結(jié)點數(shù)最多為（）［單選題］*

A.2*+1

A.

B.2"+1

B.

C.2*-1

C.

D.2川

D.

27.設有n個結(jié)點的無向圖，該圖至少應有（）條邊才能確保是一個連通圖［單選題］

*

A“1（正確答案）

B.n

C.n+l

D.n+2

28.將長度為n的單鏈表鏈接在長度為m的單鏈表之后的算法的時間復雜度為（）

［單選題］*

A.0(1)

B.0(n)

C.O(m)(正確答案)

D.O(m+n)

29.設數(shù)組data［m］作為循環(huán)隊列SQ的存儲空間，front為隊頭指針，rear為隊尾指

針，則執(zhí)行出隊操作后其頭指針front值為()［單選題］*

A.front=front+l

B.front=(front+1)%(m-1)

C.front=(front-1)%m

D.front=(front+1)%m

30.一個非空廣義表的表頭()［單選題］*

A.不可能是子表

B.只能是子表

C.只能是原子

D.可以是子表或原子三確答安)

31.設數(shù)據(jù)結(jié)構A=(D,R),其中D={1,2,3,4},R={r},r={<l,2>,<2,3>,

<3,4>,<4,1>},則數(shù)據(jù)結(jié)構A是()［單選題］*

A.線性結(jié)構

B.樹形結(jié)構

C.圖形結(jié)構

D.集合

32.設某棵二叉樹的中序遍歷序列為ABCD,前序遍歷序列為CABD,則后序遍歷

該二叉樹得到序列為()［單選題］*

A.BADC（正田

B.BCDA

C.CDAB

D.CBDA

33.設某棵二叉樹中有2000個結(jié)點，則該二叉樹的最小高度為（）［單選題］*

A.9

B.10

C.11（正確答案）

D.12

34.設一組初始記錄關鍵字序列（5,2,6,3,8）,以第一個記錄關鍵字5為基準進

行一趟快速排序的結(jié)果為（）［單選題］*

A.2,3,5,8,6

B.3,2,5,8,6

C.3,2,5,6,8（正確答案）

D.2,3,6,5,8

35.下面程序的時間復雜為（）

for（i=l,s=0；i<=n；i++）{t=l；for（j=l；j<=i；j++）t=t*j；s=s+t；}

［單選題］*

Qin）

A.

。廳）

B.（正確答案）

O(rP)

C.

0(n+

D.

36.設有n個待排序的記錄關鍵字，則在堆排序中需要（）個輔助記錄單元［單選

題］*

A.1（正確答案）

B.n

nlog2n

C.

n2*

D.

37.設有5（）0萬個待排序的記錄關鍵字，如果需要用最快的方法選出其中最小的10

個記錄關鍵字，則用下列（）方法可以達到此目的［單選題］*

A.快速排列

B.堆排列（正確答案）

C.歸并排列

D.插入排列

38.設一組初始記錄關鍵字序列為（25,50,15,35,80,85,20,40,36,70）,

其中含有5個長度為2的有序子表，則用歸并排序的方法對該記錄關鍵字序列進行

一趟歸并后的結(jié)果為（）［單選題］*

A.15,25,35,5（）,20,40,80,85,36,70（正確答案）

B.15,25,35,50,80,20,85,40,70,36

C.15,25,35,50,80,85,20,36,40,70

D.15,25,35,50,80,20,36,40,70,85

39.函數(shù)substr("DATASTRUCTURE”，5,9)的返回值為()［單選題］*

A."STRUCTURE”通答案)

B.“DATA”

C."ASTRUCTUR”

D."DATASTRUCTURE”

40.()二叉排序樹可以得到一個從小到大的有序序列［單選題］*

A.先序遍歷

B.中序遍歷(正確答案)

C.后序遍歷

D.層次遍歷

41.設無向圖G中的邊的集合E={(a,b),(a,e),(a,c),(b,e),(e,d),(d,

0,(f,c)},則從頂點a出發(fā)進行深度優(yōu)先遍歷可以得到的一種頂點序列為()

［單選題］*

A.aedfcb

B.acfebd

C.aebcfd

D.aedfbc

42.設有序表中的元素為(13,18,24,35,47,5(),62),則在其中利用二分法查

找值為24的元素需要經(jīng)過()次比較［單選題］*

A.1

B.2

C.3(正確答案)

D.4

43.一個棧依次入棧字符序列為ABCDABCD,當執(zhí)行完PUSH();

PUSH();PUSH();PUSH();POP();PUSH();POP();后，再執(zhí)行POP()；會輸出()【單選題】

*

A.A

B.B

C.C(正確答案)

D.D

44.平衡二叉樹的平衡因子不可能是()［單選題］*

A.-1

B.1

C.0

D.2(正確答案)

45.當一個順序表刪除一個元素時。被刪除元素之后的所有元素均需()一個位置［單

選題］*

A.前移(正確答案)

B.后移

C.跳躍

D.原地不動，不移動

46.數(shù)組的邏輯結(jié)構不同于下列()的邏輯結(jié)構［單選題］*

A.線性表

B.圖(正確答案)

C.隊列

D.棧

47.在n個元素的順序表中查找值為x的元素。

for(i=0;i<L.length;i++)

if()break;

if(i<L.length)

printf(“找到叫；

else

printf(“未找到”)；

[單選題]*

A.L.elem[i]==x(正確答案)

B.L.elem[i]=x

C.i>L.length

D.L.elem[i]>x

48.刪除：在n個元素的順序表中，將第i(ign)個元素刪除。

boolListDelete(SqList&L,inti,DataType&x)

(

if(L.length==0||i<l||i>L.length)returnfalse;//失敗

x=L.elem[i-1];

for(j=i;j<L.length;j++)

L.elemjj-l]=L.elem[j];

___________,

returntrue;//刪除成功

}

[單選題]*

A.L』ength--(正確答案)

B.x=L.elem[j-l]

C.returnfalse

D.L.length++

49.

刪除單鏈表List中第i個位置的數(shù)據(jù)元素。

typedefstructnode(

datatypedata;

structnode*next:

)*LinkList;

intDeleteLinkList(LinkListList,inti)

(

LinkListp,q;

p=GegLinkList(L,i-l);/*p指向第i-1個位置的數(shù)據(jù)元素節(jié)點*/

/*刪除前已經(jīng)檢測過第i個數(shù)據(jù)節(jié)點存在*/

q=p->next;

free(q);/*釋放q*/

retum(l);

)

單選題］*

A.p=q->next;

B.p->next=q->next;

C.p=q;

D.p->next=q

50.請?zhí)顚懲瓿上铝嘘P于入棧的代碼：

boolPush(sqStack&s,ElemTypex)

{if()

returnfalse;

s.data[++s.top]=x;

returntrue;}[單選題]*

A.s.stop==0

B.s.top==Maxsize-l

C.s.top==Maxsize

D.s.top==-1

51.將下列折半查找的代碼補充完整

intBinSearch(SeqListR,KeyTypeK)

{intlow=l,high=n,mid；

while(low<=high)

{mid=(low+high)/2；

if(R[mid].key==K)returnmid；

if(R[mid].key>K)

else

return0；

}

[單選題]*

A.high=mid-1low=mid+l

B.low=mid+1high=mid-l

C.high=midlow=mid

D.low二midhigh=mid

52.下列是在循環(huán)隊列中插入數(shù)據(jù)元素e的算法，請將算法補充完整。

刪除單鏈表List中第i個位置的數(shù)據(jù)元素。

typedefstructnode{

datatypedata;

structnode*next:

}*LinkList;

intDeleteLinkList(LinkListLi)

(

LinkListp,q;

p=GegLinkList(L,i-l);/*p指向第i-1個位置的數(shù)據(jù)元素節(jié)點*/

/*刪除前已經(jīng)檢測過第i個數(shù)據(jù)節(jié)點存在*/

q=p->next;

free(q);/*釋放q*/

retum(l);

}

［單選題］*

A.Q.front++；

B.Q.front=(Q.front+l)%MAXSIZE

C.Q.rear=(Q.rear+l)%MAXSIZE正確答案)

D.Q.re