2021杭州電子科技大學《數(shù)據(jù)結構》試卷含答案

2021《數(shù)據(jù)結構》復習及答案

一.是非題

(正確的打“J”，錯誤的打“X”。)

1.數(shù)據(jù)結構可用三元式表示(D,S,P)。其中：D是數(shù)據(jù)對象，S是D上的關系，

P是對D的基本操作集。X

2.線性表的鏈式存儲結構具有可直接存取表中任一元素的優(yōu)點。X

3.字符串是數(shù)據(jù)對象特定的線性表。

4.二叉樹是一棵結點的度最大為二的樹。X

5.鄰接多重表可以用以表示無向圖，也可用以表示有向圖。X

6.可從任意有向圖中得到關于所有頂點的拓撲次序。X

7.一棵無向連通圖的生成樹是其極大的連通子圖。X

8.二叉排序樹的查找長度至多為logzn。X

9.對于一棵m階的B一樹.樹中每個結點至多有m個關鍵字。除根之外的所有非終端結點至

少有「m/2r個關鍵字。X

10.對于目前所知的排序方法，快速排序具有最好的平均性能。

11.順序存儲方式的優(yōu)點是存儲密度大，且插入、刪除運算效率高。X

12.二維數(shù)組是其數(shù)據(jù)元素為線性表的線性表.

13.連通圖G的生成樹是一個包含G的所有n個頂點和n-1條邊的子圖。X

14.折半查找不適用于有序鏈表的查找。

15.完全二叉樹必定是平衡二叉樹。

16.中序線索二叉樹的優(yōu)點是便于在中序下查找直接前驅(qū)結點和直接后繼結點。

17.隊列是與線性表完全不同的一種數(shù)據(jù)結構。X

18.平均查找長度與記錄的查找概率有關。

19.二叉樹中每個結點有兩個子結點，而對一般的樹，則無此限制，所以，二叉樹是樹的

特殊情形。X

20.算法的時間復雜性越好，可讀性就越差；反之，算法的可讀性越好，則時間復雜性就越

差。X

二.選擇題

1.若廣義表LS滿足GetHead(LS)==GetTail(LS),則LS為(b)。

A.()B.(())C.((),())D.((),(),())

3.在下列數(shù)據(jù)結構中(c)具有先進先出(FIFO)特性，(b)具有先進后出(FILO)

特性。

a:線性表b:棧c:隊列d:廣義表

4.假設用于通訊的電文僅由6個字符組成，字母在電文中出現(xiàn)的頻率分別為7,19,22,6,

