2018年北京市培养单位信息工程研究所863计算机学科综合(专业)之数据结构考研强化五套模拟题
● 摘要
一、填空题
1． 有向图G=(V, E) ，其中
权d 。E(G)为
，则从源点0到顶点3的最短路径长度是_____，经过的中间顶点是_____。
【答案】50；4
2． 求最短路径的Dijkstra 算法的时间复杂度为_____。 【答案】
3． 一个字符串中_____称为该串的子串。
【答案】任意个连续的字符组成的子序列
4． 无用单元是指_____，例_____
【答案】用户不再使用而系统没有回收的结构和变量；
5． 外排序的基本操作过程是_____和_____。
【答案】生成有序归并段(顺串) ；归并
6． 对n 个元素的序列进行起泡排序时，最少的比较次数是_____。
【答案】n －1
【解析】如果序列是正序，冒泡排序第一次只要进行n －1次比较，发现没有移动元素，说明序列有序。
7． 在一个无向图的的邻接表中，若表结点的个数是m ，则图中边的条数是_____条。 【答案】
【解析】对于无向图，在邻接表中，如果存在n 条边，则会有2n 个表结点。
8． 文件可按其记录的类型不同而分成两类，即 _____和_____文件。
【答案】操作系统文件；数据库
，用三元组表示弧及弧上的
9． 设有两个算法在同一机器上运行，其执行时闻分别为100n 2和2n ，要使前者快于后者，n 至少为_____。
【答案】15
【解析】当时，100n2>2n，而，时，100n ＜2
10．对于双向链表，在两个结点之间插入一个新结点需修改的指针共_____个，单链表为_____个。 2n
【答案】4；2
二、判断题
11．在待排数据基本有序的情况下，快速排序效果好。（ ）
【答案】×
【解析】在待排数据基本有序的情况下，插入排序效果好。
12．在执行某个排序算法过程中，出现了排序码朝着最终排序序列位置相反方向移动，则该算法是不稳定的。（ ）
【答案】×
【解析】例如起泡排序是稳定排序，将4， 3， 2，1按起泡排序排成升序序列，第一趟变成3， 2，1，4，此 时3就朝向最终位置的相反方向移动。
13．若一个广义表的表头为空表，则此广义表亦为空表。（ ）
【答案】 ×
【解析】广义表的表头就是广义表的第一个元素。只有非空广义表才能取表头。
14．健壮的算法不会因非法的输入数据而出现莫名其妙的状态。（ ）
【答案】 √
【解析】算法的健壮性是指当输入数据非法时，算法能作适当的处理并作出反应，而不应死机或输出异常结果。
15．倒排文件的目的是为了多关键字查找。（ ）
【答案】√
【解析】多关键字文件的特点是，在对文件进行检索操作时，不仅对主关键字进行简单询问，还经常需要对次关键字进行其它类型的询问检索。常见的多关键字文件为:多重表文件和倒排文件。
16．二维以上的数组其实是一种特殊的广义表。（ ）
【答案】 √
【解析】广义表是线性表的推广。广义表中的元素还有可能是广义表。对于维数大于二的数
组，它在某一维上的元素还是数组。符合广义表的定义，因此二维以上的数组其实是一种特殊的广义表。
17．栈和队列都是限制存取点的线性结构。（ ）
【答案】 √
18．哈希表的平均查找长度与处理冲突的方法无关。（ ）
【答案】×
【解析】常见的处理冲突的方法:开放地址法；再哈希法；链地址法；建立一个公共的溢出区。选取不同的处理冲突的方法，哈希表的平均查找长度可能不同。
19．完全二叉树肯定是平衡二叉树。（ ）
【答案】×
【解析】从平衡因子定义看，完全二叉树任一结点的平衡因子的绝对值确实是小于等于1。但是，平衡二叉树本质上是二叉排序树，完全二叉树不一定是排序树。故不能说完全二叉树是平衡二叉树。
20．串长度是指串中不同字符的个数。（ ）
【答案】 ×
【解析】不是，串长度是指串中字符的总个数。需要注意的是，在计算字符串的长度时，不要漏掉了空格。
三、算法设计题
21．编写算法，将自然数1〜n 2按“蛇形”填nxn 矩阵中。例(1〜42) 如图所示(用程序实现) 。
图
【答案】算法如下:
//将自然数，按" 蛇形M 填入n 阶方阵A 中
//i，j 是矩阵元素的下标，k 是要填入的自然数
//从右上向左下填数