试卷一

试卷一

一、选择题（本题共30分,每题2分）

1. 计算机识别、存储和加工处理的对象被统称为________。

A. 数据 B. 数据元素 C. 数据结构 D. 数据类型

2. 已知一栈的进栈序列为：1234，则下列哪个序列为不可能的出栈序列________。

A．1234 B．4321 C．2143 D．4123 3. 链表不具有的特点是________。

A. 随机访问 B. 不必事先估计所需存储空间大小 C. 插入与删除时不必移动元素 D. 所需空间与线性表长度成正比

4. 设InitQueue(Q)、EnQueue(Q,e)、DeQueue(Q,e)分别表示队列初始化、入队和出队的操作。经过以下队列操作后，队头的值是________

InitQueue(Q); EnQueue(Q,a); EnQueue(Q,b); EnQueue(Q,c); DeQueue(Q,x) A. a B. b C.NULL D.x

5.在一个单链表HL中，若要删除由指针q所指向结点的后继结点，则执行________。

A．p=q->next; p->next=q->next;free(p); B．p=q->next; q->next=p; free(p);

C．p=q->next; q->next=p->next; free(p);

D．q->next=q->next->next; q->next=q; free(p);

6. 一个顺序表第一个元素的存储地址是100,每个元素占2个存储单元，则第5个元素的地址是________。

A．110 B．108 C．100 D．120

7. 在一个长度为n的顺序存储的线性表中，在其第i个位置插入一个新元素时，需要移动元素的次数是________。

A. n-i B. n-i+1 C. n-i-1 D. i

8．下面关于线性表的叙述错误的是________。

A. 线性表采用顺序存储必须占用一片连续的存储空间 B. 线性表采用链式存储不必占用一片连续的存储空间 C. 线性表采用链式存储便于插入和删除操作的实现 D. 线性表采用顺序存储便于插入和删除操作的实现

9. Push(e)表示e进栈，Pop(e)表示退栈并将栈顶元素存入e。下面的程序段可以将A,B的值交换的操作序列是________。

A.Push(A) Push(B) Pop(A) Pop(B) B.Push(A) Push(B) Pop(B) Pop(A) C.Push(A) Pop(B) Push(B) Pop(A) D.Push(B) Pop(A) Push(A) Pop(B)

10.下列查找方法中哪一种不适合元素的链式存储结构________。

A．顺序查找 B．分块查找 C．二分查找 D．散列查找

11. 下列排序算法中，不能保证每趟排序至少能将一个元素放到其最终的位置上的算法是________。

A. 快速排序 B.希尔排序 C.堆排序 D.冒泡排序 12. 设一棵二叉树的深度为k，则该二叉树中最多有________个结点。

kk-1k

A． 2k-1 B. 2 C. 2 D. 2-1

13. 下列四个选项中，能构成堆的是________。

A.75,65,30,15,25,45,20,10 B.75,65,45,10,30,25,20, 15 C.75,45,65,30,15,25,20,10 D.75,45,65,10,25,30,20,15

14. 在一个具有n个顶点的无向图中，要连通全部顶点至少需要多少条边________。

A．n(n-1)/2 B．n-1 C．n D．n+1 15.栈和队列的共同特点是________。

A. 都是操作受限的线性表 B.都是先进后出 C. 都是后进先出 D.无共同点

二、填空题（本题共 10分，每空1分）

若经常需要对线性表进行查找操作，则最好采用________存储结构。

某带头结点单链表的头指针为L，判定该单链表非空的条件________________。 数据的逻辑结构包括集合、________、________和图状结构四种类型。 图的两种遍历方式为：广度优先遍历和_______________。

线性表的链式存储结构中的结点包含________域和________域。 向一棵二叉搜索树中插入一个元素时，若元素的值小于根结点的值，则应把它插入到根结点的_______上。

7. 下面程序段的功能实现数据x进栈，要求在下划线处填上正确的语句。

typedef struct {int stack[100]; int top;} seqstack; void push(seqstack *s,int x) {

if (s->top==99) printf(“overflow”);

else {_____(1)_______________;__(2)_______________;} }

1. 2. 3. 4. 5. 6.

三、应用题（本题共40分）

1． 设散列表长度为11，散列函数h(key)=key % 11。给定的关键字为1，13，12，34，38，33，2，22。试画出用线性探查法解决冲突时所构造的散列表。并计算在查找成功时候的平均查找长度。（6分）

2．有一组权值14、21、32、15、28，画出哈夫曼树，并计算其WPL。（6分）

3．已知图G=(V,E)，其中V={1,2,3,4,5}, E={(1,2),(1,3),(1,4),(2,3),(2,5),(3,4),(4,5)}。要求完成如下操作：（6分）

（1）写出图的邻接矩阵

（2）写出采用邻接矩阵存储时，从顶点1出发的广度优先搜索遍历序列。