32,14。若為這6個字母設計哈夫曼編碼(設生成新的二叉樹的規(guī)則是按給出的次序從左

至右的結合，新生成的二叉樹總是插入在最右），則頻率為7的字符編碼是（g）,頻率為

32的字符編碼是（c）。

a:00b:01c:10d:11

e:Oilf:110g:1110h:llll

5.對二叉排序樹按（c）可得到有序序列。

a:層次遍歷b:前序遍歷c:中序遍歷d:后序遍歷

6.已知某樹的先根遍歷次序為abcdefg,后根遍歷次序為cdebgfa。若將該樹轉(zhuǎn)換為二叉

樹，其后序遍歷次序為（d）。

a:abcdefgb:cdebgfac:cdegbfad:edcgfba

7.對一棵完全二叉樹進行層序編號。則編號為n的結點若存在右孩子，其編號是（d）。

編號為n的結點若存在雙親，其編號是（a）。

a:n/2b:2nc:2n-ld:2n+le:nf:2（n+l）

8.關鍵路徑是指在只有一個源點和一個匯點的有向無環(huán)網(wǎng)中源點至匯點（c）的路徑。

a:弧的數(shù)目最多b:弧的數(shù)目最少c:權值之和最大d:權值之和最小

9.哈希表的查找效率取決于（d）0

a:哈希函數(shù)b:處理沖突的方法。c:哈希表的裝填因子。d:以上都是

10.從邏輯上可以把數(shù)據(jù)結構分成（c）。

a:動態(tài)結構和靜態(tài)結構b:順序組織和鏈接組織

c:線性結構和非線性結構d:基本類型和組合類型

11.在計算遞歸函數(shù)時，如不用遞歸過程,應借助于（b）這種數(shù)據(jù)結構。

a:線性表b:棧c:隊列d:雙向隊列

12.若已知某二叉樹的中序和后序遍歷序列分別BCAEFD和CBFEDA,則該二叉樹的先序

序列為（a）。

a:ABCDEFb:ABDCEFc:ABDCFEd:ACBDFE

13.當待排序序列的關鍵字次序為倒序時，若需為之進行正序排序，下列方案中（d）為佳。

a:起泡排序b:快速排序

c:直接插入排序d:簡單選擇排序

14.若從二叉樹的根結點到其它任一結點的路徑上所經(jīng)過的結點序列按其關鍵字遞增有序,

則該二叉樹是（c）o

a:二叉排序樹b:赫夫曼樹c:堆d:平衡二叉樹

15.下圖所有可能的拓撲序列有（b）種。

16.下列排序算法中，（d）算法可能會出現(xiàn)：初始數(shù)據(jù)為正序時，花費的時間反而最多。

a:堆排序b:起泡排序c:歸并排序d:快速排序

18.設森林F中有三棵樹，第一、第二和第三棵樹的結點個數(shù)分別為ml、m2和m3,則與

森林F對應的二叉樹根結點的右子樹上的結點個數(shù)是（d）。

a:mlb:ml+m2c:m3d:m2+m3

19.根據(jù)插入次序（80,90,100,110,85,70,75,60,72）建立二叉排序樹。圖（a）

是最終變化的結果。若仍以該插入次序建立平衡二叉樹?圖（c）是最終變化的結果。

c:d:

9090

2。設輸入序列為20,45,30,89,70,38,62,19,依次插入到一棵2-3樹中（初始狀態(tài)為空）,

該B-樹為（b）o再刪除38,該B-樹為（f）。

(1920)(38)(62)(89)

21.已知一組待排序的記錄關鍵字初始排列如下：45,34,87,25,67,43,11,66,27,78。

g）是快速排序法一趟排序的結果；

a）是希爾排序法（初始步長為4）一趟排序的結果;

(b)是初始堆(大堆頂)；

(d)是基數(shù)排序法一趟排序的結果。

a：27,34,11,25,45,43,87,66,67,78b:87,78,45,66,67,43,11,25,27,34

c:11,43,34,25,45,66,27,67,87,78d:ll,43,34,45,25,66,87,67,27,78

e:34,45,25,67,43,11,66,27,78,87f:87,45,11,25,34,78,27,66,67,43

g:27,34,11,25,43,45,67,66,87,78h:34,11,27,25,43,78,45,67,66,87

22.若有序表中關鍵字序列為:14,20,25,32,34,45,57,69,77,83,92。對其進行

折半查找，則在等概率情況下，查找成功時的平均查找長度是（c）。查找32時需進行

（C）次比較。

a:1b:2c:3d:4

23.設一棵二叉樹BT的存儲結構如下：

12345678

23006000

ABCDEFGH

05408700

其中Ichild,rchild分別為結點的左、右孩子指針域，data為結點的數(shù)據(jù)域。則

該二叉樹的高度為（d）；

第3層有（a）個結點（根結點為第1層）。

a:2b:3c:4d:5

24.一個連通圖的最小生成樹（b）。

a:只有一棵b:有一棵或多棵c:一定有多棵d:可能不存在

25.若某二叉樹有20個葉子結點，有20個結點僅有一個孩子，則該二叉樹的總結點數(shù)是（c）。

a:40b:55c:59d:61

26.己知哈希表地址空間為A[0..8],哈希函數(shù)為H（k）=kmod7,采用線性探測再散列處理

沖突。若依次將數(shù)據(jù)序列：76,45,88,21,94,77,17存入該散列表中，則元素17存儲的

下標為（f）；在等概率情況下查找成功的平均查找長度為（c）。

a:0b:1c:2d:3

e:4f:5g:6h:7

27.己知某有向圖的鄰接表存儲結構如圖所示。

根據(jù)存儲結構，依教材中的算法其深度優(yōu)先遍歷次序為（d）。

廣度優(yōu)先遍歷次序為（c）。各強連通分量的頂點集為（f）。

a:abcde.b:edcba.c:ecdab.d:ecadb.

e:abc及edf:ac及bedg:ab及cedh:be及aed

28.已知某無向圖的鄰接表如下所示；

（e）是其原圖。

（c）是按該鄰接表遍歷所得深度優(yōu)先生成樹。

（d）是按該鄰接表遍歷所得廣度優(yōu)先生成樹。

a

b

c

d1512Ai14rg"n

ei514?r^~~n

f-I1I4?l3II

a:a---b

!\I

29.設有二維數(shù)組A5X7,每一元素用相鄰的4個字節(jié)存儲，存儲器按字節(jié)編址。

已知A的起始地址為100。則按行存儲時，元素Aoe的存儲地址是(d)；

按列存儲時，元素A06的存儲地址是(a)。

a.220b.200c.140d.124

30.若順序表中各結點的查找概率不等，則可用如下策略提高順序查找的效率：若找到指定

的結點，將該結點與其后繼(若存在)結點交換位置，使得經(jīng)常被查找的結點逐漸移至

表尾。以下為據(jù)此策略編寫的算法，請選擇適當?shù)膬?nèi)容，完成此功能。

