09級(jí)數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)題完整修正版版

1、一、填空題（每空1分 ）1、組成數(shù)據(jù)的基本單位是（數(shù)據(jù)元素）。2、棧和隊(duì)列的共同點(diǎn)是（只允許在端點(diǎn)處插入和刪除元素）。3、算法設(shè)計(jì)的原則是（正確性）、（可讀性）、（健壯性）及（高效率與存儲(chǔ)量）。4、ADT（Abstract Data Type），即稱(chēng)為（抽象數(shù)據(jù)類(lèi)型），是指一個(gè)數(shù)學(xué)模型及定義在該模型上的一組操作（運(yùn)算）；ADT只考慮數(shù)據(jù)的（類(lèi)型）。5、算法分析的兩個(gè)主要方面是（空間復(fù)雜性）和（時(shí)間復(fù)雜性）。6、所有能輸入到計(jì)算機(jī)中去的描述客觀事物的符號(hào)，稱(chēng)為（數(shù)據(jù)）。7、線性表a是n 個(gè)類(lèi)型相同數(shù)據(jù)元素的有限序列，通常記作（a0,a1,.ai-1,ai,ai+1,.,an）。8、若線性表第一個(gè)

2、元素的存儲(chǔ)地址是102，每個(gè)元素的長(zhǎng)度為4，則第5個(gè)元素的地址是：(118)9、在插入排序、選擇排序、快速排序和歸并排序等方法中，平均查找長(zhǎng)度最小的是：（快速排序）10、線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)是用一組任意的存儲(chǔ)單元存儲(chǔ)線性表的各個(gè)數(shù)據(jù)元素。為了表示線性表中元素的先后關(guān)系，每個(gè)元素除了需要存儲(chǔ)自身的信息外還需保存（直接前驅(qū)元素）或（直接后繼元素）的存儲(chǔ)位置。11、數(shù)據(jù)元素及直接后繼的存儲(chǔ)位置（地址）組成一個(gè)數(shù)據(jù)元素的存儲(chǔ)結(jié)構(gòu)，稱(chēng)為：（指針域）。12、線性結(jié)構(gòu)中元素之間存在（一對(duì)一）關(guān)系,樹(shù)形結(jié)構(gòu)中元素之間存在（一對(duì)多）關(guān)系,圖形結(jié)構(gòu)中元素之間存在（多對(duì)多）關(guān)系。13、數(shù)據(jù)結(jié)構(gòu)是研究數(shù)據(jù)的（物理結(jié)構(gòu)

3、）與（邏輯結(jié)構(gòu)）以及它們之間的相互關(guān)系。14、線性的數(shù)據(jù)結(jié)構(gòu)包括：（線性表）、（棧）、（隊(duì)列）、（數(shù)組）和（串）。15、在一棵高度為k的滿(mǎn)二叉樹(shù)中，結(jié)點(diǎn)總數(shù)為（2k-1）。16、判定一個(gè)棧ST(最多元素為m0)為棧滿(mǎn)的條件是（ST> top= =0）。17、頭結(jié)點(diǎn)是指：（在單鏈表的第一個(gè)結(jié)點(diǎn)之前附設(shè)一個(gè)結(jié)點(diǎn)），稱(chēng)為頭結(jié)點(diǎn)。18、在線性結(jié)構(gòu)中,第一個(gè)結(jié)點(diǎn)（沒(méi)有）前驅(qū)結(jié)點(diǎn),其余每個(gè)結(jié)點(diǎn)有且只有（一個(gè)）個(gè)前驅(qū)結(jié)點(diǎn)；最后一個(gè)結(jié)點(diǎn)（沒(méi)有）后續(xù)結(jié)點(diǎn),其余每個(gè)結(jié)點(diǎn)有且只有（一個(gè)）個(gè)后續(xù)結(jié)點(diǎn)。19、在樹(shù)形結(jié)構(gòu)中,樹(shù)根結(jié)點(diǎn)沒(méi)有（前驅(qū)）結(jié)點(diǎn),其余每個(gè)結(jié)點(diǎn)有且只有（一個(gè)）個(gè)前驅(qū)結(jié)點(diǎn)；葉子結(jié)點(diǎn)沒(méi)有（后繼）結(jié)點(diǎn),

4、其余每個(gè)結(jié)點(diǎn)的后續(xù)結(jié)點(diǎn)可以（任意個(gè)）。20、數(shù)據(jù)結(jié)構(gòu)被形式地定義為（D, R），其中D是(數(shù)據(jù)元素)的有限集合，R是D上的 關(guān)系有限集合。21在各種查找方法中,平均查找長(zhǎng)度與結(jié)點(diǎn)個(gè)數(shù)n無(wú)關(guān)的查法方法是（哈希表查找法）22、哈夫曼樹(shù)是帶權(quán)路徑長(zhǎng)度 最小 的二叉樹(shù)，又稱(chēng)最優(yōu)二叉樹(shù)。23、 數(shù)據(jù)結(jié)構(gòu)被形式地定義為（D, R），其中D是數(shù)據(jù)元素的有限集合，R是D上的關(guān)系 有限集合。二、選擇題（每題1分 ）1、樹(shù)是結(jié)點(diǎn)的集合，它的根結(jié)點(diǎn)數(shù)目是 A 。A)有且只有1 B)1或多于 C)0或1 D)至少22、線性表L=(a1，a2，a3，ai，an)，下列說(shuō)法正確的是 D 。A) 每個(gè)元素都有一個(gè)直接前件和

