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

2022年吉首大学计算机科学与技术专业《数据结构与算法》科目期末试卷A（有答案）一、选择题1、下列说法不正确的是（）。A.图的遍历是从给定的源点出发每个顶点仅被访问一次B.遍历的基本方法有两种：深度遍历和广度遍历C.图的深度遍历不适用于有向图D.图的深度遍历是一个递归过程2、用数组r存储静态链表，结点的next域指向后继，工作指针j指向链中结点，使j沿链移动的操作为（）。A.j=r[j].nextB.j=j+lC.j=j->nextD.j=r[j]->next3、算法的计算量的大小称为计算的（）。A.效率B.复杂性C.现实性D.难度4、有六个元素6，5，4，3，2，1顺序入栈，下列不是合法的出栈序列的是（）。A.543612B.453126C.346521D.2341565、下面关于串的叙述中，不正确的是（）。A.串是字符的有限序列B.空串是由空格构成的串C.模式匹配是串的一种重要运算D.串既可以采用顺序存储，也可以采用链式存储6、下列关于无向连通图特性的叙述中，正确的是（）。Ⅰ．所有的顶点的度之和为偶数Ⅱ．边数大于顶点个数减1Ⅲ．至少有一个顶点的度为1A．只有ⅠB．只有ⅡC．Ⅰ和ⅡD．Ⅰ和Ⅲ7、下列选项中，不能构成折半查找中关键字比较序列的是（）。A．500，200，450，180B．500，450，200，180C．180，500，200，450D．180，200，500，4508、一棵哈夫曼树共有215个结点，对其进行哈夫曼编码，共能得到（）个不同的码字。A.107B.108C.214D.2159、在下述结论中，正确的有（）。①只有一个结点的二叉树的度为0。②二叉树的度为2。③二叉树的左右子树可任意交换。④深度为K的完全二叉树的结点个数小于或等于深度相同的满二叉树。A.①②③B.⑦③④C.②④D.①④10、在文件“局部有序”或文件长度较小的情况下，最佳内部排序的方法是（）。A.直接插入排序B.起泡排序C.简单选择排序D.快速排序二、填空题11、对n个记录的表r[1..n]进行简单选择排序，所需进行的关键字间的比较次数为______。12、起始地址为480，大小为8的块，其伙伴块的起始地址是______；若块大小为32，则其伙伴块的起始地址为______。13、数据结构中评价算法的两个重要指标是______。14、数据结构是研讨数据的______和______以及它们之间的相互关系，并对与这种结构定义相应的______，设计出相应的______。15、按LSD进行关键字排序，除最次位关键字之外，对每个关键字进行排序时，只能用______的排序方法。16、每一棵树都能唯一地转换为它所对应的二叉树。若已知一棵二叉树的前序序列是BEFCGDH，中序序列是FEBGCHD，则它的后序序列是______。设上述二叉树是由某棵树转换而成，则该树的前序序列是______。17、一棵有n个结点的满二叉树有______个度为1的结点、有______个分支（非终端）结点和______个叶子，该满二叉树的深度为______。18、在顺序存储的二叉树中，编号为i和j的两个结点处在同一层的条件是______。三、判断题19、倒排文件的目的是为了多关键字查找。（）20、哈希表与哈希文件的唯一区别是哈希文件引入了“桶”的概念。（）21、循环队列也存在空间溢出问题。（）22、广义表（（（a，b，c），d，e，f））的长度是4。（）23、对于有n个结点的二叉树，其高度为log2n。（）24、二叉树是一般树的特殊情形。（）25、排序算法中的比较次数与初始元素序列的排列无关。（）26、为提高排序速度，进行外排序时，必须选用最快的内排序算法。（）27、无环有向图才能进行拓扑排序。（）28、采用线性探测法处理散列时的冲突，当从哈希表删除一个记录时，不应将这个记录的所在位置置空，因为这会影响以后的查找。（）四、简答题29、阅读下面的算法，说明算法实现的功能。30、调用下列C函数f（n），回答下列问题：（1）试指出f（n）值的大小，并写出，f（n）值的推导过程。（2）假定n=5，试指出，f（5）值的大小和执行，f（5）时的输出结果。C函数：31、设二叉树BT的存储结构如表：其中BT为树根结点的指针，其值为6，Lchild、Rchild分别为结点的左、右孩子指针域data为结点的数据域。试完成下列各题：（1）画出二叉树BT逻辑结构。（2）写出按前序、中序、后序遍历该二叉树所得到的结点序列。（3）画出二叉树的后序线索树。五、算法设计题32、假设有两个按元素值递增次序排列的线性表，均以单链表形式存储。请编写算法将这两个单链表归并为一个按元素值递减次序排列的单链表，并要求利用原来两个单链表的结点存放归并后的单链表。33、给定一个整数数组b[0..N-1]，b中连续的相等元素构成的子序列称为平台。试设计算法，求出b中最长平台的长度。34、图G有n个点，利用从某个源点到其余各点最短路径算法思想，设计一产生G的最小生成树的算法。35、设二叉排序树的各元素值均不相同，采用二叉链表作为存储结构，试分别设计递归和非递归算法按递减序打印所有左子树为空，右子树非空的结点的数据域的值。

参考答案一、选择题1、【答案】C2、【答案】A3、【答案】B4、【答案】C5、【答案】B6、【答案】A7、【答案】A8、【答案】B9、【答案】D10、【答案】A二、填空题11、【答案】n（n-1）/212、【答案】480+8=488；480-32=44813、【答案】算法的时间复杂度和空间复杂度14、【答案】逻辑结构；物理结构；操作（运算）；算法15、【答案】稳定16、【答案】FEGHDCB；BEF【解析】树的前序序列对应二叉树的前序序列，该二叉树转换成森林时含三棵树，其第一棵树的前序是BEF。17、【答案】【解析】满二叉树没有度为1的结点，度为0的结点等于度为2的结点个数+1。18、【答案】【解析】用顺序存储结构存储二叉树时，要按完全二叉树的形式存储，非完全二叉树存储时，要加“虚结点”。设编号为i和j的结点在顺序存储中的下标为s和t，则结点i和j在同一层上的条件是三、判断题19、【答案】√20、【答案】×21、【答案】√22、【答案】×23、【答案】×24、【答案】×25、【答案】×26、【答案】×27、【答案】√28、【答案】√四、简答题29、答：本算法功能是将两个无头结点的循环链表合并为一个循环链表。head1最后一个结点的链域指向head2，head2最后一个结点的链域指向head1，head1为结果循环链表的指针。30、答：（1）第一层for循环判断n+1次，往下执行n次，第二层for执行次数为（n+（n-1）+（n-2）+…+1），第三层循环体受第一层循环和第二层循环的控制，其执行次数如表1-1所示。执行次数为f(n)=（1+2+…+，n）+（2+3+…+，n）+…+n=n*n（n+1）/2-n（n2-1）/6。（2）在n=5对，f（5）=55，执行过程中，输出结果为：31、答：（1）二叉树