《数据结构》模拟试卷1

本文格式为Word版，下载可任意编辑——《数据结构》模拟试卷1《数据结构》A卷（2023）

一、简答题（15分，每题3分）1.简要说明算法与程序的区别。

2.在哈希表中，发生冲突的可能性与哪些因素有关？为什么？3.说明在图的遍历中，设置访问标志数组的作用。

4.说明以下三个概念的关系：头指针，头结点，首元素结点。5.在一般的顺序队列中，什么是假溢出？怎样解决假溢出问题？

二、判断题（10分，每题1分）正确在括号内打√，错误打×()（1）广义表(((a),b),c)的表头是((a),b)，表尾是(c)。()（2）在哈夫曼树中，权值最小的结点离根结点最近。()（3）基数排序是高位优先排序法。

()（4）在平衡二叉树中，任意结点左右子树的高度差（绝对值）不超过1。()（5）在单链表中，给定任一结点的地址p，则可用下述语句将新结点s插入结点p的后面：p->next=s;s->next=p->next;

()（6）抽象数据类型（ADT）包括定义和实现两方面，其中定义是独立于实现的，定义仅给出一个ADT的规律特性，不必考虑如何在计算机中实现。()（7）数组元素的下标值越大，存取时间越长。

()（8）用邻接矩阵法存储一个图时，在不考虑压缩存储的状况下，所占用的存储空间大小只与图中结点个数有关，而与图的边数无关。

()（9）拓扑排序是按AOE网中每个结点事件的最早发生时间对结点进行排序。

()（10）长度为1的串等价于一个字符型常量。

三、单项选择题（10分,每题1分）

1．排序时扫描待排序记录序列，顺次比较相邻的两个元素的大小，逆序时就交换位置。这是哪种排序方法的基本思想？A.堆排序B.直接插入排序C.快速排序D.冒泡排序2．已知一个有向图的邻接矩阵表示，要删除所有从第i个结点发出的边，应当：A.将邻接矩阵的第i行删除B.将邻接矩阵的第i行元素全部置为0C.将邻接矩阵的第i列删除D.将邻接矩阵的第i列元素全部置为0

3．有一个含头结点的双向循环链表，头指针为head,则其为空的条件是：A.head->priro==NULLB.head->next==NULL

C.head->next==headD.head->next->priro==NULL

4.在顺序表(3,6,8,10,12,15,16,18,21,25,30)中，用折半法查找关键码值11，所需的关键码比较次数为：

A.2B.3C.4D.55.以下哪一个不是队列的基本运算？

A.从队尾插入一个新元素B.从队列中删除第i个元素C.判断一个队列是否为空D.读取队头元素的值

6.在长度为n的顺序表的第i个位置上插入一个元素（1≤i≤n+1），元素的移动次数为：

A.n–i+1B.n–iC.iD.i–1

7．对于只在表的首、尾两端进行插入操作的线性表，宜采用的存储结构为:A.顺序表B.用头指针表示的循环单链表C.用尾指针表示的循环单链表D.单链表

8．对包含n个元素的哈希表进行查找，平均查找长度为：

A.O(log2n)B.O(n)C.O(nlog2n)D.不直接依靠于n

9．将一棵有100个结点的完全二叉树从根这一层开始，每一层从左到右依次对结点进行编号，根结点编号为1，则编号最大的非叶结点的编号为：A.48B.49C.50D.51

10．某二叉树结点的中序序列为A、B、C、D、E、F、G，后序序列为B、D、C、A、F、G、E，则其左子树中结点数目为：

A.3B.2C.4D.5

四、填空题（10分，每空1分）

1．填空完成下面一趟快速排序算法：

