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

算法與數(shù)據(jù)結(jié)構(gòu)復習題單選題1．要求具有同一邏輯結(jié)構(gòu)的數(shù)據(jù)元素具有相同的特性，其含義為（B）。A.數(shù)據(jù)元素具有同一的特點B.不僅數(shù)據(jù)元素包含的數(shù)據(jù)項的個數(shù)相同，而且其對應數(shù)據(jù)項的類型要一致C.每個數(shù)據(jù)元素都一樣D.僅需要數(shù)據(jù)元素包含的數(shù)據(jù)項的個數(shù)相同2．下列程序段for(i=1;i<=n;i++)A[I,j]=0;的時間復雜度是（D）。A.O(1) B.O(0) C.O(1+n) D.O(n)3．在一個單鏈表中，已知*q結(jié)點是*p結(jié)點的前驅(qū)結(jié)點，若在*q和*p之間插入結(jié)點*s，則執(zhí)行操作（C）。A.s->next=p->next;p->next=s; B.s->next=p;p->next=sC.q->next=s;s->next=p; D.p->next=s;s->next=q;4．在一個單鏈表中，若刪除*p結(jié)點的后繼結(jié)點，則執(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指向雙鏈表的某一結(jié)點，則雙鏈表結(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．表達式a*(b+c)--d的后綴表達式是(B)。A．a(chǎn)bcd*+- B．a(chǎn)bc+*d- C．a(chǎn)bc*+d- D．-+*abcd7．設(shè)一個棧的輸入序列為A，B，C，D，則借助一個棧所得到的輸出序列不可能是(D)。A．A，B，C，DB．D，C，B，A C.A，C，D，B D.D，A，B，C8．設(shè)一個棧的輸入序列為12345，則借助一個棧所得到的輸出序列不可能是(B)。A．23415 B．54132 C.23145 D.154329．設(shè)有一個順序棧，6個元素1、2、3、4、5、6依次入棧，如果6個元素出棧的順序是2、3、4、6、5、1，則棧的容量至少應該是(B)。A．2 B．3 C.5 D.610．設(shè)有一個順序棧的入棧序列是a、b、c，則3個元素都出棧的可能不同排列個數(shù)為(B)。A．4 B．5 C.6 D.711．若已知一個棧的入棧序列是1，2，3，…，n，其輸出序列為pl，p2，p3，…，pn，若pl是n，則pi是（C）。A．i B．n-IC．n-i+1D．不確定12．已知廣義表LS=((a，b，c)，(d，e，f))，運算head和tail函數(shù)取出元素e的運算是(C)。A．head(tail(LS))B．tail(head(LS))C．head(tail(head(tail(LS))))D．head(tail(tail(head(LS))))13．二維數(shù)組A的每個元素是由6個字符組成的串，其行下標i=0，l，…，8，列下標為j=1，2．…，10。設(shè)每個字符占一個字節(jié),若按行先存儲，元素A[8，5]的起始地址與A按列存儲時起始地址相同的元素是(B)。A．A[8，5] B．A[3，10] C．A[5，8] D．A[0，9]14．數(shù)組A[1..5，1..6]的每個元素占5個單元，將其按行優(yōu)先次序存儲在起始地址為1000的連續(xù)的內(nèi)存單元中，則元素A[5，5]的地址為(A)A.1140B.1145C.1120D.112515．對二叉樹從1開始進行連續(xù)編號，要求每個結(jié)點的編號大于其左右孩子的編號，同一個結(jié)點的左右孩子中，其左孩子的編號小于其右孩子的編號，則可采用遍歷方式是（C）。A.先序 B.中序 C.后序 D.從根開始的層次遍歷16．某二叉樹的先序序列和后序序列正好相反，則該二叉樹的特點一定是（B）。A.空或只有一個結(jié)點 B.高度等于其結(jié)點數(shù) C.任一結(jié)點無左孩子 D.任一結(jié)點無右孩子17．下列說法正確的是(D)。(1)二又樹按某種方式線索化后，任一節(jié)點均有指向前趨和后繼的線索(2)二叉樹的前序遍歷序列中，任意一個節(jié)點均處于在子孫節(jié)點前(3)二叉排序樹中任一節(jié)點的值大于其左孩子的值，小于右孩子的值A(chǔ)．(1)(2)(3)B．(1)(2)C．(1)(3)D．前面的可選答案都不對18．下面的說法中正確的是(B)。(1)任何一棵二叉樹的葉子節(jié)點在三種遍歷中的相對次序不變。(2)按二叉樹定義，具有三個節(jié)點的二叉樹共有6種。A．(1)，(2)B．(1)C．(2)D．(1)，(2)都錯19．樹有先根遍歷和后根遍歷，樹可以轉(zhuǎn)化為對應的二叉樹。下面的說法正確的是(B)。A．樹的后根遍歷與其對應的二叉樹的后根遍歷相同B．樹的后根遍歷與其對應的二叉樹的中根遍歷相同C．樹的先根遍歷與其對應的二叉樹的中根遍歷相同D．以上都不對20．下圖的鄰接表中，從頂點V1出發(fā)采用深度優(yōu)先搜索法遍歷該圖，則可能的頂點序列是（D）。A.V1V2V3V4V5B.V1V2V3V5V4C.V1V4V3V5V2D.V1V3V4V5V221．以下說法不正確的是(D)。A．無向圖中的極大連通子圖稱為連通分量B．連通圖的廣度優(yōu)先搜索中一般要采用隊列來暫存剛訪問過的頂點C．圖的深度優(yōu)先搜索中一般要采用棧來暫存剛訪問過的頂點D．有向圖的遍歷不可采用廣度優(yōu)先搜索22．在平衡二叉樹中插入一個結(jié)點后引起了不平衡，設(shè)最低(最接近于葉子)的不平衡點是A，并已知A的左、右孩子的平衡因子分別為-1和0，則應進行的平衡旋轉(zhuǎn)是(B)。A．LL型 B．LR型 C．RL型 D．RR型23．設(shè)哈希表長為14，哈希函數(shù)H(key)=key％11，表中已有數(shù)據(jù)的關(guān)鍵字為15，38，61，84，四個，現(xiàn)將關(guān)鍵字為49的結(jié)點加到表中，用二次探測再散列法解決沖突，則放入的位置是(A)。A．8B．3C．5D．924．對散列文件，以下說法錯誤的是(D)。A．散列文件插入、刪除方便，不需要索引區(qū)且節(jié)省存儲空間B．散列文件只能按關(guān)鍵字隨機存取且存取速度快C．經(jīng)過多次插入、刪除后，可能出現(xiàn)溢出桶滿的情況D．散列文件順序存取方便26．對有18個元素的有序表作二分查找，則查找A[3]的比較序列的下標為（D）。A.1，2，3 B.9，5，2，3 C．9，5，3 D.9，4，2，327．在平衡二叉樹中插入一個結(jié)點后造成了不平衡，設(shè)最低的不平衡結(jié)點為A，并已知A的左孩子的平衡因子為0，右孩子的平衡因子為1，則應調(diào)整以使其平衡，所作的平衡旋轉(zhuǎn)是（C）。A.LL型 B.LR型 C.RL型 D.RR型28．在n個結(jié)點且為完全二叉樹的二叉排序樹中查找一個鍵值，其平均比較次數(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)。A．B-樹和B+樹都能有效地支持順序查找B．B-樹和B+樹都能有效地支持隨機查找C．B-樹和B+樹都是平衡的多叉樹D．B-樹和B+樹都可用于文件索引結(jié)構(gòu)31．關(guān)鍵路徑是事件結(jié)點網(wǎng)絡(luò)中(B)。A．從源點到匯點的最長路徑B．從源點到匯點的最短路徑C．最長的回路D．最短的回路32．將兩個各有n個元素的有序表歸并成一個有序表，其最少的比較次數(shù)是(A)。A．nB．2n-1 C．2n D．n-133．下列排序算法中，時間復雜度不受數(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)被形式地定義為（D,R），其中D是（）。A.算法 B.操作的集合 C.數(shù)據(jù)元素的集合 D.數(shù)據(jù)關(guān)系的集合37．順序表是線性表的（A）。A.順序存儲結(jié)構(gòu)B.鏈式存儲結(jié)構(gòu)C.索引存儲結(jié)構(gòu)D.散列存儲結(jié)構(gòu)38．在一個單鏈表中，已知*p結(jié)點不是最后結(jié)點，若在*p之后插入結(jié)點*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)隊列A[O..m-1]存放其元素值，用front和rear分別表示隊頭及隊尾，則循環(huán)隊列滿的條件是(A)。A．(Q.rear+1)％m==Q.frontB．Q.rear==Q.front+1C．Q.rear+l=Q.frontD．Q.real==Q.front40．如果以鏈棧為存儲結(jié)構(gòu)，則出棧操作時(B)。A．必須判棧滿 B．必須判別?？?C.判別棧中元素類型 D.不必作任何判別41．對矩陣壓縮存儲是為了(B)。A.方便運算 B.節(jié)省空間 C.方便存儲 D.提高運算速度42．將一棵有100個結(jié)點的完全二叉樹從根這一層開始，每一層上從左到右依次對結(jié)點進行編號，根結(jié)點的編號為1，則編號為49的結(jié)點的左孩子編號為（B）。A.98 B.99 C.50 D.4843．二義樹在線索化后，仍不能有效求解的問題是（D）。A.先序線索二叉樹中求先序后繼 B.中序線索二叉樹中求中序后繼C.中序線索二叉樹中求中序前趨 D.后序線索二又樹中求后序后繼44．對于關(guān)鍵字序列(12，13，11，18，60，15，7，18，25，100)，用篩選法建堆，則開始結(jié)點的鍵值必須為（C）。A.100 B.12 C.60 D.1545．無向圖G=(VE)，其中V={a，b，C，d，e，f}，E={<a，b>，<a，e>，<a，c>，<b，e>，<c，f>，<f，d>，<e，d>}，對該圖進行深度優(yōu)先排序，得到的頂點序列正確的是(D)。A．a(chǎn)，b，e，c，d，fB．a(chǎn)，c，f,e，b，dC．a(chǎn)，e，b，c，f,dD．a(chǎn)，e，d，f,c,b46．設(shè)圖G用鄰接表存儲，則拓撲排序的時間復雜度為(B)。A．D(n)B．O(n+e)C．O(n×n)D．0(n×e)47．關(guān)于散列法查找說法正確的是(B)。A．采用鏈地址解決沖突時，查找一個元素的時間是相同的B．采用鏈地址解決沖突時，若規(guī)定插入總是在鏈首，則插入任一個元素的時間是相同的C．采用鏈地址解決沖突容易引起聚集現(xiàn)象D．再散列不易產(chǎn)生聚集48．在平衡二叉樹中插入一個結(jié)點后引起了不平衡，設(shè)最低(最接近于葉子)的不平衡點是A，并已知A的左、右孩子的平衡因子分別為-1和0，則應進行的平衡旋轉(zhuǎn)是(B)。A．LL型 B．LR型 C．RL型 D．RR型49．在有向圖G的拓撲序列中，若頂點Vi在頂點Vj之前，則下列情形不可能出現(xiàn)的是(D)。A．G中有弧<Vi，Vj>B．G中有一條從Vi到Vj的路徑C．G中沒有弧<Vi，Vj>D．G中有一條從Vj到Vi的路徑50．排序算法中，算法可能會出現(xiàn)下面情況：初始數(shù)據(jù)有序時，花費的時間反而最多的是（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)的概念上講，順序表是線性表的（順序存儲結(jié)構(gòu)），鏈表是（鏈式存儲結(jié)構(gòu)）。2．算法的五個重要特性有哪些。（有窮性、確定性、可行性、輸入、輸出）。抽象數(shù)據(jù)類型是指一個（數(shù)學模型）以及定義在該模型上的（一組操作）。3．在含有n個結(jié)點的順序存儲的線性表中，在任意一個結(jié)點前插入一個結(jié)點所需要移動結(jié)點的平均次數(shù)為（n/2）。在含有n個結(jié)點的順序存儲的線性表中，任意刪除一個結(jié)點所需要移動結(jié)點的平均次數(shù)為（n-1/2）。對一個線性表分別進行遍歷和逆置運算，其最好的時間復雜度量級均為（O(n)）。4．線性結(jié)構(gòu)中的一個結(jié)點代表一個（數(shù)據(jù)元素）。若線性表中最常用的操作是取第i個元素和查找該元素的前驅(qū)，則采用的存儲方式最能節(jié)省時間的是（順序表）。若最常用的操作是插入和刪除第i個元素，則采用的存儲方式最能節(jié)省時間的是（單鏈表）。5．在一個不帶頭結(jié)點的單鏈表中，在表頭插入或刪除與在其他位置插入或刪除操作過程不同，，需要修改（頭指針）。在單鏈表中設(shè)置頭結(jié)點的作用是（便于操作），無論鏈表是否為空。使（頭指針）均不為空。對于雙向鏈表，在兩個結(jié)點之間插入一個新結(jié)點需修改的指針共有（4個），單鏈表為（2個）。6．如果以鏈棧為存儲結(jié)構(gòu)，則出棧操作時(必須判別?？?，與順序棧相比，鏈棧有一個明顯的優(yōu)勢是(不易出現(xiàn)棧滿)。7．循環(huán)隊列采用數(shù)組data[1．．n]來存儲元素的值，并用front和rear分別作為其頭尾指針。為區(qū)分隊列的滿和空，約定：隊中能夠存放的元素個數(shù)最大為n-l，也即至少有一個元素空間不用，則在任意時刻，至少可以知道一個空的元素的下標是（front）；入隊時，可用語句（rear=rear+1%n）求出新元素在數(shù)組data中的下標。8．已知棧的輸入序列為1，2，3…．，n，輸出序列為a1，a2，…，an，a2=n的輸出序列共有（n-1）種輸出序列。9．稀疏矩陣一般的壓縮存儲方法有兩種，它們是用（哈希表、三元組和十字鏈表)。對矩陣壓縮存儲是為了(節(jié)省空間)。10．將下三角矩陣A[l..8，1..8]的下三角部分逐行地存儲到起始地址為1000的內(nèi)存單元中，已知每個元素占4個單元，則A[7，5]的地址為（1100）。11．已知數(shù)組A[1..10，1..10]為對稱矩陣，其中每個元素占5個單元。現(xiàn)將其下三角部分按行優(yōu)先次序存儲在起始地址為1000的連續(xù)的內(nèi)存單元中，則元素A[5，6]對應的地址為（1095）。12．兩個串相等的充要條件是，兩個串的(長度)相等，且其所對應各個位置的（字符）也相等。13．取出廣義表A=((x，(a，b，c，d)))中原子C的函數(shù)是（head(tail(tail((head(tail(head(A))))))）。14．在有n個結(jié)點的二又鏈表中，值為非空的鏈域的個數(shù)為（n-1）。在有n個葉子結(jié)點的哈夫曼樹中，總結(jié)點數(shù)是（2n-1）。在樹形結(jié)構(gòu)中，根結(jié)點數(shù)只有（1個），其余每個結(jié)點有且僅有一個元素（前驅(qū)）結(jié)點。15．一棵二叉樹L的高度為h，所有結(jié)點的度或為0，或為2，則這棵二叉樹最少的結(jié)點數(shù)為(2h-1)。已知二叉樹有50個葉子結(jié)點，則該二叉樹的總結(jié)點數(shù)至少是（99）。將一棵有100個結(jié)點的完全二叉樹從根這一層開始，每一層上從左到右依次對結(jié)點進行編號，根結(jié)點的編號為1，則編號為49的結(jié)點的左孩子編號為（98）。有64個結(jié)點的完全二叉樹的深度為(7)。16．拓撲排序只能用于（有向無環(huán)圖）。連通圖是指圖中任意兩個頂點之間（都連通的無向圖）。一個有n個頂點的無向連通圖，它所包含的連通分量個數(shù)最多為(1)個。任何一個無向連通圖的最小生成樹（有一棵或多棵）。若含有n個頂點的圖形成一個環(huán)，則它有（n）棵生成樹。17．求圖的最小生成樹有兩種算法，（prim（普里姆））算法適合于求稠密圖的最小生成樹，（kruskal（克魯斯卡爾））算法適合于求稀疏圖的最小生成樹。設(shè)圖G用鄰接表存儲，則拓撲排序的時間復雜度為(O(n+e))。18．在一棵三叉樹中，度為3的結(jié)點數(shù)為2個，度為2的結(jié)點數(shù)為1個，度為1的結(jié)點數(shù)為2個，則度為0的結(jié)點數(shù)為(6)。19．中序表達式A*(B+C)／(D-E+F)的后序表達式是(ABC+*DE-F+/)。20．有向圖G用鄰接矩陣A存儲，則頂點i的入度等于A中（第i列1的元素之和）。具有10個頂點的無向圖，邊的總數(shù)最多為（45）個，具有n個頂點的強連通有向圖G，邊的總數(shù)至少有（n）條。21．從未排序序列中依次取出元素與已排序序列(初始時為空)中的元素進行比較，將其放入已排序序列的正確位置上的方法，稱為(插入排序)。對于關(guān)鍵字序列(12，13，11，18，60，15，7，18，25，100)，用篩選法建堆，則開始結(jié)點的鍵值必須為（60）。22．在有序表A[l..20]中，采用二分查找算法查找元素值等于A[12]的元素，所比較過的元素的下標依次為（10,15,12），查找元素值等于5的元素，所比較過的元素個數(shù)為（5）個。分別采用堆排序、快速排序、插入排序和歸并排序算法對初始狀態(tài)為遞增序列的表按遞增順序排序，最省時間的是（插入排序）算法，最費時問的是（快速排序）算法。直接選擇排序算法所執(zhí)行的元素交換次數(shù)最多為（n-1）次，最好情況下所作的交換元素的次數(shù)為（0）次。在堆排序，希爾排序，快速排序，歸并排序算法中，占用輔助空間最多的是(歸并排序)。二分查找法要求查找表中各元素的關(guān)鍵字的值得排列必須是（遞增或遞減或有序）。23．若一個待散列存儲的線性表長度為n，用于散列的散列表長度為m，則m應（小于等于）n，裝填因子公式為（n/m）。散列表的平均查找長度(與處理沖突方法有關(guān)而與表的長度有關(guān))。24．在平衡二叉樹上刪除一個結(jié)點后可以通過旋轉(zhuǎn)使其平衡，最壞情況下需旋轉(zhuǎn)（O(log2n)）次。25．貪心算法的基本思想是，逐步構(gòu)造最優(yōu)解，每步都按照一定的標準，稱為（貪心）準則，做出決策。0/1背包問題的三種貪心準則中，相對較優(yōu)的是（價值密度）貪心準則。分治法與（遞歸）技術(shù)緊密結(jié)合。與分治法不同的是，動態(tài)規(guī)劃是（自底向上或自下而上）、逐級求解子問題。分枝定界的搜索策略與（廣度優(yōu)先）類似，而回溯方法則采用（深度優(yōu)先）搜索策略。26．對于單鏈表、單循環(huán)鏈表和雙向鏈表，若僅僅知道一個指向鏈表中某結(jié)點的指針p，能否將p所指的結(jié)點的數(shù)據(jù)元素與它的直接前趨（假設(shè)存在）交換？若不可以，說明理由；若可以，寫出主要算法。（1）單鏈表不能，單循環(huán)鏈表和雙向鏈表可以。（2）單循環(huán)鏈表q=p;while(q－>next!=p)q=q－>next;temp=p－>data;p－>data=q－>data;q－>data=temp;（3）雙向鏈表：q=p－>prior;temp=q－>data;q－>data=p－>data;p－>data=temp;27．設(shè)有三對角矩陣a[1..n,1..n]把非零元素按列存儲在向量b[1..3*n-2]中，使得b[k]=a[i,j]。求：⑴用i，j表示k的下標變換公式（k=2*(j-1)+i）⑵用k表示i，j的下標變換公式（j=(kDIV3)+1i=k-2*(j-1)）28．內(nèi)存中一片連續(xù)空間（不妨設(shè)地址從1到m），提供給兩個棧S1和S2使用，怎樣分配這部分存儲空間，使得對任意一個棧，僅當這部分全滿時才發(fā)生上溢。(為了盡量利用空間，減少溢出的可能，可采用棧頂相向，棧底分設(shè)兩端的存儲方式，這樣，對任何一個棧，僅當整個空間全滿時才會發(fā)生上溢。)29．有一n個結(jié)點的樹，其中所有分支結(jié)點的度均為k，求該樹中葉子結(jié)點的個數(shù)。設(shè)no為葉子結(jié)點數(shù)，nk為度為k的結(jié)點數(shù)，n為結(jié)點總數(shù)（依題意：n=no+nk—(1)n=knk+1(2)綜合(1)和(2)得：no=n-(n-1)/k30.設(shè)有n個無序元素，按非遞減次序排序，但只想得到前面長度為k的部分序列，其中n>>k,最好采用什么排序方法？為什么？如有這樣一個序列：{59,11,26,34,17,91,25}，得到的部分序列是{11,17,25}，對于該例使用所選擇的方法實現(xiàn)時，共執(zhí)行多少次比較？（1）采用堆排序最合適，因為當部分序列較小時，堆排序的時間復雜度近似為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é)點，下述關(guān)鍵字序列哪一個不可能是在二叉排序樹中查到的序列？說明原因。（1）51,250,501,390,320,340,382,363;（2）24,877,125,342,501,623,421,363;((1）是；⑵不是。因為查詢序列是：查421時，其623左、右兩個區(qū)間都不存在，查找失敗。)32.在執(zhí)行某個排序算法過程中，出現(xiàn)了排序關(guān)鍵字朝著最終排序序列相反方向的移動，從而認為該算法是不穩(wěn)定的，這種說法對么？為什么？（不正確。算法的穩(wěn)定性是考察最終排行的位置交換，與中間過程無關(guān)。如：對于整數(shù)序列（18，36，25）。按基數(shù)排序的LSD方法，第一趟排序后（25，36，18），第二趟排序后得到（18，25，36），18雖向相反方向移動，但不影響最終位置。）33.將算術(shù)表達式（（a+b）+c*(d+e)+f）*(g+h)轉(zhuǎn)化為二叉樹(二叉鏈表結(jié)構(gòu))（略）34．在線性結(jié)構(gòu)中，開始結(jié)點沒有（前驅(qū)）結(jié)點，最后一個元素沒有（后繼）結(jié)點。35．線性表的邏輯結(jié)構(gòu)是（線性結(jié)構(gòu)），其所含結(jié)點的個數(shù)稱為線性表的（長度）。36．隊列的特性是（先入先出或后入后出），棧的特性是（后入先出或先入后出）。37．數(shù)組A[l..10，1..10]的每個元素占5個單元，將其按列優(yōu)先次序存儲在起始地址為1000的連續(xù)的內(nèi)存單元中，則元素A[5，6]的地址為（1270）。38．若某二叉樹有20個葉子結(jié)點，有30個結(jié)點僅有一個孩子，則該二叉樹的總結(jié)點數(shù)是（69）。39．樹t的存儲結(jié)構(gòu)為二叉鏈表bt，樹t中的一個葉子結(jié)點在bt中滿足條件（bt->lchild<>null&&bt->rchild<>null;40．求圖的最小生成樹有兩種算法，(prim（普里姆）)算法適合于求稠密圖的最小生成樹。41．在索引順序表上實現(xiàn)分塊查找，在等概率查找情況下，其平均查找長度不僅與表的（長度）有關(guān)，而且與每一塊中的元素（長度）有關(guān)。42．分枝定界的搜索策略與(廣度優(yōu)先)類似，而回溯方法則采用(深度優(yōu)先)搜索策略。43．0/1背包問題的三種貪婪準則中，相對較優(yōu)的是(價值密度)貪婪準則。三、應用題1．有一個二叉樹按層次順序存放在一維數(shù)組中，如下圖所示：試求：（1）該樹的后序遍歷序列。（C,E,B,D,A）（2）畫出該樹的后序線索樹。（略）1234567891011ACBED2．按順序輸入下列頂點對:(1,2)、(1,6)、(2,6)、(1,4)、(6,4)、(1,3)、(3,4)、(6,5)、(4,5)、(1,5)、(3,5)，（1）畫出相應的鄰接表。（2）寫出在鄰接表上，從頂點3開始（表下標從0開始）的DFS序列和DFS生成樹。（1）鄰接表1∧5324V1∧5324V1V2V3V4V5V6123450123450∧0∧50∧30∧340∧5240∧5245∧305∧3020∧1340∧134（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）100101102103104105106107108109110111112521541296720723625（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哈希表012345678921153036254026375．寫出對關(guān)鍵字序列{503,087,512,061,908,124,897,275,653,426}建立一棵平衡二叉排序樹的過程，并寫出調(diào)整平衡時的旋轉(zhuǎn)類型。503503087512RL087897061124908061124512908897503503087897RR0878970611245129080612755129082756531244266534266.已知一棵二叉樹的先序序列和中序序列分別為：abdgicefhj及bgidaecfjh，畫出該的二叉樹的后序線索二叉樹。（略）7.假設(shè)通信電文使用的字符集為{a,b,c,d,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個頂點的連通圖，頂點編號為1至10，其邊的關(guān)系集合表示為{（1，2）（1，3），（1，8），（2，4），（3，9），（3，10），（5，7），（6，7），（7，8），（8，9）}，試求：畫出該連通圖及以頂點③為根的深度優(yōu)先生成樹。（略）9.對下面的關(guān)鍵字集{35，15，21，99，25，26，36，37，01，18}寫出快速排序的每趟結(jié)果和最終結(jié)果。（略）10．有字符串次序為3*-y-a/y^2，利用棧，給出將次序改為3y-*ay2^/-的操作步驟。（可用X代表掃描改字符串過程中順序取一個字符進棧的操作，用S代表從棧中取出一個字符加入到新字符串尾的出棧操作。例如，ABC變?yōu)锽CA的操作步驟為XXSXSS）。（略）11.設(shè)有一個由正整數(shù)組成的無序單鏈表，閱讀下面的算法，指出該算法的功能，并在“//”后面加上必要的注釋。voidF1(Linklist&L){p=L→next;pre=p;//pre為最小結(jié)點指針while(p){if(p→data<pre→data;pre=p;p=p→next;//（1）}//whileprintf(pre→data);//（2）if(pre→next&&pre→data%2！=0){//（3）temp=pre→data;pre→data=pre→next→data;pre→next→data=temp;}//if}//F1算法功能：找出最小值結(jié)點，且打印該數(shù)值。若該數(shù)值是奇數(shù)且有后繼，則與后繼結(jié)點的數(shù)值交換。(1)查找最小值結(jié)點；（2）輸出最小值結(jié)點；（3）若該數(shù)值是奇數(shù)且有后繼，則與后繼結(jié)點的數(shù)值交換。12.已知二叉樹的存儲結(jié)構(gòu)為二叉鏈表，LinkList和BiTree為已定義的指針類型，ListNode為已定義的結(jié)點類型，閱讀下面算法并回答：LinkListL=Null;p;voidF2(BiTreeT){if(T){F2(T→lchild);if((!T→lchild)&&(!T→child){p=(ListNode*)malloc(sizeof(ListNode));p→data=T→data;p→next=L;L=p;}//ifF2(T→rchild);}//if}//F2說明該算法的功能；對于一棵有8個結(jié)點的完全二叉數(shù)（假設(shè)結(jié)點順序為A、B、C、D、E、F、G、H），畫出執(zhí)行上述算法后建立的結(jié)構(gòu)。（1）按中序遍歷二叉樹，逆序建立以葉子結(jié)點為鏈表結(jié)點、以L為頭指針的無頭結(jié)點的單鏈表。（2）（略）四、算法分析與設(shè)計題1．設(shè)有一個由正整數(shù)組成的無序單鏈表，閱讀下面的算法，指出該算法的功能，并在“//”后面加上必要的注釋。voidF1(Linklist&L){p=L→next;pre=p;//pre為最小結(jié)點指針while(p){if(p→data<pre→data;pre=p;p=p→next;//（1）查找最小值結(jié)點}//whileprintf(pre→data);//（2）輸出最小值結(jié)點if(pre→next&&pre→data%2==0){//（3）刪除其后繼結(jié)點p=pre→next,pre→next=p→next;free(p);}//if}//F1算法功能：找出最小值結(jié)點，打印該數(shù)值。若該值是偶數(shù)且有后繼，則將其后繼結(jié)點刪除。2．設(shè)有n個大小不等的數(shù)據(jù)組（n個數(shù)據(jù)組中數(shù)據(jù)的總數(shù)為m），順序存放在空間區(qū)D內(nèi)，每個數(shù)據(jù)占一個存儲單元。數(shù)據(jù)組的首地址由數(shù)組S給出，閱讀下面的算法，指出該算法的功能，并在“//”后面加上必要的注釋。voidF1(sqlist&L,inti,ElemTypex){if(i>=1&&i<=L.length){//（1）插入到D區(qū)for(j=0,p=L.elem[0];j<=m;j++)p++;//（2）求D區(qū)空閑空間首地址if(i==L.length)*p=x;//（3）插入到第n個數(shù)組else{for(q=L.elem[i];p>=q;--p)*(p+1)=*p;*p=x;//插入xfor(q=&L.elem[i],p=&L.elem[L.length-1];p>=q;q++)(*q)++;//elsem++;}//if}//F1算法功能：將數(shù)據(jù)x插入到D區(qū)，插入后D和S關(guān)系不變。3．設(shè)有一個正整數(shù)序列組成的非遞減有序單鏈表，閱讀下面的算法，指出該算法的功能，并在“//后面加上必要的注釋。voidF1(LinklistL;int,x){p=L→next;q=p;//p為工作指針pre=L;L→next=NULL;.//q指最小元素while(P&&P→data<x){//（1）比x小的數(shù)遞減r=p→next;p→next=L→next;L→next=p;p=r;//（2）置逆}//whileq→next=p;pre=q;//（3）重新鏈接}//F1算法功能：在單鏈表中將比正整數(shù)x小的數(shù)按遞減次序排列。4．假設(shè)一個僅包含二元運算符的算術(shù)表達式以二叉鏈表形式存儲在二叉樹T中，閱讀下面的算法，指出該算法的功能，并在“//”后面加上必要的注釋。intF1(BiTrecT){if(!T)return0;if(!T→lchild&&!T→rchild)//（1）判斷是否為葉子結(jié)點return(T→data);Lv=F1(T→lchild);Rv=F1(T→rchild);switch(T→data){//（2）運算case’+’:V=Lv+Rv;break;case’-’:V=Lv-Rv;break;case’*’:V=Lv*Rv;break;case’/’:V=lv/Rv;break;}//switchreturnV;//（3）返回結(jié)果}//F1算法功能：后序遍歷二叉樹，求算術(shù)表達式的值。5．在有向圖G中，如果r到G的每個結(jié)點都有路徑可達，則稱結(jié)點r為G的根結(jié)點，下面算法的功能是判斷有向圖G是否有根，若有，則打印出所有根結(jié)點的值。請?zhí)羁昭a全算法，并在“//”后面給以注釋。voidF2(ALGraphG){//利用深度優(yōu)先搜索，判斷有向圖G是否有根結(jié)點。intvisited[maxsige],count;//count為記錄結(jié)構(gòu)的頂點數(shù)。for(v=0;v<G.vexnum;v++){for(v=0;v<G.vexnum;v++)(1)_;//初始化頂點數(shù)組count=0;DFS(G,v);if(count==(2)_)//判斷是否為根printf(G.ver[v].data);}}//F2voidDFS(ALGraphG,intv){//從第v個頂點出發(fā)遞歸地深度優(yōu)先遍歷圖Gvisited[v]=1;count++;for(p=G.vertices[v].firstarc;p;p=p→nextarc){w=p→adjvex;if(!visited[w])(3)_;//深度優(yōu)先搜索}}//DFS（1）visited[v]=0;（2）G.vexnum（3）DFS(G,w);6．下面算法的功能是實現(xiàn)單鏈表中的簡單選擇排序，其中L為鏈表的頭結(jié)點指針，請?zhí)羁昭a全算法，并在“//”后面給以注釋。voidF2(LinkList&L){//用單鏈表實現(xiàn)簡單選擇排序p=L－>next;//初始化，p為工作指針while(p){min=p;(1)___________;//q為插入指針，min為當前最小指針while((2)___________){//一趟選擇排序if(q－>data<min－>data)min=p;q=q－>next;}//while(q)if((3)___________){//交換temp=p－>data;p－>data=min－>data;min－>data=temp;}//ifp=p－>next;}//while(p)}//F2（1）q=p－>next;（2）q或q!=null（3）min7．設(shè)計算法DeleteX的功能是：刪除單鏈表L中值為x的結(jié)點的直接前趨結(jié)點。（設(shè)L是帶頭結(jié)點的單鏈表的頭指針，并為已知的LinkList類型）voidDeleteX(LinkList&L){//刪除單鏈表中的直接前驅(qū)結(jié)點p=L－>next;//初始化，p為工作指針while(p&&p－>next－>data!=x){//q為前驅(qū)結(jié)點指針q=p;p=p－>next;}//whileif(p){//刪除q－>next=p－>next;free(p);}//if}//DeleteX8．Internet的域名系統(tǒng)是一個典型的層次結(jié)構(gòu)，可用樹形結(jié)構(gòu)表示。每一個域名服務(wù)器提供的區(qū)域信息恰好是以該結(jié)點為根的子樹中的全部的IP地址。設(shè)計算法以孩子-兄弟鏈表作為樹的存儲結(jié)構(gòu),實現(xiàn)搜索所有www域名的IP地址。voidOutpath(CSTreeT,Stack&S){//搜索IP地址while(T){Push(S,T－>data)if(!T－>firstchild&&T－>data==”www”)visitstack(S);//輸出一條路徑elseOutpath(T－>firstchild,&S)//遞歸遍歷左子樹Pop(S,e);T=T－>nextsibiling;//遍歷右子樹}//while}//Outpath9．設(shè)計算法實現(xiàn)以逆鄰接表為存儲結(jié)構(gòu)的有向圖的拓撲排序（要求給出逆鄰接表的存儲結(jié)構(gòu)定義）。(1)存儲結(jié)構(gòu)定義vexdatafirstin頂點結(jié)構(gòu)adjvexinfofirstarc表結(jié)點結(jié)構(gòu)(2)算法設(shè)計inttoposort(ALGraphG,inttpv[]){//以逆鄰接表為存儲結(jié)構(gòu)的有向圖的拓撲排序top=0;for(i=0;i<G.vexnum;i++)for(p=G.adjlist[i].firstedge;p;p→next)findoutdegree(G,outdegree);//對各頂點求出度outdegree[p→adjvex]++;InitStack(&S);//初始化棧for(i=0;i<G.Vexnum;i++)if(outdegree[i]==0)Push(&S,i);//出度為零的頂點入棧while(!Stack(S)){Pop(&S,i);printf(G.adjlist[i].vextex);tpv[top++]=i;for(p=G.adjlist[i].firstedge;p;p→next){j=p→adjvex;outdegree[j]--;if(!outdegree[j])Push(&S,j);//出度為零的頂點入棧}//for}//whileif(top<G.vexnum)return0;//無環(huán)else{//輸出頂點拓撲排序序列for(i=0;j=top-1;i<G.vexnum/2;i++,j--){//置逆輸出temp=tpv[i];tpv[i]=tpv[j];tpv[j]=temp;}//forreturn1;}//else}//toposort10．已知深度為h的二叉樹采用順序存儲結(jié)構(gòu)存放在數(shù)組B[1..2h-1]中，設(shè)計一個遞歸算法，產(chǎn)生該二叉樹的二叉鏈表結(jié)構(gòu)。voidCreateTree(intB[2h],intj,BiTreet){//創(chuàng)建t樹的二叉鏈表結(jié)構(gòu)，j為數(shù)組下標，初值為1t=(BiTree)malloc(sizeof(BiTNode));t－>data=B[j];//創(chuàng)建根結(jié)點if(2*j>2h)t－>Lchild=null;//無左子樹else//遞歸創(chuàng)建左子樹t－>Lchild=CreateTree(B,2*j,t－>Lchild)；if(2*j+1>2h)t－>Rchild=null;//無右子樹else//遞歸創(chuàng)建右子樹t－>Rchild=CreateTree(B,2*j+1,t－>Rchild)；}//CreateTree11．假設(shè)哈希函數(shù)為H（key）,編寫用鏈地址法解決沖突的哈希表的插入和刪除算法。voidF2(HashTable&H,keytypeKey){//哈希表插入，用鏈地址法解決沖突i=H(Key);;//獲取哈希地址if(H[i]==Null){s=(Linklist)malloc(sizeof(Lnode));s