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

2022年首都师范大学计算机科学与技术专业《数据结构与算法》科目期末试卷A（有答案）一、选择题1、将线性表的数据元素进行扩充，允许带结构的线性表是（）。A.串B.树C.广义表D.栈2、将两个各有N个元素的有序表归并成一个有序表，其最少的比较次数是（）。A.NB.2N-1C.2ND.N-13、连续存储设计时，存储单元的地址（）。A.一定连续B.一定不连续C.不一定连续D.部分连续，部分不连续4、向一个栈顶指针为h的带头结点的链栈中插入指针s所指的结点时，应执行（）。A.h->next=sB.s->next=hC.s->next=h;h->next=sD.s->next=h-next;h->next=s5、已知串S='aaab'，其next数组值为（）。A.0123B.1123C.1231D.12116、已知关键字序列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，197、若一棵二叉树的前序遍历序列为a，e，b，d，c，后序遍历序列为b，c，d，e，a，则根结点的孩子结点（）。A．只有eB．有e、bC．有e、cD．无法确定8、已知一棵二叉树的前序遍历结果为ABCDEF，中序遍历结果为CBAEDF，则后序遍历结果为（）。A.CBEFDAB.FEDCBAC.CBEDFAD.不定9、在下述结论中，正确的有（）。①只有一个结点的二叉树的度为0。②二叉树的度为2。③二叉树的左右子树可任意交换。④深度为K的完全二叉树的结点个数小于或等于深度相同的满二叉树。A.①②③B.⑦③④C.②④D.①④10、在文件“局部有序”或文件长度较小的情况下，最佳内部排序的方法是（）。A.直接插入排序B.起泡排序C.简单选择排序D.快速排序二、填空题11、如果按关键码值递增的顺序依次将关键码值插入到二叉排序树中，则对这样的二叉排序树检索时，平均比较次数为______。12、若用n表示图中顶点数目，则有______条边的无向图成为完全图。13、VSAM（虚拟存储存取方法）文件的优点是：动态地______，不需要文件进行______，并能较快地______进行查找。14、应用Prim算法求解连通网络的最小生成树问题。（1）针对如图所示的连通网络，试按如下格式给出在构造最小生成树过程中顺序选出的各条边。（2）下面是Prim算法的实现，中间有5个地方缺失，请阅读程序后将它们补上。15、以下是用类C语言写出的算法，该算法将以二叉链表存储的二叉树中的叶结点按从左到右的顺序链成一个带头结点的双向循环链表，链接时，结点的Lchild域作为前链域，指向结点的直接前驱，结点的Rchild域作为后链域，指向结点的直接后继。算法中，使用一个顺序栈stack，栈顶指针为top，p，t为辅助指针，head为双向循环链表的头指针。试填充算法中的空格，使算法完整。16、一棵有n个结点的满二叉树有______个度为1的结点、有______个分支（非终端）结点和______个叶子，该满二叉树的深度为______。17、下列程序是快速排序的非递归算法，请填写适当的语句，完成该功能。18、阅读下列程序说明和程序，填充程序中的______。【程序说明】本程序完成将二叉树中左、右孩子交换的操作。交换的结果如下所示（编者略）。本程序采用非递归的方法，设立一个堆栈stack存放还没有转换过的结点，它的栈顶指针为tp。交换左、右子树的算法为：（1）把根结点放入堆栈。（2）当堆栈不空时，取出栈顶元素，交换它的左、右子树，并把它的左、右子树分别入栈。（3）重复（2）直到堆栈为空时为止。三、判断题19、哈希表与哈希文件的唯一区别是哈希文件引入了“桶”的概念。（）20、对磁带机而言，ISAM是一种方便的文件组织方法（）21、数组不适合作为任何二叉树的存储结构。（）22、设模式串的长度为m，目标串的长度为n，当n≈m且处理只匹配一次的模式时，朴素的匹配（即子串定位函数）算法所花的时间代价可能会更为节省。（）23、树形结构中元素之间存在一对多的关系。（）24、一个树形的叶结点，在前序遍历和后序遍历下，皆以相同的相对位置出现。（）25、顺序存储方式的优点是存储密度大，且插入、删除运算效率高。（）26、归并排序辅助存储为O（1）。（）27、B-树中所有结点的平衡因子都为零。（）28、有向图中顶点V度等于其邻接矩阵中第V行中的1的个数。（）四、简答题29、调用下列C函数f（n），回答下列问题：（1）试指出f（n）值的大小，并写出，f（n）值的推导过程。（2）假定n=5，试指出，f（5）值的大小和执行，f（5）时的输出结果。C函数：30、下面程序段的时间复杂度是什么？31、已知世界六大城市为：北京(Pe)、纽约(N)、巴黎(Pa)、伦敦(L)、东京(T)、墨西哥(M)，下表给定了这六大城市之间的交通里程：世界六大城市交通里程表(单位：百公里)（1）画出这六大城市的交通网络图。（2）画出该图的邻接表表示法。（3）画出该图按权值递增的顺序来构造的最小（代价）生成树。五、算法设计题32、在一棵以二叉链表表示的二叉树上，试写出按层次顺序遍历二叉树的方法，统计树中具有度为1的结点数目的算法。33、试编写一算法对二叉树按前序线索化。34、请用流程图或高级语言表示算法。已知有向图有n个顶点，请写算法，根据用户输入的数对建立该有向图的邻接表。即接受用户输入的<vi，vj>(以其中之一为0标志结束)，对于每条这样的边，申请一个结点，并插入到的单链表中，如此反复，直到将图中所有边处理完毕。提示：先产生邻接表的n个头结点(其结点数值域从1到n)。35、已知两个定长数组，它们分别存放两个非降序有序序列，请编写程序把第二个数组序列中的数逐个插入到前一个数组序列中，完成后两个数组中的数分别有序（非降序）并且第一数组中所有的数都不大于第二个数组中的任意一个数。注意，不能另开辟数组，也不能对任意一个数组进行排序操作。例如：第一个数组为：4，12，28第二个数组为：1，7，9，29，45输出结果为：l，4，7……第一个数组9，12，28，29，45……第二个数组

