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

1、練習(xí)題：一、 填空題1、元素項(xiàng)是數(shù)據(jù)的最小單位，數(shù)據(jù)元素是討論數(shù)據(jù)結(jié)構(gòu)時(shí)涉及的最小數(shù)據(jù)單位。2、設(shè)一棵完全二叉樹(shù)具有100個(gè)結(jié)點(diǎn)，則此完全二叉樹(shù)有49個(gè)度為2的結(jié)點(diǎn)。3、在用于表示有向圖的鄰接矩陣中，對(duì)第i列的元素進(jìn)行累加，可得到第i個(gè)頂點(diǎn)的出度。4、已知一棵度為3的樹(shù)有2個(gè)度為1的結(jié)點(diǎn)，3個(gè)度為2的結(jié)點(diǎn)，4個(gè)度為3的結(jié)點(diǎn)，則該樹(shù)中有12個(gè)葉子的結(jié)點(diǎn)。n=n0+n1+n2+nm (1)又有除根結(jié)點(diǎn)外,樹(shù)中其他結(jié)點(diǎn)都有雙親結(jié)點(diǎn),且是唯一的(由樹(shù)中的分支表示),所以,有雙親的結(jié)點(diǎn)數(shù)為：n-1=0*n0+1*n1+2*n2+m*nm (2)聯(lián)立(1)(2)方程組可得：葉子數(shù)為：n0=1+0*n1+1

2、*n2+2*n3+.+(m-1)*nm5、有一個(gè)長(zhǎng)度為20的有序表采用二分查找方法進(jìn)行查找，共有4個(gè)元素的查找長(zhǎng)度為3。6、對(duì)于雙向鏈表，在兩個(gè)結(jié)點(diǎn)之間插入一個(gè)新結(jié)點(diǎn)需要修改的指針共4個(gè)。 刪除一個(gè)結(jié)點(diǎn)需要修改的指針共2個(gè)。7、已知廣義表LS=(a,(b,c,d),e)，它的深度是2，長(zhǎng)度是3。8、循環(huán)隊(duì)列的引入是為了克服假溢出。9、表達(dá)式a*(b+c)-d/f的后綴表達(dá)式是abc+*df/-。10、數(shù)據(jù)結(jié)構(gòu)中評(píng)價(jià)算法的兩個(gè)重要指標(biāo)是時(shí)間復(fù)雜度和空間復(fù)雜度。11、設(shè)r指向單鏈表的最后一個(gè)結(jié)點(diǎn)，要在最后一個(gè)結(jié)點(diǎn)之后插入s所指的結(jié)點(diǎn)，需執(zhí)行的三條語(yǔ)句是r->next=s; r=s; r-&g

3、t;next=null;12、設(shè)有一個(gè)空棧，棧頂指針為1000H(十六進(jìn)制)，現(xiàn)有輸入序列為1，2，3，4，5，經(jīng)過(guò)PUSH,PUSH,POP,PUSH,POP,PUSH,PUSH之后，輸出序列是23，而棧頂指針值是1012_H。設(shè)棧為順序棧，每個(gè)元素占4個(gè)字節(jié)。13、模式串P=abaabcac的next函數(shù)值序列為01122312。14、任意連通圖的連通分量只有一個(gè)，即是自身。15、棧的特性是先進(jìn)后出。16、串的長(zhǎng)度是包含的元素個(gè)數(shù)。17、如果一個(gè)有向圖中沒(méi)有回路，則該圖的全部頂點(diǎn)可能排成一個(gè)拓?fù)湫蛄小?8、在具有n個(gè)葉子結(jié)點(diǎn)的哈夫曼樹(shù)中，分支結(jié)點(diǎn)總數(shù)為n-1。17619、在線性表的散列存儲(chǔ)

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

5、n+1 。15025、在有序表A120中，按二分查找方法進(jìn)行查找，查找長(zhǎng)度為4的元素的下標(biāo)從小到大依次是1 3 6 8 11 13 16 1926、設(shè)查找表中有100個(gè)元素，如果用二分法查找方法查找數(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)，樹(shù)形結(jié)構(gòu)，圖狀結(jié)構(gòu)）。從存儲(chǔ)結(jié)構(gòu)的概念上講，順序表是線性表的（順序存儲(chǔ)結(jié)構(gòu)），鏈表是（鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)）。27、根據(jù)初始關(guān)鍵字序列(17，25，3，39，12)建立的二叉排序樹(shù)的高度為3

