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

1、一是非題1.數(shù)據(jù)結(jié)構(gòu)(應(yīng)該是抽象數(shù)據(jù)類型)可用三元式表示(D，S，P)。其中：D是數(shù)據(jù)對象，S是D上的關(guān)系，P是對D的基本操作集。(f)2簡單地說數(shù)據(jù)結(jié)構(gòu)是帶有結(jié)構(gòu)的數(shù)據(jù)元素的集合。(t)3判斷帶頭結(jié)點(diǎn)的非空循環(huán)單鏈表(頭指針為L)中指針p所指結(jié)點(diǎn)是最后一個(gè)元素結(jié)點(diǎn)的條件是：pnext==L。(t)4線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)具有可直接存取表中任一元素的優(yōu)點(diǎn)。(f)5線性表的順序存儲(chǔ)結(jié)構(gòu)優(yōu)于鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。(f)6.在單鏈表P指針?biāo)附Y(jié)點(diǎn)之后插

2、入S結(jié)點(diǎn)的操作是：Pnext=SSnext=Pnext。(f)(順序弄反了Snext=PnextPnext=S)7對于插入、刪除而言，線性表的鏈?zhǔn)酱鎯?chǔ)優(yōu)于順序存儲(chǔ)。(t)8.順序存儲(chǔ)方式的優(yōu)點(diǎn)是存儲(chǔ)密度大，且插入、刪除運(yùn)算效率高。(f)9.棧和隊(duì)列是操作上受限制的線性表。(t)10.隊(duì)列是與線性表完全不同的一種數(shù)據(jù)結(jié)構(gòu)。(f)(棧和隊(duì)列是操作上受限制的線性表)11.隊(duì)列是一種操作受限的線性表，凡對數(shù)據(jù)元素的操作僅限一端進(jìn)行。(f)(兩端

3、)12.棧和隊(duì)列也是線性表。如果需要，可對它們中的任一元素進(jìn)行操作。(f)(“如果需要可對它們中的任一元素進(jìn)行操作.”這里的意思是在O(1)的時(shí)間來讀和改某個(gè)元素。比如數(shù)組的直接索引。棧：如果需要，每一次只能對棧頂?shù)脑剡M(jìn)行操作隊(duì)列：如果需要，每一次只能對兩端，或者只能對隊(duì)列頭的元素進(jìn)行操作。)13.棧是限定僅在表頭進(jìn)行插入和表尾進(jìn)行刪除運(yùn)算的線性表。(f)14.二叉樹中每個(gè)結(jié)點(diǎn)有兩個(gè)子結(jié)點(diǎn)，而對一般的樹，則無此限制，所以，二叉樹是樹的

4、特殊情形。(f)(二叉樹和樹相互獨(dú)立)15二叉樹是一棵結(jié)點(diǎn)的度最大為二的樹。(f)(二叉樹和樹相互獨(dú)立)16赫夫曼樹中結(jié)點(diǎn)個(gè)數(shù)一定是奇數(shù)。(t)17在二叉樹的中序遍歷序列中，任意一個(gè)結(jié)點(diǎn)均處在其左孩子結(jié)點(diǎn)的后面。(t)(LDR)18假設(shè)B是一棵樹，B′是對應(yīng)的二叉樹。則B的后根遍歷相當(dāng)于B′的后序遍歷。(f)(后根遍歷相當(dāng)于中序遍歷)19.通常，二叉樹的第i層上有2i1個(gè)結(jié)點(diǎn)。(f)(應(yīng)該為1~2i1個(gè))20.中序線索二叉樹的優(yōu)點(diǎn)是便于

5、在中序下查找直接前驅(qū)結(jié)點(diǎn)和直接后繼結(jié)點(diǎn)。(t)21二叉樹的先序遍歷序列中，任意一個(gè)結(jié)點(diǎn)均處在其孩子結(jié)點(diǎn)的前面。(t)22由樹結(jié)點(diǎn)的先根序列和后根序列可以唯一地確定一棵樹。(t)23鄰接多重表可以用以表示無向圖，也可用以表示有向圖。(f)(只能表示無向圖，有向圖用十字鏈表)24可從任意有向圖中得到關(guān)于所有頂點(diǎn)的拓?fù)浯涡颉?f)(帶環(huán)圖沒有)25有向圖的十字鏈表是將鄰接表和逆鄰接表合二為一的鏈表表示形式。(t)C.Lnext==LD.L!=

6、null4若順序表中各結(jié)點(diǎn)的查找概率不等，則可用如下策略提高順序查找的效率：若找到指定的結(jié)點(diǎn)，將該結(jié)點(diǎn)與其后繼(若存在)結(jié)點(diǎn)交換位置，使得經(jīng)常被查找的結(jié)點(diǎn)逐漸移至表尾。以下為據(jù)此策略編寫的算法，請選擇適當(dāng)?shù)膬?nèi)容，完成此功能。順序表的存儲(chǔ)結(jié)構(gòu)為：typedefstructElemTypeelem數(shù)據(jù)元素存儲(chǔ)空間，0號(hào)單元作監(jiān)視哨intlength表長度SSTableintsearch_seq(SSTableSTKeyTypekey)在順序

7、表ST中順序查找關(guān)鍵字等于key的數(shù)據(jù)元素。若找到，則將該元素與其后繼交換位置，并返回其在表中的位置，否則為0。ST.elem[0].key=keyi=ST.lengthwhile(ST.elem[i].key!=key)fif(G)ST.elem[i]←→ST.elem[i1]；e；returniA.i0B.i=0C.iST.lengthD.i=ST.lengthE.iF.iG.A和C同時(shí)滿足H.B和D同時(shí)滿足5若入棧順序?yàn)锳、B、C

8、、D、E，則下列(d)出棧序列是不可能的。AA、B、C、D、EBB、C、D、A、ECC、D、B、E、ADD、E、C、A、B6遞歸程序可借助于(c)轉(zhuǎn)化為非遞歸程序。a.線性表b.隊(duì)列c:棧d.數(shù)組7在下列數(shù)據(jù)結(jié)構(gòu)中(c)具有先進(jìn)先出(FIFO)特性，(b)具有先進(jìn)后出(FILO)特性。a線性表b棧c隊(duì)列d廣義表8若對編號(hào)為1，2，3的列車車廂依次通過扳道棧進(jìn)行調(diào)度，不能得到(e)的序列。a:123b:132c:213d:231e:312

9、f:3219在計(jì)算遞歸函數(shù)時(shí)，如不用遞歸過程，應(yīng)借助于(b)這種數(shù)據(jù)結(jié)構(gòu)。A.線性表B.棧C.隊(duì)列D.雙向隊(duì)列10若帶頭結(jié)點(diǎn)的鏈表只設(shè)尾結(jié)點(diǎn)指針。下列選擇中(c)最適用于隊(duì)列。A)單鏈表B)雙向鏈表C循環(huán)單鏈表D)雙向循環(huán)鏈表11棧和隊(duì)列的一個(gè)共同點(diǎn)是(c)。A.都是先進(jìn)先出B.都是先進(jìn)后出C.只允許在端點(diǎn)處插入和刪除元素D.沒有共同點(diǎn)12循環(huán)隊(duì)列用數(shù)組A[0..m1]存放其元素值，設(shè)頭尾指針分別為front和rear，則當(dāng)前隊(duì)列中的元