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

1、【精品文檔】如有侵權(quán)，請聯(lián)系網(wǎng)站刪除，僅供學(xué)習(xí)與交流數(shù)據(jù)結(jié)構(gòu)期末復(fù)習(xí)題.精品文檔.練習(xí)題：一、 填空題1、元素項是數(shù)據(jù)的最小單位，數(shù)據(jù)元素是討論數(shù)據(jù)結(jié)構(gòu)時涉及的最小數(shù)據(jù)單位。2、設(shè)一棵完全二叉樹具有100個結(jié)點，則此完全二叉樹有49個度為2的結(jié)點。3、在用于表示有向圖的鄰接矩陣中，對第i列的元素進(jìn)行累加，可得到第i個頂點的出度。4、已知一棵度為3的樹有2個度為1的結(jié)點，3個度為2的結(jié)點，4個度為3的結(jié)點，則該樹中有12個葉子的結(jié)點。n=n0+n1+n2+nm (1)又有除根結(jié)點外,樹中其他結(jié)點都有雙親結(jié)點,且是唯一的(由樹中的分支表示),所以,有雙親的結(jié)點數(shù)為：n-1=0*n0+1*n1+2*

2、n2+m*nm (2)聯(lián)立(1)(2)方程組可得：葉子數(shù)為：n0=1+0*n1+1*n2+2*n3+.+(m-1)*nm5、有一個長度為20的有序表采用二分查找方法進(jìn)行查找，共有4個元素的查找長度為3。6、對于雙向鏈表，在兩個結(jié)點之間插入一個新結(jié)點需要修改的指針共4個。 刪除一個結(jié)點需要修改的指針共2個。7、已知廣義表LS=(a,(b,c,d),e)，它的深度是2，長度是3。8、循環(huán)隊列的引入是為了克服假溢出。9、表達(dá)式a*(b+c)-d/f的后綴表達(dá)式是abc+*df/-。10、數(shù)據(jù)結(jié)構(gòu)中評價算法的兩個重要指標(biāo)是時間復(fù)雜度和空間復(fù)雜度。11、設(shè)r指向單鏈表的最后一個結(jié)點，要在最后一個結(jié)點之后

3、插入s所指的結(jié)點，需執(zhí)行的三條語句是r->next=s; r=s; r->next=null;12、設(shè)有一個空棧，棧頂指針為1000H(十六進(jìn)制)，現(xiàn)有輸入序列為1，2，3，4，5，經(jīng)過PUSH,PUSH,POP,PUSH,POP,PUSH,PUSH之后，輸出序列是23，而棧頂指針值是1012_H。設(shè)棧為順序棧，每個元素占4個字節(jié)。13、模式串P=abaabcac的next函數(shù)值序列為01122312。14、任意連通圖的連通分量只有一個，即是自身。15、棧的特性是先進(jìn)后出。16、串的長度是包含的元素個數(shù)。17、如果一個有向圖中沒有回路，則該圖的全部頂點可能排成一個拓?fù)湫蛄小?8、在

4、具有n個葉子結(jié)點的哈夫曼樹中，分支結(jié)點總數(shù)為n-1。17619、在線性表的散列存儲中，裝填因子a又稱為裝填系數(shù)，若用m表示散列表的長度，n表示待散列存儲的元素的個數(shù)，則a等于n/m。20、排序的主要目的是為了以后對已排序的數(shù)據(jù)元素進(jìn)行 查找。21、對于一個具有n個結(jié)點的單鏈表，在已知的結(jié)點*p后插入一個新結(jié)點的時間復(fù)雜度為O(1),在給定值為x的結(jié)點后插入一個新結(jié)點的時間復(fù)雜度為O(n)。22、線性表L=（a1,a2,an）用數(shù)組表示，假定刪除表中任一元素的概率相同，則刪除一個元素平均需要移動元素的個數(shù)是 n/2。23、兩個棧共享空間時棧滿的條件top1=top2-1。24、深度為H 的完全二

5、叉樹至少有H個結(jié)點；至多有2H-1個結(jié)點；H和結(jié)點總數(shù)N之間的關(guān)系是 H=log2n+1 。15025、在有序表A120中，按二分查找方法進(jìn)行查找，查找長度為4的元素的下標(biāo)從小到大依次是1 3 6 8 11 13 16 1926、設(shè)查找表中有100個元素，如果用二分法查找方法查找數(shù)據(jù)元素X，則最多需要比較7次就可以斷定數(shù)據(jù)元素X是否在查找表中。26、數(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)），鏈表是（鏈?zhǔn)酱鎯Y(jié)構(gòu)）

