2018年北京市培养单位光电研究院863计算机学科综合(专业)之数据结构考研基础五套测试题
● 摘要
一、填空题
1． 下面描述的是一种构造最小生成树算法的基本思想。设要处理的无向图包括n 个顶点
用相邻矩阵A 表示，边的权全是正数。请在下列划线处填上正确叙述。
(1)若是边，则的值等于_____，若不是边，则A(i, j) 的值是一个比任何
置边的权_____，矩阵的对角线元素全为0。 (2)构造最小生成树过程中，若顶点已包括进生成树，就把相邻矩阵的对角线元素
成_____，若
【答案】(1)已包括进生成树，就把矩阵元素置成_____。 (3)算法结束时，相邻矩阵中_____的元素指出最小生成树的_____。 边上的权值；都大的数；(2)1; 负值；(3)为负；边
2． 堆是一种有用的数据结构。堆排序是一种_____排序，堆实质上是一棵_____结点的层次序列。对含有N 个元素的序列进行排序时，堆排序的时间复杂度是_____，所需的附加存储结点是_____。关键码序列05, 23, 16, 68, 94, 72, 71, 73是否满足堆的险质_____ 。
【答案】选择；完全二叉树；；O(1)；满足堆的性质
3． 从用户的观点看，文件的逻辑结构通常可以区分为两类:一类是如NdBASE 中数据库文件那样的文件组织结构，称为_____文件; 另一种是诸如用各种文字处理软件编辑成的文本文件，称为_____文件。从文件在存储器上的存放方式来看，文件的物理结构往往可区分为三类，即_____， _____和_____。B+树适用于组织_____的索引结构，m 阶B+树毎个结点至多有_____个儿子，除根结点外每个结点至少有_____个儿子，根结点至少有_____个儿子，有k 个儿子的结点必有_____个关键码。
【答案】数据库；文本；顺序组织；随机组织；链组织；随机组织；m ;
4． 已知一循环队列的存储空间为
则此循环队列判满的条件是_____ 【答案】
5． 设为哈夫曼树的叶结点数目，则该哈夫曼树共有_____个结点。 【答案】
【解析】哈夫曼树只有度为0和2的节点。
；2；k ，其中n ＞m ，队头和队尾指针分别为front 和rear ，
6． 数据结构是研讨数据的_____和_____以及它们之间的相互关系，并对与这种结构定义相应的_____, 设计出相应的_____。
【答案】逻辑结构；物理结构；操作(运算) ；算法
7． 一个字符串中_____称为该串的子串。
【答案】任意个连续的字符组成的子序列
8．
线性表
【答案】(n﹣1)/2
【解析】删除第一个元素需要移动n ﹣1次，以此类推，删除最后一个元素需要移动0次。平均次数为(n﹣l)*n/n/2＝(n﹣l)/2。
9． 对n 个记录的表进行简单选择排序，所需进行的关键字间的比较次数为_____。
【答案】n (n－1) /2
【解析】第一次需要n －1次比较，第i 此需要n －i 此比较，所以共需要。
10．设二维数组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。
用数组表示，假定删除表中任一元素的概率相同，则删除一个元素平均需要移动元素的个数是_____。
二、判断题
11．当改变网上某一关键路径上任一关键活动后，必将产生不同的关键路径。（ ）
【答案】×
【解析】当改变任意关键路径上的关键话动之后，这个活动可能还是关键活动，因此不会产生不同的关键路径。
12．采用线性探测法处理散列时的冲突，当从哈希表删除一个记录时，不应将这个记录的所在位置置空，因为这会影响以后的查找。（ ）
【答案】√
【解析】从哈希表删除一个记录，不是将这个记录的位置置空，而是设置一个标记，标记这个元素是无效的了。
13．为提高排序速度，进行外排序时，必须选用最快的内排序算法。（ ）
【答案】×
【解析】外部排序算法最常用的是多路归并，即将原文件分解成多个能够一次性装人内存的部分，分别把每一部分调入内存完成排序。然后，对己经排序的子文件进行归并排序。
14．快速排序和归并排序在最坏情况下的比较次数都是（ ）
【答案】×
【解析】快速排序最坏的情况下比较次数是
15．堆肯定是一棵平衡二叉树。（ ）
【答案】×
【解析】堆是n 个元素的序列，排序树，更不会是平衡二叉树。
可以看成是完全二叉树，但相对于根并无左小右大的要求，故其既不是二叉
16．若一个广义表的表头为空表，则此广义表亦为空表。（ ）
【答案】 ×
【解析】广义表的表头就是广义表的第一个元素。只有非空广义表才能取表头。
17．抽象数据类型与计算机内部表示和实现无关。（ ）
【答案】 √
【解析】抽象数据类型只表示数据的逻辑结构，与计算机内部表示和实现无关。
18．在外部排序过程中，对长度为n 的初始序列进行“置换-选择”排序时，可以得到的最大初始有序段的长度不超过n/2。（ ）
【答案】×
【解析】当输入文件以关键字的升序排序时，只能得到一个长度为文件长度的初始归并段
19．队列逻辑上是一个下端和上端既能增加又能减少的线性表。（ ）
【答案】 ×
【解析】队列只在下端(队尾) 增加，在上端(队头) 减少。
20．二叉树中序线索化后，不存在空指针域。（ ）
【答案】×
【解析】非空二叉树中序遍历第一个结点无前驱，最后一个结点无后继，这两个结点的前驱线索和后继线索为空指针。
三、算法设计题
相关内容
相关标签