《2017年北京市培养单位国家空间科学中心863计算机学科综合(专业)之数据结构考研强化模拟题.doc》由会员分享，可在线阅读，更多相关《2017年北京市培养单位国家空间科学中心863计算机学科综合(专业)之数据结构考研强化模拟题.doc（5页珍藏版）》请在金锄头文库上搜索。
1、2017年北京市培养单位国家空间科学中心863计算机学科综合(专业)之数据结构考研强化模拟题一、填空题1 一个有2001个结点的完全二叉树的高度是_。【答案】11【解析】完全二叉树的高度 2 如果按关键码值递増的顺序依次将关键码值插入到二叉排序树中，则对这样的二叉排序树检索时，平均比较次数为_。【答案】 【解析】如果关键码是排好序的，构建二叉排序树就会形成一个单支树，它的查找效率和顺 序查找效率一样为 3 当广义表中的每个元素都是原子时，广义表便成了_。【答案】线性表【解析】如果每个元素都是原子，则元素不可分。此时的元素是只有一对一的关系，所以广义表变成了线性表。4 中缀式运算结果为_。【答案
2、】 【解析】中缀式相当于中序遍历，前缀式相当于前序遍历，后缀式相当于后序遍历。 5 n 个顶点的有向图用邻接矩阵array 表示，下面是其拓扑排序算法，试补充完整。注：（1）图的顶点号从0开始计；（2）indegree 是有n 个分量的一维数组，放顶点的入度， （3）函数crein 用于记算顶点入度；（4）有三个函数push （data ）, pop（ ）, check（ ）其含义为数据data 入浅，出栈和测试栈是否空（不空返回1, 否则0）。 ） 第 2 页，共 56 页对应的前缀式为_，若则后缀式的 . 【答案】0; j; i; 0; indegreei=0; vexi; k=l; in
3、degreei=0【解析】有向图用邻接矩阵表示时，顶点i 的入度等于第i 列的所有元素之和。拓扑排序过程：首先将入度 为0的顶点全部进栈。然后弹出栈顶结点，并将与弹出的顶点相连的其它顶点的入度 减一，然后判断这些顶点的 入度是否为零，如果为零，继续进栈，重复这些操作，完成拓扑排序。 6 有向图G=（V ，E ）, 其中V （G ）=0, 1，2，3，4, 5, 用三元组表示弧及弧上的权d 。 E （G ）为 E （G= , , ， ，则从源点0到顶点3的最短路径长度是_，经过的中间顶点是_。【答案】50; 4 7 在顺序存储的二叉树中，编号为i 和j 的两个结点处在同一层的条件是_。【答案】要
4、加“虚结点”。设编号为和的结点在顺序存储中的下标为和。 8 个字符串中_称为该串的子串。【答案】任意个连续的字符组成的子序列 9 已知二叉排序树的左右子树均不为空，则_上所有结点的值均小于它的根结点值，_上所有结点的值均大于它的根结点的值。【答案】左子树；右子树 【解析】二叉排序树或者是一棵空树，或者是具有下列性质的二叉树：若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；它的左、右子树也分别为二叉排序树。 ，则结点和在同一层上的条件是 【解析】用顺序存储结构存储二叉树时，要按完全二叉树的形式存储，非完全二叉树存储时，；
5、（“图有回路”） 第 3 页，共 56 页 10若不考虑基数排序，则在排序过程中，主要进行的两种基本操作是关键字的_和记录的_，【答案】比较；移动二、判断题11采用线性探测法处理散列时的冲突，当从哈希表删除一个记录时，不应将这个记录的所在位置置空，因为这会影响以后的查找。（ ）【答案】【解析】从哈希表删除一个记录，不是将这个记录的位置置空，而是设置一个标记，标记这个元素是无效的了。 12强连通分量是无向图的极大强连通子图。（ ）【答案】【解析】强连通分量是对有向图而言的，一般在无向图中讨论连通性。 13为了很方便的插入和删除数据，可以使用双向链表存放数据。（ ）【答案】【解析】链式存储结构便于
6、数据的插入和删除，但只能顺序访问表中的元素。14个稀疏矩阵采用三元组形式表示，若把三元组中有关行下标与列下标的值互换，并把m 和n 的值互换，则就完成了【答案】【解析】稀疏矩阵转置后，除行列下标及行列数互换外，还必须确定该元素转置后在新三元组中的位置。 15广义表【答案】【解析】长度为1。因为只含一个元素即子表 16在平衡二又树中，向某个平衡因子不为零的结点的树中插入一新结点，必引起平衡旋转。（ ）【答案】【解析】不一定，比如一个平衡因子为1的结点，这时往它的右部插入一个新结点，就不会引起平衡旋转 17内排序要求数据一定要以顺序方式存储。（ ）【答案】【解析】由于待排序的记录数量不同，使得排序过程中涉及的存储器不同，可将排序方法分第 4 页，共 56 页的转置运算。（ ）的长度是4。（ ）一、填空题考研试题
