第一篇：數據結構試卷及參考答案_9

數據結構試卷

（九）一、選擇題(30分)1．下列程序段的時間復雜度為（）。

for(i=0； i

for(i=0； i

(A)O(m*n*t)(B)O(m+n+t)(C)O(m+n*t)(D)O(m*t+n)2．設順序線性表中有n個數據元素，則刪除表中第i個元素需要移動（）個元素。

(A)n-i(B)n+l-i(C)n-1-i(D)i 3．設F是由T1、T2和T3三棵樹組成的森林，與F對應的二叉樹為B，T1、T2和T3的結點數分別為N1、N2和N3，則二叉樹B的根結點的左子樹的結點數為（）。

(A)N1-1(B)N2-1(C)N2+N3(D)N1+N3 4．利用直接插入排序法的思想建立一個有序線性表的時間復雜度為（）。

(A)O(n)(B)O(nlog2n)(C)O(n2)(D)O(1og2n)5．設指針變量p指向雙向鏈表中結點A，指針變量s指向被插入的結點X，則在結點A的后面插入結點X的操作序列為（）。

(A)p->right=s； s->left=p； p->right->left=s； s->right=p->right；

(B)s->left=p；s->right=p->right；p->right=s； p->right->left=s；

(C)p->right=s； p->right->left=s； s->left=p； s->right=p->right；

(D)s->left=p；s->right=p->right；p->right->left=s； p->right=s； 6．下列各種排序算法中平均時間復雜度為O(n2)是（）。

(A)快速排序(B)堆排序(C)歸并排序(D)冒泡排序

7．設輸入序列1、2、3、…、n經過棧作用后，輸出序列中的第一個元素是n，則輸出序列中的第i個輸出元素是（）。

(A)n-i(B)n-1-i(C)n+l-i(D)不能確定

8．設散列表中有m個存儲單元，散列函數H(key)= key%p，則p最好選擇（）。

(A)小于等于m的最大奇數(B)小于等于m的最大素數

(C)小于等于m的最大偶數(D)小于等于m的最大合數

9．設在一棵度數為3的樹中，度數為3的結點數有2個，度數為2的結點數有1個，度數為1的結點數有2個，那么度數為0的結點數有（）個。

(A)4(B)5(C)6(D)7 10.設完全無向圖中有n個頂點，則該完全無向圖中有（）條邊。

(A)n(n-1)/2(B)n(n-1)(C)n(n+1)/2(D)(n-1)/2 11.設順序表的長度為n，則順序查找的平均比較次數為（）。

(A)n(B)n/2(C)(n+1)/2(D)(n-1)/2 12.設有序表中的元素為(13，18，24，35，47，50，62)，則在其中利用二分法查找值為24的元素需要經過（）次比較。

(A)1(B)2(C)3(D)4 13.設順序線性表的長度為30，分成5塊，每塊6個元素，如果采用分塊查找，則其平均查找長度為（）。

(A)6(B)11(C)5(D)6.5 14.設有向無環圖G中的有向邊集合E={<1，2>，<2，3>，<3，4>，<1，4>}，則下列屬于該有向圖G的一種拓撲排序序列的是（）。(A)1，2，3，4(B)2，3，4，1(C)1，4，2，3(D)1，2，4，3 15.設有一組初始記錄關鍵字序列為(34，76，45，18，26，54，92)，則由這組記錄關鍵字生成的二叉排序樹的深度為（）。

(A)4(B)5(C)6(D)7

二、填空題(30分)1． 設指針p指向單鏈表中結點A，指針s指向被插入的結點X，則在結點A的前面插入結點X時的操作序列為：

1)s->next=___________；2)p->next=s；3)t=p->data； 4)p->data=___________；5)s->data=t；

2． 設某棵完全二叉樹中有100個結點，則該二叉樹中有______________個葉子結點。3． 設某順序循環隊列中有m個元素，且規定隊頭指針F指向隊頭元素的前一個位置，隊尾指針R指向隊尾元素的當前位置，則該循環隊列中最多存儲_______隊列元素。

