2018年北京林业大学信息学院839数据结构[专业硕士]考研仿真模拟五套题
● 摘要
一、填空题
1． 中缀式
运算结果为_____。 【答案】
【解析】中缀式相当于中序遍历，前缀式相当于前序遍历，后缀式相当于后序遍历。
2． 已知如下程序段:
语句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。
3． 已知一循环队列的存储空间为
则此循环队列判满的条件是_____ 【答案】
4． 实现字符串拷贝的函数strcpv 为:
(_____)
【答案】s++＝*t++或(*s++＝*t++)!＝'\0’
第 2 页，共 58 页 (c-d)对应的前缀式为_____，若a=l，b=2, c=3, d=4, 则后缀式的，其中n ＞m ，队头和队尾指针分别为front 和rear ，
5． 模式串
【答案】01122312 的next 函数值序列为_____。
6． 一个字符串中_____称为该串的子串。
【答案】任意个连续的字符组成的子序列
7． 假设一个15阶的上三角矩阵A 按行优先顺序压缩存储在一维数组B 中，则非零元素中的存储位置k ＝_____。(注:矩阵元素下标从1开始)
【答案】93
【解析】对于上三角矩阵，k ＝(i﹣l)(2n﹣i ＋2)/2＋(j﹣i) ＋l 。将i ＝j ＝9，n ＝15代入得93。
8． 若不考虑基数排序，则在排序过程中，主要进行的两种基本操作是关键字的 _____和记录的_____。
【答案】比较；移动
9． 假定有k 个关键字互为同义词，若用线性探测再哈希法把这k 个关键字存入哈希表中，至少要进行_____次探测。 【答案】
【解析】当该关键字发生冲突时，用线性探测不会遇到别的关键字冲突，这个时候需要探测的次数最小。总次数为。
10．在双向循环链表中，向P 所指的结点之后插入指针f 所指的结点，其操作是_____、_____、_____、_____。
【答案】f ﹣＞next ＝p ﹣＞next ；f ﹣＞prior ＝p ；p ﹣＞next ﹣＞prior ＝f ；p ﹣＞next ＝f ；
11．二叉树的前序序列和中序序列相同的条件是_____。
【答案】空树或任何结点至多只有右子树的二叉树
【解析】前序遍历的顺序为根左右，中序遍历的顺序为左根右，因此若中序遍历和前序遍历序列相同，则任何结点都没有左子树。
12．无用单元是指_____，例_____
【答案】用户不再使用而系统没有回收的结构和变量；
在B
二、单项选择题
13．已知有向图G=(V，E) , 其中
,
G 的拓扑序列是（ ）。
第 3 页，共 58 页
A.
B.
C.
D.
【答案】A
拓扑序列的条件:若
在顶
点 能被称为必须排【解析】设G=(V，E) 是一个具有n 个顶点的有向图，V 中顶点序列是图中的边(即从顶点。 到有一条路径) ，则在序列中顶点之前。根据上面拓扑序列的定义，就可以得出G 的拓扑序列
是
14．已知两个长度分别为m 和n 的升序链表, 若将它们合并为一个长度为m+n的降序链表, 则最坏情况下的时间复杂度是（ ） A. B. C. D.
【答案】D
m 和n 是两个升序链表长度分别为m 和n , 在合并过程中最坏的情况是两个链表中的【解析】
元素依次进行比较, 比较的次数是m 和n 中的最大值。
15．处理外部中断时, 应该由操作系统保存的是（ ）。
A. 程序计数器(PC)的内容
B. 通用寄存器的内容
C. 快表(TLB)的内容
D.Cache 中的内容
【答案】B
【解析】外部中断处理过程首先要保护现场, 使得中断处理完后能够恢复程序的状态继续执行。保护现场有两个含义:
①由中断隐指令保存程序的断点(程序计数器) ;
②由中断服务程序保存通用寄存器和状态寄存器的内容。中断服务程序是操作系统的一部分。
16．若数据元素序列11，12，13，7，8，9，23，4，5是采用下列排序方法之一得到的第二趟排序后的结果，则该排序算法只能是（ ）.
A.. 起泡排序
B. 插入排序
C. 选择排序
D. 二路归并排序
【答案】B
【解析】经过两趟排序后，A 项起泡排序的结果是两个最小或最大的元素放到了序列的最终
第 4 页，共 58 页