完整word版12年南大金陵學(xué)院數(shù)據(jù)結(jié)構(gòu)期末考試

1、南京大學(xué)金陵學(xué)院期末試卷20112012學(xué)年第一學(xué)期學(xué)號數(shù)據(jù)結(jié)構(gòu)期末考試試題09 1.2姓名成績14選擇題（共15題，每題2分，計 30在下列各題 A）、B）、C）、D）四個選項中, 號中。選擇一個正確的選項，將其字母編號填寫在括iJ+1 亠 一 n、B) 2= O(2 )D) O( n2) O(2n)(1)下列哪個選項是錯誤的？(A) 2n+n3 = O(2n)C)22n = O(2n)（2）在下列4個選項中，聲明一個向量數(shù)組的是A) vector vex ;B)vector vec(10);C) vector vex10;D)vector vex(10, a);（3）下列每組代碼利用標(biāo)準(zhǔn)容

2、器list建立一個表,確的？然后逐個刪除表中的元素。 其中那組代碼是正A)list lst;B)list lst;for( int i = 0;i5;i+) lst .pu sh_back(i); for( int i = 0;i5;i+) lst .pu sh_back(i);while( !lst.e mp ty() ) lst.erase( p);list:iterator p;list:iterator p=Ist.begi n();for( p=Ist.begi n() ; p!=lst.e nd() ; p+) lst.erase( p);C)list lst;D)list lst

3、;for( int i = 0;i5;i+) lst .pu sh_back(i); for( int i = 0;i5;i+) lst .pu sh_back(i);list:iterator p=Ist.begi n(); list:iterator p=Ist.begi n();while( p!=lst.e nd() ) lst.erase( p); while (p!=lst.e nd() ) p=lst.erase( p);4的字符串,（4）字符a、b、c、d依次進入一個棧，按所有可能的次序出棧后組成一個長度是 至多可以組成多少個不同的字符串？（）A) 4B)14C) 24D) 1

4、6（5）設(shè)有如下定義的數(shù)組const intm=20 ;T Qm;Q存儲一個環(huán)形隊列。中第一個元素的實際位置是/ T為隊列元素的類型quelen是隊列中元素的個數(shù),（ ）back是實際隊尾元素的位置，隊列A) back+m-quele nB) back -quelenC) ( back+m -quelen +1) % mD) ( m -back +quelen) % mC+標(biāo)準(zhǔn)模板庫的“表”容器（list）是用雙向鏈表實現(xiàn)的，對這種實現(xiàn)，下列敘述正確的（A)元素的物理順序與元素的邏輯順序一定相同B)C)一個表元素所占用的存儲空間只用來存儲表元素的值，不含其他附加信息 可以隨機地訪問元素D)可以

5、高效地進行插入和刪除操作設(shè)一個長度為10的排好序的序列存儲在數(shù)組 法查找與k相等的元素，若查找 不成功，(8)(9)(10)中有A) 3設(shè)一棵樹的度是A) 4B) 44，其中度為0、1、B) 3F面關(guān)于二叉樹的敘述正確的是A)B)C)D)任何二叉樹至少有一個結(jié)點二叉樹的度是2C) 5D) 62、3和4的結(jié)點個數(shù)分別是C) 2D)）。在二叉樹中，度為 0的結(jié)點個數(shù)等于度為 2的結(jié)點個數(shù)加 在任何一棵完全二叉樹中，沒有度為1的結(jié)點。& 4、 2、 1 和 X, x 是一棵二叉樹含有25個結(jié)點，這些結(jié)點要么是葉，要么是有兩棵非空子的子樹，此二叉樹 ）個非葉結(jié)點。A) 11B) 12C) 13D) 1

