《2017年军事医学科学院总后勤部卫生部药品仪器检验所836计算机应用之数据结构考研仿真模拟题.doc》由会员分享，可在线阅读，更多相关《2017年军事医学科学院总后勤部卫生部药品仪器检验所836计算机应用之数据结构考研仿真模拟题.doc（4页珍藏版）》请在金锄头文库上搜索。
1、2017年军事医学科学院总后勤部卫生部药品仪器检验所836计算机应用之数据结构考研仿真模拟题一、填空题1 【答案】5 2 抽象数据类型的定义仅取决于它的一组_，而与_无关, 即不论其内部结构如何变化，只要它的_不变，都不影响其外部使用。【答案】逻辑特性；在计算机内部如何表示和实现；数学特性3 设广义表则是_tail（L ）是_；L 的长度是_；深度是_。=_；2；2 【答案】（ ）（ ）【解析】广义表的表头是表的第一个元素，表尾是除了第一个元素外其余的所有的元素构成的表；表的长度指表中元素的个数；表的深度指展开后括号的层数。 4 在基于关键字比较且时间为O （nl g2n ）的排序中，若要求排
2、序是稳定的，则可选用_，则可选用_排序。 排序；若要求就地排序（及辅助空间为0（1）【答案】归并；堆 5 在二叉树中，指针p 所指结点为叶结点的条件是_。【答案】 【解析】叶子节点的左右孩子都不存在。6 棵有个结点的满二叉树有_个度为1的结点、有_个分支（非终端）结点和_个叶子，该满二叉树的深度为_。【答案】或 【解析】满二叉树没有度为1的结点，度为0的结点等于度为2的结点个数+1。7 阅读下列程序说明和裎序，填充程序中的_。【程序说明】本程序完成将二叉树中左、右孩子交换的操作。交换的结果如下所示（编科略）本程序采用非递归的方法，设立一个堆栈交换左、右子树的算法为：（1）把根结点放入堆栈。（2
3、）当堆栈不空时，取出栈顶元素，交换它的左、右子树，并把它的左、右子树分别入栈。（3）重复（2）直到堆栈为空时为止。第 2 页，共 33 页存放还没有转换过的结点，它的栈顶指针为。 （1） （2）If （ （3） ） 【答案】 【解析】本题主要使用堆栈完成了二叉树左右子树交换的操作。首先根结点进栈，然后判断栈足否为空，如果不为空，则取栈顶元素，交换取出节点的左右指针。并将左右指针分别进桟，重复这一操作。完成二叉树左右孩子的交换。 8 设m 、n 均为自然数，m 可表示为一些不超过n 的自然数之和，f （m , n ）为这种表示方式的 数目。例f （5, 3）=5，有5种表示方式：32, 311，
4、221，2111, 11111。以下是该函数的程序段，请将未完成的部分填入，使之完整。 执行程序，f （6，4）=_。 【答案】1; 1; f （m ，n 1）; n 9 9 文件可按其记录的类型不同而分成两类，即_和_文件。【答案】操作系统文件；数据库 10一个有2001个结点的完全二叉树的高度是_。【答案】11【解析】完全二叉树的高度 第 3 页，共 33 页 11检索是为了在文件中寻找满足一定条件的记录而设置的操作。检索可以按_检索。也可以按_检索；按_检索又可以有_检索和_检索。【答案】关键字；记录号；记录号；顺序；直接12在一棵m 阶的个数是_。【答案】 【解析】m 阶树除根结点和叶
5、子结点外，结点中关键字个数最多是最少 13用循环链表表示的队列长度为n ，若只设头指针，则出队和入队的时间复杂度分别是_和_；若只设尾指针，则出队和入队的时间复杂度分别是_和_。【答案】 【解析】队列的出队操作即删除队头的元素，队列的入队操作即在队尾添加元素，循环链表只设头指针，出队时，只要把头结点的下一个结点删除就好了，入队时，要把新的结点插入队尾，必须把队列遍历，找到队尾指针，才能插入。循环队列只设尾指针，出队时只要把为指针的下一个结点或者下下个结点删除即可，入队时，只要在尾指针的后面插入新的结点，并更新尾结点即可。 14下列程序是快速排序的非递归算法，请填写适当的语句，完成该功能。 第 4 页，共 33 页树中，若在某结点中插入一个新关键字而引起该结点分裂，则此结点中原有的关键字的个数是_；若在某结点中删除一个关键字而导致结点合并，则该结点中原有的关键字一、填空题考研试题
