數(shù)據(jù)結(jié)構(gòu)期末試題(帶答案)

模擬試題7一、選擇題（每小題1分，共10分）1、如果樹的結(jié)點(diǎn)A有4個(gè)兄弟，而且B為A的雙親，則 B的度為。(A)3 (B)4 (C)5 (D)12、設(shè)有一個(gè)棧，元素的進(jìn)棧次序?yàn)锳，B，C，D，E，則下列是不可能的出棧序列。(A)A,B,C,D,E (B)B,C,D,E,A (C)E,A,B,C,D (D)E,D,C,B,A3、在所有排序方法中，關(guān)鍵字的比較次數(shù)與記錄的初始排列無(wú)關(guān)的是。(A)快速排序 (B)冒泡排序 (C)直接插入排序 (D)直接選擇排序4、設(shè)一棵二叉樹共有20個(gè)度為2的結(jié)點(diǎn)，則葉子結(jié)點(diǎn)共有個(gè)。(A)4 0 (B)19 (C)20 (D)215、在具有N個(gè)單元的順序存儲(chǔ)的循環(huán)隊(duì)列中，假定front和rear分別為隊(duì)頭指針和隊(duì)尾指針，則判斷隊(duì)空的條件為。(A)front==rear (B)（rear+1）%MAXSIZE==front (C)front-rear==1 (D)rear%MAXSIZE==front6、設(shè)有1000個(gè)元素，用二分法查找時(shí)，最小比較次數(shù)為。(A)0 (B)1 (C)10 (D)5007、一個(gè)元素進(jìn)入隊(duì)列的時(shí)間復(fù)雜度是。(A)O(1) (B)O(n) (C)O(n2) (D)O(log2n)8、設(shè)一顆完全二叉樹中根結(jié)點(diǎn)的編號(hào)為1，而且23號(hào)結(jié)點(diǎn)有左孩子但沒(méi)有右孩子，則完全二叉樹總共有個(gè)結(jié)點(diǎn)。(A)24 (B)45 (C)46 (D)47二、判斷題（每題1分，共8分，對(duì)的打√，錯(cuò)的打×）1、如果某數(shù)據(jù)結(jié)構(gòu)的每一個(gè)元素都最多只有一個(gè)直接前驅(qū)和一個(gè)直接后繼結(jié)點(diǎn)，則必為線性表。（）2、先序遍歷一棵二叉搜索樹所得的結(jié)點(diǎn)訪問(wèn)序列不可能是鍵值遞增序列。（）3、若有一個(gè)葉子結(jié)點(diǎn)是某子樹的中序遍歷的最后一個(gè)結(jié)點(diǎn)，則它必須是該子樹的先序遍歷的最后一個(gè)結(jié)點(diǎn)。（）4、有向圖的鄰接矩陣的第i行的所有元素之和等于第i列的所有元素之和。（）5、二叉排序樹中，任一結(jié)點(diǎn)的值都大于或等于其孩子的值。（）6、圖的生成樹的邊數(shù)要小于頂點(diǎn)數(shù)。（√）7、進(jìn)棧操作時(shí)，必須判斷棧是否已滿。（）8、如果某排序算法是穩(wěn)定的，那么該方法一定具有實(shí)際應(yīng)用價(jià)值。（）三、填空題（每題2分，共16分）1、數(shù)據(jù)結(jié)構(gòu)有線性結(jié)構(gòu)、樹結(jié)構(gòu)、、等幾種邏輯結(jié)構(gòu)。2、已知某算法的執(zhí)行時(shí)間為（n+n2）/2+log2(2n+1)，n代表問(wèn)題規(guī)模，則該算法的時(shí)間復(fù)雜度是O(n2)。3、一個(gè)無(wú)向連通圖有6個(gè)頂點(diǎn)7條邊，則其生成樹有條邊。4、順序存儲(chǔ)的隊(duì)列如果不采用循環(huán)方式，則會(huì)出現(xiàn)問(wèn)題。5、一個(gè)10×10的三角矩陣a采用行優(yōu)先壓縮存儲(chǔ)后，如果首元素a[0][0]是第一個(gè)元素，那么a[4][2]是第個(gè)元素。6、如果一個(gè)有向圖有5個(gè)頂點(diǎn)，則它最多有條弧。7、采用快速排序法進(jìn)行排序時(shí)，如果有序排列時(shí)，排序效率會(huì)大大降低。8、設(shè)無(wú)向圖G有100條邊，則G至少有101個(gè)頂點(diǎn)。四、簡(jiǎn)答題（共38分）1、排序。（1）寫出線性表（26，45，12，2.，30，6，15，29，16，2，18）采用快速算法排序后，第一趟結(jié)束時(shí)的結(jié)果。（4分）//答案錯(cuò)，正確如下：//18,2,12,2,16,6,15,26,29,30,45（2）線性表采用插入排序算法排序幾趟后，有序部分是（16，20，40），無(wú)序部分是（18，25），則下一趟的排序需要移動(dòng)幾個(gè)元素？寫出下一趟結(jié)束時(shí)的結(jié)果。（4分）//答：采用插入排序算法2趟后，可得到上述結(jié)果。下一趟的排序需要移動(dòng)2個(gè)元素，結(jié)束時(shí)的結(jié)果是：有序部分是（16，18，20，40），無(wú)序部分是（25）。2、給出如圖1所示的二叉樹的中序遍歷結(jié)果。（5分）3、已知5個(gè)結(jié)點(diǎn)的權(quán)值分別是4，6，1，13，7，請(qǐng)畫出這結(jié)點(diǎn)構(gòu)成的Huffman樹。（5分）4、已知圖2是一個(gè)無(wú)向圖：（1）畫出該無(wú)向圖的鄰接鏈表。（5分）（2）基于你給出的鄰接鏈表，求從頂點(diǎn)C出發(fā)的廣度優(yōu)先遍歷。（5分）5、（1）根據(jù)線性表（23，49，28，10，30，5，16），畫出二叉排序樹。（5分）（2）根據(jù)上述二叉排序樹，查找數(shù)7，需要比較哪幾個(gè)數(shù)？（5分）五、程序填空題（共15分）1、已知QUEUE表示循環(huán)隊(duì)列的數(shù)據(jù)結(jié)構(gòu)，函數(shù)leavequeue是將隊(duì)頭元素的值放入變量e，然后刪除隊(duì)頭元素，操作成功返回1，否則返回0。完成以下程序。（4分）typedefstruct{intdata[100];intfront;/*隊(duì)頭元素的下標(biāo)*/intrear；/*等于隊(duì)尾元素的下標(biāo)加1*/}QUEUE;leavequeue(QUEUE*Q,int*e){if(){return0;}*e=Q->data[Q->front];Q->front=;return1;}2、以下函數(shù)ins的功能是在順序表a中找到第一個(gè)值為x的元素，然后在該元素之前插入一個(gè)值為y的元素，如果找不到值為x的元素，則新元素成為順序表的最后一個(gè)元素。插入成功返回1，否則返回0。完成程序。（6分）typedefstruct{intelem[100];intlength;}SQ;intins(SQ*a,intx,inty){intk,i;if(){return0;}for(k=0;k<a->length;++k){if(a->elem[k]==x){break;}}if(k==a->length){--k;}else{for(i=a->length-1;i>k;--i)//應(yīng)改為：for(i=a->length-1;i>=k;--i){a->elem[i+1]=a->elem[i];}}a[k+1]=y;a->length;return1;}3、已知一個(gè)單鏈表的表頭指針為h，每個(gè)結(jié)點(diǎn)含元素值data和下一結(jié)點(diǎn)的地址next。鏈表一共有5個(gè)結(jié)點(diǎn)，其元素值分別為100，200，300，400，500，經(jīng)過(guò)下列語(yǔ)句后，輸出什么結(jié)果？（本題3分）for(p=h;p->data<300;p=p->next){p->next=p->next->next;}printf(“%d”,p->data);六、編程題（共15分）1、編寫算法求二叉樹的非葉子結(jié)點(diǎn)數(shù)目。（8分）已知二叉樹結(jié)點(diǎn)數(shù)據(jù)結(jié)構(gòu)如下：typedefstructlinkNode{intdata;structlinkNode*lchild,*rchild;}Node;2、編寫算法判斷一個(gè)單鏈表中各結(jié)點(diǎn)的值是不是由小到大排列，如是（包括空表）返回1，不是返回0。（7分）已知單鏈表結(jié)點(diǎn)數(shù)據(jù)結(jié)構(gòu)如下：typedefstructlinkNode{intdata;structlinkNode*next;}Node;模擬題7答案一、選擇題12345678CCDDBBAC二、判斷題12345678××××××××三、填空題1、圖結(jié)構(gòu) 集合結(jié)構(gòu)2、O(n2log2n)3、54、虛溢出5、136、207、降序排列8、11四、簡(jiǎn)答題1、（1）20 12 26 45 30（2）16 18 20 40，需移動(dòng)2個(gè)元素2、（1）D B A F G E C3、4、（1）//下圖錯(cuò)誤！//正確的鄰接表如下：1261260350ABCDEFG0312435012345614（2）C A D B G F E//正確為：C A D B G E F5、（1）（2）23 10 5五、程序填空題1、（1）Q->front==Q->rear(2)(Q->front+1)%1002、（1）a->length>=100（2）a->elem[i]=a->elem[i-1]（3）a[k](4)++或者=a->length+13、300六、編程題1、intcountNotLeaf(Node*BT){if(BT==NULL){return0;

}if((BT->lchild==NULL)&&(BT->rchild==NULL)){return0;

}return(1+countNotLeaf(BT->lchild)+countN