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

2022年黄山学院计算机科学与技术专业《数据结构与算法》科目期末试卷A（有答案）一、选择题1、下列排序算法中，占用辅助空间最多的是（）。A.归并排序B.快速排序C.希尔排序D.堆排序2、无向图G=(V，E)，其中：V={a，b，c，d，e，f}，E={(a，b)，(a，e)，(a，c)，(b，e)，(c，f)，(f，d)，(e，d)}，对该图进行深度优先遍历，得到的顶点序列正确的是（）。A.a，b，e，c，d，fB.a，c，f,e，b，dC.a，e，b，c，f,dD.a，e，d，f，c，b3、线性表的顺序存储结构是一种（）。A.随机存取的存储结构B.顺序存取的存储结构C.索引存取的存储结构D.Hash存取的存储结构4、有六个元素6，5，4，3，2，1顺序入栈，下列不是合法的出栈序列的是（）。A.543612B.453126C.346521D.2341565、已知有向图G=(V，E)，其中V={V1，V2，V3，V4，V5，V6，V7}，E=｛<V1，V2>，<V1，V3>，<V1，V4>，<V2，V5>，<V3，V5>，<V3，V6>，<V4，V6>，<V5，V7>，<V6，V7>｝，G的拓扑序列是（）。A.V1，V3，V4，V6，V2，V5，V7B.V1，V3，V2，V6，V4，V5，V7C.V1，V3，V5，V2，V6，V7D.V1，V2，V5，V3，V4，V6，V76、若一棵二叉树的前序遍历序列为a，e，b，d，c，后序遍历序列为b，c，d，e，a，则根结点的孩子结点（）。A．只有eB．有e、bC．有e、cD．无法确定7、已知关键字序列5，8，12，19，28，20，15，22是小根堆（最小堆），插入关键字3，调整后的小根堆是（）。A．3，5，12，8，28，20，15，22，19B．3，5，12，19，20，15，22，8，28C．3，8，12，5，20，15，22，28，19D．3，12，5，8，28，20，15，22，198、有n（n>0）个分支结点的满二叉树的深度是（）。A.n2-1B.log2（n+1）+1C.log2（n+1）D.log2（n-l）9、设X是树T中的一个非根结点，B是T所对应的二叉树。在B中，X是其双亲的右孩子，下列结论正确的是（）。A.在树T中，X是其双亲的第一个孩子B.在树T中，X一定无右兄弟C.在树T中，X一定是叶结点D.在树T中，X一定有左兄弟10、对n个记录的线性表进行快速排序为减少算法的递归深度，以下叙述正确的是（）。A.每次分区后，先处理较短的部分B.每次分区后，先处理较长的部分C.与算法每次分区后的处理顺序无关D.以上三者都不对二、填空题11、有向图G=(V，E)，其中V(G)={0，1，2，3，4，5｝，用<a，b，d>三元组表示弧<a，b>及弧上的权d。E(G)为E(G)=｛<0，5，100>，<0，2，10>，<1，2，5>，<0，4，30>，<4，5，60>，<3，5，10>，<2，3，50>，<4，3，20>｝，则从源点0到顶点3的最短路径长度是______，经过的中间顶点是______。12、设用希尔排序对数组{98，36，-9，0，47，23，1，8，10，7}进行排序，给出的步长（也称增量序列）依次是4，2，1则排序需______趟，写出第一趟结束后，数组中数据的排列次序______。13、在基于关键字比较且时间为O（nlog2n）的排序中，若要求排序是稳定的，则可选用______排序；若要求就地排序（及辅助空间为O（1）），则可选用______排序。14、数据结构是研讨数据的______和______以及它们之间的相互关系，并对与这种结构定义相应的______，设计出相应的______。15、线性表L=（a1，a2，…，an）用数组表示，假定删除表中任一元素的概率相同，则删除一个元素平均需要移动元素的个数是______。16、设正文串长度为n，模式串长度为m，则串匹配的KMP算法的时间复杂度为______。17、设广义表L=（（），（）），则head（L）是______；tail（L）是______；L的长度是______；深度是______。18、设有一个空栈，栈顶指针为1000H（十六进制），现有输入序列为l，2，3，4，5，经过PUSH，PUSH，POP，PUSH，POP，PUSH，PUSH之后，输出序列是______，而栈顶指针值是______。设栈为顺序栈，每个元素占4个字节。三、判断题19、对处理大量数据的外存介质而言，索引顺序存取方法是一种方便的文件组织方法。（）20、倒排序文件的优点是维护简单。（）21、广义表（（（a，b，c），d，e，f））的长度是4。（）22、一个广义表可以为其他广义表所共享。（）23、对于有n个结点的二叉树，其高度为log2n。（）24、树形结构中元素之间存在一对多的关系。（）25、顺序存储方式的优点是存储密度大，且插入、删除运算效率高。（）26、若中序遍历平衡的二叉排序树，可得到排好序的关键码序列。（）27、采用线性探测法处理散列时的冲突，当从哈希表删除一个记录时，不应将这个记录的所在位置置空，因为这会影响以后的查找。（）28、有向图中顶点V度等于其邻接矩阵中第V行中的1的个数。（）四、简答题29、对于具有n个叶结点且所有非叶结点都有左、右孩子的二叉树。(1)试问这种二叉树的结点总数是多少?(2)试证明2-（li-1）=1。其中：li表示第i个叶结点所在的层号（设根结点所在层号为1）。30、下面程序段的时间复杂度是什么？31、已知有6个顶点（顶点编号为0～5）的有向带权图G，其邻接矩阵A为上三角矩阵，按行为主序（行优先）保存在如下的一维数组中。要求：（1）写出图G的邻接矩阵A。（2）画出有向带权图G。求图G的关键路径，并计算该关键路径的长度。五、算法设计题32、当一棵有n（n≤100）个结点的二叉树按顺序存储方式存储在bt[1..n]中时，试写一个算法，求出二叉树中结点值分别为x和y的两个结点的最近公共祖先结点的值。33、写出一趟快速排序算法。34、已知字符串s1中存放一段英文，写出算法format（s1，s2，s3，n），将其按给定的长度n格式化成两端对齐的字符串s2，其多余的字符送s3。35、在输入数据无序的情况下，建立一个数据值为整型的递增有序的顺序存储线性表L，且要求当输入相同数据值时，线性表中不能存在数据值相同的数据元素，试写出其算法。顺序存储结构的线性表描述为：

参考答案一、选择题1、【答案】A2、【答案】D3、【答案】A4、【答案】C5、【答案】A6、【答案】A7、【答案】A8、【答案】C9、【答案】D10、【答案】A二、填空题11、【答案】50；412、【答案】3；（10，7，-9，0，47，23，1，8，98，36）@13、【答案】归并；堆14、【答案】逻辑结构；物理结构；操作（运算）；算法15、【答案】（n-1）/216、【答案】O（m+n）17、【答案】（）；（（））；2；218、【答案】23；100CH三、判断题19、【答案】×20、【答案】×21、【答案】×22、【答案】√23、【答案】×24、【答案】√25、【答案】×26、【答案】√27、【答案】√28、【答案】×四、简答题29、答：（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）+2-（t+1-1），所以结果不变，这就证明当i=n时公式仍成立。证毕。30、答：赋值语句一共被执行了m*n次，所以该程序段的时间复杂度是O（m*n）。31、答：（1）由题可以画出待定上三角矩阵的结构图如下（图中？为待定元素）：可以看出，第一行至第五行主对角线上方的