1、南京理工大學課程考試試卷（學生考試用）課程名稱：數據結構學分：3大綱編號062204試卷編號：考試方式：閉卷滿分分值：100考試時間：120分鐘組卷日期：2007年6月4日組卷教師（簽字）張宏審定人（簽字）王樹梅學生班級：計算機學院05級、選擇題（2*20=40分）不是算法的基本特征A）可行性B）長度有限C）在有限時間內完成D）確定性某算法的時間復雜度為0（n2）,表明該算法的A）問題規模是n2B）執行時間等于n2C）執行時間與n2成正比D）問題規模與n2成正比C）不可能是1D）定是1設n個元素進棧序列是P/P2,P3，,p，其輸出序列是1,2,3,n,若p3=3，則的值為A）可能是2B）一定

2、是2鏈表不具備的特點是B）插入、刪除不需要移動元素D）所需空間與其長度成正比A）可隨機訪問任一結點C）不必事先估計存儲空間最不合適用作鏈隊的鏈表。A）只帶隊首指針的非循環單鏈表B）只帶隊首指針的循環雙鏈表C）只帶隊尾指針的循環雙鏈表D）只帶隊尾指針的循環單鏈表設二維數組A610,每個數組元素占用4個字節，若按行優先順序存放時，數組元素A35的存儲地址為1000，則A00的存儲地址是A）872B）860C）868D）864以下不是堆的序列是。A）100，85，98，77，80，60，82，40，20，10，66B）100，98，85，82，80，77，66，60，40，20，10C）10，20，

3、40，60，66，77，80，82，85，98，100D）100，85，40，77，80，60，66，98，82，10，20&一棵完全二叉樹上有1001個結點，其中葉子結點的個數A）250B）500C）505D）501無向圖的鄰接矩陣是一個矩陣。A）對稱B）零C）上三角D）對角對于含有n個結點的帶權連通圖，它的最小生成樹是指圖中任意一個。A）有n-1條權值最小的邊構成的子圖B）有n-1條權值之和最小的邊構成的子圖C）有n-1條權值最小的邊構成的連通子圖D）有n個頂點構成的邊的權值之和最小的連通子圖有n個結點的線索二叉樹上含有的線索數為A）2nB）nTC）n+1D）n若一個有向圖中的頂點不能排成

4、一個拓撲序列，則可斷定該有向。A）是個有根有向圖B）含有多個入度為0的頂點C）是個強連通圖D）含有頂點數目大于1的強連通分量關鍵路徑是指AOE網絡中A）從源點到匯點的最長路徑B）從源點到匯點的最短路徑C）最長的回路D）最短的回路對有18個元素的有序表R0至R17，則二分查找R2的比較序列的下標為A）0、1、2B）8、4、1、2C）8、4、2D）8、3、1、2有k個相同的數據，若用線性探測法把這k個數據存入哈希表，至少要進行次探查A）k-1B）kC）k+1D）k（k+1）/2在一棵二叉排序樹上查找值為35的數據，以下比較的數據序列正確的為A）28、36、18、46、35B）18、36、28、46

5、、35C）46、28、18、36、35D）46、36、18、28、35快速排序在情況下最不利于發揮其長處A）要排序的數據量太大B）要排序的數據中含有多個相同的值C）要排序的數據已基本有序D）要排序的數據個數是奇數稀疏矩陣采用壓縮存儲的目的主要是為了。A）表達變得簡單B）對矩陣元素的存取變得簡單C）去掉矩陣中的多余元素D）減少不必要的存儲空間的開銷哈希函數構造的原則是：它的函數值應概率的取其值域的每一個值。A）最大B）最小C）同等D）平均樹的遍歷策略可分為先序遍歷和后序遍歷（也有稱為中序遍歷的）；二叉樹的基本遍歷有二種，即先序、中序和后序。這里，我們把由樹轉化得到的二叉樹叫做這棵樹對應的二叉樹。

6、結論：“樹的序遍歷序列與其對應的二叉樹的遍歷序列相同”是正確的A）先先B）后（中）后C）先中D）先后二、填空題（20分，其余每空2分）n,下面是對無向圖的一種操作，其中g是無向圖的鄰接矩陣，n是圖的頂點數，頂點標號為1到n，vi是一個全程變量的一維數組，初值為全0,下面的類C/C+算法tt對圖做什么操作（1）。voidtr（gn,v0）/v0是圖的頂點號，值范圍為1到n之間的整數visit（v0）;/visit是一個函數，完成對給定圖頂點的訪問viv0T=l;for（i=0;in;i+）if（!vii&gv0-1i）tr（g,i）;voidtt(gn,n)for(i=0;in;i+)vii=0

7、;for(i=0;in;i+)if(!vii)tr(g,i+l);求最短路徑的Dijkstra算法若用鄰接矩陣表示圖，在有100個頂點時如果時間是t,則在400個頂點時，時間大約是（2）。已知一棵完全二叉樹共有892個結點，則該二叉樹的高度是（3），葉子數是（4），度為1的結點數是（5），最后一個非葉結點的序號是_（）。（注：二叉樹結點按自然數順序從1開始從上到下，同一層從左到右編號）原始數據為（34、90，30，50，23，11，10，100,46）按快速排序算法一趟劃分后，數據的排列是（7）。求最小生成樹有（8）和（9）兩個算法。在一棵5階B_樹中，高度是5（葉子層不算），則這棵B樹至少有

8、（10）個結點、簡答題（26分）1.（6分）按13、24、37、90、53的次序，a）畫出建立平衡二叉樹的過程并注明平衡類型（3分）b）畫出建立3階B_樹（又稱2-3樹）的過程（3分）2.3.4.5.6.號是(6)o（13分）有一個AOE網如下:a=710a=2a=8a=710a=614a=13a=48a11=4a=3a=3a=10a=1041213a=41a=55a=29（1）畫出該AOE網的鄰接表示意圖（3分）（2）求出所有事件的最早發生時間與最遲發生時間（4分）（3）列出所有關鍵活動（3分）（4）把上圖看成無向圖（忽略弧的方向），求出一棵最小生成樹，生成樹邊權之和為多少？（生成樹不需要畫出，3分）（4分）有數據13、24、37、90、53,試建立一棵Huffman樹并計算WPL。（4分）（3分）簡述分塊查找的數據組織方式，查找過程。（3分）四、算法設計（用類-C/類-C+描述）（14分）（7分）完成一個二叉樹拷貝的遞歸算法treecopy（d,s）。其中s是源二叉樹，d是目的二叉樹。（7分）設在n