《2017年军事医学科学院总后勤部卫生部药品仪器检验所836计算机应用之数据结构考研冲刺密押题.doc》由会员分享，可在线阅读，更多相关《2017年军事医学科学院总后勤部卫生部药品仪器检验所836计算机应用之数据结构考研冲刺密押题.doc（4页珍藏版）》请在金锄头文库上搜索。
1、2017年军事医学科学院总后勤部卫生部药品仪器检验所836计算机应用之数据结构考研冲刺密押题一、填空题1每一棵树都能唯一地转换为它所对应的二叉树。若已知一棵二叉树的前序序列是中序序列是前庁序列是_。【答案】 【解析】树的抑序序列对应二叉树的前序序列. 该二叉树转换成森林吋含三棵树. 其第一棵树的前序是。2 对于给定的元素，可以构造出的逻辑结构有_，_，_，_四种。【答案】集合；线性结构；树形结构；图状结构（网状结构） 3 N 个顶点的连通图用邻接矩阵表示时，该矩阵至少有_个非零元素。【答案】2（N-1）【解析】所谓连通图一定指的是无向图，有向图会称作强连通图。连接N 个顶点，至少需要N-1条边
2、就可 以了。由于无向图的每一条边同时关联了两个顶点。因此用邻接矩阵表示时，该矩阵至少有2（N-1）个非零元素。 4 数据结构中评价算法的两个重要指标是_。【答案】算法的时间复杂度和空间复杂度 5 设T 和P 是两个给定的串，在T 中寻找等于P 的子串的过程称为_，又称P 为_。【答案】模式匹配；模式串 6 己知有序表为（12，18，24，35，47，50，62，83，90，115，134）当用二分法查找90时，需_次查找成功，查找47时_成功，查找100时，需_次才能确定不成功。【答案】2；4；3【解析】二分法查找元素次数列表.，则它的后庁序列是_。设上述二叉树是由某棵树转换而成，则该树的查找
3、100是找到115就停止了。7 【答案】5 8 串是一种特殊的线性表，其特殊性表现在_; 串的两种最基本的存储方式是_、_; 两个串相等的充分必要条件是_。【答案】其数据元素都是字符；顺序存储；链式存储；串的长度相等且两串中对应位置的字符也相等9 遍历图的过程实质上是_，广度优先遍历图的时间复杂度_; 深度优先遍历图的时间复杂度_, 两者不同之处在于_, 反映在数据结构上的差别是_。【答案】查找顶点的邻接点的过程；0（n+e）; 0（n+e）; 访问顶点的顺序不同；队列和栈 【解析】广度优先遍历图使用队列这种数据结构，深度优先遍历图使用栈这种数据结构。10阅读下列程序，指出其功能，并写出空格处
4、应填上的语句。 【答案】【解析】本题是在哈希表ht中插入值为 11无用单元是指_，例_的元素，如该元素已在哈希表中，报告出错。=_【答案】用户不再使用而系统没有回收的结构和变量；12在拓扑分类中，拓扑序列的最后一个顶点必定是_的顶点。【答案】出度为0 【解析】如果最后一个顶点的出度不为0, 则必定还有顶点存在，与题目所说的最后一个顶点矛盾，所有最 后一个顶点的出度必定为零。 13当线性表的元素总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素时，应采用_存储结构。【答案】顺序【解析】顺序存储结构的存取操作比较方便，但插入和删除操作不如链式存储结构方便，而且需要连续的存
5、储空间，由于该线性表的元素总数基本稳定，而且很少进行插入删除操作，为了更快的存取元素，顺序表更合适。 14已知链队列的头尾指针分别是f 和r , 则将值x 入队的操作序列是_。【答案】【解析】队列采用链式存储结构，先分配一个节点的内存，然后在队尾添加该节点。15索引顺序文件既可以顺序存取，也可以_存取。【答案】随机 二、选择题16现在有一颗无重复关键字的平衡二叉树（A VL 树），对其进行中序遍历可得到一个降序序列。下列关于该平衡二叉树的叙述中，正确的是（ ）。A. 根节点的度一定为2 B. 树中最小元素一定是叶节点 C. 最后插入的元素一定是叶节点 D. 树中最大元素一定是无左子树 【答案】
6、D【解析】二叉树的中序遍历定义是“若二叉树为空，则空操作；否则：中序遍历左子树；访问根节点；中序遍历右子树”。A 项错误，当树中仅有一个或者两个结点时，根节点的度就可能不为2；B 项错误，树中最小元素是中序遍历时最后访问的节点，当没有右子树时，最后访问的节点是根节点；C 项错误，当最后插入的元素破坏树的平衡后，树会进行调整，使其成为中间节点；D 项正确，由中序遍历的特点可知，左子树的值大于根节点，所以最大元素一定没有左子树。 17操作系统的A. 用户级B. 用户级C. 用户级D. 用户级【答案】A 。子系统通常由四个层次组成，每一层明确定义了与邻近层次的接口。其合理软件、设备无关软件、设备驱动程序、中断处理程序 软件、设备无关软件、中断处理程序、设备驱动程序 软件、设备驱动程序、设备无关软件、中断处理程序 软件、中断处理程序、设备无关软件、设备驱动程序的层次组织排列顺序是（ ）。一、填空题考研试题
