数据结构(第二版)-模拟试题自测卷AB卷带答案1.doc

试卷一

一、选择题（本题共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，则该二叉树中最多有________个结点。
A． 2k-1 B. 2k C. 2k-1 D. 2k-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分）

1. 若经常需要对线性表进行查找操作，则最好采用________存储结构。
2. 某带头结点单链表的头指针为L，判定该单链表非空的条件________________。
3. 数据的逻辑结构包括集合、________、________和图状结构四种类型。
4. 图的两种遍历方式为：广度优先遍历和_______________。
5. 线性表的链式存储结构中的结点包含________域和________域。
6. 向一棵二叉搜索树中插入一个元素时，若元素的值小于根结点的值，则应把它插入到根结点的_______上。
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)_______________;}
}

三、应用题（本题共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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
A
D
A
B
C
B
B
D
A
C
B
D
C
B
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分）

A
B
D
E
F
G
H
C
6. （7分）

层序遍历序列: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])
{
a[j+1]=a[j];
j--;
}
a[j+1]=a[0];
}
}

试卷二
一、选择题（本题共20分,每题2分）

1.下面程序段的时间复杂度为（ ）。
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
s++;
A. O(n) B. O(n2) C. O(2*n) D. O（i*j）
2. 线性表采用链式存储时，结点的存储地址（ ）。
A．必须是不连续的 B．部分地址必须是连续的
C．连续与否均可 D．和头结点的存储地址相连续
3.若让元素1，2，3依次进栈，则出栈时的序列不可能出现的是（ ）。
A．3，2，1 B．1，2，3 C．3，1，2 D．2，1，3
4.下面说法不正确的是(　　)
A．串S1=“this_is_a_string”的长度是16。
B．串S2=“this”是串S1的子串。
C．串S3=“thisis”在串S1中的位置是1。　　
D．串S4=“a”在串S1中的位置是9。
5. 一个非空广义表的表头（ ）。
A．不可能是子表 B．只能是子表
C．只能是原子 D．可以是子表或原子
6.完全二叉树(　　)满二叉树
A． 不一定是 B．一定不是 C．一定是 D．不能确定关系
7. 用链表表示线性表的优点是（ ）
A. 便于随机存取
B. 便于插入和删除操作
C. 花费的存储空间较顺序存储少
D. 元素的物理顺序与逻辑顺序相同
8.在一个具有n个顶点的无向图中，要连通全部顶点至少需要多少条边(　　)。
A．n(n-1)/2 B．n-1 C．n D．n+1
9.下列查找方法中哪一种不适合元素的链式存储结构(　　)
　　A．顺序查找 B．分块查找 C．二分查找 D．散列查找
10.下面哪种排序方法稳定性最好(　　)。
A．希尔排序 B．冒泡排序 C．快速排序 D．堆排序
二、填空题（本题共 20分）

1. 数据的逻辑结构可以分为两大类：_________和________。
2. 在二叉树的第i层上最多有___________个结点。
3. 无向图中恰好有__________条边，才称为无向完全图。
4. 用单链表方式存储的线性表，存储每个结点需要有两个域，一个是_________，另一个是________。
5. 设二维数组A5×6的每个元素占4个字节，已知LOC（a00）=1000，则A一共占用_______字节。如果按行优先存储时，a25的起始地址是_________。
6. 3个结点的树有_______种形态，3个结点的二叉树有________种形态。
7. 一个广义表为（a，（a，b），d，e，（（i，j），k）），则该广义表的深度为________。
8. 栈的插入操作在_______进行，删除操作在_______进行。
9. 在二叉树中，结点的最大度数是_______。
10. 判定一个有向图中是否存在回路，即是否含有环，可以使用_________方法。
11. 二分查找的效率较高，但是要求查找表中的关键字_______，并且要求表的存储为________。
12. 在构造散列表的过程中，不可避免会出现冲突，通常解决它的方法有_______和_______。
13．从任何一个结点开始都能成功查找其他结点的单链表是 表。
三、应用题（本题共 50分，每题10分）

1. 一棵二叉树如右面的图所示，要求：
（1）写出对此二叉树进行中序遍历时得到的结点序列。
（2）画出由此二叉树转换得到的森林。

2. 已知图G的邻接表如下，写出从顶点O出发的深度优先和广度优先遍历的顶点序列。
0 0 2 1 3

1 0 0 2

2 0 3 0 1

3 0 2 0
3. 对于下面所示的连通图，写出由Prim算法生成的最小生成树。

4.下图所示为AOE网，求其关键路径和关键活动。

四、算法填空题（本题共10 分）

下列两个算法分别为二分查找算法和冒泡排序算法，阅读下面程序代码，填充空白位置，使算法完整。
#Define n 10
typedef int KeyType;
typedef struct
{ KeyType key;
} NodeType;
typedef NodeType SeqList[n+1];
1. int BinSearch (SeqList R,KeyType k)
{
int low=1,high=n,mid;
while(low<=high)
{ mid=(low+high)/2;
if(R[mid].key==k) return mid;
if(R[mid].key>k) ______1_____;
else ________2_______;
}
return 0;
}
2. void BubbleSort (SeqList R)
{ int i,j
Boolean exchange;
For( i=1;i<n;i++)
{exchange=false;
for(j=1;j<=n-I;j++)
if(R[j+1].key<R[j].key)
{_______3_____;
______4______;
R[j]=R[0];
________5__________
}
if (!exchange) return;
}
}
参考答案
一、选择题（本题共20分,每题2分）
1
2
3
4
5
6
7
8
9
10
B
C
C
C
D
A
b
B
C
B
二、填空题（本题共20分,每空1分）
1） 线性结构 ，非线性结构 2） 2i-1
3） n(n-1)/2 4） 数据域 ，指针域
5） 1120 ，1068 6） 2 ，5
7） 5 8） 栈顶， 栈顶
9） 2 10） 拓扑排序
11） 有序， 顺序存储 12） 开放定址法， 拉链法
13） 单循环链表

三、应用题（本题共50分）
1） DEFBAC --------8分

―――――――8分
2）深度优先遍历：0231 ―――――6分
广度优先遍历：0213 ――――6分
3）
--------12分
4）
顶点
ve
vl
活动
e
l
l-e
V1
0
0
a1
0
1
1
V2
3
4
a2
0
0
0
V3
2
2
a3
3
4
1
V4
6
6
a4
3
4
1
V5
6
7
a5
2
2
0
V6
8
8
a6
2
5
3

a7
6
6
0

a8
6
7
1
---------6分
关键路径是：V1-V3-V4-V6 ---------2分
关键活动是：a2,a5,a7 ---------2分

四、算法填空题（本题共10分,每空2分）
1） high=mid-1; ---------2分
2） low= mid+1; ---------2分
3） R[0]=R[j+1]; ---------2分
4） R[j+1]=R[j]; ---------2分
5） exchange=true; ---------2分