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

1、一、選擇題1、一個(gè)n個(gè)頂點(diǎn)的無(wú)向連通圖，其邊的個(gè)數(shù)至少為（ ）。an-1 bn cn+1 dnlogn2、以下數(shù)據(jù)結(jié)構(gòu)中，（ ）是非線性數(shù)據(jù)結(jié)構(gòu)。a樹(shù) b字符串 c隊(duì)列 d棧3、在長(zhǎng)度為n的順序表的第i個(gè)位置上插入一個(gè)元素（1in+1），元素的移動(dòng)次數(shù)為（ ）。an i+1 bn i c i d i-14、與線性表的鏈接存貯不相符合的特性是（ ）。a便于插、刪運(yùn)算 b需要連續(xù)的存貯空間c只能順序查找 d存貯空間動(dòng)態(tài)分配5、順序存放的循環(huán)隊(duì)列的元素以數(shù)組am存放,其頭尾指針?lè)謩e為front和rear，則當(dāng)前隊(duì)列中的元素個(gè)數(shù)為（ ）。a(rear-front+m)%m brear-front+1

2、c(front+rear+m)%m d(rear-front)%m6、一個(gè)有n個(gè)頂點(diǎn)的無(wú)向圖最多有( )條邊。an(n-1)/2 bn (n-1) cn-1 dn+17、設(shè)棧的入棧序列是1，2，3，4，則（ ）不可能是其出棧序列。a1，2，4，3 b2，1，3，4 c1，4，3，2 d4，3，1，2，8、從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分為（ ）兩大類。a動(dòng)態(tài)結(jié)構(gòu)、靜態(tài)結(jié)構(gòu) b初等結(jié)構(gòu)、構(gòu)造型結(jié)構(gòu)c線性結(jié)構(gòu)、非線性結(jié)構(gòu) d樹(shù)型結(jié)構(gòu)、圖型結(jié)構(gòu)9、某二叉樹(shù)的先序序列和后序序列正好相反，則該二叉樹(shù)一定是（ ）a空或只有一個(gè)根結(jié)點(diǎn) b高度等于其結(jié)點(diǎn)數(shù)c任一結(jié)點(diǎn)無(wú)左孩子 d任一結(jié)點(diǎn)無(wú)右孩子10、已知一個(gè)有向圖用鄰

3、接矩陣表示，要?jiǎng)h除所有從第i個(gè)結(jié)點(diǎn)發(fā)出的邊，應(yīng)該（ ）。a將鄰接矩陣的第 i 行刪除 b將鄰接矩陣的第 i 行元素全部置零c將鄰接矩陣的第 i 列刪除 d將鄰接矩陣的第 i 列元素全部置零11、算法分析的兩個(gè)主要方面是（ ）a空間復(fù)雜性和時(shí)間復(fù)雜性 b正確性和簡(jiǎn)明性c可讀性和文檔性 d數(shù)據(jù)復(fù)雜性和程序復(fù)雜性12、線性表若采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)時(shí)，要求內(nèi)存中可用存儲(chǔ)單元的地址( )。a必須是連續(xù)的 b部分地址必須是連續(xù)的c一定是不連續(xù)的 d連續(xù)或不連續(xù)都可以13、具有6個(gè)頂點(diǎn)的無(wú)向連通圖的生成樹(shù)應(yīng)有（ ）條邊。a5 b6 c7 d814、設(shè)棧的輸入序列是a、b、c，則（ ）不可能是其出棧序列。acba

