数据结构期末考试试卷
仙人掌的作文-班组建设汇报材料
数据结构期末试卷
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) 线性结构
(A) 线性表
(A) 2i
(B)
树型结构
(B) 栈
(B) 2
i
(C) 图型结构
(C) 队列
(C) 2
i-1
(B) p=p->next
(D) 集合
(D) 树
(D) 2i-1
3．数组的逻辑结构不同于下列（ ）的逻辑结构。
4．二叉树中第i(i≥1)层上的结点数最多有（ ）个。
5．设指针变量p指向单链表结点A，则删除结点A的后继结点B需要的操作为（ ）。
(A) p->next=p->next->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
(A) 100
(A)
3
(A) 4
(A) 冒泡排序
(B) 4
(B) 40
(B) 4
(B) 5
(B) 快速排序
(C) 3
(C)
55
(C) 5
(C) 6
(C) 堆排序
(D) 2
(D) 80
(D) 1
(D) 7
(D) 希尔排序
7．将10阶对称矩阵压缩存储到一维数组A中，则数组A的长度最少为（ ）。
8．设结点A有3个兄弟结点且结点B为结点A的双亲结点，则结点B的度数数为（ ）。
9．根据二叉树的定义可知二叉树共有（ ）种不同的形态。
10. 10.
设有以下四种排序方法，则（ ）的空间复杂度最大。
二、填空题
1. 设顺序循环
队列Q[0：m-1]的队头指针和队尾指针分别为F和R，其中队头指针F指向
当前队头元素的前一个
位置，队尾指针R指向当前队尾元素所在的位置，则出队列的
语句为F =___________;。
2. 设线性表中有n个数据元素，则在顺序存储结构上实现顺序查找的平均时间复杂度为
__
___，在链式存储结构上实现顺序查找的平均时间复杂度为_________。
3. 设一棵二叉
树中有n个结点，则当用二叉链表作为其存储结构时，该二叉链表中共有
________个指针域，_
_______个空指针域。
4. 设指针变量p指向单链表中结点A，指针变量s指向被插入的结点
B，则在结点A的后
面插入结点B的操作序列为 s->next=p->next;
s->next=s_________________。
5. 设无向图G中有n个顶点和e条边
，则其对应的邻接表中有_________个表头结点和
_________个表结点。
6.
设无向图G中有n个顶点e条边，所有顶点的度数之和为m，则e和m有______关系。
7
设一棵二叉树的前序遍历序列和中序遍历序列均为ABC，则该二叉树的后序遍历序列
为_______
___。
8 设一棵完全二叉树中有21个结点，如果按照从上到下、从左到右的顺序从1开始
顺序
编号，则编号为8的双亲结点的编号是___________，编号为8的左孩子结点的编号是<
br>_____________。
9.
下列程序段的功能实现子串t在主串s中位置的算法，要求在下划线处填上正确语句。
int
index(char s[ ], char t[ ])
{
i=j=0;
while(i
}
10
设一个连通图G中有n个顶点e条边，则其最小生成树上有________条边。
三
判断题
1. 顺序存储方式的优点是存储密度大，且插入、删除运算效率高。（ ）
2. 若输入序列为1，2，3，4，5，6，用栈可以输出序列1，5，4，6，2，3。（ ）
3. 数据的逻辑结构是指数据的各数据项之间的逻辑关系。（ ）
4.
中序遍历一棵二叉排序树的结点就可得到排好序的结点序列。（ ）
5.
在n个结点的无向图中，若边数大于n-1，则该图必是连通图。（ ）
6.
归并排序在任何情况下都比所有简单排序速度快。（ ）
7.
栈和队列的存储方式，既可以是顺序方式，又可以是链式方式。（ ）
8.
完全二叉树中，若一个结点没有左孩子，则它必是树叶。（ ）
9.
不同的求最小生成树的方法最后得到的生成树是相同的。（ ）
10. 采用线性探测法处理散列时
的冲突，当从哈希表删除一个记录时，不应将这个记录的所
在位置置空，因为这会影响以后的查找。（
）
四、应用题
1．设完全二叉树的顺序存储结构中存储数据ABCDE，要求给出该二叉树
的链式存储结构
并给出该二叉树的前序、中序和后序遍历序列。
2．设给定一个权值集合W=
(3，5，7，9，11)，要求根据给定的权值集合构造一棵哈夫曼树
并计算哈夫曼树的带权路径长度
WPL。
3．设一组初始记录关键字序列为(19，21，16，5，18，23)，要求
给
出以19为基准的一趟快速排序结果以及第2趟直接选择排序
后的结果。
<
br>4．设一组初始记录关键字集合为(25，10，8，27，32，68)，散列表的长度为8，散列函数
H(k)=k mod 7，要求分别用线性探测和链地址法作为解决冲突的方法设计哈希表。
5．设无向图G（所右图所示），要求给出该图的深度优先和广度优先遍历的序列并给出该图
的最小生
成树。
五、算法设计题
1. 设计判断单链表中结点是否关于中心对称算法。
2. 设计在链式存储结构上设计直接插入排序算法
3 设计算法实现按层次遍历（遍历
操作定义为打印结点的data域）二叉树。二叉树的存
储结构描述同上题，在算法中可能要使用一个队
列Q，其相关操作:（编程题）
Iniqueue(Q) 置队列空操作
Empty(Q)
判空函数
Enqueue(Q,x) 入队列操作
Dlqueue(Q) 出队列操作
4 设计判断一棵二叉树是否是二叉排序树的算法。
数据结构模拟试卷（B卷）参考答案
一、选择题
1.C
6.C
2.C
7.C
3.D
8.B
4.C
9.B
5.A
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
三 判断题
h
0
1. X 2 X. 3 . X 4
. √ 5 . X 6 . X 7. √ 8 . √ 9. √ 10. √
h
1
8
四、应用题
h
2
1.
链式存储结构略，前序ABDEC，中序DBEAC，后序DEBCA
h
。
10
3
2. 哈夫曼树略，WPL=78
0
12
，16
3
，21
4
，19
5
，18
6
，23)
7
3.
(18,5,16,19,21,23)，(5
4.
线性探测：
81025322768
链地址法：
h
6
27
(5，6)，(5,6)}
五、算法设计题
1. 设计判断单链表中结点是否关于中心对称算法。
typedef struct {int s[100]; int top;} sqstack;
h
4
2532
h
5
68
5. 深度：125364，广度：123456，最小生成树T的边集为E={(1，4)，(
1，3)，(3，5)，
int
lklistsymmetry(lklist *head)
{
sqstack
stack; = -1; lklist *p;
for(p=head;p!=0;p=p->next) {++;
stack.s[]=p->data;}
for(p=head;p!=0;p=p->next) if (p->data==stack.s[])
=-1;
else return(0);
return(1);
}
2. 在链式存储结构上设计直接插入排序算法
void
straightinsertsort(lklist *&head)
{
lklist *s,*p,*q; int t;
if (head==0 ||
head->next==0) return;
else
for(q=head,p=head->next;p!=0;p=q->next)
{
for(s=head;s!=q->next;s=s->next) if
(s->data>p->data) break;
if(s==q->next)q=p;
else{q->next=p->next;
p->next=s->next;
t=p->data;p->data=s->data;s->data=t;}
}
}
s->next=p;
4.
设计判断一棵二叉树是否是二叉排序树的算法。
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);
inorder(bt->rchild);}
}
if(minnum>bt->key)flag=0;
minnum=bt->key;