2025年大学计算机科学与技术（数据结构与算法）试题及答案

2025年大学计算机科学与技术（数据结构与算法）试题及答案

（考试时间：90分钟满分100分）班级______姓名______第I卷（选择题共40分）每题只有一个正确答案，请将正确答案填涂在答题卡相应位置。（总共8题，每题5分）1.以下关于线性表的说法，错误的是（）A.线性表是一种线性结构B.线性表可以采用顺序存储或链式存储C.线性表的插入和删除操作效率在顺序存储和链式存储下相同D.线性表的元素具有一对一的逻辑关系2.若某线性表最常用的操作是存取第i个元素及其前驱的值，则采用（）存储方式最节省时间。A.单链表B.双链表C.顺序表D.单循环链表3.一个栈的入栈序列是1，2，3，4，5，则栈的不可能的输出序列是（）A.5，4，3，2，1B.4，5，3，2，1C.4，3，5，1，2D.1，2，3，4，54.深度为5的完全二叉树的结点数不可能是（）A.15B.16C.17D.185.对关键字集合K={60，40，49，23，25，13，95，196，85}，创建平衡二叉排序树，其根结点的值为（）A.49B.60C.40D.236.对一组数据进行排序，若关键字序列基本有序，则采用（）排序算法效率最高。A.快速排序B.冒泡排序C.归并排序D.选择排序7.哈希表的平均查找长度与（）有关。A.哈希函数B.哈希表的装填因子C.哈希表的大小D.以上都有关8.以下关于图的说法，正确的是（）A.无向图的邻接矩阵一定是对称矩阵B.有向图的邻接矩阵一定是非对称矩阵C.图的遍历只能采用深度优先遍历D.图的最小生成树一定是唯一的第II卷（非选择题共60分）9.（10分）简述顺序表和链表的优缺点。10.（10分）已知一棵二叉树的先序遍历序列为ABDECF，中序遍历序列为DBEAFC，画出该二叉树。11.（15分）用堆排序法对关键字序列{38，27，43，3，9，82，10}进行排序，写出每一趟排序后的结果。12.（15分）阅读以下材料：在一个学校的学生信息管理系统中，需要对学生的成绩进行管理。学生成绩包括学号、姓名、课程成绩等信息。要求能够快速地根据学号查询学生成绩，并且能够方便地对学生成绩进行修改和添加。请设计一种合适的数据结构来存储学生成绩信息，并说明理由。同时，设计相应的算法来实现根据学号查询学生成绩、修改学生成绩和添加学生成绩的功能。13.（10分）简述图的深度优先遍历和广度优先遍历的基本思想，并分析它们的时间复杂度。答案：1.C2.C3.C4.A5.B6.B7.D8.A9.顺序表优点：随机存取效率高，存储密度大；缺点：插入和删除操作效率低，需要预先分配存储空间。链表优点：插入和删除操作效率高，不需要预先分配存储空间；缺点：随机存取效率低，存储密度小。10.先序遍历确定根结点，中序遍历确定左右子树。二叉树为：A/\BC/\\DEF11.初始序列：38，27，43，3，9，82，10第一趟：10，27，43，3，9，82，38第二趟：10，27，3，9，82，43，38第三趟：10，9，3，27，82，43，38第四趟：3，9，10，27，82，43，38第五趟：3，9，10，27，43，82，38第六趟：3，9，10，27，43，82，3812.可以采用哈希表来存储学生成绩信息。理由是哈希表能通过哈希函数快速定位元素，满足快速查询的要求。算法设计：查询时，通过学号计算哈希值找到对应位置；修改时，找到位置修改相应成绩；添加时，计算哈希值找到合适位置插入新成绩。13.深度优先遍历：从起始顶点开始，沿着一条路径尽可能深地访问顶点，直到无法继续或已访问完所有顶点，然后回溯到前一步，继续访问其