5、直接后件 B) 線性表中至少要有一個(gè)元素C) 表中諸元素的排列順序必須是由小到大或由大到小 D) 除第一個(gè)元素和最后一個(gè)元素外，其余每個(gè)元素都有一個(gè)且只有一個(gè)直接前件和直接后件3、棧底至棧頂依次存放元素A、B、C、D，在第五個(gè)元素E入棧前，棧中元素可以出棧，則出棧序列可能是 B 。A) ABCED B) DCBEA C) DBCEA D) CDABE4、 n個(gè)頂點(diǎn)的連通圖中邊的條數(shù)至少為 C 。A) 0 B) 1 C) n-1 D) n5、在待排序的元素序列基本有序的前提下，效率最高的排序方法是 A 。A) 冒泡排序 B) 選擇排序 C) 快速排序 D) 歸并排序6、希爾排序?qū)儆?D 。A)

6、交換排序 B) 歸并排序 C) 選擇排序 D) 插入排序7、由個(gè)結(jié)點(diǎn)所構(gòu)成的二叉樹(shù)有 D 種形態(tài)。A）3 B）2 C） 1 D）58、非空的循環(huán)單鏈表head的尾結(jié)點(diǎn)(由p所指向)，滿(mǎn)足 C 。A) pnext=NULL B) p=NULL C) pnext=head D) P=head9、數(shù)據(jù)結(jié)構(gòu)作為計(jì)算機(jī)的一門(mén)學(xué)科，主要研究數(shù)據(jù)的邏輯結(jié)構(gòu)、對(duì)各種數(shù)據(jù)結(jié)構(gòu)進(jìn)行的運(yùn)算，以及 A 。A)數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu) B)計(jì)算方法 C)數(shù)據(jù)映象 D)邏輯存儲(chǔ)10、 n個(gè)頂點(diǎn)的強(qiáng)連通圖的邊數(shù)至少有 C 。A) n-1 B) n(n-1) C) n D) n+l11、循環(huán)鏈表的主要優(yōu)點(diǎn)是 B 。A) 不再需要頭指針

7、了 B) 從表中任一結(jié)點(diǎn)出發(fā)都能訪問(wèn)到整個(gè)鏈表C) 在進(jìn)行插入、刪除運(yùn)算時(shí)，能更好的保證鏈表不斷開(kāi)D) 已知某個(gè)結(jié)點(diǎn)的位置后，能夠容易的找到它的直接前件12、棧和隊(duì)列的共同特點(diǎn)是 C 。A)都是先進(jìn)先出 B)都是先進(jìn)后出 C)只允許在端點(diǎn)處插入和刪除元素 D)沒(méi)有共同點(diǎn)13、己知一個(gè)有序表為(12,18,20,25,29,32,40,62,83,90,95,98)，當(dāng)順序查找值為29和90的元素時(shí)，分別需要 A 次比較才能查找成功。（A）5次和10次 （B）10次和5次 （C）5次和9次 （D）10次和4次14、設(shè)一棵完全二叉樹(shù)具有1000個(gè)結(jié)點(diǎn)，則此完全二叉樹(shù)有 D 個(gè)葉子結(jié)點(diǎn)，度為2的結(jié)點(diǎn)

8、有C 個(gè)。（A）1000 （B）501 （C） 499 （D）500 （E）0 （F）1 15、用鏈表表示線性表的優(yōu)點(diǎn)是 C 。A)便于隨機(jī)存取 B)花費(fèi)的存儲(chǔ)空間較順序存儲(chǔ)少 C)便于插入和刪除操作 D)數(shù)據(jù)元素的物理順序與邏輯順序相同16、下列敘述中正確的是 A 。A) 線性表是線性結(jié)構(gòu) B) 棧與隊(duì)列是非線性結(jié)構(gòu)C) 線性鏈表是非線性結(jié)構(gòu) D) 二叉樹(shù)是線性結(jié)構(gòu)17、深度為5的滿(mǎn)二叉樹(shù)中，葉子結(jié)點(diǎn)的個(gè)數(shù)為 C 。A)32 B)31 C)16 D)1518、一個(gè)棧的入棧序列是a,b,c,d,e,則棧的不可能的輸出序列是 C 。（A） edcba（B）decba（C）dceab （D）abc

