算法與數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)題

1、算法與數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)題一、 單選題1要求具有同一邏輯結(jié)構(gòu)的數(shù)據(jù)元素具有相同的特性，其含義為（B）。A.數(shù)據(jù)元素具有同一的特點(diǎn)B.不僅數(shù)據(jù)元素包含的數(shù)據(jù)項(xiàng)的個數(shù)相同，而且其對應(yīng)數(shù)據(jù)項(xiàng)的類型要一致C.每個數(shù)據(jù)元素都一樣D.僅需要數(shù)據(jù)元素包含的數(shù)據(jù)項(xiàng)的個數(shù)相同2下列程序段 for(i=1;i<=n;i+) AI,j=0; 的時間復(fù)雜度是（D）。A.O(1)B. O(0)C. O(1+n)D. O(n) 3在一個單鏈表中，已知*q結(jié)點(diǎn)是*p結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)，若在*q 和*p之間插入結(jié)點(diǎn)*s，則執(zhí)行操作（C）。A.s->next=p->next;p->next=s;B.s->n

2、ext=p;p->next=sC.q->next=s;s->next=p;D.p->next=s;s->next=q;4在一個單鏈表中，若刪除*p結(jié)點(diǎn)的后繼結(jié)點(diǎn)，則執(zhí)行操作（A）。A.q=p->next;p->next=q->next;free(q);B. p=p->next;p->next=p->next->next;free(p);C.p->next=q->next;free(p->next);D. p=p->next->next;free(p->next); 5設(shè)指針p指向雙鏈表的

3、某一結(jié)點(diǎn)，則雙鏈表結(jié)構(gòu)的對稱性可以用下面的操作來反映（C）。A.p->prior->next=p->next->next;B. p->prior->prior=p->next->prior;C.p->prior->next=p-> next->prior;D. p->next->next= p->prior->prior;6表達(dá)式a*(b+c)-d的后綴表達(dá)式是(B)。Aabcd*+-Babc+*d-Cabc*+d-D-+*abcd7設(shè)一個棧的輸入序列為A，B，C，D，則借助一個棧所得到的輸出序列不

4、可能是(D)。AA，B，C，DBD，C，B，AC.A，C，D，BD.D，A，B，C8設(shè)一個棧的輸入序列為12345，則借助一個棧所得到的輸出序列不可能是(B)。A23415B54132C.23145D.154329設(shè)有一個順序棧，6個元素1、2 、3、4、5、6依次入棧，如果6個元素出棧的順序是2、3、4、6、5、1，則棧的容量至少應(yīng)該是(B)。A2B3C.5D.610設(shè)有一個順序棧的入棧序列是a、b、c，則3個元素都出棧的可能不同排列個數(shù)為(B)。A4B5C.6D.711若已知一個棧的入棧序列是1，2，3，n，其輸出序列為pl，p2，p3，pn，若pl是n，則 pi是（C）。AiBn-ICn

