2022年2022年广西大学数据结构试题 .pdf

《2022年2022年广西大学数据结构试题 .pdf》由会员分享，可在线阅读，更多相关《2022年2022年广西大学数据结构试题 .pdf（3页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、在答题过程中不能将试卷拆开第 1 页 共 3 页广西大学课程考试试卷（200 200 学年度第学期）课程名称：数据结构试卷类型：（A、B）号卷 命题教师签名：集体命题 教研室主任签名：院长签名：题 号一二三四五六七八九十总 分应得分20 20 36 24 100 实得分评 分评卷人一、单项选择题（每题 2 分，共 20 分）1算法能正确的实现预定功能的特性称为_。A正确性B易读性C健壮性D高效率2在以下的叙述中，正确的是_。A线性表的线性存储结构优于链表存储结构B二维数组是它的每个数据元素为一个线性表的线性表C栈的操作方式是先进先出D队列的操作方式是先进后出3一个栈的入栈序列是a，b，c，d，

2、e，则栈的不可能的输出序列是_。Aedcba Bdecba Cdceab Dabcde 4栈和队列的共同点是_。A都是先进后出B都是先进先出C只允许在端点处插入和删除元素D没有共同点5数组 A810 中，每个元素的长度为3 个字节，该数组按行存放时，从首地址 SA 开得 分 评卷人 年月日考试用装订线（答题不能超过此线）考试班级：学号：姓名：考位号：名师资料总结-精品资料欢迎下载-名师精心整理-第 1 页，共 3 页 -在答题过程中不能将试卷拆开第 2 页 共 3 页始连续存放在存储器内，元素A74 的起始地址为 _。ASA141 BSA144 CSA 222 DSA225 6对二叉树从1 开

3、始进行连续编号，要求每个结点的编号大于其左右孩子的编号，同一个结点的左右孩子中，其左孩子的编号小于其右孩子的编号，则可采用_次序的遍历实现编号。A先序B中序C后序D从根开始的层次遍历7一棵非空的二叉树的先序序列和后序序列正好相反，则该二叉树一定满足_。A其中任意一结点均无左孩子B其中任意一结点均无右孩子C其中只有一个叶子结点D是任意一棵二又树8对于键值序列（12，13，11，18，60，15,7，18，25，10O），用筛选法建堆，必须从键值为 _的结点开始。A100 B12 C60 D15 9下列序列中，_是执行第一趟快速排序后得到的序列（排序的关键字类型是字符串）。A da,ax,eb,d

4、e,bb,ff,ha,gcB cd,eb,ax,da,ff,ha,gc,bb C gc,ax,eb,cd,bb,ff,da,ha D ax,bb,cd,da,ff,eb,gc,ha10下列排序算法中，_算法可能会出现下面情况：初始数据有序时，花费的时间反而最多。A堆排序B冒泡排序C快速排序DSHELL 排序二、判断题（下列各题中，正确的打“”，否则打“”。每小题 2 分，共 20 分）1（）循环链表中，任意一结点的后继指针均指向其逻辑后继。2（）在对链队列做出队操作时，不会改变front 指针的值。3（）空串与空格串是相同的。4（）二又树只能采用二又链表来存储。5（）若一棵二叉树的任一非叶子结

5、点的度为2，则该二叉树为满二又树。6（）已知一棵树的先序序列和后序序列，一定能构造出该树。7（）图 G 的一棵最小代价生成树的代价未必小于G 的其他任何一棵生成树的代价。8（）有向图用邻接矩阵表示后，顶点i 的出度等于第i 行中非 0 且非的元素个数。9（）堆排序中，在输出一个根之后的调整操作中，“临时根”结点的值将被调到“叶子结点”上。10（）只有在初始数据表为倒序时，冒泡排序所执行的比较次数最多。得 分 评卷人 名师资料总结-精品资料欢迎下载-名师精心整理-第 2 页，共 3 页 -在答题过程中不能将试卷拆开第 3 页 共 3 页三综合题（每题9 分，共 36 分）1对给定的数列R 7，1

6、6，4，8，20，9，6，18，5构造一棵二叉排序树，并且分别给出中序遍历序列和后序遍历序列。2有一份电文中共使用五个字符：a、b、c、d、e，它们的出现频率依次为4，7，5，2，9，试画出对应的Huffman 树，求出每个字符的Huffman 编码。3试利用Dijkstra 算法求下图中从顶点a 到其他各顶点间的最短路径，用表格写出执行算法过程中各步的状态。4已知序列为503，87，512，61，908，170，897，275，653，462，请给出采用快速排序法对该序列作升序排序时的每一趟的结果。四算法设计题（共24 分）1 设 线 性 表 L中 的 数 据 元 素 递 增 有 序，并 以单 链 表 作 存储 结 构，试写 一 算 法Delete_Del_Between(Linklist&L,int min,int max)，实现删除表中所有值大于min 且小于 max 的元素。2以二叉链表为存储结构，写出求二叉树叶子结点总数的算法Leaf（binTree T）。得 分 评卷人 得 分 评卷人 名师资料总结-精品资料欢迎下载-名师精心整理-第 3 页，共 3 页 -