9、de19、為了方便插入一個(gè)元素,數(shù)據(jù)結(jié)構(gòu)宜用 B 結(jié)構(gòu)。（A）順序存儲(chǔ) （B）鏈?zhǔn)酱鎯?chǔ) （C） 指針存儲(chǔ) （D）數(shù)組存儲(chǔ)20、拓?fù)渑判蛩惴ㄊ峭ㄟ^(guò)重復(fù)選擇具有0個(gè)前驅(qū)頂點(diǎn)的過(guò)程來(lái)完成的。圖的BFS生成樹(shù)的樹(shù)高比DFS生成樹(shù)的樹(shù)高 A 。（A）小或相等 （B）大或相等 （C）小或不相等 （D）大或不相等21、數(shù)據(jù)結(jié)構(gòu)的三要素是指_ B_。（A）數(shù)據(jù)元素、順序存儲(chǔ)、存儲(chǔ)結(jié)構(gòu)（B）數(shù)據(jù)元素、邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)（C）順序存儲(chǔ)、鏈?zhǔn)酱鎯?chǔ)、存儲(chǔ)結(jié)構(gòu)（D）數(shù)據(jù)元素、邏輯結(jié)構(gòu)、鏈?zhǔn)酱鎯?chǔ)22、己知一個(gè)有序表為(12,18,20,25,29,32,40,62,83,90,95,98),當(dāng)二分查找值為29和90的元素

10、時(shí),分別需要_ C _比較才能查找成功。（A）4次和2次 （B）3次和4次 （C）4次和4次 （D）3次和5次23、在一個(gè)長(zhǎng)度為n的順序表中第i個(gè)元素（1<=i<=n）之前插入一個(gè)元素時(shí)，需向后移動(dòng)_ A _個(gè)元素。（A）ni+1 （B）n+i+1 （C）ni （D） n+1 24、 在一個(gè)單鏈表中，若p所指結(jié)點(diǎn)不是最后結(jié)點(diǎn)，在p之后插入s所指結(jié)點(diǎn)，則執(zhí)行 B （A）s->next=p;p->next=s; （B） s->next=p->next;p->next=s;（C）s->next=p->next;p=s; （D）p->next

11、=s;s->next=p;25、設(shè)有一個(gè)空棧，棧頂指針為1000H(十六進(jìn)制)，現(xiàn)有輸入序列為1，2，3，4，5，經(jīng)過(guò)PUSH,PUSH,POP,PUSH,POP,PUSH,PUSH之后，輸出序列是_ B _。（A）16 （B）23 （C） 28 （D）2026、設(shè)有1000個(gè)無(wú)序的元素,希望用最快的速度挑選出其中前10個(gè)最大的元素，最好用_ B_ _ 排序法。（A）快速排序 （B）堆排序 （C）插入排序 （D）選擇排序27、設(shè)有一批數(shù)據(jù)元素,為了最快的存儲(chǔ)某元素,數(shù)據(jù)結(jié)構(gòu)宜用_ A_結(jié)構(gòu),（A）順序存儲(chǔ) （B）鏈?zhǔn)酱鎯?chǔ) （C） 指針存儲(chǔ) （D）數(shù)組存儲(chǔ)28、一棵具有個(gè)結(jié)點(diǎn)的完全二叉樹(shù)，

12、它的深度為_(kāi) D_。（A）6 （B）7 （C） 8（D）929、一個(gè)有n個(gè)頂點(diǎn)的無(wú)向圖最多有_C_條邊。（A）n(n-1) （B）n /2 （C） n(n-1)/2 （D） (n-1)/230、在計(jì)算機(jī)中，算法是指_B_A)加工方法 B)解題方案的準(zhǔn)確而完整的描述 C)排序方法 D)查詢(xún)方法31. 引入二叉線索樹(shù)的目的是（A）A加快查找結(jié)點(diǎn)的前驅(qū)或后繼的速度 B為了能在二叉樹(shù)中方便的進(jìn)行插入與刪除C為了能方便的找到雙親 D使二叉樹(shù)的遍歷結(jié)果唯一32設(shè)無(wú)向圖的頂點(diǎn)個(gè)數(shù)為n，則該圖最多有（B）條邊。An-1 Bn(n-1)/2 C n(n+1)/2 D0 En233下面哪一方法可以判斷出一個(gè)有向圖

