青島科技大學(xué)數(shù)據(jù)結(jié)構(gòu)與算法分析期末復(fù)習(xí)題及參考答案

一單選題（共38題，總分值76）

1.以下說法正確的是（D）

A.數(shù)據(jù)元素是數(shù)據(jù)的最小單位

B,數(shù)據(jù)項(xiàng)是數(shù)據(jù)的基本單位

C.數(shù)據(jù)結(jié)構(gòu)是帶有結(jié)構(gòu)的各數(shù)據(jù)項(xiàng)的集合

D.一些表面上很不相同的數(shù)據(jù)可以有相同的邏輯結(jié)構(gòu)

2.n個(gè)頂點(diǎn)的連通圖用鄰接距陣表示時(shí)，該距陣至少

有（B）個(gè)非零元素

A.n

B.2（n-l）

C.n/2

D.nA2

3.下面（D）方法可以判斷出一個(gè)有向圖是否有

環(huán)。

A.深度優(yōu)先遍歷

B.求關(guān)鍵路徑

C.求最短路徑

D.拓?fù)渑判?/p>

4.在一個(gè)有127個(gè)元素的順序表中插入一個(gè)新元素并

保持原來順序不變，平均要移動(dòng)的元素個(gè)數(shù)為

B)

A.8

B.63.5

C.63.7

5.在長度為n的順序表的第i（lWiWn+l）個(gè)位置上插

入一個(gè)元素，移動(dòng)元素的個(gè)數(shù)為（D）

A.i-1

B.n-i

C.i

D.n-i+1

6.n（n〉=2）個(gè)權(quán)值均不相同的字符構(gòu)成哈夫曼樹，關(guān)于

該樹的敘述中，錯(cuò)誤的是（）

A.該樹一定是一顆完全二叉樹

B.樹中一定沒有度為1的結(jié)點(diǎn)

C.樹中兩個(gè)權(quán)值最小的結(jié)點(diǎn)一定是兄弟結(jié)點(diǎn)

D.樹中任一非葉結(jié)點(diǎn)的權(quán)值一定不小于下一層任一結(jié)

點(diǎn)的權(quán)值

7.設(shè)哈希表長為14,哈希函數(shù)是H（key）=key機(jī)1,表中

已有數(shù)據(jù)的關(guān)鍵字為15,38,61,84共四個(gè)，現(xiàn)

要將關(guān)鍵字為49的結(jié)點(diǎn)加到表中，用二次探測(cè)再

散列法解決沖突，則放入的位置是（A）

A.9

B.3

C.5

D.8

8.若讓元素1,2,3,4,5依次進(jìn)棧，則出棧次序不

可能出現(xiàn)在（B）種情況

A.5,4,3,2,1

B.4,3,1,2,5

C.2,1,5,4,3

D.2,3,5,4,1

9.某二叉樹的前序序列和后序序列正好相反，則該二

叉樹一定是（C）的二叉樹。

A.空或只有一個(gè)結(jié)點(diǎn)

B.任一結(jié)點(diǎn)無左子樹

C.高度等于其結(jié)點(diǎn)數(shù)

D.任一結(jié)點(diǎn)無右子樹

10.一個(gè)遞歸算法必須包括（B）

A.遞歸部分

B.終止條件和遞歸部分

C.迭代部分

D.終止條件和迭代部分

11.下列（A）數(shù)據(jù)結(jié)構(gòu)是操作受限的線性表。

A.隊(duì)列

B.數(shù)組

C.線索二叉樹

D.集合

12.以下與數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)無關(guān)的術(shù)語是（C）

A.順序隊(duì)列

B.鏈表

C.有序表

D.鏈棧

13.對(duì)于一棵具有n個(gè)結(jié)點(diǎn)的樹，分支個(gè)數(shù)為

（I））

A.n

B.不確定

C.n+1

D.n-1

14.若一個(gè)棧的輸入序列為1,2,3,…,n,輸出序列的

第一個(gè)元素是i,則第j個(gè)輸出元素是（B）

A.i-j-1

B.不確定的

C.j-i+1

D.i-j

15.下面程序段的時(shí)間復(fù)雜度為（B）

for（inti=0;i<m;i++）

for(intj=0;j<n;j++)

a[i][j]=i*j;

A.0(m2)

B.O(m*n)

C.0(n2)

