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