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

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