數(shù)據(jù)結(jié)構(gòu)c版試題及答案姓名：____________________

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

1.下列哪種數(shù)據(jù)結(jié)構(gòu)是非線性的？

A.隊(duì)列

B.棧

C.樹

D.數(shù)組

2.下列哪個(gè)算法的時(shí)間復(fù)雜度是O(n^2)？

A.快速排序

B.冒泡排序

C.選擇排序

D.插入排序

3.下列哪種數(shù)據(jù)結(jié)構(gòu)適用于頻繁的插入和刪除操作？

A.鏈表

B.數(shù)組

C.樹

D.堆

4.在二叉搜索樹中，查找元素的平均時(shí)間復(fù)雜度是？

A.O(1)

B.O(logn)

C.O(n)

D.O(n^2)

5.下列哪種數(shù)據(jù)結(jié)構(gòu)適用于實(shí)現(xiàn)優(yōu)先隊(duì)列？

A.隊(duì)列

B.棧

C.鏈表

D.堆

6.下列哪個(gè)數(shù)據(jù)結(jié)構(gòu)可以用來(lái)實(shí)現(xiàn)動(dòng)態(tài)數(shù)組？

A.隊(duì)列

B.棧

C.鏈表

D.動(dòng)態(tài)數(shù)組

7.下列哪個(gè)數(shù)據(jù)結(jié)構(gòu)可以用來(lái)實(shí)現(xiàn)動(dòng)態(tài)鏈表？

A.隊(duì)列

B.棧

C.鏈表

D.動(dòng)態(tài)數(shù)組

8.下列哪種數(shù)據(jù)結(jié)構(gòu)可以用來(lái)實(shí)現(xiàn)靜態(tài)數(shù)組？

A.隊(duì)列

B.棧

C.鏈表

D.靜態(tài)數(shù)組

9.下列哪個(gè)數(shù)據(jù)結(jié)構(gòu)可以用來(lái)實(shí)現(xiàn)靜態(tài)鏈表？

A.隊(duì)列

B.棧

C.鏈表

D.靜態(tài)數(shù)組

10.下列哪個(gè)數(shù)據(jù)結(jié)構(gòu)可以用來(lái)實(shí)現(xiàn)靜態(tài)棧？

A.隊(duì)列

B.棧

C.鏈表

D.靜態(tài)數(shù)組

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

1.在C語(yǔ)言中，使用______關(guān)鍵字來(lái)定義一個(gè)結(jié)構(gòu)體。

2.在C語(yǔ)言中，使用______關(guān)鍵字來(lái)定義一個(gè)指針。

3.在C語(yǔ)言中，使用______函數(shù)來(lái)分配內(nèi)存。

4.在C語(yǔ)言中，使用______函數(shù)來(lái)釋放內(nèi)存。

5.在C語(yǔ)言中，使用______函數(shù)來(lái)比較兩個(gè)字符串。

6.在C語(yǔ)言中，使用______函數(shù)來(lái)獲取字符串的長(zhǎng)度。

7.在C語(yǔ)言中，使用______關(guān)鍵字來(lái)聲明一個(gè)二維數(shù)組。

8.在C語(yǔ)言中，使用______關(guān)鍵字來(lái)聲明一個(gè)一維數(shù)組。

9.在C語(yǔ)言中，使用______關(guān)鍵字來(lái)聲明一個(gè)指針數(shù)組。

10.在C語(yǔ)言中，使用______關(guān)鍵字來(lái)聲明一個(gè)結(jié)構(gòu)體數(shù)組。

四、編程題（每題[20]分，共[40]分）

1.編寫一個(gè)C程序，實(shí)現(xiàn)一個(gè)簡(jiǎn)單的棧，支持入棧（push）、出棧（pop）和查看棧頂元素（peek）的功能。

```c

#include<stdio.h>

#include<stdlib.h>

#defineMAX_SIZE100

typedefstruct{

intdata[MAX_SIZE];

inttop;

}Stack;

voidinitStack(Stack*s){

s->top=-1;

}

intisEmpty(Stack*s){

returns->top==-1;

}

intisFull(Stack*s){

returns->top==MAX_SIZE-1;

}

voidpush(Stack*s,intvalue){

if(isFull(s)){

printf("Stackisfull.\n");

return;

}

s->data[++s->top]=value;

}

intpop(Stack*s){

if(isEmpty(s)){

printf("Stackisempty.\n");

return-1;

}

returns->data[s->top--];

}

intpeek(Stack*s){

if(isEmpty(s)){

printf("Stackisempty.\n");

return-1;

}

returns->data[s->top];

}

intmain(){

Stacks;

initStack(&s);

push(&s,10);

push(&s,20);

push(&s,30);

printf("Topelement:%d\n",peek(&s));

printf("Poppedelement:%d\n",pop(&s));

printf("Topelement:%d\n",peek(&s));

return0;

}

```

