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

朽木易折，金石可鏤。千里之行，始于足下。第頁/共頁北京航天航空大學(xué)2000年碩士研究生入學(xué)考試程序設(shè)計與數(shù)據(jù)結(jié)構(gòu)一、挑選題(2’x10)1.在非空雙向循環(huán)鏈表中q所指的結(jié)點前插入一個由p所指的點的過程依次為：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.若對n階對稱矩陣A以行序為主序方式將其下三角形的元素(包括主對角線上所有元素)依次存放于一維數(shù)組B中，則在B中決定aij(i<j)的位置k的關(guān)系為_________。(A)(B)

(C)(D)

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