2017年华中科技大学软件学院887数据结构与算法分析考研强化模拟题一、填空题1 假设一个15阶的上三角矩阵A 按行优先顺序压缩存储在一维数组B 中，则非零元素中的存储位置k=_。（注：矩阵元素下标从1开始）【答案】93【解析】对于上三角矩阵，将代入得93。 2 已知二叉排序树的左右子树均不为空，则_上所有结点的值均小于它的根结点值，_上所有结点的值均大于它的根结点的值。【答案】左子树；右子树 【解析】二叉排序树或者是一棵空树，或者是具有下列性质的二叉树：若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；它的左、右子树也分别为二叉排序树。 3 试利用下列栈和串的基本操作完成下述填空题。initstack （S ） 置S 为空找； push （S , X ） 元素X 入找； pop （S ） 出栈操作； gettop （S ） 返回栈顶元素； sempty （S ） 判找空函数； 置串 判串 返回联接empty （st ） 判串空函数 若给定的表达式的前缀式pre 正确，本过程求得和它相应的表达式exp 并返回true , 否则exp 为空串，并返回false 。已知原表达式中不包含括弧，opset 为运算符的集合。） 第 2 页，共 37 页在B为空串；是否相等的函数； 之后的串；length （st ） 返回串st 的长度； sub （S , i , 1） 返回S 中第i 个字符； 注意：毎个空格只填一个语句。 【答案】（1）（2）（3）（4）（5）（6）（7）exp （8）（9）exp （10）（11）（12） 4取栈顶操作符 操作符取出后，出栈将pre 的最后一个字符（操作数）加入到中缀式exp 的最后 求REPLACE （S ，V , m ）=_。【答案】 5 循环队列的引入，目的是为了克服_。【答案】假溢出时大量移动数据元素【解析】用数组实现队列时，如果不移动，随着数据的不断读写，会出现假满队列的情况。即尾数组已满但头数组还是空的。循环队列也是一种数组，引入循环队列，有效克服假溢出大量移动数据元素的问题。 6 VSAM 系统是由_、_、_构成的。【答案】索引集；顺序集；数据集第 3 页，共 37 页 栈S 初始化为空栈 串exp 初始化为空串 判取出字符是否是操作符如ch 是运算符，则入操作符栈s 判栈8是否为空若读出ch 是操作数且栈为空，则按出错处理若ch 是操作数且栈非空，则形成部分中缀表达式已 知7 从平均时间性能而言，_排序最佳。【答案】快速【解析】快速算法的平均时间复杂度为nlogn 。8 在基于关键字比较且时间为O （nl g2n ）的排序中，若要求排序是稳定的，则可选用_，则可选用_排序。 排序；若要求就地排序（及辅助空间为0（1）【答案】归并；堆 9 在一个无向图的的邻接表中，若表结点的个数是m , 则图中边的条数是_条。【答案】m/2【解析】对于无向图，在邻接表中，如果存在n 条边，则会有2n 个表结点。10起始地址为480，大小为8的块，其伙伴块的起始地址是_；若块大小为32，则其伙伴块的起始地址为_。【答案】 【解析】起始地址为P ，大小为的内存块，其伙伴块的起始地址计算公式如下： 根据上述公式起始地址就为488。11遍历图的过程实质上是_，广度优先遍历图的时间复杂度_; 深度优先遍历图的时间复杂度_, 两者不同之处在于_, 反映在数据结构上的差别是_。【答案】查找顶点的邻接点的过程；0（n+e）; 0（n+e）; 访问顶点的顺序不同；队列和栈 【解析】广度优先遍历图使用队列这种数据结构，深度优先遍历图使用栈这种数据结构。12数据结构是研讨数据的_和_以及它们之间的相互关系，并对与这种结构定义相应的_，设计出相应的_。；算法 【答案】逻辑结构；物理结构；操作（运算）13一个有2001个结点的完全二叉树的高度是_。【答案】11【解析】完全二叉树的高度 第 4 页，共 37 页一、填空题考研试题