2.編寫一個(gè)C程序，實(shí)現(xiàn)一個(gè)簡(jiǎn)單的隊(duì)列，支持入隊(duì)（enqueue）、出隊(duì)（dequeue）和查看隊(duì)列頭元素（front）的功能。

```c

#include<stdio.h>

#include<stdlib.h>

#defineMAX_SIZE100

typedefstruct{

intdata[MAX_SIZE];

intfront;

intrear;

}Queue;

voidinitQueue(Queue*q){

q->front=q->rear=0;

}

intisEmpty(Queue*q){

returnq->front==q->rear;

}

intisFull(Queue*q){

return(q->rear+1)%MAX_SIZE==q->front;

}

voidenqueue(Queue*q,intvalue){

if(isFull(q)){

printf("Queueisfull.\n");

return;

}

q->data[q->rear]=value;

q->rear=(q->rear+1)%MAX_SIZE;

}

intdequeue(Queue*q){

if(isEmpty(q)){

printf("Queueisempty.\n");

return-1;

}

intvalue=q->data[q->front];

q->front=(q->front+1)%MAX_SIZE;

returnvalue;

}

intfront(Queue*q){

if(isEmpty(q)){

printf("Queueisempty.\n");

return-1;

}

returnq->data[q->front];

}

intmain(){

Queueq;

initQueue(&q);

enqueue(&q,10);

enqueue(&q,20);

enqueue(&q,30);

printf("Frontelement:%d\n",front(&q));

printf("Dequeuedelement:%d\n",dequeue(&q));

printf("Frontelement:%d\n",front(&q));

return0;

}

```

五、簡(jiǎn)答題（每題[10]分，共[20]分）

1.簡(jiǎn)述線性表、棧、隊(duì)列和樹的區(qū)別。

2.簡(jiǎn)述二叉搜索樹的特點(diǎn)和查找效率。

六、綜合題（每題[20]分，共[40]分）

1.編寫一個(gè)C程序，實(shí)現(xiàn)一個(gè)二叉搜索樹，支持插入、刪除和查找操作。

```c

#include<stdio.h>

#include<stdlib.h>

typedefstructTreeNode{

intvalue;

structTreeNode*left;

structTreeNode*right;

}TreeNode;

TreeNode*createNode(intvalue){

TreeNode*node=(TreeNode*)malloc(sizeof(TreeNode));

node->value=value;

node->left=NULL;

node->right=NULL;

returnnode;

}

TreeNode*insert(TreeNode*root,intvalue){

if(root==NULL){

returncreateNode(value);

}

if(value<root->value){

root->left=insert(root->left,value);

}elseif(value>root->value){

root->right=insert(root->right,value);

}

returnroot;

}

TreeNode*search(TreeNode*root,intvalue){

if(root==NULL||root->value==value){

returnroot;

}

if(value<root->value){

returnsearch(root->left,value);

}

returnsearch(root->right,value);

}

TreeNode*minValueNode(TreeNode*node){

TreeNode*current=node;

while(current&¤t->left!=NULL){

current=current->left;

}

returncurrent;

}

TreeNode*deleteNode(TreeNode*root,intvalue){

if(root==NULL){

returnroot;

}

if(value<root->value){

root->left=deleteNode(root->left,value);

}elseif(value>root->value){

root->right=deleteNode(root->right,value);

}else{

if(root->left==NULL){

TreeNode*temp=root->right;

free(root);

returntemp;

}elseif(root->right==NULL){

TreeNode*temp=root->left;

free(root);

returntemp;

}

TreeNode*temp=minValueNode(root->right);

root->value=temp->value;

root->right=deleteNode(root->right,temp->value);

}

returnroot;

}

voidinorderTraversal(TreeNode*root){

if(root!=NULL){

inorderTraversal(root->left);

printf("%d",root->value);

inorderTraversal(root->right);

}

}

intmain(){

TreeNode*root=NULL;

root=insert(root,50);

insert(root,30);

insert(root,20);

insert(root,40);

insert(root,70);

insert(root,60);

insert(root,80);

printf("Inordertraversalofthegiventree:");

inorderTraversal(root);

printf("\n");

root=deleteNode(root,20);

printf("Inordertraversalafterdeleting20:");

inorderTraversal(root);

printf("\n");

root=deleteNode(root,30);

printf("Inordertraversalafterdeleting30:");

inorderTraversal(root);

printf("\n");

root=deleteNode(root,50);

printf("Inordertraversalafterdeleting50:");

inorderTraversal(root);

printf("\n");

return0;

}

```