6、。27、算法的五個(gè)重要特性有哪些。（有窮性、確定性、可行性、輸入、輸出）。抽象數(shù)據(jù)類型是指一個(gè)（數(shù)學(xué)模型）以及定義在該模型上的（一組操作）。28、設(shè)有一個(gè)n階的下三角矩陣A，如果按照行的順序?qū)⑾氯蔷仃囍械脑兀ò▽?duì)角上元素）存放在n(n+1)個(gè)連續(xù)的存儲(chǔ)單元中，則Aij與A00之間有(i)個(gè)數(shù)據(jù)元素。29、 棧的插入和刪除只能在棧的棧頂進(jìn)行，后進(jìn)棧的元素必定先出棧，所以又把棧稱為FILO；隊(duì)列的插入和刪除運(yùn)算分別在隊(duì)列的兩端進(jìn)行，先進(jìn)隊(duì)列的元素必定先出隊(duì)列，所以又把隊(duì)列稱為FIFO表。30、 設(shè)一棵完全二叉樹(shù)的順序存儲(chǔ)結(jié)構(gòu)中存儲(chǔ)數(shù)據(jù)元素為ABCDEF，則該二叉樹(shù)的前序遍歷序列為ABDEF，

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

8、3、已知棧的輸入序列為1，2，3，n，輸出序列為a1，a2，an，a2=n的輸出序列共有（n-1）種輸出序列。34、 設(shè)有向圖G的存儲(chǔ)結(jié)構(gòu)用鄰接矩陣A來(lái)表示，則A中第i行中所有非零元素個(gè)數(shù)之和等于頂點(diǎn)i的出度，第i列中所有非零元素個(gè)數(shù)之和等于頂點(diǎn)i的入度。35、將下三角矩陣Al.8，1.8的下三角部分逐行地存儲(chǔ)到起始地址為1000的內(nèi)存單元中，已知每個(gè)元素占4個(gè)單元，則A7，5的地址為 （1100）。36、已知數(shù)組A1.10，1.10為對(duì)稱矩陣，其中每個(gè)元素占5個(gè)單元?，F(xiàn)將其下三角部分按行優(yōu)先次序存儲(chǔ)在起始地址為1000的連續(xù)的內(nèi)存單元中，則元素A5，6對(duì)應(yīng)的地址為（1095）。37、兩個(gè)串相

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

10、的深度為( 7)。41、拓?fù)渑判蛑荒苡糜冢ㄓ邢驘o(wú)環(huán)圖）。連通圖是指圖中任意兩個(gè)頂點(diǎn)之間（都連通的無(wú)向圖）。一個(gè)有n個(gè)頂點(diǎn)的無(wú)向連通圖，它所包含的連通分量個(gè)數(shù)最多為(1)個(gè)。任何一個(gè)無(wú)向連通圖的最小生成樹(shù)（有一棵或多棵）。若含有n個(gè)頂點(diǎn)的圖形成一個(gè)環(huán)，則它有（n）棵生成樹(shù)。42、求圖的最小生成樹(shù)有兩種算法，（普利姆）算法適合于求稠密圖的最小生成樹(shù)，（克魯斯卡爾）算法適合于求稀疏圖的最小生成樹(shù)。設(shè)圖G用鄰接表存儲(chǔ)，則拓?fù)渑判虻臅r(shí)間復(fù)雜度為(O(n+e)。44、從未排序序列中依次取出元素與已排序序列(初始時(shí)為空)中的元素進(jìn)行比較，將其放入已排序序列的正確位置上的方法，稱為(插入排序)。對(duì)于關(guān)鍵字序列

11、(12，13，11，18，60，15，7，18，25，100)，用篩選法建堆，則開(kāi)始結(jié)點(diǎn)的鍵值必須為（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 (t->key>k) t=t->lchild; elset=t

12、->lchild;34、 下面程序段的功能是實(shí)現(xiàn)冒泡排序算法，請(qǐng)?jiān)谙聞澗€處填上正確的語(yǔ)句。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、 下面程序段的功能是實(shí)現(xiàn)二分查找算法，請(qǐng)?jiān)谙聞澗€處填上正確的語(yǔ)句。struct recordint key; int others;int bisearch(struct record r

13、 , 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ù)中度數(shù)為0的結(jié)點(diǎn)數(shù)為50，度數(shù)為1的結(jié)點(diǎn)數(shù)為30，則該二叉樹(shù)中總共有129個(gè)結(jié)點(diǎn)數(shù)。15137、設(shè)有向圖G的二元組形式表示為G =（D，R），D=1，2，3，4，5，R=r，r=<1,2>，<2,4>，<4,5>，<1,

