《2017年北京市培养单位电子电气与通信工程学院863计算机学科综合(专业)之数据结构考研题库.doc》由会员分享，可在线阅读，更多相关《2017年北京市培养单位电子电气与通信工程学院863计算机学科综合(专业)之数据结构考研题库.doc（4页珍藏版）》请在金锄头文库上搜索。
1、2017年北京市培养单位电子电气与通信工程学院863计算机学科综合(专业)之数据结构考研题库一、填空题1 在二叉树中，指针p 所指结点为叶结点的条件是_。【答案】 【解析】叶子节点的左右孩子都不存在。2 文件由_组成；记录由_组成。【答案】记录；数据项 3 完善算法：求KMP 算法.next 数组。 END ； 【答案】 4 在一个无向图的的邻接表中，若表结点的个数是m , 则图中边的条数是_条。【答案】m/2【解析】对于无向图，在邻接表中，如果存在n 条边，则会有2n 个表结点。5 文件可按其记录的类型不同而分成两类，即_和_文件。【答案】操作系统文件；数据库6 设数组储，则元素为_。【答案
2、】9174；8788【解析】设一个元素的行标为i ，列标为j 。若以行序为主存储顺序，则它的存储地址为若以列序为主存储顺序，则它的存储地址为 7 对于一个具有n 个结点的二叉树，当它为一棵_二叉树时具有最小高度，当它为一棵_ 时. 具有最大高度【答案】完全；只有一个叶结点的二叉树第 2 页，共 55 页的基地址为2000，每个元素占2个存储单元，若以行序为主序顺序存的存储地址为_；若以列序为主序顺序存储，则元素的存储地址 8 二进制地址为011011110000，大小为【答案】011011110100；011011100000和块的伙伴地址分别为：_ 和其伙伴块的起始地址计算公01101111
3、0000是块的起始地址，【解析】大小分别为式如下： 当大小为4时，起始地址为当大小为16时，起始地址为： 9 棵深度为k 的平衡二叉树， 其每个非终端结点的平衡因子均为0，则该树共有_个结点。【答案】 【解析】每个非终端结点都是0表示该平衡二叉树没有高度落差。也就是说它是一棵满二叉 树。故结点个数为10A 是一个任意给定的整数。free_tree设T 是一棵结点值为整数的二叉排序树，在下面的算法中，（T ）在对二叉排序树丁进行后序遍历时释放二又排序树T 的所有结点；首先在二叉排序树T 中查找值为A 的结点，根据查找情况分别进行如下处理：（1）若找不到值为A 的结点，则返回根结点的地址（2）若找
4、到值为A 的结点，则删除以此结点为根的子树，并释放此子树中的所有结点，若值为A 的结点是查找树的根结点，删除后变成空的二叉树，则返否则返回根结点的地址。 【答案】 二、判断题11对磁带机而言，ISAM 是一种方便的文件组织方法。（ ）【答案】【解析】ISAM 是一种专为磁盘存取设计的文件组织方式。 第 3 页，共 55 页12若一个有向图的邻接矩阵对角线以下元素均为零，则该图的拓扑有序序列必定存在。 （ ）【答案】【解析】因为一个有向图的邻接矩阵对角线以下元素均为零，则该图是一个有向无环图，所以该图的拓扑有序序列必定存在。 13负载因子（装填因子）是哈希表的一个重要参数，它反映哈希表的装满程度
5、。（ ）【答案】【解析】查找过程中需和给定值进行比较的关键字的个数取决于三个因素：哈希函数，处理冲突的方法和哈希表的装填因子。其中装填因子标志哈希表的装满程度。 14文件系统采用索引结构是为了节省存储空间。（ ）【答案】【解析】是为了缩短查找的时间，牺牲了一部分存储空间。 15堆肯定是一棵平衡二叉树。（ ）【答案】【解析】堆是n 个元素的序列，可以看成是完全二叉树，但相对于根并无左小右大的要求，故其既不是二叉排序树，更不会是平衡二叉树。 16当改变网上某一关键路径上任一关键活动后，必将产生不同的关键路径。（ ）【答案】【解析】当改变任意关键路径上的关键活动之后，这个活动可能还是关键活动，因此不
6、会产生不同的关键路径。 17排序的稳定性是指排序算法中的比较次数保持不变，且算法能够终止。（ ）【答案】【解析】排序的稳定性指：假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，且ri 在rj 之前，而在排序后的序列中，ri 仍在rj 之前，则称这种排序算法是稳定的；否则称为不稳定的。 18两分法插入排序所需比较次数与待排序记录的初始排列状态相关。（ ）【答案】【解析】折半插入排序所需的附加存储空间和直接插入排序相同，从时间上比较，折半插入排序仅减少了关键字间的比较次数，而记录的移动次数不变。因此，折半插入排序的时间复杂度仍为 19倒排文件的目的是为了多关键字查找。（ ）【答案】第 4 页，共 55 页与待排序记录的初始排列状态无关。一、填空题考研试题
