2017年合肥工业大学科研机构和宣城校区848软件工程学科专业基础综合之数据结构考研冲刺密押题
● 摘要
一、填空题
1． 中缀式
运算结果为_____。 【答案】
【解析】中缀式相当于中序遍历，前缀式相当于前序遍历，后缀式相当于后序遍历。
2． —棵左子树为空的二叉树在前序线索化后，其中的空链域的个数为 _____。
【答案】2
【解析】只有根结点的做指针为空和最右边的叶结点的右指针为空。
3． 在下面的程序段中，对X 的赋值语句的时间复杂度为_____（表示为n 的函数）。
【答案】1＋（1＋2）＋（1＋2＋3）＋"•＋（l ＋2＋... ＋n ）=n（n ＋1）（n ＋2）/6，即对应的前缀式为_____，若则后缀式的
【解析】当i=l时，赋值语句就被执行了一次。当i=2时，赋值语句被执行了1＋2次。当i=3时，赋值语句被执行了1＋2＋3次。可以推出赋值语句总共被执行了1＋（1＋2）＋（1＋2＋3）＋…＋（l ＋2＋... ＋n ）=n（n ＋1）（n ＋2）/6次。
4． 空格串是指_____，其长度等于_____。
【答案】由空格字符（值32）所组成的字符串；空格个数
5． 实现字符串拷贝的函数strcpy 为：
【答案】
第 2 页，共 42 页
6． VSAM （虚拟存储存取方法）文件的优点是：动态地_____，不需要文件进行_____，并能较快地_____进行查找。
【答案】分配和释放存储空间；重组；对插入的记录
7． 已知二叉排序树的左右子树均不为空，则_____上所有结点的值均小于它的根结点值，_____上所有结点的值均大于它的根结点的值。
【答案】左子树；右子树
【解析】二叉排序树或者是一棵空树，或者是具有下列性质的二叉树：①若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；②若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；③它的左、右子树也分别为二叉排序树。
8． 如果按关键码值递増的顺序依次将关键码值插入到二叉排序树中，则对这样的二叉排序树检索时，平均比较次数为_____。 【答案】
【解析】如果关键码是排好序的，构建二叉排序树就会形成一个单支树，它的查找效率和顺 序查找效率一样为
9． 顺序存储结构是通过_____表示元素之间的关系的；链式存储结构是通过_____表示元素之间的关系的。
【答案】物理上相邻；指针
【解析】顺序存储结构是通过物理位置表示元素之间的关系的，链式存储结构通过指针表示元素之间的关系。
10．在一个具有n 个单元的顺序栈中，假定以地址高端（即下标为n 的单元）作为栈底，以top 作为栈顶指针，则当向栈中压入一个元素时，top 的变化是top=_____。 【答案】
【解析】由于栈底在地址高端，栈中压入一个元素时，栈顶向地址底端移动一个单位，
所以
二、判断题
11．在二叉排序树中插入一个新结点，总是插入到叶结点下面。（ ）
【答案】×
【解析】不一定。插入二叉排序树的原则：将新节点元素值与根结点元素值相比较，如小于
根结点元素值则插入到左子树口，否则插入到右子树中。所以就可能插在一个度为1的结点下面。
12．为提高排序速度，进行外排序时，必须选用最快的内排序算法。（ ）
【答案】×
第 3 页，共 42 页
【解析】外部排序算法最常用的是多路归并，即将原文件分解成多个能够一次性装人内存的部分，分别把每一部分调入内存完成排序。然后，对已经排序的子文件进行归并排序。
13．折半查找与二元查找树的时间性能在最坏的情况下是相同的。（ ）
【答案】×
【解析】不是，当二元查找树是一棵单支树时，时间性能是而折半查找依然是
14．哈希函数越复杂越好，因为这样随机性好，冲突概率小。（ ）
【答案】×
【解析】随机性好和冲突概率小跟哈希函数的复杂程度无关，是根据具体情况而定的，跟实际的数据有很大
关系。
15．任何二叉树的后序线索树进行后序遍历时都必须用栈。（ ）
【答案】×
【解析】任何结点至多只有左子树的二叉树的遍历就不需要栈。
16．拓扑排序的有向图中，最多存在一条环路。（ ）
【答案】×
【解析】要进行拓扑排序，需要满足一个条件为：若顶点A 在序列中排在顶点B 的前面，则在图中不存在 顶点B 到顶点A 的路径。如果是一个有环图，则不能满足这个条件, 所以拓扑排序的有向图中不能存在环路。
17．平衡二叉树中，若某个结点的左、右孩子的平衡因子为零，则该结点的平衡因子一定是零。（ ）
【答案】×
【解析】平衡因子定义为该结点的左子树的深度减去右子树的深度，一个平衡二叉树中，某节点的左右孩子的平衡因子为0，说明左孩子的左子树和右子数的深度相同，而且右子树的左子树和右子数的深度相同，但这不能说明该节点的左子树和右子树的深度相同。
18．一个广义表可以为其他广义表所共享。（ ）
【答案】√
【解析】因为广义表中的元素还可能是表，所以对于一个广义表可以为其他广义表所共享。
19．—个稀疏矩阵采用三元组形式表示，若把三元组中有关行下标与列下标的值互换，并把m 和n 的值互换，则就完成了
【答案】×
【解析】稀疏矩阵转置后，除行列下标及行列数互换外，还必须确定该元素转置后在新三元
第 4 页，共 42 页 的转置运算。（ ）
相关内容
相关标签