2025年大学大四（工学）数据结构综合测试题及解析

2025年大学大四（工学）数据结构综合测试题及解析

（考试时间：90分钟满分100分）班级______姓名______第I卷（选择题共40分）答题要求：本大题共20小题，每小题2分，共40分。在每小题给出的四个选项中，只有一项是符合题目要求的。1.以下关于线性表的说法，正确的是（）A.线性表只能采用顺序存储结构B.线性表只能采用链式存储结构C.线性表既可以采用顺序存储结构，也可以采用链式存储结构D.线性表的顺序存储结构和链式存储结构各有优缺点，适用于不同的应用场景2.若线性表最常用的操作是存取第i个元素及其前驱和后继元素的值，为节省时间应采用的存储方式是（）A.单链表B.双向链表C.顺序表D.循环链表3.一个栈的入栈序列是1，2，3，4，5，则栈的不可能的输出序列是（）A.5，4，3，2，1B.4，3，5，1，2C.4，5，3，2，1D.1，2，3，4，54.已知循环队列的存储空间为数组data[21]，且当前队列的头指针front=8，尾指针rear=3，则该队列的当前长度为（）A.5B.6C.16D.175.深度为5的完全二叉树的结点数不可能是（）A.15B.16C.17D.186.设一棵完全二叉树共有699个结点，则在该二叉树中的叶子结点数为（）A.349B.350C.255D.3517.若对一棵有100个结点的完全二叉树按层序编号，则编号为49的结点的左孩子的编号为（）A.98B.99C.50D.518.对于一个具有n个顶点的无向图，若采用邻接矩阵表示，则该矩阵的大小是（）A.nB.(n-1)×(n-1)C.n×nD.(n+1)×(n+1)9.若一个有向图的邻接矩阵中，主对角线以下元素均为零，则该图的拓扑序列（）A.存在B.不存在C.不一定存在D.以上都不对10.对图进行深度优先遍历和广度优先遍历的时间复杂度分别为（）A.O(n)，O(n^2)B.O(n^2)，O(n)C.O(n)，O(n)D.O(n^2)，O(n^2)11.已知一棵二叉排序树的前序遍历序列为ABCDEFG，中序遍历序列为CBEDAFG，则后序遍历序列为（）A.CEBFGDAB.CEDBGFAC.ECDBFGAD.EDCBGFA12.在平衡二叉排序树中插入一个结点后造成了不平衡，设最低的不平衡结点为A，并已知A的左孩子的平衡因子为0，右孩子的平衡因子为l，则应进行的调整是（）A.LL型B.LR型C.RL型D.RR型13.哈希表的平均查找长度与（）有关。A.哈希函数B.哈希表的装填因子C.哈希表的大小D.以上都对14.已知关键字集合K={60，40，49，23，25，13，95，196，85}，哈希函数H(key)=key%13，采用链地址法存储，哈希表的装填因子α=0.6，则哈希表的长度m为（）A.10B.13C.16D.1915.对一组记录的关键码（54，36，72，15，40，38，91）进行堆排序，初始建堆后堆顶元素为（）A.15B.36C.72D.9116.对一组记录的关键码（25，38，48，52，63，74）进行快速排序，以第一个记录为基准，一趟快速排序的结果为（）A.25，38，48，52，63，74B.25，38，48，52，63，74C.25，38，48，52，63，74D.25，38，48，52，63，7417.以下排序方法中，平均时间复杂度为O(nlogn)且空间复杂度为O(1)的是（）A.快速排序B.堆排序C.归并排序D.冒泡排序18.若数据元素序列11，12，13，7，8，9，23，4，5是采用下列排序方法之一得到的第二趟排序后的结果，则该排序算法只能是（）A.冒泡排序B.插入排序C.选择排序D.二路归并排序19.设有两个串p和q，求q在p中首次出现的位置的运算称作（）A.连接B.模式匹配C.求子串D.求串长20.下面关于串的叙述中，哪一个是不正确的（）A.串是字符的有限序列B.空串是由空格构成的串C.模式匹配是串的一种重要运算D.串既可以采用顺序存储，也可以采用链式存储第II卷（非选择题共60分）21.（1)已知一个栈的入栈序列为1，2，3，4，5，试写出所有可能的出栈序列。（5分）(2)若栈的入栈序列为a，b，c，d，e，试写出所有可能的出栈序列。（5分）22.已知一棵二叉树的先序遍历序列为ABDEGCFH，中序遍历序列为DBGEACHF，试画出该二叉树，并写出其后序遍历序列。（10分）23.已知有向图G如下所示：(1)画出其邻接矩阵。（5分）(2)写出从顶点v1出发的深度优先遍历序列和广度优先遍历序列。（5分）24.设哈希表的长度m=13，哈希函数H(key)=key%13，用链地址法处理冲突。已知关键字集合K={23，44，36，40，请构造哈希表，并计算查找成功时的平均查找长度。（10分）25.对关键字序列{49，38，65，97，76，13，27}进行快速排序，写出每一趟排序的结果。（10分）答案：1.D2.C3.B4.C5.A6.B7.A8.C9.A10.C11.B12.B13.D14.B15.D16.A17.B18.B19.B20.B21.（1）12345，12354，12435，12453，12543，13245，13254，13425，13452，13542，14325，14352，14532，15432，21345，21354，21435，21453，21543，23145，23154，23415，23451，23541，24315，24351，24531，25431，32145，32154，32415，32451，32541，34215，34251，34521，35421，43215，43251，43521，45321，54321。（2）abcde，abcde，abced，abecd，abecd，acbde，acbed，acdeb，acedb，adecb，aebcd，aebdc，aecbd，aecdb……（答案较多，不一一列举）22.二叉树：根节点A，左子树根B，B的左子树根D，D的左子树为空，D右子树根G；B右子树根E，E左子树为空，E右子树为空；A右子树根C，C左子树根H，H左子树为空，H右子树为空，C右子树根F，F左子树为空，F右子树为空。后序遍历序列：DGEBHFCA23.（1）邻接矩阵：第一行0表示v1到v1无边，1表示v1到v2有边，0表示v1到v3无边，1表示v1到v4有边；第二行0表示v2到v1无边，0表示v2到v2无边，1表示v2到v3有边，0表示v2到v4无边；第三行0表示v3到v1无边，0表示v3到v2无边，0表示v3到v3无边，1表示v3到v4有边；第四行0表示v4到v1无边，0表示v4到v2无边，0表示v4到v3无边，0表示v4到v4无边。（2）深度优先遍历序列：v1，v2，v3，v4；广度优先遍历序列：v1，v2，v4，v324.哈希表：0号链表：23；1号链表：44；2号链表：36；3号链表：40。平均查找长度=(1+1+1+1