2026年长沙理工大学城南学院计算机科学与技术专业《数据结构与算法》科目期末试卷A(有答案)

2026年长沙理工大学城南学院计算机科学与技术专业《数据结构与算法》科目期末试卷A（有答案）一、选择题1、已知广义表LS=（（a，b，c），（d，e，f）），用head和tail数取出LS中原子e的运算是（）。A.head（tail（LS））B.tail（head（LS））C.head（tail（head（tail（LS））））D.head（tail（tail（head（LS））））2、用有向无环图描述表达式(A+B)*((A+B)／/A)，至少需要顶点的数目为（）。A.5B.6C.8D.93、链表不具有的特点是（）。A.插入、删除不需要移动元素B.可随机访问任一元素C.不必事先估计存储空间D.所需空间与线性长度成正比4、下列关于AOE网的叙述中，不正确的是（）。A.关键活动不按期完成就会影响整个工程的完成时间B.任何一个关键活动提前完成，那么整个工程将会提前完成C.所有的关键活动提前完成，那么整个工程将会提前完成D.某些关键活动若提前完成，那么整个工程将会提前完成5、已知串S='aaab'，其next数组值为（）。A.0123B.1123C.1231D.12116、排序过程中，对尚未确定最终位置的所有元素进行一遍处理称为一趟排序。下列排序方法中，每一趟排序结束时都至少能够确定一个元素最终位置的方法是（）。Ⅰ．简单选择排序Ⅱ．希尔排序Ⅲ．快速排序Ⅳ．堆排Ⅴ．二路归并排序A．仅Ⅰ、Ⅲ、ⅣB．仅Ⅰ、Ⅱ、ⅢC．仅Ⅱ、Ⅲ、ⅣD．仅Ⅲ、Ⅳ、Ⅴ7、下列叙述中，不符合m阶B树定义要求的是（）。A．根结点最多有m棵子树B．所有叶结点都在同一层上C．各结点内关键字均升序或降序排列D．叶结点之间通过指针链接8、一棵哈夫曼树共有215个结点，对其进行哈夫曼编码，共能得到（）个不同的码字。A.107B.108C.214D.2159、有关二叉树下列说法正确的是（）。A.二叉树的度为2B.一棵二叉树的度可以小于2C.二叉树中至少有一个结点的度为2D.二叉树中任何一个结点的度都为210、对关键码序列28，16，32，12，60，2，5，72快速排序，从小到大一次划分结果为（）。A.（2，5，12，16）26（60，32，72）B.（5，16，2，12）28（60，32，72）C.（2，16，12，5）28（60，32，72）D.（5，16，2，12）28（32，60，72）二、填空题11、如果按关键码值递增的顺序依次将关键码值插入到二叉排序树中，则对这样的二叉排序树检索时，平均比较次数为______。12、下面程序的功能是用递归算法将一个整数按逆序存放到一个字符数组中。如123存放成321。请填空：13、如下的算法分别是后序线索二叉树求给定结点node的前驱结点与后继结点的算法，请在算法空格处填上正确的语句。设线索二叉树的结点数据结构为（lflag，left，data，right，rflag），其中：lflag=0，left指向其左孩子，lflag=1，left指向其前驱；rflag=0，right指向其右孩子，rflag=1，right指向其后继。14、在一棵m阶B-树中，若在某结点中插入一个新关键字而引起该结点分裂，则此结点中原有的关键字的个数是______；若在某结点中删除一个关键字而导致结点合并，则该结点中原有的关键字的个数是______。15、线性表L=（a1，a2，…，an）用数组表示，假定删除表中任一元素的概率相同，则删除一个元素平均需要移动元素的个数是______。16、设T和P是两个给定的串，在T中寻找等于P的子串的过程称为______，又称P为______。17、已知链队列的头尾指针分别是f和r，则将值x入队的操作序列是______。18、设有一个10阶对称矩阵A采用压缩存储方式（以行为主序存储：a11=1），则a85的地址为______。三、判断题19、哈希表与哈希文件的唯一区别是哈希文件引入了“桶”的概念。（）20、直接访问文件也能顺序访问，只是一般效率不高。（）21、循环队列也存在空间溢出问题。（）22、设模式串的长度为m，目标串的长度为n，当n≈m且处理只匹配一次的模式时，朴素的匹配（即子串定位函数）算法所花的时间代价可能会更为节省。（）23、树形结构中元素之间存在一对多的关系。（）24、任何二叉树的后序线索树进行后序遍历时都必须用栈。（）25、线性表采用链表存储时，结点和结点内部的存储空间可以是不连续的。（）26、在一个设有头指针和尾指针的单链表中，执行删除该单链表中最后一个元素的操作与链表的长度无关。（）27、连通图上各边权值均不相同，则该图的最小生成树是唯一的。（）28、对两棵具有相同关键字集合的而形状不同的二叉排序树，按中序遍历它们得到的序列的顺序却是一致的。（）四、简答题29、s是字符数组，s[0]中存放的是该字符串的有效长度，假设s[1..7]中字符串的内容为"abcabaa"，说明下列程序的功能及执行结果。30、三维数组A[1..10，-2..6，2..8]的每个元素的长度为4个字节，试问该数组要占多少个字节的存储空间?如果数组元素以行优先的顺序存储，设第一个元素的首地址是100，试求元素A[5，0，7]的存储首地址。31、已知有6个顶点（顶点编号为0～5）的有向带权图G，其邻接矩阵A为上三角矩阵，按行为主序（行优先）保存在如下的一维数组中。要求：（1）写出图G的邻接矩阵A。（2）画出有向带权图G。求图G的关键路径，并计算该关键路径的长度。五、算法设计题32、已知字符串s1中存放一段英文，写出算法format（s1，s2，s3，n），将其按给定的长度n格式化成两端对齐的字符串s2，其多余的字符送s3。33、（1）试分别找出满足下列条件的所有二叉树：（a）前序序列和中序序列相同：（b）前序序列和后序序列相同；（c）中序序列和后序序列相同。（2）已知非空二叉树的结点结构为（lchild，data，rchild），设计算法：从右向左依次将所有叶子的数据值放到向量（假定向量的空间大于叶子的总个数）中。34、假设一个仅包含二元运算符的算术表达式以链表形式存储在二叉树BT中，写出计算该算术表达式值的算法。35、假设串的存储结构如下所示，编写算法实现串的置换操作。

