北航數(shù)據(jù)結(jié)構(gòu)與程序設(shè)計(jì)真題 2013年北航991真題及答案

1、2013年“數(shù)據(jù)結(jié)構(gòu)與C程序設(shè)計(jì)”(代碼991)試題一、單項(xiàng)選擇題（本題共一、單項(xiàng)選擇題（本題共20分，每小題各分，每小題各2分）分）1對于長度為n的線性表，建立其對應(yīng)的單鏈表的時間復(fù)雜度為()。AO(1)；BO(log2n)；O(n)；DO(n2)。2一般情況下，在一個雙向鏈表中插入一個新的鏈結(jié)點(diǎn)，()。A需要修改4個指針域內(nèi)的指針；B需要修改3個指針域內(nèi)的指針；C需要修改2個指針域內(nèi)的指針；D只需要修改1個指針域內(nèi)的指針。3假設(shè)用單

2、個字母表示中綴表達(dá)式中的一個運(yùn)算數(shù)(或稱運(yùn)算對象)，并利用堆棧產(chǎn)生中綴表達(dá)式對應(yīng)的后綴表達(dá)式。對于中綴表達(dá)式AB(CDE)，當(dāng)從左至右掃描到運(yùn)算數(shù)E時，堆棧中的運(yùn)算符依次是()。(注：不包含表達(dá)式的分界符)A；B(；C；(。4若某二叉排序樹的前序遍歷序列為50204030806070，則后序遍歷序列為()。A30402050706080；B30402070608050；C70608050304020；D70608030402050。5分

3、別以6381257對應(yīng)葉結(jié)點(diǎn)的權(quán)值構(gòu)造的哈夫曼(Huffman)樹的深度為()。A6；B5；C4；D3。6下列關(guān)于圖的敘述中，錯誤的是()。A根據(jù)圖的定義，圖中至少有一個頂點(diǎn)；B根據(jù)圖的定義，圖中至少有一個頂點(diǎn)和一條邊(弧)；C具有n個頂點(diǎn)的無向圖最多有n(n1)2條邊；D具有n個頂點(diǎn)的有向圖最多有n(n1)條邊(弧)。7若在有向圖G的拓?fù)湫蛄兄校旤c(diǎn)vi在頂點(diǎn)vj之前，則下列4種情形中不可能出現(xiàn)的是()。AG中有??；BG中沒有弧；CG

4、中有一條從頂點(diǎn)vi到頂點(diǎn)vj的路徑；DG中有一條從頂點(diǎn)vj到頂點(diǎn)vi的路徑。8下列關(guān)于查找操作的敘述中，錯誤的是()。A在順序表中查找元素可以采用順序查找法，也可以采用折半查找法；B在鏈表中查找結(jié)點(diǎn)只能采用順序查找法，不能采用折半查找法；C一般情況下，順序查找法不如折半查找法的時間效率高；D折半查找的過程可以用一棵稱之為“判定樹”的二叉樹來描述。9在一棵m階B樹中，除根結(jié)點(diǎn)之外的任何分支結(jié)點(diǎn)包含關(guān)鍵字的個數(shù)至少是()。Am21；Bm2；

5、Cm21；Dm2。10若對序列(4938659776132749’)進(jìn)行快速排序，則第一趟排序結(jié)束(即確定了第1個分界元素的最終位置)時，序列的狀態(tài)是()。A(132749’3849769765)；B(13382749’49769765)；C(133849’2749977665)；D(133849’2749769765)。二、填空題二、填空題(本題共本題共20分，每小題各分，每小題各2分)1非空線性表在采()存儲結(jié)構(gòu)的情況下，刪除表的一

6、個數(shù)據(jù)元素平均需要移動表中近一半元素的位置。2將一個長度為n的單鏈表鏈接到一個長度為m的單鏈表后面，該算法的時間復(fù)雜度用大O符號表示為()。四、算法設(shè)計(jì)題（本題四、算法設(shè)計(jì)題（本題15分）分）假設(shè)長度為n的順序表A[1..n]中每個數(shù)據(jù)元素為一整數(shù)，請寫出按照下列思想將表中數(shù)據(jù)元素按值從小到大進(jìn)行排序的算法：第1趟排序?qū)⒆钚≈翟胤旁贏[1]中，最大值元素放在A[n]中；第2趟排序?qū)⒋涡≈翟胤旁贏[2]中，次大值元素放在A[n1]中；

7、……，依此下去，直至排序結(jié)束。五、填空題五、填空題(本題共本題共20分，每小題各分，每小題各2分)1已知某等比數(shù)列的第一項(xiàng)a1為1，公比為3，下列程序的功能是輸出該數(shù)列中小于1000的最大項(xiàng)an及其對應(yīng)的n。請?jiān)诔绦虻目瞻滋?符號處)填入合適內(nèi)容，使程序完整。main()intn=1a=1q=3while(1)a=aqnif(a=1000)printf(“n=%da=%dn”n1)2下列遞歸函數(shù)FUNC2的功能是判斷整型數(shù)組a[n]是否

8、為遞增數(shù)組，即判斷數(shù)組的元素是否按值從小到大排列。若是一個遞增數(shù)組，則函數(shù)返回true，否則，函數(shù)返回false。請?jiān)诤瘮?shù)的空白處(符號處)填入合適內(nèi)容，使函數(shù)完整。boolFUNC2(inta[]intn)if(n==1)returntrueif(n==2)returnreturn3下列程序的功能是主函數(shù)調(diào)用FUNC3函數(shù)求方陣a中兩條對角線上元素之和。請?jiān)诔绦虻目瞻滋?符號處)填入合適內(nèi)容，使程序完整。#defineN10voidF