一九九六年上海海運(yùn)學(xué)院攻讀碩士學(xué)位研究生入學(xué)考試試題

1、一九九六年上海海運(yùn)學(xué)院攻讀碩士學(xué)位研究生入學(xué)考試試題數(shù)據(jù)結(jié)構(gòu)一 判斷下列敘述的正確性，將判斷的結(jié)果填在括號(hào)中，正確的填，不正確的填×。（本題滿分10分，每小題1分）。 1 順序存貯方式的優(yōu)點(diǎn)是存儲(chǔ)密度大，且插入刪除效率高。 （ ） 2 棧和隊(duì)列的存儲(chǔ)方式，既可以是順序方式，有可是鏈?zhǔn)椒绞健?（ ） 3 數(shù)組是同類型的集合。 （ ） 4 負(fù)載因子是散存儲(chǔ)的一個(gè)重要參數(shù)，它反映散列表的裝滿程度。 （ ） 5 用鏈表(llink-rlink) 存儲(chǔ)包含幾個(gè)結(jié)點(diǎn)的二叉樹，結(jié)點(diǎn)的2n個(gè)指針區(qū)域中有n-1個(gè)空指針。 （ ） 6 一棵一般樹的結(jié)點(diǎn)的前序遍歷和后序遍歷分別于它相應(yīng)二叉樹的結(jié)

2、點(diǎn)前序遍歷和后序遍歷是一致的。 （ ） 7 線索二叉樹的優(yōu)點(diǎn)是便于在中序下查找前驅(qū)結(jié)點(diǎn)和后繼結(jié)點(diǎn)。 （ ） 8 用鄰接矩陣存儲(chǔ)一個(gè)圖時(shí)，再不考慮壓縮存儲(chǔ)的情況下，所占用的存儲(chǔ)空間大小與圖中結(jié)點(diǎn)個(gè)數(shù)有關(guān)，而與圖的邊數(shù)無(wú)關(guān)。 （ ） 9 快速排序和歸并排序在最壞情況下的比較次數(shù)都是O(nlog2n). （ ） 10 任意查找樹(二叉分類樹)的平均查找時(shí)間都小于用順序查找法查找同樣結(jié)點(diǎn)的線性表的平均查找時(shí)間。 （ ）二 從供選擇的答案中選出應(yīng)填入下列敘述中_內(nèi)的正確答案。 （本題滿分25分，每小題5分） 1 有一個(gè)二維數(shù)組A0.8,1.5,每個(gè)數(shù)組元素用相鄰的四個(gè)字節(jié)存儲(chǔ)，存儲(chǔ)器按字節(jié)編址，假設(shè)存儲(chǔ)

3、數(shù)組元素A0,1的第一個(gè)字節(jié)的地址是0，存儲(chǔ)數(shù)組A的最后一個(gè)元素的第一個(gè)字節(jié)的地址是_。若按行存儲(chǔ)，則A3,5和 A5,3的第一個(gè)字節(jié)的地址是 _ 和_。若按列存儲(chǔ)，則A7,1和A2,4的第一個(gè)字節(jié)的地址是_和_。 供選擇的答案：A- E: 28 44 76 92 108 116 132 176 184 188 2 只能在一端刪除結(jié)點(diǎn)，另端插入結(jié)點(diǎn)的線索表是_ ；只能在端點(diǎn)對(duì)結(jié)點(diǎn)進(jìn)行刪除，插入操作的線性表是_,所有插入和刪除均在一端進(jìn)行，而另端不允許插入或刪除的線性表是_,其中的結(jié)點(diǎn)已按中序次序分類好的樹是_,其中每個(gè)結(jié)點(diǎn)的左右子樹的高度差都不大于1樹是_; 所有后件數(shù)小于2的結(jié)點(diǎn)均在最下面二

