2018年北京市培养单位信息工程研究所863计算机学科综合(专业)之数据结构考研核心题库
● 摘要
一、填空题
1． 有五个数据依次入找:1，2，3，4，5。在各种出栈的序列中，以3，4先出栈的序列有_____。(3在4之前出栈)
【答案】3个
【解析】以3，4先出栈的序列有34521、34215、34251共3个。
2． 模式串的next 函数值序列为_____。
【答案】01122312
3． 已知有序表为(12，18，24，35，47，50，62，83，90，115，134) 当用二分法查找90时，需次查找成功，查找47时_____成功，查找100时，需_____次才能确定不成功。
【答案】2; 4; 3
【解析】二分法查找元素次数列表
查找100是找到115就停止了。
4． VSAM 系统是由_____、_____、_____构成的。
【答案】索引集；顺序集；数据集
5． 设为哈夫曼树的叶结点数目，则该哈夫曼树共有_____个结点。 【答案】
【解析】哈夫曼树只有度为0和2的节点。
6． 顺序查找n 个元素的顺序表，若查找成功，则比较关键字的次数最多为_____次；当使用监视哨时，若查找失败，则比较关键字的次数为_____。
【答案】n ; n+1
【解析】最多的情况就是把整个表遍历了一遍。使用监视哨时，需要多一个存储空间来存监视哨。
7． 在图G 的邻接表表示中，每个顶点邻接表中所含的结点数，对于无向图来说等于该顶点的_____; 对于有向图来说等于该顶点的_____。
【答案】度；出度
8． N 个顶点的连通图用邻接矩阵表示时，该矩阵至少有_____个非零元素。 【答案】
【解析】所谓连通图一定指的是无向图，有向图会称作强连通图。连接N 个顶点，至少需要N －1条边就可以了。由于无向图的每一条边同时关联了两个顶点。因此用邻接矩阵表示时，该矩阵至少有2(N－1) 个非零元素。
9． 二叉树由_____，_____，_____三个基本单元组成。
【答案】根结点；左子树；右子树
10．空格串是指_____，其长度等于_____。
【答案】由空格字符(ASCII值32) 所组成的字符串；空格个数
二、判断题
11．负载因子(装填因子) 是哈希表的一个重要参数，它反映哈希表的装满程度。（ ）
【答案】√
【解析】查找过程中需和给定值进行比较的关键字的个数取决于三个因素:哈希函数，处理冲突的方法和哈希表的装填因子。其中装填因子标志哈希表的装满程度。
12．数据的逻辑结构是指数据的各数据项之间的逻辑关系。（ ）
【答案】X
【解析】数据的逻辑结构是指数据元素之间的逻辑关系。
13．在外部排序过程中，对长度为n 的初始序列进行“置换-选择”排序时，可以得到的最大初始有序段的长度不超过n/2。（ ）
【答案】×
【解析】当输入文件以关键字的升序排序时，只能得到一个长度为文件长度的初始归并段
14．中序遍历一棵二叉排序树的结点就可得到排好序的结点序列。（ ）
【答案】 √
【解析】二叉排序树是的父结点和左右子树的值的大小是确定的。
15．十字链表是无向图的一种存储结构。（ ）
【答案】×
【解析】十字链表是有向图的另一种链式存储结构。在十字链表中，对应于有向图的每条弧有一个结点，对应于每个顶点也有一个结点。类似于邻接表是无向图的一种链式存储结构。
16．倒排序文件的优点是维护简单。（ ）
【答案】×
【解析】倒排文件的优点是检索记录较快。特别是对某些询问，不用读取记录，就可得到解答。
17．循环队列也存在空间溢出问题。（ ）
【答案】 √
【解析】循环队列的存储空间也是有限的，因此也存在空间溢出问题。
18．连通图上各边权值均不相同，则该图的最小生成树是唯一的。（ ）
【答案】√
【解析】由最小生成树的构建过程知，在确定根结点之后，因为连通图上各边权值均不相同，下一个结点的选择是唯一的，所以该图的最小生成树是唯一的。
19．无环有向图才能进行拓扑排序。（ ）
【答案】√
【解析】在图论中，由一个有向无环图的顶点组成的序列，才能进行拓扑排序。
20．强连通分量是无向图的极大强连通子图。（ ）
【答案】×
【解析】强连通分量是对有向图而言的，一般在无向图中讨论连通性。
三、算法设计题
21．假设以双亲表示法作树的存储结构，写出双亲表示的类型说明，并编写求给定的树的深度的算法(注:已知树中的结点数) 。
【答案】算法如下:
求以双亲表示法作为存储结构的树的深度
深度加1, 并取新的双亲
最大深度更新
返回树的深度
’结束Depth
相关内容
相关标签