2018年北京市培养单位高能物理研究所863计算机学科综合(专业)之数据结构考研仿真模拟五套题
● 摘要
一、填空题
1． 一棵有11个结点的满二叉树有_____个度为1的结点、有_____个分支(非终端) 结点和_____个叶子，该满二叉树的深度为_____。 【答案】或
【解析】满二叉树没有度为1的结点，度为0的结点等于度为2的结点个数+1。
2． 当广义表中的每个元素都是原子时，广义表便成了_____。
【答案】线性表
【解析】如果每个元素都是原子，则元素不可分。此时的元素是只有一对一的关系，所以广义表变成了线性表。
3． 实现字符串拷贝的函数strcpv 为:
(_____)
【答案】s++＝*t++或(*s++＝*t++)!＝'\0’
4． N 个顶点的连通图用邻接矩阵表示时，该矩阵至少有_____个非零元素。 【答案】
【解析】所谓连通图一定指的是无向图，有向图会称作强连通图。连接N 个顶点，至少需要N －1条边就可以了。由于无向图的每一条边同时关联了两个顶点。因此用邻接矩阵表示时，该矩阵至少有2(N－1) 个非零元素。
5． 设有一个10阶对称矩阵A 采用压缩存储方式(以行为主序存储:a 11＝l) ， 则a 85的地址为_____。
【答案】33
【解析】设存储的元素的行标为i ，列标为j 。若i ＞＝j ，则的地址为l ＋2＋... ＋i ﹣l ＋j ＝i(i﹣l)/2＋j 。若i ＜j 。则的地址为j(j﹣l)/2＋i 。将i ＝8，j ＝5代入得33。
6． 按LSD 进行关键字排序，除最次位关键字之外，对每个关键字进行排序时，只能用_____的排序方法。
【答案】稳定
7． 若不考虑基数排序，则在排序过程中，主要进行的两种基本操作是关键字的 _____和记录的_____。
【答案】比较；移动
8． 在单链表L 中，指针P 所指结点有后继结点的条件是_____
【答案】P ﹣＞next! ＝NULL
【解析】指针所指节点的指针域所指向的元素非空，说明该指针所指节点有后继结点。
9． 数据结构是研讨数据的_____和_____以及它们之间的相互关系，并对与这种结构定义相应的_____, 设计出相应的_____。
【答案】逻辑结构；物理结构；操作(运算) ；算法
10．n 个顶点的有向图用邻接矩阵array 表示，下面是其拓扑排序算法，试补充完整。
注:(1)图的顶点号从0开始计；
(2)indegree是有n 个分量的一维数组，放顶点的入度，
(3)函数crein 用于记算顶点入度；
(4)有三个函数
回1，否则0) 。
("图有回路") ;
【答案】
其含义为数据data 入栈，出栈和测试栈是否空(不空返
【解析】有向图用邻接矩阵表示时，顶点i 的入度等于第i 列的所有元素之和。拓扑排序过程:首先将入度为0的顶点全部进栈。然后弹出栈顶结点，并将与弹出的顶点相连的其它顶点的入度
减一，然后判断这些顶点的入度是否为零，如果为零，继续进栈，重复这些操作，完成拓扑排序。
二、判断题
11．任何二叉树的后序线索树进行后序遍历时都必须用栈。（ ）
【答案】 ×
【解析】任何结点至多只有左子树的二叉树的遍历就不需要栈。
12．当改变网上某一关键路径上任一关键活动后，必将产生不同的关键路径。（ ）
【答案】×
【解析】当改变任意关键路径上的关键话动之后，这个活动可能还是关键活动，因此不会产生不同的关键路径。
13．倒排文件是对次关键字建立索引。（ ）
【答案】√
【解析】倒排文件是对每一个次关键字项建立次关键字索引(称为倒排表) ，将所有具有相同次关键字的记录的物理记录号都填入倒排表为此次关键字的表中。
14．为提高排序速度，进行外排序时，必须选用最快的内排序算法。（ ）
【答案】×
【解析】外部排序算法最常用的是多路归并，即将原文件分解成多个能够一次性装人内存的部分，分别把每一部分调入内存完成排序。然后，对己经排序的子文件进行归并排序。
15．在动态存储管理系统中做空间分配时，最佳适配法与最先适配法相比，前者容易增加闲置空间的碎片。（ ）
【答案】√
【解析】最佳适配法:将可利用空间表中一个不小于n 且最接近n 的空闲块的一部分分配给用户；最先适配法:从表头指针开始查找可利用空间表，将找到的第一个大小不小于n 的空闲块的一部分分配给用户；从适配法选择上可以看出最佳适配法会增加闲置空间。
16．有n 个数顺序(依次) 入栈，出栈序列有Cn 种，
【答案】 √
17．一棵树中的叶子数一定等于与其对应的二叉树的叶子数。（ ）
【答案】 ×
【解析】一颗树的叶子树与它对一个的二叉树的叶子树没有直接联系。不妨举例:假设一个有三个结点的二叉树，层数为2。则它的叶结点数为2。将其按规则转为对应的二叉树时，则它的叶结点数为1。
18．完全二叉树肯定是平衡二叉树。（ ）
【答案】×
（ ）