延边大学2020-2021学年第2学期《数据结构》期末考试试卷（A卷）含标准答案

延边大学2020-2021学年第2学期《数据结构》期末考试试卷（A卷）含标准答案考试说明1.本试卷适用于计算机科学与技术、软件工程等相关专业本科学生，考试时长120分钟，满分100分；2.考试方式为闭卷，禁止携带教材、笔记及电子设备，答题需使用黑色签字笔或钢笔；3.答案需写在答题纸对应区域，试卷上作答无效，答题结束后将试卷与答题纸一并上交。一、单项选择题（共15小题，每小题2分，共30分）（每题只有一个正确答案，多选、错选、不选均不得分）数据结构中，与所使用的计算机无关的是（）

A.逻辑结构B.存储结构C.物理结构D.以上都不是

算法的时间复杂度是指（）

A.执行算法程序所需要的时间B.算法程序的长度

C.算法执行过程中所需要的基本运算次数D.算法程序中的指令条数

线性表的顺序存储结构中，存储地址是（）

A.连续的B.不连续的C.部分连续的D.随机的

单链表中，要实现删除某一指定结点，需要找到该结点的（）

A.前驱结点B.后继结点C.头结点D.尾结点

栈的特点是（）

A.先进先出B.先进后出C.随机存取D.顺序存取

队列的特点是（）

A.先进先出B.先进后出C.随机存取D.顺序存取

二叉树的第k层上，最多有（）个结点（k≥1）

A.2^kB.2^(k-1)C.2^k-1D.k

在图的邻接矩阵存储结构中，对于无向图，矩阵是（）

A.对称矩阵B.非对称矩阵C.对角矩阵D.零矩阵

下列排序算法中，时间复杂度为O(nlogn)的是（）

A.冒泡排序B.插入排序C.快速排序D.选择排序

哈希表的查找效率主要取决于（）

A.哈希函数B.处理冲突的方法C.装填因子D.以上都是

一棵二叉树的前序遍历序列为ABCDEF，中序遍历序列为CBAEDF，则后序遍历序列为（）

A.CBEFDAB.FEDCBAC.CBEDFAD.不确定

在图的遍历中，深度优先搜索（DFS）使用的辅助数据结构是（）

A.栈B.队列C.链表D.数组

下列关于二叉排序树的说法，错误的是（）

A.左子树所有结点值小于根结点值B.右子树所有结点值大于根结点值

C.中序遍历可得到有序序列D.任意二叉树都可作为二叉排序树顺序查找的时间复杂度为（）

A.O(n)B.O(logn)C.O(nlogn)D.O(1)

算法的基本特征不包括（）

A.有穷性B.确定性C.可行性D.无限性

二、填空题（共10小题，每小题2分，共20分）数据结构的三个基本要素是数据的逻辑结构、__________和数据的运算。线性表的两种主要存储结构是顺序存储结构和__________。栈和队列都是特殊的线性表，栈的插入和删除操作在__________进行，队列的插入在队尾、删除在队头进行。二叉树的遍历方式主要有前序遍历、中序遍历和__________三种。图的存储结构主要有邻接矩阵和__________两种。排序算法中，稳定排序的特点是__________。哈希函数的构造方法主要有直接定址法、__________、平方取中法等。一棵二叉树有10个度为2的结点，则该二叉树的叶子结点数为__________。在图的遍历中，广度优先搜索（BFS）使用的辅助数据结构是__________。算法的时间复杂度和空间复杂度统称为算法的__________。三、简答题（共4小题，每小题8分，共32分）简述线性表顺序存储结构和链式存储结构的优缺点。简述栈和队列的区别与联系。简述二叉树的定义及其基本性质。简述快速排序算法的基本思想及执行过程。四、算法设计题（共2小题，每小题9分，共18分）设计一个算法，实现单链表的反转（要求不使用额外的链表空间，时间复杂度为O(n)）。设计一个算法，实现二叉树的层序遍历（要求输出每一层的结点值）。标准答案及评分标准一、单项选择题（每小题2分，共30分）A2.C3.A4.A5.B6.A7.B8.A9.C10.D11.A12.A13.D14.A15.D二、填空题（每小题2分，共20分）存储结构（物理结构）2.链式存储结构3.栈顶4.后序遍历5.邻接表

