北京航天航空大學(xué)2000年數(shù)據(jù)結(jié)構(gòu)與程序設(shè)計(jì)

朽木易折，金石可鏤。千里之行，始于足下。第頁/共頁北京航天航空大學(xué)2000年碩士研究生入學(xué)考試程序設(shè)計(jì)與數(shù)據(jù)結(jié)構(gòu)一、挑選題(2’x10)1.在非空雙向循環(huán)鏈表中q所指的結(jié)點(diǎn)前插入一個(gè)由p所指的點(diǎn)的過程依次為：rlink(p)←q；llink(p)←llink(q)；llink(q)←p；_________。(A)rlink(q)←p(B)rlink(llink(q))←p(C)rlink(llink(p))←p(D)rlink(rlink(p))←p2.若對(duì)n階對(duì)稱矩陣A以行序?yàn)橹餍蚍绞綄⑵湎氯切蔚脑?包括主對(duì)角線上所有元素)依次存放于一維數(shù)組B中，則在B中決定aij(i<j)的位置k的關(guān)系為_________。(A)(B)

(C)(D)

3.某堆棧的輸入序列為a，b，c，d，下面的四個(gè)序列中，_________不可能是它的輸出序列。(A)a，c，b，d(B)b，c，d，a(C)c，d，b，a(D)d，c，a，b4.深度為h的滿m叉數(shù)的第k層有_________個(gè)結(jié)點(diǎn)。(1≤k≤h)(A)mk-1(B)mk-1(C)mh-1(D)mh-15.具有10個(gè)葉結(jié)點(diǎn)的二叉樹中有_________個(gè)度為2的結(jié)點(diǎn)。(A)8(B)9(C)10(D)116.要連通具有n個(gè)頂點(diǎn)的有向圖，至少需要_________條邊。(A)n-1(B)n(C)n+1(D)2n7.已知有向圖G=(V，E)，其中V={v1，v2，v3，v4，v5，v6，v7}，

E={<v1，v2>，<v1，v3>，<v1，v4>，<v2，v5>，<v3，v5>，<v3，v6>，

<v4，v6>，<v5，v7>，<v6，v7>}，G的拓?fù)湫蛄惺莀________。(A)v1，v3，v4，v6，v2，v5，v7(B)v1，v3，v2，v6，v4，v5，v7(C)v1，v3，v4，v5，v2，v6，v7(D)v1，v2，v5，v3，v4，v6，v78.若尋找每個(gè)記錄的概率均等，則在具有n個(gè)記錄的延續(xù)順序文件中采用順序?qū)ふ曳▽ふ乙粋€(gè)記錄，其平均尋找長度ASL為_________(A)(B)(C)(D)n9.下面關(guān)于B樹和B+樹的講述中，不準(zhǔn)確的是_________(A)B樹和B+樹都是平衡的多分樹。(B)B樹和B+樹都可用于文件的索引結(jié)構(gòu)。(C)B樹和B+樹都能有效地支持隨機(jī)檢索。(D)B樹和B+樹都能有效地支持順序檢索。10.下面給出的四種排序主意中，排序過程中的比較次數(shù)與排序主意無關(guān)的是_________。(A)挑選排序法(B)插入排序法(C)迅速排序法(D)堆積排序法二、(10’)有實(shí)現(xiàn)同一功能的兩個(gè)算法A1和A2，其中A1的時(shí)光復(fù)雜度為T1=O(2n)，A2的時(shí)光復(fù)雜度為T2=O(n2)，僅就時(shí)光復(fù)雜度而言，請(qǐng)?jiān)敿?xì)分析這兩個(gè)算法哪一個(gè)好。三、(5’+10’+10’+5’)為建立一個(gè)具有n份檔案的檔案庫需要設(shè)計(jì)如下數(shù)據(jù)結(jié)構(gòu)：所有檔案存儲(chǔ)在一個(gè)動(dòng)態(tài)存儲(chǔ)的雙向循環(huán)鏈表中，每份檔案占用一個(gè)地址延續(xù)的存儲(chǔ)塊成為該鏈表中的一個(gè)結(jié)點(diǎn)，囫圇鏈表為一個(gè)順序文件，取名為dossier(檔案)，同時(shí)分離建立兩個(gè)索引，其中一個(gè)為稠密索引，取名為dense，另一個(gè)是表長為m的雜湊表索引，取名為bucket，該雜湊表采用鏈地址法處理矛盾。上述兩種索引中都分離存儲(chǔ)在每一份檔案的存儲(chǔ)地址。1.請(qǐng)分離畫出dossier、dense、bucket的結(jié)構(gòu)暗示圖。2.分離設(shè)計(jì)出dossier、dense、bucket的數(shù)據(jù)結(jié)點(diǎn)的結(jié)構(gòu)，即為了滿意檔案的插入、刪除、尋找的操作，每個(gè)結(jié)點(diǎn)須要的數(shù)據(jù)項(xiàng)的名稱及其作用。3.針對(duì)上述結(jié)構(gòu)，用簡明的文字分離說明所有可能的尋找主意(尋找路徑)。4.分離給出每一種尋找主意在尋找勝利時(shí)的平均尋找長度。四、(10’)已知num為無符號(hào)十進(jìn)制整數(shù)，請(qǐng)寫一非遞歸算法，該算法依次輸出num對(duì)應(yīng)的r進(jìn)制的各位數(shù)字。要求算法中用到的堆棧采用線性鏈表存儲(chǔ)結(jié)構(gòu)。(1<r<10)五、(10’)已知長度為n的線性表A采用順序存儲(chǔ)結(jié)構(gòu)，請(qǐng)寫一時(shí)光復(fù)雜度為O(n)、空間復(fù)雜度為O(1)的算法，該算法刪除線性表中所有值為item的數(shù)據(jù)元素。(O(1)表示算法的輔助空間為常量)六、(10’x2)設(shè)有一