D.O(m+n)

16.單鏈表的存儲(chǔ)密度(C)

A.大于1

B.等于1

C.小于1

D,不能確定

17.在數(shù)據(jù)結(jié)構(gòu)中，從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分成

(C)

A.動(dòng)態(tài)結(jié)構(gòu)和靜態(tài)結(jié)構(gòu)

B.緊湊結(jié)構(gòu)和非緊湊結(jié)構(gòu)

C.線性結(jié)構(gòu)和非線性結(jié)構(gòu)

D,內(nèi)部結(jié)構(gòu)和外部結(jié)構(gòu)

18.算法的時(shí)間復(fù)雜度取決于(D)

A.問題的規(guī)模

B.待處理數(shù)據(jù)的初態(tài)

C.計(jì)算機(jī)的配置

D.A和B

19.以下哪一個(gè)術(shù)語與數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)無關(guān)？

(A)

A.棧

B.哈希表

C.線索樹

D.雙向鏈表

20.一個(gè)向量第一個(gè)元素的存儲(chǔ)地址是100,每個(gè)元素

的長度為2,則第5個(gè)元素的地址是(B)

A.110

B.108

C.100

D.120

21.若某線性表最常用的操作是存取任意指定序號(hào)的元

素和在最后進(jìn)行插入和刪除運(yùn)算，則利用

(B)存儲(chǔ)方式最節(jié)省時(shí)間。

A.雙鏈表

B.順序表

C.帶頭結(jié)點(diǎn)的雙循環(huán)鏈表

D.單循環(huán)鏈表

22.通常要求同一邏輯結(jié)構(gòu)中的所有數(shù)據(jù)元素具有相同

的特性，這意味著(B)

A.數(shù)據(jù)具有同一特點(diǎn)

B.不僅數(shù)據(jù)元素所包含的數(shù)據(jù)項(xiàng)的個(gè)數(shù)要相同，而且

對(duì)應(yīng)數(shù)據(jù)項(xiàng)的類型要一致

C.每個(gè)數(shù)據(jù)元素都一樣

D.數(shù)據(jù)元素所包含的數(shù)據(jù)項(xiàng)的個(gè)數(shù)要相等

23.以下陳述錯(cuò)誤的是（D）

A.求表長、定位這兩種運(yùn)算在采用順序存儲(chǔ)結(jié)構(gòu)時(shí)實(shí)

現(xiàn)的效率不比采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)時(shí)實(shí)現(xiàn)的效率低

B.順序存儲(chǔ)的線性表可以隨機(jī)存取

C.由于順序存儲(chǔ)要求連續(xù)的存儲(chǔ)區(qū)域，所以在存儲(chǔ)管

理上不夠靈活

D.線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)優(yōu)于順序存儲(chǔ)結(jié)構(gòu)

24.數(shù)據(jù)結(jié)構(gòu)的存儲(chǔ)結(jié)構(gòu)可以分為（D）類。

A.初等結(jié)構(gòu)、構(gòu)造型結(jié)構(gòu)

B.順序結(jié)構(gòu)、鏈?zhǔn)浇Y(jié)構(gòu)

C.動(dòng)態(tài)結(jié)構(gòu)、靜態(tài)結(jié)構(gòu)

D.線性結(jié)構(gòu)、樹形結(jié)構(gòu)、圖形結(jié)構(gòu)、集合

25.以下數(shù)據(jù)結(jié)構(gòu)中，（A）是非線性數(shù)據(jù)結(jié)

構(gòu)。

A.樹

B.字符串

C.對(duì)列

D.棧

26.算法是指(A)

A.解決問題的有限運(yùn)算序列

B.解決問題的計(jì)算方法

C.計(jì)算機(jī)程序

D.排序算法

27.適用于折半查找的表的存儲(chǔ)方式及元素排列要求為

(D)

A.鏈接方式存儲(chǔ)，元素?zé)o序

B.鏈接方式存儲(chǔ)，元素有序

C.順序方式存儲(chǔ)，元素?zé)o序

D.順序方式存儲(chǔ)，元素有序

28.設(shè)棧S和隊(duì)列Q的初始狀態(tài)為空，元素el、e2、

e3、e4、e5和e6依次進(jìn)入棧S,一個(gè)元素出棧后

即進(jìn)入Q，若6個(gè)元素出隊(duì)的序列是e2、e4、e3、

