數(shù)據(jù)結(jié)構(gòu)原理和分析-01343-18日下-復(fù)習(xí)題資料全

...wd......wd......wd...數(shù)據(jù)構(gòu)造原理與分析-01343-18日下-復(fù)習(xí)資料一、填空1.線性表是具有n個(gè)什么的有限序列〔數(shù)據(jù)元素〕。2.鄰接表的存儲(chǔ)構(gòu)造以以下列圖的深度優(yōu)先遍歷類似于二叉樹的(先序遍歷)。3.在一棵二叉樹的二叉鏈表中，空指針域數(shù)等于非空指針域數(shù)加〔2〕。4.某二叉樹的前序和后序序列正好相反，那么該二叉樹一定是什么二叉樹(高度等于其結(jié)點(diǎn)數(shù))。5.對(duì)于棧操作數(shù)據(jù)的原那么是〔后進(jìn)先出〕。6.結(jié)點(diǎn)前序?yàn)閤yz的不同二叉樹，所具有的不同形態(tài)為(5)。7.設(shè)長度為n的鏈隊(duì)列用單循環(huán)鏈表表示，假設(shè)只設(shè)頭指針，那么入隊(duì)操作的時(shí)間復(fù)雜度為(O(n))。8.在一棵高度為h(假定樹根結(jié)點(diǎn)的層號(hào)為0)的完全二叉樹中，所含結(jié)點(diǎn)個(gè)數(shù)不小于(2h)。9.具有n個(gè)頂點(diǎn)的有向無環(huán)圖最多可包含有向邊的條數(shù)是(n(n-1)/2)。10.因此在初始為空的隊(duì)列中插入元素a,b,c,d以后，緊接著作了兩次刪除操作，此時(shí)的隊(duì)尾元素是(d).11.假設(shè)二叉樹中度為2的結(jié)點(diǎn)有15個(gè)，度為1的結(jié)點(diǎn)有10個(gè)，那么葉結(jié)點(diǎn)的個(gè)數(shù)〔16〕。12.對(duì)于一棵滿二叉樹，m個(gè)樹葉，n個(gè)結(jié)點(diǎn)，深度為h,那么(n=2h＋1-1)。13.在一棵具有n個(gè)結(jié)點(diǎn)的二叉樹中，所有結(jié)點(diǎn)的空子樹個(gè)數(shù)等于〔n+1〕14.用鄰接表表示圖進(jìn)展深度優(yōu)先遍歷時(shí)，通常用來實(shí)現(xiàn)算法的輔助構(gòu)造是(棧)。15.堆的形狀是一棵(完全二叉樹)。16.假設(shè)在一棵非空樹中，某結(jié)點(diǎn)A有3個(gè)兄弟結(jié)點(diǎn)〔包括A自身〕，B是A的雙親結(jié)點(diǎn)，那么B的度為(4)。17.任何一個(gè)無向連通圖的最小生成樹(有一棵或多棵)18.在非空二叉樹的中序遍歷序列中，二叉樹的根結(jié)點(diǎn)的左邊應(yīng)該(只有左子樹上的所有結(jié)點(diǎn))。19.排序方法中，從未排序序列中依次取出元素與已排序序列中的元素進(jìn)展比較，將其放入已排序序列的正確位置上的方法，稱為(插入排序)。20.對(duì)于一棵滿二叉樹，m個(gè)樹葉，n個(gè)結(jié)點(diǎn)，深度為h,那么(n=2h＋1-1)。21.具有n個(gè)頂點(diǎn)的有向圖最多可包含的有向邊的條數(shù)是(n(n-1))。22.某二叉樹的前序和后序序列正好一樣，那么該二叉樹一定是什么樣的二叉樹(空或只有一個(gè)結(jié)點(diǎn))。23.棧和隊(duì)列的主要區(qū)別在于(插入刪除運(yùn)算的限定不一樣)。24.串是〔任意有限個(gè)字符構(gòu)成的序列〕。25.對(duì)有14個(gè)數(shù)據(jù)元素的有序表R[14]進(jìn)展折半搜索，搜索到R[3]的關(guān)鍵碼等于給定值，此時(shí)元素比較順序依次為〔R[6]，R[2]，R[4]，R[3]〕。26.深度為h且有多少個(gè)結(jié)點(diǎn)的二叉樹稱為滿二叉樹(2h+1-1)。27.在含n個(gè)頂點(diǎn)e條邊的無向圖的鄰接矩陣中，零元素的個(gè)數(shù)為〔n2-2e〕。28.在一個(gè)有向圖中，所有頂點(diǎn)的入度之和與所有頂點(diǎn)出度之和的倍數(shù)為(1)。29.鄰接表的存儲(chǔ)構(gòu)造以以下列圖的廣度優(yōu)先遍歷類似于二叉樹的(按層遍歷)。30.設(shè)高度為h的二叉樹上只有度為0和度為2的結(jié)點(diǎn)，那么此類二叉樹中所包含的結(jié)點(diǎn)數(shù)至少為(2h-1)。31.假設(shè)一棵二叉樹具有10個(gè)度為2的結(jié)點(diǎn)，5個(gè)度為1的結(jié)點(diǎn)，那么度為0的結(jié)點(diǎn)個(gè)數(shù)是〔11〕32.在一棵具有n個(gè)結(jié)點(diǎn)的二叉樹中，所有結(jié)點(diǎn)的空子樹個(gè)數(shù)等于〔n+1〕33.假設(shè)一棵二叉樹有11個(gè)度為2的結(jié)點(diǎn)，那么該二叉樹的葉結(jié)點(diǎn)的個(gè)數(shù)是〔12〕。34.對(duì)有n個(gè)記錄的表按記錄鍵值有序建設(shè)二叉查找樹，在這種情況下，其平均查找長度的量級(jí)為〔O(n)〕。35.設(shè)森林F中有三棵樹，第一、第二和第三棵的結(jié)點(diǎn)個(gè)數(shù)分別為m1,m2和m3,那么森林F對(duì)應(yīng)的二叉樹根結(jié)點(diǎn)上的右子樹上結(jié)點(diǎn)個(gè)數(shù)是(m2+m3)。36.對(duì)有18個(gè)元素的有序表作二分〔折半〕查找，那么查找A[3]的比較序列的下標(biāo)為〔9、4、2、3〕。37.假設(shè)要在O〔1〕的時(shí)間復(fù)雜度上實(shí)現(xiàn)兩個(gè)循環(huán)鏈表頭尾相接，那么應(yīng)對(duì)兩個(gè)循環(huán)鏈表各設(shè)置一個(gè)指針，分別指向(各自的尾結(jié)點(diǎn))。38.深度為h的滿二叉樹所具有的結(jié)點(diǎn)個(gè)數(shù)是〔2h+1-1〕。39.設(shè)高度為h的二叉樹上只有度為0和度為2的結(jié)點(diǎn)，那么此類二叉樹中所包含的結(jié)點(diǎn)數(shù)至少為〔2h-1〕。40.如果T2是由有序樹T轉(zhuǎn)換而來的二叉樹，那么T中結(jié)點(diǎn)的先根序列就是T2中結(jié)點(diǎn)的〔先根序列〕。41.有n個(gè)葉子的哈夫曼樹的結(jié)點(diǎn)總數(shù)為〔2n-1〕。42.設(shè)長度為n的鏈隊(duì)列用單循環(huán)鏈表表示，假設(shè)只設(shè)頭指針，那么入隊(duì)操作的時(shí)間復(fù)雜度為(O(n))。43.假設(shè)二叉樹中度為2的結(jié)點(diǎn)有15個(gè)，度為1的結(jié)點(diǎn)有10個(gè)，那么葉子結(jié)點(diǎn)的個(gè)數(shù)為〔16〕。44.假設(shè)某完全二叉樹的深度為h，那么該完全二叉樹中具有的結(jié)點(diǎn)數(shù)至少是(2h－1)。45.叉樹的前序和后序序列正好相反，那么該二叉樹一定是什么二叉樹(度等于其結(jié)點(diǎn)數(shù))。46.初始序列已經(jīng)按鍵值有序時(shí)，用直接插入算法進(jìn)展排序，需要比較的次數(shù)為(n-1)。47.接表表示圖進(jìn)展廣度優(yōu)先遍歷時(shí)，為實(shí)現(xiàn)算法通常采用的輔助構(gòu)造是(隊(duì)列)。48.用冒泡排序法對(duì)序列{18,16,14,12,10,8}從小到大進(jìn)展排序，需要進(jìn)展的比較次數(shù)是(15)。49.有n個(gè)頂點(diǎn)的圖采用鄰接矩陣表示，那么該矩陣的大小為〔n*n〕。50.6個(gè)頂點(diǎn)的無向圖成為一個(gè)連通圖至少應(yīng)有邊的條數(shù)是〔5〕。51.單鏈表中，增加頭結(jié)點(diǎn)的目的是為了〔方便運(yùn)算的實(shí)現(xiàn)〕。52.在線索二叉樹中,結(jié)點(diǎn)(*t)沒有左子樹的充要條件是(t->ltag==1)。53.按照二叉樹的定義,具有3個(gè)結(jié)點(diǎn)的二叉樹有多少種(5)。54.對(duì)待排序的元素序列進(jìn)展劃分，將其分為左、右兩個(gè)子序列，再對(duì)兩個(gè)子序列施加同樣的排序操作，直到子序列為空或只剩一個(gè)元素為止。這樣的排序方法是〔快速排序〕55.二分查找法要求查找表中各元素的鍵值必須是(遞增或遞減)。56.線性表的長度是指〔表中的元素個(gè)數(shù)〕57.將長度為m的單鏈表連接在長度為n的單鏈表之后的算法的時(shí)間復(fù)雜度為(O(n))。58.有一個(gè)有序表為{1，3，9，12，32，41，45，62，75，77，82，95，100}，當(dāng)二分查找值為82的結(jié)點(diǎn)時(shí)，查找成功的比較次數(shù)是〔4〕。.59.假設(shè)在一棵非空樹中，某結(jié)點(diǎn)A有3個(gè)兄弟結(jié)點(diǎn)〔包括A自身〕，B是A的雙親結(jié)點(diǎn)，那么B的度為〔4〕。60.深度為h的滿二叉樹具有的結(jié)點(diǎn)個(gè)數(shù)為〔2h+1-1〕。61.用二叉鏈表存儲(chǔ)樹，那么根結(jié)點(diǎn)的右指針是〔空〕。62.個(gè)無向圖中，所有頂點(diǎn)的度數(shù)之和等于所有邊數(shù)〔1〕倍。63.單鏈表表示的鏈?zhǔn)疥?duì)列的隊(duì)頭在鏈表的什么位置〔鏈頭〕。64.線性表的長度是指〔表中的元素個(gè)數(shù)〕65.某二叉樹的前序和后序序列正好一樣，那么該二叉樹一定是什么樣的二叉樹(空或只有一個(gè)結(jié)點(diǎn))。66.在一棵具有n個(gè)結(jié)點(diǎn)的二叉樹中，所有結(jié)點(diǎn)的空子樹個(gè)數(shù)等于〔n+1〕。67.一個(gè)具有n個(gè)頂點(diǎn)e條邊的無向圖中，采用鄰接表表示，那么所有頂點(diǎn)的鄰接表的結(jié)點(diǎn)總數(shù)為〔2e〕。68.鏈棧和順序棧相比，有一個(gè)較明顯的優(yōu)點(diǎn)是(通常不會(huì)出現(xiàn)棧滿的情況)。69.對(duì)于鍵值序列{72,73,71,23,94,16,5,68,76,103}用篩選法建堆，開場結(jié)點(diǎn)的鍵值必須為(94)。70.在圖形構(gòu)造中，每個(gè)結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)數(shù)和后續(xù)結(jié)點(diǎn)數(shù)可以有(任意多個(gè))。71.對(duì)有n個(gè)記錄的有序表采用二分查找，其平均查找長度的量級(jí)為(O(log2n))。72.在一棵高度為h(假定樹根結(jié)點(diǎn)的層號(hào)為0)的完全二叉樹中，所含結(jié)點(diǎn)個(gè)數(shù)不小于(2h)。73.假設(shè)一棵二叉樹有10個(gè)葉結(jié)點(diǎn)，那么該二叉樹中度為2的結(jié)點(diǎn)個(gè)數(shù)為9。74.設(shè)有一個(gè)順序棧S，元素S1，S2，S3，S4，S5，S6依次進(jìn)棧，如果6個(gè)元素的出棧順序?yàn)镾2，S3，S4，S6，S5，S1，那么順序棧的容量至少應(yīng)為3。75.對(duì)于一棵二叉樹，設(shè)葉子結(jié)點(diǎn)數(shù)為n0,次數(shù)為2的結(jié)點(diǎn)數(shù)為n2,那么n0和n2的關(guān)系是n0=n2＋1。76.假設(shè)一棵二叉樹有12個(gè)葉結(jié)點(diǎn)，那么該二叉樹中度為2的結(jié)點(diǎn)個(gè)數(shù)為11。77.二叉樹的存儲(chǔ)構(gòu)造有順序存儲(chǔ)構(gòu)造和鏈?zhǔn)酱鎯?chǔ)構(gòu)造。78.深度為h且有2k-1個(gè)結(jié)點(diǎn)的二叉樹稱為滿二叉樹。(設(shè)根結(jié)點(diǎn)處在第1層)。79.圖的深度優(yōu)先搜索方法類似于二叉樹的先序遍歷。80.哈夫曼樹是帶權(quán)路徑長度最小的二叉樹。81.在線索二叉樹中，線索是指向結(jié)點(diǎn)在某遍歷次序下的前驅(qū)或后繼結(jié)點(diǎn)的指針。82.棧可以作為實(shí)現(xiàn)遞歸函數(shù)調(diào)用的一種數(shù)據(jù)構(gòu)造。83.一般樹的存儲(chǔ)構(gòu)造有雙親表示法、孩子兄弟表示法和孩子鏈表表示法。84.將數(shù)據(jù)元素2,4,6,8,10,12,14,16,18,20依次存于一個(gè)一維數(shù)組中，然后采用折半查找元素12，被比較過的數(shù)組元素的下標(biāo)依次為5，7，6。。85.圖的深度優(yōu)先遍歷序列不是唯一的。86.假設(shè)二叉樹的一個(gè)葉子結(jié)點(diǎn)是某子樹的中根遍歷序列中的第一個(gè)結(jié)點(diǎn)，那么它必是該子樹的后跟遍歷中的第一個(gè)結(jié)點(diǎn)。87.圖的遍歷是指從圖中某一頂點(diǎn)出發(fā)訪問圖中全部頂點(diǎn)且使每一頂點(diǎn)僅被_訪問一次。88.在一個(gè)圖中，所有頂點(diǎn)的度數(shù)之和等于所有邊的數(shù)目的2倍。89.由一棵二叉樹的后序序列和中序序列可唯一確定這棵二叉樹。90.在有序表(12,24,36,48,60,72,84)中二分查找關(guān)鍵字72時(shí)所需進(jìn)展的關(guān)鍵字比較次數(shù)為2。91.設(shè)根結(jié)點(diǎn)的層數(shù)為0，定義樹的高度為樹中層數(shù)最大的結(jié)點(diǎn)的層數(shù)加1，那么高度為k的二叉樹具有的結(jié)點(diǎn)數(shù)目，最少為k，最多為2k-1。92.在直接插入排序、直接選擇排序、分劃交換排序、堆排序中穩(wěn)定的排序方法有直接插入排序。93.具有100個(gè)結(jié)點(diǎn)的完全二叉樹的葉子結(jié)點(diǎn)數(shù)為50。94.普里姆(Prim)算法適用于邊稠密圖。95.在有n個(gè)葉子結(jié)點(diǎn)的哈夫曼樹中,其結(jié)點(diǎn)總數(shù)為2n-1。96.將一棵樹轉(zhuǎn)換成一棵二叉樹后，二叉樹根結(jié)點(diǎn)沒有右子樹。97.矩陣采用壓縮存儲(chǔ)是為了節(jié)省空間98.假設(shè)連通網(wǎng)絡(luò)上各邊的權(quán)值均不一樣，那么該圖的最小生成樹有1棵。99.設(shè)無向圖G的頂點(diǎn)數(shù)為n，那么要使G連通最少有n-1條邊。100.棧和隊(duì)列的共同特點(diǎn)是插入和刪除均在端點(diǎn)處進(jìn)展。101.克魯斯卡爾(Kruskar)算法適用于邊稀疏圖。102.假設(shè)連通圖的頂點(diǎn)個(gè)數(shù)為n，那么該圖的生成樹的邊數(shù)為n-1。103.圖的存儲(chǔ)構(gòu)造最常用的有鄰接矩陣和鄰接表。104.由一棵二叉樹的前序序列和中序序列可唯一確定這棵二叉樹。105.隊(duì)列中允許進(jìn)展插入的一端稱為隊(duì)尾。106.拓?fù)渑判蜉敵龅捻旤c(diǎn)數(shù)小于有向圖的頂點(diǎn)數(shù)，那么該圖一定存在環(huán)。107.在有序表(15,23,24,45,48,62,85)中二分查找關(guān)鍵詞23時(shí)所需進(jìn)展的關(guān)鍵詞比較次數(shù)為2。108.樹中所有結(jié)點(diǎn)的度等于所有結(jié)點(diǎn)數(shù)加〔-1〕。109.在一個(gè)具有n個(gè)頂點(diǎn)的完全無向圖的邊數(shù)為(n(n-1)/2)。110.用分劃交換排序方法對(duì)包含有n個(gè)關(guān)鍵的序列進(jìn)展排序，最壞情況下執(zhí)行的時(shí)間雜度為(O(n2))111.一棵高度為h(假定樹根結(jié)點(diǎn)的層號(hào)為0)的完全二叉樹中，所含結(jié)點(diǎn)個(gè)數(shù)不小于(2h)。112.假設(shè)長度為n的非空線性表采用順序存儲(chǔ)構(gòu)造，刪除表的第i個(gè)數(shù)據(jù)元素，首先需要移動(dòng)表中數(shù)據(jù)元素的個(gè)數(shù)是〔n-i〕。113.在非空二叉樹的中序遍歷序列中，二叉樹的根結(jié)點(diǎn)的左邊應(yīng)該(只有左子樹上的所有結(jié)點(diǎn))。114.假設(shè)一棵二叉樹具有45個(gè)度為2的結(jié)點(diǎn)，6個(gè)度為1的結(jié)點(diǎn)，那么度為0的結(jié)點(diǎn)個(gè)數(shù)是〔46〕。115.在一個(gè)有向圖中，所有頂點(diǎn)的入度之和等于所有邊數(shù)〔4〕倍。116.設(shè)輸入序列為A,B,C,D,借助一個(gè)棧不可以得到的輸出序列是(D,A,B,C)。117.一維數(shù)組A采用順序存儲(chǔ)構(gòu)造，每個(gè)元素占用6個(gè)字節(jié)，第6個(gè)元素的起始地址為100，那么該數(shù)組的首地址是〔70〕。118.設(shè)abcdef以所給的次序進(jìn)棧，假設(shè)在進(jìn)棧操作時(shí)，允許退棧操作,那么下面得不到的序列為〔cbdef〕。119.一般情況下，將遞歸算法轉(zhuǎn)換成等價(jià)的非遞歸算法應(yīng)該設(shè)置〔堆?！?。120.假設(shè)長度為n的非空線性表采用順序存儲(chǔ)構(gòu)造，刪除表的第i個(gè)數(shù)據(jù)元素，i的合法值應(yīng)該121.是〔C.1≤i≤n〕。122.假設(shè)某線性表中最常用的操作是取第i個(gè)元素和刪除最后一個(gè)元素，那么采用什么存儲(chǔ)方123.式最節(jié)省時(shí)間〔順序表〕。124.一組記錄的關(guān)鍵字為{45,80,55,40,42,85}，那么利用堆排序的方法建設(shè)的初始堆為〔85,80,55,40,42,45〕。125.設(shè)有6000個(gè)無序的元素,希望用最快的速度挑選出其中前5個(gè)最大的元素,最好選用(堆排序)法。126.排序方法中，從未排序序列中挑選元素，將其放入已排序序列的一端的方法，稱為(選擇排序)。127.帶頭結(jié)點(diǎn)的單鏈表head為空的判斷條件是(head->next==NULL)。128.在一個(gè)單鏈表中，假設(shè)刪除(*p)結(jié)點(diǎn)的后繼結(jié)點(diǎn)，那么執(zhí)行(p->next=p->next->next)。129.在一棵具有n個(gè)結(jié)點(diǎn)的二叉樹中，所有結(jié)點(diǎn)的空子樹個(gè)數(shù)等于〔n+1〕130.有向圖中，以頂點(diǎn)v為終點(diǎn)的邊的數(shù)目，稱為頂點(diǎn)v的〔入度〕。131.假設(shè)頻繁地對(duì)線性表進(jìn)展插入和刪除操作，該線性表應(yīng)該采用的存儲(chǔ)構(gòu)造是〔鏈?zhǔn)健场?32.設(shè)一個(gè)棧的輸入序列是1，2，3，4，5,那么以下序列中，是棧的合法輸出序列的是〔32154〕。133.有數(shù)據(jù){53，30，37，12，45，24，96}，從空二叉樹開場逐個(gè)插入數(shù)據(jù)來形成二叉查找樹，假設(shè)希望高度最小，那么應(yīng)選擇下面輸入序列是〔37,24,12,30,53,45,96〕。134.二叉樹的第I層上最多含有結(jié)點(diǎn)數(shù)為〔2I〕。135.稀疏矩陣一般采用的壓縮存儲(chǔ)方法為(三元組表)。136.某二叉樹的前序和后序序列正好一樣，那么該二叉樹一定是什么樣的二叉樹(空或只有一個(gè)結(jié)點(diǎn))。137.假設(shè)長度為n的線性表采用順序存儲(chǔ)構(gòu)造，在表的第i個(gè)位置插入一個(gè)數(shù)據(jù)元素，需要移動(dòng)表中元素的個(gè)數(shù)是〔n-i+1〕。138.設(shè)有數(shù)組A[i,j]，數(shù)組的每個(gè)元素長度為3字節(jié)，i的值為1到8，j的值為1到10，數(shù)組從內(nèi)存首地址BA開場順序存放，當(dāng)用以列為主存放時(shí)，元素A[5，8]的存儲(chǔ)首地址為(BA+180)。139.二維數(shù)組A[5][6]的每個(gè)元素占5個(gè)單元，將其按行優(yōu)先順序存儲(chǔ)在起始地址為3000的連續(xù)的內(nèi)存單元中，那么元素A[4][5]的存儲(chǔ)地址為〔3145〕。140.一個(gè)具有n個(gè)頂點(diǎn)的圖采用鄰接矩陣表示，那么該矩陣的大小為〔n*n〕。141.假設(shè)字符串“1234567〞采用鏈?zhǔn)酱鎯?chǔ)，假設(shè)每個(gè)字符占用1個(gè)字節(jié)，每個(gè)指針占用2個(gè)字節(jié)，那么該字符串的存儲(chǔ)密度為〔33.3﹪〕。142.假設(shè)在一棵非空樹中，某結(jié)點(diǎn)A有3個(gè)兄弟結(jié)點(diǎn)〔包括A自身〕，B是A的雙親結(jié)點(diǎn)，那么B的度為〔3〕。143.設(shè)有三個(gè)元素X，Y，Z順序進(jìn)?！策M(jìn)的過程中允許出?！常韵碌貌坏降某鰲Ｅ帕惺?ZXY)。144.樹形構(gòu)造的特點(diǎn)是：一個(gè)結(jié)點(diǎn)可以有(多個(gè)直接后繼)。145.使具有30個(gè)頂點(diǎn)的無向圖成為一個(gè)連通圖至少應(yīng)有邊的條數(shù)是〔29〕。146.使具有9個(gè)頂點(diǎn)的無向圖成為一個(gè)連通圖至少應(yīng)有邊的條數(shù)是〔8〕。147.在順序表〔n足夠大〕中進(jìn)展順序查找，其查找不成功的平均長度是〔n+1〕。148.設(shè)樹T的度為4，其中度為1，2，3和4的結(jié)點(diǎn)個(gè)數(shù)分別為4，2，1，1那么T中的葉子數(shù)為〔8〕。149.棧的插入和刪除操作進(jìn)展的位置在〔棧頂〕。150.假設(shè)一棵二叉樹具有20個(gè)度為2的結(jié)點(diǎn)，6個(gè)度為1的結(jié)點(diǎn)，那么度為0的結(jié)點(diǎn)個(gè)數(shù)是〔21〕。151.一棵線索二叉樹的線索個(gè)數(shù)比鏈接個(gè)數(shù)多〔2〕個(gè)。152.在循環(huán)鏈表中，從任何一結(jié)點(diǎn)出發(fā)都能訪問到表中的所有結(jié)點(diǎn)。153.在n個(gè)結(jié)點(diǎn)的順序表中插入一個(gè)結(jié)點(diǎn)需平均移動(dòng)n/2個(gè)結(jié)點(diǎn)。154.循環(huán)隊(duì)列的引入，目的是為了抑制假溢出。155.假設(shè)連通網(wǎng)絡(luò)上各邊的權(quán)值均不一樣，那么該圖的最小生成樹有1棵。156.二叉樹的遍歷方式有三種：先序遍歷、中序遍歷、后序遍歷。157.假設(shè)一棵二叉樹有15個(gè)葉結(jié)點(diǎn)，那么該二叉樹中度為2的結(jié)的點(diǎn)個(gè)數(shù)為14。158.設(shè)某二叉樹的后序遍歷序列為ABKCBPM，那么可知該二叉樹的根為M。159.數(shù)據(jù)構(gòu)造的三個(gè)方面：數(shù)據(jù)的邏輯構(gòu)造、物理構(gòu)造、運(yùn)算。160.每個(gè)結(jié)點(diǎn)只有一個(gè)鏈接域的鏈表叫做單鏈表。161.組成串的數(shù)據(jù)元素只能是字符。162.具有n個(gè)結(jié)點(diǎn)的二叉樹采用鏈接構(gòu)造存儲(chǔ)，鏈表中存放NULL指針域的個(gè)數(shù)為〔n+1〕。163.在一個(gè)無向圖中，所有頂點(diǎn)的度數(shù)之和等于所有邊數(shù)〔2〕倍。164設(shè)二叉樹根結(jié)點(diǎn)的層次為0，一棵高度為h的滿二叉樹中的結(jié)點(diǎn)個(gè)數(shù)是(2h+1-1)。165.將一棵有50個(gè)結(jié)點(diǎn)的完全二叉樹按層編號(hào)，那么對(duì)編號(hào)為25的結(jié)點(diǎn)x，該結(jié)點(diǎn)(有左孩子，無右孩子)。166.樹〔或樹形〕的定義是什么答：一個(gè)樹〔或樹形〕就是一個(gè)有限非空的結(jié)點(diǎn)集合T，其中有一個(gè)特別標(biāo)出的稱為該樹之根root〔T〕的結(jié)點(diǎn)；其余〔除根外〕的結(jié)點(diǎn)劃分成個(gè)不相交集合,而且這些集合的每一個(gè)又都是樹。167在圖形構(gòu)造中，每個(gè)結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)數(shù)和后續(xù)結(jié)點(diǎn)數(shù)可以有(任意多個(gè))。168.什么是樹的路徑長度答：樹的路徑長度是指從根結(jié)點(diǎn)到樹中每個(gè)葉結(jié)點(diǎn)的路徑長度之和。二、選擇1.假設(shè)某線性表中最常用的操作是取第i個(gè)元素和刪除最后一個(gè)元素，那么采用什么存儲(chǔ)方式最節(jié)省時(shí)間〔A〕。A.順序表B.單鏈表C.雙鏈表D.單循環(huán)鏈表2.在下述的排序方法中，不屬于內(nèi)排序方法的是〔C〕。A.插入排序法B.選擇排序法C.拓?fù)渑判蚍―.歸并排序法3.以下四個(gè)關(guān)鍵詞序列中,不是堆的序列為(C)。A.{05,23,16,68,94,72,71,73}B.{05,16,23,68,94,72,71,73}C.{05,23,16,73,94,72,71,68}D.{05,23,16,68,73,71,72,94}4.以下排序算法中,某一趟完畢后未必能選出一個(gè)元素放其最終位置上的是(D)。A.堆排序B.冒泡排序C.快速排序D.直接插入排序5.用孩子兄弟鏈表表示一棵樹，假設(shè)要找到結(jié)點(diǎn)x的第5個(gè)孩子，只要先找到x的第一個(gè)孩子，然后(D)。A.從孩子域指針連續(xù)掃描5個(gè)結(jié)點(diǎn)即可B.從孩子域指針連續(xù)掃描4個(gè)結(jié)點(diǎn)即可C.從兄弟域指針連續(xù)掃描5個(gè)結(jié)點(diǎn)即可D.從兄弟域指針連續(xù)掃描4個(gè)結(jié)點(diǎn)即可6.鏈棧和順序棧相比，有一個(gè)較明顯的優(yōu)點(diǎn)是(A)。A.通常不會(huì)出現(xiàn)棧滿的情況B.通常不會(huì)出現(xiàn)?？盏那闆rC插入操作更加方便D.刪除操作更加方便7.任何一棵二叉樹的葉結(jié)點(diǎn)在其先根、中根、后根遍歷序列中的相對(duì)位置(C)。A.肯定發(fā)生變化B.有時(shí)發(fā)生變化C.肯定不發(fā)生變化D.無法確定8.排序方法中，從未排序序列中挑選元素，將其放入已排序序列的一端的方法，稱為(D)。A.希爾排序B.冒泡排序C.插入排序D.選擇排序9.堆是一種什么排序〔B〕。A.插入B.選擇C.交換D.歸并10.以下排序方法中不穩(wěn)定的排序是(C)。A.直接插入排序B.冒泡排序C.堆排序D.歸并排序11.一個(gè)無向連通圖的生成樹是含有該連通圖的全部頂點(diǎn)的(A)。A.極小連通子圖B.極大連通子圖C.極小子圖D.極大子圖12.如下陳述中正確的選項(xiàng)是(A)。A.串是一種特殊的線性表B.串的長度必須大于零B.串中元素只能是字母D.空串就是空白串13.快速排序不利于發(fā)揮其長處的情況是〔C〕。[A]待排序數(shù)據(jù)量太大[B]待排序數(shù)據(jù)一樣值過多[C]待排序數(shù)據(jù)已基本有序[D]待排序數(shù)據(jù)值差過大14.性表中采用折半查找法查找元素，該線性表必須滿足〔C〕。[A]元素按值有序[B]采用順序存儲(chǔ)構(gòu)造[C]元素按值有序，且采用順序存儲(chǔ)構(gòu)造[D]元素按值有序，且采用鏈?zhǔn)酱鎯?chǔ)構(gòu)造15.r在排序前已按元素鍵值遞增順序排列，那么比較次數(shù)較少的排序方法是(A)。A.直接插入排序B.快速排序C.歸并排序D.選擇排序16.一個(gè)遞歸的定義可以用遞歸過程求解，也可以用非遞歸過程求解，但單從運(yùn)行時(shí)間來看，通常遞歸過程比非遞歸過程〔B〕A．較快B．較慢C．一樣D.不確定17.如果待排序序列中兩個(gè)數(shù)據(jù)元素具有一樣的值，在排序后它們的位置發(fā)生顛倒，那么稱該排序是不穩(wěn)定的。不穩(wěn)定的排序方法是〔D〕。A．起泡排序B．歸并排序C．直接插入法排序D．簡單項(xiàng)選擇擇排序18.將一棵有50個(gè)結(jié)點(diǎn)的完全二叉樹按層編號(hào)，那么對(duì)編號(hào)為25的結(jié)點(diǎn)x，該結(jié)點(diǎn)(B)。A.無左、右孩子B.有左孩子，無右孩子C.有右孩子，無左孩子D.有左、右孩子19.假設(shè)某鏈表最常用的操作是在最后一個(gè)結(jié)點(diǎn)之后插入一個(gè)結(jié)點(diǎn)和刪除最后一個(gè)結(jié)點(diǎn)，那么采用那種存儲(chǔ)方式最節(jié)省時(shí)間(C)。A.單鏈表B.雙鏈表C.帶頭結(jié)點(diǎn)的雙循環(huán)鏈表D.單循環(huán)鏈表20.以下排序算法中,第一趟排序完畢后,其最大或最小元素一定在其最終位置上的算法是(D)。A.歸并排序B.直接插入排序C.快速排序D.冒泡排序21.樹形構(gòu)造最適合用來描述〔C〕。[A]有序的數(shù)據(jù)元素[B]無序的數(shù)據(jù)元素[C]數(shù)據(jù)元素之間具有層次關(guān)系的數(shù)據(jù)[D]數(shù)據(jù)元素之間沒有關(guān)系的數(shù)據(jù)22.設(shè)有7000個(gè)無序的元素,希望用最快的速度挑選出其中前5個(gè)最大的元素,最好選用方法是(C)。A.冒泡排序B.快速排序C.堆排序D.基數(shù)排序23.鏈表不具有的特點(diǎn)是(A)。A.可隨機(jī)訪問任一元素B.插入刪除不需要移動(dòng)元素C.不必事先估計(jì)存儲(chǔ)空間D.所需空間與線性表長度成正比24.假設(shè)待排序?qū)ο笮蛄性谂判蚯耙寻雌渑判虼a遞增順序排序，那么比較次數(shù)最少的方法排序是〔A〕。A．直接插入排序B．快速排序C．歸并排序D．直接選擇排序25.以下關(guān)鍵字序列中是堆的序列為(D)。A.16,72,31,23,94,53B.94,23,31,72,16,53B.16,53,23,94,31,72D.16,23,53,31,94,7226.以下四個(gè)關(guān)鍵字序列中,那個(gè)序列不是堆(C)。A.{05,23,16,68,94,72,71,73}B.{05,16,23,68,94,72,71,73}C.{05,23,16,73,94,72,71,68}D.{05,23,16,68,73,71,72,94}27.下面4個(gè)序列中，滿足堆的定義是〔D〕。A.13,27,49,76,76,38,85,97B.76,38,27,49,76,85,13,97C.13,76,49,76,27,38,85,97D.13,27,38,76,49,85,76,9728.采用線性探查法處理沖突所構(gòu)成的散列表上進(jìn)展查找，可能要探測到多個(gè)位置，在查找成功情況下，所探測的這些位置上的鍵值〔D〕。A.一定都是同義詞B.一定都不是同義詞C.都一樣D.不一定都是同義詞29.性表中采用折半查找法查找元素，該線性表必須滿足〔C〕。[A]元素按值有序[B]采用順序存儲(chǔ)構(gòu)造[C]元素按值有序，且采用順序存儲(chǔ)構(gòu)造[D]元素按值有序，且采用鏈?zhǔn)酱鎯?chǔ)構(gòu)造三、簡答1.對(duì)于一個(gè)隊(duì)列，如果輸入項(xiàng)序列由1,2,3,4所組成，試給出全部可能的輸出序列。答：1,2,3,4。2.將表達(dá)式(a+b)*c+d-(e+g)*h改寫成后綴表達(dá)式。答：后綴表達(dá)式為：ab+c*d+eg+h*-3.對(duì)于一個(gè)棧，給出輸入序列A，B，C，試給出全部可能的輸出序列。答：解：輸出序列為：ABC，CBA,ACB,BAC,BCA。4．將算術(shù)表達(dá)式a+b*〔c+d/e〕轉(zhuǎn)為后綴表達(dá)式。答：B．a(chǎn)bcde/+*+5.由權(quán)值為12，6，5，9,10的五個(gè)葉子結(jié)點(diǎn)構(gòu)造一棵哈夫曼樹，請(qǐng)問該樹的帶權(quán)路徑長度是多少答：權(quán)值為95。6.由二叉樹的前序和后序遍歷序列能否唯一確定一棵二叉樹。假設(shè)不能請(qǐng)舉出反例。答：不能唯一確定一棵二叉樹。如以以下列圖。11231237.求出以以下列圖所示有向圖的鄰接矩陣。VV0V4V3V2V1213457答：有向圖的鄰接矩陣為：027027∞1∞0∞∞∞∞∞05∞∞∞∞0∞3∞∞4001234012348.有個(gè)頂點(diǎn)的無向連通圖至少有多少條邊有個(gè)頂點(diǎn)的有向連通圖至少有多少條邊答：有個(gè)頂點(diǎn)的無向連通圖至少有n-1條邊，有個(gè)頂點(diǎn)的有向連通圖至少有n條邊。9．下面列舉的是常用的排序方法：直接插入排序，起泡排序，快速排序，直接選擇排序，堆排序，歸并排序。試問，哪些排序方法是穩(wěn)定的答：起泡排序,直接插入排序，歸并排序是穩(wěn)定的。10.為什么說樹是一種非線性構(gòu)造樹中的每個(gè)結(jié)點(diǎn)除了根結(jié)點(diǎn)外，其余每個(gè)結(jié)點(diǎn)有一個(gè)直接前驅(qū)，但有多個(gè)直接后繼，所以說樹是一種非線性構(gòu)造。11．一棵二叉樹的前序和中序序列，求該二叉樹的后序序列。前序序列：A,B,C,D,E,F,G,H,I,J中序序列：C,B,A,F,E,D,I,H,J,G答：后序序列為：C,B,F,E,I,J,H,G,D,A12．試述順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)的區(qū)別及各自的優(yōu)缺點(diǎn)。答：數(shù)組占用連續(xù)的內(nèi)存空間，鏈表不要求結(jié)點(diǎn)的空間連續(xù)。1〕插入與刪除操作：由于數(shù)組在插入與刪除數(shù)據(jù)時(shí)需移動(dòng)大量的數(shù)據(jù)元素，而鏈表只需要改變一些指針的鏈接，因此，鏈表比數(shù)組易于實(shí)現(xiàn)數(shù)據(jù)的插入和刪除操作。2〕內(nèi)存空間的占用情況：因鏈表多了一個(gè)指針域，故較浪費(fèi)空間，因此，在空間占用方面，數(shù)組優(yōu)于鏈表。3〕數(shù)據(jù)的存取操作：訪問鏈表中的結(jié)點(diǎn)必須從表頭開場，是順序的存取方式，而數(shù)組元素的訪問是通過數(shù)組下標(biāo)來實(shí)現(xiàn)的，是隨機(jī)存取方式，因此，在數(shù)據(jù)存取方面，數(shù)組優(yōu)于鏈表。數(shù)據(jù)的合并與別離：鏈表優(yōu)于數(shù)組，因?yàn)橹恍枰淖冎羔樀闹赶?3.將表達(dá)式((a+b)-c*(d+e)-f)*(g+h)改寫成后綴表達(dá)式。答：后綴表達(dá)式為：ab+cde+*-f-gh+*14．將算術(shù)表達(dá)式a*(b+c)-d轉(zhuǎn)為后綴表達(dá)式。答：abc+*d-15.求出以以下列圖所示有向圖的鄰接表。VV0V4V3V2V1213457答：有向圖的鄰接表為：VV0V1∧V2V3∧V4122741∧35∧34∧03Head16．試找出中序序列和后序序列一樣的所有二叉樹。答：空樹或缺右子樹的單支樹。17.用鄰接矩陣存儲(chǔ)一個(gè)包含1000個(gè)頂點(diǎn)和1000條邊的圖，那么該圖的鄰接矩陣中有多少元素有多少非零元素答：該圖的鄰接矩陣中有1000*1000個(gè)元素。該圖的鄰接矩陣中有2000個(gè)非零元素。18.畫出以以下列圖中二叉樹的順序存儲(chǔ)構(gòu)造示意圖。113715答：二叉樹的順序存儲(chǔ)構(gòu)造示意圖為：113715A[0]A[2]A[6]A[14]19.寫出中綴表達(dá)式A-(B+C/D)*E的后綴形式。答：中綴表達(dá)式A-(B+C/D)*E的后綴形式是：ABCD/+E*-。20．為什么用二叉樹表示一般樹答：樹的最直觀表示是為樹中結(jié)點(diǎn)設(shè)置指向子結(jié)點(diǎn)的指針域，對(duì)k叉樹而言，每個(gè)結(jié)點(diǎn)除data域外，還有k個(gè)鏈接域。這樣，對(duì)一個(gè)有n個(gè)結(jié)點(diǎn)的k叉樹來說，共有n*k個(gè)指針域，其中n-1個(gè)不空，另外n(k-1)+1個(gè)指針域?yàn)榭?，因此，空鏈接域的比例約為〔k-1〕/k，于是導(dǎo)致大量的空間浪費(fèi)。然而，如果采用二叉樹表示一棵n個(gè)結(jié)點(diǎn)的樹，那么樹中共有2n個(gè)鏈接域，其中未用到的有n+1個(gè)，占所有指針域的比例約為1/2，空間浪費(fèi)少很多。另外，因?yàn)槿魏螛湫蜆?gòu)造都可以轉(zhuǎn)換成二叉樹，因此，通常用二叉樹表示樹型構(gòu)造。21．請(qǐng)指出一組權(quán)值〔7，5，2，4〕對(duì)應(yīng)的哈夫曼樹的帶權(quán)路徑長度。答：哈夫曼樹的帶權(quán)路徑長度是35。22．試找出前序序列和中序序列一樣的所有二叉樹。解答：空樹或缺左子樹的單支樹。23．完全二叉樹用什么數(shù)據(jù)構(gòu)造實(shí)現(xiàn)最適宜，為什么答：完全二叉樹用一維數(shù)組實(shí)現(xiàn)最適宜。因?yàn)橥耆鏄浔４嬖谝痪S數(shù)組中時(shí)，數(shù)組內(nèi)沒有空洞，不存在空間浪費(fèi)問題；另外，順序存儲(chǔ)方式下，父子結(jié)點(diǎn)之間的關(guān)系可用公式描述，即父〔或子〕結(jié)點(diǎn)尋找子〔或父〕結(jié)點(diǎn)只需計(jì)算一個(gè)公式，訪問結(jié)點(diǎn)方便。但采用鏈表存儲(chǔ)時(shí)就存在空間浪費(fèi)問題，因?yàn)槊總€(gè)結(jié)點(diǎn)要另外保存兩個(gè)鏈接域，并且尋找結(jié)點(diǎn)也不容易。24.求出以以下列圖所示無向圖的鄰接矩陣。VV0V1V2V30012301111001100111100123答：無向圖的鄰接矩陣為：5539132541805513571221183025.請(qǐng)構(gòu)造權(quán)值為{5，13，21，7，18，30，41}的哈夫曼樹。答：哈夫曼樹為：26．我們已經(jīng)知道，樹的先根序列與其對(duì)應(yīng)的二叉樹的先根序列一樣，樹的后根序列與其對(duì)應(yīng)的二叉樹的中根序列一樣。那么利用樹的先根遍歷次序與后根遍歷次序，能否唯一確定一棵樹請(qǐng)說明理由。答：能。因?yàn)闃涞南雀蛄信c其對(duì)應(yīng)的二叉樹的先根序列一樣，樹的后根序列與其對(duì)應(yīng)的二叉樹的中根序列一樣，而二叉樹的先根序列與二叉樹的中根序列能唯一確定一棵二叉樹，所以利用樹的先根遍歷次序與后根遍歷次序，能唯一確定一棵樹。27．請(qǐng)給出如以以下列圖所示的權(quán)圖的鄰接矩陣。VV0V4V3V2V1213457答：解：027∞1027∞1∞0∞∞∞∞∞05∞∞∞∞0∞3∞∞40012340123428．一棵二叉樹的中序和前序序列如下，求該二叉樹的后序序列。中序序列：c，b，d，e，a，g，i，h，j，f前序序列：a，b，c，d，e，f，g，h，i，j答：該二叉樹的后序序列為：c,e,d,b,i,j,h,g,f,a29．對(duì)半查找是否適合于以鏈接構(gòu)造組織的表答：對(duì)半查找不適合于以鏈接構(gòu)造組織的表。。30.請(qǐng)指出中序遍歷二叉查找樹的結(jié)點(diǎn)可以得到什么樣的結(jié)點(diǎn)序列。答：中序遍歷二叉查找樹的結(jié)點(diǎn)就可以得到從小到大排序的結(jié)點(diǎn)序列。31．把以以下列圖中的森林轉(zhuǎn)化為一棵二叉樹。112684735解答：森林轉(zhuǎn)化成的二叉樹如以以下列圖。11268473532.指出一般樹的存儲(chǔ)構(gòu)造有哪幾種答：樹的存儲(chǔ)構(gòu)造有雙親表示法、孩子鏈表表示法和孩子兄弟表示法33.試找出前序序列和后序序列一樣的所有二叉樹。答：空樹或只有根結(jié)點(diǎn)的二叉樹。34.線性表有兩種存儲(chǔ)構(gòu)造：一是順序表，二是鏈表。試問：如果有n個(gè)線性表同時(shí)并存，并且在處理過程中各表的長度會(huì)動(dòng)態(tài)變化，線性表的總數(shù)也會(huì)自動(dòng)地改變。在此情況下，應(yīng)選用哪種存儲(chǔ)構(gòu)造為什么答：選鏈?zhǔn)酱鎯?chǔ)構(gòu)造。它可動(dòng)態(tài)申請(qǐng)內(nèi)存空間，不受表長度〔即表中元素個(gè)數(shù)〕的影響，插入、刪除時(shí)間復(fù)雜度為O35.求出以以下列圖所示無向圖的鄰接表。VV0V1V2V3VV0V1V2V313∧203∧03∧02∧1Head答：無向圖的鄰接表為：36.一個(gè)圖如下所示，假設(shè)從頂點(diǎn)0出發(fā)求出其廣度優(yōu)先搜索序列。003425167解答：廣度優(yōu)先搜索序列：0123456737.一組記錄的關(guān)鍵字為(52,56,26,12,69,85,33,48,70)，給出快速排序的過程。解答：解：52,56,26,12,69,85,33,48,70第一趟排序33,48,26,12,52,85,69,56,70第二趟排序26,12,33,48,52,69,56,70,85第三趟排序12,26,33,48,52,56,70,69,85第四趟排序12,26,33,48,52,56,70,69,85第五趟排序12,26,33,48,52,56,70,69,8538．下面列舉的是常用的排序方法：直接插入排序，起泡排序，快速排序，直接選擇排序，堆排序，歸并排序。試問，哪些排序方法是穩(wěn)定的起泡排序,直接插入排序，歸并排序是穩(wěn)定的。39．一棵二叉樹的前序和中序序列，求該二叉樹的后序序列。前序序列：A,B,C,D,E,F,G,H,I,J中序序列：C,B,A,F,E,D,I,H,J,G答：后序序列為：C,B,F,E,I,J,H,G,D,A40．把以以下列圖中的二叉樹轉(zhuǎn)化成森林。112684735112684735答案：41.給定表〔43,36,56,6,64,32,8,41〕，按數(shù)據(jù)元素在表中的次序構(gòu)造一棵二叉查找樹，并求其平均查找長度。解答：根據(jù)給定表〔43,36,56,6,64,32,8,41〕，構(gòu)造的二叉查找樹如以以下列圖；其平均查找長度為：23/8。646483241656364342．將以以下列圖中的二叉樹，轉(zhuǎn)換成相應(yīng)的森林。AABCHFDJEILKGNM答：森林轉(zhuǎn)化成的二叉樹如以以下列圖。JJCHEKFILNMABDG43.知二叉樹按中根遍歷所得到的結(jié)點(diǎn)序列為DCBGEAHFIJK，按后根遍歷所得到的結(jié)點(diǎn)序列為DCEGBFHKJIA，畫出該樹形構(gòu)造，并按中根遍歷序列進(jìn)展線索化。答：HHKFGCIBAJED44.對(duì)于以以下列圖所示的二叉樹，試分別寫出先根遍歷、中根遍歷該樹所得到的先根序列、中根序列。GGFEDCBALKJIH答：先根遍歷的結(jié)點(diǎn)序列：ABCEIFJDGHKL，中遍歷的結(jié)點(diǎn)序列：EICFJBGDKHLA46．把以以下列圖中的二叉樹轉(zhuǎn)化成森林。126126847351268473547.一組記錄的關(guān)鍵字為(52,56,26,12,69,85,33,48,70)，給出快速排序的過程。解答：解：52,56,26,12,69,85,33,48,70第一趟排序33,48,26,12,52,85,69,56,70第二趟排序26,12,33,48,52,69,56,70,85第三趟排序12,26,33,48,52,56,70,69,85第四趟排序12,26,33,48,52,56,70,69,85第五趟排序12,26,33,48,52,56,70,69,8548.設(shè)記錄的關(guān)鍵字集合key={51,28,38,86,70,90,7,30,40,25}，試寫出對(duì)key進(jìn)展?jié)u減增量排序〔增量d=5，3，1〕時(shí)，各趟排序完畢后的結(jié)果。解答：各趟排序完畢后的結(jié)果。初始狀態(tài)：5128388670907304025第一趟排序(d=5):5173040259028388670第二趟排序(d=3):2873040258651389070第三趟排序(d=1):7252830384051708690〕49.有一棵二叉樹如以以下列圖所示，分別指出其前序、中序遍歷的結(jié)點(diǎn)序列。AABHGFEDCIJ答：它的前序序列為：ABCDEFGHIJ,它的中序序列為：CDBAFGEIHJ。50.8個(gè)記錄，對(duì)應(yīng)的關(guān)鍵詞為：{25,84,21,47,15,27,68,35,20}寫出快速排序的第一趟排序過程圖示。答：初始鍵值序列[258421471527683520]第一次交換[258421471527683520]↑i=2↑j=9第二次交換[252021471527683584]i↑↑j掃描穿插[252021154727683584]j↑↑iRm與Rj互換[252021154727683584]Rm↑j↑分劃表[152021]25[4727683584]51.給定表〔40,9,56,6,39,73,8,23〕，按數(shù)據(jù)元素在表中的次序構(gòu)造一棵二叉查找樹。答：.二叉排序樹如下。40409563986237352.有二叉樹先序序列為：ABCDEF,中序序列為：CBAEDF,試畫出該二叉樹。答：二叉樹如以以下列圖。AACDFEB53.給定表〔40,36,56,6,64,73,8,23〕，按數(shù)據(jù)元素在表中的次序構(gòu)造一棵二叉查找樹，并求其平均查找長度。答：二叉查找樹如下，平均查找長度為3。404036566486237353．根據(jù)以以下列圖給出的二叉樹，求出先序、中序遍歷的結(jié)點(diǎn)序列。aacedfb答：先序遍歷為：abdcef中序遍歷為：dbaefc54.一組記錄的關(guān)鍵字為〔50，79，8，56，32，41，85〕，給出利用重建堆方法建設(shè)的初始堆〔堆頂最大〕，并給出堆排序的過程。答：1〕建設(shè)的初始堆為:85，79，50，56，32，41，82〕堆排序的過程如下：858579328504156〔C〕第2次交換85418541328505679〔B〕第1次交換8413256507985〔A〕初始建堆858579565041832〔f〕第5次交換85798579565032841〔e〕第4次交換8579568324150〔D〕第3次交換858579565041328〔g〕第6次交換55.答：把以下森林轉(zhuǎn)化為一棵二叉樹。112684735答：森林轉(zhuǎn)化成的二叉樹如以以下列圖。11268473556.數(shù)據(jù)序列為12,5,9,20,6,31,24，對(duì)該數(shù)據(jù)序列進(jìn)展排序，試寫出冒泡排序每趟的結(jié)果。答：初始鍵值序列12592063124第一趟排序[591262024]31第二趟排序[5961220]2431第三趟排序[59612]202431第四趟排序5691220243157.給定表〔40,36,55,6,64,77,9,41〕，按數(shù)據(jù)元素在表中的次序構(gòu)造一棵二叉查找樹，并求其平均查找長度。答：構(gòu)造的二叉查找樹如以以下列圖，其平均查找長度為11/4。404035556496417758.對(duì)于以以下列圖所示的二叉樹，試分別寫出先根遍歷、中根遍歷和后根遍歷該樹所得到的先根序列、中根序列和后根序列。GGFEDCBALKJIH解答：先根遍歷的結(jié)點(diǎn)序列：ABCEIFJDGHKL中遍歷的結(jié)點(diǎn)序列：EICFJBGDKHLA后根遍歷的結(jié)點(diǎn)序列：IEJFCGKLHDBA59.數(shù)據(jù)序列為12,5,9,20,6,31,24，對(duì)該數(shù)據(jù)序列進(jìn)展排序，試寫出歸并排序每趟的結(jié)果。解答：初始鍵值序列12592063124第一趟排序[512][920][631][24]第二趟排序[591220][62431]第三趟排序56912202431〔〕60.序表(5,12,17,19,23,25,30,36,45,49,58)中，用二分法查找關(guān)鍵詞36，進(jìn)展多少次比較后查找成功寫出查找過程。解答：經(jīng)過4次比較查找成功。查找過程如下：5,12,17,19,23,25,30,36,45,49,58j=115,12,17,19,23,25,30,36,45,49,58j=11m=6i=1〔A〕第1次與25進(jìn)展比較j=115,12,17,19,23,25,30,36,45,49,585,12,17,19,23,25,30,36,45,49,58i=7m=9〔B〕第2次與45進(jìn)展比較5,12,17,19,23,25,30,36,45,49,58j=8i=7m=7〔C〕第3次與30進(jìn)展比較i=8i=85,12,17,19,23,25,30,36,45,49,58j=8m=8〔D〕第4次與36進(jìn)展比較61.一組記錄的關(guān)鍵字為(52,56,26,12,69,85,33,48,70)，給出快速排序的過程。解答：52,56,26,12,69,85,33,48,70第一趟排序33,48,26,12,52,85,69,56,70第二趟排序26,12,33,48,52,69,56,70,85第三趟排序12,26,33,48,52,56,70,69,85第四趟排序12,26,33,48,52,56,70,69,85第五趟排序12,26,33,48,52,56,70,69,8562.某二叉樹的后序序列為：ABCDEFG,中序序列為：ACBGEDF,給出它的前序序列。解：它的前序序列為：GCABFED。63．根據(jù)以以下列圖給出的二叉樹，求出中序和后序遍歷的結(jié)點(diǎn)序列。aacedfb解答：中序遍歷為：dbaefc后序遍歷為：dbfeca00342516764.一個(gè)圖如下所示，假設(shè)從頂點(diǎn)0出發(fā)求出其深度優(yōu)先搜索序列。解答：深度優(yōu)先搜索序列：0137425665．給定表〔45,36,56,6,64,32,8,41〕，按數(shù)據(jù)元素在表中的次序構(gòu)造一棵二叉查找樹。解答：按數(shù)據(jù)元素在表中的次序構(gòu)造一棵二叉查找樹為：646483241656364566.找出所有這樣的二叉樹形，其結(jié)點(diǎn)在先根次序遍歷和中根次序遍歷下的排列是一樣的。答：為空樹，或?yàn)槿我唤Y(jié)點(diǎn)至多只有右子樹的二叉樹。下面程序段的時(shí)間復(fù)雜度是O〔mn〕。for(inti=1;i<=n;i++)for(intj=1;j<=m;j++)a[i][j]=0;67.設(shè)有序順序表為{10,20,30,40,50,60,70,80}，采用折半查找時(shí)，查找成功和查找失敗的平均查找長度分別是多少答：包含這8個(gè)元素的二叉判定樹為：303010204070608050很明顯，查找成功的平均比較次數(shù)是；查找失敗的平均比較次數(shù)是。68.給定表〔43,36,56,6,64,32,8,41〕，按數(shù)據(jù)元素在表中的次序構(gòu)造一棵二叉查找樹，并求其平均查找長度。解答：根據(jù)給定表〔43,36,56,6,64,32,8,41〕，構(gòu)造的二叉查找樹如以以下列圖；其平均查找長度為：23/8。646483241656364369.什么是增長樹答：當(dāng)二叉樹中結(jié)點(diǎn)沒有左子樹形或沒有右子樹形時(shí)，增加特殊的結(jié)點(diǎn)，由此生成的二叉樹稱為增長的二叉樹，簡稱增長樹。70.什么是線性表答：一個(gè)線性表是由零個(gè)或多個(gè)具有一樣類型的結(jié)點(diǎn)組成的有序集合。71.什么是一維數(shù)組答：一維數(shù)組是假設(shè)干個(gè)元素的一個(gè)有限序列，每個(gè)元素都通過一個(gè)下標(biāo)來指定，所有的數(shù)組元素都具有一樣的數(shù)據(jù)類型，占據(jù)一樣大小的存儲(chǔ)空間.72.什么是森林答：一個(gè)森林就是一組〔0個(gè)或多個(gè)〕不相交的樹形〔通常諸樹形間還有次序〕。73.什么是強(qiáng)連通圖答：假設(shè)G為有向圖，且對(duì)于V(G)中任意兩個(gè)不同的頂點(diǎn)和，與連通，與也連通，那么稱G為強(qiáng)連通圖。74.什么是圖中兩點(diǎn)的簡單路徑答：如果一條路徑上除了起點(diǎn)和終點(diǎn)可以一樣外，再無一樣的頂點(diǎn)，那么稱此路徑為簡單路徑。75.設(shè)單鏈表中存放著n個(gè)字符，設(shè)計(jì)算法判斷字符串是否中心對(duì)稱，如xyzzyx即為中心對(duì)稱的字符串。答：將全部字符進(jìn)棧，然后將棧中的字符逐個(gè)與鏈表中的字符比較隊(duì)列的定義是什么答：隊(duì)列是一種操作受限的線性表，它只允許在表的一端進(jìn)展插入，在表的另一端進(jìn)展刪除。76.字符串的定義是什么答：字符串是由零個(gè)或多個(gè)字符〔字母、數(shù)字及其它一些符號(hào)〕組成的有限連續(xù)序列，簡稱為串。77.二叉樹的定義是什么答：二叉樹是結(jié)點(diǎn)的有限集合，它必須滿足下面的一個(gè)條件：它是空集。它由一個(gè)根結(jié)點(diǎn)和根結(jié)點(diǎn)的左右子樹構(gòu)成，且其左右子樹滿足二叉樹定義。78.有向圖的定義是什么答：圖G由兩個(gè)集合V和E組成，記為G=(V,E).其中V是頂點(diǎn)的有限集合，E是連接V中兩個(gè)不同頂點(diǎn)〔頂點(diǎn)對(duì)〕的邊的有限集合。如果E中的頂點(diǎn)對(duì)是有序的，即E中的每條邊都是有方向的，那么稱G為有向圖。79.AOV網(wǎng)的定義是什么答：用頂點(diǎn)表示活動(dòng)，有向邊表示活動(dòng)之間先后關(guān)系的有向圖簡稱為AOV網(wǎng)。80.設(shè)計(jì)一個(gè)算法，求出無向無權(quán)連通圖中距離頂點(diǎn)v的最短路徑長度為k的所有頂點(diǎn)，路徑長度以變數(shù)為單位計(jì)算。答：算法中須用從頂點(diǎn)v出發(fā)廣度優(yōu)先遍歷的層次特性來求解，因此，訪問頂點(diǎn)時(shí)要知道一個(gè)頂點(diǎn)相對(duì)于v的層數(shù)，而每個(gè)頂點(diǎn)的層數(shù)是由其前驅(qū)頂點(diǎn)決定的?？梢詮捻旤c(diǎn)v開場，每訪問到一個(gè)頂點(diǎn)就根據(jù)其前驅(qū)的層數(shù)計(jì)算該頂點(diǎn)的層數(shù)，并將層數(shù)值與頂點(diǎn)編號(hào)一起入隊(duì)和出隊(duì)。算法中可以使用兩個(gè)隊(duì)列，一個(gè)記錄入隊(duì)的頂點(diǎn)編號(hào)，另一個(gè)記錄該頂點(diǎn)的層數(shù)，并保持二者的同步。81.兩個(gè)整數(shù)序列A=a1,a2,a3,…,am和B=b1,b2,b3,…,bn已經(jīng)存入兩個(gè)單鏈表中，設(shè)計(jì)一個(gè)算法，判斷序列B是否是序列A的子序列。1)給出算法的基本設(shè)計(jì)思想(4分)；2)用算法描述語言描述算法，并要求對(duì)算法中的關(guān)鍵步驟給出注釋。答：1〕此題實(shí)質(zhì)上是一個(gè)模式匹配問題，這里匹配的元素是整數(shù)而不是字符。因兩整數(shù)序列已存入兩個(gè)鏈表中，操作從兩鏈表的第一個(gè)結(jié)點(diǎn)開場，假設(shè)對(duì)應(yīng)數(shù)據(jù)相等，那么后移指針；假設(shè)對(duì)應(yīng)數(shù)據(jù)不等，那么A鏈表從上次開場比較結(jié)點(diǎn)的后繼開場，B鏈表仍從第一結(jié)點(diǎn)開場比較，直到B鏈表到尾表示匹配成功。A鏈表到尾B鏈表未到尾表示失敗。操作中應(yīng)記住A鏈表每次的開場結(jié)點(diǎn)，以便下趟匹配時(shí)好從其后繼開場。2〕intPattern〔LinkedListA，B〕∥A和B分別是數(shù)據(jù)域?yàn)檎麛?shù)的單鏈表，本算法判斷B是否是A的子序列。如是，返回1；否那么，返回0表示失敗。{p=A；∥p為A鏈表的工作指針，此題假定A和B均無頭結(jié)點(diǎn)。pre=p；∥pre記住每趟比較中A鏈表的開場結(jié)點(diǎn)。q=B；∥q是B鏈表的工作指針。while〔p&&q〕if〔p->data==q->data〕{p=p->next；q=q->next；}else{pre=pre->next；p=pre；∥A鏈表新的開場比較結(jié)點(diǎn)。q=B；}∥q從B鏈表第一結(jié)點(diǎn)開場。if〔q==null〕return〔1〕；∥B是A的子序列。elsereturn〔0〕；∥B不是A的子序列。}∥算法完畢。82.設(shè)一棵二叉樹的先序、中序遍歷序列分別為：先序遍歷序列：ABDFCEGH中序遍歷序列：BFDAGEHC請(qǐng)畫出這棵二叉樹。83.什么是權(quán)圖答：設(shè)G=(V，E)是圖，假設(shè)將圖中的每條邊L都賦上一個(gè)實(shí)數(shù)w(L)作為邊的權(quán)值，那么稱G為權(quán)圖。84.畫出后綴表達(dá)式ab+cde+*-f-gh+*對(duì)應(yīng)的二叉表達(dá)式樹。答：85.用序列(46,88,45,39,70,58,101,10,66,34)建設(shè)一棵二叉查找樹，畫出該樹。答：4545883970101103458664686什么是隊(duì)列的順序存儲(chǔ)答：隊(duì)列的順序存儲(chǔ)是指利用一組地址連續(xù)的存儲(chǔ)單元依次存放自隊(duì)頭到隊(duì)尾的數(shù)據(jù)元素。87.什么是數(shù)組答：數(shù)組通常被定義為具有一樣數(shù)據(jù)類型的元素的集合。88.什么是滿二叉樹答：一棵高度為的滿二叉樹，是具有個(gè)結(jié)點(diǎn)且高度為的二叉樹89.什么是連通圖答：設(shè)G是無向圖，假設(shè)從頂點(diǎn)到頂點(diǎn)有路徑，那么稱與連通。假設(shè)G為無向圖，且V(G)中任意兩頂點(diǎn)都連通，那么稱G為連通圖。90.什么是拓?fù)渑判虼穑和負(fù)湫蛄邪袮OV網(wǎng)中的所有頂點(diǎn)排成一個(gè)線性序列，該序列滿足如下條件：假設(shè)AOV網(wǎng)中存在邊，那么在該序列中，必位于之前。構(gòu)造AOV網(wǎng)的拓?fù)湫蛄械牟僮鞅环Q為拓?fù)渑判颉?1.什么是子串答：一個(gè)串的子串系指該串中的任意一個(gè)連續(xù)子序列92.基于關(guān)鍵詞比較的排序算法的下界是什么請(qǐng)指明直接插入排序、希爾排序、冒泡排序、快速排序、直接選擇排序、堆排序、兩路合并排序算法中，哪些算法的時(shí)間復(fù)雜度到達(dá)了排序下界，并簡單分析其能夠到達(dá)下界的原因。答：O(nlogn).快速排序，堆排序，合并排序到達(dá)下界。主要原因分別是，快速排序的分劃方法一次消除多個(gè)反序?qū)?，堆排序采用基于樹形的最大元查找策略，合并排序采用分治法?3.一個(gè)棧的輸入序列是：1，2，3那么不可能的棧輸出序列是312。94.什么是單向循環(huán)鏈表答：單向循環(huán)鏈表系指將單鏈表中表尾結(jié)點(diǎn)的next域指向表頭結(jié)點(diǎn)，而不是存放空指針NULL，形成一個(gè)環(huán)形鏈表。95.什么是串的長度答：串包含的字符總數(shù)被稱為串的長度。96.什么是線性表的鏈接存儲(chǔ)答：線性表的鏈接存儲(chǔ)是指線性表中的結(jié)點(diǎn)在內(nèi)存中任意存放，相鄰結(jié)點(diǎn)間用指針鏈接。四、解答1.寫出計(jì)算單鏈表head〔head為單鏈表的表頭〕中數(shù)據(jù)域data值為m的結(jié)點(diǎn)個(gè)數(shù)的算法。intcount(Node*head)//計(jì)算單鏈表head中數(shù)據(jù)域data值為m的結(jié)點(diǎn)個(gè)數(shù){Node*p=head->next;intn=0;while(p!=NULL){if(p->data==m)n++；p=p->next;}returnn;}//count2.非空單鏈表head，試設(shè)計(jì)一個(gè)算法，交換p所指結(jié)點(diǎn)與其后繼結(jié)點(diǎn)在鏈表中的位置。解答：intrevers(listnode*head,listnode*p)/*交換p所指結(jié)點(diǎn)與其后繼結(jié)點(diǎn)在鏈表中的位置*/{if(p->next==NULL)return0;listnode*q=head;while(q->next!=p)q=q->next;{r=p->next；q->next=r;p->next=r->next;r->next=p;return1;}//revers3.線性表用帶頭結(jié)點(diǎn)的單向鏈表示，試寫出刪除表中所有data域?yàn)榱愕脑氐乃惴?。解：intDeleteItem(Node*head){Node*p=head;//聲明指針p，并令其指向鏈表頭結(jié)點(diǎn)while(p->nextNode()!=NULL){if(p->nextNode()->data==0)p->next=p->nextNode()->next.elsep=p->nextNode();//指針下移}}4．試設(shè)計(jì)一算法，計(jì)算帶頭結(jié)點(diǎn)的單鏈表head(head指向表頭)的結(jié)點(diǎn)個(gè)數(shù)。解答：intLength()//計(jì)算帶表頭結(jié)點(diǎn)的單鏈表head的長度{Node*p=head->next;intcount=1;while(p->next!=NULL){p=p->next;count++;}returncount;}5．判斷單鏈表head(head指向表頭)是否是遞增的。解答：intorder(Node*head){Node*p=head;while(p->next!=NULL)if(p->data<p->next->data)p=p->next;elsebreak;if(p->next==NULL)return1;elsereturn0;}6.設(shè)計(jì)一個(gè)算法，在一個(gè)單鏈表head中找出值最小的元素。解答：intMin(Node*head)//在單鏈表head中找出值最小的元素{Node*p=head;intmin=p->data;while(p->next!=NULL)阿{if(p->next->data<min)min=p->next->data;p=p->next;}returnmin;}nextdata7設(shè)有兩個(gè)單鏈表L和L1,其結(jié)點(diǎn)構(gòu)造為,試編寫算法判斷鏈表L1中的各元素是否都是單鏈表L中的元素。nextdata解答：intSubLnk(Node*L,Node*L1){Node*p1=L1;while(p1!=NULL){Node*p=L;while((p!=NULL)&&(p1->data!=p->data)){p=p->next;if(p==NULL)return0;elsep1=p1->next;}return1;}}8.設(shè)一棵二叉樹以二叉鏈表為存儲(chǔ)構(gòu)造，設(shè)計(jì)一個(gè)算法交換二叉樹中每個(gè)結(jié)點(diǎn)的左子女和右子女?！?2分〕解答：voidexchange(BinTreeNode*t){if(t!=NULL)BinTreeNode*temp;if((t->lchild!=NULL)||(t->rchild!=NULL)){temp=t->lchild;t->lchild=t->rchild;t->rchild=temp;exchange(t->lchild);exchange(t->rchild);}}9.設(shè)有一個(gè)正整數(shù)序列組成帶頭結(jié)點(diǎn)的單鏈表head，試編寫算法確定在序列中比正整數(shù)x大的數(shù)有幾個(gè)?！?分〕解答：intcount〔Node*head，intx〕∥在帶頭結(jié)點(diǎn)的單鏈表head中，確定序列中比正整數(shù)x大的數(shù)有幾個(gè){Node*p=head->next;intcount=0;while(p!=NULL){if(p->data>x)count++;p=p->next;}returncount;}∥算法count完畢10.設(shè)一棵二叉樹以二叉鏈表為存儲(chǔ)構(gòu)造，試設(shè)計(jì)一個(gè)算法計(jì)算二叉樹中葉子結(jié)點(diǎn)的個(gè)數(shù)。〔12分〕解答：voidcountleaf(BinTreeNode*t,int&count){if(t!=NULL){if((t->lchild==NULL)&&(t->rchild==NULL))count++;〔2分〕countleaf(t->lchild,count);countleaf(t->rchild,count);}}11.設(shè)一棵二叉樹以二叉鏈表為存儲(chǔ)構(gòu)造，試寫一算法求該二叉樹上度為2的結(jié)點(diǎn)個(gè)數(shù)?！?2分〕解答：voidcount2(bitreptrt，intcount){if(t!=NULL){if((t->lchild!=NULL)&&(t->rchild!=NULL))count++;count2(t->lchild,count)；count2(t->rchild,count)；}}//count212.設(shè)一棵二叉樹以二叉鏈表為存儲(chǔ)構(gòu)造，試寫一算法求該二叉樹中最大值〔元〕?！?2分〕解答：voidmaxnode(bitreptrt，intmax){if(t!=NULL)〔2分〕{if(t->data>max)max=t->data;〔4分〕max=maxnode(t->lchild,max)；〔2分〕max=maxnode(t->rchild,max)；〔2分〕}returnmax;〔2分〕}//maxnode13.編寫一個(gè)將二叉樹中每個(gè)結(jié)點(diǎn)的左右孩子交換的算法。(1)給出算法的基本設(shè)計(jì)思想；(2)用算法描述語言描述算法，并要求對(duì)算法中的關(guān)鍵步驟給出注釋。答：〔1〕用前根遍歷的遞歸算法交換二叉樹中各結(jié)點(diǎn)的左、右子樹?！?〕算法的C++實(shí)現(xiàn)：BintreeNode*swap(BintreeNode*b){BintreeNode*t,*t1,*t2;//t為交換后的二叉樹if(b==NULL)t=NULL;else{t=newBintreeNode;//復(fù)制一個(gè)根節(jié)點(diǎn)t->data=b->data;t1=swap(b->left);t2=swap(b->right);t->left=t2;t->right=t1;}return(t);}14．假定整型數(shù)組A[n]中有多個(gè)零元素，試設(shè)計(jì)一個(gè)算法將A中所有非零元素依次移到A的前端。(1)給出算法的基本設(shè)計(jì)思想；(2)用算法描述語言描述算法，并要求對(duì)算法中的關(guān)鍵步驟給出注釋。答：〔1〕方法1：因?yàn)閿?shù)組是一種根據(jù)元素下標(biāo)可以直接存取的數(shù)據(jù)構(gòu)造，設(shè)置一