4． 對一組初始關鍵字序列（40，50，95，20，15，70，60，45，10）進行冒泡排序，則第一趟需要進行相鄰記錄的比較的次數為__________，在整個排序過程中最多需要進行__________趟排序才可以完成。

5． 在堆排序和快速排序中，如果從平均情況下排序的速度最快的角度來考慮應最好選擇_________排序，如果從節省存儲空間的角度來考慮則最好選擇________排序。

6． 設一組初始記錄關鍵字序列為(20，12，42，31，18，14，28)，則根據這些記錄關鍵字構造的二叉排序樹的平均查找長度是_______________________________。

7． 設一棵二叉樹的中序遍歷序列為BDCA，后序遍歷序列為DBAC，則這棵二叉樹的前序序列為____________________。

8． 設用于通信的電文僅由8個字母組成，字母在電文中出現的頻率分別為7、19、2、6、32、3、21、10，根據這些頻率作為權值構造哈夫曼樹，則這棵哈夫曼樹的高度為________________。

9． 設一組記錄關鍵字序列為(80，70，33，65，24，56，48)，則用篩選法建成的初始堆為_______________________。10． 設無向圖G（如右圖所示），則其最小生成樹上所有邊的權值之和為_________________。

三、判斷題(20分)1． 有向圖的鄰接表和逆鄰接表中表結點的個數不一定相等。()2． 對鏈表進行插入和刪除操作時不必移動鏈表中結點。()3． 子串“ABC”在主串“AABCABCD”中的位置為2。()4． 若一個葉子結點是某二叉樹的中序遍歷序列的最后一個結點，則它必是該二叉樹的先序遍歷序列中的最后一個結點。()5． 希爾排序算法的時間復雜度為O(n2)。()6． 用鄰接矩陣作為圖的存儲結構時，則其所占用的存儲空間與圖中頂點數無關而與圖中邊數有關。()7． 中序遍歷一棵二叉排序樹可以得到一個有序的序列。()8． 入棧操作和入隊列操作在鏈式存儲結構上實現時不需要考慮棧溢出的情況。()9． 順序表查找指的是在順序存儲結構上進行查找。（）10． 堆是完全二叉樹，完全二叉樹不一定是堆。（）

五、算法設計題(20分)1． 設計計算二叉樹中所有結點值之和的算法。2． 設計將所有奇數移到所有偶數之前的算法。3． 設計判斷單鏈表中元素是否是遞增的算法。

數據結構試卷

（九）參考答案

一、選擇題 1．A 2．A 6．D 7．C 11．C 12．C 3．A 8．B 13．D 4．C 9．C 14．A 5．D 10．A 15．A

二、填空題

1.p->next，s->data 2.3.4.5.6.7.8.9.50 m-1 6，8 快速，堆

19/7 CBDA 6(24，65，33，80，70，56，48)10.8

三、判斷題

1．錯 2．對 3．對 4．對 5．錯 6．錯 7．對 8．對 9．錯 10．對

四、算法設計題

1． 設計計算二叉樹中所有結點值之和的算法。