e6、e5和el,則棧S的容量至少應(yīng)該是

(D)

A.2

B.6

C.4

D.3

29.線性表L=(al,a2,……an),下列說法正確的是

D)

A.每個(gè)元素都有一個(gè)直接前驅(qū)和一個(gè)直接后繼

B.線性表中至少有一個(gè)元素

C.表中諸元素的排列必須是由小到大或由大到小

D.除第一個(gè)和最后一個(gè)元素外，其余每個(gè)元素都有一

個(gè)且僅有一個(gè)直接前驅(qū)和直接后繼

30.n個(gè)頂點(diǎn)的連通圖中至少含有（B）條邊。

A.n

B.n-1

C.n（n-l）/2

D.n（n-l）

31.在下列存儲(chǔ)形式中，（B）不是樹的存儲(chǔ)形

式？

A.雙親表示法

B.順序存儲(chǔ)表示法

C.孩子兄弟表示法

D.孩子鏈表表示法

32.下列陳述中正確的是（A）

A.二叉樹中最多只有兩棵子樹，并且有左右之分

B.二叉樹中結(jié)點(diǎn)只有一個(gè)孩子時(shí)無左右之分

C.二叉樹中必有度為2的結(jié)點(diǎn)

D.二叉樹是度為2的有序樹

33.完全二叉樹的結(jié)點(diǎn)個(gè)數(shù)11,則它的葉子結(jié)點(diǎn)個(gè)數(shù)

為(A)

A.6

B.3

C.4

D.5

34.在一個(gè)具有n個(gè)單元的順序棧中，假設(shè)以地址低端

作為棧底，以top作為棧頂指針，則當(dāng)作進(jìn)棧處理

時(shí)，top的變化為(D)

A.top不變

B.top=0

C.top-

D.top++

35.在單鏈表中，要將s所指結(jié)點(diǎn)插入到p所指結(jié)點(diǎn)之

后，其語句應(yīng)為(D)

A.s->next=p+l

B.p->next=s

C.(*p).next=s

D.(*s).next=(*p).next

E.s->next=p->next

F.p->next=s->next

G.s->next=p->next

H.p->next=s

36.圖的深度優(yōu)先遍歷類似于二叉樹的（A）

A.先序遍歷

B.中序遍歷

C.后序遍歷

D.層序遍歷

37.AVL樹是一種平衡的二叉排序樹，樹中任一結(jié)點(diǎn)的

（A）

A.左、右子樹高度差的絕對(duì)值不超過1

B.左、右子樹的高度均相同

C.左子樹的高度均大于右子樹的高度

D.左子樹的高度均小于右子樹的高度

38.在n個(gè)結(jié)點(diǎn)的順序表中，算法的時(shí)間復(fù)雜度是0（1）

的操作是（A）

A.訪問第i個(gè)結(jié)點(diǎn)（lvivn）和求第i個(gè)結(jié)點(diǎn)的直接前驅(qū)

（2<i<n）

B.在第i個(gè)結(jié)點(diǎn)后插入一個(gè)新結(jié)點(diǎn)（lSiSn）

C.刪除第i個(gè)結(jié)點(diǎn)（BiSn）

D.將n個(gè)結(jié)點(diǎn)從小到大排序

二判斷（共20題，總分值40）

39.算法的優(yōu)劣與算法描述語言無關(guān)，但與所用計(jì)算機(jī)

有關(guān)。（）（F）

40.連通分量指的是有向圖中的極大連通子圖。

（）（F）

41.順序存儲(chǔ)方式的優(yōu)點(diǎn)是存儲(chǔ)密度大，且插入、刪除

運(yùn)算效率高。（）（F）

42.在n個(gè)結(jié)點(diǎn)的無向圖中，若邊數(shù)大于nT,則該圖

必是連通圖。（）（F）

43.數(shù)據(jù)元素是數(shù)據(jù)的基本單位。（）

（T）

44.樹形結(jié)構(gòu)的特點(diǎn)是一對(duì)多。（）（T）

45.圖形結(jié)構(gòu)的特點(diǎn)是一對(duì)多,樹形結(jié)構(gòu)的特點(diǎn)是多對(duì)

多。（）（F）

46.無向圖的鄰接矩陣一定是對(duì)稱的。（）

（T）