13、是否有環(huán)（B）： A廣度優(yōu)先遍歷 B. 拓?fù)渑判?C. 求最短路徑 D. 求關(guān)鍵路徑34、設(shè)計(jì)一個(gè)判別表達(dá)式中左，右括號(hào)是否配對(duì)出現(xiàn)的算法，采用_D_數(shù)據(jù)結(jié)構(gòu)最佳。A線性表的順序存儲(chǔ)結(jié)構(gòu) B. 隊(duì)列 C. 線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) D. 棧35、已知一棵二叉樹(shù)的前序遍歷結(jié)果為ABCDEF,中序遍歷結(jié)果為CBAEDF,則后序遍歷的結(jié)果為_(kāi)A_。ACBEFDA B FEDCBA C CBEDFA D不定36、數(shù)據(jù)在計(jì)算機(jī)存儲(chǔ)器內(nèi)表示時(shí)，物理地址與邏輯地址相同并且是連續(xù)的，稱(chēng)之為：_C_A. 存儲(chǔ)結(jié)構(gòu) B. 邏輯結(jié)構(gòu) C. 順序存儲(chǔ)結(jié)構(gòu) D. 鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)37、 廣度優(yōu)先遍歷類(lèi)似于二叉樹(shù)的_D_ 。A先

14、序遍歷 B. 中序遍歷 C. 后序遍歷 D. 層次遍歷38、以下與數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)無(wú)關(guān)的術(shù)語(yǔ)是_D_。A循環(huán)隊(duì)列 B. 鏈表 C. 哈希表 D. 棧39、 設(shè)樹(shù)T的度為4，其中度為1，2，3和4的結(jié)點(diǎn)個(gè)數(shù)分別為4，2，1，1 , 則T中的葉子數(shù)為_(kāi)D_ A5 B6 C7 D8 三、判斷題（ 正確在括號(hào)內(nèi)打“”，錯(cuò)的打“X”。 ）1、線性表在順序存儲(chǔ)時(shí)，邏輯上相鄰的元素未必在存儲(chǔ)的物理位置次序上相鄰（X）2、對(duì)任何數(shù)據(jù)結(jié)構(gòu)鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)一定優(yōu)于順序存儲(chǔ)結(jié)構(gòu)。(X)3、有向圖的鄰接矩陣必定不是對(duì)稱(chēng)矩陣。(X)4、歸并排序要求內(nèi)存量比較大。()5、棧和鏈表是兩種相同的數(shù)據(jù)結(jié)構(gòu)。() 6、線性表在物理存儲(chǔ)

15、空間中也不一定是連續(xù)的。()7、數(shù)據(jù)的邏輯結(jié)構(gòu)是指數(shù)據(jù)在計(jì)算機(jī)內(nèi)的實(shí)際存儲(chǔ)形式。(X) 8、樹(shù)的后根遍歷序列等同于該樹(shù)對(duì)應(yīng)的二叉樹(shù)的中序遍歷。( )9、棧是實(shí)現(xiàn)過(guò)程和函數(shù)等子程序所必需的結(jié)構(gòu)。()10、棧和隊(duì)列的存儲(chǔ)方式只能是鏈接方式。（X）11、線性表在物理存儲(chǔ)空間中也一定是連續(xù)的。（X ）12、棧和隊(duì)列的存儲(chǔ)方式，既可以是順序方式，又可以是鏈?zhǔn)椒绞健?)13、二叉樹(shù)是一般樹(shù)的特殊情形。( )14、棧和隊(duì)列是一種非線性數(shù)據(jù)結(jié)構(gòu)。(X) 15、一棵哈夫曼樹(shù)的帶權(quán)路徑長(zhǎng)度等于其中所有分支結(jié)點(diǎn)的權(quán)值之和。( )16、在中序線索二叉樹(shù)中，每一非空的線索均指向其祖先結(jié)點(diǎn)。( )17、必須把一般樹(shù)轉(zhuǎn)換成

16、二叉樹(shù)后才能進(jìn)行存儲(chǔ)。(X)18、二叉樹(shù)的遍歷只是為了在應(yīng)用中找到一種線性次序。( )19、由一棵二叉樹(shù)的前序序列和后序序列可以唯一確定它。(X)20、數(shù)據(jù)的物理結(jié)構(gòu)是指數(shù)據(jù)在計(jì)算機(jī)內(nèi)的實(shí)際存儲(chǔ)形式。()21、棧和鏈表是兩種不同的數(shù)據(jù)結(jié)構(gòu)。（X）22、數(shù)據(jù)元素是數(shù)據(jù)的最小單位。(X)23、二叉樹(shù)中每個(gè)結(jié)點(diǎn)的兩棵子樹(shù)是有序的。（）24、集合與線性表的區(qū)別在于是否按關(guān)鍵字排序。(X)25、順序存儲(chǔ)方式只能用于存儲(chǔ)線性結(jié)構(gòu)（X）。 26、程序一定是算法。(X)27、一棵哈夫曼樹(shù)的帶權(quán)路徑長(zhǎng)度等于其中所有分支結(jié)點(diǎn)的權(quán)值之和。( )28、鏈表中的頭結(jié)點(diǎn)僅起到標(biāo)識(shí)的作用。(X) 29、健壯的算法不會(huì)因非法