6、。27、根據(jù)初始關(guān)鍵字序列(17，25，3，39，12)建立的二叉排序樹的高度為3。27、算法的五個重要特性有哪些。（有窮性、確定性、可行性、輸入、輸出）。抽象數(shù)據(jù)類型是指一個（數(shù)學(xué)模型）以及定義在該模型上的（一組操作）。28、設(shè)有一個n階的下三角矩陣A，如果按照行的順序?qū)⑾氯蔷仃囍械脑兀ò▽巧显兀┐娣旁趎(n+1)個連續(xù)的存儲單元中，則Aij與A00之間有(i)個數(shù)據(jù)元素。29、 棧的插入和刪除只能在棧的棧頂進(jìn)行，后進(jìn)棧的元素必定先出棧，所以又把棧稱為FILO；隊列的插入和刪除運算分別在隊列的兩端進(jìn)行，先進(jìn)隊列的元素必定先出隊列，所以又把隊列稱為FIFO表。30、 設(shè)一棵完全二叉樹

7、的順序存儲結(jié)構(gòu)中存儲數(shù)據(jù)元素為ABCDEF，則該二叉樹的前序遍歷序列為ABDEF，中序遍歷序列為DBEAFC，后序遍歷序列為DEBFCA。31、 如果以鏈棧為存儲結(jié)構(gòu)，則出棧操作時(必須判別棧是否空)，與順序棧相比，鏈棧有一個明顯的優(yōu)勢是(通常不會出現(xiàn)棧滿的情況)。32、 循環(huán)隊列采用數(shù)組data1n來存儲元素的值，并用front和rear分別作為其頭尾指針。為區(qū)分隊列的滿和空，約定：隊中能夠存放的元素個數(shù)最大為n-l，也即至少有一個元素空間不用，則在任意時刻，至少可以知道一個空的元素的下標(biāo)是（front） ；入隊時，可用語句（rear=rear+1%n）求出新元素在數(shù)組data中的下標(biāo)。33

8、、 設(shè)一棵完全二叉樹有128個結(jié)點，則該完全二叉樹的深度為8，有65個葉子結(jié)點。33、已知棧的輸入序列為1，2，3，n，輸出序列為a1，a2，an，a2=n的輸出序列共有（n-1）種輸出序列。34、 設(shè)有向圖G的存儲結(jié)構(gòu)用鄰接矩陣A來表示，則A中第i行中所有非零元素個數(shù)之和等于頂點i的出度，第i列中所有非零元素個數(shù)之和等于頂點i的入度。35、將下三角矩陣Al.8，1.8的下三角部分逐行地存儲到起始地址為1000的內(nèi)存單元中，已知每個元素占4個單元，則A7，5的地址為 （1100）。36、已知數(shù)組A1.10，1.10為對稱矩陣，其中每個元素占5個單元。現(xiàn)將其下三角部分按行優(yōu)先次序存儲在起始地址為

9、1000的連續(xù)的內(nèi)存單元中，則元素A5，6對應(yīng)的地址為（1095）。37、兩個串相等的充要條件是，兩個串的(長度)相等，且其所對應(yīng)各個位置的（字符）也相等。39、在有n個結(jié)點的二叉鏈表中，值為非空的鏈域的個數(shù)為（n-1）。在有n個葉子結(jié)點的哈夫曼樹中，總結(jié)點數(shù)是（2n-1）。在樹形結(jié)構(gòu)中，根結(jié)點數(shù)只有（1），其余每個結(jié)點有且僅有一個（前驅(qū)）元素結(jié)點。40、一棵二叉樹L的高度為h，所有結(jié)點的度或為0，或為2，則這棵二叉樹最少的結(jié)點數(shù)為(2h-1)。已知二叉樹有50個葉子結(jié)點，則該二叉樹的總結(jié)點數(shù)至少是（99）。將一棵有100個結(jié)點的完全二叉樹從根這一層開始，每一層上從左到右依次對結(jié)點進(jìn)行編號，根

