2018年北京服装学院计算机信息中心917程序设计与算法之数据结构考研核心题库
● 摘要
目录
2018年北京服装学院计算机信息中心917程序设计与算法之数据结构考研核心题库（一） ... 2 2018年北京服装学院计算机信息中心917程序设计与算法之数据结构考研核心题库（二） . 16 2018年北京服装学院计算机信息中心917程序设计与算法之数据结构考研核心题库（三） . 30 2018年北京服装学院计算机信息中心917程序设计与算法之数据结构考研核心题库（四） . 46 2018年北京服装学院计算机信息中心917程序设计与算法之数据结构考研核心题库（五） . 60
第 1 页，共 71 页
一、填空题
1． 设T 和P 是两个给定的串，在T 中寻找等于P 的子串的过程称为_____，又称P 为_____。
【答案】模式匹配；模式串
2． 设有一个10阶对称矩阵A 采用压缩存储方式(以行为主序存储:a 11＝l) ， 则a 85的地址为_____。
【答案】33
【解析】设存储的元素的行标为i ，列标为j 。若i ＞＝j ，则
的地址为l ＋2＋... ＋i ﹣l ＋j
＝i(i﹣l)/2＋j 。若i ＜j 。则的地址为j(j﹣l)/2＋i 。将i ＝8，j ＝5代入得33。
3． 已知一循环队列的存储空间为，其中n ＞m ，队头和队尾指针分别为front 和rear ，则此循环队列判满的条件是_____
【答案】
4． 在哈希函数
中，p 值最好取_____。
【答案】小于等于表长的最大素数或不包含小于20的质因子的合数
【解析】在使用除留余数法时，对除数P 的选择很重要。若P 选的不好，容易产生同义词。一般情况下，可以选P 为质数或不包含小于20的质因素的合数。
5． n 个顶点的有向图用邻接矩阵array 表示，下面是其拓扑排序算法，试补充完整。
注:(1)图的顶点号从0开始计；
(2)indegree是有n 个分量的一维数组，放顶点的入度， (3)函数crein 用于记算顶点入度； (4)有三个函数回1，否则0) 。
第 2 页，共 71 页
其含义为数据data 入栈，出栈和测试栈是否空(不空返
("图有回路") ;
【答案】
【解析】有向图用邻接矩阵表示时，顶点i 的入度等于第i 列的所有元素之和。拓扑排序过程:首先将入度为0的顶点全部进栈。然后弹出栈顶结点，并将与弹出的顶点相连的其它顶点的入度 减一，然后判断这些顶点的入度是否为零，如果为零，继续进栈，重复这些操作，完成拓扑排序。 6． 每一棵树都能唯一地转换为它所对应的二叉树。若已知一棵二叉树的前序序列是BEFCGDH ，中序序列是FEBGCHD ，则它的后序序列是_____。设上述二叉树是由某棵树转换而成，则该树的前序序列是_____
【答案】FEGHDCB ；BEF
【解析】树的前序序列对应二叉树的前序序列，该二叉树转换成森林时含三棵树，其第一棵树的前序是BEF 。
7． 从用户的观点看，文件的逻辑结构通常可以区分为两类:一类是如NdBASE 中数据库文件那样的文件组织结构，称为_____文件; 另一种是诸如用各种文字处理软件编辑成的文本文件，称为_____文件。从文件在存储器上的存放方式来看，文件的物理结构往往可区分为三类，即_____， _____和_____。B+树适用于组织_____的索引结构，m 阶B+树毎个结点至多有_____个儿子，除根结点外每个结点至少有_____个儿子，根结点至少有_____个儿子，有k 个儿子的结点必有_____个关键码。
【答案】数据库；文本；顺序组织；随机组织；链组织；随机组织；m ;
；2；k
8． 对于一个具有n 个结点的单链表，在已知的结点半p 后插入一个新结点的时间. 复杂度为_____，在给定值为x 的结点后插入一个新结点的时间复杂度为_____。
【答案】O(1)；O(n)
【解析】第一种情况只需直接修改指针的指向。第二种情况必须从头结点遍历找到x 的结点。
9． 堆是一种有用的数据结构。堆排序是一种_____排序，堆实质上是一棵_____结点的层次序列。对含有N 个元素的序列进行排序时，堆排序的时间复杂度是_____，所需的附加存储结点是_____。关键码序列05, 23, 16, 68, 94, 72, 71, 73是否满足堆的险质_____ 。
【答案】选择；完全二叉树；
；O(1)；满足堆的性质
10．阅读下列程序说明和程序，填充程序中的_____。
【程序说明】本程序完成将二叉树中左、右孩子交换的操作。交换的结果如下所示。
第 3 页，共 71 页
本程序采用非递归的方法，设立一个堆栈stack 存放还没有转换过的结点，它的栈顶指针为tp 。交换左、右子树的算法为:
(1)把根结点放入堆栈。
(2)当堆栈不空时，取出栈顶元素，交换它的左、右子树，并把它的左、右子树分别入栈。 (3)重复(2)直到堆栈为空时为止。
【答案】
【解析】本题主要使用堆栈完成了二叉树左右子树交换的操作。首先根结点进栈，然后判断栈是否为空，如果不为空，则取栈顶元素，交换取出结点的左右指针。并将左右指针分别进栈，重复这一操作。完成二叉树左右孩子的交换。
11．在n 个顶点的非空无向图中，最多有_____个连通分量。
【答案】n
【解析】当n 个顶点之间没有边，都是孤立的顶点时，有n 个连通分量。
12．假定有k 个关键字互为同义词，若用线性探测再哈希法把这k 个关键字存入哈希表中，至少要进行_____次探测。
【答案】的次数最小。总次数为
。
【解析】当该关键字发生冲突时，用线性探测不会遇到别的关键字冲突，这个时候需要探测
二、单项选择题
13．对任意一棵树，设它有n 个结点，这n 个结点的度数之和为（ ）。
A.n B.n ﹣2
C.n ﹣1 D.n ＋1 【答案】c
【解析】每个结点(除根节点外) 都是一个分支，即所有结点的度数之和等于分支个数等于总
第 4 页，共 71 页
相关内容
相关标签