4、 bcab cbca dacb15、有一個(gè)含頭結(jié)點(diǎn)的單鏈表，頭指針為head，則判斷其是否為空的條件為（ ）。ahead=null bhead-next=nullchead-next= head dhead ！=null16、棧和隊(duì)都是（ ）a順序存儲(chǔ)的線性結(jié)構(gòu) b鏈?zhǔn)酱鎯?chǔ)的非線性結(jié)構(gòu)c限制存取點(diǎn)的線性結(jié)構(gòu) d限制存取點(diǎn)的非線性結(jié)構(gòu)17、在下述結(jié)論中，正確的是（ ）只有一個(gè)結(jié)點(diǎn)的二叉樹(shù)的度為0; 二叉樹(shù)的度為2； 二叉樹(shù)的左右子樹(shù)可任意交換;深度為k的完全二叉樹(shù)結(jié)點(diǎn)個(gè)數(shù)小于或等于深度相同的滿二叉樹(shù)。 a b c d18、以下數(shù)據(jù)結(jié)構(gòu)中，（ ）是非線性數(shù)據(jù)結(jié)構(gòu)。a樹(shù) b字符串 c隊(duì)列 d棧19、

5、設(shè)森林f中有三棵樹(shù)，第一，第二，第三棵樹(shù)的結(jié)點(diǎn)個(gè)數(shù)分別為m1，m2和m3。與森林f對(duì)應(yīng)的二叉樹(shù)根結(jié)點(diǎn)的右子樹(shù)上的結(jié)點(diǎn)個(gè)數(shù)是（ ）。am1 bm1+m2 cm3 dm2+m320、在下面的程序段的時(shí)間復(fù)雜度為（ ）。for (int i=1;in;i+) for (int j=1;jn;j+) aij=i*j;ao(m2) bo(m*n) co(n2) do(log2n)21、二叉樹(shù)的第i層上最多含有結(jié)點(diǎn)數(shù)為（ ）a2i b 2i-1-1 c 2i-1 d2i -122、下列排序算法中( )排序在一趟結(jié)束后不一定能選出一個(gè)元素放在其最終位置上。a選擇 b冒泡 c歸并 d堆23、線性表第一個(gè)元素的

6、存儲(chǔ)地址是100,每個(gè)元素的長(zhǎng)度為2,則第5個(gè)元素的地址是( )a110 b 108 c 100 d 12024、棧中元素的進(jìn)出原則是（ ）。先進(jìn)先出 后進(jìn)先出 棧空則進(jìn) 棧滿則出25、下列字符串中（ ）不是串a(chǎn)bcabdeabx的子串。 aa bc bbx c ab dad26、對(duì)稀疏矩陣進(jìn)行壓縮存儲(chǔ)目的是（ ）。 a便于進(jìn)行矩陣運(yùn)算 b便于輸入和輸出 c節(jié)省存儲(chǔ)空間 d降低運(yùn)算的時(shí)間復(fù)雜度27、設(shè)二維數(shù)組a1.5,1.6的每個(gè)元素占5個(gè)存儲(chǔ)單元，將其按行優(yōu)先順序存儲(chǔ)在起始地址是1000的連續(xù)內(nèi)存單元中，則a5,5的存儲(chǔ)地址是（ ）。a1140 b1145 c1120 d112528、外排序

7、是指（ ）。a數(shù)據(jù)量很大，排序時(shí)要借外存進(jìn)行的排序方法 b不需要使用內(nèi)存的排序方法c數(shù)據(jù)量很大，需要人工干預(yù)的排序方法 d沒(méi)有正確答案29、下列數(shù)據(jù)中不可能是平衡二叉樹(shù)上結(jié)點(diǎn)的平衡因子的是（ ）。a-1 b0 c1 d230、在下面的程序段的時(shí)間復(fù)雜度為（ ）。for (int i=1;i m;i+) for (int j=1;jnext=s;s-next=p-next; bs-next=p-next;p-next=s;cp-next=s;p-next=s-next; dp-next=s-next;p-next=s;45、設(shè)棧的輸入序列是1，2，3，4,則（）不可能是其出棧序列。a1，2，4，

8、3， b2，1，3，4， c1，4，3，2， d4，3，1，2， e3，2，1，4，46、棧在（ ）中應(yīng)用。a遞歸調(diào)用 b子程序調(diào)用 c表達(dá)式求值 da，b，c47、下列哪一種圖的鄰接矩陣是對(duì)稱矩陣？（ ）a有向圖 b無(wú)向圖 caov網(wǎng) daoe網(wǎng)48、下述哪一條是順序存儲(chǔ)結(jié)構(gòu)的優(yōu)點(diǎn)？（ a ）a存儲(chǔ)密度大 b插入運(yùn)算方便 c刪除運(yùn)算方便 d可方便地用于各種邏輯結(jié)構(gòu)的存儲(chǔ)表示49、線性表是具有n個(gè)（ c ）的有限序列（n0）。a表元素 b字符 c數(shù)據(jù)元素 d數(shù)據(jù)項(xiàng) e信息項(xiàng)50、輸入序列為abc，可以變?yōu)閏ba時(shí)，經(jīng)過(guò)的棧操作為（ b ）a. push,pop,push,pop,push,po

