北航自主招生考試題目

《北航自主招生考試題目》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。

1、第一部分??數(shù)據(jù)結(jié)構(gòu)一、是非判斷題（本題共10分，每小題各1分）（對于下面給出的論述，你認(rèn)為正確，請在小題后的括號中填入符號√，否則，填入符號×）1．對算法進行分析的目的是為了提高算法的質(zhì)量。（??）2．一般情況下，雙向鏈表比單向鏈表要占用更多的存儲空間。（??）3．將插入與刪除操作限制在表的一端的線性表被稱為堆棧。（??）4．完全二叉樹不一定是滿二叉樹，滿二叉樹一定是完全二叉樹。（??）5．利用二叉樹的前序遍歷序列和后序遍歷序列一定可以構(gòu)造出一棵二叉樹。（??）6．鄰接表中邊結(jié)點數(shù)目為偶數(shù)的圖一定是無向圖。（??）7．拓?fù)渑判虿皇菣z測有向

2、圖中是否存在回路的惟一方法。（??）8．采用折半查找的線性表只要求表中元素按值的大小有序排列就可以。（??）9．對具有n個元素的序列進行插入排序，排序的總趟數(shù)為n-1。（??）10．無論什么情況，快速排序法比其他排序法的時間效率都要高。（??）二、填空題（本題共15分，每小題各1分）1．若長度為n的線性表采用順序存儲結(jié)構(gòu)，當(dāng)不溢出時，在其第i個位置(1≤i≤n+1)插入一個新的數(shù)據(jù)元素之前需要依次移動（????）個元素的位置。2．在非空雙向循環(huán)鏈表中由q指的鏈結(jié)點前面插入一個p指的鏈結(jié)點的過程對應(yīng)的語句依次為：p->rlink=q;p->l

3、link=q->llink;q->llink=p;??（??????????）。（空白處為一條語句）3．在實際應(yīng)用中，當(dāng)堆棧的最大長度難以估計時，堆棧最好采用（????）存儲結(jié)構(gòu)。4．若a,b,c,d是初始為空的隊列的輸入序列，則此時該隊列的輸出序列是（????）。5．若具有n個結(jié)點的二叉樹采用二叉鏈表存儲，則鏈表中有（????）個指針域存放著NULL。6．已知二叉樹的前序遍歷序列為ABDCEFG，中序遍歷序列為DBCAFEG，其后序遍歷序列為（????）。7．采用“逐點插入法”建立序列(54,28,16,34,73,62,95,60,26

4、,43)的二叉排序樹后，在該二叉排序樹中查找到數(shù)據(jù)元素62時一共進行了（????）次元素之間的比較。8．在一個圖中，所有頂點的度數(shù)之和等于所有邊數(shù)的（????）倍。9．具有n個頂點的有向圖最多有（????）條邊。10．具有n個頂點的無向連通圖采用鄰接矩陣表示，鄰接矩陣中至少有（????）個非零元素。11．將數(shù)據(jù)元素2,4,6,8,10,12,14,16,18,20依次存放于一個一維數(shù)組中(設(shè)數(shù)組下標(biāo)從0開始)，然后采用折半查找方法查找元素12，被比較過的數(shù)組元素的下標(biāo)依次為（????）。12．若一個待散列存儲的線性表為K=(18,25,63

5、,50,42,32,9,45)，散列函數(shù)為H(k)=kMOD9，則與元素18發(fā)生沖突的元素有（????）個。13．若對序列(1,2,5,3,4)采用泡排序法按元素值從小到大進行排序，則整個排序過程中進行的元素之間的比較次數(shù)為（????）。14．若對序列(tang,deng,an,wang,shi,bai,fang,liu)采用選擇排序法按字典順序進行排序，則第三趟排序結(jié)束時序列的狀態(tài)是（????）。15．設(shè)有10000個元素組成的序列，希望盡快挑選出其中前10個(僅挑出前10個!)最大值元，在不改變已有算法結(jié)構(gòu)的前提下，插入排序法、快速排序

6、法、堆積排序法和泡排序法這4種內(nèi)排序算法中，最合適的是（????）。三、綜合題（本題共15分，每小題各5分）1．證明：具有n個結(jié)點的非空滿二叉樹，其葉結(jié)點的數(shù)目為(n+1)/2。2．已知某帶權(quán)連通圖采用鄰接矩陣存儲，鄰接矩陣以三元組表形式給出。鄰接矩陣下三角形部分的元素（不包括主對角線上元素）對應(yīng)的各三元組分別為)，μ)，(5,2,4)，(5,3,μ(2,1,7)，(3,1,6)，(3,2,8)，(4,1,9)，(4,2,4)，(4,3,6)，(5,1,(5,4,2)。請分別畫出該連通圖所有可能的最小生成樹。3．已知散列函數(shù)為H(key)=

7、(key%3)MOD11，散列地址空間為[0..10]，并且采用線性探測再散列法處理沖突。請畫出在初始為空的散列表中依次插入22,41,53,8,46,30,1,31,66以后散列表的狀態(tài)。四、算法設(shè)計題（本題10分）??結(jié)點的祖先定義為從根結(jié)點到該結(jié)點的所有分支上經(jīng)過的結(jié)點。??已知非空二叉排序樹采用二叉鏈表存儲結(jié)構(gòu)，鏈結(jié)點構(gòu)造為lchild??datarchild,??根結(jié)點指針為T。請寫一非遞歸算法,依次打印數(shù)據(jù)信息為item的結(jié)點的祖先結(jié)點。設(shè)結(jié)點的數(shù)據(jù)信息分別為整數(shù)，并且假設(shè)該結(jié)點的祖先結(jié)點存在。第二部分??C語言程序設(shè)計五、單項

8、選擇題（本題共20分，每小題各1分）1．一個C語言程序是由（????）。A．一個主程序和若干個子程序組成????B．函數(shù)組成C．若干過程組成??????????????D．若干子