《數(shù)據(jù)結(jié)構(gòu)》全真模擬試題與解答

1、全真模擬試題、單項選擇題(在每個小題的4個備選答案中，選出正確的答案，并將其號碼填在題后的括號內(nèi)。每小題 2分，共24分)1一個具有n個頂點的無向完全圖的邊數(shù)為() n(n+1)/2 n(n-1)/2 n( n-1) n(n +1)2在索引順序表中查找一個元素，可用的且最快的方法是() 用順序查找法確定元素所在塊，再用順序查找法在相應(yīng)塊中查找 用順序查找法確定元素所在塊，再用二分查找法在相應(yīng)塊中查找 用二分查找法確定元素所在塊，再用順序查找法在相應(yīng)塊中查找 用二分查找法確定元素所在塊，再用二分查找法在相應(yīng)塊中查找3 .若某線性表中最常用的操作是在最后一個元素之后插入一個元素和刪除最后一個 元素

2、，則采用()存儲方式最節(jié)省運算時間。雙鏈表容量足夠大的順序表單鏈表帶頭結(jié)點的雙循環(huán)鏈表4串是()一些符號構(gòu)成的序列一個以上的字符構(gòu)成的序列有限個字母構(gòu)成的序列有限個字符構(gòu)成的序列5堆排序在最壞情況下，其時間復(fù)雜性為() 0(nlog 2n) 0(n2) O(log 2n2) O(log 2n)6快速排序的記錄移動次數(shù)()比較次數(shù)，其總執(zhí)行時間為0(nlog2n)。大于大于等于小于等于小于7. 棵二叉樹有n個結(jié)點，要按某順序?qū)υ摱鏄渲械慕Y(jié)點編號，(號碼為1-n ),編號須具有如下性質(zhì)：二叉樹中任一結(jié)點V,其編號等于其左子樹中結(jié)點的最大編號加1。而其右子樹中結(jié)點的最小編號等于V的編號加1。試冋應(yīng)

3、按()遍歷順序編號。前根 中根8.3個結(jié)點可構(gòu)成(234后根 層次 )個不同形態(tài)的二叉樹。59對有n個記錄的有序表采用二分查找，其平均查找長度的量級為() O(log 2n) O(nlog 2n) O(n) O(n2)10 對有n個記錄的表按記錄鍵值有序的順序建立二叉樹，在這種情況下，其平均查 找長度的量級為() O(n) O(nlog 2n) O(1)(log 2n)11 .棧操作的原則是()先進(jìn)先出后進(jìn)先出棧頂插入棧頂刪除12 .設(shè)矩陣A是一對稱矩陣(a ij =aji ,1<=i,j<=8)，若每個矩陣元素占 3個單元，將其上三角部分(包括對角線)按行序為主序存放在數(shù)組B中，

4、B的首地址為1000,則矩陣元素a67的地址為() 1031 1093 1096 1032二、判斷題(判斷下列各題是否正確，正確在括號內(nèi)打“V” ，錯的打“x”。每小題1 分, 共10分)1 如果兩個串含有相同的字符，則這兩個串相等。()2. 數(shù)組可以看成線性結(jié)構(gòu)的一種推廣，因此可以對它進(jìn)行插入、刪除等運算。()3. 在索引順序表上實現(xiàn)分塊查找，在等概率查找情況下，其平均查找長度不僅與表 中元素個數(shù)有關(guān)，而且與每一塊中元素個數(shù)有關(guān)。（）4在順序表中取出第i個元素所花費的時間與i成正比。（）5在棧滿情況下不能作進(jìn)棧運算，否則產(chǎn)生“上溢”。（）6. 二路歸并排序的核心操作是將兩上有序序列歸并為一個