10、結(jié)點的編號為1，則編號為49的結(jié)點的左孩子編號為（98）。有64個結(jié)點的完全二叉樹的深度為( 7)。41、拓?fù)渑判蛑荒苡糜冢ㄓ邢驘o環(huán)圖）。連通圖是指圖中任意兩個頂點之間（都連通的無向圖）。一個有n個頂點的無向連通圖，它所包含的連通分量個數(shù)最多為(1)個。任何一個無向連通圖的最小生成樹（有一棵或多棵）。若含有n個頂點的圖形成一個環(huán)，則它有（n）棵生成樹。42、求圖的最小生成樹有兩種算法，（普利姆）算法適合于求稠密圖的最小生成樹，（克魯斯卡爾）算法適合于求稀疏圖的最小生成樹。設(shè)圖G用鄰接表存儲，則拓?fù)渑判虻臅r間復(fù)雜度為(O(n+e)。44、從未排序序列中依次取出元素與已排序序列(初始時為空)中的元

11、素進(jìn)行比較，將其放入已排序序列的正確位置上的方法，稱為(插入排序)。對于關(guān)鍵字序列(12，13，11，18，60，15，7，18，25，100)，用篩選法建堆，則開始結(jié)點的鍵值必須為（60）。33、typedef struct nodeint key; struct node *lchild; struct node *rchild;bitree;bitree *bstsearch(bitree *t, int k)if (t=0 ) return(0);else while (t!=0)if (t->key=k)t->lchild=t->rchild=0; else if

12、(t->key>k) t=t->lchild; elset=t->lchild;34、 下面程序段的功能是實現(xiàn)冒泡排序算法，請在下劃線處填上正確的語句。void bubble(int rn)272for(i=1;i<=n-1; i+)for(exchange=0,j=0; j<n-i;j+) if (rj>rj+1)temp=rj+1;_ rj=rj+1_;rj=temp;exchange=1;if (exchange=0) return；35、 下面程序段的功能是實現(xiàn)二分查找算法，請在下劃線處填上正確的語句。struct recordint key;

13、 int others;int bisearch(struct record r , int k) int low=0,mid,high=n-1; while(low<=high) mid=(low+high)/2; if(rmid.key=k) return(mid+1); else if(rmid.key<k) high=mid-1;else low=mid+1; return(0);36、設(shè)二叉樹中度數(shù)為0的結(jié)點數(shù)為50，度數(shù)為1的結(jié)點數(shù)為30，則該二叉樹中總共有129個結(jié)點數(shù)。15137、設(shè)有向圖G的二元組形式表示為G =（D，R），D=1，2，3，4，5，R=r，r=&l

14、t;1,2>，<2,4>，<4,5>，<1,3>，<3,2>，<3,5>，則給出該圖的一種拓?fù)渑判蛐蛄?3245。38、設(shè)一組初始記錄關(guān)鍵字序列為(49，38，65，97，76，13，27，50)，則以d=4為增量的一趟希爾排序結(jié)束后的結(jié)果為49 13 27 50 76 38 65 97。39、設(shè)二叉排序樹的高度為h，則在該樹中查找關(guān)鍵字key最多需要比較h次.二、選擇題1、從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分為（ C ）兩大類。A動態(tài)結(jié)構(gòu)、靜態(tài)結(jié)構(gòu) B順序結(jié)構(gòu)、鏈?zhǔn)浇Y(jié)構(gòu) C線性結(jié)構(gòu)、非線性結(jié)構(gòu) D初等結(jié)構(gòu)、構(gòu)造型結(jié)構(gòu)2、若長度為n的線性表

15、采用順序存儲結(jié)構(gòu)，在其第i個位置插入一個新元素的算法的時間復(fù)雜度為（ C ）(1<=i<=n+1)。A. O(0) B. O(1) C. O(n) D. O(n2)3、若已知一個棧的入棧序列是1,2,3,n，其輸出序列為p1,p2,p3，pN,若pN是n，則pi是( A )。 A. i B. n-i C. n-i+1 D. 不確定4、已知廣義表L=（x,y,z），a，（u，t，w），從L表中取出原子項t的運算是（D）。A. head（tail（tail（L） B. tail（head（head（tail（L） C. head（tail（head（tail（L）D. head（tai

16、l(head（tail（tail（L）)）5、下列陳述中正確的是（ D ）。A.二叉樹是度為2的有序樹 B.二叉樹中結(jié)點只有一個孩子時無左右之分C.二叉樹中必有度為2的結(jié)點 D.二叉樹中最多只有兩棵子樹，并且有左右之分6、設(shè)森林F對應(yīng)的二叉樹為B，它有m個結(jié)點，B的根為p,p的右子樹結(jié)點個數(shù)為n,森林F 中第一棵樹的結(jié)點個數(shù)是（ A ）。173Am-n Bm-n-1 Cn+1 D條件不足，無法確定7、算術(shù)表達(dá)式a+b*（c+d/e）轉(zhuǎn)為后綴表達(dá)式后為（ B ）。Aab+cde/* Babcde/+*+ Cabcde/*+ Dabcde*/+8、關(guān)鍵路徑是事件結(jié)點網(wǎng)絡(luò)中（A）。A從源點到終點的最

17、長路徑 B從源點到終點的最短路徑C最長回路 D最短回路9、具有12個關(guān)鍵字的有序表，二分查找的平均查找長度（C）。236 A. 2.5 B. 4 C. 3.1 D. 510、AVL樹是一種平衡的二叉排序樹，樹中任一結(jié)點的（ B ）245A.左、右子樹的高度均相同 B.左、右子樹高度差的絕對值不超過1C.左子樹的高度均大于右子樹的高度 D.左子樹的高度均小于右子樹的高度11、線性表采用鏈接存儲時，其地址（D ）。A.必須是連續(xù)的 B.部分地址必須是連續(xù)的C.一定是不連續(xù)的 D.連續(xù)與否均可以12、棧和隊列是兩種特殊的線性表，只能在它們的（B）處添加或刪除結(jié)點。  中間點  