5、-i+1D不確定12已知廣義表LS=(a，b，c)，(d，e，f)，運(yùn)算head和tail函數(shù)取出元素e的運(yùn)算是(C)。Ahead(tail(LS)Btail(head(LS)Chead(tail(head(tail(LS)Dhead(tail(tail(head(LS)13 二維數(shù)組A的每個元素是由6個字符組成的串，其行下標(biāo)i=0，l，8，列下標(biāo)為j=1，2，10。設(shè)每個字符占一個字節(jié),若按行先存儲，元素A8，5的起始地址與A按列存儲時起始地址相同的元素是(B)。AA8，5BA3，10CA5，8DA0，914數(shù)組A1.5，1.6的每個元素占5個單元，將其按行優(yōu)先次序存儲在起始地址為1000的

6、連續(xù)的內(nèi)存單元中，則元素A5，5的地址為(A)A.1140B.1145C.1120D.112515對二叉樹從1開始進(jìn)行連續(xù)編號，要求每個結(jié)點(diǎn)的編號大于其左右孩子的編號，同一個結(jié)點(diǎn)的左右孩子中，其左孩子的編號小于其右孩子的編號，則可采用遍歷方式是（C）。A.先序B.中序C.后序D.從根開始的層次遍歷16某二叉樹的先序序列和后序序列正好相反，則該二叉樹的特點(diǎn)一定是（B）。A.空或只有一個結(jié)點(diǎn)B.高度等于其結(jié)點(diǎn)數(shù)C.任一結(jié)點(diǎn)無左孩子D.任一結(jié)點(diǎn)無右孩子17下列說法正確的是(D)。(1)二又樹按某種方式線索化后，任一節(jié)點(diǎn)均有指向前趨和后繼的線索(2)二叉樹的前序遍歷序列中，任意一個節(jié)點(diǎn)均處于在子孫節(jié)點(diǎn)

7、前(3)二叉排序樹中任一節(jié)點(diǎn)的值大于其左孩子的值，小于右孩子的值A(chǔ)(1)(2)(3)B(1)(2)C(1)(3)D前面的可選答案都不對18下面的說法中正確的是(B)。(1)任何一棵二叉樹的葉子節(jié)點(diǎn)在三種遍歷中的相對次序不變。(2)按二叉樹定義，具有三個節(jié)點(diǎn)的二叉樹共有6種。A(1)，(2)B(1)C(2)D(1)，(2)都錯19樹有先根遍歷和后根遍歷，樹可以轉(zhuǎn)化為對應(yīng)的二叉樹。下面的說法正確的是(B)。A樹的后根遍歷與其對應(yīng)的二叉樹的后根遍歷相同 B樹的后根遍歷與其對應(yīng)的二叉樹的中根遍歷相同C樹的先根遍歷與其對應(yīng)的二叉樹的中根遍歷相同 D以上都不對20下圖的鄰接表中，從頂點(diǎn)V1 出發(fā)采用深度優(yōu)

8、先搜索法遍歷該圖，則可能的頂點(diǎn)序列是（D）。 A.V1V2V3V4V5B.V1V2V3V5V4C.V1V4V3V5V2D.V1V3V4V5V2 21以下說法不正確的是(D)。A無向圖中的極大連通子圖稱為連通分量B連通圖的廣度優(yōu)先搜索中一般要采用隊(duì)列來暫存剛訪問過的頂點(diǎn)C圖的深度優(yōu)先搜索中一般要采用棧來暫存剛訪問過的頂點(diǎn)D有向圖的遍歷不可采用廣度優(yōu)先搜索22在平衡二叉樹中插入一個結(jié)點(diǎn)后引起了不平衡，設(shè)最低(最接近于葉子)的不平衡點(diǎn)是A，并已知A的左、右孩子的平衡因子分別為-1和0，則應(yīng)進(jìn)行的平衡旋轉(zhuǎn)是(B)。ALL型BLR型CRL型DRR型23設(shè)哈希表長為14，哈希函數(shù)H(key)=key11，

9、表中已有數(shù)據(jù)的關(guān)鍵字為15，38，61，84，四個，現(xiàn)將關(guān)鍵字為49的結(jié)點(diǎn)加到表中，用二次探測再散列法解決沖突，則放入的位置是(A)。A8B3C5D924對散列文件，以下說法錯誤的是(D)。A散列文件插入、刪除方便，不需要索引區(qū)且節(jié)省存儲空間B散列文件只能按關(guān)鍵字隨機(jī)存取且存取速度快C經(jīng)過多次插入、刪除后，可能出現(xiàn)溢出桶滿的情況D散列文件順序存取方便26對有18個元素的有序表作二分查找，則查找A3的比較序列的下標(biāo)為（D）。A.1，2，3B.9，5，2，3C9，5，3D.9，4，2，327在平衡二叉樹中插入一個結(jié)點(diǎn)后造成了不平衡，設(shè)最低的不平衡結(jié)點(diǎn)為A，并已知A的左孩子的平衡因子為0，右孩子的平

10、衡因子為1，則應(yīng)調(diào)整以使其平衡，所作的平衡旋轉(zhuǎn)是（C）。A.LL型B.LR型C.RL型D.RR型28在n個結(jié)點(diǎn)且為完全二叉樹的二叉排序樹中查找一個鍵值，其平均比較次數(shù)的數(shù)量級為（B）。A.O(n)B.O(log2n)C.O(nlog2n)D.O(n2)29下列排序算法中，在待排序數(shù)據(jù)已基本有序時，效率最高的排序方法是(A)。A插入B選擇C快速D堆30下面關(guān)于B-樹和B+樹的敘述中，不正確的結(jié)論是(A)。AB-樹和B+樹都能有效地支持順序查找BB-樹和B+樹都能有效地支持隨機(jī)查找CB-樹和B+樹都是平衡的多叉樹DB-樹和B+樹都可用于文件索引結(jié)構(gòu)31關(guān)鍵路徑是事件結(jié)點(diǎn)網(wǎng)絡(luò)中(B)。A從源點(diǎn)到匯點(diǎn)

11、的最長路徑B從源點(diǎn)到匯點(diǎn)的最短路徑C最長的回路D最短的回路32將兩個各有n個元素的有序表歸并成一個有序表，其最少的比較次數(shù)是(A)。AnB2n-1C2nDn-133下列排序算法中，時間復(fù)雜度不受數(shù)據(jù)初始狀態(tài)影響，恒為0(nlog2n)的是（A）。A.堆排序B.冒泡排序C.直接選擇排序D.快速排序34下列排序算法中，某一趟結(jié)束后未必能選出一個元素放在其最終位置上的是（D）A.堆排序B.冒泡排序C.快速排序D.直接插入排序35數(shù)據(jù)表A中有10000個元素，如果僅要求求出其中最大的10個元素，則采用最節(jié)省時間的排序算法是（A）。A.堆排序B.希爾排序C.快速排序D.直接選擇排序36數(shù)據(jù)結(jié)構(gòu)被形式地定

12、義為（D,R），其中D 是（ ）。A.算法B.操作的集合C.數(shù)據(jù)元素的集合D.數(shù)據(jù)關(guān)系的集合37順序表是線性表的（A）。A.順序存儲結(jié)構(gòu) B.鏈?zhǔn)酱鎯Y(jié)構(gòu) C.索引存儲結(jié)構(gòu) D.散列存儲結(jié)構(gòu)38在一個單鏈表中，已知*p結(jié)點(diǎn)不是最后結(jié)點(diǎn)，若在*p之后插入結(jié)點(diǎn)*s，則執(zhí)行操作（B）。A.s->next=p;p->next=s;B.s->next=p->next;p->next=sC.s->next=p->next;p=s;D.p->next=s;s->next= p ;39循環(huán)隊(duì)列AO.m-1存放其元素值，用front和rear分別表示隊(duì)頭及隊(duì)

13、尾，則循環(huán)隊(duì)列滿的條件是(A)。A(Q.rear+1)m=Q.frontBQ.rear=Q.front+1CQ.rear+l=Q.frontDQ.real=Q.front40如果以鏈棧為存儲結(jié)構(gòu)，則出棧操作時( B )。A必須判棧滿B必須判別?？誄.判別棧中元素類型D.不必作任何判別41對矩陣壓縮存儲是為了(B)。A.方便運(yùn)算B.節(jié)省空間C.方便存儲D.提高運(yùn)算速度42將一棵有100個結(jié)點(diǎn)的完全二叉樹從根這一層開始，每一層上從左到右依次對結(jié)點(diǎn)進(jìn)行編號，根結(jié)點(diǎn)的編號為1，則編號為49的結(jié)點(diǎn)的左孩子編號為（B）。A.98B.99C.50D.4843二義樹在線索化后，仍不能有效求解的問題是（D）。A

14、.先序線索二叉樹中求先序后繼B.中序線索二叉樹中求中序后繼C.中序線索二叉樹中求中序前趨D.后序線索二又樹中求后序后繼44對于關(guān)鍵字序列(12，13，11，18，60，15，7，18，25，100)，用篩選法建堆，則開始結(jié)點(diǎn)的鍵值必須為（C）。A.100B.12C.60D.1545無向圖G=(V E)，其中V=a，b，C，d，e，f，E=<a，b>，<a，e>，<a，c>，<b，e>，<c，f>，<f，d>，<e，d>，對該圖進(jìn)行深度優(yōu)先排序，得到的頂點(diǎn)序列正確的是(D)。Aa，b，e，c，d，f Ba，c，f

15、, e，b，dCa，e，b，c，f, d Da，e，d，f, c, b46設(shè)圖G用鄰接表存儲，則拓?fù)渑判虻臅r間復(fù)雜度為(B )。AD(n) BO(n+e) CO(n×n) D0(n×e)47關(guān)于散列法查找說法正確的是(B)。A采用鏈地址解決沖突時，查找一個元素的時間是相同的B采用鏈地址解決沖突時，若規(guī)定插入總是在鏈?zhǔn)?，則插入任一個元素的時間是相同的C采用鏈地址解決沖突容易引起聚集現(xiàn)象D再散列不易產(chǎn)生聚集48在平衡二叉樹中插入一個結(jié)點(diǎn)后引起了不平衡，設(shè)最低(最接近于葉子)的不平衡點(diǎn)是A，并已知A的左、右孩子的平衡因子分別為-1和0，則應(yīng)進(jìn)行的平衡旋轉(zhuǎn)是(B)。ALL型BLR型

16、CRL型DRR型49在有向圖G的拓?fù)湫蛄兄?，若頂點(diǎn)Vi在頂點(diǎn)Vj之前，則下列情形不可能出現(xiàn)的是(D)。AG中有弧<Vi，Vj>BG中有一條從Vi到Vj的路徑CG中沒有弧<Vi，Vj>DG中有一條從Vj到Vi的路徑50排序算法中，算法可能會出現(xiàn)下面情況：初始數(shù)據(jù)有序時，花費(fèi)的時間反而最多的是（C）。A.堆排序B.冒泡排序C.快速排序D.SHELL排序二、填空（問答）題1數(shù)據(jù)結(jié)構(gòu)被形式地定義為（D,R），其中D和R 的含義是什么。（D是數(shù)據(jù)元素的集合，R是數(shù)據(jù)關(guān)系的集合）。數(shù)據(jù)的邏輯結(jié)構(gòu)包括哪四種類型。（線性結(jié)構(gòu)、樹形結(jié)構(gòu)、圖形結(jié)構(gòu)、集合類型）。從存儲結(jié)構(gòu)的概念上講，順序表

17、是線性表的（順序存儲結(jié)構(gòu) ），鏈表是（鏈?zhǔn)酱鎯Y(jié)構(gòu)）。2算法的五個重要特性有哪些。（有窮性、確定性、可行性、輸入、輸出）。抽象數(shù)據(jù)類型是指一個（數(shù)學(xué)模型）以及定義在該模型上的（一組操作）。3在含有n個結(jié)點(diǎn)的順序存儲的線性表中，在任意一個結(jié)點(diǎn)前插入一個結(jié)點(diǎn)所需要移動結(jié)點(diǎn)的平均次數(shù)為（ n/2 ）。在含有n個結(jié)點(diǎn)的順序存儲的線性表中，任意刪除一個結(jié)點(diǎn)所需要移動結(jié)點(diǎn)的平均次數(shù)為（ n-1/2 ）。對一個線性表分別進(jìn)行遍歷和逆置運(yùn)算，其最好的時間復(fù)雜度量級均為（O(n)）。4線性結(jié)構(gòu)中的一個結(jié)點(diǎn)代表一個（數(shù)據(jù)元素 ）。若線性表中最常用的操作是取第i個元素和查找該元素的前驅(qū)，則采用的存儲方式最能節(jié)省時間

18、的是（順序表 ）。若最常用的操作是插入和刪除第i個元素，則采用的存儲方式最能節(jié)省時間的是（單鏈表 ）。5在一個不帶頭結(jié)點(diǎn)的單鏈表中，在表頭插入或刪除與在其他位置插入或刪除操作過程不同，需要修改（頭指針）。在單鏈表中設(shè)置頭結(jié)點(diǎn)的作用是（便于操作），無論鏈表是否為空。使（頭指針）均不為空。對于雙向鏈表，在兩個結(jié)點(diǎn)之間插入一個新結(jié)點(diǎn)需修改的指針共有（4個），單鏈表為（2個）。6如果以鏈棧為存儲結(jié)構(gòu)，則出棧操作時( 必須判別?？?)，與順序棧相比，鏈棧有一個明顯的優(yōu)勢是( 不易出現(xiàn)棧滿 )。7循環(huán)隊(duì)列采用數(shù)組data1n來存儲元素的值，并用front和rear分別作為其頭尾指針。為區(qū)分隊(duì)列的滿和空，約

19、定：隊(duì)中能夠存放的元素個數(shù)最大為n-l，也即至少有一個元素空間不用，則在任意時刻，至少可以知道一個空的元素的下標(biāo)是（front） ；入隊(duì)時，可用語句（rear=rear+1%n）求出新元素在數(shù)組data中的下標(biāo)。8已知棧的輸入序列為1，2，3，n，輸出序列為a1，a2，an，a2=n的輸出序列共有（n-1）種輸出序列。9稀疏矩陣一般的壓縮存儲方法有兩種，它們是用（哈希表、三元組和十字鏈表 )。對矩陣壓縮存儲是為了(節(jié)省空間)。10將下三角矩陣Al.8，1.8的下三角部分逐行地存儲到起始地址為1000的內(nèi)存單元中，已知每個元素占4個單元，則A7，5的地址為 （1100）。11已知數(shù)組A1.10，

20、1.10為對稱矩陣，其中每個元素占5個單元?，F(xiàn)將其下三角部分按行優(yōu)先次序存儲在起始地址為1000的連續(xù)的內(nèi)存單元中，則元素A5，6對應(yīng)的地址為（1095）。12兩個串相等的充要條件是，兩個串的(長度)相等，且其所對應(yīng)各個位置的（字符）也相等。13取出廣義表A=(x，(a，b，c，d)中原子C的函數(shù)是（ head(tail(tail(head(tail(head(A) ）。14在有n個結(jié)點(diǎn)的二又鏈表中，值為非空的鏈域的個數(shù)為（n-1）。在有n個葉子結(jié)點(diǎn)的哈夫曼樹中，總結(jié)點(diǎn)數(shù)是（2n-1）。在樹形結(jié)構(gòu)中，根結(jié)點(diǎn)數(shù)只有（1個），其余每個結(jié)點(diǎn)有且僅有一個元素（前驅(qū)）結(jié)點(diǎn)。15一棵二叉樹L的高度為h，所

21、有結(jié)點(diǎn)的度或?yàn)?，或?yàn)?，則這棵二叉樹最少的結(jié)點(diǎn)數(shù)為( 2h-1 )。已知二叉樹有50個葉子結(jié)點(diǎn)，則該二叉樹的總結(jié)點(diǎn)數(shù)至少是（99）。將一棵有100個結(jié)點(diǎn)的完全二叉樹從根這一層開始，每一層上從左到右依次對結(jié)點(diǎn)進(jìn)行編號，根結(jié)點(diǎn)的編號為1，則編號為49的結(jié)點(diǎn)的左孩子編號為（98 ）。有64個結(jié)點(diǎn)的完全二叉樹的深度為( 7 )。16拓?fù)渑判蛑荒苡糜冢ㄓ邢驘o環(huán)圖）。連通圖是指圖中任意兩個頂點(diǎn)之間（都連通的無向圖 ）。一個有n個頂點(diǎn)的無向連通圖，它所包含的連通分量個數(shù)最多為( 1 )個。任何一個無向連通圖的最小生成樹（有一棵或多棵）。若含有n個頂點(diǎn)的圖形成一個環(huán)，則它有（n）棵生成樹。17求圖的最小生成

22、樹有兩種算法，（prim（普里姆）算法適合于求稠密圖的最小生成樹，（kruskal（克魯斯卡爾）算法適合于求稀疏圖的最小生成樹。設(shè)圖G用鄰接表存儲，則拓?fù)渑判虻臅r間復(fù)雜度為(O(n+e) )。18在一棵三叉樹中，度為3的結(jié)點(diǎn)數(shù)為2個，度為2的結(jié)點(diǎn)數(shù)為1個，度為1的結(jié)點(diǎn)數(shù)為2個，則度為0的結(jié)點(diǎn)數(shù)為( 6 )。19中序表達(dá)式A*(B+C)(D-E+F)的后序表達(dá)式是(ABC+*DE-F+/ )。 20有向圖G用鄰接矩陣A存儲，則頂點(diǎn)i的入度等于A中（第i列1的元素之和 ）。具有10個頂點(diǎn)的無向圖，邊的總數(shù)最多為（45）個，具有n個頂點(diǎn)的強(qiáng)連通有向圖G，邊的總數(shù)至少有（n）條。21從未排序序列中依次

23、取出元素與已排序序列(初始時為空)中的元素進(jìn)行比較，將其放入已排序序列的正確位置上的方法，稱為( 插入排序 )。對于關(guān)鍵字序列(12，13，11，18，60，15，7，18，25，100)，用篩選法建堆，則開始結(jié)點(diǎn)的鍵值必須為（ 60 ）。22在有序表Al.20中，采用二分查找算法查找元素值等于A12的元素，所比較過的元素的下標(biāo)依次為（10,15,12），查找元素值等于5的元素，所比較過的元素個數(shù)為（5）個。分別采用堆排序、快速排序、插入排序和歸并排序算法對初始狀態(tài)為遞增序列的表按遞增順序排序，最省時間的是（插入排序）算法，最費(fèi)時問的是（快速排序）算法。直接選擇排序算法所執(zhí)行的元素交換次數(shù)最多

24、為（n-1）次，最好情況下所作的交換元素的次數(shù)為（0）次。在堆排序，希爾排序，快速排序，歸并排序算法中，占用輔助空間最多的是 (歸并排序)。二分查找法要求查找表中各元素的關(guān)鍵字的值得排列必須是（遞增或遞減或有序 ）。23若一個待散列存儲的線性表長度為n，用于散列的散列表長度為m，則m應(yīng)（小于等于）n，裝填因子公式為（n/m）。散列表的平均查找長度(與處理沖突方法有關(guān)而與表的長度有關(guān) )。24在平衡二叉樹上刪除一個結(jié)點(diǎn)后可以通過旋轉(zhuǎn)使其平衡，最壞情況下需旋轉(zhuǎn)（O(log2n) ）次。25貪心算法的基本思想是，逐步構(gòu)造最優(yōu)解，每步都按照一定的標(biāo)準(zhǔn)，稱為（貪心）準(zhǔn)則，做出決策。0/1背包問題的三種貪

25、心準(zhǔn)則中，相對較優(yōu)的是（價值密度）貪心準(zhǔn)則。分治法與（遞歸）技術(shù)緊密結(jié)合。與分治法不同的是，動態(tài)規(guī)劃是（自底向上或自下而上）、逐級求解子問題。分枝定界的搜索策略與（廣度優(yōu)先）類似，而回溯方法則采用（深度優(yōu)先）搜索策略。26對于單鏈表、單循環(huán)鏈表和雙向鏈表，若僅僅知道一個指向鏈表中某結(jié)點(diǎn)的指針p，能否將p所指的結(jié)點(diǎn)的數(shù)據(jù)元素與它的直接前趨（假設(shè)存在）交換？若不可以，說明理由；若可以，寫出主要算法。（1）單鏈表不能，單循環(huán)鏈表和雙向鏈表可以。（2）單循環(huán)鏈表 q=p;while(q>next!=p) q=q>next;temp=p>data; p>data=q>dat

26、a;q>data=temp;（3）雙向鏈表：q=p>prior; temp=q>data; q>data=p>data;p>data=temp;27設(shè)有三對角矩陣a1.n,1.n把非零元素按列存儲在向量b1.3*n-2中，使得bk=ai,j。求： 用i，j表示k的下標(biāo)變換公式 （k=2*(j-1)+i） 用k表示i，j的下標(biāo)變換公式 （j=(k DIV 3)+1 i=k-2*(j-1)）28內(nèi)存中一片連續(xù)空間（不妨設(shè)地址從1到m），提供給兩個棧S1和S2使用，怎樣分配這部分存儲空間，使得對任意一個棧，僅當(dāng)這部分全滿時才發(fā)生上溢。(為了盡量利用空間，減少溢出的

27、可能，可采用棧頂相向，棧底分設(shè)兩端的存儲方式，這樣，對任何一個棧，僅當(dāng)整個空間全滿時才會發(fā)生上溢。) 29有一n個結(jié)點(diǎn)的樹，其中所有分支結(jié)點(diǎn)的度均為k，求該樹中葉子結(jié)點(diǎn)的個數(shù)。設(shè)no為葉子結(jié)點(diǎn)數(shù)，nk為度為k的結(jié)點(diǎn)數(shù)，n為結(jié)點(diǎn)總數(shù)（依題意：n=no+nk (1) n= knk+1 (2)綜合(1) 和(2)得： no=n-(n-1)/k 30. 設(shè)有n個無序元素，按非遞減次序排序，但只想得到前面長度為k的部分序列，其中n>>k,最好采用什么排序方法？為什么？如有這樣一個序列：59,11,26,34,17,91,25，得到的部分序列是11,17,25，對于該例使用所選擇的方法實(shí)現(xiàn)時，

28、共執(zhí)行多少次比較？（1）采用堆排序最合適，因?yàn)楫?dāng)部分序列較小時，堆排序的時間復(fù)雜度近似為O(n)。（2）初始建堆：比較8次輸出11,第一次調(diào)整：比較次輸出17第二次調(diào)整：比較2次輸出 25,總共比較14次。31. 設(shè)二叉排序樹中關(guān)鍵字由1至1000的整數(shù)組成，現(xiàn)要查找關(guān)鍵字為363的結(jié)點(diǎn)，下述關(guān)鍵字序列哪一個不可能是在二叉排序樹中查到的序列？說明原因。（1）51,250,501,390,320,340,382,363;（2）24,877,125,342,501,623,421,363;(1）是；不是。因?yàn)椴樵冃蛄惺牵翰?21時，其623左、右兩個區(qū)間都不存在，查找失敗。)32. 在執(zhí)行某個排序

29、算法過程中，出現(xiàn)了排序關(guān)鍵字朝著最終排序序列相反方向的移動，從而認(rèn)為該算法是不穩(wěn)定的，這種說法對么？為什么？（不正確。算法的穩(wěn)定性是考察最終排行的位置交換，與中間過程無關(guān)。如：對于整數(shù)序列（18，36，25）。按基數(shù)排序的LSD方法，第一趟排序后（25，36，18），第二趟排序后得到（18，25，36），18雖向相反方向移動，但不影響最終位置。）33. 將算術(shù)表達(dá)式（a+b）+c*(d+e)+f）*(g+h)轉(zhuǎn)化為二叉樹( 二叉鏈表結(jié)構(gòu))（略）34在線性結(jié)構(gòu)中，開始結(jié)點(diǎn)沒有（前驅(qū)）結(jié)點(diǎn)，最后一個元素沒有（后繼）結(jié)點(diǎn)。35線性表的邏輯結(jié)構(gòu)是（線性結(jié)構(gòu)），其所含結(jié)點(diǎn)的個數(shù)稱為線性表的（長度）。36

30、隊(duì)列的特性是（先入先出或后入后出），棧的特性是（后入先出或先入后出）。37數(shù)組Al.10，1.10的每個元素占5個單元，將其按列優(yōu)先次序存儲在起始地址為1000的連續(xù)的內(nèi)存單元中，則元素A5，6的地址為（1270）。38若某二叉樹有20個葉子結(jié)點(diǎn)，有30個結(jié)點(diǎn)僅有一個孩子，則該二叉樹的總結(jié)點(diǎn)數(shù)是（69）。39樹t的存儲結(jié)構(gòu)為二叉鏈表bt，樹t中的一個葉子結(jié)點(diǎn)在bt中滿足條件（bt->lchild<>null&& bt->rchild<>null;40求圖的最小生成樹有兩種算法，(prim（普里姆）) 算法適合于求稠密圖的最小生成樹。41在索引

31、順序表上實(shí)現(xiàn)分塊查找，在等概率查找情況下，其平均查找長度不僅與表的（長度）有關(guān)，而且與每一塊中的元素（長度）有關(guān)。42分枝定界的搜索策略與(廣度優(yōu)先) 類似，而回溯方法則采用(深度優(yōu)先)搜索策略。430/1背包問題的三種貪婪準(zhǔn)則中，相對較優(yōu)的是(價值密度) 貪婪準(zhǔn)則。三、應(yīng)用題1有一個二叉樹按層次順序存放在一維數(shù)組中，如下圖所示：試求：（1）該樹的后序遍歷序列。（C,E,B,D,A） （2）畫出該樹的后序線索樹。（略）1 2 3 4 5 6 7 8 9 10 11 ACBED2按順序輸入下列頂點(diǎn)對: (1,2)、(1,6)、(2,6)、(1,4)、(6,4)、(1,3)、(3,4)、(6,5)

32、、(4,5)、(1,5)、(3,5)，（1）畫出相應(yīng)的鄰接表。（2）寫出在鄰接表上，從頂點(diǎn)3開始（表下標(biāo)從0開始）的DFS序列和DFS生成樹。（1）鄰接表15324V1V2V3 V4V5V6 123450123450503405245302 0134（2）DFS序列 2-0-1-5-3-43設(shè)一哈希表長為13，采用線性探測法解決沖突，哈希函數(shù)H(key)=key%13,（1）畫出在空表中依次插入關(guān)鍵字25，20，36，15，41，52，29，72，67后的哈希表。（2）求在等概率情況下，查找成功和查找不成功的平均查找長度。（1） 100 101 102 103 104 105 106 107

33、108 109 110 111 112521541296720723625（2）平均查找長度查找成功的平均查找長度=(5*1+3*2+1*4)/9=1.6查找不成功的平均查找長度=(2+1+5+4+3+2+1+3+2+1+2+1+3)/13=30/134對下面的關(guān)鍵字集（30，15，21，40，25，26，36，37），若查找表的裝填因子為0.8，采用線性探測再散列解決沖突：（1）設(shè)計哈希函數(shù)；（2）畫出哈希表；（1）表長: m=n/=8/0.8 =10 哈希函數(shù)： H(key)=key%7 （2） 哈希表 0 1 2 3 4 5 6 7 8 9 21153036254026375寫出對關(guān)鍵字

34、序列503,087,512,061,908,124,897,275,653,426建立一棵平衡二叉排序樹的過程，并寫出調(diào)整平衡時的旋轉(zhuǎn)類型。503 503 087 512 RL 087 897 061 124 908 061 124 512 908 897 503 503 087 897 RR 087 897 061 124 512 908 061 275 512 908 275 653 124 426 653 426 6. 已知一棵二叉樹的先序序列和中序序列分別為：abdgicefhj及bgidaecfjh，畫出該的二叉樹的后序線索二叉樹。（略）7. 假設(shè)通信電文使用的字符集為a,b,c,d

35、,e,f,g，字符的哈夫曼編碼依次為：0110，10，110，111，00，0111和010。（1）畫出此哈夫曼樹（略）（2）若這些字符在電文中出現(xiàn)的頻度分別為3、35、13、15、20、5、9，求哈夫曼樹的帶權(quán)路徑長度。（帶權(quán)路徑長度WPL=2.53）8. 已知有一個10個頂點(diǎn)的連通圖，頂點(diǎn)編號為1至10，其邊的關(guān)系集合表示為（1，2）（1，3），（1，8），（2，4），（3，9），（3，10），（5，7），（6，7），（7，8），（8，9），試求：畫出該連通圖及以頂點(diǎn)為根的深度優(yōu)先生成樹。（略）9. 對下面的關(guān)鍵字集35，15，21，99，25，26，36，37，01，18寫出快速排序的每

36、趟結(jié)果和最終結(jié)果。（略）10有字符串次序?yàn)?*-y-a/y2，利用棧，給出將次序改為3y-*ay2/-的操作步驟。（可用X代表掃描改字符串過程中順序取一個字符進(jìn)棧的操作，用S代表從棧中取出一個字符加入到新字符串尾的出棧操作。例如，ABC變?yōu)锽CA的操作步驟為XXSXSS）。（略）11. 設(shè)有一個由正整數(shù)組成的無序單鏈表，閱讀下面的算法，指出該算法的功能，并在“/”后面加上必要的注釋。void F1(Linklist &L) p=Lnext; pre=p; /pre為最小結(jié)點(diǎn)指針while(p) if(pdata<predata;pre=p; p=pnext; /（1） /whil

37、eprintf(predata); /（2）if(prenext && predata%2！=0) /（3）temp=predata; predata=prenextdata; prenextdata=temp;/if/F1算法功能：找出最小值結(jié)點(diǎn)，且打印該數(shù)值。若該數(shù)值是奇數(shù)且有后繼，則與后繼結(jié)點(diǎn)的數(shù)值交換。(1)查找最小值結(jié)點(diǎn)；（2）輸出最小值結(jié)點(diǎn)；（3）若該數(shù)值是奇數(shù)且有后繼，則與后繼結(jié)點(diǎn)的數(shù)值交換。12. 已知二叉樹的存儲結(jié)構(gòu)為二叉鏈表，LinkList和BiTree為已定義的指針類型，ListNode為已定義的結(jié)點(diǎn)類型，閱讀下面算法并回答：LinkList L=Nul

38、l; p;void F2(BiTree T) if(T) F2(Tlchild); if(!Tlchild)&&(!Tchild) p=(ListNode *)malloc(sizeof(ListNode);pdata=Tdata; pnext=L;L=p; /ifF2(Trchild);/if/F2（1） 說明該算法的功能；（2） 對于一棵有8個結(jié)點(diǎn)的完全二叉數(shù)（假設(shè)結(jié)點(diǎn)順序?yàn)锳、B、C、D、E、F、G、H），畫出執(zhí)行上述算法后建立的結(jié)構(gòu)。（1）按中序遍歷二叉樹，逆序建立以葉子結(jié)點(diǎn)為鏈表結(jié)點(diǎn)、以L為頭指針的無頭結(jié)點(diǎn)的單鏈表。（2）（略）四、算法分析與設(shè)計題1設(shè)有一個由正整數(shù)組

39、成的無序單鏈表，閱讀下面的算法，指出該算法的功能，并在“/”后面加上必要的注釋。void F1(Linklist &L) p=Lnext; pre=p; /pre為最小結(jié)點(diǎn)指針while(p) if(pdata<predata;pre=p; p=pnext; /（1）查找最小值結(jié)點(diǎn)/whileprintf(predata); /（2）輸出最小值結(jié)點(diǎn)if(prenext && predata%2=0) /（3）刪除其后繼結(jié)點(diǎn)p=prenext, prenext=pnext;free(p);/if/ F1算法功能：找出最小值結(jié)點(diǎn)，打印該數(shù)值。若該值是偶數(shù)且有后繼，則將

40、其后繼結(jié)點(diǎn)刪除。2設(shè)有n個大小不等的數(shù)據(jù)組（n個數(shù)據(jù)組中數(shù)據(jù)的總數(shù)為m），順序存放在空間區(qū)D內(nèi)，每個數(shù)據(jù)占一個存儲單元。數(shù)據(jù)組的首地址由數(shù)組S給出，閱讀下面的算法，指出該算法的功能，并在“/”后面加上必要的注釋。void F1(sqlist &L,int i, ElemType x)if(i>=1&&i<=L.length) /（1）插入到D區(qū)for(j=0,p=L.elem0;j<=m;j+) p+; /（2）求D區(qū)空閑空間首地址if(i=L.length) *p=x;/（3）插入到第n個數(shù)組else for(q=L.elemi;p>=q;-p

41、) *(p+1)=*p; *p=x; /插入xfor(q=&L.elemi,p=&L.elemL.length-1; p>=q;q+) (*q)+;/elsem+; /if/F1算法功能：將數(shù)據(jù)x插入到D區(qū)，插入后D和S關(guān)系不變。3設(shè)有一個正整數(shù)序列組成的非遞減有序單鏈表，閱讀下面的算法，指出該算法的功能，并在“/后面加上必要的注釋。void F1 (Linklist L;int,x) p= Lnext; q=p; /p為工作指針pre=L; Lnext=NULL; ./q指最小元素while(P&&Pdata<x)/ （1）比x小的數(shù)遞減r=pne

42、xt; pnext=Lnext;Lnext=p; p=r; /（2）置逆/whileqnext=p; pre=q; /（3）重新鏈接/F1算法功能：在單鏈表中將比正整數(shù)x小的數(shù)按遞減次序排列。4假設(shè)一個僅包含二元運(yùn)算符的算術(shù)表達(dá)式以二叉鏈表形式存儲在二叉樹 T 中，閱讀下面的算法，指出該算法的功能，并在“/”后面加上必要的注釋。int F1(BiTrec T)if(!T) return 0; if(!Tlchild &&!Trchild)/（1）判斷是否為葉子結(jié)點(diǎn)return (Tdata);Lv= F1(Tlchild);Rv= F1(Trchild); switch(Tda

43、ta)/（2）運(yùn)算 case + : V=Lv+Rv; break; case- : V=Lv-Rv; break; case*: V=Lv*Rv; break; case/: V=lv/Rv; break; /switch return V;/（3）返回結(jié)果/F1算法功能：后序遍歷二叉樹，求算術(shù)表達(dá)式的值。5在有向圖G中，如果r到G的每個結(jié)點(diǎn)都有路徑可達(dá)，則稱結(jié)點(diǎn)r為G的根結(jié)點(diǎn)，下面算法的功能是判斷有向圖G是否有根，若有，則打印出所有根結(jié)點(diǎn)的值。請?zhí)羁昭a(bǔ)全算法，并在“/”后面給以注釋。void F2(ALGraph G) /利用深度優(yōu)先搜索，判斷有向圖G是否有根結(jié)點(diǎn)。int visitedm

44、axsige,count; /count為記錄結(jié)構(gòu)的頂點(diǎn)數(shù)。 for(v=0;v<G.vexnum ;v+) for(v=0;v<G.vexnum;v+) (1)_;/ 初始化頂點(diǎn)數(shù)組 count=0; DFS(G,v) ; if(count=(2)_)/ 判斷是否為根printf(G.verv.data); / F2void DFS(ALGraph G,int v) /從第v個頂點(diǎn)出發(fā)遞歸地深度優(yōu)先遍歷圖Gvisitedv=1; count+; for(p=G.verticesv.firstarc; p; p=pnextarc) w=padjvex; if(!visitedw)

45、(3)_;/ 深度優(yōu)先搜索 /DFS（1）visitedv=0;（2）G.vexnum （3）DFS(G,w) ;6下面算法的功能是實(shí)現(xiàn)單鏈表中的簡單選擇排序，其中L為鏈表的頭結(jié)點(diǎn)指針，請?zhí)羁昭a(bǔ)全算法，并在“/”后面給以注釋。 void F2(LinkList &L)/用單鏈表實(shí)現(xiàn)簡單選擇排序 p=L>next; /初始化，p為工作指針 while(p) min=p; (1)_;/ q為插入指針，min為當(dāng)前最小指針 while(2)_) /一趟選擇排序 if(q>data<min>data) min=p; q=q>next; /while(q)if( (

46、3)_)/ 交換temp=p>data; p>data=min>data;min>data=temp; /if p=p>next; /while(p) /F2（1）q=p>next; （2）q 或q !=null （3）min7設(shè)計算法DeleteX的功能是：刪除單鏈表L中值為x的結(jié)點(diǎn)的直接前趨結(jié)點(diǎn)。（設(shè)L是帶頭結(jié)點(diǎn)的單鏈表的頭指針，并為已知的LinkList類型）void DeleteX(LinkList &L) /刪除單鏈表中的直接前驅(qū)結(jié)點(diǎn) p=L>next; /初始化，p為工作指針 while(p&& p>next&

47、gt;data!=x)/q為前驅(qū)結(jié)點(diǎn)指針 q=p;p=p>next; / while if(p) /刪除q>next=p>next; free(p);/if / DeleteX8Internet的域名系統(tǒng)是一個典型的層次結(jié)構(gòu)，可用樹形結(jié)構(gòu)表示。每一個域名服務(wù)器提供的區(qū)域信息恰好是以該結(jié)點(diǎn)為根的子樹中的全部的IP地址。設(shè)計算法以孩子-兄弟鏈表作為樹的存儲結(jié)構(gòu),實(shí)現(xiàn)搜索所有www域名的IP地址。void Outpath(CSTree T,Stack &S)/搜索IP地址 while(T) Push(S,T>data) if(!T>firstchild &

48、;& T>data=”www”) visitstack(S);/輸出一條路徑 else Outpath(T>firstchild ,&S)/遞歸遍歷左子樹 Pop(S,e); T=T>nextsibiling; / 遍歷右子樹 /while /Outpath 9設(shè)計算法實(shí)現(xiàn)以逆鄰接表為存儲結(jié)構(gòu)的有向圖的拓?fù)渑判颍ㄒ蠼o出逆鄰接表的存儲結(jié)構(gòu)定義）。(1)存儲結(jié)構(gòu)定義vexdatafirstin 頂點(diǎn)結(jié)構(gòu) adjvexinfofirstarc 表結(jié)點(diǎn)結(jié)構(gòu) (2) 算法設(shè)計int toposort (ALGraph G,int tpv) /以逆鄰接表為存儲結(jié)構(gòu)的有向