参考答案一、选择题1、【答案】C2、【答案】A3、【答案】B4、【答案】B5、【答案】A6、【答案】A7、【答案】D8、【答案】B9、【答案】B10、【答案】B二、填空题11、【答案】（n+1）/212、【答案】a+1；n%10【解析】通过递归算法，首先找到最高位的值，将其放到str对应的数组中，依次反向获取从高位到地位的值，将其放到数组中，完成了将整数逆序放到一个字符数组中。13、【答案】node->rflag==0；*x=bt；*x=node->right；prior（t，x）14、【答案】【解析】m阶B-树除根结点和叶子结点外，结点中关键字个数最多是m1，最少15、【答案】（n-1）/216、【答案】模式匹配；模式串17、【答案】s=（LinkedList*）ma11oc（sizeof（LNode））；s->data=x；s->next=r->next；r->next=s；r=s。18、【答案】33三、判断题19、【答案】×20、【答案】×21、【答案】√22、【答案】√23、【答案】√24、【答案】×25、【答案】×26、【答案】×27、【答案】√28、【答案】√四、简答题29、答：本程序的功能是求字符串的nextval函数，程序执行结果是0110132。30、答：数组占的存储字节数=10*9*7*4=2520；A[5，0，7]的存储地址=100+[4*9*7+2*7+5]*4=1184。31、答：（1）由题可以画出待定上三角矩阵的结构图如下（图中？为待定元素）：可以看出，第一行至第五行主对角线上方的元素分别为5，4，3，2，1个，由此可以画出压缩存储数组中的元素所属行的情况，如下图所示：将各元素填入各行即得邻接矩阵：（2）根据第一步所得矩阵A容易做出有向带权图G，如下：（3）关键路径为0-＞1-＞2-＞3-＞5（如下图所示粗线表示