18、端點   隨機存取點   結(jié)點13、輸入序列為ABC，可以變?yōu)锽AC時，經(jīng)過的棧操作為（ C ）。A. push,pop,push,pop,push,pop B. push,push,push,pop,pop,pop C. push,push,pop,pop,push,pop D. push,pop,push,push,pop,pop14、下面（ C ）不是算法所具有的特性。 有窮性 確切性 高效性   可行性15、下面關(guān)于串的的敘述中，（B）是不正確的？A串是字符的有限序列 B空串是由空格構(gòu)成的串C模式匹配是串的一種重要運算 D串既可以采用順序存儲，也可以采用鏈

19、式存儲16、數(shù)組A67的每個元素占五個字節(jié)，將其按行優(yōu)先次序存儲在起始地址為1000的內(nèi)存單元中，則元素A35的地址是( A )。117 A. 1130 B. 1180 C. 1205 D. 121017、對于一個具有n個頂點的無向圖，若采用鄰接矩陣存儲，則該矩陣的大小是（ D ）。195An B(n-1)2 Cn-1 Dn218、若廣義表A滿足Head(A)=Tail(A)，則A為（ B ）。A（ ） B（） C（），（） D（），（），（）19、堆的形狀是一棵 (C )。 A.二叉排序樹 B.滿二叉樹 C.完全二叉樹 D.判定樹20、若要在單鏈表中的結(jié)點 *p 之后插入一個結(jié)點 *s ，則

20、應(yīng)執(zhí)行的語句是 (A ) As->next=p->next； p->next=s； Bp->next=s； s->next=p->next；Cp->next=s->next； s->next=p； Ds->next=p； p->next=s->next；21、鏈表不具有的特點是（ ）。A插入、刪除不需要移動元素 B可隨機訪問任一元素 C不必事先估計存儲空間 D所需空間與線性長度成正比22、一個棧的輸入序列為1 2 3 4 5，則下列序列中不可能是棧的輸出序列的是（ B ）。 A. 2 3 4 1 5 B. 5 4 1 3

21、2 C. 2 3 1 4 5 D. 1 5 4 3 223、遞歸過程或函數(shù)調(diào)用時，處理參數(shù)及返回地址，要用一種稱為（ ）的數(shù)據(jù)結(jié)構(gòu)。A隊列 B多維數(shù)組 C棧 D. 線性表24、設(shè)給定權(quán)值總數(shù)有n 個，其哈夫曼樹的結(jié)點總數(shù)為( ) 。A不確定 B2n C2n+1 D2n-125、若需在O(nlog2n)的時間內(nèi)完成對數(shù)組的排序，且要求排序是穩(wěn)定的，則可選擇的排序方法是（ ）。課件 A. 快速排序 B. 堆排序 C. 歸并排序 D. 直接插入排序26、設(shè)有一個二維數(shù)組Amn，假設(shè)A00存放位置在644(10)，A22存放位置在676(10)，每個元素占一個空間，問A33(10)存放在什么位置？腳注

22、(10)表示用10進(jìn)制表示。() A688 B678 C692 D69627、若有18個元素的有序表存放在一維數(shù)組A19中，第一個元素放A1中，現(xiàn)進(jìn)行二分查找，則查找A3的比較序列的下標(biāo)依次為( D )A. 1，2，3B. 9，5，2，3 C. 9，5，3D. 9，4，2，328、設(shè)一組初始記錄關(guān)鍵字序列(5，2，6，3，8)，以第一個記錄關(guān)鍵字5為基準(zhǔn)進(jìn)行一趟快速排序的結(jié)果為（C ）。(A) 2，3，5，8，6(B) 3，2，5，8，6(C) 3，2，5，6，8(D) 2，3，6，5，829、設(shè)指針變量p指向單鏈表中結(jié)點A，若刪除單鏈表中結(jié)點A，則需要修改指針的操作序列為（A ）。A q=p

23、->next；p->data=q->data；p->next=q->next；free(q)；B q=p->next；q->data=p->data；p->next=q->next；free(q)；C q=p->next；p->next=q->next；free(q)；D q=p->next；p->data=q->data；free(q)；30、設(shè)某二叉樹中度數(shù)為0的結(jié)點數(shù)為N0，度數(shù)為1的結(jié)點數(shù)為Nl，度數(shù)為2的結(jié)點數(shù)為N2，則下列等式成立的是（C ）。A N0=N1+1B. N0=Nl+N2C.

24、 N0=N2+1D. N0=2N1+l31、設(shè)一棵m叉樹中度數(shù)為0的結(jié)點數(shù)為N0，度數(shù)為1的結(jié)點數(shù)為Nl，度數(shù)為m的結(jié)點數(shù)為Nm，則N0=（B）。A. Nl+N2+NmB. l+N2+2N3+3N4+(m-1)NmC. N2+2N3+3N4+(m-1)Nm D. 2Nl+3N2+(m+1)Nm32、設(shè)無向圖G中的邊的集合E=(a，b)，(a，e)，(a，c)，(b，e)，(e，d)，(d，f)，(f，c)，則從頂點a出發(fā)進(jìn)行深度優(yōu)先遍歷可以得到的一種頂點序列為（ A ）。A. aedfcb B. acfebd C. aebcfd D. aedfbc26、某二叉樹的先序序列和后序序列正好相反，則

