2018年哈尔滨工业大学生命科学与技术学院854计算机基础之数据结构考研仿真模拟五套题
● 摘要
一、填空题
1． 循环队列的引入，目的是为了克服_____。
【答案】假溢出时大量移动数据元素
【解析】用数组实现队列时，如果不移动，随着数据的不断读写，会出现假满队列的情况。即尾数组已满但头数组还是空的。循环队列也是一种数组，引入循环队列，有效克服假溢出大量移动数据元素的问题。
2． 设单链表的结点结构为(data，next) ，next 为指针域，已知指针px 指向单链表中data 为x 的结点，指针py 指向data 为y 的新结点，若将结点y 插入结点x 之后，则需要执行以下语句: _____；_____；
【答案】py ﹣＞next ＝px ﹣＞next ；px ﹣＞next ＝py
3． 对于一个具有n 个结点的二叉树，当它为一棵_____二叉树时具有最小高度, 当它为一棵_____时，具有最大高度。
【答案】完全；只有一个叶结点的二叉树
4． 阅读下列程序，指出其功能，并写出空格处应填上的语句。
【答案】
【解析】本题是在哈希表中插入值为item 的元素，如该元素已在哈希表中，报告出错。
5． 按LSD 进行关键字排序，除最次位关键字之外，对每个关键字进行排序时，只能用_____的排序方法。
【答案】稳定
6． 设有一个10阶对称矩阵A 采用压缩存储方式(以行为主序存储:a 11＝l) ， 则a 85的地址为_____。
【答案】33
【解析】设存储的元素的行标为i ，列标为j 。若i ＞＝j ，则
＝i(i﹣l)/2＋j 。若i ＜j 。则
的地址为l ＋2＋... ＋i ﹣l ＋j 的地址为j(j﹣l)/2＋i 。将i ＝8，j ＝5代入得33。
二、单项选择题
7． 下面关于串的叙述中，不正确的是（ ）。
A. 串是字符的有限序列
B. 空串是由空格构成的串
C. 模式匹配是串的一种重要运算
D. 串既可以采用顺序存储，也可以采用链式存储
【答案】B
【解析】空格构成的串称空格串。空串用表示。零个字符的串称为空串，空格也是一个字符，因此B 项不正确。
8． 假定下列指令已装入指令寄存器。则执行时不可能导致CPU 从用户态变为内核态(系统态) 的是（ ）。 A.
B. ; 产生软中断 C. ; 寄存器R0的内容取非 D.MOVRO , addr ; 把地址处的内存数据放入寄存器RO 中
【答案】C
【解析】A 项, 除法操作出现除数为零的情况时, 会产生内中断, CPU 切换为内核态进行中断处理; B 项, 直接产生中断, 会切换到内核态; D 项, addr 出现非法地址, 会出现中断, 进而切换到内核态。
9． 在用邻接表表示图时，拓扑排序算法时间复杂度为（ ）。
A.0(n)
B.0(n+e) C. D.
【答案】B
【解析】由于输出每个顶点的同时还要删除以它为起点的边，故拓扑排序的时间复杂度为0(n+e)
10．下列说法不正确的是（ ）。
A. 图的遍历是从给定的源点出发每个顶点仅被访问一次
B. 遍历的基本方法有两种:深度遍历和广度遍历
C. 图的深度遍历不适用于有向图
D. 图的深度遍历是一个递归过程
【答案】C
【解析】图的遍历是指从图中的某一个顶点出发，按照某种搜索算法沿着图中的边对图中的所有顶点访问一次且仅访问一次。图的深度遍历类似于树的先序遍历，不仅适合无向图，也适合于有向图。
11．某系统有n 台互斥使用的同类设备, 3个并发进程需要3, 4, 5台设备, 可确保系统不发生死锁的设备数n 最小为（ ）
A.9
B.10
C.11
D.12
【答案】B 【解析】
12．将一棵树t 转换为孩子兄弟链表表示的二叉树h ，则t 的后序遍历是h 的（ ）。
A. 前序遍历
B. 中序遍历
C. 后序遍历
【答案】B
【解析】树的后序遍历恰好对应于二叉树的中序遍历。
13．设置当前工作目录的主要目的是（ ）.
A. 节省外存空间
B. 节省内存空间
C. 加快文件的检索速度
D. 加快文件的读/写速度
【答案】C
【解析】工作目录只是指出了当前操作的默认目录，使得在每次访问的时候不需要由根目录一层一层地解析，在文件路径比较长时，可以节省许多解析的时间，从而加快了文件的检索速度.
14．若元素a , b , c , d , e , f 依次进栈, 允许进栈、退栈操作交替进行, 但不允许连续三次进行退栈操作, 则不可能得到的出栈序列是（ ）。
A.d , c , e , b , f , a
B.c , b , d , a , e , f
C.b , c , a , e , f , d
D.a , f , e , d , c , b