17、的輸入數(shù)據(jù)而出現(xiàn)莫名其妙的狀態(tài)。()30、一個(gè)圖按廣度優(yōu)先搜索法遍歷的結(jié)果是惟一的。(X)四、簡(jiǎn)答題 1、數(shù)據(jù)結(jié)構(gòu)是一門(mén)研究什么內(nèi)容的學(xué)科？ 答：數(shù)據(jù)結(jié)構(gòu)是一門(mén)研究在非數(shù)值計(jì)算的程序設(shè)計(jì)問(wèn)題中，計(jì)算機(jī)的操作對(duì)象及對(duì)象間的關(guān)系和施加于對(duì)象的操作等的學(xué)科。2、設(shè)有一個(gè)二維數(shù)組Amn，假設(shè)A00存放位置在644(10)，A22存放位置在676(10)，每個(gè)元素占一個(gè)空間，問(wèn)A33(10)存放在什么位置？腳注(10)表示用10進(jìn)制表示。 答：設(shè)數(shù)組元素Aij存放在起始地址為L(zhǎng)oc ( i, j ) 的存儲(chǔ)單元中. Loc ( 2, 2 ) = Loc ( 0, 0 ) + 2 * n + 2 = 64

18、4 + 2 * n + 2 = 676. n= ( 676 - 2 - 644 ) / 2 = 15 Loc ( 3, 3 ) = Loc ( 0, 0 ) + 3 * 15 + 3 = 644 + 45 + 3 = 692.3、在結(jié)點(diǎn)個(gè)數(shù)為n (n>1)的各棵樹(shù)中，高度最小的樹(shù)的高度是多少？它有多少個(gè)葉結(jié)點(diǎn)？多少個(gè)分支結(jié)點(diǎn)？高度最大的樹(shù)的高度是多少？它有多少個(gè)葉結(jié)點(diǎn)？多少個(gè)分支結(jié)點(diǎn)？ 答：結(jié)點(diǎn)個(gè)數(shù)為n時(shí)，高度最小的樹(shù)的高度為2，有2層； 它有n -1個(gè)葉結(jié)點(diǎn)，1個(gè)分支結(jié)點(diǎn)； 高度最大的樹(shù)的高度為n ,有n層；它有1個(gè)葉結(jié)點(diǎn)，n-1個(gè)分支結(jié)點(diǎn)。4、用鄰接矩陣表示圖時(shí)，矩陣元素的個(gè)數(shù)與頂點(diǎn)

19、個(gè)數(shù)是否相關(guān)？與邊的條數(shù)是否相關(guān)？ 答：設(shè)圖的頂點(diǎn)個(gè)數(shù)為n(n>1),則鄰接矩陣元素的個(gè)數(shù)為n2，即頂點(diǎn)個(gè)數(shù)的平方，與圖的邊數(shù)無(wú)關(guān)。5、 已知某圖的鄰接表，如何建立該圖的鄰接矩陣？6、如果一棵樹(shù)有n1個(gè)度為1的結(jié)點(diǎn), 有n2個(gè)度為2的結(jié)點(diǎn), , nm個(gè)度為m的結(jié)點(diǎn), 試問(wèn)有多少個(gè)度為0的結(jié)點(diǎn)? 試推導(dǎo)之。 答：總結(jié)點(diǎn)數(shù) n = n0 + n1 + n2 + + nm總分支數(shù) e = n-1 = n0 + n1 + n2 + + nm-1= m*nm + (m-1)*nm-1 + + 2*n2 + n1則有 n0=1+0*n1+1*n2+2*n3+.(m-1)*nm7、有n個(gè)頂點(diǎn)的無(wú)向連通

20、圖至少有多少條邊？有n個(gè)頂點(diǎn)的有向強(qiáng)連通圖至少有多少條邊？試舉例說(shuō)明 答：n個(gè)頂點(diǎn)的無(wú)向連通圖至少有n-1條邊,n個(gè)頂點(diǎn)的有向強(qiáng)連通圖至少有n條邊.例如:特例情況是當(dāng)n = 1時(shí),此時(shí)至少有0條邊.8、簡(jiǎn)述分塊查找算法的思想。答：（1）首先查找索引表 ，索引表是有序表，可采用二分查找或順序查找，以確定待查的結(jié)點(diǎn)在哪一塊。 （2）然后在已確定的塊中進(jìn)行順序查找 由于塊內(nèi)無(wú)序，只能用順序查找。9、什么是AOV網(wǎng)的關(guān)鍵路徑？ 答：用頂點(diǎn)表示活動(dòng)，用弧表示活動(dòng)間的優(yōu)先關(guān)系的有向圖，叫頂點(diǎn)表示活動(dòng)的網(wǎng)，簡(jiǎn)稱(chēng)AOV網(wǎng)，在AOV-網(wǎng)中路徑長(zhǎng)度最長(zhǎng)的路徑叫關(guān)鍵路徑。10、試分別找出滿(mǎn)足以下條件的所有二叉樹(shù):(

21、1) 二叉樹(shù)的前序序列與中序序列相同;(2) 二叉樹(shù)的中序序列與后序序列相同;(3) 二叉樹(shù)的前序序列與后序序列相同。 答：1) 二叉樹(shù)的前序序列與中序序列相同：空樹(shù)或缺左子樹(shù)的單支樹(shù)；(2) 二叉樹(shù)的中序序列與后序序列相同：空樹(shù)或缺右子樹(shù)的單支樹(shù)；(3) 二叉樹(shù)的前序序列與后序序列相同：空樹(shù)或只有根結(jié)點(diǎn)的二叉樹(shù)。11、數(shù)據(jù)結(jié)構(gòu)與數(shù)據(jù)類(lèi)型有什么區(qū)別？ 答：“數(shù)據(jù)結(jié)構(gòu)”這一術(shù)語(yǔ)有兩種含義，一是作為一門(mén)課程的名稱(chēng)；二是作為一個(gè)科學(xué)的概念。作為科學(xué)概念，目前尚無(wú)公認(rèn)定義，一般認(rèn)為，討論數(shù)據(jù)結(jié)構(gòu)要包括三個(gè)方面，一是數(shù)據(jù)的邏輯結(jié)構(gòu)，二是數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)，三是對(duì)數(shù)據(jù)進(jìn)行的操作（