25、該二叉樹的特點一定是（ BB ）。A. 空或只有一個結(jié)點 B.高度等于其結(jié)點數(shù) C. 任一結(jié)點無左孩子 D.任一結(jié)點無右孩子28、下面的說法中正確的是（ B ）。 (1)任何一棵二叉樹的葉子節(jié)點在三種遍歷中的相對次序不變。 (2)按二叉樹定義，具有三個節(jié)點的二叉樹共有6種。A(1)，(2) B(1) C(2) D(1)，(2)都錯29、樹有先根遍歷和后根遍歷，樹可以轉(zhuǎn)化為對應(yīng)的二叉樹。下面的說法正確的是（ B ）。 A樹的后根遍歷與其對應(yīng)的二叉樹的后根遍歷相同 B樹的后根遍歷與其對應(yīng)的二叉樹的中根遍歷相同C樹的先根遍歷與其對應(yīng)的二叉樹的中根遍歷相同 D以上都不對30、.下圖的鄰接表中，從頂點V

26、1 出發(fā)采用深度優(yōu)先搜索法遍歷該圖，則可能的頂點序列是 （ D ）。A. V1V2V3V4V5 B. V1V2V3V5V4 C. V1V4V3V5V2 D.V1V3V4V5V2 31、以下說法不正確的是（ D ）。 A無向圖中的極大連通子圖稱為連通分量 B連通圖的廣度優(yōu)先搜索中一般要采用隊列來暫存剛訪問過的頂點 C圖的深度優(yōu)先搜索中一般要采用棧來暫存剛訪問過的頂點 D有向圖的遍歷不可采用廣度優(yōu)先搜索32、設(shè)哈希表長為14，哈希函數(shù)H(key)=key11，表中已有數(shù)據(jù)的關(guān)鍵字為15，38，61，84，四個，現(xiàn)將關(guān)鍵字為49的結(jié)點加到表中，用二次探測再散列法解決沖突，則放入的位置是（ DD ）。

27、 A8 B3 C5 D934、二維數(shù)組A的每個元素是由6個字符組成的串，其行下標(biāo)i=0，l，8，列下標(biāo)為j=1，210。設(shè)每個字符占一個字節(jié),若按行先存儲，元素A8，5的起始地址與A按列存儲時起始地址相同的元素是（ B ）。 AA8，5 BA3，10 CA5，8 DA0，935、.在n個結(jié)點且為完全二叉樹的二叉排序樹中查找一個鍵值，其平均比較次數(shù)的數(shù)量級為（ B ）。 A. O(n) B. O(log2n) C. O(nlog2n) D. O(n2)37、關(guān)鍵路徑是事件結(jié)點網(wǎng)絡(luò)中（ AA ）。 A從源點到匯點的最長路徑 B從源點到匯點的最短路徑 C最長的回路 D最短的回路38、將兩個各有n個元

28、素的有序表歸并成一個有序表，其最少的比較次數(shù)是（ AA ）。 An B2n-1 C2n Dn-141、有向圖G用鄰接矩陣A存儲，則頂點i的入度等于A中（ BB ）。A. 第i行1的元素之和 B. 第i列1的元素之和C. 第i行0的元素個數(shù) D. 第i列0的元素個數(shù)42、用某種排序方法對關(guān)鍵字序列（25，84，21，47，15，27，68，35，20）進(jìn)行排序時，序列的變化情況如下： 20，15，21，25，47，27，68，35，84 15，20，21，25，35，27，47，68，84 15，20，21，25，27，35，47，68，84 則所采用的排序方法是（DD ）A選擇排序 B希爾排序

29、 C歸并排序 D快速排序43、設(shè)一組初始關(guān)鍵字記錄關(guān)鍵字為(20，15，14，18，21，36，40，10)，則以20為基準(zhǔn)記錄的一趟快速排序結(jié)束后的結(jié)果為(AA )。(A) 10，15，14，18，20，36，40，21(B) 10，15，14，18，20，40，36，21(C) 10，15，14，20，18，40，36，2l(D) 15，10，14，18，20，36，40，2144、設(shè)有n個關(guān)鍵字具有相同的Hash函數(shù)值，則用線性探測法把這n個關(guān)鍵字映射到HASH表中需要做（ D）次線性探測。A. n2 B. n(n+1)C. n(n+1)/2D. n(n-1)/2三、判斷題1如果兩個串含