参考答案一、选择题1、【答案】C2、【答案】A3、【答案】A4、【答案】D5、【答案】A6、【答案】A7、【答案】A8、【答案】A9、【答案】D10、【答案】A二、填空题11、【答案】（n+1）/212、【答案】n(n-1)/213、【答案】分配和释放存储空间；重组；对插入的记录@14、【答案】(1)(0，3，1)；(3，5，4)；(5，2，2)；(3，1，5)；(1，4，3)(2)①T[k]；toVex=i②min=MaxInt;③mispos=i④exit(0)⑤T[i]；fromVex=v【解析】Prim算法的执行类似于寻找图的最短路径的Dijkstra算法。假设N={V，E}是连通图，ET是N上最小生成树边的集合。算法从VT={u0}，ET开始，重复执行下述操作：在所有u属于VT，v属于V-VT的边（u，v）属于E中找一条代价最小的边（u0，v0）加入集合ET，同时将v0并入VT，直到VT=V为止。15、【答案】p->Rchild=t；t->Lchild=p；p=t；t->Rchild!=null；t->Rchild；t->Lchild!=null；t->Lchild；p->Rchild=head；head->Lchild=p16、【答案】【解析】满二叉树没有度为1的结点，度为0的结点等于度为2的结点个数+1。17、【答案】a[j]=a[k]；low=stack[top][0]；stack[top][0]=k+1【解析】快速排序(quicksort)的基本思想是，通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。18、【答案】stack[tp]=t；p=stack[tp--]；p；++tp【解析】本题主要使用堆栈完成了二叉树左右子树交换的操作。首先根结点进栈，然后判断栈是否为空，如果不为空，则取栈顶元素，交换取出结点的左右指针。并将左右指针分别进栈，重复这一操作。完成二叉树左右孩子的交换。三、判断题19、【答案】×20、【答案】×21、【答案】×22、【答案】√23、【答案】√24、【答案】√25、【答案】×26、【答案】×27、【答案】√28、【答案】×四、简答题29、答：（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，执行过程中，输出结果为：30、答：赋值语句一共被执