數(shù)據(jù)結(jié)構(gòu) 習(xí)題答案

千里之行，始于足下讓知識(shí)帶有溫度。第第2頁(yè)/共2頁(yè)精品文檔推薦數(shù)據(jù)結(jié)構(gòu)習(xí)題答案第1章概論

1.數(shù)據(jù)結(jié)構(gòu)是一門(mén)討論非數(shù)值計(jì)算的程序設(shè)計(jì)問(wèn)題中,數(shù)據(jù)元素的①Ｃ、數(shù)據(jù)信息在計(jì)算機(jī)中的②A以及一組相關(guān)的運(yùn)算等的課程。

①A．操作對(duì)象Ｂ．計(jì)算辦法Ｃ．規(guī)律結(jié)構(gòu)Ｄ．?dāng)?shù)據(jù)映象

②A．存儲(chǔ)結(jié)構(gòu)Ｂ．關(guān)系Ｃ．運(yùn)算Ｄ．算法

2.計(jì)算機(jī)算法指的是①C，它必具備輸入、輸出和②B等五個(gè)特性。

①A.計(jì)算辦法B.排序辦法

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

D.調(diào)度辦法

②A.可行性、可移植性和可擴(kuò)充性B.可行性、確定性和有窮性

C.確定性、有窮性和穩(wěn)定性

D.易讀性、穩(wěn)定性和平安性

3.下面程序段的時(shí)光復(fù)雜度是D

for(i=0;inext=p；p->next=s；

B.s->next=p->next；p->next=s；

C.s->next=p->next；p=s；

D.p->next=s；s->next=p；

2.非空的不帶頭結(jié)點(diǎn)的循環(huán)單鏈表，首結(jié)點(diǎn)由first指向，尾結(jié)點(diǎn)由p指向，則滿足：

C

A.p->next==NULL；

B.p==NULL；

C.p->next==first；

D.p==first；

3.在一個(gè)長(zhǎng)度為n的挨次存儲(chǔ)的線性表中，刪除第i個(gè)元素（0≤i≤n-1）時(shí)，需要移動(dòng)多少個(gè)元素？C

A.n-i

B.n-i+1

C.n-i-1

D.I

4.在帶頭結(jié)點(diǎn)指針head的單鏈表中，鏈表為空的推斷條件是？B

A.head==NULL

B.head->next==NULL

C.head!=NULL

D.head->next==head；

5.在單鏈表中，指針p指向元素為x的結(jié)點(diǎn)，實(shí)現(xiàn)“刪除x的后繼”的語(yǔ)句是B

A.p=p->next;

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

C.p->next=p;

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

6.在雙鏈表中刪除某個(gè)結(jié)點(diǎn)p，實(shí)現(xiàn)的語(yǔ)句是A

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

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

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

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

7.在雙鏈表中給定結(jié)點(diǎn)p之后插入一個(gè)新結(jié)點(diǎn)s，實(shí)現(xiàn)的語(yǔ)句是C

A.s->next=p->next;s->prior=p;p->prior=s;p->next=s;

B.p->next=s;s->next=p->next;s->prior=p;p->next->prior=s;

C.s->next=p->next;s->prior=p;p->next->prior=s;p->next=s;

D.s->next=p->next;s->prior=p;p->next=s;p->prior=s;

8.在雙鏈表中，每個(gè)結(jié)點(diǎn)有兩個(gè)指針域，一個(gè)指向前驅(qū)結(jié)點(diǎn)，另一個(gè)指向后繼結(jié)點(diǎn)。

9.在線性結(jié)構(gòu)中，第一個(gè)結(jié)點(diǎn)沒(méi)有前驅(qū)結(jié)點(diǎn)，其余每個(gè)結(jié)點(diǎn)有且惟獨(dú)1個(gè)前驅(qū)結(jié)點(diǎn)；最后一個(gè)結(jié)點(diǎn)沒(méi)有后續(xù)結(jié)點(diǎn)，其余每個(gè)結(jié)點(diǎn)有且惟獨(dú)1個(gè)后續(xù)結(jié)點(diǎn)。

第3章棧和隊(duì)列

1.引起循環(huán)隊(duì)列頭位置發(fā)生變化的操作是？A

A.出對(duì)

B.入對(duì)

C.取對(duì)頭元素

D.取對(duì)尾元素

2.若進(jìn)棧序列為1，2，3，4，下面哪一個(gè)序列不行能是這個(gè)棧的輸出序列？C

A.1，3，2，4

B.2，3，4，1

C.4，3，1，2

D.3，4，2，1

3.若進(jìn)棧序列為1，2，3，4，5，6，且進(jìn)棧和出?？梢源┎迮e行，則可能浮現(xiàn)的出棧序列

為B

A．3，2，6，1，4，5B．3，4，2，1，6，5

C．1，2，5，3，4，6D．5，6，4，2，3，1

4.一個(gè)隊(duì)列的數(shù)據(jù)入隊(duì)序列是1，2，3，4，則隊(duì)列的出隊(duì)時(shí)輸出序列是？B

A.4，3，2，1

B.1，2，3，4

C.1，4，3，2

D.3，2，4，1

5.棧的兩種常用存儲(chǔ)結(jié)構(gòu)分離為A

A．挨次存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)B．挨次存儲(chǔ)結(jié)構(gòu)和散列存儲(chǔ)結(jié)構(gòu)