30、有相同的字符，則這兩個串相等。（x ）2數(shù)組可以看成線性結(jié)構(gòu)的一種推廣，因此可以對它進(jìn)行插入、刪除等運算。（ x）3二叉樹是度為2的樹。（x ）4在順序表中取出第i個元素所花費的時間與i成正比。（x ）5在棧滿情況下不能作進(jìn)棧運算，否則產(chǎn)生“上溢”。( v ）6圖G的生成樹是該圖的一個極小連通子圖。（v ）7所謂數(shù)據(jù)的邏輯結(jié)構(gòu)指的是數(shù)據(jù)之間的邏輯關(guān)系。（ x ）數(shù)據(jù)項8二叉排序樹的查找和折半查找的時間性能相同。（x）9在執(zhí)行某個排序算法過程中，出現(xiàn)了排序碼朝著最終排序序列位置相反方向移動，則該算法是不穩(wěn)定的。（x ）10一個有向圖的鄰接表和逆鄰接表中表結(jié)點的個數(shù)一定相等。（ v）11、雙向鏈表

31、中至多只有一個結(jié)點的后繼指針為空。（ v ）12、在循環(huán)隊列中，front指向隊列中第一個元素的前一位置，rear指向?qū)嶋H的隊尾元素，隊列為滿的條件是front=rear。（ x ）13、對鏈表進(jìn)行插入和刪除操作時，不必移動結(jié)點。（ v ）14、棧可以作為實現(xiàn)程序設(shè)計語言過程調(diào)用時的一種數(shù)據(jù)結(jié)構(gòu)。（ v ）15、在一個有向圖的拓樸序列中，若頂點a在頂點b之前，則圖中必有一條弧<a,b> ( x ) 。16、對有向圖G，如果從任一頂點出發(fā)進(jìn)行一次深度優(yōu)先或廣度優(yōu)先搜索就能訪問每個頂點，則該圖一定是完全圖。( x )17、“順序查找法”是指在順序表上進(jìn)行查找的方法。（ x ）18、向二

32、叉排序樹插入一個新結(jié)點時，新結(jié)點一定成為二叉排序樹的一個葉子結(jié)點。（ v ）19、二分查找要求序列順序存儲且關(guān)鍵字序列有序。（v）20、二路歸并時，被歸并的兩個子序列中的關(guān)鍵字個數(shù)一定要相等。（x）21.調(diào)用一次深度優(yōu)先遍歷可以訪問到圖中的所有頂點。（ x ）21分塊查找的平均查找長度不僅與索引表的長度有關(guān)，而且與塊的長度有關(guān)。（v ）22冒泡排序在初始關(guān)鍵字序列為逆序的情況下執(zhí)行的交換次數(shù)最多。（ v ）23滿二叉樹一定是完全二叉樹，完全二叉樹不一定是滿二叉樹。（ v ）24設(shè)一棵二叉樹的先序序列和后序序列，則能夠唯一確定出該二叉樹的形狀。（ x ）25層次遍歷初始堆可以得到一個有序的序列。

33、（ x ）26設(shè)一棵樹T可以轉(zhuǎn)化成二叉樹BT，則二叉樹BT中一定沒有右子樹。（ v ）27線性表的順序存儲結(jié)構(gòu)比鏈?zhǔn)酱鎯Y(jié)構(gòu)更好。（ x ）28中序遍歷二叉排序樹可以得到一個有序的序列。（ v ）29.快速排序是排序算法中平均性能最好的一種排序。（v ）30不論是入隊列操作還是入棧操作，在順序存儲結(jié)構(gòu)上都需要考慮“溢出”情況。（ v ）31當(dāng)向二叉排序樹中插入一個結(jié)點，則該結(jié)點一定成為葉子結(jié)點。（ v ）32設(shè)某堆中有n個結(jié)點，則在該堆中插入一個新結(jié)點的時間復(fù)雜度為O(log2n)。（v ）33完全二叉樹中的葉子結(jié)點只可能在最后兩層中出現(xiàn)。（ v ）34哈夫曼樹中沒有度數(shù)為1的結(jié)點。（ v ）

34、35對連通圖進(jìn)行深度優(yōu)先遍歷可以訪問到該圖中的所有頂點。（ v ）36先序遍歷一棵二叉排序樹得到的結(jié)點序列不一定是有序的序列。（v ）37由樹轉(zhuǎn)化成二叉樹，該二叉樹的右子樹不一定為空。（x）38線性表中的所有元素都有一個前驅(qū)元素和后繼元素。（ x ）39.帶權(quán)無向圖的最小生成樹是唯一的。（ x ）四、應(yīng)用題1、已知一棵二叉樹的中根序列和后根序列分別為CBEDAFIGH及CEDBIFHGA，請畫出這棵二叉樹，并給出其先序序列。ABCDEGFIH1、已知一棵二叉樹的先根序列和中根序列分別為ABDGHECFIJ及GDHBEACIJF，請畫出這棵二叉樹，并給出其后序序列。GHDEBJIFCA2、將下列

