2017年上海市培养单位上海高等研究院866计算机原理之数据结构考研仿真模拟题
● 摘要
目录
2017年上海市培养单位上海高等研究院866计算机原理之数据结构考研仿真模拟题（一） ... 2 2017年上海市培养单位上海高等研究院866计算机原理之数据结构考研仿真模拟题（二） . 14 2017年上海市培养单位上海高等研究院866计算机原理之数据结构考研仿真模拟题（三） . 26 2017年上海市培养单位上海高等研究院866计算机原理之数据结构考研仿真模拟题（四） . 39 2017年上海市培养单位上海高等研究院866计算机原理之数据结构考研仿真模拟题（五） . 50
第 1 页，共 61 页
一、填空题
1． 设T 是一棵结点值为整数的二叉排序树，A 是一个任意给定的整数。free_tree在下面的算法中，（T ）在对二叉排序树丁进行后序遍历时释放二又排序树T 的所有结点；
首
先在二叉排序树T 中查找值为A 的结点，根据查找情况分别进行如下处理：（1）若找不到值为A 的结点，则返回根结点的地址（2）若找到值为A 的结点，则删除以此结点为根的子树，并释放此子树中的所有结点，若值为A 的结点是查找树的根结点，删除后变成空的二叉树，则返否则返回根结点的地址。
【答案】
2． 二叉树的前序序列和中序序列相同的条件是_____。
【答案】空树或任何结点至多只有右子树的二叉树
【解析】前序遍历的顺序为根左右，中序遍历的顺序为左根右，因此若中序遍历和前序遍历序列相同，则任何结点都没有左子树。
3． 若不考虑基数排序，则在排序过程中，主要进行的两种基本操作是关键字的_____和记录的_____，
【答案】比较；移动 4． 设有一个10阶对称矩阵A 采用压缩存储方式 ，（以行为主序存储：）则的地址为_____。
【答案】33
【解析】设存储的元素的行标为i ，列标为j 。若
则
的地址为
将
代入得33。
第 2 页，共 61 页
则的地址为若
5． 试利用下列栈和串的基本操作完成下述填空题。
initstack （S ） 置S 为空找； push （S , X ） 元素X 入找； pop （S ） 出栈操作； gettop （S ） 返回栈顶元素； sempty （S ） 判找空函数；
置串 判串 返回联接
empty （st ） 判串空函数
{若给定的表达式的前缀式pre 正确，本过程求得和它相应的表达式exp 并返回true , 否则exp 为空串，并返回false 。已知原表达式中不包含括弧，opset 为运算符的集合。）
注意：毎个空格只填一个语句。 【答案】（1）（2）（3）（4）（5）（6）
栈S 初始化为空栈 串exp 初始化为空串 判取出字符是否是操作符
如ch 是运算符，则入操作符栈s 判栈8是否为空
若读出ch 是操作数且栈为空，则按出错处理
第 3 页，共 61 页
为空串；
是否相等的函数；
之后的串；
length （st ） 返回串st 的长度；
sub （S , i , 1） 返回S 中第i 个字符；
（7）exp （8）（9）exp （10）（11）（12）
取栈顶操作符 操作符取出后，出栈
将pre 的最后一个字符（操作数）加入到中缀式exp 的最后
若ch 是操作数且栈非空，则形成部分中缀表达式
6． 对于一个具有n 个结点的二叉树，当它为一棵_____二叉树时具有最小高度，当它为一棵_____ 时. 具有最大高度
【答案】完全；只有一个叶结点的二叉树
7． 抽象数据类型的定义仅取决于它的一组_____，而与_____无关, 即不论其内部结构如何变化，只要它的_____不变，都不影响其外部使用。
【答案】逻辑特性；在计算机内部如何表示和实现；数学特性
8． 实现字符串拷贝的函数strcpy 为：
【答案】 9
．
求REPLACE （S ，V , m ）=_____。
【答案】
10．
给定一组数据
的值为_____。 【答案】5；96
【解析】每次找两个最小的权值构建哈夫曼树：
以它构造一棵哈夫曼树，则树高为_____，
带权路径长度
已
知
11．在下面的程序段中，对X 的赋值语句的时间复杂度为_____（表示为n 的函数）。
第 4 页，共 61 页
相关内容
相关标签