22、運(yùn)算）。而數(shù)據(jù)類(lèi)型是值的集合和操作的集合，可以看作是已實(shí)現(xiàn)了的數(shù)據(jù)結(jié)構(gòu)，后者是前者的一種簡(jiǎn)化情況。12、一棵度為2的樹(shù)與一棵二叉樹(shù)有何區(qū)別？ 答：一棵度為二的有序樹(shù)與一棵二叉樹(shù)的區(qū)別在于:有序樹(shù)的結(jié)點(diǎn)次序是相對(duì)于另一結(jié)點(diǎn)而言的，如果有序樹(shù)中的子樹(shù)只有一個(gè)孩子時(shí)，這個(gè)孩子結(jié)點(diǎn)就無(wú)須區(qū)分其左右次序，而二叉樹(shù)無(wú)論其孩子數(shù)是否為2，均需確定其左右次序，也就是說(shuō)二叉樹(shù)的結(jié)點(diǎn)次序不是相對(duì)于另一結(jié)點(diǎn)而言而是確定的。13、對(duì)于有n個(gè)頂點(diǎn)的無(wú)向圖，采用鄰接矩陣表示，如何判斷以下問(wèn)題： 圖中有多少條邊？任意兩個(gè)頂點(diǎn)i和j之間是否有邊相連？任意一個(gè)頂點(diǎn)的度是多少？ 答：1）若有n個(gè)非零值，則邊為n/2條邊。（2）設(shè)

23、鄰接矩陣為A，若aij=1，則i,j有邊直接相連；若aik=1，akj=1則經(jīng)過(guò)k有邊直接相連。（3）統(tǒng)計(jì)以該點(diǎn)為行的非零元素個(gè)數(shù)。14、求網(wǎng)的最小生成樹(shù)有哪些算法？各適用于哪些情況？為什么？ 答：有普里姆算法和克魯斯卡爾算法。1）普里姆算法的時(shí)間復(fù)雜度為O(n2),與網(wǎng)中的邊無(wú)關(guān)，因此適用于求邊稀疏的網(wǎng)的生成樹(shù)。2）克魯斯卡爾算法恰恰相反，他的時(shí)間復(fù)雜度為O(eloge)(e為網(wǎng)中的邊數(shù))，因此它相對(duì)于普里姆算法而言，適合于求邊稀疏的網(wǎng)的最小生成樹(shù)。15、簡(jiǎn)述順序查找法，折半（二分）查找法和分塊查找法對(duì)被查找表中元素中的要求。答：1）順序查找法：表中元素可以任意次序存入。2）二分查找法：表中

24、元素必須以關(guān)鍵字的大小遞增或遞減的次序有序列且順序表存儲(chǔ)。3）分塊查找法：表中元素塊內(nèi)的元素可以任意次序存放，但塊與塊之間必須以關(guān)鍵字的大小遞增（或遞減）存放，即前一塊內(nèi)所有元素的關(guān)鍵字都不能大（或?。┯诤笠粔K內(nèi)任何元素的關(guān)鍵字。 16、 一棵高度為h的滿(mǎn)k叉樹(shù)有如下性質(zhì): 第h層上的結(jié)點(diǎn)都是葉結(jié)點(diǎn), 其余各層上每個(gè)結(jié)點(diǎn)都有k棵非空子樹(shù), 如果按層次自頂向下, 同一層自左向右, 順序從1開(kāi)始對(duì)全部結(jié)點(diǎn)進(jìn)行編號(hào), 試問(wèn):(1) 各層的結(jié)點(diǎn)個(gè)數(shù)是多少?(2) 編號(hào)為i的結(jié)點(diǎn)的父結(jié)點(diǎn)(若存在)的編號(hào)是多少?(3) 編號(hào)為i的結(jié)點(diǎn)的第m個(gè)孩子結(jié)點(diǎn)(若存在)的編號(hào)是多少?(4) 編號(hào)為i的結(jié)點(diǎn)有右兄弟的