35、由三棵樹組成的森林轉(zhuǎn)換為二叉樹。（只要求給出轉(zhuǎn)換結(jié)果）3、已知無向圖如下所示：（1）給出從V1開始的廣度優(yōu)先搜索序列；（2）畫出它的鄰接表；（3）畫出從V1開始深度優(yōu)先搜索生成樹。4.假定用于通訊的電文僅有8個字母C1，C2，C8組成，各個字母在電文中出現(xiàn)的頻率分別為5，15，3，6，22，11，30，8，請先構(gòu)建一棵哈夫曼樹，計算其WPL值，并為這8個字母設(shè)計相應(yīng)的哈夫曼編碼4、假定用于通訊的電文僅有8個字母C1，C2，C8組成，各個字母在電文中出現(xiàn)的頻率分別為5，25，3，6，10，11，36，4，請先構(gòu)建一棵哈夫曼樹，計算其WPL值，并為這8個字母設(shè)計相應(yīng)的哈夫曼編碼。5、已知一表為（J

36、an,Feb,Mar,Apr,May,Jun,Jul,Aug,Sep,Oct,Nov,Dec）,按表中順序依次插入初始為空的二叉排序樹，要求：(1)畫出建立的二叉排序樹（值的大小以字母順序為準(zhǔn)）。(2)對該二叉排序樹作中序遍歷，試寫出遍歷序列。(3)求出在等概率情況下查找成功的平均查找長度。6、已知一個圖的頂點集V和邊集G分別為： V=0,1,2,3,4,5,6,7;E=(0,1)8,(0,2)5,(0,3)2,(1,5)6,(2,3)25,(2,4)13,(3,5)9,(3,6)10, (4,6)4,(5,7)20; 按照普里姆算法從頂點0出發(fā)得到最小生成樹，試寫出在最小生成樹中依次得到的各

37、條邊。(0,1),(0,3),(0,2),(1,5),(3,6),(6,4),(5,7)。7、設(shè)一哈希表長為13，采用線性探測法解決沖突，哈希函數(shù)H(key)=key%13,（1）畫出在空表中依次插入關(guān)鍵字25，20，34，15，21，32，29，82，57后的哈希表。（2）求在等概率情況下，查找成功和查找不成功的平均查找長度。7、已知散列函數(shù)為H(K)=K mod 11,健值序列為47，7，29，11，16，92，22，8，3哈希表長為11，采用線性探測法處理沖突，試構(gòu)造閉散列表，并計算查找成功和不成功的平均查找長度。8、已知待排序的序列為（403，187，312，61，818，170，85

38、7，272，633，442），試完成下列各題。(1) 根據(jù)以上序列建立一個堆（畫出第一步和最后堆的結(jié)果圖），希望先輸出最小值。(2) 輸出最小值后，如何得到次小值。（并畫出相應(yīng)結(jié)果圖）。8、已知待排序的序列為（503，87，512，61，908，170，897，275，653，462），試完成下列各題。(1) 根據(jù)以上序列建立一個堆（畫出第一步和最后堆的結(jié)果圖），希望先輸出最小值。(2) 輸出最小值后，如何得到次小值。（并畫出相應(yīng)結(jié)果圖）。9、下圖表示一個地區(qū)的交通網(wǎng)，頂點表示城市，邊表示連結(jié)城市間的公路，邊上的權(quán)表示修建公路花費的代價。怎樣選擇能夠溝通每個城市且總造價最省的n-1條公路，畫出

39、一個方案。v2v4v1v5v3v61621111433619186510、已知圖G=（V, E），其中V=v1,v2,v3,v4,v5, E=<v1,v2>, <v1,v4>, <v2,v3>, <v2,v5>, <v4,v5>), <v5,v3>；畫出這個圖的圖形并寫出所有的拓?fù)湫蛄小?1、設(shè)有關(guān)鍵碼序列19，32，40，13，30，24，35，請給出平衡二叉樹的構(gòu)造過程（只需要給出不平衡時到平衡的過程即可）。11、設(shè)有關(guān)鍵碼序列20，35，40，15，30，25，38，請給出平衡二叉樹的構(gòu)造過程（只需要給出不平衡時到平

40、衡的過程即可）。 12、已知散列函數(shù)為H(K)=K mod 13,健值序列為12，31，15，54，04，78，22，29，34，54，29，47，采用拉鏈法處理沖突，試構(gòu)造開散列表，并計算查找成功的平均查找長度。12、已知散列函數(shù)為H(K)=K mod 13,健值序列為13，41，15，44，06，68，12，25，38，64，19，49，采用拉鏈法處理沖突，試構(gòu)造開散列表，并計算查找成功的平均查找長度。13、對于下列一組關(guān)鍵字36，48，25，55，80，17，11，72，試寫出快速排序每一趟的排序結(jié)果。13、對于下列一組關(guān)鍵字46，58，15，45，90，18，10，62，試寫出快速排序

