資源描述：
《全真模擬試題(二)》由會員上傳分享，免費在線閱讀，更多相關內容在教育資源-天天文庫。
1、全真模擬試題（二）一、單項選擇題（在每個小題的4個備選答案中，選出正確的答案，并將其號碼填在題后的括號內。每小題2分，共24分）1．一個具有n個頂點的無向完全圖的邊數(shù)為（?。賜(n+1)/2②n(n-1)/2③n(n-1)④n(n+1)2．在索引順序表中查找一個元素，可用的且最快的方法是（?。儆庙樞虿檎曳ù_定元素所在塊，再用順序查找法在相應塊中查找②用順序查找法確定元素所在塊，再用二分查找法在相應塊中查找③用二分查找法確定元素所在塊，再用順序查找法在相應塊中查找④用二分查找法確定元素所在塊，再用二分查找法在相應塊中查找3．若某線性表中最常用的操作是在
2、最后一個元素之后插入一個元素和刪除最后一個元素，則采用（?。┐鎯Ψ绞阶罟?jié)省運算時間。①單鏈表?、陔p鏈表 ③帶頭結點的雙循環(huán)鏈表?、苋萘孔銐虼蟮捻樞虮?．串是（?。僖恍┓枠嫵傻男蛄小、谟邢迋€字母構成的序列③一個以上的字符構成的序列?、苡邢迋€字符構成的序列5．堆排序在最壞情況下，其時間復雜性為（?。貽(nlog2n)?、贠(n2)?、跲(log2n2)④O(log2n)6．快速排序的記錄移動次數(shù)（ ）比較次數(shù)，其總執(zhí)行時間為O(nlog2n)。①大于 ②大于等于?、坌∮诘扔凇、苄∮凇 ?．一棵二叉樹有n個結點，要按某順序對該二叉樹中的結點編號，（號碼為
3、1-n），編號須具有如下性質：二叉樹中任一結點V，其編號等于其左子樹中結點的最大編號加1。而其右子樹中結點的最小編號等于V的編號加1。試問應按（?。┍闅v順序編號。①前根?、谥懈、酆蟾、軐哟巍 ?.3個結點可構成（ ）個不同形態(tài)的二叉樹。①2?、? ③4?、? 9．對有n個記錄的有序表采用二分查找，其平均查找長度的量級為（ ）①O(log2n)?、贠(nlog2n)?、跲(n) ④O(n2)10．對有n個記錄的表按記錄鍵值有序的順序建立二叉樹，在這種情況下，其平均查找長度的量級為（?。貽(n) ②O(nlog2n)?、跲(1)?、?log2n)11
4、．棧操作的原則是（?。傧冗M先出 ②后進先出?、蹢ｍ敳迦搿、軛ｍ攧h除12．設矩陣A是一對稱矩陣(aij=aji,1<=i,j<=8)，若每個矩陣元素占3個單元，將其上三角部分（包括對角線）按行序為主序存放在數(shù)組B中，B的首地址為1000，則矩陣元素a67的地址為（?。?031?、?093?、?096?、?032二、判斷題（判斷下列各題是否正確，正確在括號內打“√”，錯的打“×”。每小題1分，共10分）41．如果兩個串含有相同的字符，則這兩個串相等。 ?。ā。?．數(shù)組可以看成線性結構的一種推廣，因此可以對它進行插入、刪除等運算?！。ā。?．在索引順序表上
5、實現(xiàn)分塊查找，在等概率查找情況下，其平均查找長度不僅與表中元素個數(shù)有關，而且與每一塊中元素個數(shù)有關。（?。?．在順序表中取出第i個元素所花費的時間與i成正比?！ 。ā。?．在棧滿情況下不能作進棧運算，否則產生“上溢”?！ ??。?．二路歸并排序的核心操作是將兩上有序序列歸并為一個有序序列?！。ā。?．對任意一個圖，從它的某個頂點出發(fā)，進行一次深度優(yōu)先或廣度優(yōu)先搜索，即可訪問圖的每個頂點.（?。?．二叉排序樹或者是一棵空二叉樹，或者是具有下列性質的二叉樹：若它的左子樹非空，則根結點的值大于其左孩子的值;若它的右子樹非空，則根結點的值小于其右孩子的值。（
6、?。?．在執(zhí)行某個排序算法過程中，出現(xiàn)了排序碼朝著最終排序序列位置相反方向移動，則該算法是不穩(wěn)定的。（?。?0．一個有向圖的鄰接表和逆鄰接表中表結點的個數(shù)一定相等?！。ā。┤?、填空題（每空2分，共26分）1．在帶有頭結點的單鏈表L中，若要刪除第一個結點，則需執(zhí)行下列三條語句：＿＿＿＿＿＿＿＿；L->next=U->next；free(U)；2．有一個長度為20的有序表采用二分查找方法進行查找，共有＿＿＿＿＿＿個元素的查找長度為3。3．采用冒泡排序對有n個記錄的表A按鍵值遞增排序，若L的初始狀態(tài)是按鍵值遞增，則排序過程中記錄的比較次數(shù)為＿＿＿＿＿。若A的初
7、始狀態(tài)為遞減排列，則記錄的交換次數(shù)為＿＿＿＿＿＿＿。4．在無頭結點的雙鏈表中，指針P所指結點是第一個結點的條件是＿＿＿＿＿＿。5．G為無向圖，如果從G的某個頂點出發(fā)，進行一次廣度優(yōu)先搜索，即可訪問圖的每個頂點，則該圖一定是＿＿＿＿＿圖。6．如果一個有向圖中沒有＿＿＿＿＿＿，則該圖的全部頂點可能排成一個拓撲序列。7．深度為8（根的層次號為1）的滿二叉樹有＿＿＿＿＿＿個葉子結點。8．將一棵有100個結點的完全二叉樹按層編號，則編號為49的結點X，其雙親PARENT（X）的編號為＿＿＿＿＿＿＿。9．設某閉散列表HT未滿，散列函數(shù)H（KEY）為鍵值第一字母在字母
8、表中的序號，處理沖突方法為線性探測法，請在下列算法劃線處填上適當內容，以實現(xiàn)按鍵