25、條件是什么? 其右兄弟結(jié)點(diǎn)的編號(hào)是多少? 答：(1) ki ( i = 0, 1, , h ) (2) (3) ( i-1)*k + m + 1 (4) ( i-1 ) % k ¹ 0 或 時(shí)有右兄弟，右兄弟為i + 1。17、在單鏈表中設(shè)置頭結(jié)點(diǎn)的作用是什么？ 【答案】主要是使插入和刪除等操作統(tǒng)一，在第一個(gè)元素之前插入元素和刪除第一個(gè)結(jié)點(diǎn)不必另作判斷。另外，不論鏈表是否為空，鏈表頭指針不變。18、一個(gè)有序表是采用鏈?zhǔn)酱鎯?chǔ)的，那么你能采用什么樣的查找技術(shù)從該表中查找某個(gè)給定的關(guān)鍵字？ 【答案】順序查找法進(jìn)行查找。19、 給定一組權(quán)值: 23, 15, 66, 07, 11, 45,

26、33, 52, 39, 26, 58, 試構(gòu)造一棵具有最小帶權(quán)外部路徑長(zhǎng)度的擴(kuò)充4叉樹(shù), 要求該4叉樹(shù)中所有內(nèi)部結(jié)點(diǎn)的度都是4, 所有外部結(jié)點(diǎn)的度都是0。這棵擴(kuò)充4叉樹(shù)的帶權(quán)外部路徑長(zhǎng)度是多少? 20、 設(shè)有序順序表中的元素依次為017, 094, 154, 170, 275, 503, 509, 512, 553, 612, 677, 765, 897, 908。試畫(huà)出對(duì)其進(jìn)行折半搜索時(shí)的二叉搜索樹(shù), 并計(jì)算搜索成功的平均搜索長(zhǎng)度和搜索不成功的平均搜索長(zhǎng)度。 ASLsucc = ASLunsucc = 21、有一份電文中共使用5個(gè)字符：a、b、c、d、e，它們的出現(xiàn)頻率依次為4、7、5、2、

27、4，試畫(huà)出對(duì)應(yīng)的哈夫曼樹(shù)，并求出每個(gè)字符的哈夫曼編碼五、寫(xiě)出下列各題的構(gòu)造過(guò)程： 1、已知一棵二叉樹(shù)的前序遍歷結(jié)果為ABCDEF,中序遍歷結(jié)果為CBAEDF,則構(gòu)造出此二叉樹(shù)并寫(xiě)其后序遍歷的結(jié)果。2、請(qǐng)畫(huà)出下圖所示的樹(shù)所對(duì)應(yīng)的二叉樹(shù) 。12543768 3、設(shè)一棵二叉樹(shù)的先序、中序遍歷序列分別為先序遍歷序列： A B D F C E G H 中序遍歷序列： B F D A G E H C（1）畫(huà)出這棵二叉樹(shù)。 （2）畫(huà)出這棵二叉樹(shù)的后序線索樹(shù)。 （3）將這棵二叉樹(shù)轉(zhuǎn)換成對(duì)應(yīng)的樹(shù)（或森林）。 4、已知一棵二叉樹(shù)的前序遍歷的結(jié)果是ABECDFGHIJ, 中序遍歷的結(jié)果是EBCDAFHIGJ, 試畫(huà)

28、出這棵二叉樹(shù)。 5、設(shè)無(wú)向網(wǎng)絡(luò)圖G的鄰接矩陣的上三角部分如下表，請(qǐng)回答：（1） 畫(huà)出該網(wǎng)絡(luò)圖； （2） 求該網(wǎng)絡(luò)圖的最小生成樹(shù)(只要給出生成樹(shù)即可)； （3） 給出從頂點(diǎn)V5出發(fā)深度優(yōu)先搜索遍歷該圖的頂點(diǎn)序列（頂點(diǎn)標(biāo)號(hào)小者優(yōu)先）。 V1 V2 V3 V4 V5 V6 V7 V1 18 23 4 6 V2 5 8 12 V3 10 G: V4 15 V5 25 V6 7 V7 6、假定用于通信的電文僅由8個(gè)字母c1, c2, c3, c4, c5, c6, 組成, 各字母在電文中出現(xiàn)的頻率分別為5, 25, 3, 6, 10, 11,。試為這6個(gè)字母設(shè)計(jì)不等長(zhǎng)Huffman編碼, 并給出該電文的