6、4int arr10中。對一個給定的值 k,用二分 至少需要比較多少次？（）。（11）設(shè)二叉樹根結(jié)點的層次為0，棵深度（高度）為k的滿二叉樹和同樣深度的完全二叉樹分別有f個結(jié)點和c個結(jié)點，下列關(guān)系式錯誤的是（）(12)B) c fC) f = 2k+1 - 1D) c vv ; II 二維向量 vv執(zhí)行循環(huán)語句：for ( int i = 1 ;i (i , 2*i );后，向量 vv的元素vv1是值：count=(3)對下列函數(shù) mystery ( int n )，參數(shù)n是2的正整數(shù)幕(n=2k , k=1 ,2,3，)，用參數(shù)n表示 函數(shù)執(zhí)行結(jié)束時的cou ntintmystery ( i

7、ntn)int x = 2 ,count = 0 ;while ( x n )x *= 2 ;count +retur n count(4)設(shè)棧s和隊列Q的初始狀態(tài)為空，元素 ei, e2, 出棧后立即進入隊列，若 6個元素出隊列順序是 62, S的最大長度(size)是多少？e3, e4, e5和e6依次通過棧s, 個元素 5, e6, e4, e3, 8,在操作過程中，?？梢愿咝У卦趦啥诉M行插入和刪除操作的隊列稱為隊列。廣義表 D=(), (e), ( a, (b, c, d)，則:D的長度是 , D的表頭Head(D)是_D的表尾 Tail(D)是二叉樹根結(jié)點的左子樹有tl、t2和t3,

8、與森林對應(yīng)的設(shè)森林F有3棵樹，第一、第二和第三棵樹的結(jié)點個數(shù)分別是 個結(jié)點。(8)在一棵中序線索樹中，一個結(jié)點P有兩棵非空的子樹，它的中序前驅(qū)結(jié)點的度至多是(10)對一棵二叉樹進行先序和中序遍歷的結(jié)果分別是G(9)在n個結(jié)點的完全二叉樹中，葉結(jié)點的個數(shù)是先序序列：ADB中序序列：BGD則這棵二叉樹根結(jié)點的左子女和右子女分別是解答題(共5題，每題5分，計25分)請按照題意解答下列各題。(1)函數(shù)func()對表alist進行什么操作?temp latevoid func( list& alist )list: iterator iter = alist.begi n();while ( iter

9、 != alist.e nd()alist .pu sh_fr ont( * iter );函數(shù)Bsearch ()在數(shù)組中查找否則返回-1。實現(xiàn)代碼如alist.erase ( iter+) ;/ 本句也可改用 p=alist.erase(iter);a叫的長度為n,元素已按值遞增的順序排好序,(2)設(shè)整型數(shù)組與給定值target相等的元素，若查找成功，返回元素在數(shù)組中的位置, 下：int Bsearch (int const *arr , int n , const int& target )bool found = false ;int first = 0, last = n-1, m

10、;while ( first mid ) first = melse last = m ;if ( found )returnelse return -1 ;查找成功，返回元素在數(shù)組中的位置查找失敗，返回-1無任是查找成功或查找失敗，函數(shù)是否總能正確地工作？如果不能，請舉例說明。(3)刪除一棵二叉搜索樹中的一個結(jié)點，然后再插入這個結(jié)點，所得的結(jié)果二叉樹是否與原先 的二叉樹一定相同？舉例說明你的結(jié)論。 設(shè)被排序的初始序列為 26, 28, 41,57, 14, 10, 35, 22 ，用快速排序方法進行排序，以第一個元素26作為劃分的基準(zhǔn)，寫成第一次劃分后所得到的兩個序列。本題不宜作為考題，因為

11、劃分的具體算法不同會得到不同結(jié)果。(5) 假設(shè)一則電文中僅出現(xiàn)6個不同的字母a, b，c, d，e和f，每個字母在電文中出現(xiàn)的頻率分別是3，10，12，7，4和20。試為這6個字母設(shè)計哈夫曼編碼。四.編程題(共2題，第(1 )題5 分，第題10分，計 15 分)heade-a1a2(1)對下列單鏈表aiai+1an寫一個遞歸函數(shù)，反向輸出單鏈表中的結(jié)點，即依次輸出 單鏈表的結(jié)點類型定義如下：struct nodean,an-1, ,a2, aint data ;node* next ;；函數(shù)的原型： void Print( Node* head);/函數(shù)寫在下面若序列 ho, hi, h2,h

12、n-1 中的元素滿足下列關(guān)系:n -22hi A h+i并且hi 21+2( i = 0, 1 , 2 ,.,則該序列是一個堆(heap)。設(shè)向量A有n個元素，若它的前n-1個元素組成的序列 ao, a1, a2,an-2 已經(jīng)是一個堆，編寫函數(shù) Push_heap (,它將向量A的n個元素組成的序列 ao , a1 , a2,ai-2，an-1 變成堆。函數(shù)原型是void Push_heap ( vectorvint& A );2008.1.2 考試A卷答案:選擇題（每題2分）(2) C(4) B(5) C(2) D(8) D(9) C(10) B(11) B(12) D(13) B(14)

13、 B(15) D二、填空題（每題3分）(11)操作雙端（或雙向）隊列3,(3) COUnt = long 2門-1Head(D)=() ，Tail(D)=( (e)，(4)4(a，(b，c，d)t1-1(8) 1n或,n +1或f22 .2 I(9) n -(10)解答題（每題5分）(1)逆轉(zhuǎn)一個表函數(shù)有時不能正確地工作，例如：序列1,5,8,10， 若要杳找元素10(3)不一定相同。例如:刪除10,然后再插入10,將得到下列不同的二叉查找樹:【22 ， 10， 141 【57,41, 28, 35, 26】(5)構(gòu)造哈夫曼樹如下:be6個字母的哈夫曼編碼分別是:a=1010b=00c=01d=100d=100e=1011f = 11(4)編程題voidPrint ( node* head )if ( head )Prin t(head-n ext);voidcoutdata ;pu sh_hea p ( vector &A ) int n = A.size()