2018年北京工业大学计算机学院896数据结构[专业学位]之数据结构考研仿真模拟五套题
● 摘要
一、填空题
1． 索引顺序文件既可以顺序存取，也可以 _____存取。
【答案】随机
2． 设广义表L ＝(（ ），（ ）) ，则head(L)是_____tail(L)是_____L的长度是_____；深度是_____。
【答案】（ ）；(（ ）) ；2；2
【解析】广义表的表头是表的第一个元素，表尾是除了第一个元素外其余的所有的元素构成的表；表的长度指表中元素的个数；表的深度指展开后括号的层数。
3． 无用单元是指_____，例_____
【答案】用户不再使用而系统没有回收的结构和变量；
4． 设为哈夫曼树的叶结点数目，则该哈夫曼树共有_____个结点。 【答案】
【解析】哈夫曼树只有度为0和2的节点。
5． 中缀式(c-d)对应的前缀式为_____，若a=l，b=2, c=3, d=4, 则后缀式
运算结果为_____。 【答案】
【解析】中缀式相当于中序遍历，前缀式相当于前序遍历，后缀式相当于后序遍历。
6． 在基于关键字比较且时间为_ 的排序中，若要求排序是稳定的，则可选用_____排序；若要求就地排序(及辅助空间为O(1))，则可选用_____排序。
【答案】归并；堆
7． 栈是_____的线性表，其运算遵循_____的原则。
【答案】操作受限(或限定仅在表尾进行插入和删除操作) ；后进先出
8． —棵深度为k 的平衡二叉树， 其每个非终端结点的平衡因子均为0，则该树共有_____个结点。
【答案】
第 2 页，共 66 页 的【解析】每个非终端结点都是0表示该平衡二叉树没有高度落差。也就是说它是一棵满二叉
树。故结点个数为。
9． 在一个无向图的的邻接表中，若表结点的个数是m ，则图中边的条数是_____条。 【答案】
【解析】对于无向图，在邻接表中，如果存在n 条边，则会有2n 个表结点。
10．试利用下列栈和串的基本操作完成下述填空题。
initstack(S)置S 为空栈；
push(S，X) 元素X 入栈；
pop(S)出栈操作；
gettop(S)返回栈顶元素；
sempty(S)判栈空函数；
setnull(St)置串St 为空串；
length(st)返回串st 的长度；
equal(S1，S 2) 判串S 1并S 2是否相等的函数；
concat(S1，S 2) 返回联接S 1和S 2之后的串；
sub(S，i ，1) 返回S 中第i 个字符；
empty(st)判串空函数
FUNCinvert(pre:string ；V ARexp :string) :boolean ；
{若给定的表达式的前缀式pre 正确，本过程求得和它相应的表达式exp 并返回true ，否则exp 为空串，并返回false 。已知原表达式中不包含括弧，opset 为运算符的集合。
)
_____；_____；
_____THEN_____
IF_____THEN_____
(_____，_____)；
(_____，_____)；
_____
_____THEN
第 3 页，共 66 页
注意:每个空格只填一个语句。
【答案】(1)initstack(S)//栈s 初始化为空栈
(2)setnull(exp)//串exp 初始化为空串
(3)chinopset//判取出字符是否是操作符
(4)push(s，ch)//如ch 是运算符，则入操作符栈s
(5)sempty(s)//判栈s 是否为空
(6)succ:＝false//若读出ch 是操作数且栈为空，则按出错处理
(7)exp
(8)ch//若ch 是操作数且栈非空，则形成部分中缀表达式
(9)exp
(10)gettop(s)//取栈顶操作符
(11)pop(s)//操作符取出后，出栈
(12)sempty(s)//将pre 的最后一个字符(操作数) 加入到中缀式exp 的最后
11．如果按关键码值递增的顺序依次将关键码值插入到二叉排序树中，则对这样的二叉排序树检索时，平均比较次数为_____。 【答案】
【解析】如果关键码是排好序的，构建二叉排序树就会形成一个单支树，它的查找效率和顺序查找效率一样为。
12．在顺序存储的二叉树中，编号为i 和j 的两个结点处在同一层的条件是_____。 【答案】
要加“虚结点”。
设编号为i 和j 的结点在顺序存储中的下标为s 和t , 则结点i 和j 在同一层上的条件是
。
【解析】用顺序存储结构存储二叉树时，要按完全二叉树的形式存储，非完全二叉树存储时，
二、单项选择题
13．设与某资源相关联的信号量初值为3，当前为1，若M 表示该资源的可用个数，N 表示等待该资源的进程数，则M ，N 分别是（ ）.
A.0、1
B.1、0
C.1、2
D.2、0
【答案】B
【解析】信号量初值是3表示资源数有3个，当前为1表示已经用掉2个，剩余可用的资源
第 4 页，共 66 页