41、每一趟的排序結(jié)果。10,15,18,45,46,58,62,9014、對下面的關(guān)鍵字集（30，14，25，43，35，27，64，49），若查找表的裝填因子為0.8，采用線性探測再散列解決沖突：（1）設(shè)計哈希函數(shù)；（2）畫出哈希表；（3）求查找成功的平均查找長度。14、在如下數(shù)組A中鏈接存儲了一個線性表，表頭指針為A 0.next，試寫出該線性表。 A 0 1 2 3 4 5 6 7 data605078903440next3572041線性表為：（78，50，40，60，34，90）15、按順序輸入下列頂點對: (V1, V2)、(V1, V6)、(V2, V6)、(V1, V4)、(V6,

42、 V4)、(V1, V3)、(V3, V4)、(V6, V5)、(V4, V5)、(V1, V5)、(V3, V5)。（頂點序列為：V1，V2，V3，V4，V5，V6）（1）畫出相應(yīng)的鄰接表。（2）寫出在鄰接表上，從頂點3開始（表下標(biāo)從0開始）的DFS序列和DFS生成樹五、算法與程序設(shè)計1、閱讀算法完成題目要求：（1）說出下列算法的功能。 template <class T>struct Binnode T data; Binnode<T> *prior, *next; ;bool Unknown (Binnode<T> *first) Binnode<

43、;T> *p,*q; p=first->next; q=first->prior; while(p!=q && p->prior!=q) if(p->data=q->data) p=p->next; q=q->prior; else return 0;return 1;/判斷雙鏈表的對稱性算法功能： （2）根據(jù)下列算法和輸入的數(shù)據(jù)畫出生成的鏈表形式。template <class T> LinkList<T>: LinkList( int n) first=new Node<T> Node<

44、;T> *s; T x; first->next=NULL; for (int i=0; i<n; i+) cin>>x;s=new Node<T> s->data=x; s->next=first->next; first->next=s; 輸入數(shù)據(jù)為：1 2 3 4 5 6 輸出結(jié)果為：（3）說出下列算法的功能，它是采用什么結(jié)構(gòu)實現(xiàn)的。 template <class T>void BiTree<T>:Unknown (BiNode<T> *root) const int MaxSize

45、= 100; int front = 0; int rear = 0; BiNode<T>* QMaxSize; BiNode<T>* q;if (root=NULL) return;elseQrear+ = root;while (front != rear)q = Qfront+; cout<<q->data<<" " if (q->lchild != NULL) Qrear+ = q->lchild;if (q->rchild != NULL) Qrear+ = q->rchild;算法功能

46、：二叉樹的層序遍歷 對列 （4）閱讀下列算法求出調(diào)用該算法后輸出結(jié)果。void AE(Stack& S) InitStack(S); Push(S,30); Push(S,40); Push(S,50); int x=Pop(S)+2*Pop(S); Push(S,x); int i,a4=5,8,12,15; for(i=0;i<4;i+) Push(S,ai); while(!StackEmpty(S) cout<<Pop(S)<<' '輸出結(jié)果為：（5）設(shè)有一個正整數(shù)序列組成的非遞減有序單鏈表，閱讀下面的算法，指出該算法的功能，并在“

47、/后面加上必要的注釋。void F1(Linklist L;int,x) p= Lnext; q=p; /p為工作指針pre=L; Lnext=NULL; ./q指最小元素while(P&&Pdata<x)/ （1）比x小的數(shù)遞減r=pnext; pnext=Lnext;Lnext=p; p=r; /（2）置逆/whileqnext=p; pre=q; /（3）重新鏈接/F1算法功能：在單鏈表中將比正整數(shù)X小的數(shù)按遞減次序排序（6）設(shè)有一個由正整數(shù)組成的無序單鏈表，閱讀下面的算法，指出該算法的功能。void F1(Linklist &L) p=Lnext; pre

48、=p; /pre為最小結(jié)點指針while(p) if(pdata<predata;pre=p; p=pnext; /（1）查找最小值結(jié)點/whileprintf(predata); /（2）輸出最小值結(jié)點if(prenext && predata%2=0) /如果最小節(jié)點的下一個接點是偶數(shù)就刪除p=prenext, prenext=pnext;free(p); /（3）刪除其后繼結(jié)點/if/ F1算法功能： （7）閱讀下列算法：（設(shè)L是帶頭結(jié)點的單鏈表的頭指針，并為已知的LinkList類型）void DeleteX(LinkList &L) p=L>next; while(p&& p>next>data!=x) q=p;p=p>next; if(p) q>next=p>next; free(p);算法的功能： 刪除單鏈表L中值為X的結(jié)點的直接前驅(qū)結(jié)點2、程序設(shè)計(1) 設(shè)有一單鏈表L，結(jié)點結(jié)構(gòu)為dat