47.完全二叉樹一定存在度為1的結(jié)點(diǎn)。（)

（F）

48.冒泡法排序排序趟數(shù)與序列的原始狀態(tài)有關(guān)。

()(T)

49.集合與線性表的區(qū)別在于是否按關(guān)鍵字排序。

()(F)

50.棧和隊(duì)列的存儲(chǔ)方式，既可以是順序方式，又可以

是鏈?zhǔn)椒绞健?)(T)

51.查找相同結(jié)點(diǎn)的效率折半查找總比順序查找高。

()(F)

52.隊(duì)列和棧都是操作受限的線性表。()

(T)

53.隨機(jī)稀疏矩陣壓縮存儲(chǔ)后，必會(huì)失去隨機(jī)存取功

能。()(T)

54.隊(duì)列是一種插入與刪除操作分別在表的兩端進(jìn)行的

線性表，是一種先進(jìn)后出型結(jié)構(gòu)。()

(F)

55.二叉排序樹是一種動(dòng)態(tài)查找樹。()

(T)

56.鏈表中的頭結(jié)點(diǎn)僅起到標(biāo)識(shí)作用。（）

（F）

57.完全二叉樹中，若一個(gè)結(jié)點(diǎn)沒有左孩子，則它必是

樹葉。（）（T）

58.堆肯定是一棵平衡二叉樹。（）（T）

三計(jì)算題（共10題，總分值20）

59.設(shè)一棵二叉樹的先序序

歹U：ABDFCEGH,中序序

歹（J：BFDAGEHC

（1）畫出這棵二叉樹。

（2）寫出這棵二叉樹的后序序列和層次遍歷序

列。

答案：FDBGHECA（4分）

ABCDEFGH（4分）

60.閱讀下列算法，并回答下列問題：