4．已知序列{503，87，512，61，908，170，897，275，653，462}，分别写出执行下列排序算法的各趟排序结束时，关键字序列的状态：（10分）

（1）直接插入排序 （2）基数排序

5．对于下面所示的连通图，写出由Prim算法生成的最小生成树。（5分）

6. 将下面的树转化为一棵二叉树,并写出对二叉树进行层序遍历的序列。（7分）

A

B C D

E F G H

四、算法题（本题共20 分）

1．完成中序遍历二叉树。

Typedef struct node {

Char data;

Struct node *lchild;

Struct node *rchild;

}BTreeNode,*LinkBtree;

Void InOrder(LinkBtree Bt_pointer) {

If(Bt_pointer!=NULL)

{ _________(1)_____________; __________(2)_____________; __________(3)____________; } }

2.完成二分查找算法：

#Define n 10

typedef int KeyType; typedef struct {

KeyType key; } NodeType;

Typedef NodeType SeqList[n+1]; int BinSearch (SeqList R,KeyType k) {

int low=1,high=n,mid; while(_____（4）_______) { mid=(low+high)/2;

if(R[mid].key==k) return mid; if(R[mid].key>k) _____（5）_____;

else ________（6）_______; }

return 0;

}

3.编写算法实现直接插入排序。（8分）

参考答案

一、选择题（本题共30分,每题2分） 1 A 2 D 3 A 4 B 5 C 6 B 7 B 8 D 9 A 10 C 11 B 12 D 13 C 14 B 15 A 二、填空题（本题共10分，每空1分） 1） 顺序 2）L->next!=NULL 3） 线性结构 树形结构 4） 深度优先遍历 5） 数据 指针 6）左子树 7） s->top++ s->stack[s->top]=x

三、应用题（本题共40分） 1、（6分）

H(1)=1 H(13)=2

H(12)=1 冲突 ， H1=2 冲突， H2=3

H(34)=1 冲突 ， H1=2 冲突， H2=3 冲突， H3=4 H(38)=5 H(33)=0

H(2)=2 冲突 ， H1=3 冲突， H2=4 冲突， H3=5 冲突， H4=6

H(22)=0 冲突 ， H1=1 冲突， H2=2 冲突， H3=3 冲突， H4=4 冲突，H5=5 冲突，

H6=6 冲突， H7=7

ASL=(1+1+3+4+1+1+5+8)/8=24/8=3

2、（6分）

110 49 61 21 28 29 32 14 15

Wpl=249

3、图的邻接矩阵：（3分） 广度优先序列： 1 2 3 4 5（3分）

0 1 1 1 0 1 0 1 0 1 1 1 0 1 0 1 0 1 0 1 0 1 0 1 0

4、 1）（503）87 512 61 908 170 897 275 653 462（5分）

（87 503）512 61 908 170 897 275 653 462 （87 503 512）61 908 170 897 275 653 462 （61 87 503 512）908 170 897 275 653 462 （61 87 503 512 908）170 897 275 653 462 （61 87 170 503 512 908）897 275 653 462 （61 87 170 503 512 897 908）275 653 462 （61 87 170 275 503 512 897 908）653 462 （61 87 170 275 503 512 653 897 908）462 （61 87 170 275 462 503 512 653 897 908） 2）第一趟： 170 61 512 462 503 653 275 87 897 908（5分） 第二趟： 503 908 512 653 61 462 170 275 87 897 第三趟： 61 87 170 275 462 503 512 653 897 908 5、（5分）

152

4A 3

6. （7分）

E

B C D F G H

层序遍历序列:ABECFDGH 四、算法题（本题共20分）

1、 （1）InOrder (Bt_pointer ->lchild); （2分）

(2) printf(“%c”, Bt_pointer ->data);（2分） (3) InOrder (Bt_pointer ->rchild); （2分）

2、 （4） low<=high （5）high=mid-1; （6） low= mid+1; （6分） 3、 void InsertSort(int a[],int n) （8分） {

int i,j;

for(i=2;i<=n;i++) {

a[0]=a[i]; j=i-1;

while(a[0]

a[j+1]=a[j]; j--;

}

a[j+1]=a[0]; } }

层序遍历序列:ABECFDGH 四、算法题（本题共20分）

1、 （1）InOrder (Bt_pointer ->lchild); （2分）

(2) printf(“%c”, Bt_pointer ->data);（2分） (3) InOrder (Bt_pointer ->rchild); （2分）

2、 （4） low<=high （5）high=mid-1; （6） low= mid+1; （6分） 3、 void InsertSort(int a[],int n) （8分） {

int i,j;

for(i=2;i<=n;i++) {

a[0]=a[i]; j=i-1;

while(a[0]

a[j+1]=a[j]; j--;

}

a[j+1]=a[0]; } }

本文来源：https://www.bwwdw.com/article/r66x.html