大學計算機《數(shù)據(jù)結構》試卷及答案

1、大學計算機數(shù)據(jù)結構試卷及答案一、選擇題(20分)組成數(shù)據(jù)的基本單位是()。(A)數(shù)據(jù)項 (B)數(shù)據(jù)類型(C)數(shù)據(jù)元素(D)數(shù)據(jù)變量設數(shù)據(jù)結構A=(D, R),其中D=1, 2, 3, 4, R=r, r=, , , ,則數(shù)據(jù)結構A是()。(A)線性結構 (B)樹型結構(C)圖型結構(D)集合數(shù)組的邏輯結構不同于下列()的邏輯結構。(A)線性表(B)棧(C)隊列(D)樹二叉樹中第i(iMD上的結點數(shù)最多有()個。(A) 2i(B) 2i(C) 2i-1(D) 2i-1設指針變量p指向單鏈表結點A,則刪除結點A的后繼結點B需要的操作為()。(A) p-next=p-next-next(B) p=p

2、-next(C) p=p-next-next(D) p-next=p設棧S和隊列Q的初始狀態(tài)為空，元素E1、E2、E3、E4、E5和E6依次通 過棧S, 一個元素出棧后即進入隊列Q,若6個元素出列的順序為E2、E4、E3、 E6、E5和E1,則棧S的容量至少應該是()。(A) 6(B) 4(C) 3(D) 2將10階對稱矩陣壓縮存儲到一維數(shù)組A中，則數(shù)組A的長度最少為()。(A) 100(B) 40(C) 55(D) 80設結點A有3個兄弟結點且結點B為結點A的雙親結點，則結點B的度數(shù) 數(shù)為()。(A) 3(B) 4(C) 5(D) 1 根據(jù)二叉樹的定義可知二叉樹共有()種不同的形態(tài)。(A)

3、4(B) 5(C) 6(D) 7設有以下四種排序方法，則()的空間復雜度最大。(A)冒泡排序 (B)快速排序(C)堆排序 (D)希爾排序二、填空題(30分)設順序循環(huán)隊列Q0： m-1的隊頭指針和隊尾指針分別為F和R,其中隊頭 指針F指向當前隊頭元素的前一個位置，隊尾指針R指向當前隊尾元素所在的 位置，則出隊列的語句為F =;。設線性表中有n個數(shù)據(jù)元素，則在順序存儲結構上實現(xiàn)順序查找的平均時間 復雜度為，在鏈式存儲結構上實現(xiàn)順序查找的平均時間復雜度為設一棵二叉樹中有n個結點，則當用二叉鏈表作為其存儲結構時，該二叉鏈表中共有 個指針域，個空指針域。設指針變量p指向單鏈表中結點A，指針變量s指向被

4、插入的結點B，則在 結點A的后面插入結點B的操作序列為。設無向圖G中有n個頂點和e條邊，則其對應的鄰接表中有 個表頭結點和 個表結點。設無向圖G中有n個頂點e條邊，所有頂點的度數(shù)之和為m，則e和m有 關系。設一棵二叉樹的前序遍歷序列和中序遍歷序列均為ABC，則該二叉樹的后 序遍歷序列為。設一棵完全二叉樹中有21個結點，如果按照從上到下、從左到右的順序從 1開始順序編號，則編號為8的雙親結點的編號是，編號為8的左 孩子結點的編號是。下列程序段的功能實現(xiàn)子串t在主串s中位置的算法，要求在下劃線處填上 正確語句。int index(char s , char t)i=j=;while(istrlen

5、(s) & jnext=p-next; s-next=sn, 2em=2eCBA4, 16i-j+1, 010.n-1三、應用題f1. 鏈式存儲結構略，前序ABDEC，中序DBEAC，后序dEbCAo2.3.哈夫曼樹略，WPL=78(18,5,16,19,20,23)，套，316,4 215 19，18，23)h - 25-32 h4 - 68線性探測：八8 A 10 25 32 27 68鏈地址法：-27深度：125364，廣度：123456，最小生成樹T的邊集為E=（1，4），（1，3）， （3，5），（5，6），（5,6）四、算法設計題1.設計判斷單鏈表中結點是否關于中心對稱算法。typ

6、edef struct int s100; int top; sqstack;int lklistsymmetry(lklist *head)sqstack stack; stack.top= -1; lklist *p;for(p=head;p!=0;p=p-next) stack.top+; stack.sstack.top=p-data;for(p=head;p!=0;p=p-next)if (p-data=stack.sstack.top)stack.top=stack.top-1; else return(0);return(1);1. 2.設計在鏈式存儲結構上建立一棵二叉樹的算法。

7、typedef char datatype;typedef struct node datatype data; struct node *lchild,*rchild; bitree;void createbitree(bitree *&bt)char ch; scanf(%c”,&ch);if(ch=#) bt=0; return;bt=(bitree*)malloc(sizeof(bitree); bt-data=ch;createbitree(bt-lchild); createbitree(bt-rchild);3.設計判斷一棵二叉樹是否是二叉排序樹的算法。int minnum=-32768,flag=1;typedef struct nodeint key; struct node *lchild,*rchild;bitr