voidInsertSort（SqList&L）{

for（i=2;i<=L.length;++i）

if(L.r[i].key<L.r[i-l].key){

L.r[0]=L.r[i];

for(j=i-

1；L.r[0].key<L.r[j].key;-j)

L.r[j+1]=L.r[jJ;

L.r[j+1]=L.r[0];

)

}//InsertSort

(1)該算法采用何種策略進(jìn)行排序？

(2)這種排序方法的穩(wěn)定性如何？

(3)寫出用此種排序方法對(duì)關(guān)鍵字序列{49,38,

65,97,76,13,27}排序的過程。

答案：(1)直接插入排序(3分)

(2)穩(wěn)定(3分)

(3)(6分)

初始：(49),38,65,97,76,13,27

第一趟：(38)(38,49),65,97,76,13,

27

第二趟：(65)(38,49,65),97,76,13,

27

第三趟：(97)(38,49,65,97)，76,13,

27

第四趟：(76)(38,49,65,76,97),13,

27

第五趟:(13)(13,38,49,65,76,97),

27

第六趟：(27)(13,27,38,49,65,76,

97）

結(jié)果：13,27,38,49,65,76,97

61.回答下列問題：（1）什么是數(shù)據(jù)結(jié)構(gòu)？（2）對(duì)于

數(shù)據(jù)結(jié)構(gòu)一般包含哪三個(gè)方面的討論？（3）在編

制管理通訊錄的程序時(shí)，通訊錄數(shù)據(jù)采用什么樣的

數(shù)據(jù)結(jié)構(gòu)合適？（4）對(duì)于第（3）問，存儲(chǔ)結(jié)構(gòu)采

用什么樣的結(jié)構(gòu)合適？為什么？

答案：（1）數(shù)據(jù)結(jié)構(gòu)就是數(shù)據(jù)之間存在著一種或多種特

定關(guān)系的數(shù)據(jù)元素的集合（4分）。（2）邏輯結(jié)

構(gòu)、存儲(chǔ)結(jié)構(gòu)和操作（運(yùn)算）。（3分）（3）線性

結(jié)構(gòu)。（2分）（4）要分情況而定，如果僅僅進(jìn)行查

詢操作，那么可以采用順序表，如果經(jīng)常進(jìn)行插入

和刪除操作，那么采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。（3分）

62.寫出用按層次順序遍歷二叉樹的方法，統(tǒng)計(jì)樹中葉

子結(jié)點(diǎn)數(shù)目的算法。

答案：?intLevel(BiTree*bt)

?{intnum=O;

〃num統(tǒng)計(jì)度為1的結(jié)點(diǎn)的個(gè)數(shù)

?if(bt){

?Queuelnit(Q);Queuein(Q,bt)；〃Q是以二

叉樹結(jié)

?點(diǎn)指針為元素的隊(duì)列

while(!QueueEmpty(Q))

?{p=QueueOut(Q);printf(p-

>data);〃出隊(duì),訪問結(jié)點(diǎn)

?if(p->lchild&&!p->rchildI|!p-

>lchild&&p->rchild)

?num++;

〃度為1的結(jié)點(diǎn)

?if(p->lchild)Queuein(Q,p->lchild);//

非空左子女入隊(duì)

?if(p->rchild)Queuein(Q,p->rchild);//

非空右子女入隊(duì)

?}}//if(bt)

,return(num);

63.寫出將兩個(gè)遞增的有序鏈表合并為一個(gè)遞增的有序

鏈表的算法。要求結(jié)果鏈表仍使用原來兩個(gè)鏈表的

存儲(chǔ)空間，不另外占用其它的存儲(chǔ)空間，表中不允

許有重復(fù)的數(shù)據(jù)

答案：(1)合并后的新表使用頭指針Lc指向，pa和

pb分別是鏈表La和Lb的工作指針,初始化為相應(yīng)

鏈表的第一個(gè)結(jié)點(diǎn)，從第一個(gè)結(jié)點(diǎn)開始進(jìn)行比較，

當(dāng)兩個(gè)鏈表La和Lb均為到達(dá)表尾結(jié)點(diǎn)時(shí)，依次摘

取其中較小者重新鏈接在Lc表的最后。如果兩個(gè)

表中的元素相等，只摘取La表中的元素，刪除Lb

表中的元素，這樣確保合并后表中無重復(fù)的元素。

當(dāng)一個(gè)表到達(dá)表尾結(jié)點(diǎn)，為空時(shí).，將非空表的剩余

元素直接鏈接在Lc表的最后。

(2)voidMergeList(LinkList&La,LinkLi

st&Lb,LinkList&Lc)

{〃合并鏈表La和Lb,合并后的新表使用頭指針

Lc指向pa=La->next;pb=Lb->next;

//pa和pb分別是鏈表La和Lb的工作指針，

初始化為相應(yīng)鏈表的第一個(gè)結(jié)點(diǎn)Lc=pc=La;//

用La的頭結(jié)點(diǎn)作為Lc的頭結(jié)點(diǎn)while(pa&&pb)

{if(pa->data<pb->data){pc-

>next=pa;pc=pa;pa=pa->next;}

//取較小者La中的元素，將pa鏈接在pc的

后面，pa指針后移elseif(pa->data>pb-

>data){pc->next=pb;pc=pb;pb=pb->next;)

//取較小者Lb中的元素，將pb鏈接在pc

的后面，pb指針后移else〃相等時(shí)取La中的元

素，刪除Lb中的元素{pc->next=paRLpaipHpa-

Anext;

qz:pb->next;deletepb;pb=q;

}

}

pc->next=pa?pa:pb;〃插入剩余段

deleteLb;〃釋放Lb

的頭結(jié)點(diǎn)}

64.數(shù)據(jù)結(jié)構(gòu)是什么？算法是什么？試分析下列程序段

的漸近時(shí)間復(fù)雜度：

x=90;y二100;

while(y>0)

if(x>100)

{x=xT0;y—;}

elsex++;

答案：數(shù)據(jù)結(jié)構(gòu)就是數(shù)據(jù)之間存在著一種或多種特定關(guān)

系的數(shù)據(jù)元素的集合(4分)。算法是為了解決某

類問題而規(guī)定的一個(gè)有限長的操作序列(4分)。0

(1)(4分)。

65.寫出創(chuàng)建一個(gè)的單鏈表的算法。

答案：

voidCreateList_L(LinkList&L,intn){

//逆序輸入n個(gè)數(shù)據(jù)元素，建立帶頭結(jié)點(diǎn)

的單鏈表

L=(LinkList)malloc(sizeof(LNode));

L->next=NULL;//先建立一個(gè)帶頭

結(jié)點(diǎn)的單鏈表

for(i=n;i>0;-i){

p二(LinkList)malloc(sizeof(LNod

e));

scanf(&p->data);//輸入元素

值

p->next=