試卷答案如下：

一、選擇題答案及解析：

1.C。樹是一種非線性數(shù)據(jù)結(jié)構(gòu)，它由節(jié)點(diǎn)組成，每個(gè)節(jié)點(diǎn)可以有多個(gè)子節(jié)點(diǎn)。

2.B。冒泡排序的時(shí)間復(fù)雜度是O(n^2)，因?yàn)樗枰容^相鄰的元素并交換它們的位置。

3.A。鏈表適用于頻繁的插入和刪除操作，因?yàn)樗恍枰苿?dòng)其他元素。

4.B。在二叉搜索樹中，查找元素的平均時(shí)間復(fù)雜度是O(logn)，因?yàn)槊看尾檎叶紩?huì)排除一半的節(jié)點(diǎn)。

5.D。堆是一種可以用來(lái)實(shí)現(xiàn)優(yōu)先隊(duì)列的數(shù)據(jù)結(jié)構(gòu)，它保證了根節(jié)點(diǎn)的值是最小的。

6.D。動(dòng)態(tài)數(shù)組可以用來(lái)實(shí)現(xiàn)動(dòng)態(tài)數(shù)組，因?yàn)樗梢愿鶕?jù)需要擴(kuò)展或縮小數(shù)組的大小。

7.C。鏈表可以用來(lái)實(shí)現(xiàn)動(dòng)態(tài)鏈表，因?yàn)樗恍枰B續(xù)的內(nèi)存空間。

8.D。靜態(tài)數(shù)組可以用來(lái)實(shí)現(xiàn)靜態(tài)數(shù)組，因?yàn)樗诰幾g時(shí)就已經(jīng)確定了大小。

9.C。鏈表可以用來(lái)實(shí)現(xiàn)靜態(tài)鏈表，因?yàn)樗恍枰B續(xù)的內(nèi)存空間。

10.D。靜態(tài)數(shù)組可以用來(lái)實(shí)現(xiàn)靜態(tài)棧，因?yàn)樗诰幾g時(shí)就已經(jīng)確定了大小。

二、填空題答案及解析：

1.struct。在C語(yǔ)言中，使用struct關(guān)鍵字來(lái)定義一個(gè)結(jié)構(gòu)體。

2.*。在C語(yǔ)言中，使用*關(guān)鍵字來(lái)定義一個(gè)指針。

3.malloc。在C語(yǔ)言中，使用malloc函數(shù)來(lái)分配內(nèi)存。

4.free。在C語(yǔ)言中，使用free函數(shù)來(lái)釋放內(nèi)存。

5.strcmp。在C語(yǔ)言中，使用strcmp函數(shù)來(lái)比較兩個(gè)字符串。

6.strlen。在C語(yǔ)言中，使用strlen函數(shù)來(lái)獲取字符串的長(zhǎng)度。

7.int[行數(shù)][列數(shù)]。在C語(yǔ)言中，使用int[行數(shù)][列數(shù)]關(guān)鍵字來(lái)聲明一個(gè)二維數(shù)組。

8.int[列數(shù)]。在C語(yǔ)言中，使用int[列數(shù)]關(guān)鍵字來(lái)聲明一個(gè)一維數(shù)組。

9.int*。在C語(yǔ)言中，使用int*關(guān)鍵字來(lái)聲明一個(gè)指針數(shù)組。

10.struct。在C語(yǔ)言中，使用struct關(guān)鍵字來(lái)聲明一個(gè)結(jié)構(gòu)體數(shù)組。

四、編程題答案及解析：

1.棧的實(shí)現(xiàn)：

-`initStack`初始化棧，設(shè)置棧頂指針為-1。

-`isEmpty`檢查棧是否為空。

-`isFull`檢查棧是否已滿。

-`push`將元素推入棧頂。

-`pop`從棧頂彈出元素。

-`peek`返