2017年合肥工业大学科研机构和宣城校区848软件工程学科专业基础综合之数据结构考研仿真模拟题
● 摘要
一、填空题
1． 二叉树的前序序列和中序序列相同的条件是_____。
【答案】空树或任何结点至多只有右子树的二叉树
【解析】前序遍历的顺序为根左右，中序遍历的顺序为左根右，因此若中序遍历和前序遍历序列相同，则任何结点都没有左子树。
2． 表达式
【答案】
3． 当两个栈共享一存储区时，栈利用一维数组当栈1空时，
【答案】
为_____，栈2空时
，
表示，两栈顶指针为
的后缀表达式是_____。
则
为_____，栈满时为_____。
【解析】共享栈的栈底在共享存储区的两端，当栈满时栈顶相邻。
4． 检索是为了在文件中寻找满足一定条件的记录而设置的操作。检索可以按_____检索。也可以按_____检索；按_____检索又可以有_____检索和_____检索。
【答案】关键字；记录号；记录号；顺序；直接
5． 顺序栈用
【答案】
存储数据，栈顶指针是top ，则值为x 的元素入栈的操作是_____。
【解析】先判断栈是否满，如果不满，元素入栈。否则返回溢出信息。 6． 设有一个10阶对称矩阵A 采用压缩存储方式，（以行为主序存储：）则
【答案】33
【解析】设存储的元素的行标为i ，列标为j 。若
则
则的地址为
的地址为_____。
若
的地址为将代入得33。
7． 对单链表中元素按插入方法排序的C 语言描述算法如下，其中L 为链表头结点指针。请填充算法中标出的空白处，完成其功能。
【答案】（1）（2）（3）（4）（5）
置空链表，然后将原链表结点逐个插入到有序表中
当链表尚未到尾，p 为工作指针
查P 结点在链表中的插入位置，这时q 是工作指针
将P 结点链入链表中
是q 的前驱，u 是下个待插入结点的指针
8． 下面程序的功能是用递归算法将一个整数按逆序存放到一个字符数组中。如123存放成321。请填空：
【答案】
【解析】通过递归算法，首先找到最高位的值，将其放到str 对应的数组中，依次反向获取从高位到地位的值，将其放到数组中，完成了将整数逆序放到一个字符数组中。
9． 有五个数据依次入栈：1，2, 3, 4, 5。在各种出栈的序列中，以3, 4先出栈的序列有_____。（3在4之前出栈）
【答案】3个
【解析】以3, 4先出栈的序列有34521、34215、34251共3个。
10．在一个具有n 个单元的顺序栈中，假定以地址高端（即下标为n 的单元）作为栈底，以top 作为栈顶指针，则当向栈中压入一个元素时，top 的变化是top=_____。
【答案】
【解析】由于栈底在地址高端，栈中压入一个元素时，栈顶向地址底端移动一个单位，
所以
二、判断题
11．B-树中所有结点的平衡因子都为零。（ ）
【答案】√
【解析】一棵m 阶的B-树，如果不为空，则所有的叶子结点都出现在同一层次上，所以B-树总的所有结点的平衡因子都为零。
12．堆是满二叉树。（ ）
【答案】× 【解析】堆的定义： n 个关键字序列
且
且
称为堆，当且仅当该序列满足如下性质（简称为堆性质）：
小根堆：满足第①种情况的堆； 大根堆：满足第②种情况的堆。
因此并不能保证堆是满二叉树。
13．不同的求最小生成树的方法最后得到的生成树是相同的。（ ）
【答案】×
，生成树不同，每棵树的权也可能不同。若生【解析】对于一个带权连通无向图G=（V ，E ）
成树T 上的所有边的权值之和最小，则T 称为G 的最小生成树。因此可以看出，最小生成树不是唯一的，最小生成树的权值之和总是唯一的。
14．十字链表是无向图的一种存储结构。（ ）
【答案】×
【解析】十字链表是有向图的另一种链式存储结构。在十字链表中，对应于有向图的每条弧有一个结点，对应于每个顶点也有一个结点。类似于邻接表是无向图的一种链式存储结构。
15．在伙伴系统中的伙伴是指任意两块大小相同、位置相邻的内存块。（ ）
【答案】×
【解析】伙伴系统的伙伴不一定是位置相邻的内存块。
起始地址为P ，大小为的内存块，其伙伴块的起始地址计算公式如下：
只要符合公式的内存块都是伙伴。
16．在用堆排序算法排序时，如果要进行增序排序，则需要采用“大根堆”。（ ）
【答案】√
，使其n 个元素的最大（小）【解析】堆排序：基本思想先将原始序列构造成一个堆（初始堆）
相关内容
相关标签