14、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è)二叉排序樹(shù)的高度為h，則在該樹(shù)中查找關(guān)鍵字key最多需要比較h次.二、選擇題1、從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分為（ C ）兩大類。A動(dòng)態(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、若長(zhǎng)度為n的線性表采用順序存儲(chǔ)結(jié)構(gòu)，在其第i個(gè)位置插入一個(gè)新元素的算法的時(shí)間復(fù)雜度為（ C ）(1

15、<=i<=n+1)。A. O(0) B. O(1) C. O(n) D. O(n2)3、若已知一個(gè)棧的入棧序列是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表中取出原子項(xiàng)t的運(yùn)算是（D）。A. head（tail（tail（L） B. tail（head（head（tail（L） C. head（tail（head（tail（L）D. head（tail(head（tail（tail（L）)）5、下列陳述中正確的是（ D ）。A.

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

17、表，二分查找的平均查找長(zhǎng)度（C）。236 A. 2.5 B. 4 C. 3.1 D. 510、AVL樹(shù)是一種平衡的二叉排序樹(shù)，樹(shù)中任一結(jié)點(diǎn)的（ B ）245A.左、右子樹(shù)的高度均相同 B.左、右子樹(shù)高度差的絕對(duì)值不超過(guò)1C.左子樹(shù)的高度均大于右子樹(shù)的高度 D.左子樹(shù)的高度均小于右子樹(shù)的高度11、線性表采用鏈接存儲(chǔ)時(shí)，其地址（D ）。A.必須是連續(xù)的 B.部分地址必須是連續(xù)的C.一定是不連續(xù)的 D.連續(xù)與否均可以12、棧和隊(duì)列是兩種特殊的線性表，只能在它們的（B）處添加或刪除結(jié)點(diǎn)。  中間點(diǎn)   端點(diǎn)   隨機(jī)存取點(diǎn)   結(jié)點(diǎn)13、輸入序列為ABC，可以變

18、為BAC時(shí)，經(jīng)過(guò)的棧操作為（ 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模式匹配是串的一種重要運(yùn)算 D串既可以采用順序存儲(chǔ)，也可以采用鏈?zhǔn)酱鎯?chǔ)16、數(shù)組A67的每個(gè)元素占五個(gè)字節(jié)，將其按行優(yōu)先次序存儲(chǔ)在起始地址為10

19、00的內(nèi)存單元中，則元素A35的地址是( A )。117 A. 1130 B. 1180 C. 1205 D. 121017、對(duì)于一個(gè)具有n個(gè)頂點(diǎn)的無(wú)向圖，若采用鄰接矩陣存儲(chǔ)，則該矩陣的大小是（ D ）。195An B(n-1)2 Cn-1 Dn218、若廣義表A滿足Head(A)=Tail(A)，則A為（ B ）。A（ ） B（） C（），（） D（），（），（）19、堆的形狀是一棵 (C )。 A.二叉排序樹(shù) B.滿二叉樹(shù) C.完全二叉樹(shù) D.判定樹(shù)20、若要在單鏈表中的結(jié)點(diǎn) *p 之后插入一個(gè)結(jié)點(diǎn) *s ，則應(yīng)執(zhí)行的語(yǔ)句是 (A ) As->next=p->next； p-&

20、gt;next=s； Bp->next=s； s->next=p->next；Cp->next=s->next； s->next=p； Ds->next=p； p->next=s->next；21、鏈表不具有的特點(diǎn)是（ ）。A插入、刪除不需要移動(dòng)元素 B可隨機(jī)訪問(wèn)任一元素 C不必事先估計(jì)存儲(chǔ)空間 D所需空間與線性長(zhǎng)度成正比22、一個(gè)棧的輸入序列為1 2 3 4 5，則下列序列中不可能是棧的輸出序列的是（ B ）。 A. 2 3 4 1 5 B. 5 4 1 3 2 C. 2 3 1 4 5 D. 1 5 4 3 223、遞歸過(guò)程或函數(shù)調(diào)用時(shí)

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