49、圖的拓?fù)渑判騮op=0; for(i=0;i<G.vexnum;i+) for(p=G.adjlisti.firstedge;p;pnext)findoutdegree(G,outdegree); / 對各頂點(diǎn)求出度 outdegreepadjvex+; InitStack(&S); /初始化棧 for(i=0;i<G.Vexnum;i+) if(outdegreei=0) Push(&S,i); /出度為零的頂點(diǎn)入棧 while(!Stack(S) Pop(&S,i);printf(G.adjlisti.vextex); tpvtop+=i; for(p=

50、G.adjlisti.firstedge;p;pnext) j=padjvex; outdegreej-; if(!outdegreej) Push(&S,j); /出度為零的頂點(diǎn)入棧/for/while if(top<G.vexnum) return 0; /無環(huán) else /輸出頂點(diǎn)拓?fù)渑判蛐蛄?for(i=0;j=top-1;i< G.vexnum/2;i+,j-)/置逆輸出 temp=tpvi;tpvi=tpvj;tpvj=temp;/forreturn 1; /else/toposort10已知深度為h的二叉樹采用順序存儲結(jié)構(gòu)存放在數(shù)組B1.2h-1中，設(shè)計一個遞歸算法，產(chǎn)生該二叉樹的二叉鏈表結(jié)構(gòu)。void CreateTree(int B2h,int j,BiTree t)/創(chuàng)建t樹的二叉鏈表結(jié)構(gòu)，j為數(shù)組下標(biāo)，初值為1 t=( BiTree ) malloc( sizeof(BiTNode);t>data=Bj; /創(chuàng)建根結(jié)點(diǎn) if(2*j>2h) t>Lchild=null;/無左子樹 else /遞歸創(chuàng)建左子樹 t>Lchild=CreateTree(B,2*j,t>Lchild)； if