4、層的樹是_。供選擇的答案：A- F: (1) 隊(duì)列 (2) 數(shù)組 （3）十字鏈表 （4）雙向隊(duì)列 （5） 循環(huán)鏈表（6）棧 （7） 雙向鏈表 （8） 有序樹 （9） 豐滿二叉樹 （10）完全二叉樹 （11）平衡樹 （12） 分類二叉樹 3 設(shè)T是正則二叉樹（完全二叉樹），它具有6片樹葉，那么樹T的高度最多可以是_， 最小可以是_;樹的內(nèi)結(jié)點(diǎn)數(shù)是_.如果T是哈夫曼樹（Hoffman）最優(yōu)樹，且各片樹葉的權(quán)（頻率）分別是1，2，3，4，5，6，則最優(yōu)樹T的非葉結(jié)點(diǎn)的權(quán)之和是 _;權(quán)為1的樹葉的高度是_. 注：樹的根結(jié)點(diǎn)高度為1。 供選擇的答案： A,B,C,E:(1)7 (2)5 (3)6 (4)

5、4 (5)3 D: (1)27 (2)30 (3)45 (4)51 (5)61 4 如下圖所示的網(wǎng)絡(luò)表示的工程中，這個(gè)工程由_個(gè)作業(yè)構(gòu)成，各個(gè)作業(yè)所需天數(shù)由箭頭先上的樹子給出。另外，各作業(yè)都可能縮短一天，而且所需要的費(fèi)用由（ ）中的數(shù)字給出。 這項(xiàng)工程需要_天可以全部完成，關(guān)鍵路徑是_。 同時(shí)，為了將工程所用的天數(shù)縮短一天，可以將作業(yè)_縮短一天，這樣可以用最低費(fèi)用縮短工期，這是以關(guān)鍵路徑為 _ ,將它已經(jīng)可能少的費(fèi)用在縮短一天時(shí)，則可以將作業(yè)_縮短。 供選擇的答案： A,B: (1) 8 (2) 9 (3) 10 (4) 11 (5) 13 (6) 14 (7) 15 (8) 16 (9) 2

6、0 (10) 23 C,E: (1) 1-2-4-5-6-7-8 (2) 1-2-4-6-7-8 (3) 1-2-5-6-7-8 (4) 1-3-5-6-7-8 (5)1-2-7-8 (6) 1-2-4-6-7-8和1-2-5-6-7-8 (7) 1-2-4-6-7-8和1-2-4-5-6-7-8 (8) 1-2-4-5-6-7-8和1-2-5-6-7-8 (9) 1-3-5-6-7-8和1-3-7-8 D,F: (1) (2,4) (2) (2,5) (3) (3,5) (4) (3,7) (5) (4,6) (6) (5,6) (7) (7,8) (8) (2,4)和(2,5) (9) (

7、2,4)和(4,6) (10) (2,4)和(5,6)5 某順序存儲(chǔ)的表格，其中有90000個(gè)元素，以按關(guān)鍵項(xiàng)的值的上升順序排列?，F(xiàn)假定對(duì)各個(gè)元素進(jìn)行查找的概率是相同的，并且各個(gè)元素的關(guān)鍵項(xiàng)的值皆不相同。用順序查找法時(shí)，平均比較次數(shù)是_,最大比較次數(shù)是_?，F(xiàn)把90000個(gè)元素按排列順序劃分成若干組，使每組有g(shù)個(gè)元素(最后一組可能不是g個(gè))。查找時(shí)，先從頭一組開始，通過(guò)比較各組的最后一個(gè)元素的關(guān)鍵項(xiàng)的值，找到欲查找的元素所在的組，然后再用順序查找法找到欲查找的元素。在這種查找法中，使總的平均比較次數(shù)最小的g是_，此時(shí)的平均比較數(shù)是_。當(dāng)g的值大于等于90000時(shí)，此方法的查找次數(shù)接近于_。供選擇

8、的答案： A,B:(1) 2500 (2) 30000 (3)4500 (4)9000 C,D:(1) 100 (2)200 (3) 300 (4) 400 E:(1) 快速分類法 (2) 斐波那契查找法 (3) 二分法 (4) 順序查找法三 試用過(guò)程或函數(shù)使現(xiàn)有序表的兩種操作：INSERT DELETE 有序表的表示法是基于如下結(jié)構(gòu) (1)數(shù)組 (2)指針(鏈表) (本題滿分16分)四 假設(shè)一個(gè)二叉樹的兩種遍歷如下：前序：ABFGCHDEIJLK 中序：FGBHCDILJKEA(1) 畫出這棵二叉樹及它的中序線索樹；(2) 寫出在中序線索樹的情況下，找到結(jié)點(diǎn)N的前驅(qū)結(jié)點(diǎn)的算法INORDER-