C．鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)和索引存儲(chǔ)結(jié)構(gòu)D．鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)和散列存儲(chǔ)結(jié)構(gòu)

6.已知循環(huán)隊(duì)列的存儲(chǔ)空間為數(shù)組data[21]，且當(dāng)前隊(duì)列的頭指針和尾指針的值分離為8

和3，則該隊(duì)列的當(dāng)前長(zhǎng)度為C

A．5B．6C．16D．17

7.已知循環(huán)隊(duì)列的存儲(chǔ)空間為數(shù)組data[25]，且當(dāng)前隊(duì)列的頭指針和尾指針的值分離為10

和5，則該隊(duì)列的當(dāng)前長(zhǎng)度為？A

A．20B．25C．10D．15

8.判定一個(gè)循環(huán)隊(duì)列QU（最多元素為m0,m0==Maxsize-1）為滿隊(duì)列的條件是A。

A.((rear-front)+Maxsize)%Maxsize==m0

B.rear-front-1==m0

C.front==rear

D.front==rear+1

9.循環(huán)隊(duì)列用數(shù)組A[0，m-1]存放其元素值，已知其頭尾指針?lè)蛛x是front和rear，則當(dāng)前

隊(duì)列中的元素個(gè)數(shù)是A。

A.(rear-front+m)%m

B.rear-front+1

C.rear-front-1

D.rear-front

10.棧和隊(duì)列都是A

A．限制存取位置的線性結(jié)構(gòu)B．挨次存儲(chǔ)的線性結(jié)構(gòu)

C．鏈?zhǔn)酱鎯?chǔ)的線性結(jié)構(gòu)D．限制存取位置的非線性結(jié)構(gòu)

11.隊(duì)和棧的主要區(qū)分是D

A.規(guī)律結(jié)構(gòu)不同

B.存儲(chǔ)結(jié)構(gòu)不同

C.所包含的運(yùn)算個(gè)數(shù)不同

D.限定插入和刪除的位置不同

12.已知循環(huán)隊(duì)列的存儲(chǔ)空間為數(shù)組data[18]，且當(dāng)前隊(duì)列的頭指針和尾指針的值分離為7和2，則該隊(duì)列的當(dāng)前長(zhǎng)度為？A

A．13B．5C．9D．18

13.向量、棧和隊(duì)列都是線性結(jié)構(gòu)，可以在向量的_任何___位置插入和刪除元素；對(duì)于棧只能在棧頂插入和刪除元素；對(duì)于隊(duì)列只能在隊(duì)尾插入元素和隊(duì)首刪除元素。

第4章串第5章數(shù)組

1.二維數(shù)組A中，每個(gè)元素的長(zhǎng)度為3個(gè)字節(jié)，行下標(biāo)i從0到7，列下標(biāo)j從0到9，從首地址SA開(kāi)頭延續(xù)存放在存儲(chǔ)器內(nèi)，存放該數(shù)組至少需要的字節(jié)數(shù)是C。

A.80

B.100

C.240

D.270

2.二維數(shù)組A中，每個(gè)元素A的長(zhǎng)度為3個(gè)字節(jié)，行下標(biāo)i從0到7，列下標(biāo)j從0到9，從首地址SA開(kāi)頭延續(xù)存放在存儲(chǔ)器內(nèi)，該數(shù)組按行存放時(shí)，數(shù)組元素A[7][4]的起始地址為C。

A.SA+141

B.SA+144

C.SA+222

D.SA+225