22、有18個(gè)元素的有序表存放在一維數(shù)組A19中，第一個(gè)元素放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)，以第一個(gè)記錄關(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é)點(diǎn)A，若刪除單鏈表中結(jié)點(diǎn)A，則需要修改指針的操作序列為（A ）。A q=p->next；p->data=q->data；p->ne

23、xt=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ù)中度數(shù)為0的結(jié)點(diǎn)數(shù)為N0，度數(shù)為1的結(jié)點(diǎn)數(shù)為Nl，度數(shù)為2的結(jié)點(diǎn)數(shù)為N2，則下列等式成立的是（C ）。A N0=N1+1B. N0=Nl+N2C. N0=N2+1D. N0=2N1+l31、設(shè)一棵m叉樹(shù)中度數(shù)為0的結(jié)點(diǎn)數(shù)為N0

24、，度數(shù)為1的結(jié)點(diǎn)數(shù)為Nl，度數(shù)為m的結(jié)點(diǎn)數(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è)無(wú)向圖G中的邊的集合E=(a，b)，(a，e)，(a，c)，(b，e)，(e，d)，(d，f)，(f，c)，則從頂點(diǎn)a出發(fā)進(jìn)行深度優(yōu)先遍歷可以得到的一種頂點(diǎn)序列為（ A ）。A. aedfcb B. acfebd C. aebcfd D. aedfbc26、某二叉樹(shù)的先序序列和后序序列正好相反，則該二叉樹(shù)的特點(diǎn)一定是（ BB ）。A. 空或只有一個(gè)結(jié)點(diǎn) B.高度等于其結(jié)點(diǎn)數(shù)

25、C. 任一結(jié)點(diǎn)無(wú)左孩子 D.任一結(jié)點(diǎn)無(wú)右孩子28、下面的說(shuō)法中正確的是（ B ）。 (1)任何一棵二叉樹(shù)的葉子節(jié)點(diǎn)在三種遍歷中的相對(duì)次序不變。 (2)按二叉樹(shù)定義，具有三個(gè)節(jié)點(diǎn)的二叉樹(shù)共有6種。A(1)，(2) B(1) C(2) D(1)，(2)都錯(cuò)29、樹(shù)有先根遍歷和后根遍歷，樹(shù)可以轉(zhuǎn)化為對(duì)應(yīng)的二叉樹(shù)。下面的說(shuō)法正確的是（ B ）。 A樹(shù)的后根遍歷與其對(duì)應(yīng)的二叉樹(shù)的后根遍歷相同 B樹(shù)的后根遍歷與其對(duì)應(yīng)的二叉樹(shù)的中根遍歷相同C樹(shù)的先根遍歷與其對(duì)應(yīng)的二叉樹(shù)的中根遍歷相同 D以上都不對(duì)30、.下圖的鄰接表中，從頂點(diǎn)V1 出發(fā)采用深度優(yōu)先搜索法遍歷該圖，則可能的頂點(diǎn)序列是 （ D ）。A. V1V

26、2V3V4V5 B. V1V2V3V5V4 C. V1V4V3V5V2 D.V1V3V4V5V2 31、以下說(shuō)法不正確的是（ D ）。 A無(wú)向圖中的極大連通子圖稱為連通分量 B連通圖的廣度優(yōu)先搜索中一般要采用隊(duì)列來(lái)暫存剛訪問(wèn)過(guò)的頂點(diǎn) C圖的深度優(yōu)先搜索中一般要采用棧來(lái)暫存剛訪問(wèn)過(guò)的頂點(diǎn) D有向圖的遍歷不可采用廣度優(yōu)先搜索32、設(shè)哈希表長(zhǎng)為14，哈希函數(shù)H(key)=key11，表中已有數(shù)據(jù)的關(guān)鍵字為15，38，61，84，四個(gè)，現(xiàn)將關(guān)鍵字為49的結(jié)點(diǎn)加到表中，用二次探測(cè)再散列法解決沖突，則放入的位置是（ DD ）。 A8 B3 C5 D934、二維數(shù)組A的每個(gè)元素是由6個(gè)字符組成的串，其行下標(biāo)

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

