南京理工大學(xué)課程考試試卷學(xué)生考試用

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

2、是2鏈表不具備的特點(diǎn)是B）插入、刪除不需要移動(dòng)元素D）所需空間與其長(zhǎng)度成正比A）可隨機(jī)訪問(wèn)任一結(jié)點(diǎn)C）不必事先估計(jì)存儲(chǔ)空間最不合適用作鏈隊(duì)的鏈表。A）只帶隊(duì)首指針的非循環(huán)單鏈表B）只帶隊(duì)首指針的循環(huán)雙鏈表C）只帶隊(duì)尾指針的循環(huán)雙鏈表D）只帶隊(duì)尾指針的循環(huán)單鏈表設(shè)二維數(shù)組A610,每個(gè)數(shù)組元素占用4個(gè)字節(jié)，若按行優(yōu)先順序存放時(shí)，數(shù)組元素A35的存儲(chǔ)地址為1000，則A00的存儲(chǔ)地址是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&一棵完全二叉樹(shù)上有1001個(gè)結(jié)點(diǎn)，其中葉子結(jié)點(diǎn)的個(gè)數(shù)A）250B）500C）505D）501無(wú)向圖的鄰接矩陣是一個(gè)矩陣。A）對(duì)稱B）零C）上三角D）對(duì)角對(duì)于含有n個(gè)結(jié)點(diǎn)的帶權(quán)連通圖，它的最小生成樹(shù)是指圖中任意一個(gè)。A）有n-1條權(quán)值最小的邊構(gòu)成的子圖B）有n-1條權(quán)值之和最小的邊構(gòu)成的子圖C）有n-1條權(quán)值最小的邊構(gòu)成的連通子圖D）有n個(gè)頂點(diǎn)構(gòu)成的邊的權(quán)值之和最小的連通子圖有n個(gè)結(jié)點(diǎn)的線索二叉樹(shù)上含有的線索數(shù)為A）2nB）nTC）n+1D）n若一個(gè)有向圖中的頂點(diǎn)不能排成

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

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

6、結(jié)論：“樹(shù)的序遍歷序列與其對(duì)應(yīng)的二叉樹(shù)的遍歷序列相同”是正確的A）先先B）后（中）后C）先中D）先后二、填空題（20分，其余每空2分）n,下面是對(duì)無(wú)向圖的一種操作，其中g(shù)是無(wú)向圖的鄰接矩陣，n是圖的頂點(diǎn)數(shù)，頂點(diǎn)標(biāo)號(hào)為1到n，vi是一個(gè)全程變量的一維數(shù)組，初值為全0,下面的類C/C+算法tt對(duì)圖做什么操作（1）。voidtr（gn,v0）/v0是圖的頂點(diǎn)號(hào)，值范圍為1到n之間的整數(shù)visit（v0）;/visit是一個(gè)函數(shù)，完成對(duì)給定圖頂點(diǎn)的訪問(wèn)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個(gè)頂點(diǎn)時(shí)如果時(shí)間是t,則在400個(gè)頂點(diǎn)時(shí)，時(shí)間大約是（2）。已知一棵完全二叉樹(shù)共有892個(gè)結(jié)點(diǎn)，則該二叉樹(shù)的高度是（3），葉子數(shù)是（4），度為1的結(jié)點(diǎn)數(shù)是（5），最后一個(gè)非葉結(jié)點(diǎn)的序號(hào)是_（）。（注：二叉樹(shù)結(jié)點(diǎn)按自然數(shù)順序從1開(kāi)始從上到下，同一層從左到右編號(hào)）原始數(shù)據(jù)為（34、90，30，50，23，11，10，100,46）按快速排序算法一趟劃分后，數(shù)據(jù)的排列是（7）。求最小生成樹(shù)有（8）和（9）兩個(gè)算法。在一棵5階B_樹(shù)中，高度是5（葉子層不算），則這棵B樹(shù)至少有

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