2018年北京市培养单位空间应用工程与技术中心863计算机学科综合(专业)之数据结构考研仿真模拟五套题
● 摘要
一、填空题
1． 求图的最小生成树有两种算法，_____算法适合于求稀疏图的最小生成树e
【答案】克鲁斯卡尔
【解析】克鲁斯卡尔算法是一种按权值的递增次序选择合适的边来构造最小生成树的方法，这种算法中，采用堆来存放边的集合，适合于边稀疏而顶点较多的图。
2． 设单链表的结点结构为(data，next) ，next 为指针域，已知指针px 指向单链表中data 为x 的结点，指针py 指向data 为y 的新结点，若将结点y 插入结点x 之后，则需要执行以下语句: _____；_____；
【答案】py ﹣＞next ＝px ﹣＞next ；px ﹣＞next ＝py
3． 堆是一种有用的数据结构。堆排序是一种_____排序，堆实质上是一棵_____结点的层次序列。对含有N 个元素的序列进行排序时，堆排序的时间复杂度是_____，所需的附加存储结点是_____。关键码序列05, 23, 16, 68, 94, 72, 71, 73是否满足堆的险质_____ 。
【答案】选择；完全二叉树；；O(1)；满足堆的性质
4． 文件可按其记录的类型不同而分成两类，即 _____和_____文件。
【答案】操作系统文件；数据库
5． 对n 个元素的序列进行起泡排序时，最少的比较次数是_____。
【答案】n －1
【解析】如果序列是正序，冒泡排序第一次只要进行n －1次比较，发现没有移动元素，说明序列有序。
6． 一个算法具有5个特性: _____、_____、_____、有零个或多个输入、有一个或多个输出。
【答案】有穷性；确定性；可行性
7． 设为哈夫曼树的叶结点数目，则该哈夫曼树共有_____个结点。 【答案】
【解析】哈夫曼树只有度为0和2的节点。
8． 二叉树的前序序列和中序序列相同的条件是_____。
【答案】空树或任何结点至多只有右子树的二叉树
【解析】前序遍历的顺序为根左右，中序遍历的顺序为左根右，因此若中序遍历和前序遍历序列相同，则任何结点都没有左子树。
9． VSAM 系统是由_____、_____、_____构成的。
【答案】索引集；顺序集；数据集
10．如果按关键码值递增的顺序依次将关键码值插入到二叉排序树中，则对这样的二叉排序树检索时，平均比较次数为_____。 【答案】
序查找效率一样为
。 【解析】如果关键码是排好序的，构建二叉排序树就会形成一个单支树，它的查找效率和顺二、判断题
11． 若一个有向图的邻接矩阵对角线以下元素均为零，则该图的拓扑有序序列必定存在。（ ）
【答案】√
【解析】因为一个有向图的邻接矩阵对角线以下元素均为零，则该图是一个有向无环图，所以该图的拓扑有序序列必定存在。
12．归并排序辅助存储为O(1)（ ）
【答案】×
【解析】归并排序的辅助存储是O Cn)o
13．一个广义表可以为其他广义表所共享。（ ）
【答案】 √
【解析】因为广义表中的元素还可能是表，所以对于一个广义表可以为其他广义表所共享。
14．基数分类只适用于以数字为关键字的情况，不适用于以字符串为关键字的情况。（ ）
【答案】×
【解析】如果用字符串为关键字，可以将其中的字符串的每一位用Ascn 码进行比较。
15．顺序存储方式的优点是存储密度大，且插入、删除运算效率高。（ ）
【答案】 ×
【解析】前者正确，后者错误。顺序存储方式在插入、删除元素时需要挪动大量的元素，执行效率较低。
16．在二叉排序树中插入一个新结点，总是插入到叶结点下面。（ ）
【答案】×
【解析】不一定。插入二叉排序树的原则:将新节点元素值与根结点元素值相比较，如小于根结点元素值则插入到左子树口，否则插入到右子树中。所以就可能插在一个度为1的结点下面。
17．哈希表的平均查找长度与处理冲突的方法无关。（ ）
【答案】×
【解析】常见的处理冲突的方法:开放地址法；再哈希法；链地址法；建立一个公共的溢出区。选取不同的处理冲突的方法，哈希表的平均查找长度可能不同。
18．就平均查找长度而言，分块查找最小，折半查找次之，顺序查找最大。（ ）
【答案】×
【解析】折半查找最小，分块查找次之，顺序查找最大。分块查找的速度虽然不如折半查找算法，但比顺序查找算法快得多，同时又不需要对全部节点进行排序。当结点很多且块数很大时，对索引表可以采用折半查找，这样能够进一步提高查找的速度。
19．2，n ，a 2，a n
若…，…，桟的输入序列是1，输出序列是a 1，
（ ）
【答案】 ×
【解析】出找序列不一定满足a 1＞a i+1... ＞a n ，比如1进栈，然后出找，a 1＝1。
20．为提高排序速度，进行外排序时，必须选用最快的内排序算法。（ ）
【答案】×
【解析】外部排序算法最常用的是多路归并，即将原文件分解成多个能够一次性装人内存的部分，分别把每一部分调入内存完成排序。然后，对己经排序的子文件进行归并排序。
。 则有:。
三、算法设计题
21．给出以十字链表作存储结构，建立图的算法，输入(i, j , V) , 其中i , j 为顶点号，v 为权值。
【答案】算法如下:
建立有向图的十字链表存储结构
假定权值为整型
建立顶点向量
当输入i 、j 、v 之一为0时，结
束算法运行
相关内容
相关标签