intQKPass(RecordTyper[],intlow，inthigh){

x=r[low]；while(low,,,,

,,,,,}

2．（6分）对以下关键字序列建立哈希表：（SUN,MON,TUE,WED,THU,FRI,SAT）,哈希函数为H(K)=（K中最终一个字母在字母表中的序号）MOD7。用线性探测法处理冲突，要求构造一个装填因子为0.7的哈希表，并计算出在等概率状况下查找成功的平均查找长度。

3.（6分）将关键字序列（3，26，12，61，38，40，97，75，53，87）调整为大根堆。4．（4分）已知权值集合为：{5，7，2，3，6，9}，要求给出哈夫曼树，并计算其带权路径长度WPL。

六、算法分析题（10分）

阅读下面程序，并回复有关问题。其中BSTree为用二叉链表表示的二叉排序树类型。

（1）简要说明程序功能。（5分）

（2）n个结点的满二叉树的深度h是多少？（3分）

（3）假设二叉排序树*bst是有n个结点的满二叉树,给出算法的时间繁杂度。

（2分）

intProc(BSTree*bst,KeyTypeK){

BSTreef,q,s;

s=(BSTree)malloc(sizeof(BSTNode));

s->key=K;s->lchild=NULL;s->rchild=NULL;if(*bst==NULL){*bst=s;return1;}f=NULL;q=*bst;while(q!=NULL){

if(Kkey)

{f=q;q=q->lchild;}else

{f=q;q=q->rchild;}}

if(Kkey)f->lchild=s;elsef->rchild=s;return1;}

七、算法设计题（25分）

1．已知一个带头结点的整数单链表L，要求将其拆分为一个正整数单链表L1和一个负整数单链表L2。（9分）

2．无向图采用邻接表存储结构，编写算法输出图中各连通分量的结点序列。（8分）

3．编写一个建立二叉树的算法，要求采用二叉链表存储结构。（8分）

《数据结构》期中卷（2023）

一、简答题（10分，每题5分）

1．顺序存储结构和链式存储结构各有哪些优缺点？

2．简述栈和队列的共同点和不同点。它们与线性表有什么关系？

二、判断题（10分，每题2分）正确在括号内打√，错误打×

()（1）顺序存储结构只能用来存放线性结构，链式存储结构只能用来存放非线性结构。

()（2）三元组表相当于一个由若干三元组构成的顺序表。

()（3）广义表的表头是表中第一个元素，表尾是表中最终一个元素。

()（4）将一棵树转换为二叉树表示后,该二叉树的根结点一定没有右子树。()（5）哈夫曼树中没有度为1的结点。

三、单项选择题（10分,每题2分）

1．下面关于串的表达中，哪一个是不正确的？

A.串是字符的有限序列B.空串是由空格构成的串

C.模式匹配是串的重要运算D.串既可顺序存储，也可采用链式存储

2．将一棵有100个结点的完全二叉树从根这一层开始，每一层从左到右依次对结点进行编号，根结点编号为1，则编号为49的结点的左孩子的编号为：A.98B.99C.50D.48

3．栈S最多能容纳4个元素。现有6个元素按A、B、C、D、E、F的顺序进栈,

问以下哪一个序列是可能的出栈序列？

A.E、D、C、B、A、FB.B、C、E、F、A、DC.C、B、E、D、A、FD.A、D、F、E、B、C

4．有一个含头结点的单链表，头指针为head,则判断其是否为空的条件为：A.head==NULLB.Head->next==NULLC.head->next==headD.Head!=NULL

5．在以下存储形式中，哪一个不是树的存储形式？A.双亲表示法B.孩子链表表示法C.孩子兄弟表示法D.顺序存储表示法

四、填空题（15分）

填空完成下面中序遍历二叉树的非递归算法：voidInOrder（BiTreeroot）{

InitStack(p=_________;

while(_____________||!IsEmpty(S)){

while(p!=NULL)

{

Push(p=______________;

}

if(_______________){

Pop(Visit(p->data);

p=_______________;

}

}}

五、构造题（15分,每题5分）

1.已知一棵树如图1所示,请将该树转化为二叉树。

2023级《数据结构》试卷A参考答案与评分标准

一、简答题（15分，每题3分）

1.算法是解决特定问题的操作序列，可以用多种方式描述。程序是算法在计算机中的实现，与具体的计算机语言有关。

2.主要与哈希函数、装填因子α有关。假使用哈希函数计算的地址分布均匀，则冲突的

可能性较小，假使装填因子α较小，则哈希表较稀疏，发生冲突的可能性较小。3.图中结点可能有多个前驱，设置访问标志数组主要是为了避免重复访问同一个结点。4.头指针指向头结点，头结点的后继域指向首元素结点。

5.当队尾到达数组最终一个单元时，就认为队满，但此时数组前面可能还有空单元，因

此叫假溢出。解决的方法是采用循环队列，即令最终一个单元的后继是第一个单元。

二、判断题（10分，每题1分）

（1）(√)（2）(×)（3）(×)（4）(√)（5）(×)（6）(√)（7）(×)（8）(√)（9）(×)（10）(×)

三、单项选择题（10分,每题1分）

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

四、填空题（10分，每空1分）

1．highlowlowhigh2.S->next=R->next；R->next=S；3．时间空间4．A[2,3]5．2h-1

五、构造题（20分）

1．（4分）

2．（6分）

012345

SUNMONTHUFRIWEDTUE

ASLsucc=(1×4+2×2+3)/7=11/7

3.（6分）

6SAT

7

8

9

4．（4分）已知权值集合为：{5，7，2，3，6，9}，要求给出哈夫曼树，并计算其带权路径长度WPL。

WPL=2×(9+6+7)+3×5+4×(2+3)=79

六、算法分析题（10分）

解：

（1）在二叉排序树中插入关键字为K的结点

（2）h=log2(n+1)或h=[log2n]+1（方括号表示向下取整）（3）O(log2(n+1))或O(log2n)

七、算法设计题（25分）

（答案略）

试卷成绩分析表

填表日期：年月日课程名称数据结构课程类型必修院系、年级、专业、班级命题人及所在院系阅卷人及所在院系计算科学系2023级计算科学与技术专业