5、有序序列。（）7對任意一個圖，從它的某個頂點出發(fā)，進(jìn)行一次深度優(yōu)先或廣度優(yōu)先搜索，即可 訪問圖的每個頂點（）&二叉排序樹或者是一棵空二叉樹，或者是具有下列性質(zhì)的二叉樹：若它的左子樹 非空，則根結(jié)點的值大于其左孩子的值；若它的右子樹非空，則根結(jié)點的值小于其右孩子的值。（）9在執(zhí)行某個排序算法過程中，出現(xiàn)了排序碼朝著最終排序序列位置相反方向移動， 則該算法是不穩(wěn)定的。（）10.一個有向圖的鄰接表和逆鄰接表中表結(jié)點的個數(shù)一定相等。（）三、填空題（每空 2分，共26分）1. 在帶有頭結(jié)點的單鏈表L中，若要刪除第一個結(jié)點，則需執(zhí)行下列三條語句：;L->next=U->next ; f

6、ree（U）;2. 有一個長度為20的有序表采用二分查找方法進(jìn)行查找，共有個元素 的查找長度為3。3. 采用冒泡排序?qū)τ衝個記錄的表A按鍵值遞增排序，若L的初始狀態(tài)是按鍵值遞增，則排序過程中記錄的比較次數(shù)為。若A的初始狀態(tài)為遞減排列，則記錄的交換次數(shù)為。4. 在無頭結(jié)點的雙鏈表中，指針P所指結(jié)點是第一個結(jié)點的條件是。5. G為無向圖，如果從 G的某個頂點出發(fā)，進(jìn)行一次廣度優(yōu)先搜索，即可訪問圖的每個頂點，則該圖-圖。6如果一個有向圖中沒有，則該圖的全部頂點可能排成一個拓?fù)湫蛄小?. 深度為8 （根的層次號為1）的滿二叉樹有個葉子結(jié)點。8. 將一棵有100個結(jié)點的完全二叉樹按層編號，則編號為49的

7、結(jié)點X,其雙親PARENT（X） 的編號為。9. 設(shè)某閉散列表 HT未滿，散列函數(shù) H（ KEY為鍵值第一字母在字母表中的序號，處 理沖突方法為線性探測法，請在下列算法劃線處填上適當(dāng)內(nèi)容，以實現(xiàn)按鍵值第一字母的 順序輸出閉散列表中所有鍵值的算法。void prin tword（keytype HTm） for（i=1;i<=26;i+） j=i;while（） if （） printf（datatype ",HTj）;j=（j+1）% m; 10. 設(shè)有一個鏈隊，結(jié)點結(jié)構(gòu)為data|next , front為隊頭指針，rear為隊尾指針， 當(dāng)執(zhí)行入隊操作時需執(zhí)行下列語句：mal

8、loc（p） ; p->data=x; p->next=NULL ;?四、應(yīng)用題（共26分）1有向圖G的鄰接表如下圖所示，若刪去圖G中的邊V V3, V6>和V V4, V5>,試畫出修改后圖的鄰接表。（4分）頂點入度2有向圖如下圖所示，寫出以V1為出發(fā)點對圖進(jìn)行深度優(yōu)先搜索所得到的所有可能的訪問序列。（4分）3. 對于鍵值序列（49,38,65,97,76,13,27,50）,使用堆排序算法完成排序過程。要求：畫出初始堆（用二叉樹表示）。畫出分別輸出13,27后重建的兩個堆。（5分）4. 一個深度為d （根的層次號為1）的滿K叉樹有如下性質(zhì)：第d層上的結(jié)點都是葉子結(jié)點

9、，其余各層上的每個結(jié)點都有K棵非空子樹。如果從根這一層開始從左到右順序逐層對全部結(jié)點編號，且根結(jié)點的編號為1，問編號為n的結(jié)點有右兄弟的條件是什么？其右兄弟的編號是多少？（3分）5. 給定權(quán)值 5,10,12,15,30,40,構(gòu)造相應(yīng)的哈夫曼樹，要求寫構(gòu)造歩驟。（4 分）6. 已知一表為（Jan,Feb,Mar,Apr,May,Jun,Jul,Aug,Sep,Oct,Nov,Dec）,按表中順 序依次插入初始為空的二叉排序樹，要求：畫出建立的二叉排序樹。（4分）求出在等概率情況下查找成功的平均查找長度。（2分）五、設(shè)計題（共14分1. 設(shè)有一單鏈表L,結(jié)點結(jié)構(gòu)為data|next ，結(jié)點個數(shù)

