數(shù)據(jù)結(jié)構(gòu)試卷(專升本).doc

數(shù)學(xué)系計算機科學(xué)與技術(shù)專業(yè)05級9班（專升本）數(shù)據(jù)結(jié)構(gòu)期末試題（A）20052006（一）一、 選擇題（每題2分 ，共20分）1. 下面程序段的時間復(fù)雜度為( )。 for(int i=0;im;i+) for(int j=0;jn;j+) aij=i*j; A、O(m2) B、O(n2) C、O(m*n) D、O(m+n) 2. 一個棧的輸入序列為1，2，3，4，下面哪一個序列不可能是這個棧的輸出序列().A、 1，3，2，4 B、2，3，4，1C、 4，3，1，2 D、3，4，2，1 3. 采用順序搜索方法查找長度為n的順序表時，搜索成功的平均搜索長度為（）。A、 nB、 n/C、 (n-1)/2D、(n+1)/2 4. 若一棵二叉樹具有10個度為2的結(jié)點，則該二叉樹的度為0的結(jié)點個數(shù)是（ ）A、 9B、 11C、 12D、不確定 5. 有64個結(jié)點的完全二叉樹的深度為（）（根的層次為1）。 A、8 B、7 C、6 D、5 6. 在已知待排序文件已基本有序的前提下，效率最高的排序方法是（ ） A、 直接插入排序 B、 直接選擇排序 C、 快速排序 D、 歸并排序 7. 在有n個葉子結(jié)點的哈夫曼樹中，其結(jié)點總數(shù)為（ ）。、 不確定 、2n 、2n+1 、2n-1 8. 廣義表( (A , B, E, F , G)的表尾是( )。A、(B, E , F, G) B、( )C、（A，B， E，F(xiàn)，G） D、不存在 9. 折半查找要求查找表中各元素的關(guān)鍵字值必須是（ ）排列。 、遞增或遞減 、遞增 、遞減 、無序 10. 設(shè)有一個N*N的對稱矩陣A，將其下三角部分以行為主序存入一個一維數(shù)組B中，A00存入B0中，那么第i行的對角元素Aii存入于B中的（ ）處。 A、（i+3）*i/2 B、(i+1)*i/2 C、(2N-i+1)*i/2 D、(2N-i-1)*i/2 二、 判斷題（每題2分，共20分）1. 有回路的有向圖不能完成拓?fù)渑判颉?（ ） 2. 一棵樹的度是指該樹中所有結(jié)點的度的和。（ ） 3. 在完全二叉樹中，一個結(jié)點若沒有左孩子，則它一定沒有右孩子。 （ ） 4. 滿二叉樹一定是完全二叉樹，并且完全二叉樹也一定是滿二叉樹。（ ） 5. 能夠在鏈接存儲的有序表上進行折半搜索，其時間復(fù)雜度與在順序表上相同。（ ）6. 棧與隊列都是限制存取點的表，只是它們的存取特征不一樣。（ ） 7. 直接選擇排序是一種不穩(wěn)定的排序方法 。（ ） 8. 雙循環(huán)鏈表中，任一結(jié)點的后繼指針均指向其邏輯后繼。 （ ） 9. 對任意一個圖，從它的某個頂點出發(fā)進行一次深度優(yōu)先或廣度優(yōu)先搜索遍歷可訪問到該圖的每個頂點。（ ） 10. 順序存儲的數(shù)組是一個隨機存取結(jié)構(gòu)。（ ） 三、 填空（每題2分，共20分）1. 數(shù)據(jù)結(jié)構(gòu)的抽象數(shù)據(jù)類型ADT可用三元組表示（D，S，P），其中D是數(shù)據(jù)對象，S是_，P是_。2. 已知順序存儲的循環(huán)隊列中，front，rear分別為隊頭、隊尾指針，MAX為隊列中存儲單元的最大個數(shù)，若當(dāng)隊列中僅有一個空閑單元時視為隊滿，則隊滿條件為_；一般情況下，隊列中元素個數(shù)可表示為_。3. 已知一棵度為5的樹中，2度、3度、4度、5度結(jié)點的個數(shù)依次為1，2，3，4個，則葉子個數(shù)為_。4. 假設(shè)有一個順序棧A，其中元素a1,a2,a3,a4,a5,a6依次進棧，如果已知六個元素出棧的順序是a2,a3,a4,a6,a5,a1,則此棧容量至少應(yīng)該為_。5. 順序表中邏輯上相鄰的元素的物理位置_緊鄰。單鏈表中邏輯上相鄰的元素的物理位置_緊鄰。6. 一個向量的第一個元素存儲地址是100，每個元素的長度為2，則第五個元素的地址是_。7. 在對于一組記錄（54，38，96，23，15，72，60，45，83）進行直接插入排序時，當(dāng)把第七個記錄60插入到有序表時，為尋找插入位置需比較_次。 四、 操作題（每題5分，共20分）1. 請寫出下面關(guān)鍵字序列的第一趟和第二趟快速排序(排序是從小到大)后的序列。49 38 65 97 76 13 27 49 2. 已知二叉樹的先序、中序和后序序列分別如下，但其中有一些模糊不清，請將其補完整。 先序序列BCEF 中序序列BDEAGH 后序序列DCGHA 3. 假設(shè)字符a,b,c,d,e,f的使用頻度分別是0.07,0.09,0.12,0.22,0.23,0.27。 (1)畫出這棵Huffman（哈夫曼）樹。 (2)寫出a,b,c,d,e,f的Huffman（哈夫曼）編碼。 4. 已知哈希函數(shù)為除余法（對7取余）, 關(guān)鍵字序列(49，10，16，79，13，20，76)，分別畫出利用線性探測法（表長為7）、鏈地址法處理沖突的哈希表。五、 寫算法（每題10分，共20分） 1. 線性鏈表就地逆置算法.int revLinkList(LinkList L)2. 已知兩個單向鏈表A=(a，b，c)；B=(d，e，f)，設(shè)計算法void MergeList（LinkList &A，