2023年大学试题(计算机科学)-数据结构考试历年高频考点试题含答案

2023年大学试题(计算机科学)-数据结构考试历年高频考点试题含答案（图片大小可自由调整）第1卷一.参考题库(共50题)1.简述结点的权、结点的带权路径长度、树的带权路径长度等基本术语的含义。2.在二叉树的顺序存储结构中，实际上隐含着双亲的信息，因此可和三叉链表对应。假设每个指针域占4个字节，每个信息域占k个字节。试问：对于一棵有n个结点的二叉树，且在顺序存储结构中最后一个节点的下标为m，在什么条件下顺序存储结构比三叉链表更节省空间？3.二次聚集4.设定串采用顺序存储结构，写出对串s1和串s2比较大小的算法。串值大小按字典排序（升序）方式，返回值等于-1，0和1分别表示s1＜s2，s1=s2和s1＞s2。5.试写一个判别给定二叉树是否为二叉排序树的算法，设此二叉树以二叉链表作存储结构。且树中结点的关键字均不同。6.将数列（24，15，38，27，121，76，130）的各元素依次插入一棵初始为空的二叉排序树中，请画出最后的结果并求等概率情况下查找成功的平均查找长度。7.对图所示的无向图，依次输入各边：（v1，v2）、（v1，v4）、（v2，v3）、（v3，v4）、（v3，v5），请回答下列各问： （2）画出该图的邻接表（头插法建表）存储结构图示。8.设待排序的关键字序列为{12，2，16，30，28，10，16*，20，6，18}，试分别写出使用以下排序方法，每趟排序结束后关键字序列的状态。快速排序9.下面程序段的时间复杂度为（） 10.已知如下所示长度为12的表：（Jan，Feb，Mar，Apr，May，June，July，Aug，Sep，Oct，Nov，Dec）按表中元素顺序构造一棵平衡二叉排序树，并求其在等概率的情况下查找成功的平均查找长度。11.假设有两个按元素递增有序排列的线性表A和B，均以单链表作存储结构。请编写算法，将表A和表B归并成一个按元素值非递减有序（允许值相同）排列的线性表C，并要求利用原表（即表A和表B）的结点空间存放表C。12.对于List类型的线性表，编写出下列算法： 从线性表中删除具有最小值的元素并由函数返回，空出的位置由最后一个元素填补，若线性表为空则显示出错信息并退出运行。13.包含n个结点的二叉树，高度最大为（），高度最小为（）。14.已知某哈希表的装载因子小于1，哈希函数H（key）为关键字（标识符）的第一个字母在字母表中的序号，处理冲突的方法为线性探测开放定址法。试编写一个按第一个字母的顺序输出哈希表中所有关键字的算法。15.双向链表16.数据的存储结构17.下列是顺序存储线性表排序的算法问：此算法的时间复杂性为（）。 A、O（n）   B、（n2）   C、（n*i）   D、（n*j）18.下面程序段的时间复杂性的量级为（） A、O（1）B、O（n）C、O（n2）D、O（n3）19.设计在无头结点的单链表中删除第i个结点的算法。20.栈上的基本运算有哪些？21.简述分块查找对待查找数据集合的要求及分块查找的具体步骤。22.设顺序表va中的数据元数递增有序。试写一算法，将x插入到顺序表的适当位置上，以保持该表的有序性23.已知有一个单向循环链表，其每个结点中含三个域：pre，data和next，其中data为数据域，next为指向后继结点的指针域，pre也为指针域，但它的值为空，试编写算法将此单向循环链表改为双向循环链表，即使pre成为指向前驱结点的指针域。24.以下函数为直接选择排序算法，对a[1],a[2],…a[n]中的记录进行直接选择排序，完成程序中的空格。 25.算法中R[n+1]的作用是什么？ 26.将如图所示的树转换为二叉树。 27.已知一棵度为k的树中有n1个度为1的结点，n2个度为2的结点，…，nk个度为k的结点，问该树中有多少个叶子结点？28.已知权值集合为{5，7，2，3，6，9}，要求给出哈夫曼树，并计算带权路径长度WPL。29.具有什么特征的数据结构被称为栈和队列？先进后出、栈顶、栈底、先进先出、队头、队尾的概念是什么？30.深度优先搜索（DFS）31.已知一棵二叉树的先序序列：ABDGJEHCFIKL；中序序列：DJGBEHACKILF。画出二叉树的形态。32.试编写如下定义的递归函数的递归算法，并根据算法画出求g（5，2）时栈的变化过程。 33.快速排序34.顺序表的定义如下： 其中ElemType的含义是：通用数据类型；size的含义是：（）。35.在下面数组a中链接存储着一个线性表，表头指针为a[0].next，则该线性表为（）。 36.指出下述程序段的功能是什么？ 37.设计顺序查找算法，将哨兵设在下标高端。38.编写算法求给定结点在二叉排序树中所在的层数。39.原地工作40.假定一个待哈希存储的线性表为（32，75，29，63，48，94，25，36，18，70，49，80），哈希地址空间为HT[12]，若采用除留余数法构造哈希函数和拉链法处理冲突，试画出最后得到的哈希表，并求出平均查找长度。41.简述数据结构中讨论的三种经典结构的逻辑特征是什么？42.简述以下算法的功能。 43.下面程序的时间复杂度为（）。 x=0； for（i=1；i<n；i++）for（j=i+1；j<=n；j++） x++；</n；i++） A、O（）B、O（n2）C、O（1）D、O（n）44.下面算法是判断字符串是否为回文（即正读和倒读相同），试完成程序填空。 45.外部排序46.已知一组元素为（46，25，78，62，12，37，70，29），画出按元素排列顺序输入生成的一棵二叉搜索树。47.将下面图5-16所示的树转换为二叉树，图5-17所示的二叉树转换为树或森林。 48.已知P结点是某双向链表的中间结点，试从下列提供的答案中选择合适的语句序列。 a.在P结点后插入S结点的语句序列是（）。 b.在P结点前插入S结点的语句序列是（）。 c.删除P结点的直接后继结点的语句序列是（）。 d.删除P结点的直接前驱结点的语句序列是（）。 e.删除P结点的语句序列是（）。 （1）P->next=P->next->next； （2）P->priou=P->priou->priou； （3）P->next=S； （4）P->priou=S； （5）S->next=P； （6）S->priou=P； （7）S->next=P->next； （8）S->priou=P->priou； （9）P->priou->next=P->next； （10）P->priou->next=P； （11）P->next->priou=P； （12）P->next->priou=S； （13）P->priou->next=S； （14）P->next->priou=P->priou； （15）Q=P->next； （16）Q=P->priou； （17）free（P）； （18）free（Q）；49.完成从一维数组A[n]上进行快速排序的递归算法。 50.有七个带权结点，其权值分别为3，7，8，2，6，10，14，试以它们为叶子结点构造一棵哈夫曼树，并计算出带权路径长度WPL。第1卷参考答案一.参考题库1.正确答案: 结点的权和结点的带权路径长度：在实际应用中，往往给树中的结点赋予一个具有某种意义的实数，该实数就称为是结点的权。结点的带权路径长度是指从树根到该结点的路径长度与结点的权的乘积。 2.正确答案: 3.正确答案: 指在处理冲突过程中发生的两个第一个哈希地址不同的记录争夺同一个后继哈希地址的现象。4.正确答案:5.正确答案:6.正确答案:二叉排序树如下图所示，其平均查找长度=1+2×2+3×2+4×2=19/7 7.正确答案: 8.正确答案:9.正确答案:O(n)10.正确答案:11.正确答案:12.正确答案: 13.正确答案: n；14.正确答案:15.正确答案: 线性表采用链式存储时，每个结点除一个数据域外，包含两个指针域，一个指向该结点的直接后继，一个指向该结点的直接前驱，这种方式构成的链表，即为双向链表。16.正确答案: 指数据结构在计算机中的表示，也成物理结构。主要有顺序存储、连接存储、索引存储、散列存储。17.正确答案:B18.正确答案:D19.正确答案:20.正确答案: 21.正确答案: 22.正确答案: voidInsert_sq（Sqlistva[]，ElemTypex） {inti，j，n； n=length（va[]）； if（x>=va[i]） va[n]=x； else {i=0； while（x>va[i]）i++； for（j=n-1；j>=I；j--） va[j+1]=va[j]； va[i]=x；} n++； }23.正确答案: 24.正确答案: 25.正确答案: 哨兵。避免边界检测，提高程序运行效率。26.正确答案:27.正确答案: 28.正确答案: 树形态： 带权路径长度：WPL=(6+7+9)*2+5*3+(2+3)*4=44+15+20=7929.正确答案: 栈：一种插入和删除都只能在表的同一端进行的线性表。 队列：一种只允许在表的一端进行插入操作，而在表的另一端进行删除操作的线性表。 先进后出：元素是以e1，e2，……en顺序进入数据结构，以相反的顺序即en，en-1，……e1离开数据结构。 栈顶：允许进行插入和删除操作的一端。 栈底：栈中与栈顶相对的另一端。 先进先出：元素是以e1，e2，……en顺序进入数据结构，以相同的顺序即e1，e2，……en。离开数据结构。 队头：允许删除操作的一端。 队尾：允许插入操作的一端。30.正确答案: 类似树的先序遍历，在图中任选一个顶点作为出发顶点V0，访问V0后，依次从V0的没被访问过的邻接点出发进行深度优先搜索。直到与V0所连通的所有顶点均被访问。如果，此时图中还有顶点尚未访问，则从剩余的顶点中再任选一个顶点作为出发顶点V0，重复上述过程，直到图中全部顶点均被访问为止。31.正确答案: 32.正确答案: 33.正确答案: 快速排序的基本思想是把当前待排序的记录，存放到整个表排好序后，它应当在的最终位置上。将原来的待排序表分割成两部分，其中一部分表中的关键字均比另一部分表中的关键字小。然后，分别对两部分表用同样的方式进行排序，直到整个表排好序。34.正确答案:顺序表中元素的个数35.正确答案:（38，56，25，60，42，74）36.正确答案:这段程序的功能是将队列1的所有元素复制到队列2中去，但其执行过程是先把队列1的元素全部出队，进入队列2，然后再把队列2的元素复制到队列1中。37.正确答案:将哨兵设置在下标高端，表示从数组的低端开始查找，在查找不成功的情况下，算法自动在哨兵处终止。具体算法如下： 38.正确答案:根据题目要求采用递归方法，从根结点开始查找结点p，若待查结点是根结点，则深度为1，否则到左子树（或右子树）上去找，查找深度加1。 具体算法如下： 39.正确答案: 算法执行时，若额外空间相对于输入数据量来说是常数，则称此算法为原地工作。40.正确答案:41.正确答案: 三种经典结构：线性表、树和图。逻辑特征分别为： （1）线性表：一对一。有且仅有一个开始结点和一个终端结点，其余的内部结点都有且仅有一个前趋结点和一个后继结点。 （2）树：一对多。有且仅有一个开始结点，可有若干个终端结点，其余的内部结点都有且仅有一个前趋结点，可以有若干个后继结点。 （3）图：多对多。可有若干个开始结点和终端结点，其余的内部结点可以有若干个前趋结点和若干个后继结点。42.正确答案: （1）如果L的长度不小于2，将L的首元结点变成尾元结点。 （2）将单循环链表拆成两个单循环链表。43.