9、p b. push,push,push,pop,pop,popc. push,push,pop,pop,push,pop d. push,pop,push,push,pop,pop51、從鄰接陣矩可以看出，該圖共有（ ）個(gè)頂點(diǎn)；如果是有向圖該圖共有（ ）條??；如果是無(wú)向圖，則共有（ ）條邊。a9 b3 c6 d1 e以上答案均不正確a5 b4 c3 d2 e以上答案均不正確a5 b4 c3 d2 e以上答案均不正確52、最大容量為n的循環(huán)隊(duì)列，隊(duì)尾指針是rear，隊(duì)頭是front，則隊(duì)滿的條件是（ a ）。a. (rear+1) %n=front b. rear=front crear+1=f

10、ront d. (rear-l) % n=front53、循環(huán)隊(duì)列a0.m-1存放其元素值，用front和rear分別表示隊(duì)頭和隊(duì)尾，則當(dāng)前隊(duì)列中的元素?cái)?shù)是( a )。a. (rear-front+m)%m b. rear-front+1 c. rear-front-1 d. rear-front54、最大容量為n的循環(huán)隊(duì)列，隊(duì)尾指針是rear，隊(duì)頭是front，則隊(duì)空的條件是（ b ）。a. (rear+1) %n=front b. rear=front crear+1=front d. (rear-l) % n=front55、設(shè)樹(shù)t的度為4，其中度為1，2，3和4的結(jié)點(diǎn)個(gè)數(shù)分別為4，2，

11、1，1 則t中的葉子數(shù)為（ c ）a5 b6 c7 d856、有n個(gè)葉子的哈夫曼樹(shù)的結(jié)點(diǎn)總數(shù)為（ d ）。a不確定 b2n c2n+1 d2n-157、有關(guān)二叉樹(shù)下列說(shuō)法正確的是（ a ）a一棵二叉樹(shù)的度可以小于2 b二叉樹(shù)中至少有一個(gè)結(jié)點(diǎn)的度為2 c二叉樹(shù)的度為2 d二叉樹(shù)中任何一個(gè)結(jié)點(diǎn)的度都為258對(duì)一組數(shù)據(jù)（84，47，25，15，21）排序，數(shù)據(jù)的排列次序在排序的過(guò)程中的變化為（1） 84 47 25 15 21 （2） 15 47 25 84 21 （3） 15 21 25 84 47 （4） 15 21 25 47 84 則采用的排序是 ( a )。 a. 選擇 b. 冒泡 c.

12、快速 d. 插入59、對(duì)序列15，9，7，8，20，-1，4進(jìn)行排序，進(jìn)行一趟后數(shù)據(jù)的排列變?yōu)?，9，-1，8，20，7，15；則采用的是（ c ）排序。a. 選擇 b. 快速 c. 希爾 d. 冒泡60、若序列15，9，7，8，20，-1，4經(jīng)一趟排序后的排列為9，15，7，8，20，-1，4，則采用的是（ c ）排序。a選擇 b. 堆 c. 直接插入 d. 冒泡 61、下列排序算法中( b )不能保證每趟排序至少能將一個(gè)元素放到其最終的位置上。a.快速排序 b. shell排序 c. 堆排序 d.冒泡排序 62、下列排序算法中( c )排序在一趟結(jié)束后不一定能選出一個(gè)元素放在其最終位置上。