10、至少3個，試畫出鏈表 L的結(jié)構(gòu)圖，并編寫算法判斷該單鏈表L中的元素是否成等差關(guān)系，即：設(shè)各元素值次為a1,a 2,a 3, -；a n,判斷 ai+1 -ai=ai-a i-1 是否成立，其中 i 滿足 2<=i<=n-1.（8 分）2. 設(shè)有一棵二叉樹以二叉鏈表作為存儲結(jié)構(gòu)，結(jié)點結(jié)構(gòu)為|lchild|data|rchild,其中data域中存放一個字符，設(shè)計一個算法按前根遍歷順序僅打印出data域為數(shù)字的字符（即0'<=data<= 9'） （6 分）全真模擬參考答案一、單項選擇題I. 2.3.45.6.78910. 對鍵值有序的、具有 n個記錄的表來

11、講，當(dāng)所建立的二叉排序樹是一棵 深度為n的單支樹時，在它上面的查找操作已經(jīng)退化為順序查找，所以其平均查找長 度的量級為0(n).II. 12. 按題意要求，將對稱矩陣A的上三角部分按行優(yōu)先進(jìn)行存放數(shù)組了B中，那么Bk與aij的對應(yīng)關(guān)系為：當(dāng) i<=j 時，k=(i-1)/2*(2*n-i+2)+j-i+1因此有：k=(6-1)/2*(2*8-6+2)+7-6+1=32故LOC (a67) =L0C(a11 )+(k-1)*l=1000+(32-1)*3=1093二、判斷題1. X 2. X 3. V 4. X 5. V 6. V 7. X 8. X 9. X 10.三、填空題1. U=L

12、 - > n ext2. 4。 分析：二分查找的過程可以用一棵有序樹來表示，該樹第三層上有4個結(jié)點，表示經(jīng)過三次比較查找成功的元素個數(shù)為4。3. n-1、n(n-1)/2 。分析：采用冒泡排序時，若初始時已經(jīng)自然有序，那么經(jīng)過一趟n-1次比較后，算法就自動終止了。若初始狀態(tài)為遞減排列，希望排序成遞增排列，則排序過程中比較一次，交換一次，總的比較、交換次數(shù)為n(n-1)/2 ，其中n-1為趟數(shù)，n/2為平均每趟的比較交換次數(shù)。4. p - > prior = NULL 。5. 連通6. 回路或環(huán)7. 28-1 = 27 = 1288. 249. HTj!=NULL 或 HTj不為空、

13、H(HTj)=l10 . rear - > next = p 、rear = p四、應(yīng)用題1.修改后的有向圖 G的鄰接表如圖所示。2. 1, 2, 5, 4, 3, 61, 3, 6, 4, 5, 21, 3, 5, 4, 6, 23 初始堆如圖所示。輸出13后重建的堆如圖所示。輸出27后重建的堆如圖所示。4分析：在滿k叉樹中，除編號為1的根結(jié)點外，其余結(jié)點依次為每k個結(jié)點擁有一個共同的雙親。比如：第二號一第k+1號結(jié)點的雙親是第1號結(jié)點；第k+2號一第2k+1號結(jié)點的雙親是第 2號結(jié)點；第2k+1號一第3k+1號結(jié)點的雙親是第 3號結(jié)點；從中可以看出，若編號為n,那么當(dāng)（n-1）%k

14、= 0 時，它一定是某個結(jié)點的最右邊的孩子，即它的右邊不會再有兄弟了。反之，當(dāng)（n-1）%k工0，它的右邊一定還有兄弟。答案：編號為n的結(jié)點有兄弟的條件是（n-1）%k工0,該點的右兄弟的編號是 n+1。5.哈夫曼樹的構(gòu)造過程如圖所示。1080101111111011001101在等概率情況下，查找成功的平均查找長度為(1+2+3+4+5+6+.+12)/12 = 7*12/12 = 7五、設(shè)計題1 單鏈表的結(jié)構(gòu)圖如圖設(shè)計題n9.1.2 所示。ala2anAn算法：int isrise (Iklist L)p = L -> next; b = p -> data- L -> data;while (p -> next != NULL)q =p -> n ext;if (q -> data- p -> data !=b)