數(shù)據(jù)結構試卷及答案1

1、1 .算法分析的目的是(C )。A.找出數(shù)據(jù)結構的合理性B.研究算法中輸入和輸出的關系C分析算法的效率以求改進D.分析算法的易懂性和文檔性2 . ( B )是具有相同特性數(shù)據(jù)元素的集合，是數(shù)據(jù)的子集。A.數(shù)據(jù)符號B.數(shù)據(jù)對象C數(shù)據(jù)D.數(shù)據(jù)結構3 .用鏈表表示線性表的優(yōu)點是( C)。A.便于隨機存取B.花費的存儲空間比順序表少C便于插入與刪除D.數(shù)據(jù)元素的物理順序與邏輯順序相同4 .輸入序列為(A,B,C,D)不可能的輸出有(D )。A.(A,B,C,D)B. (D,C,B,A) C. (A,C,D,B) D . (C,A,B,D)5 .在數(shù)組表示的循環(huán)隊列中，front、rear分別為隊列的頭

2、、尾指針，maxSize為數(shù)組的最大長度，隊滿的條件是(B )。A. front=maxSizeB. (rear+1)%maxSize=frontC. rear=maxSizeD. rear=front6 .設有串 t='I am a good student ',那么 Substr(t,6,6)= ( D )。A. studentB. a good sC. goodD. a good7 .設有一個對稱矩陣 A,采用壓縮存儲方式，以行序為主序存儲a11為第一個元素，其存儲地址為1,每個元素占一個地址空間，則 a85地址為( B )。D. 408.已知廣義表 LS=(A,(B,C

3、,D),曜用head和tail函數(shù)，取出LS中原子b的運算(C )。A. Gethead(Gethead(LS)B. Gettail(Gethead(LS)C. Gethead(Gethead(Gettail(LS) D. Gethead(Gettail(LS)9 .若已知一棵二叉樹先序序列為ABCDEFG中序序列為 CBDAEGF則其后序序列為(A )。A. CDBGFEAB. CDBFGEAC. CDBAGFED. BCDAGFE10 .下列存儲形式中，(C )不是樹的存儲形式。A雙親表示法B.左子女右兄弟表示法C廣義表表不法D.順序表不法11 .對待排序的元素序列進行劃分，將其分為左、右

4、兩個子序列，再對兩個子序列施加同樣的排序操作，直到子序列為空或只剩一個元素為止。這樣的排序方法是(C)。A.直接選擇排序B.直接插入排序C.快速排序D.起泡排序12 .采用折半查找方法進行查找，數(shù)據(jù)文件應為( A ),且限于()。A.有序表順序存儲結構B.有序表鏈式存儲結構C隨機表順序存儲結構D.隨機表鏈式存儲結構13 .就平均查找速度而言，下列幾種查找速度從慢至快的關系是( B )A順序折半哈希分塊B.順序分塊折半哈希C分塊折半哈希順序D.順序哈希分塊折半14 .執(zhí)行下面程序段時，執(zhí)行 S語句的次數(shù)為(D )for(int I=1;I<=n;I+)for(int j=1;j<=I

5、;j+)S;A. n2B. n2/2C. n(n+1) D. n(n+1)/215 .串是一種特殊的線性表，其特殊性體現(xiàn)在( B)A.W以順序存儲B.數(shù)據(jù)元素是一個字符C可以鏈接存儲D.數(shù)據(jù)元素可以是多個字符16 .樹的基本遍歷策略分為先根遍歷和后根遍歷；二叉樹的基本遍歷策略可分為先序遍歷、中序遍歷和后 序遍歷。結論(A)是正確的。A.樹的先根遍歷序列與其對應的二叉樹的先序遍歷序列相同B.樹的后根遍歷序列與其對應的二叉樹的先序遍歷序列相同C樹的先根遍歷序列與其對應的二叉樹的中序遍歷序列相同D以上都不對17 .由五個分別帶權值為 9, 2, 3, 5, 14的葉子結點構成的一棵哈夫曼樹，該樹的帶

6、權路徑長度為(CbA. 60B. 66C. 67D. 5018 . 一棵二叉樹有67個結點，這些結點的度要么是 0,要么是2。這棵二叉樹中度為 2的結點有(A )個A. 33B. 34C. 32D. 3019 .有一個有序表為1,3,9,12,32,41,45,62,75,77,82,95,100,當二分查找值82為的結點時，(C )次比較后查 找成功。A. 1B. 2C. 4D. 820.若有文件的關鍵字序列為：265 301 751 129937 863 742 694 076 438,以下為二路歸并排序過程。第二趟為:（D ）A.265 301 129 751 863 937 694 7

7、42 076 438B.076 129 265 301 438 694 742 751 863 937C.129 265 301 694 742 751 863 937 076 438D.129 265 301 751 694 742 863 937 076 438二、填空題（本大題共 6小題，每空2分，共12分；答案填在下表內(nèi)）1算法是指令的有限序列，其中每一條指令表示一個或多個操作，此外，一個算法還具有五個重要特性，它們分別是有窮性 、確定性_、 可行性、有零或多個輸入和有一或多個輸出。2算法優(yōu)劣的五個標準是正確性、可使用性、可讀性、健壯性、二效率 。3有n個球隊參加的足球聯(lián)賽按主客場制進

8、行比賽，共需進行一n （ n-1） 場比賽。4設有串t='I am a student ' , s='good',那么 Concat（t,s）= 'I am a student good' , Substr（t,8,7）= 'student'_ 。5在解決計算衽主機與打印機之間速度不匹配時通常設置一個打印數(shù)據(jù)緩沖區(qū)，主機將要輸出的數(shù)據(jù)依次寫入該緩沖區(qū)，而打印機從該緩沖區(qū)中取出數(shù)據(jù)打印。該緩沖區(qū)應該是一個隊列 結構，其主要特點是先進先出 。6 廣義表（a）,a）的表頭是（a）,表尾是 （a） 。三、判斷題（對的打,錯的打“x”。每小

9、題1分，共10分;答案填在下表內(nèi)）1數(shù)據(jù)的邏輯結構與數(shù)據(jù)元素本身的內(nèi)容和形式無關。（，）2三個結點的二叉樹和三個結點的樹一樣，都具有三種不同的形態(tài)。（X ）3中序序列和后序序列相同的二叉樹為：空樹和缺右子樹的單支樹。（，）4對于兩棵具有相同關鍵字集合而形狀不同的二叉排序樹，中序遍歷后得到的關鍵字排列順序相同。（V ）5 序列30, 40, 50, 15, 25, 35, 38, 10是堆。（X ）6對于無向圖的生成樹，從同一頂點出發(fā)所得的生成樹相同。（X ）7 若設哈希表長 m=14,哈希函數(shù) H（key）=key%11,表中已有 4 個結點。addr（15）=4 addr（38）=5 add

10、r（61）=6addr（84）=7其余地址為空，如用二次探測再散列處理沖突，關鍵字為 49的結點的地址是9。（ M ） 8一個深度為k的，具有最少結點數(shù)的完全二叉樹按層次，（同層次從左向右）用自然數(shù)依此對結點編號則，則編號最小的葉子的序號是2k-2+1 ；編號是i的結點所在的層次號是log2 i|+1。（log2 i|表示向上取整（根所在的層次號規(guī)定為1層）。（V ）9在一棵7階B樹中，一個結點中最多有6棵子樹，最少有3棵子樹。（X ）10算法可以沒有輸入，但是必須有輸出。（M ）四、畫出樹的孩子兄弟表示法示意的樹或森林。（4分）五、要求題（本大題共 2小題，共12分）設關鍵字的輸入序列為4,

11、 5, 7, 2, 1, 3, 61. （8分）從空樹開始構造平衡二叉樹，畫出每加入一個新結點時二叉樹的形態(tài)，若發(fā)生不平衡，指明需 做的平衡旋轉類型及平衡旋轉的結果。（4分）上面的數(shù)據(jù)作為待排序的數(shù)據(jù)，寫出用快速排序進行一趟劃分后的數(shù)據(jù)序列六、按要求做題（本大題共 2小題，共12分）1畫出無向圖G的鄰接表存儲結構，根據(jù)鄰接表存儲結構寫出深度優(yōu)先和廣度優(yōu)先遍歷序列。（7分）2用prim算法求下圖的最小生成樹，寫出最小生成樹的生成過程。（5分）七、算法分析設計題(本大題共 5小題，共30分)1 .寫出程序段的功能，并給出一個測試用例(一個輸入數(shù)據(jù)和一個輸出結果)(5分)。void conversi

12、on()(Stack s;int n;SElemType e;initstack(s);printf("Please input number:");scanf( "%d" ,&n);while(n)push(s,n%8);n=n/8; while(!stackempty(s)pop(s,e);printf( "d” ,e); 2 .下面是一個使用棧 stack實現(xiàn)對二叉樹進行非遞歸先根遍歷的函數(shù)，請在標號處填寫合適的語句。(每空1 分，共5分)程序：Void preorder(bitree *T)bitree *stackm;int

13、top;if(T!=NULL)top=1;stacktop=(1);while( (2)p=stacktop;top-;printf( “d” ,p->data);if(p->rchild!=NULL) (3); stacktop=p->rchild;if( (4) ) top+; (5) ;)(1)(4)3.請在標號處填寫合適的語句。完成下列程序。（每空1分，共5分）int Binary_Search(S_TBL tbl, KEY kx) /*在表tbl中查找關鍵碼為kx的數(shù)據(jù)元素,若找到返回該元素在表中的位置，否則，返回0 */int mid , flag=0；low=1

14、 ； high=length；while( (1) &!flag )/*非空，進行比較測試*/mid= ；if(kx<mid.key) (3)；else if(kx>mid.key) else flag= ；break； )return flag;(1)(4)4.下面是一個采用直接選擇排序方法進行升序排序的函數(shù)，請在標號處填寫合適的語句。分）程序：（每空1分，共5Void seletesort(int An,int n)int i,j,t,minval,minidx;for(i=1;i<=n-1;i+)minval=Ai+1;(1)for(j=i+2;j<=n;

15、j+)if(2) (3) ; minidx=j;if(4) t=Ai+1;(5) Aminidx=t; (1)(3)(4)5試寫出求有向無環(huán)圖的關鍵路徑算法的設計思路（10分）四、畫出樹的孩子兄弟表示法示意的樹或森林。（4分）五、要求題（本大題共 2小題，共12分）1.454322.一趟劃分后的數(shù)據(jù)序列3 1六、按要求做題（12分）DFS遍歷序歹U v1 v2 v4 v8 v5 v3 v6 v7(或 1 2 4 8 5 3 6 7)BFS遍歷序歹U v1 v2 v3 v4 v5 v6 v7 v8（或 1 2 3 4 5 6 7 8）（5分，如有錯誤酌情扣分。）鄰接點的順序可以不同，可以有不同的

16、深度優(yōu)先和廣度優(yōu)先遍歷序列。七、算法設計題(30分)1 .將十進制轉化成八進制數(shù)(5分) 測試用例：輸入10輸出122 (5分，每空1分)(1) T(2) top>0 top+(4) p->lchild!=NULL(5) stacktop=p->lchild3 (5分，每空1分)(1) low<=high(2) (low+high)/2(3) high=mid-1(4) low=mid+11(5) (5分，每空1分)(1) minidx=i+1 minval>Aj minval=Aj i!=j Ai+1=Aminidx5 (10分，不同答案，酌情得分) 輸入頂點和

17、弧信息，建立其鄰接表計算每個頂點的入度對其進行拓撲排序排序過程中求頂點的 Vei將得到的拓撲序列進棧按逆拓撲序列求頂點的Vli計算每條弧的ei和li,找出ei=li的關鍵活動第2學期數(shù)據(jù)結構試卷A選擇題(本大題共15小題，每題2分，共30分；答案填在下表內(nèi))1 .從一個長度為100的順序表中刪除第30個元素時需向前移動(A)個元素A、70 B、71C、69D、302 .在一個具有N個單元的順序表中，假定以地址低端(即下標為1的單元)作為底，以top作為頂指針，則當做進 棧處理時top變化為D。A、top 不變B、top=0C、top=top-1D、top=top+13 .從一個具有n個結點的單

18、鏈表中查找其值等于x結點時在查找成功情況下，則平均比較_B_個結點。A、nB、n/2 C (n-1)/2 D、(n+1)/24 .在一個單鏈表中，若要刪除p指針所指結點的后繼結點，則執(zhí)行(B)A p-> next; p-> next=p-> next-> next;B、 p-> next=p-> next-> next;C p=p-> next;D、 p=p-> next->>next;5 .在一個鏈隊列中，假定front和rear分別為隊首和隊后指針，則進行插入S結點的操作時應執(zhí)行 _C,A、front-> next=s

19、 ； front=s ；B、s-> next=rear;rear=s；C、rear-> next=s;rear=s；D、s-> next=front;front=s ；6 .在一棵度為3的樹中度為3的結點數(shù)為3個，度為2的結點數(shù)為1個，度為1的結點數(shù)為1個，那么度為0 的結點數(shù)為_C_個A、6B、7 C、 8D、97 .假定一棵二叉樹的結點數(shù)為33個，則它的最小高度為_C_最大高度為A、 4,33B、5,33C、6,33 D、6,328 .在一棵完全二叉樹中，若編號為i的結點有右孩子，則該結點的右孩子編號為_B_OA 2i B 2i+1 C 2i-1 D i/29 .在一個有

20、向圖中，所有頂點的入度之和等于所有弧數(shù)和_A_倍。A1 B 2 C3 D 410 .對于一個具有N個頂點的圖，若用鄰接矩陣表示，則該矩陣的大小為_D_OA NB (N-1)2 C (N+1)2D、N211 .已知一個圖如圖所示，在該圖的最小生成樹中各邊上數(shù)值之和為_B_。D、33B、v1v2v3v4v5v6(A)C、v1v4v2v3v6v5D、v1v2v4v6v3v513.二維數(shù)組M的元素是4個字符（每個字符占一個存儲單元）組成的串，行下標i的范圍從0到4,列下標j的范圍從0到5,M按行存儲時元素 M24的起始地址與 M按列存儲時元素（D）的起始地址相同。A、m24B、M42C、M31 D、M

21、3114 .具有6個結點的無向圖至少應有（A）條邊才能保證是連通圖。5B、6C、7D、8(A)15 .采用鄰接表存儲的圖的深度優(yōu)先遍歷類似于二叉樹的A先序遍歷B中序遍歷 C.后序遍歷D.按層遍歷1.數(shù)據(jù)結構是研究數(shù)據(jù)元素之間抽象化的相互關系和這種關系在計算機中的存儲結構表示，根據(jù)數(shù)據(jù)元素之間關系的不同特性，通常有下列四類基本結構：集合、線性結構、(1)和 （2）2.評價算法的標準很多，通常是以執(zhí)行算法所需要的 劣。（3）和所占用的（4）來判別一個算法的優(yōu)3 .線性表的順序存儲結構特點是表中邏輯關系相鄰的元素在機器內(nèi)的（5)也是相鄰的。4 .空格串的長度為串中所包含（6） 字符的個數(shù)，空串的長度

22、為（7）5.加上表示指向前驅和（8） 的線索的二叉數(shù)稱為線索二叉樹。三、判斷題（對的打，錯的打“X”。每小題1分，共10分）（錯）1.線性表的唯一存儲形式是鏈表。（對）2.已知指針P指向鍵表L中的某結點，執(zhí)行語句 P=P-next不會刪除該鏈表中的結點。（對）3.在鏈隊列中，即使不設置尾指針也能進行入隊操作。（錯）4.如果一個串中的所有字符均在另一串中出現(xiàn)，則說前者是后者的子串。（錯）5.設與一棵樹T所對應的二叉樹為 BT,則與T中的葉子結點所對應的 BT中的結點也一定是葉 子結點。（對）6.快速排序是不穩(wěn)定排序。（錯）7.任一 AOE網(wǎng)中至少有一條關鍵路徑，且是從源點到匯點的路徑中最短的一條

23、。（錯）8.若圖G的最小生成樹不唯一，則 G的邊數(shù)一定多于n-1,并且權值最小的邊有多條（其中 n 為G的頂點數(shù)）。（錯）9.給出不同的輸入序列建造二叉排序樹，一定得到不同的二叉排序樹。（錯）10.基數(shù)排序是多關鍵字排序。從最低位關鍵字起進行排序。四、應用題。（共44分）1 .畫出該圖的鄰接矩陣和鄰接表。根據(jù)鄰接表從A開始求DFS和BFS序列。（12分）2 .假設用于通信的電子由字符集 a,b,c,d,e,f,g,h中的字母構成，這 8個字母在電文中出現(xiàn)的概率分別為 , 畫出哈夫曼樹，并為這 8個字母設計哈夫曼編碼。（8分）3 .已知序列70, 73, 69, 23, 93, 18,11 , 68請給出直接插入排序作升序排序每一趟的結果和快速排 序作升序排序時一趟的結果。（10分）4 .設有一組關鍵字關鍵碼集為47, 7, 29, 11 ,16, 92, 22, 8, 3,哈希表表長為11, Hash（key）=keymod 11,用線性探測法處理沖突，構造哈希表，并求它成功查找的ASL （8分）5 .二叉樹的先序遍歷序列為A B C D E F G H ,I中序遍歷序列為 B C A E D G H F, I畫出這棵二叉樹。（6分）五、算法設計題（