2018年哈尔滨工业大学威海校区854计算机基础(含数据结构、计算机组成原理)之数据结构考研仿真模拟五套题
● 摘要
一、填空题
1． 数据结构是研讨数据的_____和_____以及它们之间的相互关系，并对与这种结构定义相应的_____, 设计出相应的_____。
【答案】逻辑结构；物理结构；操作(运算) ；算法
2． 在拓扑分类中，拓扑序列的最后一个顶点必定是_____的顶点。
【答案】出度为0
【解析】如果最后一个顶点的出度不为0, 则必定还有顶点存在，与题目所说的最后一个顶点矛盾，所有最后一个顶点的出度必定为零。
3． 一棵有11个结点的满二叉树有_____个度为1的结点、有_____个分支(非终端) 结点和_____个叶子，该满二叉树的深度为_____。 【答案】或
【解析】满二叉树没有度为1的结点，度为0的结点等于度为2的结点个数+1。
4． 设为哈夫曼树的叶结点数目，则该哈夫曼树共有_____个结点。 【答案】
【解析】哈夫曼树只有度为0和2的节点。
5． 用循环链表表示的队列长度为n ，若只设头指针，则出队和入队的时间复杂度分别是_____和_____；若只设尾指针，则出队和入队的时间复杂度分别是_____和_____。
【答案】O(1)；O(n)；O(1)；O(1)
【解析】队列的出队操作即删除队头的元素，队列的入队操作即在队尾添加元素，循环链表只设头指针，出队时，只要把头结点的下一个结点删除就好了，入队时，要把新的结点插入队尾，必须把队列遍历，找到队尾指针，才能插入。循环队列只设尾指针，出队时只要把为指针的下一个结点或者下下个结点删除即可，入队时，只要在尾指针的后面插入新的结点，并更新尾结点即可。
6． 在进行入栈运算时应先判别栈是否_____:在进行出栈运算时应先判别栈是否_____:当栈中元素为n 个，进行入栈运算时发生上溢，则说明该栈的最大容量为_____。为了增加内存空间的利用率和减少溢出的可能性，由两个栈共享一片连续的空间时，应将两栈的_____分别设在内存空间的两端，这样只有当_____时才产生溢出。
【答案】满；空；n ；栈底；两栈顶指针相邻(即值之差的绝对值为1)
二、单项选择题
7． 在对n 个元素的序列进行排序时，堆排序所需要的附加存储空间是（ ）。 A.
B.O(1)
C.O(n) D.
【答案】B
【解析】堆排序需要一个空间用于交换，因此堆排序所需要的附加存储空间为O(1)。
8． 基于比较方法的n 个数据的内部排序。最坏情况下的时间复杂度能达到的最好下界是（
A. B.
C. O (n) D.
【答案】A
【解析】在内部排序中，最坏情况下的时间复杂度为。
9． 最大容量为n 的循环队列，队尾指针是rear ，队头:front ，则队空的条件是（ ）。
A.(rear+1)MODn＝front
B.rear ＝front
C.rear+1＝front
D.(rear-1)MODn＝front
【答案】B
【解析】循环队列队空的条件是:rear ＝front 。循环队列队满的条件，
通常采用(rear+1)%MAXQSIZE＝front 来判定队满，其中MAXQSIZE 表示队列的长度。
10．已知一算术表达式的中缀表达式为a ﹣(b＋c/d)*e，其后缀形式为（ ）。 A. B. C. D.
【答案】D
【解析】后缀表达式:在程序语言中，运算符位于两个操作数后面的表达式。
。 ）
11．某时刻进程的资源使用情况如下表所示
此时的安全序列是（ ）。
A.P1, P2, P3, P4
B.P1, P3, P2, P4
C.P1, P4, P3, P2
D. 不存在
【答案】D
【解析】典型的死锁避免算法, 银行家算法的应用。银行家算法是操作系统中的一个重点知识单元, 考生对此应该非常熟悉, 本题并无难点。分析一下下表, 可以看到, 经过P1, P4的运行以后, 可用资源是2, 2, 1, 而P2, P3所需资源分别是1, 3, 2和1, 3, 1。所以剩余资源已经不够P2或P3的
分配, 亦即找不到能够安全运行的序列, 因此此时是处于不安全状态, 所以不存在这样的安全序列。
12．下列选项中的英文缩写均为总线标准的是（ ）。
A.PCI 、CRT 、USB 、EISA
B.ISA 、CPI 、VESA 、EISA
C.ISA 、SCSI 、RAM 、MIPS
D.ISA 、EISA 、PCI 、PCI-Express
【答案】D
【解析】选项A 中的CRT 和USB 、选项B 中的CPI 、选项C 中的RAM 和MIPS 均不是总线标准的英文缩写, 只有选项D 中的英文缩写均为总线标准。
13．有n(n＞0) 个分支结点的满二叉树的深度是（ ）。
A.n 2﹣l
B.log 2(n＋1) ＋1
C.log 2(n＋1)