6.相同关键字的元素在排序后相对位置不变7.除留余数法（或数字分析法）8.119.队列10.复杂度

三、简答题（每小题8分，共32分）参考答案：

（1）顺序存储结构优点：①存储密度大，节省存储空间；②可随机存取任意元素，访问速度快。（4分）

（2）顺序存储结构缺点：①插入和删除操作需要移动大量元素，效率低；②存储空间固定，难以动态扩展。（2分）

（3）链式存储结构优点：①插入和删除操作灵活，无需移动元素；②存储空间可动态分配，扩展性强。（2分）

（4）链式存储结构缺点：①存储密度小，占用额外空间存储指针；②不能随机存取元素，访问效率低。（2分）

（评分标准：答出核心要点即可得分，表述合理酌情给分）

参考答案：

（1）联系：①栈和队列都是特殊的线性表，都属于线性结构；②都可以通过顺序存储或链式存储实现；③都可用于算法设计中的辅助数据结构。（4分）

（2）区别：①操作规则不同：栈是先进后出（LIFO），队列是先进先出（FIFO）；②插入和删除位置不同：栈的插入和删除都在栈顶进行，队列的插入在队尾、删除在队头进行；③应用场景不同：栈常用于递归、表达式求值等，队列常用于任务排队、广度优先搜索等。（4分）

（评分标准：答出核心要点即可得分，表述合理酌情给分）参考答案：

（1）定义：二叉树是一种特殊的树形结构，每个结点最多有两个子树，分别称为左子树和右子树，且左右子树有严格的顺序之分。（3分）

（2）基本性质：①二叉树第k层（k≥1）最多有2^(k-1)个结点；②深度为k的二叉树最多有2^k-1个结点；③对于任意二叉树，叶子结点数=度为2的结点数+1；④具有n个结点的完全二叉树，深度为⌊log₂n⌋+1。（5分）

（评分标准：定义准确得3分，性质答出3条及以上得5分，表述合理酌情给分）

参考答案：

（1）基本思想：通过一趟排序将待排序列分割成两个独立的子序列，其中一个子序列的所有元素均小于等于基准元素，另一个子序列的所有元素均大于等于基准元素，然后分别对两个子序列继续进行排序，直至整个序列有序。（4分）

（2）执行过程：①选择基准元素（通常选序列第一个元素或中间元素）；②划分序列：将小于等于基准元素的元素移到基准元素左侧，大于等于基准元素的元素移到右侧；③递归排序：对左右两个子序列分别重复上述步骤，直至子序列长度为1或0。（4分）

（评分标准：基本思想表述清晰得4分，执行过程描述完整得4分，表述合理酌情给分）四、算法设计题（每小题9分，共18分）参考答案（伪代码）：

//定义单链表结点结构

typedefstructNode{

intdata;

structNode*next;

}Node;

//反转单链表函数

Node*reverseList(Node*head){

Node*prev=NULL;//前驱结点

Node*curr=head;//当前结点

Node*next=NULL;//后继结点

while(curr!=NULL){

next=curr->next;//保存后继结点

curr->next=prev;//反转当前结点指针

prev=curr;//前驱结点后移

curr=next;//当前结点后移

}

returnprev;//新的头结点

}

（评分标准：结点结构定义正确得2分，算法逻辑清晰、实现反转功能得6分，时间复杂度符合要求得1分，表述合理酌情给分）

参考答案（伪代码）：

//定义二叉树结点结构

typedefstructTreeNode{

intdata;

structTreeNode*left;

structTreeNode*right;

}TreeNode;

//二叉树层序遍历函数

voidlevelOrder(TreeNode*root){

if(root==NULL)return;

Queue*queue=initQueue();//初始化队列

enqueue(queue,root);//根结点入队

while(!isEmpty(queue)){

intsize=queueSize(queue);//当前层结点数

for(inti=0;i<size;i++){

TreeNode*node=dequeue(queue);//出队

printf("%d",node->data);//输出结点值

if(node->left!=NULL)enqueue(queue,node->left);//左子结点入队

if(node->right!=NULL)enqueue(queue,node->right);//右子结点入队