《2017年北京市培养单位空间应用工程与技术中心863计算机学科综合(专业)之数据结构考研仿真模拟题.doc》由会员分享，可在线阅读，更多相关《2017年北京市培养单位空间应用工程与技术中心863计算机学科综合(专业)之数据结构考研仿真模拟题.doc（4页珍藏版）》请在金锄头文库上搜索。
1、2017年北京市培养单位空间应用工程与技术中心863计算机学科综合(专业)之数据结构考研仿真模拟题一、填空题1 已知如下程序段： 语句1执行的时间复杂度为_；语句2执行的时间复杂度为_；语句3执行的时间复杂度为_；语句4执行的时间复杂度为_。【答案】（1）n 1 （2）n（3）n （n 3）/2 （4）n （n l ）/2【解析】语s 句1执行到不符合条件情况下，执行了n 1次。当语句1不符合条件了是不会执行语句2的，所以语句2被执行了n 次。语句3每次都要执行到不符合条件，故为234. （n l ）加起来就是n （n 3）/2。语句3不符合条件了是不会执行语句4的。所以语句4被执行了123.
2、 n 即n （n l ）/2。2 按LSD 进行关键字排序，除最次位关键字之外，对每个关键字进行排序时，只能用_的排序方法。【答案】稳定 3 阅读下列程序，指出其功能，并写出空格处应填上的语句。 第 2 页，共 58 页 【答案】【解析】本题是在哈希表ht中插入值为的元素，如该元素已在哈希表中，报告出错。4 每一棵树都能唯一地转换为它所对应的二叉树。若已知一棵二叉树的前序序列是.中序序列是前庁序列是_。【答案】 【解析】树的抑序序列对应二叉树的前序序列. 该二叉树转换成森林吋含三棵树. 其第一棵树的前序是。 5 设有两个算法在同一机器上运行，其执行时闻分别为_。【答案】15【解析】当时，而，时
3、， 6 设T 和P 是两个给定的串，在T 中寻找等于P 的子串的过程称为_，又称P 为_。【答案】模式匹配；模式串 7 下面程序的功能是用递归算法将一个整数按逆序存放到一个字符数组中。如123存放成321。请填空： 【答案】 【解析】通过递归算法，首先找到最高位的值，将其放到str 对应的数组中，依次反向获取从高位到地位的值，将其放到数组中，完成了将整数逆序放到一个字符数组中。 8 起始地址为480，大小为8的块，其伙伴块的起始地址是_；若块大小为32，则其伙伴块的起始地址为_。【答案】 【解析】起始地址为P ，大小为的内存块，其伙伴块的起始地址计算公式如下： ，则它的后庁序列是_。设上述二叉
4、树是由某棵树转换而成，则该树的要使前者快于后者，n 至少为第 3 页，共 58 页根据上述公式起始地址就为488。9 线性表用数组表示，假定删除表中任一元素的概率相同，则删除一个元素平均需要移动元素的个数是_。【答案】（n 1）/2【解析】删除第一个元素需要移动n i 次，以此类推，删除最后一个元素需要移动0次。平 均次数为10在图G 的邻接表表示中，每个顶点邻接表中所含的结点数，对于无向图来说等于该顶点的_; 对于有向图来说等于该顶点的_。【答案】度；出度二、判断题11如果完全二叉树从根结点开始按层次遍历的输序列为1，2，3，4，5，6，7，则该完全二叉树是二叉排序树。（ ）【答案】【解析】
5、不是，2，3作为1的左右孩子，由于左节点2比1大，所以不具有二叉排序树的性质。 12快速排序和归并排序在最坏情况下的比较次数都是【答案】【解析】快速排序最坏的情况下比较次数是 13KMP 算法的特点是在模式匹配时指示主串的指针不会变小。（ ）【答案】 函数，函【解析】KMP 算法是一种字符串匹配的算法，KMP 算法的关键是利用匹配失败后的信息，尽量减少模式串与主串的匹配次数以达到快速匹配的目的。具体实现就是实现一个数本身包含了模式串的局部匹配信息。 14若中序遍历平衡的二叉排序树，可得到排好序的关键码序列。（ ）【答案】【解析】二叉排序树对于每一个结点，它的左子树的所有结点的值都小于这个结点的值，而它的右子树的所有结点的值都大于这个结点的值。而采用中序遍历，遍历顺序为左根右，因此可以得到按增序排列的关键码序列。 15AOE 网一定是有向无环图。（ ）【答案】第 4 页，共 58 页（ ）一、填空题考研试题
