2022年吉首大学张家界学院计算机科学与技术专业《数据结构与算法》科目期末试卷A(有答案)

2022年吉首大学张家界学院计算机科学与技术专业《数据结构与算法》科目期末试卷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、最大容量为n的循环队列，队尾指针是rear，队头：front，则队空的条件是（）。A.（rear+1）MODn=frontB.rear=frontC.rear+1=frontD.（rear-1）MODn=front5、有六个元素6，5，4，3，2，1顺序入栈，下列不是合法的出栈序列的是（）。A.543612B.453126C.346521D.2341566、下列选项中，不能构成折半查找中关键字比较序列的是（）。A．500，200，450，180B．500，450，200，180C．180，500，200，450D．180，200，500，4507、下列叙述中，不符合m阶B树定义要求的是（）。A．根结点最多有m棵子树B．所有叶结点都在同一层上C．各结点内关键字均升序或降序排列D．叶结点之间通过指针链接8、在下述结论中，正确的有（）。①只有一个结点的二叉树的度为0。②二叉树的度为2。③二叉树的左右子树可任意交换。④深度为K的完全二叉树的结点个数小于或等于深度相同的满二叉树。A.①②③B.⑦③④C.②④D.①④9、下述二叉树中，哪一种满足性质：从任一结点出发到根的路径上所经过的结点序列按其关键字有序（）。A.二叉排序树B.哈夫曼树C.AVL树D.堆10、对关键码序列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、设用希尔排序对数组{98，36，-9，0，47，23，1，8，10，7}进行排序，给出的步长（也称增量序列）依次是4，2，1则排序需______趟，写出第一趟结束后，数组中数据的排列次序______。12、属于不稳定排序的有______。13、在单链表L中，指针P所指结点有后继结点的条件是______。14、外排序的基本操作过程是______和______。15、索引顺序文件既可以顺序存取，也可以______存取。16、每一棵树都能唯一地转换为它所对应的二叉树。若已知一棵二叉树的前序序列是BEFCGDH，中序序列是FEBGCHD，则它的后序序列是______。设上述二叉树是由某棵树转换而成，则该树的前序序列是______。17、已知一循环队列的存储空间为[m..n]，其中n>m，队头和队尾指针分别为front和rear，则此循环队列判满的条件是______。18、设有一个10阶对称矩阵A采用压缩存储方式（以行为主序存储：a11=1），则a85的地址为______。三、判断题19、倒排文件的目的是为了多关键字查找。（）20、直接访问文件也能顺序访问，只是一般效率不高。（）21、循环队列也存在空间溢出问题。（）22、二维以上的数组其实是一种特殊的广义表。（）23、用一维数组存储二叉树时，总是以前序遍历顺序存储结点。（）24、哈夫曼树度为1的结点数等于度为2和0的结点数之差。（）25、数据的逻辑结构是指数据的各数据项之间的逻辑关系。（）26、算法的优劣与算法描述语言无关，但与所用计算机有关。（）27、在动态存储管理系统中做空间分配时，最佳适配法与最先适配法相比，前者容易增加闲置空间的碎片。（）28、采用线性探测法处理散列时的冲突，当从哈希表删除一个记录时，不应将这个记录的所在位置置空，因为这会影响以后的查找。（）四、简答题29、阅读下面的算法，说明算法实现的功能。30、对于具有n个叶结点且所有非叶结点都有左、右孩子的二叉树。(1)试问这种二叉树的结点总数是多少?(2)试证明2-（li-1）=1。其中：li表示第i个叶结点所在的层号（设根结点所在层号为1）。31、已知图的邻接矩阵为：当用邻接表作为图的存储结构，且邻接点都按序号从大到小排列时，试写出：(1)以顶点V1为出发点的唯一的深度优先遍历序列。当用邻接表作为图的存储结构，且邻接点都按序号从大到小排列时，试写出：(1)以顶点V1为出发点的唯一的深度优先遍历序列。(2)以顶点V1为出发点的唯一的广度优先遍历序列。(3)该图唯一的拓扑有序序列。五、算法设计题32、设有一个数组中存放了一个无序的关键序列K1，K2，…，Kn。现要求将Kn放在将元素排序后的正确位置上，试编写实现该功能的算法，要求比较关键字的次数不超过n（注：用程序实现）。33、设A和B均为下三角矩阵，每一个都有n行n列。因此在下三角区域中各有n（n+1）/个元素。另设有一个二维数组C，它有n行n+1列。试设计一个方案，将两个矩阵A和B中的下三角区域元素存放于同一个C中。要求将A的下三角区域中的元素存放于C的下三角区域中，B的下三角区域中的元素转置后存放于C的上三角区域中。并给出计算A的矩阵元素aij，和B的矩阵元素bij在C中的存放位置下标的公式。34、辅助地址表的排序是不改变结点物理位置的排序。辅助地址表实际上是一组指针，用它来指出结点排序后的逻辑顺序地址。设用K[1]，K[2]，…，K[n]表示n个结点的值，用T[1]，T[2]，…，T[n]表示辅助地址表。初始时T[i]：=i，在排序中，凡需对结点交换就用它的地址来进行。例如当n=3时，对K（31，11，19）则有T（2，3，1）。试编写实现辅助地址表排序（按非递减序）算法的语句序列。35、以三元组表存储的稀疏矩阵A，B非零元个数分别为m和n。试用类PASCAL语言编写时间复杂度为O（m+n）的算法将矩阵B加到矩阵A上去。A的空间足够大，不另加辅助空间。要求描述所用结构。

参考答案一、选择题1、【答案】C2、【答案】A3、【答案】B4、【答案】B5、【答案】C6、【答案】A7、【答案】D8、【答案】D9、【答案】D10、【答案】B二、填空题11、【答案】3；（10，7，-9，0，47，23，1，8，98，36）@12、【答案】希尔排序、简单选择排序、快速排序、堆排序等13、【答案】P->next!=NULL14、【答案】生成有序归并段（顺串）；归并15、【答案】随机16、【答案】FEGHDCB；BEF【解析】树的前序序列对应二叉树的前序序列，该二叉树转换成森林时含三棵树，其第一棵树的前序是BEF。17、【答案】（rear+1）%（n-m+1）==front18、【答案】33三、判断题19、【答案】√20、【答案】×21、【答案】√22、【答案】√23、【答案】×24、【答案】×25、【答案】×26、【答案】×27、【答案】√28、【答案】√四、简答题29、答：本算法功能是将两个无头结点的循环链表合并为一个循环链表。head1最后一个结点的链域指向head2，head2最后一个结点的链域指向head1，head1为结果循环链表的指针。30、答：（1）根据二叉树中度为2的结点个数等于叶结点个数减1的性质，故具有n个叶结点且非叶子结点均有左子树的二叉树的结点数是2n-1。（2）证明：当i=1时，2-（1-1）=20=1，公式成立。设当i=n-1时公式成立，证明当i=n时公式仍成立。设某叶结点的层号为t，当将该结点变为内部结点，从而再增加两个叶结点时，这两个叶结点的层号都是t+1，对于公式的变化，是减少了一个原来的叶结点，增加了两个新叶结点，反映到公式中，因为2-（t-1）=2-（t+1-1）+