《2017年上海海事大学文理学院828数据结构及程序设计之数据结构考研强化模拟题.doc》由会员分享，可在线阅读，更多相关《2017年上海海事大学文理学院828数据结构及程序设计之数据结构考研强化模拟题.doc（4页珍藏版）》请在金锄头文库上搜索。
1、2017年上海海事大学文理学院828数据结构及程序设计之数据结构考研强化模拟题目录 2017年上海海事大学文理学院828数据结构及程序设计之数据结构考研强化模拟题（一） . 2 2017年上海海事大学文理学院828数据结构及程序设计之数据结构考研强化模拟题（二） . 14 2017年上海海事大学文理学院828数据结构及程序设计之数据结构考研强化模拟题（三） . 27 2017年上海海事大学文理学院828数据结构及程序设计之数据结构考研强化模拟题（四） . 39 2017年上海海事大学文理学院828数据结构及程序设计之数据结构考研强化模拟题（五） . 50一、填空题1 遍历图的过程实质上是_，广
2、度优先遍历图的时间复杂度_; 深度优先遍历图的时间复杂度_, 两者不同之处在于_, 反映在数据结构上的差别是_。【答案】查找顶点的邻接点的过程；0（n+e）; 0（n+e）; 访问顶点的顺序不同；队列和栈 【解析】广度优先遍历图使用队列这种数据结构，深度优先遍历图使用栈这种数据结构。2 根据线性表的链式存储结构中每一个结点包含的指针个数，将线性链表分成_和_; 而又根据指针的连接方式，链表又可分成_和_。【答案】单链表；双链表；（动态）链表；静态链表【解析】线性表的链式存储结构根据每个结点包含的指针个数分为单链表和双链表，单链表只包含一个指针，指向后续元素，双链表包括两个指针，指向前一个元素和
3、后续元素。根据指针的连接方式，链表可分为动态链表和静态链表。静态链表的指针指向下一个元素的编号，动态链表的指针指向下一个元素的物理位置。3 在二叉树中，指针p 所指结点为叶结点的条件是_。【答案】 【解析】叶子节点的左右孩子都不存在。4 在n 个顶点的非空无向图中，最多有_个连通分量。【答案】n【解析】当n 个顶点之间没有边，都是孤立的顶点时，有n 个连通分量。5 索引顺序文件既可以顺序存取，也可以_存取。【答案】随机 6 无用单元是指_，例_【答案】用户不再使用而系统没有回收的结构和变量； 7 对于一个具有n 个结点的二叉树，当它为一棵_二叉树时具有最小高度，当它为一棵_ 时. 具有最大高度
4、【答案】完全；只有一个叶结点的二叉树8 设有两个算法在同一机器上运行，其执行时闻分别为_。【答案】15要使前者快于后者，n 至少为【解析】当时，而，时， 9 设T 和P 是两个给定的串，在T 中寻找等于P 的子串的过程称为_，又称P 为_。【答案】模式匹配；模式串 10在单链表中设置头结点的作用是_。【答案】方便运算 11VSAM 系统是由_、_、_构成的。【答案】索引集；顺序集；数据集 12对于给定的元素，可以构造出的逻辑结构有_，_，_，_四种。【答案】集合；线性结构；树形结构；图状结构（网状结构）13下列程序是快速排序的非递归算法，请填写适当的语句，完成该功能。 【答案】 【解析】快速排
5、序（quicksort ）的基本思想是，通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。 14给定一组数据的值为_。 【答案】5；96【解析】每次找两个最小的权值构建哈夫曼树： 以它构造一棵哈夫曼树，则树高为_，带权路径长度 15阅读下列程序说明和裎序，填充程序中的_。【程序说明】本程序完成将二叉树中左、右孩子交换的操作。交换的结果如下所示（编科略）本程序采用非递归的方法，设立一个堆栈交换左、右子树的算法为：（1）把根结点放入堆栈。（2）当堆栈不空时，取出栈顶元素，交换它的左、右子树，并把它的左、右子树分别入栈。（3）重复（2）直到堆栈为空时为止。 存放还没有转换过的结点，它的栈顶指针为。 （1） （2）If （ （3） ） 【答案】 【解析】本题主要使用堆栈完成了二叉树左右子树交换的操作。首先根结点进栈，然后判断栈足否为空，如果不为空，则取栈顶元素，交换取出节点的左右指针。并将左右指针分别进桟，重复这一操作。完成二叉树左右孩子的交换。 二、选择题考研试题