28、C2n Dn-141、有向圖G用鄰接矩陣A存儲(chǔ)，則頂點(diǎn)i的入度等于A中（ BB ）。A. 第i行1的元素之和 B. 第i列1的元素之和C. 第i行0的元素個(gè)數(shù) D. 第i列0的元素個(gè)數(shù)42、用某種排序方法對(duì)關(guān)鍵字序列（25，84，21，47，15，27，68，35，20）進(jìn)行排序時(shí)，序列的變化情況如下： 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希爾排序 C歸并排序 D快速排序43、設(shè)一組初始關(guān)鍵字記錄關(guān)鍵字為(20，15，14，1

29、8，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個(gè)關(guān)鍵字具有相同的Hash函數(shù)值，則用線性探測(cè)法把這n個(gè)關(guān)鍵字映射到HASH表中需要做（ D）次線性探測(cè)。A. n2 B. n(n+1)C. n(n+1)/2D. n(n-1)/2三、判斷題1如果兩個(gè)串含有相同的字符，則這兩個(gè)串相等。（x ）2數(shù)組可以看成線性結(jié)構(gòu)的一種推廣，因此可以

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

31、列中第一個(gè)元素的前一位置，rear指向?qū)嶋H的隊(duì)尾元素，隊(duì)列為滿的條件是front=rear。（ x ）13、對(duì)鏈表進(jìn)行插入和刪除操作時(shí)，不必移動(dòng)結(jié)點(diǎn)。（ v ）14、?？梢宰鳛閷?shí)現(xiàn)程序設(shè)計(jì)語(yǔ)言過(guò)程調(diào)用時(shí)的一種數(shù)據(jù)結(jié)構(gòu)。（ v ）15、在一個(gè)有向圖的拓樸序列中，若頂點(diǎn)a在頂點(diǎn)b之前，則圖中必有一條弧<a,b> ( x ) 。16、對(duì)有向圖G，如果從任一頂點(diǎn)出發(fā)進(jìn)行一次深度優(yōu)先或廣度優(yōu)先搜索就能訪問(wèn)每個(gè)頂點(diǎn)，則該圖一定是完全圖。( x )17、“順序查找法”是指在順序表上進(jìn)行查找的方法。（ x ）18、向二叉排序樹(shù)插入一個(gè)新結(jié)點(diǎn)時(shí)，新結(jié)點(diǎn)一定成為二叉排序樹(shù)的一個(gè)葉子結(jié)點(diǎn)。（ v ）19

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

33、v ）27線性表的順序存儲(chǔ)結(jié)構(gòu)比鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)更好。（ x ）28中序遍歷二叉排序樹(shù)可以得到一個(gè)有序的序列。（ v ）29.快速排序是排序算法中平均性能最好的一種排序。（v ）30不論是入隊(duì)列操作還是入棧操作，在順序存儲(chǔ)結(jié)構(gòu)上都需要考慮“溢出”情況。（ v ）31當(dāng)向二叉排序樹(shù)中插入一個(gè)結(jié)點(diǎn)，則該結(jié)點(diǎn)一定成為葉子結(jié)點(diǎn)。（ v ）32設(shè)某堆中有n個(gè)結(jié)點(diǎn)，則在該堆中插入一個(gè)新結(jié)點(diǎn)的時(shí)間復(fù)雜度為O(log2n)。（v ）33完全二叉樹(shù)中的葉子結(jié)點(diǎn)只可能在最后兩層中出現(xiàn)。（ v ）34哈夫曼樹(shù)中沒(méi)有度數(shù)為1的結(jié)點(diǎn)。（ v ）35對(duì)連通圖進(jìn)行深度優(yōu)先遍歷可以訪問(wèn)到該圖中的所有頂點(diǎn)。（ v ）36先序遍歷一

