2018年北京市培养单位数学与系统科学研究院863计算机学科综合(专业)之数据结构考研仿真模拟五套题
● 摘要
一、填空题
1．
【答案】5
2． 组成串的数据元素只能是_____。
【答案】字符
3． 高度为4的3阶B-树中，最多有_____个关键字。
【答案】26
【解析】第4层是叶结点，1层至3层每个结点两个关键字，每个节点的关键字达到最大时，关键字最多。
4． 在顺序存储的二叉树中，编号为i 和j 的两个结点处在同一层的条件是_____。 【答案】
要加“虚结点”。
设编号为i 和j 的结点在顺序存储中的下标为s 和t , 则结点i 和j 在同一层上的条件是
。
5． 设有两个算法在同一机器上运行，其执行时闻分别为100n 2和2n ，要使前者快于后者，n 至少为_____。
【答案】15
2n 【解析】当时，100n2>2n，而，时，100n ＜2
6． 设m 、n 均为自然数，m 可表示为一些不超过n 的自然数之和，f(m，n) 为这种表示方式的数＝_____ 【解析】用顺序存储结构存储二叉树时，要按完全二叉树的形式存储，非完全二叉树存储时，目。例f(5，3) ＝5, 有5种表示方式:3＋2, 3＋1＋1，2＋2＋1，2＋1＋1＋1，1＋1＋1＋1＋1。
①以下是该函数的程序段，请将未完成的部分填入，使之完整。
_____
_____；}
_____；
}
，
_____)
②执行程序，f(6，4) ＝_____。
【答案】①1; 1; f(m, n ﹣1) ; n ②9
7． 分别采用堆排序，快速排序，起泡排序和归并排序，对初态为有序的表，则最省时间的是_____算法，最费时间的是_____算法。
【答案】起泡；快速
【解析】当初态为有序表时，冒泡排序只需要进行一趟比较即可，此时时间复杂度为O(n)，
2而快速排序算 法需要比较的次数达到最大，时间复杂度为O (n) 。
8． 设数组数组中任一元素A[i，j]均占内存48个二进制位，从首地址2000开始连续存放在主内存里，主内存字长为16位，那么
(1)存放该数组至少需要的单元数是_____；
(2)存放数组的第8列的所有元素至少需要的单元数_____；
(3)数组按列存储时，元素A[5，8]的起始地址是_____。
【答案】270；27；2204
【解析】数组的元素个数为9*10＝90，因为每个元素占内存48个二进制位，即6个字节。故总需要90*6＝540个字节，因为主内存字长为16位，即2个字节，所以至少需要540/2＝270个单元数。第8列有9个元素，共占9*6＝54个字节，因此至少需要54/2＝27个单元数。由题知，每个元素占3个单元。按列存储时，A[5，8]的起始地址为2000＋[(8﹣1)*9＋(5﹣0)]*3＝2204。
9． 按LSD 进行关键字排序，除最次位关键字之外，对每个关键字进行排序时，只能用_____的排序方法。
【答案】稳定
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
注意:每个空格只填一个语句。
【答案】(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 的最后