2017年北京市培养单位北京基因组研究所863计算机学科综合(专业)之数据结构考研强化模拟题
● 摘要
一、填空题
1． 求最短路径的Dijkstra 算法的时间复杂度为_____。 【答案】
2． 二叉树由_____，_____，_____三个基本单元组成。
【答案】根结点；左子树；右子树
3． 二叉树的前序序列和中序序列相同的条件是_____。
【答案】空树或任何结点至多只有右子树的二叉树
【解析】前序遍历的顺序为根左右，中序遍历的顺序为左根右，因此若中序遍历和前序遍历序列相同，则任何结点都没有左子树。
4．
给定一组数据以它构造一棵哈夫曼树，则树高为_____，
带权路径长度
的值为_____。
【答案】5；96
【解析】每次找两个最小的权值构建哈夫曼树：
5． 求图的最小生成树有两种算法，_____算法适合于求稀疏图的最小生成树e
【答案】克鲁斯卡尔
【解析】克鲁斯卡尔算法是一种按权值的递增次序选择合适的边来构造最小生成树的方法，这种算法中，采用堆来存放边的集合，适合于边稀疏而顶点较多的图。
6． 在基于关键字比较且时间为O （nl 〇g2n ）的排序中，若要求排序是稳定的，则可选用_____
，则可选用_____排序。 排序；若要求就地排序（及辅助空间为0（1））
【答案】归并；堆
7． 设二维数组A 的行和列的下标范围分别为【答案】 和每个元素占2个单元，按行优先顺处的元素为_____。 当其值为序存储，第一个元素的存储起始位置为b ，则存储位置为【解析】令这个元素的行标为i ，列标为j 。则它的存储位置是时，则i=2，j=3。
8． 有向图G=（V ，E ）, 其中V （G ）=[0, 1，2，3，4, 5}, 用
【答案】50; 4
9． 检索是为了在文件中寻找满足一定条件的记录而设置的操作。检索可以按_____检索。也可以按_____检索；按_____检索又可以有_____检索和_____检索。
【答案】关键字；记录号；记录号；顺序；直接
10．G 是一个非连通无向图，共有28条边，则该图至少有_____个顶点。
【答案】9
【解析】求该非连通无向图的最少顶点数，则该图为一个孤立的顶点和一个完全连通图。
二、判断题
11．若把堆看成是一棵完全二叉树，则该树一定是一棵二叉排序树。（ ）
【答案】×
【解析】堆中某个节点的值总是不大于或不小于其父节点的值，这个并不是二叉排序树的性质。
12．—棵树中的叶子数一定等于与其对应的二叉树的叶子数。（ ）
【答案】×
【解析】一颗树的叶子树与它对一个的二叉树的叶子树没有直接联系。不妨举例：假设一个有三个结点的二叉树，层数为2。则它的叶结点数为2。将其按规则转为对应的二叉树时，则它的叶结点数为1。
13．队列和栈都是运算受限的线性表，只允许在表的两端进行运算。（ ） 【答案】
【解析】栈只能在一端进行操作，队列可以在表的两端进行运算。
14．即使对不含相同元素的同一输入序列进行两组不同的合法的入栈和出栈组合操作，所得的输出序列也一定相同。（ ） 【答案】
【解析】栈只是一种先入后出的存储结构。对于出栈、入栈的元素不进行修改，因此，输入序列的元素不相同，不可能得到相同的输出序列。
15．归并排序辅助存储为（ ）
【答案】×
【解析】归并排序的辅助存储是
16．取线性表的第i 个元素的时间同i 的大小有关。（ ） 【答案】
【解析】不一定，如果是顺序存储结构，它访问数据元素时的时间效率都是0（1）。
17．若中序遍历平衡的二叉排序树，可得到排好序的关键码序列。（ ）
【答案】√
【解析】二叉排序树对于每一个结点，它的左子树的所有结点的值都小于这个结点的值，而它的右子树的所有结点的值都大于这个结点的值。而采用中序遍历，遍历顺序为左根右，因此可以得到按增序排列的关键码序列。
18．广义表的取表尾运算，其结果通常是个表，但有时也可是个单元素值。（ ）
【答案】×
【解析】广义表的取表尾运算，是非空广义表除去表头元素，剩余元素组成的表，不可能是原子。
19．若一个有向图无环，则它一定有唯一的拓扑序列。（ ）
【答案】×
【解析】有向图无环说明它一定有拓扑序列，但这个拓扑序列不唯一。如果在一个线性有序的序列中，每个顶点有唯一的前驱后继关系，在做拓扑排序时，则排序的结果是唯一的，即它有唯一的拓扑序列。
20．串是一种数据对象和操作都特殊的线性表。（ ） 【答案】
【解析】串是一种操作特殊的线性表，其特殊性主要体现在数据元素是一个字符。在内存中，一份文本都可以看做是一个字符串，而每一行都可以看做是其子串。
三、算法设计题
相关内容
相关标签