2017年河北工业大学计算机科学与软件学院802数据结构考研强化模拟题
● 摘要
一、填空题
1． 设正文串长度为n ，模式串长度为m ，则串匹配的KMP 算法的时间复杂度为_____。
【答案】
2． 设T 是一棵结点值为整数的二叉排序树，A 是一个任意给定的整数。free_tree在下面的算法中，（T ）在对二叉排序树丁进行后序遍历时释放二又排序树T 的所有结点；
首
先在二叉排序树T 中查找值为A 的结点，根据查找情况分别进行如下处理：（1）若找不到值为A 的结点，则返回根结点的地址（2）若找到值为A 的结点，则删除以此结点为根的子树，并释放此子树中的所有结点，若值为A 的结点是查找树的根结点，删除后变成空的二叉树，则返否则返回根结点的地址。
【答案】
3． 设用希尔排序对数组{98，36，-9，0，47，23，1，8，10，7}进行排序，给出的步长（也称 增量序列）依次是4，2，1则排序需_____趟，写出第一趟结束后，数组中数据的排列次序_____。
【答案】3; （10，7，-9，0，47，23，1，8，98，36）
4． 已知如下程序段：
语句1执行的时间复杂度为_____；语句2执行的时间复杂度为_____；语句3执行的时间复杂度为_____；语句4执行的时间复杂度为_____。
【答案】（1）n ＋1 （2）n
（3）n （n ＋3）/2 （4）n （n ＋l ）/2
【解析】语s 句1执行到不符合条件情况下，执行了n ＋1次。当语句1不符合条件了是不会执行语句2的，所以语句2被执行了n 次。语句3每次都要执行到不符合条件，故为2＋3＋4...... ＋（n ＋l ）加起来就是n （n ＋3）/2。语句3不符合条件了是不会执行语句4的。所以语句4被执行了1＋2＋3...... ＋n 即n （n ＋l ）/2。
5． 组成串的数据元素只能是_____。
【答案】字符
6． 完善算法：求KMP 算法.next 数组。
END ； 【答案】
7． 遍历图的过程实质上是_____，广度优先遍历图的时间复杂度_____; 深度优先遍历图的时间复杂度_____, 两者不同之处在于_____, 反映在数据结构上的差别是_____。
【答案】查找顶点的邻接点的过程；0（n+e）; 0（n+e）; 访问顶点的顺序不同；队列和栈 【解析】广度优先遍历图使用队列这种数据结构，深度优先遍历图使用栈这种数据结构。
8． VSAM （虚拟存储存取方法）文件的优点是：动态地_____，不需要文件进行_____，并能较快地_____进行查找。
【答案】分配和释放存储空间；重组；对插入的记录
9． 数组的存储结构采用_____存储方式。
【答案】顺序存储结构
【解析】数组本身的存储结构是线性的，也就是说它是连续存储的。
10．建立索引文件的目的是_____。
【答案】提高查找速度
11．数据结构是研讨数据的_____和_____以及它们之间的相互关系，并对与这种结构定义相应的_____，设计出相应的_____。
；算法 【答案】逻辑结构；物理结构；操作（运算）
12．在图G 的邻接表表示中，每个顶点邻接表中所含的结点数，对于无向图来说等于该顶点的_____; 对于有向图来说等于该顶点的_____。
【答案】度；出度
二、选择题
13．下列有关
B.
接口的叙述中错误的是：（ ）
端口
端口
指令，
A. 状态端口和控制端口可以合用同一寄存器
接口中CPU 可访问寄存器，称为C. 采用独立编址方式时，【答案】D
【解析】采用统一编码方式，存储器和
端口共用统一的地址空间，不需要专用的
任何对存储器数据进行操作的指令都可用于端口的数据操作。所以D 错误
14．计算机开后，操作系统最终被加载到（ ）
A.BIOS B.ROM C.EPROM D.RAM 【答案】D
【解析】系统开机后, 操作系统的程序会被自动加载到内存中的系统区，这段区城是RAM ，故答案选D 。
15．在OSI 参考模型中，直接为会话层提供服务的是（ ）
A. 应用层 B. 表示层 C. 传输层 D. 网络层 【答案】C
【解析】OSI 参考模型中，下层直接为上层提供服务，而会话层的下层为传输层。
16．一棵非空的二叉树的前序序列和后序序列正好相反，则该二叉树一定满足（ ）。
A. 其中任意一个结点均无左孩子 B. 其中任意一个结点均无右孩子
端口地址和主存地址可能相同
D. 采用统一编址方式时，CPU 不能用访存指令访问
相关内容
相关标签