2018年辽宁工程技术大学管理科学与工程935数据结构考研核心题库
● 摘要
一、填空题
1． 遍历图的过程实质上是_____，广度优先遍历图的时间复杂度____；深度优先遍历图的时间复杂度_____，两者不同之处在于_____，反映在数据结构上的差别是_____。
【答案】查找顶点的邻接点的过程；0(n+e)；0(n+e)；访问顶点的顺序不同；队列和栈 【解析】广度优先遍历图使用队列这种数据结构，深度优先遍历图使用栈这种数据结构。
2． 在双向循环链表中，向P 所指的结点之后插入指针f 所指的结点，其操作是_____、_____、_____、_____。
【答案】f ﹣＞next ＝p ﹣＞next ；f ﹣＞prior ＝p ；p ﹣＞next ﹣＞prior ＝f ；p ﹣＞next ＝f ；
3． 在顺序存储的二叉树中，编号为i 和j 的两个结点处在同一层的条件是_____。
【答案】要加“虚结点”。
设编号为i 和j 的结点在顺序存储中的下标为s 和t , 则结点i 和j 在同一层上的条件是
。
4． 已知t) ，LEN(t)＋1))
:
【答案】
，其中n ＞m ，队头和队尾指针分别为front 和rear ，
5． 已知一循环队列的存储空间为则此循环队列判满的条件是_____
【答案】
6． 当两个栈共享一存储区时，栈利用一维数组stack(1，，1) 表示，两栈顶指针为top[l]与top[2]，则当栈1空时，top[l]为_____，栈2空时，top[2]为_____，栈满时为_____。
【答案】0；n+1；top[l]+l＝top[2]
【解析】共享栈的栈底在共享存储区的两端，当栈满时栈顶相邻。
；
；ASSIGN(S，U) ；ASSIGN(V，SUBSTR(S，INDEX(S，，求REPLACE(S，V ，m) ＝_____。
【解析】用顺序存储结构存储二叉树时，要按完全二叉树的形式存储，非完全二叉树存储时，
7． 对于一个具有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． 如某二叉树有20个叶结点，有30个结点仅有一个孩子，则该二叉树的总结点数为_____。
【答案】69
【解析】二叉树叶结点数为20, 则度为2的结点数为19, 所以总的结点数为20+19+30=69。
10．对n 个元素的序列进行起泡排序时，最少的比较次数是_____。
【答案】n －1
【解析】如果序列是正序，冒泡排序第一次只要进行n －1次比较，发现没有移动元素，说明序列有序。
二、算法设计题
11．设单链表的表头指针为h ，结点结构由data 和next 两个域构成，其中data 域为字符型。写出算法dc(h，n) ，判断该链表的前n 个字符是否中心对称。例如xyx ，xyyx 都是中心对称。
【答案】算法如下:
//h是带头结点的n 个字符元素的单链表，本算法判断链表是否中心对称
//i记下结点个数，s 是字符栈
//P是链表的工作指针，指向待处理的当前元素
//链表前一半元素入栈
//恢复最后的i 值
//若n 是奇数，后移过中心结点
//测试
是否中心对称
//链表中心对称
//链表不中心对称
//算法结束
12．当一棵有n(
) 个结点的二叉树按顺序存储方式存储在
中时，试写一个算法，求
出二叉树中结点值分别为X 和Y 的两个结点的最近公共祖先结点的值。
【答案】算法如下:
二叉树顺序存储在数组
中，本算法求结点i 和j 的最近公共祖先结点的值
下标为i 的结点的双亲结点的下标
下标为j 的结点的双亲结点的下标
所査结点的最近公共祖先的下标是
整型
13．已知关键字序列(
试写出一算法将(
利用(1)的算法写一个建大根堆的算法。 【答案】(1)算法如下:
''
假设
是大堆，本算法把
(2)
14．设记录
的关键字为
。
，树结点
的败者树，要求除
指向败者记录，
和1
为全胜以外，只
调成大堆
，值是
设元素类型为
) 是大根堆。
) 调整为大根堆；
记录下标。写一算法产生对应上述用O(1)辅助空间。
【答案】算法如下:
选得最小关键字记录后，沿从叶结点R[s]到根结点T[0]的路径调整败者树
是
的双亲结点