南京理工大學(xué)877計(jì)算機(jī)專業(yè)基礎(chǔ)c考研模擬試卷四及解析

1、專業(yè)課復(fù)習(xí)資料（最新版） 專業(yè)課復(fù)習(xí)資料（最新版）封面考試點(diǎn) www.kaoshidian.com 2 7.排序算法中，第一趟排序后，任一元素都不能確定其最終位置的算法是（ D ） A.選擇排序 B.快速排序 C.冒泡排序 D.插入排序 8.已知四個(gè)元素 a,b,c,d 依次進(jìn)棧，進(jìn)棧過程中可出棧，下面那一種出棧順序是不正 確的( C ) A.a,d,c,b

2、B.b,c,d,a C.c,a,d,b D.c,d,b,a 9.設(shè)某棵二叉樹的中序遍歷序列為 ABCD，前序遍歷序列為 CABD，則后序遍歷該二叉樹得到序列為（ A ） 。 A.BADC B.BCDA C.CDAB D.CBDA 10.設(shè)有序順序表中有 n 個(gè)數(shù)據(jù)元素，則利用二分查找法查找數(shù)據(jù)元素 X 的最多比較次數(shù)不超過（ A ） 。 A.log2n+1 B.log2n-1 C.log2n D.log2(n+1)

3、 二、填空題 二、填空題(本大題共 本大題共 5 小題，每小題 小題，每小題 2 分，共 分，共 10 10 分) 請?jiān)诿啃☆}的空格中填上正確答案。錯填、不填均無分。 請?jiān)诿啃☆}的空格中填上正確答案。錯填、不填均無分。 1.設(shè)有向圖 G 中有向邊的集合 E={，，，，}，則該圖的一種拓?fù)湫蛄袨開___________________。 (1，4，3，2) 2.一棵含 999 個(gè)結(jié)點(diǎn)的完全二叉樹的深度為_____。 10 3.在 16 個(gè)

4、記錄的有序順序表中進(jìn)行二分查找，最大比較次數(shù)是___________。 Log2n + 1 4.己知散列表表長 m=11，散列函數(shù) h(key)=key％11，表中存有三個(gè)關(guān)鍵字 15，27，39，其余地址為空，若采用線性探查法處理沖突，則關(guān)鍵字為 60 的結(jié)點(diǎn)保存的地址是_________。 7 5.一組字符(a,b,c,d)在文中出現(xiàn)的次數(shù)分別為(7，6，3，5)，字符＇d＇的哈夫曼編碼 的長度為______。 2 三 、簡答題（

5、本大題共 、簡答題（本大題共 2 小題，每小題 小題，每小題 5 分，共 分，共 10 10 分） 分） 1.給定表（15，11，8，20，14，13） ，試按元素在表中的順序?qū)⑺鼈円来尾迦胍豢贸跏紩r(shí)為空的二叉排序樹， 畫出插入完成后的二叉排序樹， 并判斷該二叉排序樹是否為平衡二叉排序樹，若為非平衡二叉排序樹，將它調(diào)整為平衡二叉排序樹。 2.已知圖所示，用普里姆（prim）算法從頂點(diǎn) A 開始求最小生成樹。在算法執(zhí)行之初，頂點(diǎn)的集合 U