9、PRIOR(N,X)(本題滿分10分，第一小題4分，第二小題6分)五 已知長(zhǎng)度為12 的表(Jan,Feb,Mar,Apr,May,Jun,Jul,Aug,Sep,Oct,Nov,Dec)(1) 試按表中元素的順序依次插入一棵初始為空的分類二叉樹，是畫出插入完成之后的分類二叉樹，并計(jì)算其在等概率查找情況下，查找成功的平均查找長(zhǎng)度。(2) 試用以下兩種方法構(gòu)造兩個(gè)Hash表，Hash函數(shù)H(K)=i/2,其中i為關(guān)鍵字K中第一個(gè)字母在字母表中的序號(hào)， 表示取整數(shù)。1 用線性探測(cè)開放定址法處理沖突(散列地址空間為0-16)2 用鏈地址法處理然后分別求出這兩個(gè)Hash表在等概率查找情況下，查找成功的

10、平均查找長(zhǎng)度。(本題滿分15分，第一小題5分，第二小題10分)六 下面是冒泡排序算法，請(qǐng)閱讀并完成該程序，并回答以下問(wèn)題：PROCEDURE bubblesort (r,n) BEGIN i:=1; m:=n-1; flag:=1; while (i<=_)and(flag=_) do begin flag:=_; for j:=1 to m do if rj.key>rj+1.key then begin flag:=_; t:=rj; rj:=rj+1; rj+1:=t end; i:=i+1;m:=m-1 end; end.1 請(qǐng)?jiān)谏厦鏅M線上填上適當(dāng)?shù)恼Z(yǔ)句，完成該算法程序。2

11、 設(shè)計(jì)標(biāo)志flag的作用是什么？3 該算法結(jié)點(diǎn)的最大比較次數(shù)和最大移動(dòng)次數(shù)是多少？4 該分類算法穩(wěn)定嗎？（本題滿分12分，每小題3分）七 （本題滿分12分）閱讀下列程序說(shuō)明和PASCAL程序，把應(yīng)填入其中處字句寫在答案的對(duì)應(yīng)欄內(nèi)。程序說(shuō)明：本程序根據(jù)輸入的等價(jià)對(duì)，形成并輸出相應(yīng)的等價(jià)類。等價(jià)對(duì)（a,b）表示等價(jià)元a與b等價(jià)，若存在等價(jià)對(duì)（a,b）和(b,c)(或c,b)則表示a,b,c屬于同一個(gè)等價(jià)類。算法分為兩個(gè)部分：（1） 由輸入的等級(jí)對(duì)建立若干個(gè)鏈表，數(shù)組元素Seg(i)用來(lái)指向與I有直接等價(jià)關(guān)系的等價(jià)元鏈表。當(dāng)輸入的等價(jià)對(duì)中第一個(gè)元素小于或等于0時(shí)，表示輸入結(jié)束。例如，輸入的等價(jià)對(duì)是1

12、，5；4，2；7，11；9，10；8，5；7，9；4，6；8，12；12，1時(shí)，建立的數(shù)組Seg是（2） 掃描數(shù)組元素segi，i=1,2,輸出相應(yīng)的等價(jià)類程序： program equo (input,output);const nmax=50;type pointer=node; node=record data:1nmax; link:pointer end;var seg:array1nmax of pointer; out:array1nmax of Boolean; I,j,n:integer; X,y,top:pointer; Done:Boolean;Begin Writerl

13、n(input the number n=); Read(n); For I:=1 to n do Begin(1) outI:=true end; writeln(input the equivnlent pairs); readln(I,j); while I>0 do begin new(x); x.data:=j; x.link:=segI; segI:=x; new(x); x.data:=I;x.link:=segj; segj:=x;readln(I,j); end; for I:=1 to n do if (2) then writeln(A nem class,I); outI:=false;(2) top:=nil;done:=false;repeat while x&