void sum(bitree *bt,int &s){

if(bt!=0){s=s+bt->data;sum(bt->lchild,s);sum(bt->rchild,s);} } 2． 設計將所有奇數移到所有偶數之前的算法。void quickpass(int r[], int s, int t){

int i=s,j=t,x=r[s];

while(i

while(i

while(i

}

r[i]=x;} 3． 設計判斷單鏈表中元素是否是遞增的算法。int isriselk(lklist *head){ if(head==0||head->next==0)return(1);else for(q=head,p=head->next;p!=0;q=p,p=p->next)if(q->data>p->data)return(0);return(1);}

第二篇：數據結構期中試卷及答案

一、選擇題（每小題2分，共30分）1.數據結構是（D）。

A．一種數據類型 B．數據的存儲結構 C．一組性質相同的數據元素的集合

D．相互之間存在一種或多種特定關系的數據元素的集合

2．以下與數據的存儲結構無關的術語是（D）。

A．鏈隊列 B.鏈表 C.順序表 D.棧

3．以下數據結構中，（A）是非線性數據結構

A．樹 B．字符串 C．隊 D．棧

4．一個順序存儲線性表的第一個元素的存儲地址是90，每個元素的長度是2，則第6個元素的存儲地址是（B）。

A．98 B．100 C．102 D．106

5．在線性表的下列運算中，不改變數據元素之間結構關系的運算是（D）。A．插入 B．刪除 C．排序 D．查找

6．線性表采用鏈式存儲時，其地址(D)。

A．必須是連續的 B．一定是不連續的 C．部分地址必須連續 D．連續與否均可以

7．線性表是(A)。

A．一個有限序列，可以為空 B．一個有限序列，不可以為空 C．一個無限序列，可以為空 D．一個無限序列，不可以為空

8．若進棧序列為1，2，3，4，5，6，且進棧和出棧可以穿插進行，則可能出現的出棧序列為（B）。

A．3，2，6，1，4，5 B．3，4，2，1，6，5 C．1，2，5，3，4，6 D．5，6，4，2，3，1

9.若一個棧的輸人序列是1，2，3，…，n，輸出序列的第一個元素是n，則第k個輸出元素是（C）。

A．k B．n-k-1 C．n-k+1 D．不確定

10.對于隊列操作數據的原則是（A）。

A.先進先出 B.后進先出 C.先進后出 D.不分順序 11.棧和隊列的共同點是（C）。

A.都是先進先出 B.都是先進后出 C.只允許在端點處插入和刪除元素 D.沒有共同點

12．在一個鏈隊列中，假定front和rear分別為頭指針和尾指針，刪除一個結點的操作是（A）。

A．front=front->next B．rear=rear->next C．rear->next=front D．front->next＝rear

13.空串與空格串（B）。

A．相同 B．不相同 C．可能相同 D．無法確定

14.串與普通的線性表相比較，它的特殊性體現在（C）。A．順序的存儲結構 B．鏈接的存儲結構 C．數據元素是一個字符 D．數據元素可以任意

15.串的長度是指（B）。

A.串中所含不同字母的個數 B.串中所含字符的個數

C.串中所含不同字符的個數 D.串中所含非空格字符的個數

二、填空題（每空2分，共20分）

1． 線性表、棧和隊列，串都是__線性_____結構。2． 數據的基本單位是__數據元素_______________。

3． 當線性表的元素總數基本穩定，且很少進行插入和刪除操作，但要求以最快的速度存取線性表中的元素時，應采用_順序______存儲結構。4． 已知具有n個元素的一維數組采用順序存儲結構，每個元素占k個存儲單元，第一個元素的地址為Loc(a1)，那么，第i個元素的存儲地址Loc(ai)= Loc(a1)+(i-1)*k。5． 棧（stack）是限定在表尾進行插人或刪除操作的線性表。在棧中，允許插人和刪除操作的一端稱為__棧頂________，而另一端稱為_棧底________。6． 一個循環隊列Q中，頭指針和尾指針分別為Q.front和Q.rear，且最大隊列長度為MaxQSize，則判斷隊空的條件為 Q.rear==Q.front,判斷隊滿的條件為(Q.rear+1)%MaxQSize==Q.front。隊列的長度為(.rear-Q.front+MaxQSize)%MaxQSize

7． 兩個串相等的充分必要條件是 兩個串的長度相等，且各個對應位置的字符都相等。

三、程序填空題（每空3分，共30分）

1.在帶頭結點的單鏈表L中第i個數據元素之前插入數據元素e的C語言描述算法如下，其中L為鏈表頭結點指針。請填充算法中標出的空白處，完成其功能。

typedef struct node {int data；

struct node *next；

}linknode,*link；

int ListInsert_L(link &L, int i, int e){ Linknode *p；int j； p = L； j = 0；

while(p && j < i-1){ p=p->next ； ++j； } // 尋找第i-1個結點 if(!p || j > i-1)return 0；

s=(link)malloc(sizeof(linknode))；// 生成新結點s s->data = e；

s->next=p->next ； p->next = s； // 插入L中 return 1； }

2.對順序棧的C語言描述算法如下，其中top為棧頂指針，請填充算法中標出的空白處，插入元素e為新的棧頂元素。

#define STACK_INIT_SIZE 100 #define STACKINCREMENT 10 typedef struct{ char *base;char *top;int stacksize;}SqStack;

int Push(SqStack &S, char e){ //

if((s.top-s.base)>=s.stacksize)//棧滿，追加存儲空間 { S.base=(SElemType *)realloc(S.base,S.stacksize+STACKINCREMENT)*sizeof(SElemType))； if(!S.base)return 0；

S.top = s.base+s.stacksize ； //修改棧頂指針 S.stacksize += STACKINCREMENT； } *s.top++=e ；//插入元素 return 1； }

3.對鏈隊列的C語言描述算法如下，請填充算法中標出的空白處，刪除隊列Q 的隊頭元素并用e返回其值。typedef struct QNode{ QElemType data； struct QNode *next； }QNode, *QueuePtr；

typedef struct { QueuePtr front； QueuePtr rear； }LinkQueue；

int DeQueue(LinkQueue &Q, QElemType &e){ Linknode *p；

if(Q.front==Q.rear)retrun 0；//隊列空，返回 p = Q.front-> next； e = p->data；

Q.front-> next=p->next；//修改指針

if(Q.rear==p)Q.rear= Q.front ； //隊列只有一個元素的情況 free(p)；//釋放結點空間 return 1； }

三、算法設計與分析題（每題10分，共20分）

1、簡述下列算法實現的功能：（每題5分，共10分）（1）typedef struct LNode{

Char data;

struct LNode *next;}LNode,*LinkList;LinkList Demo(LinkList &L){ // L 是無頭結點單鏈表 LNode *Q,*P;if(L&&L->next){

Q=L;L=L->next;P=L;while(P->next)P=P->next;

P->next=Q;Q->next=NULL;

} return L;}// Demo 答：將單鏈表的第一個結點刪除，放到鏈尾。

———————————————————————————————————————————————————

（2）#define STACK_INIT_SIZE 100 #define STACKINCREMENT 10 typedef struct{ int *base;int *top;int stacksize;

} Stack;void Demo1(Stack &S, int m){ Stack T;int i;

InitStack(T);//初始化棧

while(!StackEmpty(S))//判斷棧是否為空

if((i=Pop(S))!=m)Push(T,i);//入棧操作

while(!StackEmpty(T))

{

i=Pop(T);//出棧操作

Push(S,i);

}

} 答：刪除棧S中所有值為m的數據元素

2.有一個帶頭結點的單鏈表，頭指針為head，編寫一個算法計算所有數據域為X的結點的個數（不包括頭結點）。typedef struct node {int data;struct node *next;}linknode,*link;int sample(link head, int X){ int count=0;link p=head->next;while(p){if(p->data==X)count++;p=p->next;} return count;}

第三篇：數據結構期中考試試卷答案

2014－2015學第一學期《數據結構》

期中考試試卷

一、選擇題（每題2分，共20分）

1.計算機內部數據處理的基本單位是（B）。

A.數據 B.數據元素

C.數據項

D.數據庫 2.設語句x++的時間是單位時間，則以下語句的時間復雜度為（B）。

for(i=1;i<=n;i++)for(j=i;j<=n;j++)x++;A.O(1)B.O(n)C.O(n)

D.O(n)

33.在一個長度為n的順序表中刪除第i個元素(0<=i<=n)時，需向前移動（A）個元素。

A．n-i B．n-i+l C．n-i-1 D．i 4.在一個單鏈表中，已知q結點是p結點的前趨結點，若在q和p之間插入s結點，則須執行（B）。

A．s->next=p->next;p->next=s B．q->next=s;s->next=p C．p->next=s->next;s->next=p D．p->next=s;s->next=q 5.在一個具有n個單元的順序棧中，假定以地址低端（即0單元）作為棧底，以top作為棧頂指針，當做出棧處理時，top變化為______。C A．top不變

B．top=0 C．top--D．top++ 6.在具有n個單元的順序存儲的循環隊列中，假定front和rear分別為隊頭指針和隊尾指針，則判斷隊滿的條件為________。D A．rear％n= = front B．（front+l）％n= = rear C．rear％n-1= = front D．(rear+l)％n= = front 7.兩個字符串相等的條件是（D）。

A.兩串的長度相等 B.兩串的長度相等，并且兩串包含的字符相同 C.兩串包含的字符相同 D.兩串的長度相等，并且對應位置上的字符相同

8.數組A中，每個元素的長度為3個字節，行下標i從1到8，列下標j從1到10，從首地址SA開始連續存放在存儲器內，該數組按行存放時，元素A[8][5]的起始地址為（C）。A.SA+141 B.SA+144 C.SA+222 D.SA+225 9.設有廣義表D=(a,b,D)，其長度為（B），深度為（A）。A.無窮大 B.3

C.2 D.5 10.假設在一棵二叉樹中，雙分支結點數為15，單分支結點數為30個，則葉子結點數為（B）個。

A.15

B.16

C.17

D.47

二、填空題（每空1分，共20分）

1.數據的邏輯結構有四種基本形態，分別是________________、__________________、__________________和__________________。2.集合，線性，樹，圖

2.一個算法的效率可分為__________________效率和__________________效率。4.時間，空間

3.當對一個線性表經常進行存取操作，而很少進行插入和刪除操作時，則采用_______存儲結構為宜。相反，當經常進行的是插入和刪除操作時，則采用_______存儲結構為宜。7．順

（第1頁，共3頁）

序，鏈接

4.對于一個具有n個結點的單鏈表，在已知的結點p后插入一個新結點的時間復雜度為______，在給定值為x的結點后插入一個新結點的時間復雜度為_______。12．O(1)，O(n)5.可以在線性表的______位置插入和刪除元素；對于棧只能在_______位置刪除元素；對于隊列只能在_______位置插入元素。9任何，棧頂，隊尾 6.設字符串S1= “ABCDEF”，S2= “PQRS”，則運算S=CONCAT（SUB（S1，2，LEN（S2）），SUB（S1，LEN（S2），2））后的串值為___________________。3.“BCDEDE”

7.一維數組的邏輯結構是______________，存儲結構是______________；對于二維或多維數組，分為______________和______________兩種不同的存儲方式。1.線性結構，順序結構，以行為主序，以列為主序

8.三維數組R[c1?d1,c2?d2,c3?d3]共含有______________個元素。（其中：c1≤d1,c2≤d2,c3≤d3）9.（d1-c1+1）×（d2-c2+1）×（d3-c3+1）

9.數組A[1?10，-2?6，2?8]以行優先的順序存儲，設第一個元素的首地址是100，每個元素占3個存儲長度的存儲空間，則元素A[5，0，7]的存儲地址為______________。10.913

三、簡答題（每題6分，共18分）1.已知L是無表頭結點的單鏈表，且P結點既不是首元結點也不是尾元結點，試寫出合適的語句序列。(1)在P結點后插入S結點。(2)在表首插入S結點。(3)在表尾插入S結點。2已知L是帶表頭結點的非空單鏈表，且P結點既不是首元結點也不是尾元結點，試寫出合適的語句序列。(1)刪除P結點的直接后繼結點。(2)刪除P結點。（3）刪除尾元結點。3． LinkList mynote(LinkList L){//L是不帶頭結點的單鏈表的頭指針 if(L&&L->next){ q=L；L=L－>next；p=L；

S1： while(p－>next)p=p－>next； S2： p－>next=q；q－>next=NULL；

} return L； } 請回答下列問題：（1）說明語句S1的功能；（2）說明語句組S2的功能；（3）設鏈表表示的線性表為（a1,a2, ?,an）,寫出算法執行后的返回值所表示的線性表。

該算法的功能是：將開始結點摘下鏈接到終端結點之后成為新的終端結點，而原來的第二個結點成為新的開始結點，返回新鏈表的頭指針。

四、算法設計題（每題14分，共42分）1.假設有一個循環鏈表的長度大于1，且表中既無頭結點也無頭指針，已知p為指向鏈表中某結點的指針，設計在鏈表中刪除p所指結點的前趨結點的算法。

解：可引入一個指針q，當q->next=p時，說明此時q所指的結點為p所指結點的前趨結點，從而可得算法如下：

void delete(LinkList *p){ //在鏈表中刪除p所指結點的前趨結點 LinkList *q,*t;

q=p;

while(q->next->next!=p)//q->next不是p的前趨結點

（第2頁，共3頁）

q=q->next;

t=q->next;//t指向要刪除結點

q->next=p;//刪除t結點

free(t);｝

2.已知線性表的元素是無序的，且以帶頭結點的單鏈表作為存儲結構。設計一個刪除表中所有值小于max但大于min的元素的算法。

2．算法描述如下：

delete(LinkList *head, int max, int min){ LinkList *p,*q;

q=head;

p=head->next;

while(p!=NULL)

if((p->data<=min)||(p->data>=max))

{ q=p;

p=p->next;

} else { q->next=p->next;free(p);p=q->next;} }

3.假設表達式有單字母變量和雙目四則運算符構成。試寫一個算法，對一個通常書寫形式且書寫正確的表達式求值。

（第3頁，共3頁）

第四篇：數據結構試卷(一)及答案

數據結構試卷

（一）一、選擇題（20分）

1．組成數據的基本單位是（）。

(A)數據項(B)數據類型(C)數據元素(D)數據變量

2．設數據結構A=(D，R)，其中D={1，2，3，4}，R={r}，r={<1，2>，<2，3>，<3，4>，<4，1>}，則數據結構A是（）。

(A)線性結構(B)樹型結構(C)圖型結構(D)集合 3．數組的邏輯結構不同于下列（）的邏輯結構。

(A)線性表(B)棧(C)隊列(D)樹 4．二叉樹中第i(i≥1)層上的結點數最多有（）個。

ii-1(A)2i(B)2(C)2(D)2i-1 5．設指針變量p指向單鏈表結點A，則刪除結點A的后繼結點B需要的操作為（）。

(A)p->next=p->next->next(B)p=p->next

(C)p=p->next->next(D)p->next=p 6．設棧S和隊列Q的初始狀態為空，元素E1、E2、E3、E4、E5和E6依次通過棧S，一個元素出棧后即進入隊列Q，若6個元素出列的順序為E2、E4、E3、E6、E5和E1，則棧S的容量至少應該是（）。

(A)6(B)4(C)3(D)2 7．將10階對稱矩陣壓縮存儲到一維數組A中，則數組A的長度最少為（）。

(A)100(B)40(C)55(D)80 8．設結點A有3個兄弟結點且結點B為結點A的雙親結點，則結點B的度數數為（）。

(A)3(B)4(C)5(D)1 9．根據二叉樹的定義可知二叉樹共有（）種不同的形態。

(A)4(B)5(C)6(D)7 10.設有以下四種排序方法，則（）的空間復雜度最大。

(A)冒泡排序(B)快速排序(C)堆排序(D)希爾排序

二、填空題(30分)1.設順序循環隊列Q[0：m-1]的隊頭指針和隊尾指針分別為F和R，其中隊頭指針F指向當前隊頭元素的前一個位置，隊尾指針R指向當前隊尾元素所在的位置，則出隊列的語句為F =____________。

2.設線性表中有n個數據元素，則在順序存儲結構上實現順序查找的平均時間復雜度為___________，在鏈式存儲結構上實現順序查找的平均時間復雜度為___________。3.設一棵二叉樹中有n個結點，則當用二叉鏈表作為其存儲結構時，該二叉鏈表中共有________個指針域，__________個空指針域。

4.設指針變量p指向單鏈表中結點A，指針變量s指向被插入的結點B，則在結點A的后面插入結點B的操作序列為______________________________________。

5.設無向圖G中有n個頂點和e條邊，則其對應的鄰接表中有_________個表頭結點和_________個表結點。

6.設無向圖G中有n個頂點e條邊，所有頂點的度數之和為m，則e和m有______關系。7.設一棵二叉樹的前序遍歷序列和中序遍歷序列均為ABC，則該二叉樹的后序遍歷序列為__________。

8.設一棵完全二叉樹中有21個結點，如果按照從上到下、從左到右的順序從1開始順序編號，則編號為8的雙親結點的編號是___________，編號為8的左孩子結點的編號是_____________。

9.下列程序段的功能實現子串t在主串s中位置的算法，要求在下劃線處填上正確語句。

int index(char s[ ], char t[ ]){ i=j=0;while(i

三、應用題（30分）

1．設完全二叉樹的順序存儲結構中存儲數據ABCDE，要求給出該二叉樹的鏈式存儲結構并給出該二叉樹的前序、中序和后序遍歷序列。

2．設給定一個權值集合W=(3，5，7，9，11)，要求根據給定的權值集合構造一棵哈夫曼樹并計算哈夫曼樹的帶權路徑長度WPL。

3．設一組初始記錄關鍵字序列為(19，21，16，5，18，23)，要求給出以19為基準的一趟快速排序結果以及第2趟直接選擇排序后的結果。

4．設一組初始記錄關鍵字集合為(25，10，8，27，32，68)，散列表的長度為8，散列函數H(k)=k mod 7，要求分別用線性探測和鏈地址法作為解決沖突的方法設計哈希表。5．設無向圖G（所右圖所示），要求給出該圖的深度優先和廣度優先遍歷的序列并給出該圖的最小生成樹。

四、算法設計題(20分)1.設計判斷單鏈表中結點是否關于中心對稱算法。2.設計在鏈式存儲結構上建立一棵二叉樹的算法。3.設計判斷一棵二叉樹是否是二叉排序樹的算法。

數據結構試卷

（一）參考答案

一、選擇題

1.C 2.C 3.D 4.C 5.A 6.C 7.C 8.B 9.B 10.B

二、填空題 1.(F+1)% m 2.O(n)，O(n)3.2n，n+1 4.s->next=p->next;s->next=s 5.n, 2e 6.m=2e 7.CBA 8.4，16 9.i-j+1，0 10.n-1

三、應用題

1.鏈式存儲結構略，前序ABDEC，中序DBEAC，后序DEBCA。2.哈夫曼樹略，WPL=78 3.(18,5,16,19,21,23)，(5，16，21，19，18，23)

h0h1??8h2012345674.線性探測： 鏈地址法：h3??10

?8?1025322768h4??25??32h5??68h6??275.深度：125364，廣度：123456，最小生成樹T的邊集為E={(1，4)，(1，3)，(3，5)，(5，6)，(5,6)}

四、算法設計題

1.設計判斷單鏈表中結點是否關于中心對稱算法。

typedef struct {int s[100];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.s[stack.top]=p->data;}

for(p=head;p!=0;p=p->next)if(p->data==stack.s[stack.top])stack.top=stack.top-1;else return(0);

return(1);} 2.設計在鏈式存儲結構上建立一棵二叉樹的算法。

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 node{int key;struct node *lchild,*rchild;}bitree;void inorder(bitree *bt){

if(bt!=0)

{inorder(bt->lchild);if(minnum>bt->key)flag=0;minnum=bt->key;inorder(bt->rchild);} }

第五篇：廣東海洋大學數據結構試卷及答案

廣東海洋大學

2013 ——

2014 學年第 1 學期

《數據結構與算法》課程試題

一、選擇題（6小題，每題3分）

1.若某線性表中最常用的操作是取第i個元素和找第i個元素的前驅，則采用（A)存儲方法最節省時間 A 順序表

B單鏈表

C 雙鏈表

D單循環鏈表 2.一個棧的入棧序列是1,2,3,4,5，則不可能的出棧序列是(C)A 5,4,3,2,1

B 4,5,3,2,1

C 4,3,5,1,2

D 1,2,3,4,5 3.深度為k的完全二叉樹至多有（C）個結點 A 2k?2?

1B 2k?1

C

D 2k?1?1

k4.G是一個非連通無向圖，共28條邊，則該圖至少有（D）個頂點2A 6

B 7

C 8

D 9

?1

5.在平衡二叉樹中插入一個結點后造成不平衡，設最低的不平衡結點為A，并已知A的左孩子平衡因子為0，右孩子平衡因子為1，則應該做（C）型調整以使其平衡 A LL

B LR

C RL

D RR 6.下述排序方法中，時間性能和待排序記錄的初始狀態無關的是（C）A 插入排序和快速排序

B 歸并排序和快速排序 C 選擇排序和歸并排序

D 插入排序和歸并排序

二、填空題

1.數組Q[n]用來表示一個循環隊列，front為隊頭元素的前一個位置，rear為隊尾元素位置，計算隊列中元素個數的公式為______（rear-front+n）%n______________。

2.已知一棵度為3的樹有2個度為1的結點，3個度為2的結點，4個度為3的結點。則該樹中有__12_________個葉子結點。

3.已知無向圖的頂點數為n，邊數為e，其鄰接表表示的空間復雜度為____________O(n+e)____。4.假定一個數列{25,43,62,31,48,56}，采用散列函數為H(k)=k mod 7，則元素48的同義詞是____62_______。5.利用簡單選擇排序對n個記錄進行排序，最壞情況下，記錄交換次數為_____n-1_______。

三、（15分）已知一棵二叉樹的中序遍歷序列為DBKEHJAFCIG，后序遍歷序列為DKJHEBFIGCA，試畫出該二叉樹并給出其前序遍歷序列

四、（15分）設用于通信的電文由字符集{a,b,c,d,e,f,g,h}中的字母構成，它們在電文中出現的頻度分別為{0.02,0.30,0.08,0.14,0.17,0.11,0.12, 0.06}，回答下面問題：（1）為這八個字符設計哈夫曼編碼（2）對這八個字符進行等長編碼需要幾位二進制數，哈夫曼編碼比等長編碼電文總長壓縮多少？

五、（20分）已知一個長度為11的線性表List=(12, 24, 36, 90, 52, 30, 41, 8, 10, 38, 61)，試回答下面問題（1）將線性表元素依次插入一個空的平衡二叉樹，畫出所得平衡二叉樹，如果假設每個元素查找概率相同，則平均查找長度為多少？

（2）如果對線性表元素排序后進行折半查找，畫出折半查找判定樹，假設每個元素查找概率相同，計算平均查找長度。

六、（12分）已知數據序列為（11,4,8,19,6,31,23），寫出快速排序及堆排序每一趟的結果 解：

七、（11分）設單鏈表以非遞減有序排列，設計算法實現在單鏈表中刪除值相同的多余結點。