34、棵二叉排序樹(shù)得到的結(jié)點(diǎn)序列不一定是有序的序列。（v ）37由樹(shù)轉(zhuǎn)化成二叉樹(shù)，該二叉樹(shù)的右子樹(shù)不一定為空。（x）38線性表中的所有元素都有一個(gè)前驅(qū)元素和后繼元素。（ x ）39.帶權(quán)無(wú)向圖的最小生成樹(shù)是唯一的。（ x ）四、應(yīng)用題1、已知一棵二叉樹(shù)的中根序列和后根序列分別為CBEDAFIGH及CEDBIFHGA，請(qǐng)畫(huà)出這棵二叉樹(shù)，并給出其先序序列。ABCDEGFIH1、已知一棵二叉樹(shù)的先根序列和中根序列分別為ABDGHECFIJ及GDHBEACIJF，請(qǐng)畫(huà)出這棵二叉樹(shù)，并給出其后序序列。GHDEBJIFCA2、將下列由三棵樹(shù)組成的森林轉(zhuǎn)換為二叉樹(shù)。（只要求給出轉(zhuǎn)換結(jié)果）3、已知無(wú)向圖如下所示：（

35、1）給出從V1開(kāi)始的廣度優(yōu)先搜索序列；（2）畫(huà)出它的鄰接表；（3）畫(huà)出從V1開(kāi)始深度優(yōu)先搜索生成樹(shù)。 4.假定用于通訊的電文僅有8個(gè)字母C1，C2，C8組成，各個(gè)字母在電文中出現(xiàn)的頻率分別為5，15，3，6，22，11，30，8，請(qǐng)先構(gòu)建一棵哈夫曼樹(shù)，計(jì)算其WPL值，并為這8個(gè)字母設(shè)計(jì)相應(yīng)的哈夫曼編碼4、假定用于通訊的電文僅有8個(gè)字母C1，C2，C8組成，各個(gè)字母在電文中出現(xiàn)的頻率分別為5，25，3，6，10，11，36，4，請(qǐng)先構(gòu)建一棵哈夫曼樹(shù)，計(jì)算其WPL值，并為這8個(gè)字母設(shè)計(jì)相應(yīng)的哈夫曼編碼。5、已知一表為（Jan,Feb,Mar,Apr,May,Jun,Jul,Aug,Sep,Oct,

36、Nov,Dec）,按表中順序依次插入初始為空的二叉排序樹(shù)，要求：(1)畫(huà)出建立的二叉排序樹(shù)（值的大小以字母順序?yàn)闇?zhǔn)）。(2)對(duì)該二叉排序樹(shù)作中序遍歷，試寫(xiě)出遍歷序列。(3)求出在等概率情況下查找成功的平均查找長(zhǎng)度。6、已知一個(gè)圖的頂點(diǎn)集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; 按照普里姆算法從頂點(diǎn)0出發(fā)得到最小生成樹(shù)，試寫(xiě)出在最小生成樹(shù)中依次得到的各條邊。(0,1),(0,3),(0,2),(1,5),(3,6),(6,4),

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

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

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

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

41、關(guān)鍵字集（30，14，25，43，35，27，64，49），若查找表的裝填因子為0.8，采用線性探測(cè)再散列解決沖突：（1）設(shè)計(jì)哈希函數(shù)；（2）畫(huà)出哈希表；（3）求查找成功的平均查找長(zhǎng)度。14、在如下數(shù)組A中鏈接存儲(chǔ)了一個(gè)線性表，表頭指針為A 0.next，試寫(xiě)出該線性表。 A 0 1 2 3 4 5 6 7 data605078903440next3572041線性表為：（78，50，40，60，34，90）15、按順序輸入下列頂點(diǎn)對(duì): (V1, V2)、(V1, V6)、(V2, V6)、(V1, V4)、(V6, V4)、(V1, V3)、(V3, V4)、(V6, V5)、(V4, V5

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

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

44、r (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）說(shuō)出下列算法的功能，它是采用什么結(jié)構(gòu)實(shí)現(xiàn)的。 template <class T>void BiTree<T>:Unknown (BiNode<T> *root) const int MaxSize = 100; int front = 0; int rear = 0; BiN

45、ode<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; 算法功能：二叉樹(shù)的層序遍歷 對(duì)列 （4）閱讀下列算法求出調(diào)用該算法后輸出結(jié)果。voi

46、d 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è)有一個(gè)正整數(shù)序列組成的非遞減有序單鏈表，閱讀下面的算法，指出該算法的功能，并在“/后面加上必要的注釋。void F1(Linklist L;int,x)

47、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è)有一個(gè)由正整數(shù)組成的無(wú)序單鏈表，閱讀下面的算法，指出該算法的功能。void F1(Linklist &L) p=Lnext; pre=p; /pre為最小結(jié)點(diǎn)指針while(p) if(pdata<p

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