3.二維數(shù)組A中，每個(gè)元素A的長(zhǎng)度為3個(gè)字節(jié)，行下標(biāo)i從0到7，列下標(biāo)j從0到9，從首地址SA開(kāi)頭延續(xù)存放在存儲(chǔ)器內(nèi)，該數(shù)組按列存放時(shí)，元素A[4][7]的起始地址為B。

A.SA+141

B.SA+180

C.SA+222

D.SA+225

4.已知二維數(shù)組A[m][n]采納行序?yàn)橹鞣绞酱鎯?chǔ)，每個(gè)元素占k個(gè)存儲(chǔ)單元，并且第一個(gè)元素的存儲(chǔ)地址是LOC(A[0][0])，則A[i][j]的地址是__LOC(A[0][0])+(n*i+j)*k_____。

5.二維數(shù)組A[10][20]采納列序?yàn)橹鞣绞酱鎯?chǔ)，每個(gè)元素占一個(gè)存儲(chǔ)單元并且A[0][0]的存儲(chǔ)地址是200，則A[6][12]的地址是__200+（6*20+12）=326__。

6.二維數(shù)組A[10..20][5..10]采納行序?yàn)橹鞣绞酱鎯?chǔ)，每個(gè)元素占4個(gè)存儲(chǔ)單元，并且A[10][5]的存儲(chǔ)地址是1000，則A[18][9]的地址是_1000+((18-10)*6+(9-5))*4=1208__。

第6章樹(shù)

1.如圖所示的4棵二叉樹(shù)，C不是徹低二叉樹(shù)。

(A)(B)(C)(D)

2.任何一棵二叉樹(shù)的葉子結(jié)點(diǎn)在前序、中序和后序遍歷序列中的相對(duì)次序？B

A.發(fā)生轉(zhuǎn)變

B.不發(fā)生轉(zhuǎn)變

C.不能確定

D.以上都不對(duì)

3.一棵含18個(gè)結(jié)點(diǎn)的二叉樹(shù)的高度至少為C

A.3

B.4

C.5

D.6

4.根據(jù)二叉樹(shù)的定義，具有3個(gè)結(jié)點(diǎn)的不同外形的二叉樹(shù)有幾種？A

A.5

B.4

C.3

D.6

5.對(duì)一個(gè)滿二叉樹(shù)，m個(gè)樹(shù)葉，n個(gè)結(jié)點(diǎn)，深度為h，則?D

A.n=h+m

B.h+m=2n

C.m=h-1

D.n=2h-1

6.一棵二叉樹(shù)中雙分支結(jié)點(diǎn)數(shù)為15，單分支結(jié)點(diǎn)數(shù)為30個(gè)，則葉子結(jié)點(diǎn)數(shù)為16個(gè)。

7.在一棵二叉樹(shù)中，度為零的結(jié)點(diǎn)個(gè)數(shù)為n

0，度為2的結(jié)點(diǎn)個(gè)數(shù)為n

2

，則有n

=n

2

+1。

8.一棵二叉樹(shù)的第i（i≥1）層最多有2i-1個(gè)結(jié)點(diǎn)。

9.已知徹低二叉樹(shù)T的第5層惟獨(dú)7個(gè)結(jié)點(diǎn)，則該樹(shù)共有葉子結(jié)點(diǎn)數(shù)目為11。

10.深度為5的二叉樹(shù)至多有31個(gè)結(jié)點(diǎn)。

11.某二叉樹(shù)的前序遍歷結(jié)果為stuwv，中序遍歷為uwtvs，那么后序遍歷為wuvts。

12.某二叉樹(shù)的前序遍歷為abdgcefh，中序遍歷為dgbaechf，則后序遍歷的為gdbehfca。

13.在樹(shù)型結(jié)構(gòu)中，樹(shù)根結(jié)點(diǎn)沒(méi)有前驅(qū)結(jié)點(diǎn)，其余每個(gè)結(jié)點(diǎn)有且惟獨(dú)1個(gè)直接前驅(qū)結(jié)點(diǎn)，葉子結(jié)點(diǎn)沒(méi)有后繼結(jié)點(diǎn)，其余每個(gè)結(jié)點(diǎn)的直接后繼結(jié)點(diǎn)可以隨意多個(gè)。

14.有一棵樹(shù)如圖所示，回答下面的問(wèn)題：

⑴這棵樹(shù)的根結(jié)點(diǎn)是__k1__；

⑵這棵樹(shù)的葉子結(jié)點(diǎn)是