29、總碼數(shù)。 7、給定權(quán)值集合15, 03, 14,20，02, 06, 09, 16, 17, 構(gòu)造相應(yīng)的霍夫曼樹(shù), 并計(jì)算它的帶權(quán)外部路徑長(zhǎng)度。 8、設(shè)有數(shù)據(jù)邏輯結(jié)構(gòu)為：B = (K, R), K = k1, k2, , k9R=<k1, k3>, <k1, k8>, <k2, k3>,<k2, k4>, <k2, k5>, <k3, k9>,<k5, k6>, <k8, k9>, <k9, k7>, <k4, k7>, <k4, k6>（1）畫(huà)出這個(gè)邏輯結(jié)構(gòu)的圖

30、示。 （2）相對(duì)于關(guān)系R, 指出所有的開(kāi)始結(jié)點(diǎn)和終端結(jié)點(diǎn)。 （3）分別對(duì)關(guān)系R中的開(kāi)始結(jié)點(diǎn)，舉出一個(gè)拓?fù)湫蛄械睦印?（4）分別畫(huà)出該邏輯結(jié)構(gòu)的正向鄰接表和逆向鄰接表。 9、已知序列503，61， 512，87，122，908，170，897，275，請(qǐng)給出采用快速排序法對(duì)該序列作升序排列時(shí)每一趟的結(jié)果。（5分）10已知一個(gè)無(wú)向圖如下圖所示，要求用普魯姆算法算法生成最小樹(shù) V2V0V3V5V4V1365216554611、請(qǐng)寫(xiě)出如下無(wú)向連通圖的最小生成樹(shù)，寫(xiě)出prim算法執(zhí)行過(guò)程示意圖。263566455V3V2V5V6V4V1112、對(duì)如下圖所示的二叉樹(shù)進(jìn)行遍歷，分別畫(huà)出先序、中序、后序線索

31、二叉樹(shù)的邏輯表示圖。六、算法分析題 1、簡(jiǎn)述以下關(guān)于二叉樹(shù)某操作的算法的功能和主要思想。 typedef struct BiTNode char data ; / 結(jié)點(diǎn)信息是字符 struct BiTNode *lchild,*rchild; / 左右孩子指針 *BiTree;Status xxxx (BiTree T, Status(*Visit)(char e) TStack S; BiTree p; InitStack(S); if(T) Push(S,T); while (!StackEmpty(S) Pop(S,p); Visit(p->data); if(p->lchi

32、ld) Push(S,p->lchild); if(p->rchild) Push(S,p->rchild); return OK; 2、一線性表存儲(chǔ)在帶頭結(jié)點(diǎn)的雙向循環(huán)鏈表中，L為頭指針，算法如下。說(shuō)明該算法的功能。 void unknown (BNODETP *L) p=L->next; q=p->next; r=q->next；while (q!=L) while (p!=L) && (p->data>q->data) p=p->prior；q->prior->next=r；r->prior=q

33、->prior；q->next=p->next；q->prior=p；p->next->prior=q；p->next=q; q=r；p=q->prior；r=r->next;或r=q->next;3、分析下列算法，并簡(jiǎn)述其功能。 void conversion( ) InitStack(s); scanf(“%d”,&x); while(x!=0) push(s, x% 8); x=x/8; while(! StackEmpty(s) ) /輸出存放在棧中 x=pop(s); printf(“%d”,x); 4、寫(xiě)出以下遞歸

34、算法功能 。typedef struct BiTNode char data ; / 結(jié)點(diǎn)信息是字符 struct BiTNode *lchild,*rchild; / 左右孩子指針 *BiTree;Status exchangelr(BiTree &T) / 算法用函數(shù)名 exchangelr 表示BiTree p; / 臨時(shí)工作指針叉樹(shù)某操作的算法的功能和主要思想。 . / 待完成的若干語(yǔ)句；Status exchangelr(BiTree &T) / 算法用函數(shù)名 exchangelr 表示BiTree p; / 臨時(shí)工作指針if(!T) return OK; / 待完成

35、的若干語(yǔ)句；else p = T->lchild; T->lchild = T->rchild; T->rchild = p; exchangelr(T->lchild); exchangelr(T->rchild);5、簡(jiǎn)述以下兩個(gè)算法的功能并指出這兩個(gè)算法在算法思想上的主要區(qū)別是什么。 typedef struct ElemType *elem; int length; int listsize; SqList; (1) Status DK1(SqList &a, int i, int k) int j, count; if (i<1 |

36、k<0 | i+k > a.length) return INFEASIBLE; /參數(shù)不合法 else for (count = 0; count < k; count+) for (j = i; j < a.length; j+) a.elemj-1 = a.elemj;a.length-; return OK; / DK1 (2) Status DK2(SqList &a, int i, int k) int count; if (i<1 | k<0 | i+k > a.length) return INFEASIBLE; / 參數(shù)不合法

37、 else for (count = 0; count < a.length-(i+1); count+) a.elemi-1+count = a.elemi+k-1+count; a.length -= k; return OK; / DK2 6、簡(jiǎn)述以下算法的功能 void MergeList_L(LinkList &La,LinkList &Lb,LinkList &Lc)        pa=La->next; pb=Lb->next;