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

2022年南京大学计算机科学与技术专业《数据结构与算法》科目期末试卷A（有答案）一、选择题1、下述文件中适合于磁带存储的是（）。A.顺序文件B.索引文件C.哈希文件D.多关键字文件2、下列排序算法中，占用辅助空间最多的是（）。A.归并排序B.快速排序C.希尔排序D.堆排序3、单链表中，增加一个头结点是为了（）。A.使单链表至少有一个结点B.标识表结点中首结点的位置C.方便运算的实现D.说明单链表是线性表的链式存储4、循环队列A[0..m-1]存放其元素值，用front和rear分别表示队头和队尾，则当前队列中的元素数是（）。A.（rear-front+m）%mB.rear-front+1C.rear-front-1D.rear-front5、在下列表述中，正确的是（）A.含有一个或多个空格字符的串称为空格串B.对n（n>0）个顶点的网，求出权最小的n-1条边便可构成其最小生成树C.选择排序算法是不稳定的D.平衡二叉树的左右子树的结点数之差的绝对值不超过l6、下列选项中，不能构成折半查找中关键字比较序列的是（）。A．500，200，450，180B．500，450，200，180C．180，500，200，450D．180，200，500，4507、已知关键字序列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、一个具有1025个结点的二叉树的高h为（）。A.11B.10C.11至1025之间D.10至1024之间9、设X是树T中的一个非根结点，B是T所对应的二叉树。在B中，X是其双亲的右孩子，下列结论正确的是（）。A.在树T中，X是其双亲的第一个孩子B.在树T中，X一定无右兄弟C.在树T中，X一定是叶结点D.在树T中，X一定有左兄弟10、对序列{15，9，7，8，20，-1，4}用希尔排序方法排序，经一趟后序列变为{15，-1，4，8，20，9，7}则该次采用的增量是（）。A.1B.4C.3D.2二、填空题11、在有n个顶点的有向图中，每个顶点的度最大可达______。12、N个顶点的连通图用邻接矩阵表示时，该矩阵至少有______个非零元素。13、在单链表L中，指针P所指结点有后继结点的条件是______。14、关键码序列（Q，H，C，Y，Q，A，M，S，R，D，F，X），要按照关键码值递增的次序进行排序，若采用初始步长为4的希尔排序法，则一趟扫描的结果是______；若采用以第一个元素为分界元素的快速排序法，则扫描一趟的结果是______。15、设有两个算法在同一机器上运行，其执行时闻分别为100n2和2n，要使前者快于后者，n至少为______。16、一棵有n个结点的满二叉树有______个度为1的结点、有______个分支（非终端）结点和______个叶子，该满二叉树的深度为______。17、设数组A[0..8，1..10]，数组中任一元素A[i，j]均占内存48个二进制位，从首地址2000开始连续存放在主内存里，主内存字长为16位，那么（1） 存放该数组至少需要的单元数是______。（2） 存放数组的第8列的所有元素至少需要的单元数______。（3） 数组按列存储时，元素A[5，8]的起始地址是______。18、假设一个15阶的上三角矩阵A按行优先顺序压缩存储在一维数组B中，则非零元素A9.9在B中的存储位置k=______。（注：矩阵元素下标从1开始）三、判断题19、对磁带机而言，ISAM是一种方便的文件组织方法（）20、直接访问文件也能顺序访问，只是一般效率不高。（）21、KMP算法的特点是在模式匹配时指示主串的指针不会变小。（）22、一个广义表可以为其他广义表所共享。（）23、深度为k的二叉树中结点总数小于等于2k-1。（）24、树形结构中元素之间存在一对多的关系。（）25、外部排序是把外存文件调入内存，可利用内部排序的方法进行排序，因此排序所花的时间取决于内部排序的时间。（）26、快速排序和归并排序在最坏情况下的比较次数都是O（nlog2n）。（）27、连通图上各边权值均不相同，则该图的最小生成树是唯一的。（）28、对两棵具有相同关键字集合的而形状不同的二叉排序树，按中序遍历它们得到的序列的顺序却是一致的。（）四、简答题29、写出下列排序算法的基本思想，并写出对序列（23，12，35，47，16，25，36，19，21，16）进行排序时每一趟的结果。30、阅读下面的算法，说明算法实现的功能。31、已知世界六大城市为：北京(Pe)、纽约(N)、巴黎(Pa)、伦敦(L)、东京(T)、墨西哥(M)，下表给定了这六大城市之间的交通里程：世界六大城市交通里程表(单位：百公里)（1）画出这六大城市的交通网络图。（2）画出该图的邻接表表示法。（3）画出该图按权值递增的顺序来构造的最小（代价）生成树。五、算法设计题32、以顺序存储结构表示串，设计算法。求串s中出现的第一个最长重复子串及其位置并分析算法的时间复杂度。33、试编写一算法对二叉树按前序线索化。34、编写递归算法，从大到小输出给定二叉排序树中所有关踺字不小于x的数据元素。要求你的算法的时间复杂度为O（log2（x+m）），其中，2为排序树中所含结点数，m为输出的关键字个数。35、编写一算法，利用叶结点中的空指针域将所有叶结点链接为一个带有头结点的双链表，算法返回头结点的地址。

参考答案一、选择题1、【答案】A2、【答案】A3、【答案】C4、【答案】A5、【答案】C6、【答案】A7、【答案】A8、【答案】C9、【答案】D10、【答案】B二、填空题11、【答案】2(n-1)12、【答案】2(N-1)13、【答案】P->next!=NULL14、【答案】（Q，A，C，S，Q，D，F，X，R，H，M,Y）；（F，H，C，D，a，A，M，Q，R，S，Y，X）15、【答案】1516、【答案】【解析】满二叉树没有度为1的结点，度为0的结点等于度为2的结点个数+1。17、【答案】270；27；220418、【答案】93三、判断题19、【答案】×20、【答案】×21、【答案】√22、【答案】√23、【答案】√24、【答案】√25、【答案】×26、【答案】×27、【答案】√28、【答案】√四、简答题29、答：此排序为双向起泡排序：从前向后一趟排序下来得到一个最大值，若其中发生交换，则再从后向前一趟排序，得到一个最小值。第一趟：12，23，35，16，25，36，19，21，16，47第二趟：12，16，23，35，16，25，36，19，21，47第三趟：12，16，23，16，25，35，19，21，36，47第四趟：12，16，16，23，19，25，35，21，36，47第五趟：12，16，16，19，23，25，21，35，36，47第六趟：12，16，16，19，21，23，25，35，36，47第七趟：12，16，16，19，21，23，25，35，36，4730、答：本算法功能是将两个无头结点的循环链表合并为一个循环链表。head1最后一个结点的链域指向head2，head2最后一个结点的链域指向head1，head1为结果循环链表的指针。31、答：(1)这六大城市的交通网络图如图所示：(2)该图的邻接表表示法如图所示：