2017年浙江理工大学经济管理学院938数据结构与数据库技术考研题库
● 摘要
一、填空题
1． 如某二叉树有20个叶结点，有30个结点仅有一个孩子，则该二叉树的总结点数为_____。
【答案】69
【解析】二叉树叶结点数为20, 则度为2的结点数为19, 所以总的结点数为20+19+30=69。
2． 设有一个空找，栈顶指针为1000H （十六进制），现有输入序列为1，2，3, 4, 5，经过PUSH ，PUSH , POP , PUSH , POP ，PUSH ，PUSH 之后，输出序列是_____，而栈顶指针值是_____。设栈为顺序栈，每个元素占4个字节。
【答案】23; 100CH
3． 深度为H 的完全二叉树至少有_____个结点; 至多有_____个结点; H 和结点总数N 之间的关系是_____。
【答案】
4． 在拓扑分类中，拓扑序列的最后一个顶点必定是_____的顶点。
【答案】出度为0
【解析】如果最后一个顶点的出度不为0, 则必定还有顶点存在，与题目所说的最后一个顶点矛盾，所有最 后一个顶点的出度必定为零。
5． 对于给定的元素，可以构造出的逻辑结构有_____，_____，_____，_____四种。
【答案】集合；线性结构；树形结构；图状结构（网状结构）
6． 已知一循环队列的存储空间为环队列判满的条件是（ ）
【答案】
7． 在单链表中设置头结点的作用是_____。
【答案】方便运算
8． —个字符串中_____称为该串的子串。
【答案】任意个连续的字符组成的子序列
9． n 个顶点的有向图用邻接矩阵array 表示，下面是其拓扑排序算法，试补充完整。
注：（1）图的顶点号从0开始计；
第 2 页，共 49 页
其中队头和队尾指针分别为front 和rear , 则此循
（2）indegree 是有n 个分量的一维数组，放顶点的入度， （3）函数crein 用于记算顶点入度；
（4）有三个函数push （data ）, pop（ ）, check（ ）其含义为数据data 入浅，出栈和测试栈是否空（不空返回1, 否则0）。
）
.
【答案】0; j; i; 0; indegree[i]=0; [vex][i]; k==l; indegree[i]=0
【解析】有向图用邻接矩阵表示时，顶点i 的入度等于第i 列的所有元素之和。拓扑排序过程：首先将入度 为0的顶点全部进栈。然后弹出栈顶结点，并将与弹出的顶点相连的其它顶点的入度 减一，然后判断这些顶点的 入度是否为零，如果为零，继续进栈，重复这些操作，完成拓扑排序。
10．设T 和P 是两个给定的串，在T 中寻找等于P 的子串的过程称为_____，又称P 为_____。
【答案】模式匹配；模式串
；
（“图有回路”）
二、选择题
11．在一个文件被用户进程首次打开的过程中，操作系统需做的是（ ）
A. 将文件内容读到内存中 B. 将文件控制块读到内存中 C. 修改文件控制块中的读写权限
D. 将文件的数据缓冲区首指针返回给用户进程 【答案】B 【解析】概念
第 3 页，共 49 页
12．某计算机的控制器采用微程序控制方式，微指令中的操作控制字段采用字段直接编码法，共有33个微命令，构成5个互斥类，分别包含7、3、12、5和6个微命令，则操作控制字段至少有（ ）。
A.5位 B.6位 C.15 位 D.33 位 【答案】C 。
，根据每个类中微命令的多少可以分别【解析】33个微命令分成5个互斥类（即5个字段）
确定字段的长度 为3、2、4、3、3位，又因为采用直接编码方式，所以它们之和
就是操作控制字段的位数。
13．用有向无环图描述表达式（A+B）*（，至少需要顶点的数目为（ ）（A+B）/A）。
A.5 B.6 C.8 D.9 【答案】A 6条边 【解析】一共5个结点
14．若则下列表达式采用8位定点补码运算实现时，会发生溢出的是（ ）
A.x+y B.-x+y C.x-y D.-x-y
【答案】C
【解析】8位定点补码能表示的数的范围为：码能表示的数的范围，会发生溢出
15．有个分支结点的满二叉树的深度是（ ）。
A.
B.
C.
D. 【答案】C
【解析】满二叉树的结点总数=分支的结点总数+非分支的结点总数。由于此树为满二叉树，所以非分支的结点总数为1，所以满二叉树共有个结点，所以满二叉树的深度为
16．在参考摸型中，下列功能需由应用层的相邻层实现的是（ ）
A. 对话管理 B. 数据格式转换
第 4 页，共 49 页
也
A 结果为78, B结果为-128, D结果为-78都在此范围内，只有C 结果128超过了8位定点补