2018年北京市培养单位国家空间科学中心863计算机学科综合(专业)之数据结构考研核心题库
● 摘要
一、填空题
1． 在顺序存储的二叉树中，编号为i 和j 的两个结点处在同一层的条件是_____。 【答案】
要加“虚结点”。
设编号为i 和j 的结点在顺序存储中的下标为s 和t , 则结点i 和j 在同一层上的条件是
。
2． 在拓扑分类中，拓扑序列的最后一个顶点必定是_____的顶点。
【答案】出度为0
【解析】如果最后一个顶点的出度不为0, 则必定还有顶点存在，与题目所说的最后一个顶点矛盾，所有最后一个顶点的出度必定为零。
3． 用循环链表表示的队列长度为n ，若只设头指针，则出队和入队的时间复杂度分别是_____和_____；若只设尾指针，则出队和入队的时间复杂度分别是_____和_____。
【答案】O(1)；O(n)；O(1)；O(1)
【解析】队列的出队操作即删除队头的元素，队列的入队操作即在队尾添加元素，循环链表只设头指针，出队时，只要把头结点的下一个结点删除就好了，入队时，要把新的结点插入队尾，必须把队列遍历，找到队尾指针，才能插入。循环队列只设尾指针，出队时只要把为指针的下一个结点或者下下个结点删除即可，入队时，只要在尾指针的后面插入新的结点，并更新尾结点即可。
4． 已知链队列的头尾指针分别是f 和r ，则将值x 入队的操作序列是_____。
【答案】S ＝(LinkedList*)malloc(sizeof (LNode))；s ﹣＞data ＝x ；s ﹣＞next ＝r ﹣＞next ；r ﹣＞next ＝s ；r ＝s ；
【解析】队列采用链式存储结构，先分配一个节点的内存，然后在队尾添加该节点。
5． 在有n 个顶点的有向图中，每个顶点的度最大可达_____。
【答案】2(n－1)
【解析】当有向图为完全连通图时每个顶点的度达到最大，出度入度均为n －1。
【解析】用顺序存储结构存储二叉树时，要按完全二叉树的形式存储，非完全二叉树存储时，
6． 若用n 表示图中顶点数目，则有_____条边的无向图成为完全图。 【答案】
【解析】无向完全图中任意一个顶点都和其他n －1个顶点都有一条边，即为n(n－1) 。又因
. 。 为每条边重复出现两次，所有无向完全图的边数为
7． 当两个栈共享一存储区时，栈利用一维数组stack(1，，1) 表示，两栈顶指针为top[l]与top[2]，则当栈1空时，top[l]为_____，栈2空时，top[2]为_____，栈满时为_____。
【答案】0；n+1；top[l]+l＝top[2]
【解析】共享栈的栈底在共享存储区的两端，当栈满时栈顶相邻。
8． n 个顶点的有向图用邻接矩阵array 表示，下面是其拓扑排序算法，试补充完整。
注:(1)图的顶点号从0开始计；
(2)indegree是有n 个分量的一维数组，放顶点的入度，
(3)函数crein 用于记算顶点入度；
(4)有三个函数
回1，否则0) 。
("图有回路") ;
【答案】
其含义为数据data 入栈，出栈和测试栈是否空(不空返
【解析】有向图用邻接矩阵表示时，顶点i 的入度等于第i 列的所有元素之和。拓扑排序过程:首先将入度为0的顶点全部进栈。然后弹出栈顶结点，并将与弹出的顶点相连的其它顶点的入度
减一，然后判断这些顶点的入度是否为零，如果为零，继续进栈，重复这些操作，完成拓扑排序。
9． 设二维数组A 的行和列的下标范围分别为[0:8]和[0:10]，每个元素占2个单元，按行优先顺序存储，第一个元素的存储起始位置为b ，则存储位置为b+50处的元素为_____。
【答案】A[2][3]
【解析】令这个元素的行标为i ，列标为j 。则它的存储位置是(ll*i＋j ＋l ﹣l)*2＋b 。当其值为b ＋50时，则i ＝2，j ＝3。
10．假定有k 个关键字互为同义词，若用线性探测再哈希法把这k 个关键字存入哈希表中，至少要进行_____次探测。 【答案】
的次数最小。总次数为
。 【解析】当该关键字发生冲突时，用线性探测不会遇到别的关键字冲突，这个时候需要探测二、判断题
11．若把堆看成是一棵完全二叉树，则该树一定是一棵二叉排序树。（ ）
【答案】×
【解析】堆中某个节点的值总是不大于或不小于其父节点的值，这个并不是二叉排序树的性质。
12．不同的求最小生成树的方法最后得到的生成树是相同的。（ ）
【答案】×
【解析】对于一个带权连通无向图G=(V，E) , 生成树不同，每棵树的权也可能不同。若生成树T 上的所有边的权值之和最小，则T 称为G 的最小生成树。因此可以看出，最小生成树不是唯一的，最小生成树的权值之和总是唯一的。
13．循环队列也存在空间溢出问题。（ ）
【答案】 √
【解析】循环队列的存储空间也是有限的，因此也存在空间溢出问题。
14．一个广义表可以为其他广义表所共享。（ ）
【答案】 √
【解析】因为广义表中的元素还可能是表，所以对于一个广义表可以为其他广义表所共享。
15．有向图中顶点V 度等于其邻接矩阵中第V 行中的1的个数。（ ）
【答案】×
【解析】有向图顶点V 的出度等于其邻接矩阵第V 行中的1的个数，而有向图中V 的度等于其邻接矩阵中边表出现的V 的个数。
16．用希尔(Shell)方法排序时，若关键字的初始排序杂乱无序，则排序效率就低。（ ）
【答案】×
【解析】希尔排序的基本思想是:先将整个待排记录序列分割成为若干子序列分别进行直接插