_k2,k5,k7,k4___；

⑶結(jié)點(diǎn)k3的度是_2___；

⑷這棵樹(shù)的度是_3___；

⑸這棵樹(shù)的深度是__4__；

⑹結(jié)點(diǎn)k3的子女是__k5,k6__；

⑺結(jié)點(diǎn)k3的父結(jié)點(diǎn)是__k1__；

15.設(shè)字符a,b,c,d,e,f的使用權(quán)值分離是7,9,12,22,23,27，畫(huà)出Huffman樹(shù)，并寫(xiě)出a,b,c,d,e,f的Huffman編碼。

Huffman編碼為

a:1110b:1111c:110d:00e:01f:10

16.設(shè)字符a,b,c,d,e,f,g的使用權(quán)值分離是4，5，6，7，10，12，18，畫(huà)出Huffman樹(shù)，并寫(xiě)出a,b,c,d,e,f,g的Huffman編碼。

Huffman編碼為

a:1100b:1101c:010d:011e:111f:00g:10

17．二叉樹(shù)如圖所示，要求完成如下任務(wù)：

（1）畫(huà)出該二叉樹(shù)的中序線索二叉樹(shù)；（2）畫(huà)出該二叉樹(shù)對(duì)應(yīng)的森林。。

中序線索二叉樹(shù)為：該二叉樹(shù)對(duì)應(yīng)的森林為：

18．已知二叉樹(shù)的先序序列和中序序列分離為HDACBGFE和ADCBHFEG。（1）畫(huà)出該二

叉樹(shù)；（2）畫(huà)出（1）中求得的二叉樹(shù)對(duì)應(yīng)的森林。

二叉樹(shù):二叉樹(shù)對(duì)應(yīng)的森林:

19.已知二叉樹(shù)的先序序列和中序序列分離為ABDEGCFH和DBGEACFH。（1）畫(huà)出該二叉樹(shù)；（2）畫(huà)出（1）中求得的二叉樹(shù)對(duì)應(yīng)的森林。

二叉樹(shù):二叉樹(shù)對(duì)應(yīng)的森林:

第7章圖

1.在用于表示無(wú)權(quán)有向圖的相鄰矩陣中，對(duì)第j列的非0元素個(gè)數(shù)舉行累加，可得到第j個(gè)頂點(diǎn)的？B

A．出度B．入度C．權(quán)值D．銜接邊個(gè)數(shù)

2.在用于表示無(wú)權(quán)有向圖的相鄰矩陣中，對(duì)第i行的非0元素個(gè)數(shù)舉行累加，可得到第i個(gè)頂點(diǎn)的？A

A．出度B．入度C．權(quán)值D．銜接邊個(gè)數(shù)

3.在一個(gè)圖中，全部頂點(diǎn)的度數(shù)之和等于全部邊數(shù)的幾倍？C

A．1/2B．1C．2D．4

4.假如某圖的相鄰矩陣是對(duì)稱的，則此圖是？D

A.徹低圖

B.連通圖

C.有向圖

D.無(wú)向圖

5.對(duì)于一個(gè)具有n個(gè)結(jié)點(diǎn)和e條邊的無(wú)向圖，若采納鄰接表表示，則鄰接表的存儲(chǔ)單元大小為A

A．n+2eB．nC．eD．n+e

6.在圖型結(jié)構(gòu)中，每個(gè)結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)數(shù)和后續(xù)結(jié)點(diǎn)數(shù)可以隨意多個(gè)。

7.在一個(gè)具有n個(gè)頂點(diǎn)的無(wú)向圖中，要連通所有頂點(diǎn)至少需要n-1條邊。

8.一個(gè)有n個(gè)頂點(diǎn)的無(wú)向圖最多有n(n-1)/2條邊。

9.具有4個(gè)頂點(diǎn)的無(wú)向徹低圖有6條邊。

10.已知有向圖的鄰接矩陣如圖所示，要求完成如下任務(wù)：（1）請(qǐng)畫(huà)出此有向圖；（2）給出該有向圖的鄰接表。

?

????????????

???????

?????

?=00

1

000010000010000000010000000000000000010001001100001000100

A

有向圖為：鄰接表為：

11．已知有向圖的鄰接表如圖所示，要求完成如下任務(wù)：（1）請(qǐng)畫(huà)出此有向圖；（2）給出該有向圖的鄰接矩陣。

有向圖為：鄰接矩陣為：

????????????

?

???????

??????=00

1