北航自主招生考試題目

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

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

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

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

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

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

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

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

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