數據結構試卷試題及答案A

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

2、ar分別為隊列的頭、尾指針，maxSize為數組的最大長度，隊滿的條件是( )。A. front=maxSize B. (rear+1)%maxSize=front C. rear=maxSize D. rear=front6設有串t='I am a good student '，那么Substr(t,6,6)=（ ）。A. student B. a good s C. good D. a good7設有一個對稱矩陣A，采用壓縮存儲方式，以行序為主序存儲a11為第一個元素，其存儲地址為1，每個元素占一個地址空間，則 a85地址為（ ）。 A.23 B.33 C.18 D. 40

3、8已知廣義表LS=(A,(B,C,D),E)運用head和tail函數，取出LS中原子b的運算（ ）。 A. Gethead(Gethead(LS) B. Gettail(Gethead(LS) C. Gethead(Gethead(Gettail(LS) D. Gethead(Gettail(LS)9若已知一棵二叉樹先序序列為ABCDEFG，中序序列為CBDAEGF，則其后序序列為( ) 。A. CDBGFEA B. CDBFGEA C. CDBAGFE D. BCDAGFE 10下列存儲形式中，( ) 不是樹的存儲形式。A.雙親表示法 B.左子女右兄弟表示法 C.廣義表表示法 D.順序表示

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

5、or(int I=1;I<=n;I+) for(int j=1;j<=I;j+) S; A. n2 B. n2/2 C. n(n+1) D. n(n+1)/215串是一種特殊的線性表，其特殊性體現在（ ）A.可以順序存儲 B.數據元素是一個字符 C.可以鏈接存儲 D.數據元素可以是多個字符16樹的基本遍歷策略分為先根遍歷和后根遍歷；二叉樹的基本遍歷策略可分為先序遍歷、中序遍歷和后序遍歷。結論( )是正確的。A.樹的先根遍歷序列與其對應的二叉樹的先序遍歷序列相同 B.樹的后根遍歷序列與其對應的二叉樹的先序遍歷序列相同 C.樹的先根遍歷序列與其對應的二叉樹的中序遍歷序列相同 D.以上都

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

7、過程。第二趟為: A.265 301 129 751 863 937 694 742 076 438 B.076 129 265 301 438 694 742 751 863 937 C.129 265 301 694 742 751 863 937 076 438 D.129 265 301 751 694 742 863 937 076 438二、填空題（本大題共6小題，每空2分，共12分；答案填在下表內）1算法是指令的有限序列，其中每一條指令表示一個或多個操作，此外，一個算法還具有五個重要特性，它們分別是 _ 、_ 、_ 、有零或多個輸入和有一或多個輸出。2算法優(yōu)劣的五個標準是正確性、

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

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

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

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

12、入數據和一個輸出結果）(5分)。void conversion() 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實現對二叉樹進行非遞歸先根遍歷的函數,請在標號處填寫合適的語句。(每空1分，共5分)程序:Void preorder(bitree *T)b

13、itree *stackm; int 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) ; 3.請在標號處填寫合適的語句。完成下列程序。(每空1分，共5分)int Binary_Search(S_TBL tbl，KEY kx) /* 在表tbl中查找關鍵碼為kx的數據元素，若找到返回該元素在表中的位置，否則，返回0

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

15、 minval=Ai+1; (1)for(j=i+2;j<=n;j+) if( (2) ) (3) ; minidx=j; if( (4) ) t=Ai+1; (5) Aminidx=t; 5 試寫出求有向無環(huán)圖的關鍵路徑算法的設計思路（10分）數據結構試卷A答案選擇題（本大題共20小題，每題1分，共20分；答案填在下表內）12345678910C B: C: D: B: D: B: C: A: C11121314151617181920: CA: B: D: B: A: C: ACD二、填空題（本大題共5小題，每空1分，共12分；答案填在下表內）1有窮性 確定性 可行性2可讀性 健壯性

16、 效率3n(n-1)4'student'5隊列 先進先出6(a) (a)三、判斷題（對的打“”，錯的打“×”。每小題1分，共10分）1）true ; 2）flase; 3）true; 4）true; 5）flase;6）flase ; 7）true; 8）true; 9）flase; 10）true四、畫出樹的孩子兄弟表示法示意的樹或森林。（4分） ABCDEFGHI其他形式的樹形結構酌情給分。五、要求題（本大題共2小題，共12分）4574574572142571256143324517324517632461751.2.一趟劃分后的數據序列 3 1 2 4 7 5

17、6六、按要求做題（12分）1 DFS遍歷序列v1 v2 v4 v8 v5 v3 v6 v7(或1 2 4 8 5 3 6 7) BFS遍歷序列v1 v2 v3 v4 v5 v6 v7 v8(或1 2 3 4 5 6 7 8)鄰接點的順序可以不同，可以有不同的深度優(yōu)先和廣度優(yōu)先遍歷序列。（5分，如有錯誤酌情扣分。）2 V3V7V7V6V5V4V2504050V4V2V6V530504050V2V54050V6V4V7V1V3V1V3V1 V6V5V2V7V4V6V7V2V4V5V3V3V1V1七、算法設計題（30分）1.將十進制轉化成八進制數（5分）測試用例：輸入10 輸出12 2（5分，每空1

18、分）（1）T(2) top>0(3) 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+1(5) 14. （5分，每空1分）（1）minidx=i+1(2) minval>Aj(3) minval=Aj(4) i!=j(5) Ai+1=Aminidx5（10分，不同答案，酌情得分）輸入頂點和弧信息，建立其鄰接表計算每個頂點的入度對其進行拓撲排序排序過程中求頂點的Vei將得到的拓撲序列進棧按逆拓撲序

19、列求頂點的Vli計算每條弧的ei和li,找出ei=li的關鍵活動第 2 學期 數據結構試卷A一、 選擇題（本大題共15小題，每題2分，共30分；答案填在下表內）1.從一個長度為100的順序表中刪除第30個元素時需向前移動 個元素A、70 B、71 C、69 D、302.在一個具有N個單元的順序表中,假定以地址低端(即下標為1的單元)作為底,以top作為頂指針,則當做進棧處理時top變化為_。A、 top不變 B、top=0 C、top=top-1 D、top=top+13.從一個具有n個結點的單鏈表中查找其值等于x結點時,在查找成功情況下,則平均比較_個結點。 A、n B、n/2 C、(n-1

20、)/2 D、(n+1)/24.在一個單鏈表中,若要刪除p指針所指結點的后繼結點,則執(zhí)行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í)行_。A、front-> next=s； front=s；B、s-> next=rear; rear=s；C、rear-> next=s; r

21、ear=s；D、s-> next=front; front=s；6.在一棵度為3的樹中度為3的結點數為3個,度為2的結點數為1個,度為1的結點數為1個,那么度為0的結點數為_個A、6 B、7 C、 8 D、97.假定一棵二叉樹的結點數為33個,則它的最小高度為_,最大高度為_A、 4,33 B、5,33 C、6,33 D、6,328. 在一棵完全二叉樹中,若編號為i的結點有右孩子,則該結點的右孩子編號為_。A、2i B、2i+1 C、2i-1 D、i/29.在一個有向圖中,所有頂點的入度之和等于所有弧數和_倍。 A、1 B、2 C、3 D、410.對于一個具有N個頂點的圖,若用鄰接矩陣表

22、示,則該矩陣的大小為_。 A、 N B、(N-1)2 C、(N+1)2 D、 N211.已知一個圖如圖所示，在該圖的最小生成樹中各邊上數值之和為_。A、21 B、26 C、28 D、33 12.已知一個圖如圖所示，由該圖行到的一種拓樸序列為 A、v1 v4 v6 v2 v5 v3 B、v1 v2 v3 v4 v5 v6 C、v1 v4 v2 v3 v6 v5 D、v1 v2 v4 v6 v3 v513.二維數組M的元素是4個字符（每個字符占一個存儲單元）組成的串，行下標i的范圍從0到4，列下標j的范圍從0到5，M按行存儲時元素M24的起始地址與M按列存儲時元素 的起始地址相同。 A、m24 B

23、、M42 C、M31 D、M3114.具有6個結點的無向圖至少應有 條邊才能保證是連通圖。A、 5 B、 6 C、 7 D、 8 15.采用鄰接表存儲的圖的深度優(yōu)先遍歷類似于二叉樹的 。A 先序遍歷B中序遍歷 C. 后序遍歷 D. 按層遍歷 二、填空題（本大題共5小題，每空1分，共8分；答案填在下表內）123456781.數據結構是研究數據元素之間抽象化的相互關系和這種關系在計算機中的存儲結構表示，根據數據元素之間關系的不同特性，通常有下列四類基本結構：集合、線性結構、（1） 和 （2） 。2.評價算法的標準很多，通常是以執(zhí)行算法所需要的 （3） 和所占用的（4） 來判別一個算法的優(yōu)劣。3.線

24、性表的順序存儲結構特點是表中邏輯關系相鄰的元素在機器內的（5） 也是相鄰的。4.空格串的長度為串中所包含 （6） 字符的個數，空串的長度為 （7） 5.加上表示指向前驅和 （8） 的線索的二叉數稱為線索二叉樹。三、判斷題（對的打“”，錯的打“×”。每小題1分，共10分）（ ）1.線性表的唯一存儲形式是鏈表。（ ）2.已知指針P指向鍵表L中的某結點，執(zhí)行語句P=P-next不會刪除該鏈表中的結點。（ ）3.在鏈隊列中，即使不設置尾指針也能進行入隊操作。（ ）4.如果一個串中的所有字符均在另一串中出現，則說前者是后者的子串。（ ）5.設與一棵樹T所對應的二叉樹為BT，則與T中的葉子結點所

25、對應的BT中的結點也一定是葉子結點。（ ）6.快速排序是不穩(wěn)定排序。（ ）7.任一AOE網中至少有一條關鍵路徑，且是從源點到匯點的路徑中最短的一條。（ ）8.若圖G的最小生成樹不唯一，則G的邊數一定多于n-1，并且權值最小的邊有多條（其中n為G的頂點數）。（ ）9.給出不同的輸入序列建造二叉排序樹，一定得到不同的二叉排序樹。（）10.基數排序是多關鍵字排序。從最低位關鍵字起進行排序。四、應用題。（共44分）1.畫出該圖的鄰接矩陣和鄰接表。根據鄰接表從A開始求DFS和BFS序列。（12分）2.假設用于通信的電子由字符集a,b,c,d,e,f,g,h中的字母構成，這8個字母在電文中出現的概率分別為

26、0.07，0.19，0.02，0.06，0.32，0.03，0.21，0.10畫出哈夫曼樹，并為這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)=key mod 11，用線性探測法處理沖突，構造哈希表，并求它成功查找的ASL。（8分）5. 二叉樹的先序遍歷序列為 A B C D E F G H I，中序遍歷序列為 B C A E D G H F I，畫出這棵二叉樹。(6分)五、算法設計題（8分）定義有序表抽象數據類型，并據此類型設計折半查找算法。2學期數據結構試卷A參考答案及評分標準一、 選擇題本大題共15小題，每題2分，共30分123456789101112131415ADDBCCCBADBADAA二、