2017年天津财经大学计算机系统结构818计算机专业综合之数据结构考研冲刺密押题
● 摘要
一、填空题
1． 设有个结点的完全二叉树顺序存放在向量
【答案】
中，其下标值最大的分支结点为_____。
【解析】最大的分支结点是最后一个叶子结点的父结点。
2． 下面程序的功能是用递归算法将一个整数按逆序存放到一个字符数组中。如123存放成321。请填空：
【答案】
【解析】通过递归算法，首先找到最高位的值，将其放到str 对应的数组中，依次反向获取从高位到地位的值，将其放到数组中，完成了将整数逆序放到一个字符数组中。
3． 栈是_____的线性表，其运算遵循_____的原则。
；后进先出 【答案】操作受限（或限定仅在表尾进行插入和删除操作）
4．
每一棵树都能唯一地转换为它所对应的二叉树。若已知一棵二叉树的前序序列是中序序列是前庁序列是_____。
【答案】前序是
。
.
，则它的后庁序列是_____。设上述二叉树是由某棵树转换而成，则该树的
【解析】树的抑序序列对应二叉树的前序序列. 该二叉树转换成森林吋含三棵树. 其第一棵树的
5． 设T 和P 是两个给定的串，在T 中寻找等于P 的子串的过程称为_____，又称P 为_____。
【答案】模式匹配；模式串
6． 在基于关键字比较且时间为O （nl 〇g2n ）的排序中，若要求排序是稳定的，则可选用_____，则可选用_____排序。 排序；若要求就地排序（及辅助空间为0（1））
【答案】归并；堆
7． 设广义表
则
是_____tail（L ）是_____；L 的长度是_____；深度是_____。
；；2；2 【答案】（ ）（（ ））
【解析】广义表的表头是表的第一个元素，表尾是除了第一个元素外其余的所有的元素构成的表；表的长度指表中元素的个数；表的深度指展开后括号的层数。
8． 阅读下列程序，指出其功能，并写出空格处应填上的语句。
的元素，如该元素已在哈希表中，报告出错。
【答案】
【解析】本题是在哈希表ht[]中插入值为
9． 从平均时间性能而言，_____排序最佳。
【答案】快速
【解析】快速算法的平均时间复杂度为nlogn 。
10．有五个数据依次入栈：1，2, 3, 4, 5。在各种出栈的序列中，以3, 4先出栈的序列有_____。（3在4之前出栈）
【答案】3个
【解析】以3, 4先出栈的序列有34521、34215、34251共3个。
二、选择题
11．假设5个进
程共享三类资
源题表资源分配情况表
这些资源总数分别
为
时刻的资源分配情况如题表所示，此时存在的一个安全序列是（ ）。
【答案】D 。
【解析】典型的死锁避免算法、银行家算法的应用。本题的题型与2011年的27题相似。银行家算法是操作系统中的一个重点知识单元，考生对此应该非常熟悉，本题并无难点。分析一下下表，可以看到
，
运行是可以的。
本题也可以排除法，时刻可用资源是分别为2, 3, 3, 此时刻，P0需要
分别为2, 3, 7，故排除A , P1需要Rl ，R2, R3分别为1，3, 3, P2还需要资源Rl ，R2, R3分别为0, 0, 6，故C 排除，P3需要Rl ，R2, R3分别为2, 2, 1。所以正确答案在B ，D 之间。看B 选项，P1之后的可用资源Rl ，R2, R3分别变为6, 3，6，而P0尚需资源2, 3, 7, 故B 方案行不通。因而最终答案只有D 项。
12．已知序列25, 13, 10, 12, 9是大根堆，在序列尾部插入新元素18, 将其再调整为大根堆，调整过程 中元素之间进行的比较次数是（ ）。
A.1 B.2 C.4 D.5
【答案】B
【解析】对堆插入或删除一个元素，有可能不满足堆的性质，堆被破坏，需要调整为新堆。 （1）为原堆，
相关内容
相关标签