中科院計算機技術研究所1999年碩士生入學試題 數據結構與程序設

中科院計算機技術研究所1999年碩士生入學試題 數據結構與程序設計

一、選擇題(20 分 每空2分)
1.___的遍曆仍需要棧的支持。
1.前序線索樹 2.中序線索樹 3.後序線索樹

2.若度為m的哈夫曼樹中,其葉結點個數為n,則非葉結點的個數為___。
1.n-1 2.[n/m]-1 3.[(n-1)/(m-1)] 4.[n/(m-1)]-1 5.[(n+1)/(m+1)]-1

3.最優二叉樹(哈夫曼樹)、最優查找樹均為平均查找路徑長度∑wh最小的樹,其中對
最優二叉樹,n表示___,對最優查找樹,n表示___; 構造這兩種樹均___。
1.結點數 2.葉結點數 3.非葉結點數 4.度為二的結點數 5.需要一張n各關鍵字的有序
表 6.需要對n個關鍵字進行動態插入 7.需要n個關鍵字的查找概率表 8.不許要任何前提

4.對於前序遍曆與中序遍曆結果相同的二叉樹為___; 對於前序遍曆與後序遍曆結果相
同的二叉樹為___。
1.一般二叉樹 2.隻有根結點的二叉樹 3.根結點無左孩子的二叉樹 4.根接點無右孩子的
二叉樹 5.所有結點隻有左子樹的二叉樹 6所有結點隻有右子樹的二叉樹

5.m路B+樹是一棵___, 其結點中關鍵字最多為___個, 最少為___個。
1.m路平衡查找樹 2.m路平衡索引樹 3.m路trIE樹 4.m路鍵樹 5.m-1 6.m 7 m+1 8.[m/2]-1
9.[m/2] 10.[m/2]+1

二、填空題(10 分,每空一分)
1.對於給定的n個元素,可以構造出的邏輯結構有___,___,___,___四種。

2.具有n個關鍵字的B-樹的查找路徑長度不會大於___。

3.克魯斯卡爾算法的時間複雜度為___, 他對___圖較為適合。

4.深度為k(設根的層數為1)的完全二叉樹至少有___個結點, 至多有___個結點, k和結點
數n之間的關係是___。

三、問答題(10 分,每題5分)

1.一棵非空的有向樹中恰有一個頂點入度為0，其他頂點入度為1.但一個恰有一個頂點
的入度為0， 其他頂點入度為一的有向圖卻不一定是一棵有向樹。請舉例說明之。

2.若有n個元素以構成一個小根堆，那麼如果增加一個元素為K(n+1)，請用文字簡要 說
明你如何在log2(n) 的時間內將其重新調整為一個堆？

四、閱讀下述程序,指出程序的輸出。(10 分)

void g(int**);
..............................