13、a. 選擇 b. 冒泡 c. 歸并 d. 堆63、以下序列不是堆的是( )。a. (100,85,98,77,80,60,82,40,20,10,66) b. (100,98,85,82,80,77,66,60,40,20,10)c. (10,20,40,60,66,77,80,82,85,98,100) d. (100,85,40,77,80,60,66,98,82,10,20)64、下列四個(gè)序列中，哪一個(gè)是堆（ c ）。a. 75,65,30,15,25,45,20,10 b. 75,65,45,10,30,25,20,15c. 75,45,65,30,15,25,20,10 d. 75,

14、45,65,10,25,30,20,1565、散列文件使用散列函數(shù)將記錄的關(guān)鍵字值計(jì)算轉(zhuǎn)化為記錄的存放地址，因?yàn)樯⒘泻瘮?shù)是一對(duì)一的關(guān)系，則選擇好的（ d ）方法是散列文件的關(guān)鍵。a. 散列函數(shù) b. 除余法中的質(zhì)數(shù) c. 沖突處理 d. 散列函數(shù)和沖突處理參考答案:0110: a a a b a a d c a b1120: a d a b b c d a d c2130: c c b b d c a a d b3140: d c d a b b ba d c4147: d b a b d d b 二判斷題( )1、算法分析考慮的兩個(gè)主要因素是空間復(fù)雜性和時(shí)間復(fù)雜性。( )2、非線性數(shù)據(jù)結(jié)構(gòu)的

15、存儲(chǔ)只能選用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。( )3、任何有向圖的結(jié)點(diǎn)都可以排成拓?fù)渑判?，而且拓?fù)湫蛄胁晃ㄒ弧?( )4、哈希文件是一種直接存取文件。( )5、含有n個(gè)結(jié)點(diǎn)的二叉排序樹(shù)的平均查找長(zhǎng)度和樹(shù)的形態(tài)有關(guān)。( )6、滿二叉樹(shù)一定是完全二叉樹(shù)，但完全二叉樹(shù)不一定是滿二叉樹(shù)。( )7、循環(huán)鏈表不是線性表。 ( )8、文件是記錄的集合，文件上的操作主要有兩類：檢索和維護(hù)。( )9、對(duì)n個(gè)元素進(jìn)行快速排序的過(guò)程中，最壞情況下的時(shí)間復(fù)雜度為o（n2）。( )10、平衡二叉樹(shù)（avl樹(shù)），以每個(gè)分支結(jié)點(diǎn)為根的子樹(shù)都是平衡的。 ( )姓名:_ 學(xué)號(hào):_ 年級(jí):_ 專業(yè):_.密封線11、算法是由若干條指令組成的有窮序列

16、，而一個(gè)程序不一定滿足有窮性。( )12、順序存儲(chǔ)方式只能用于存儲(chǔ)線性結(jié)構(gòu)數(shù)據(jù)。 ( )13、構(gòu)造二叉排序樹(shù)的過(guò)程即為對(duì)無(wú)序序列進(jìn)行排序的過(guò)程。( )14、連通圖上各邊權(quán)值均不相同，則該圖的最小生成樹(shù)是唯一的。( )15、在單鏈表中，頭結(jié)點(diǎn)是必不可少的。 ( )16、在一個(gè)有向圖中，所有頂點(diǎn)的入度之和等于所有頂點(diǎn)的出度之和。 ( )17、一個(gè)圖的深度先遍歷序列是唯一的。 ( )18、長(zhǎng)度為1的串等價(jià)于一個(gè)字符常量。( )19、數(shù)組元素的下標(biāo)值越大，存取時(shí)間越長(zhǎng)。( )20、內(nèi)部排序是指排序過(guò)程在內(nèi)存中進(jìn)行的排序。參考答案: 三、構(gòu)造題15623418834781691231、設(shè)某二叉樹(shù)的前序遍

