2018年天津大学国际工程师学院901数据结构与程序设计[专业硕士]之数据结构考研强化五套模拟题
● 摘要
一、填空题
1． —个有2001个结点的完全二叉树的高度是_____。
【答案】11
【解析】完全二叉树的高度
2． N 个顶点的连通图用邻接矩阵表示时，该矩阵至少有_____个非零元素。 【答案】
【解析】所谓连通图一定指的是无向图，有向图会称作强连通图。连接N 个顶点，至少需要N －1条边就可以了。由于无向图的每一条边同时关联了两个顶点。因此用邻接矩阵表示时，该矩阵至少有2(N－1) 个非零元素。
3． 执行顺序查找时，存储方式可以是_____，折半查找时，要求线性表_____，分块查找时要求线性表_____，而哈希表的查找，要求线性表的存储方式是_____。
【答案】顺序存储或链式存储；顺序存储且有序；块内顺序存储，块间有序；散列存储
4． 已知二叉排序树的左右子树均不为空，则_____上所有结点的值均小于它的根结点值，_____上所有结点的值均大于它的根结点的值。
【答案】左子树；右子树
【解析】二叉排序树(binary sort tree)或者是一棵空树，或者是具有下列性质的二叉树:①若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；②若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；③它的左、右子树也分别为二叉排序树。
5． 在双向循环链表中，向P 所指的结点之后插入指针f 所指的结点，其操作是_____、_____、_____、_____。
【答案】f ﹣＞next ＝p ﹣＞next ；f ﹣＞prior ＝p ；p ﹣＞next ﹣＞prior ＝f ；p ﹣＞next ＝f ；
6． 设单链表的结点结构为(data，next) ，next 为指针域，已知指针px 指向单链表中data 为x 的结点，指针py 指向data 为y 的新结点，若将结点y 插入结点x 之后，则需要执行以下语句: _____；_____；
【答案】py ﹣＞next ＝px ﹣＞next ；px ﹣＞next ＝py
7． 设广义表L ＝(（ ），（ ）) ，则head(L)是_____tail(L)是_____L的长度是_____；深度是_____。
【答案】（ ）；(（ ）) ；2；2
【解析】广义表的表头是表的第一个元素，表尾是除了第一个元素外其余的所有的元素构成的表；表的长度指表中元素的个数；表的深度指展开后括号的层数。
8． 一个算法具有5个特性: _____、_____、_____、有零个或多个输入、有一个或多个输出。
【答案】有穷性；确定性；可行性
9． 深度为H 的完全二叉树至少有_____个结点:至多有_____个结点; H 和结点总数N 之间的关系是_____。 【答案】
10．无用单元是指_____，例_____
【答案】用户不再使用而系统没有回收的结构和变量；
11．以下程序的功能是实现带附加头结点的单链表数据结点逆序连接，请填空完善之。
h 为附加头结点指针
(_____)
_____；
【答案】(1)p!＝NULL //链表未到尾就一直进行
(2)q //将当前结点作为头结点后的第一元素结点插入
12．设T 和P 是两个给定的串，在T 中寻找等于P 的子串的过程称为_____，又称P 为_____。
【答案】模式匹配；模式串
13．属于不稳定排序的有_____。
【答案】希尔排序、简单选择排序、快速排序、堆排序等
14．求最短路径的Dijkstra 算法的时间复杂度为_____。 【答案】
15．顺序栈用 存储数据，栈顶指针是top ，则值为x 的元素入栈的操作是_____。
【答案】if(top!＝n)data[++top]＝x ；
【解析】先判断栈是否满，如果不满，元素入栈。否则返回溢出信息。
二、单项选择题
16．下列选项中, 对正确接收到的数据帧进行确认的MAC 协议是（ ）。
A.CSMA
B.CDMA C. D.
【答案】D
【解析】可采用排除法。CDMA 是码分多址复用, 是物理层的内容; CSMA/CD即带冲突检测的载波监听多路访问, 接收方并不需要确认; CSMA/CD是CSMA 的加强版, 故CSMA 也无确定; CSMA/CD是中的协议, 其利用ACK 信号来避免冲突的发生, 也就是说, 只有当客户端收到网络上返回的ACK 信号后才确认送出的数据已经正确到达目的地址, 因此答案是D 。
17．计算机硬件能够直接执行的是（ ）。
Ⅰ. 机器语言程序Ⅱ. 汇编语言程序Ⅲ. 硬件描述语言程序
A. 仅Ⅰ
B. 仅Ⅰ Ⅱ
C. 仅Ⅰ Ⅲ
D. Ⅰ Ⅱ Ⅲ
【答案】A
【解析】机器语言是计算机唯一可以直接执行的语言。汇编语言属于低级语言, 但其源程必须要翻译成目标程序成为机器语言程序后才能被直接执行。硬件描述语言是电子系统硬件行为描述、结构描述、数据流描述的语言。
18．假设5个进程P0、P1、P2、P3、P4共享三类资源R1、R2、R3, 这些资源总数分别为18、6、22。时刻的资源分配情况如下表所示, 此时存在的一个安全序列是（ ）。
表 资源分配情况表
A.P0, P2, P4, P1, P3
B.P1, P0, P3, P4, P2
C.P2, P1, P0, P3, P4
D.P3, P4, P2, P1, P0P0
【答案】D 。