2026年河北经贸大学计算机科学与技术专业《数据结构与算法》科目期末试卷A(有答案)

2026年河北经贸大学计算机科学与技术专业《数据结构与算法》科目期末试卷A（有答案）一、选择题1、用数组r存储静态链表，结点的next域指向后继，工作指针j指向链中结点，使j沿链移动的操作为（）。A.j=r[j].nextB.j=j+lC.j=j->nextD.j=r[j]->next2、下列排序算法中，占用辅助空间最多的是（）。A.归并排序B.快速排序C.希尔排序D.堆排序3、链表不具有的特点是（）。A.插入、删除不需要移动元素B.可随机访问任一元素C.不必事先估计存储空间D.所需空间与线性长度成正比4、在下列表述中，正确的是（）A.含有一个或多个空格字符的串称为空格串B.对n（n>0）个顶点的网，求出权最小的n-1条边便可构成其最小生成树C.选择排序算法是不稳定的D.平衡二叉树的左右子树的结点数之差的绝对值不超过l5、已知串S='aaab'，其next数组值为（）。A.0123B.1123C.1231D.12116、已知字符串S为“abaabaabacacaabaabcc”，模式串t为“abaabc”，采用KMP算法进行匹配，第一次出现“失配”（s!＝t）时，i＝j＝5，则下次开始匹配时，i和j的值分别（）。A．i＝1，j＝0B．i＝5，j＝0C．i＝5，j＝2D．i＝6，j＝27、下列叙述中，不符合m阶B树定义要求的是（）。A．根结点最多有m棵子树B．所有叶结点都在同一层上C．各结点内关键字均升序或降序排列D．叶结点之间通过指针链接8、一个具有1025个结点的二叉树的高h为（）。A.11B.10C.11至1025之间D.10至1024之间9、一棵非空的二叉树的前序序列和后序序列正好相反，则该二叉树一定满足（）。A.其中任意一个结点均无左孩子B.其中任意一个结点均无右孩子C.其中只有一个叶结点D.其中度为2的结点最多为一个10、下面给出的四种排序方法中，排序过程中的比较次数与排序方法无关的是（）。A.选择排序法B.插入排序法C.快速排序法D.堆排序法二、填空题11、设m、n均为自然数，m可表示为一些不超过n的自然数之和，f（m，n）为这种表示方式的数目。例f（5，3）=5，有5种表示方式：3+2，3+1+1，2+2+1，2+1+1+1，1+1+1+1+1。①以下是该函数的程序段，请将未完成的部分填入，使之完整。②执行程序，f（6，4）=______。12、N个顶点的连通图用邻接矩阵表示时，该矩阵至少有______个非零元素。13、数据结构是研讨数据的______和______以及它们之间的相互关系，并对与这种结构定义相应的______，设计出相应的______。14、文件由______组成；记录由______组成。15、索引顺序文件既可以顺序存取，也可以______存取。16、设T和P是两个给定的串，在T中寻找等于P的子串的过程称为______，又称P为______。17、在顺序存储的二叉树中，编号为i和j的两个结点处在同一层的条件是______。18、一棵有n个结点的满二叉树有______个度为1的结点、有______个分支（非终端）结点和______个叶子，该满二叉树的深度为______。三、判断题19、文件系统采用索引结构是为了节省存储空间。（）20、倒排文件的目的是为了多关键字查找。（）21、队列和栈都是运算受限的线性表，只允许在表的两端进行运算。（）22、在链队列中，即使不设置尾指针也能进行入队操作。（）23、中序遍历一棵二叉排序树的结点就可得到排好序的结点序列。（）24、一个树形的叶结点，在前序遍历和后序遍历下，皆以相同的相对位置出现。（）25、快速排序和归并排序在最坏情况下的比较次数都是O（nlog2n）。（）26、抽象数据类型与计算机内部表示和实现无关。（）27、对大小均为n的有序表和无序表分别进行顺序查找，在等概率查找的情况下，对于查找成功，它们的平均查找长度是相同的，而对于查找失败，它们的平均查找长度是不同的。（）28、在动态存储管理系统中做空间分配时，最佳适配法与最先适配法相比，前者容易增加闲置空间的碎片。（）四、简答题29、用一个数组S（设大小为MAX）作为两个堆栈的共享空间。请说明共享方法，栈满／栈空的判断条件，并用C语言或PASCAL语言设计公用的入栈操作push（i，x），其中i为0或1，用于表示栈号，x为入栈值。30、s是字符数组，s[0]中存放的是该字符串的有效长度，假设s[1..7]中字符串的内容为"abcabaa"，说明下列程序的功能及执行结果。31、已知有6个顶点（顶点编号为0～5）的有向带权图G，其邻接矩阵A为上三角矩阵，按行为主序（行优先）保存在如下的一维数组中。要求：（1）写出图G的邻接矩阵A。（2）画出有向带权图G。求图G的关键路径，并计算该关键路径的长度。五、算法设计题32、设有一个数组中存放了一个无序的关键序列K1，K2，…，Kn。现要求将Kn放在将元素排序后的正确位置上，试编写实现该功能的算法，要求比较关键字的次数不超过n（注：用程序实现）。33、设T是一棵满二叉树，写一个把T的后序遍历序列转换为前序遍历序列的递归算法。34、输入一个字符串，内有数字和非数字字符，如：ak123x4561796073029ef4563。将其中连续的数字作为一个整体，依次存放到一数组a中，例如123放入a[0]，456放入a[1]，……。编程统计其共有多少个整数，并输出这些数。35、请编写一个判别给定二叉树是否为二叉排序树的算法，设二叉树用llink—rlink法存储。

参考答案一、选择题1、【答案】A2、【答案】A3、【答案】B4、【答案】C5、【答案】A6、【答案】C7、【答案】D8、【答案】C9、【答案】C10、【答案】A二、填空题11、【答案】①1；1；f（m，n-1）；n②912、【答案】2(N-1)13、【答案】逻辑结构；物理结构；操作（运算）；算法14、【答案】记录；数据项15、【答案】随机16、【答案】模式匹配；模式串17、【答案】++a*b3*4-cd；18【解析】中缀式相当于中序遍历，前缀式相当于前序遍历，后缀式相当于后序遍历。18、【答案】【解析】满二叉树没有度为1的结点，度为0的结点等于度为2的结点个数+1。三、判断题19、【答案】×20、【答案】√21、【答案】×22、【答案】√23、【答案】√24、【答案】√25、【答案】×26、【答案】√27、【答案】√28、【答案】√四、简答题29、答：两栈共享一向量空间（一维数组），栈底设在数组的两端，两栈顶相邻时为栈满。设共享数组为S[MAX]，则一个栈顶指针为一l，另一个栈顶指针为MAX时，栈为空。用C语言写的入栈操作push（i，x）如下：30、答：本程序的功能是求字符串的nextval函数，程序执行结果是0110132。31、答：（1）由题可以画出待定上三角矩阵的结构图如下（图中？为待定元素）：可以看出，第一行至第五行主对角线上方的元素分别为5，4，3，2，1个，由此可以画出