17、歷序列為abcdefgh，中序遍歷序列為cdbafehg，試?yán)L出這棵二叉樹(shù)，并寫(xiě)出其后序遍歷結(jié)果。2、從空樹(shù)開(kāi)始，逐個(gè)讀入并插入下列關(guān)鍵字，構(gòu)造一棵二叉樹(shù)：（19，83，37，92，17，10，2，8）。3、設(shè)有無(wú)向連通網(wǎng)絡(luò)g如下圖所示：（1）畫(huà)出其鄰接矩陣存儲(chǔ)；（2）從頂點(diǎn)搜索所得的深度優(yōu)先搜索（dfs）序列和廣度優(yōu)先搜索（bfs）序列；（3）請(qǐng)采用普里姆或克魯斯卡爾算法畫(huà)出g的最小生成樹(shù)。4、給定葉結(jié)點(diǎn)的權(quán)值：5，29，7，8，14，23，3，11。要求：（1)構(gòu)造哈夫曼樹(shù)(要求左子樹(shù)根結(jié)點(diǎn)的權(quán)小于等于右子樹(shù)根結(jié)點(diǎn)的權(quán)) 。（2）計(jì)算該哈夫曼樹(shù)的最小加權(quán)路徑長(zhǎng)度wpl。5、設(shè)散列表長(zhǎng)度為1

18、3，散列函數(shù)h(k)=k mod 13,對(duì)關(guān)鍵字序列19，14，23，01，68，20，84，27，55，11，10，79。（1）分別畫(huà)出用線性探測(cè)和鏈地址法解決沖突時(shí)構(gòu)造的散列表（哈希表）。jihgfecdbaa（2）設(shè)每個(gè)記錄的查找概率相等，分別計(jì)算以上兩種散列表查找成功的平均查找長(zhǎng)度（aslsucc）以及查找不成功的平均查找長(zhǎng)度(aslunsucc)。6、設(shè)有一棵樹(shù)，如右圖所示，回答下列問(wèn)題：（1）哪個(gè)是此樹(shù)的根結(jié)點(diǎn)？哪些是葉子結(jié)點(diǎn)？（2）樹(shù)的度數(shù)和樹(shù)的深度是多少？（3）寫(xiě)出結(jié)點(diǎn)g的雙親、祖先、孩子？（4）寫(xiě)出結(jié)點(diǎn)e的子孫、兄弟和結(jié)點(diǎn)e所在的層次？7、假設(shè)用于通信的電文由字符集a,b,c

19、,d,e,f,g，h中的字母構(gòu)成。它們?cè)陔娢闹谐霈F(xiàn)的頻度分別為6,32,3,7,19,2, 21,10。要求：（1) 請(qǐng)為這8個(gè)字母設(shè)計(jì)哈夫曼編碼，并畫(huà)出對(duì)應(yīng)的哈夫曼樹(shù)；（2）計(jì)算該哈夫曼樹(shù)的最小加權(quán)路徑長(zhǎng)度wpl。8、對(duì)給定的一組關(guān)鍵字：49，38，65，97，76，13，27，49，55，4分別寫(xiě)出直接插入排序、希爾排序（增量為5，3，1）、起泡排序、快速排序、直接選擇排序和歸并排序的前2趟排序結(jié)果。9、已知有6個(gè)頂點(diǎn)（頂點(diǎn)編號(hào)為05）的有向帶權(quán)圖g，其鄰接矩陣a為上三角矩陣，按行為主序（行優(yōu)先）保存在如下的一維數(shù)組中：4654333要求：（1）寫(xiě)出圖g的鄰接矩陣a （2）畫(huà)出有向帶權(quán)圖g （3）從頂點(diǎn)0搜索所得的深度優(yōu)先搜索（dfs）序列和廣度優(yōu)先搜索（bfs）序列；（4）求圖g的關(guān)鍵路徑，并計(jì)算該關(guān)鍵路徑的長(zhǎng)度。四、算法設(shè)計(jì)題1、有序表r0至rn-1進(jìn)行二分查找，成功時(shí)返回記錄在表中的位置，失敗時(shí)返回0。請(qǐng)?jiān)跈M線上填空，把算法補(bǔ)充完整。int binsrch(sqlist r ,keytype k) /* 在表r中查找關(guān)鍵字k */ int low ,high,mid; low=0; high