大学试题(计算机科学)-数据结构笔试（2018-2023年）真题摘选含答案

长风破浪会有时，直挂云帆济沧海。大学试题(计算机科学)-数据结构笔试（2018-2023年）真题摘选含答案（图片大小可自由调整）卷I一.参考题库(共30题)1.设顺序表L是一个递减有序表，试写一算法，将x插入其后仍保持L的有序性。2.编写算法求给定结点在二叉排序树中所在的层数。3.记录的关键字序列为：63，90，70，55，67，42，98，83，10，45，58，则画出构造一棵二叉排序树的过程。4.设有二维数组A（6×8），每个元素占6个字节存储，顺序存放，A的起地址为1000，计算： （1）数组A的体积（即存储量）； （2）数组的最后一个元素A的起地址； （3）按行优先存放时，元素A1，4的起地址； （4）按列优先存放时，元素A4，7的起地址。5.用线性表的顺序结构来描述一个城市的设计和规划合适吗？为什么？6.已知一棵二叉树的中序序列和后序序列分别为BDCEAFHG和DECBHGFA，试画出这棵二叉树。7.已知一组元素的排序码为： （46，74，16，53，14，26，40，38，86，65，27，34）利用直接选择排序方法写出每次选择和交换后的排列结果。8.请列举出一些可以用栈和队列表示的实际问题。9.设顺序表va中的数据元素递增有序。试写一算法，将x插入到顺序表的适当位置上，以保持该表的有序性。10.简述多重表文件和倒排文件两种多关键字文件的组织方法。11.若已知一个栈的入栈序列是1，2，3，…，n，其输出序列为p1，p2，p3，…，pn，若p1=n，则pi为（） A、AB、BC、CD、D12.假设线性表采用顺序存储结构，表中元素值为整型。阅读算法f2，设顺序表L=（3，7，3，2，1，1，8，7，3），写出执行算法f2后的线性表L的数据元素，并描述该算法的功能。voidf2（SeqList*L）{inti，j，k；k=0；for（i=0；ilength；i++）{for（j=0；jdata[i]!=L->data[j]；j++）；if（j==k）{if（k!=i）L->data[k]=L->data[i]；k++；}}L->length=k；}13.深度为k的完全二叉树中最少有（）个结点。 A、AB、BC、CD、D14.已知有向图如下所示，请写出该图所有的拓扑序列。 15.设计算法判定一棵二叉树是否为二叉排序树。16.画出下列每个广义表的带表头附加结点的链接存储结构图并分别计算出它们的长度和深度。 （1）A=（（）） （2）B=（a，b，c） （3）C=（a，（b，（c））） （4）D=（（a，b），（c，d）） （5）E=（a，（b，（c，d）），（e）） （6）F=（（a，（b，（），c），（（d），e）））17.简述Floyd算法的作用和具体步骤。18.对下面数据表，写出采用SHELL排序算法排序的每一趟的结果，并标出数据移动情况。 （125，11，22，34，15，44，76，66，100，8，14，20，2，5，1）。19.散列表20.冲突21.已知一棵具有n个结点的完全二叉树被顺序存储于一维数组的A[1]～A[n]元素中，试编写一个算法打印出编号为i的结点的双亲和所有孩子。22.设指针变量front表示链式队列的队头指针，指针变量rear表示链式队列的队尾指针，指针变量s指向将要入队列的结点X，则入队列的操作序列为（） A、AB、BC、CD、D23.判断下列各对函数f（n）和g（n），当n→∞时，哪个函数增长更快？ 24.设计算法按前序次序打印二叉树中的叶子结点。25.设计算法判断一个算术表达式的圆括号是否正确配对。（提示：对表达式进行扫描，凡遇到’（’就进栈，遇’）’就退掉栈顶的’（’，表达式被扫描完毕，栈应为空。26.查找27.已知一组记录为（46，74，53，14，26，38，86，65，27，34），给出采用堆排序法进行排序时每一趟的排序结果。28.下面的算法功能是向HBT堆中插入一个值为item的元素，使得插入后仍是一个堆。请在画有横线的地方填上合适的语句，完成其功能。 29.写出快速排序的非递归调用算法。30.试找出满足下列条件的所有二叉树： （1）先序序列和中序序列相同； （2）中序序列和后序序列相同； （3）先序序列和后序序列相同。卷I参考答案一.参考题库1.参考答案:2.参考答案:根据题目要求采用递归方法，从根结点开始查找结点p，若待查结点是根结点，则深度为1，否则到左子树（或右子树）上去找，查找深度加1。 具体算法如下： 3.参考答案:4.参考答案:5.参考答案: 不合适。因为一个城市的设计和规划涉及非常多的项目，很复杂，经常需要修改、扩充和删除各种信息，才能适应不断发展的需要。有鉴于此，顺序线性表不能很好适应其需要，故是不合适的。6.参考答案:7.参考答案: 8.参考答案: 所有“后进先出”（LIFO，LastInFirstOut）的实际问题都可以用栈表示。栈的应用主要有：数制的转换、括号的匹配检查、行编辑处理、表达式求解、走迷宫以及高级语言中函数的嵌套调用和递归的实现等。 所有“先进先出”（FIFO，FirstInFirstOut）的实际问题都可以用队列表示。如日常中的排队问题，队列的应用主要有：操作系统中各种资源请求排队和各种缓冲区的先进先出管理，各种应用系统中的事件规划和事件模拟，树的层次遍历和图的广度优先遍历等。9.参考答案: 10.参考答案: 多重表文件是将索引方法和链接方法相结合的一种文件组织方式，对主关键字建立的索引称为主索引，对每个需做查询操作的次关键字建立的索引称为次索引。在多重表文件中，记录通常按主关键字顺序排列，同时将具有相同次关键字值的记录链接成一个链表，并将此链表的头指针、链表长度及次关键字作为对应次索引表中的索引项。 与多重表文件不同，倒排文件中具有相同次关键字的记录之间不进行链接，而是在对次关键字建立的索引中列出具有该次关键字值的所有记录的物理地址。倒排文件中的次关键字索引称为倒排表，倒排表与主文件一起就构成了倒排文件。11.参考答案:C12.参考答案: （3，7，2，1，8）删除顺序表中重复的元素13.参考答案:B14.参考答案: 拓扑排序如下： v1,v2,v4,v6,v5,v3,v7,v8v1,v2,v4,v6,v5,v7,v3,v8 v1,v2,v6,v4,v5,v3,v7,v8v1,v2,v6,v4,v5,v7,v3,v8 v1,v6,v2,v4,v5,v3,v7,v8v1,v6,v2,v4,v5,v7,v3,v815.参考答案:对二叉排序树来讲，其中序遍历序列为一个递增序列。因此，对给定二叉树进行中序遍历，如果始终能够保证前一个值比后一个值小，则说明该二叉树是二叉排序树。 具体算法如下： 16.参考答案: 17.参考答案: 18.参考答案:19.参考答案: 是根据关键字而直接进行访问的数据结构。散列表建立了关键字和存储地址指间的一种直接映射关系。20.参考答案: 散列函数可能会把两个或以上的不同关键字映射到同一地址，这种情况为冲突。21.参考答案: 22.参考答案:C23.参考答案: （1）g（n）快 （2）g（n）快 （3）f（n）快 （4）f（n）快24.参考答案:本算法的要求与前序遍历算法既有相同之处，又有不同之处。相同之处是打印次序均为前序，不同之处是此处不是打印每个结点的值，而是打印出其中的叶子结点，即为有条件打印。为此，将前序遍历 算法中的访问操作改为条件打印即可。算法如下： 25.参考答案:根据提示，可以设计算法如下： 26.参考答案: 在数据集合中寻找满足某种条件的数据元素的过程称为查找。27.参考答案:28.参考答案: 依次为： 29.参考答案:先调用划分函数Quickpass（划分函数同教材），以确定中间位置，然后再借助栈分别对中间元素的左、右两边的区域进行快速排序。 30.参考答案: （1）先序序列和中序序列相同的二叉树为：空树或者任一结点均无左孩子的非空二叉树； （2）中序序列和后序序列相同的二叉树为：空树或者任一结点均无右孩子的非空二叉树； （3）先序序列和后序序列相同的二叉树为：空树或仅有一个结点的二叉树。卷II一.参考题库(共30题)1.以孩子兄弟表示法做存储结构，求树中结点x的第i个孩子。2.对给定文件（28，07，39，10，65，14，61，17，50，21）选择第一个元素28进行划分，写出其快速排序第一遍的排序过程。3.设计两个有序单链表的合并排序算法。4.在操作序列EnQueue（1）、EnQueue（3）、DeQueue、EnQueue（5）、EnQueue（7）、DeQueue、EnQueue（9）之后，队头元素和队尾元素分别是什么？（EnQueue（k）表示整数k入队，DeQueue表示队头元素出队）。5.对于右图所示的树： 写出先根遍历得到的结点序列。6.下面程序段中带有下划线的语句的执行次数的数量级是（） 7.在下面数组a中链接存储着一个线性表，表头指针为a[0].next，则该线性表为（）。 8.给定一组记录，其关键码为字母。记录按照下面的顺序插入一棵空的B—树中：C，S，D，T，A，M，P，I，B，W，N，G，V，R，K，E，H，O，L，J。请画出插入这些记录后的3阶B—树。9.数据类型10.设一组初始记录关键字序列为（15，17，18，22，35，51，60），要求计算出成功查找时的平均查找长度。11.归并排序12.试写出如图所示的二叉树分别按先序、中序、后序遍历时得到的结点序列。 13.简述图的基本操作及各操作的含义。14.试写一算法，实现顺序表的就地逆置，即利用原表的存储空间将线性表（a1，…，an）逆置为（an，…，a1）。15.什么叫平均查找长度？写出平均查找长度的定义16.设P1和P2是两个单链表，他们的元素都递增有序，指出下面函数F的功能。 17.设关键字序列（k1，k2，…，kn-1）是堆，设计算法将关键字序列（k1，k2，…，kn-1，x）调整为堆。18.设查找表为（7，15，21，22，40，58，68，80，88，89，120），元素的下标依次为1，2，3，……，11。 （1）画出对上述查找表进行折半查找所对应的判定树（树中结点用下标表示） （2）说明成功查找到元素40需要经过多少次比较？ （3）求在等概率条件下，成功查找的平均比较次数？19.已知数据序列{10，18，4，3，6，12，9，15}，写出二路归并排序的每一趟排序结果。20.模式匹配21.设一个有向图为G=（V，E），其中V={v1，v2，v3，v4}，E={，，，，}，请回答下列各问：对（2）中的邻接矩阵，给出从顶点v2出发的BFS序列和BFS生成树。22.两个字符串分别为： 的结果是（）。23.编写递归算法，计算二叉树中叶子结点的数目。24.画出含三个结点的无序树。25.写出在顺序存储结构下将线性表逆转的算法，要求使用最少的附加空间。26.有一个早晨7点到晚上11点营业的连锁店，叫7-11店。一次，一位顾客在该店选了4样东西，付款时，营业员计算后说：“总共是7.11元。”顾客开玩笑说：“哦？难道因为你们是7-11店，所以我就要付7.11元吗？”营业员没有听出是在开玩笑，便回答说：“当然不是，我是把4样东西的价格相乘才得出结果的！”顾客非常吃惊，说：“你怎么把它们相乘呢？，应该把它们相加才对！”营业员听后，忙说：“噢，对不起，我今天头非常疼，所以按错计算器的键了。”并赶紧把4样东西的价格相加重算了一遍，但结果令两个人都十分惊讶：总和还是7.11元。请设计一个算法计算这四样东西的价格各是多少？27.已知一有向图的邻接表存储结构如下，则根据有向图的深度优先遍历算法，从顶点V1出发，不能得到的顶点序列是（）。 A、V1，V2，V3，V5，V4B、V1，V3，V4，V5，V2C、V1，V2，V4，V5，V3D、V1，V4，V3，V5，V228.阅读下面程序，并回答有关问题。其中BSTree为用二叉链表表示的二叉排序树类型。简要说明程序功能。29.设线性表以不带头结点的单向链表存储，链表头指针为head，以下程序的功能是输出链表中各结点中的数据域data。完成程序中空格部分。 30.假设用于通信的电文由字符集{a，b，c，d，e，f，g，h}中的字母构成，这8个字母在电文中出现的概率分别为{0.07，0.19，0.02，0.06，0.32，0.03，0.21，0.10}，试为这8个字母进行哈夫曼编码。请回答：写出依此哈夫曼树对各个字母的哈夫曼编码。卷II参考答案一.参考题库1.参考答案:先在链表中进行遍历，在遍历过程中查找值等于x的结点，然后由此结点的最左孩子域firstchild找到值为x结点的第一个孩子，再沿右兄弟域rightsib找到值为x结点的第i个孩子并返回指向这个孩子的指针。