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

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

（考试时间：90分钟满分100分）班级______姓名______第I卷（选择题，共40分）每题给出的四个选项中，只有一个选项是符合题目要求的。(总共20题，每题2分，在每小题给出的四个选项中，选出最符合题目要求的一项)1.以下关于数据结构的说法，正确的是A.数据结构只研究数据的逻辑结构B.数据结构只研究数据的存储结构C.数据结构研究数据的逻辑结构和存储结构D.数据结构与数据的逻辑结构和存储结构无关2.线性表的顺序存储结构中，元素之间的逻辑关系是通过A.指针表示B.相邻存储位置表示C.数组下标表示D.以上都不对3.在一个长度为n的顺序表中，删除第i个元素（1≤i≤n）时，需要移动的元素个数是A.n-iB.n-i+1C.iD.i-14.栈的特点是A.先进先出B.后进先出C.随机进出D.以上都不对5.若进栈序列为1，2，3，4，进栈过程中可以出栈，则下列不可能的一个出栈序列是A.1，4，3，2B.2，3，4，1C.3，1，4，2D.3，4，2，16.队列的特点是A.先进先出B.后进先出C.随机进出D.以上都不对7.循环队列中，队满的条件是A.（rear+1）%maxsize==frontB.rear==frontC.rear+1==frontD.以上都不对8.对于一棵具有n个结点的二叉树，若一个结点的编号为i（1≤i≤n），则它的左孩子结点的编号为A.2iB.2i+1C.2i-1D.不确定9.深度为5的满二叉树中，叶子结点的个数为A.15B.16C.31D.3210.已知二叉树的前序序列为ABDECF，中序序列为DBEAFC，则后序序列为A.DEBFCAB.DEFBCAC.DBEACFD.ABCDEF11.以下哪种排序算法的平均时间复杂度为O(n^2)A.快速排序B.冒泡排序C.归并排序D.堆排序12.对关键字集合K={60，40，49，23，25，13，95}进行排序，当一趟排序结束后，结果为23，40，49，25，13，60，95，则采用的排序方法是A.冒泡排序B.选择排序C.插入排序D.快速排序13.哈希表的平均查找长度主要取决于A.哈希表的大小B.数据元素的多少C.哈希函数和处理冲突的方法D.以上都不对14.顺序查找法适用于查找A.有序表B.无序表C.哈希表D.二叉排序树15.折半查找法适用于查找A.有序表B.无序表C.哈希表D.二叉排序树16.一个具有n个顶点的无向图，若采用邻接矩阵表示，则该矩阵的大小为A.nnB.(n-1)(n-1)C.n(n-1)D.(n-1)n17.一个具有n个顶点的有向图，其边数最多为A.n(n-1)B.n(n+1)C.nnD.(n+18.图的深度优先搜索类似于树的A.前序遍历B.中序遍历C.后序遍历D.层次遍历19.图的广度优先搜索类似于树的A.前序遍历B.中序遍历C.后序遍历D.层次遍历20.以下关于数据结构应用的说法，错误的是A.栈可用于实现表达式求值B.队列可用于实现广度优先搜索C.二叉排序树可用于实现快速排序D.哈希表可用于实现查找功能第II卷（非选择题，共60分）21.（10分）简述线性表的两种存储结构及其优缺点。22.（10分）已知一个栈的进栈序列为1，2，3，4，5，写出所有可能的出栈序列。23.（10分）画出一棵具有5个结点的二叉树，要求其前序序列为ABCDE，中序序列为CBAED。24.（15分）阅读以下材料：给定关键字集合K={30，10，40，20，50}，采用快速排序算法进行排序。快速排序的基本思想是选择一个基准元素，将数组分为两部分，使得左边部分的元素都小于等于基准元素，右边部分的元素都大于等于基准元素，然后对左右两部分分别进行排序。请回答以下问题：（1）第一次划分后，数组的状态是怎样的？（2）简述快速排序的递归过程。25.（15分）阅读以下材料：有一个无向图G，其顶点集合V={v1，v2，v3，v4，v5}，边集合E={(v1,v2),(v1,v3),(v2,v3),(v2,v4),(v3,v4),(v3,v5),(v4,v5)}。请回答以下问题：（1）画出该无向图。（2）写出该图的邻接矩阵。（3）从顶点v1出发，进行深度优先搜索