《東南大學(xué)1998數(shù)據(jù)結(jié)構(gòu)試題》由會員分享，可在線閱讀，更多相關(guān)《東南大學(xué)1998數(shù)據(jù)結(jié)構(gòu)試題（2頁珍藏版）》請?jiān)谘b配圖網(wǎng)上搜索。
1、東南大學(xué)1998數(shù)據(jù)結(jié)構(gòu)試題一:簡要回答下列問題(共40分)
1?設(shè)勝者樹(selectiontree)由k個記錄緩沖區(qū)和k-1個非葉結(jié)點(diǎn)構(gòu)成?概念上非葉結(jié)點(diǎn)表示其兩個子女中關(guān)鍵字較小者,而實(shí)際上非葉結(jié)點(diǎn)存放的是什么?(5分)2?索引順序存取方法(ISAM)中,主文件已按主關(guān)鍵字(primarykey)排序，為什么還需要主關(guān)鍵字索引?(6分)
3?一棵前序序列為1,2,3,4的二叉樹，其中序序列可能是4,1,2,3嗎？設(shè)一棵二叉樹的前序序列為1,2,3,4,5,6,7,8,9,其中序序列為2,3,1,5,4,7,8,6,9,試畫出該二叉樹?(7分)4?構(gòu)造最佳二叉檢索樹的前提條件是什么？在
2、動態(tài)情況下，一般AVL樹的查詢性能不如完
全二叉檢索樹的,為什么人們卻采用AVL樹呢？(8分)5?將兩個棧存入數(shù)組V[1..m]中應(yīng)如何安排最好？這時棧空棧滿的條件是什么？(6分)
6?已知無向圖GV(G)={1,2,3,4},E(G)={(1,2),(1,3),(2,3),(2,4),(3,4)},試畫出G的鄰接多表(AdjacencyMultilists),并說明若已知點(diǎn)i,如何根據(jù)鄰接多表找到與i相鄰的點(diǎn)j?(8分)
寫出用堆排序(heapsort)算法對文件F=(12,3,15,30,9,28)進(jìn)行排序時，初始堆及以后每挑好一個元素重新調(diào)整后堆的狀態(tài)，并指出這里的堆和敗者樹(tr
3、eeofloser)的一個主要區(qū)別.(8分)
..
設(shè)數(shù)組A存放一n位二進(jìn)制數(shù)，試說明下列算法X的功能?假設(shè)無溢出，算法X的最壞時間復(fù)雜度是什么？分析它的平均時間復(fù)雜性?(8分)typeNum=array[1..n]of[0..1];procedureX(varA:Num);varj:integer;
begini:=n;whileA[i]=1do
beginA[i]:=0;
i:=i-1;end;
A[i]:=1;end;
四:
下面是一改進(jìn)了的快速分類算法:
1 procedureqsort1(varlist:afile;m,n:integer);(設(shè)list[m].ke
4、y=k;repeatj:=j-1untillist[j].keyv=k;
6 ifi=j;
7 interchange（list[m],list[j]）;ifn-j>=j-m
8 thenbeginqsort1（list,m,j-1）;m:=j+1;
5、endelsebeginqsort1（list,j+1,n）;n:=j-1;end
9 end;（ofwhile）end;問:（共20分）
1. 將第9,10行中的>=,<=分別改成>,<行嗎?為什么?（5分）該排序算法穩(wěn)定否,舉例說明.（5分）
2. 對輸入文件（22,3,30,4,60,11,58,18,40,16）,列表表示該文件在每次調(diào)用qsort1時的狀態(tài)及相應(yīng)m,n的值.（5分）
4?若輸入文件有n個記錄,簡要說明支持qsortl遞歸所需最大?？臻g用量（設(shè)一層遞歸用一個單位?？臻g）.（5分）五:
給定AOE網(wǎng)絡(luò)各事件（標(biāo)號仁n）的ee,le值和鄰接表，寫一算法求該AOE的所有活動（用相應(yīng)邊的兩端點(diǎn)表示）的關(guān)鍵度（criticality）.（10分）
六:
給出中序線索樹的結(jié)點(diǎn)結(jié)構(gòu),并畫出一個具有頭結(jié)點(diǎn)和六個樹結(jié)點(diǎn)的中序線索樹,試寫一算法在不使用棧和遞歸的情況下前序遍歷一中序線索樹,并分析它的時間復(fù)雜性.（18分）
東南大學(xué)1998數(shù)據(jù)結(jié)構(gòu)試題