順序表的存儲結構為：

typedefstruct{

ElemType*elem;〃數(shù)據(jù)元素存儲空間，0號單元作監(jiān)視哨

intlength;〃表長度

}SSTable;

intsearch_seq(SSTableST,KeyTypekey)

{〃在順序表ST中順序查找關鍵字等于key的數(shù)據(jù)元素。

〃若找到，則將該元素與其后繼交換位置，并返回其在表中的位置，否則為0。

ST.elem[0].key=key;

i=ST.length;

while(ST.elem[i],key!=key)f;

if(g)

{ST.elem[i]'--*ST.elem[i+l]；

)

returni;

)

a:i>0b:i>=0c:i<ST.lengthd:i<=ST.length

e:i++f:i—g:A和C同時滿足h:B和D同時滿足

31.若對編號為1,2,3的列車車廂依次通過扳道棧進行調(diào)度，不能得到(e)的序列。

a:1,2,3b:l,3,2c:2,1,3d:2,3,1e:3,1,2f:3,2,1

32.遞歸程序可借助于(b)轉(zhuǎn)化為非遞歸程序。

a:線性表b:棧c:隊列d:數(shù)組

33.對字符串s='data-structure'執(zhí)行操作replace(s,substring(s,6,8),'bas')

的結果是(d)。

a:"databaseJb:'data-base'c:'bas'd:<data-basucture,

34.設有二維數(shù)組Asc,每一元素用相鄰的4個字節(jié)存儲，存儲器按字節(jié)編址。

已知A的起始地址為100。則按行存儲時，元素A06的第一個字節(jié)的地址是(d)

按列存儲時，元素即6的第一個字節(jié)的地址是(a)

a:220b:200c:140d:124

35.對廣義表A=((a,(b)),(c,()),d)執(zhí)行操作gettail(gethead(gettail(A)))

的結果是：(b)。

a:()b:(())c:dd:(d)

36.下列函數(shù)為堆排序中的堆調(diào)整過程(調(diào)整II.r[s]的關鍵字，使II.r[s..而成為一小頂堆)。

請在“”處填上合適的內(nèi)容,完成該算法。

Voidheapadjust(heaptype&H,ints,intm){

rc=H.r[s];

for(j=2*s;j<=m;j*=2){

if(j<m&&)++j;

if()break;

H.r[s]=H.r[j];s=j;

}//heapadjust

a:(H.r[j].key>H.key);

b:!(rc.key<H.r[j].key);

c:(H.r[j].key<H,r[j+l].key);

d:!(rc.key>H.r[j].key);

e:H.r[s]=rc;

f:rc=H.r[s];

g:h.r[j]=rc;

h:rc=H.r[j];

三.算法設計題

1.單鏈表結點的類型定義如下：

typedefstructLNode)

intdata;

structLNode*nexl;

}LNode,*Linklist;

寫一算法，Contrarydinklist&L),對一帶頭結點且僅設尾指針L的循環(huán)單鏈表

就地逆置。(即表頭變表尾，表尾變表頭。)

voidContrary(linklist&L)

{p=L->next;q=L;

while(p!=L)

{r=p->next;p->n