华东师范大学《数据结构》2024-2025学年第一学期期末试卷

华东师范大学《数据结构》2024-2025学年第一学期期末试卷考试科目：数据结构考试时间：110分钟满分：100分年级：__________专业：__________学号：__________姓名：__________得分：__________注意事项：1.答题前请填写个人信息，字迹清晰、工整；2.所有答案均写在答题纸上，写在试卷上无效；3.考试结束后，将试卷、答题纸一并交回；4.本试卷涵盖课程核心知识点，侧重基础应用与综合能力考查。一、单项选择题（每题2分，共20分）1.下列数据结构中，属于非线性结构的是（）A.栈B.队列C.二叉树D.顺序表2.若一个栈的入栈序列为1、2、3、4、5，且出栈序列的第一个元素为5，则出栈序列的最后一个元素不可能是（）A.1B.2C.3D.43.对于循环队列，下列说法正确的是（）A.队头指针一定小于队尾指针B.队尾指针一定小于队头指针C.队头指针与队尾指针可能相等D.以上说法均不正确4.在单链表中，删除一个节点时，需要修改指针的个数是（）A.1B.2C.3D.45.已知一棵二叉树的前序遍历序列为ABCDE，中序遍历序列为BADCE，则其后序遍历序列为（）A.BEDCAB.EDBCAC.BDECAD.EDCBA6.下列排序算法中，时间复杂度不受数据初始状态影响，始终为O(n²)的是（）A.冒泡排序B.快速排序C.堆排序D.归并排序7.若要快速查找有序表中的元素，最适合的查找方法是（）A.顺序查找B.二分查找C.哈希查找D.二叉排序树查找8.关于哈希表，下列说法错误的是（）A.哈希表的查找效率与哈希函数有关B.哈希冲突不可避免C.链地址法可以解决哈希冲突D.哈希表的空间复杂度一定为O(n)9.一棵完全二叉树共有100个节点，则其叶子节点的个数为（）A.49B.50C.51D.5210.下列关于图的说法，正确的是（）A.无向图的邻接矩阵一定是对称的B.有向图的邻接表中，每个节点的出度等于其邻接链表的长度C.图的深度优先遍历是一种层次遍历D.连通图的最小生成树一定唯一二、填空题（每空1分，共15分）1.数据结构的三要素是__________、__________和__________。2.栈的操作特性是__________，队列的操作特性是__________。3.单链表中，头指针的作用是__________，头节点的作用是__________。4.二叉树的三种遍历方式分别是前序遍历、中序遍历和__________。5.排序算法按是否稳定可分为稳定排序和不稳定排序，其中__________和__________属于稳定排序。6.图的存储结构主要有邻接矩阵和__________两种。7.哈希函数的构造方法有除留余数法、__________和__________等。三、判断题（每题1分，共10分，对的打“√”，错的打“×”）1.数据的逻辑结构与存储结构是相互独立的，没有关联。（）2.栈和队列都是线性表，都可以用顺序存储和链式存储实现。（）3.单链表的插入操作不需要移动节点，只需要修改指针。（）4.一棵二叉树的前序遍历和中序遍历可以唯一确定这棵二叉树。（）5.快速排序是所有排序算法中效率最高的，时间复杂度始终为O(nlog₂n)。（）6.二分查找只适用于有序的顺序表，不适用于有序链表。（）7.无向图中，所有顶点的度数之和等于边数的2倍。（）8.堆排序是一种不稳定的排序算法。（）9.哈希表的查找效率主要取决于哈希函数的好坏和冲突解决方法。（）10.完全二叉树中，若一个节点没有左孩子，则它一定没有右孩子。（）四、简答题（每题5分，共20分）1.简述顺序表和单链表的优缺点。2.什么是二叉排序树？简述其插入操作的基本步骤。3.简述冒泡排序的基本思想，并分析其时间复杂度。4.什么是图的深度优先遍历（DFS）？简述其基本实现思路。五、算法设计题（每题10分，共20分）1.设计一个算法，用单链表存储一个整数序列，实现求链表中所有偶数的和，并输出结果。要求：写出算法思想、算法代码（用C语言实现）及注释。2.设计一个算法，判断一棵二叉树是否为平衡二叉树（平衡二叉树定义：树上任意节点的左右子树的高度差的绝对值不超过1）。要求：写出算法思想、算法代码（用C语言实现）及注释。六、综合应用题（15分）已知一个无向图G的顶点集合为V={A,B,C,D,E,F}，边集合为E={(A,B),(A,C),(B,C),(B,D),(C,E),(D,E),(E,F)}。1.画出该无向图的结构示意图；（4分）2.写出该图的邻接矩阵和邻接表存储结构；（6分）3.从顶点A出发，分别写出深度优先遍历（DFS）和广度优先遍历（BFS）的序列。（5分）参考答案及评分标准（附）一、单项选择题（每题2分，共20分）1.C2.D3.C4.A5.C6.A7.B8.D9.C10.A二、填空题（每空1分，共15分）1.逻辑结构、存储结构、运算2.先进后出（FILO）、先进先出（FIFO）3.指向链表的第一个节点、简化链表的插入和删除操作4.后序遍历5.冒泡排序、归并排序（答案不唯一，合理即可）6.邻接表7.直接定址法、数字分析法（答案不唯一，合理即可）三、判断题（每题1分，共10分）1.×2.√3.√4.√5.×6.√7.√8.√9.√10.√四、简答题（每题5分，共20分）1.顺序表优点：随机访问效率高（O(1)），存储密度大；（2分）缺点：插入、删除操作需要移动大量节点（O(n)），存储空间固定，不易扩展。（2分）单链表优点：插入、删除操作无需移动节点（O(1)），存储空间可动态扩展；（2分）缺点：随机访问效率低（O(n)），存储密度小，需额外存储指针域。（1分）（总分5分，表述合理即可）2.二叉排序树（二叉查找树）：一棵空树，或者具有如下性质的二叉树：左子树所有节点的值小于根节点的值，右子树所有节点的值大于根节点的值，左右子树也分别是二叉排序树。（2分）插入步骤：1.若二叉排序树为空，将待插入节点作为根节点；（1分）2.若待插入节点值小于根节点值，递归插入到左子树；（1分）3.若待插入节点值大于根节点值，递归插入到右子树；（1分）4.若值相等，无需插入（避免重复）。（总分5分，表述合理即可）3.基本思想：重复遍历待排序序列，每次遍历过程中，依次比较相邻的两个元素，若前一个元素大于后一个元素，则交换两者位置，直到某次遍历中没有发生交换，说明序列已有序。（2分）时间复杂度：最好情况（序列已有序）O(n)，（1分）最坏情况（序列逆序）O(n²)，（1分）平均情况O(n²)。（1分）（总分5分，表述合理即可）4.深度优先遍历（DFS）：从图的某个起始顶点出发，沿着一条路径一直遍历到不能再前进（无未访问邻接顶点），然后回溯到上一个顶点，继续遍历其他未访问的邻接顶点，直到所有顶点都被访问。（2分）实现思路：1.标记起始顶点为已访问；（1分）2.遍历该顶点的所有邻接顶点，若邻接顶点未被访问，递归对该邻接顶点进行深度优先遍历；（1分）3.若所有邻接顶点均已访问，回溯到上一层。（1分）（总分5分，表述合理即可）五、算法设计题（每题10分，共20分）1.算法思想：遍历单链表的每个节点，判断节点的值是否为偶数，若是则累加到总和中，遍历结束后输出总和。（3分）算法代码：c

#include<stdio.h>

#include<stdlib.h>

//定义单链表节点结构

typedefstructNode{

intdata;//节点数据

structNode*next;//指向后继节点的指针

}Node,*LinkList;

//求链表中所有偶数的和

intsumEven(LinkListL){

intsum=0;//初始化总和为0

Node*p=L->next;//p指向链表第一个数据节点

while(p!=NULL){//遍历链表，直到p为空

if(p->data%2==0){//判断当前节点数据是否为偶数

sum+=p->data;//若是，累加到总和

}

p=p->next;//移动到下一个节点

}

returnsum;//返回偶数和

}

//主函数（用于测试，可省略）

intmain(){

//此处可添加链表创建、数据赋值代码

LinkListL=(LinkList)malloc(sizeof(Node));

L->next=NULL;

//假设链表已创建并赋值，调用函数求偶数和

intresult=sumEven(L);

printf("链表中所有偶数的和为：%d\n",result);

return0;

}

注释：代码中包含节点结构定义、核心求和函数及简单测试主函数，逻辑清晰，注释完整。（4分）评分标准：算法思想正确3分，代码正确（语法无误、逻辑合理）4分，注释完整3分，总分10分，表述合理即可。2.算法思想：递归计算二叉树每个节点的左右子树高度，判断每个节点的左右子树高度差的绝对值是否超过1，若所有节点均满足，则为平衡二叉树，否则不是。（3分）算法代码：c

#include<stdio.h>

#include<stdlib.h>

#include<math.h>

//定义二叉树节点结构

typedefstructBiTNode{

intdata;//节点数据

structBiTNode*lchild;//左孩子指针

structBiTNode*rchild;//右孩子指针

}BiTNode,*BiTree;

//计算二叉树的高度

intgetHeight(BiTreeT){

if(T==NULL){//空树高度为0

return0;

}

intleftH=getHeight(T->lchild);//递归计算左子树高度

intrightH=getHeight(T->rchild);//递归计算右子树高度

//返回左右子树高度的最大值加1（当前节点高度）

return(leftH>rightH?leftH:rightH)+1;

}

//判断二叉树是否为平衡二叉树

intisBalanced(BiTreeT){

if(T==NULL){//空树是平衡二叉树

return1;

}

intleftH=getHeight(T->lchild);//左子树高度

intrightH=getHeight(T->rchild);//右子树高度

//判断当前节点左右子树高度差是否≤1，且左右子树均为平衡二叉树

if(abs(leftH-rightH)<=1&&isBalanced(T->lchild)&&isBalanced(T->rchild)){

return1;

}else{

return0;

}

}

//主函数（用于测试，可省略）

intmain(){

//此处可添加二叉树创建代码

BiTreeT=NULL;

//假设二叉树已创建，调用函数判断

if(isBalanced(T)){

printf("该二叉树是平衡二叉树\n");

}else{

printf("该二叉树不是平衡二叉树\n");

}

return0;

}

注释：代码中包含二叉树节点结构定义、高度计算函数、平衡判断函数及简单测试主函数，逻辑清晰，注释完整。（4分）评分标准：算法思想正确3分，代码正确（语法无误、逻辑合理）4分，注释完整3分，总分10分，表述合理即可。六、综合应用题（15分）1.无向图结构示意图（4分）：以A、B、C、D、E、F为顶点，按边集合连接，画图规范、顶点标注清晰即可得分（示例：A连接B、C；B连接A、C、D；C连接A、B、E；D连接B、E；E连接C、D、F；F连接E）。2.邻接矩阵（3分）：6×6矩阵，行和列分别对应顶点A-F（顺序可自定义，需标注），若两顶点之间有边则记1，无边则记0，对角线记0（无自环）。示例（顶点顺序A、B、C、D、E、F）：0110001011