2017年北方民族大学计算机软件与理论832C语言程序设计与数据结构之数据结构考研题库
● 摘要
一、填空题
1． 在二叉树中，指针p 所指结点为叶结点的条件是_____。 【答案】
【解析】叶子节点的左右孩子都不存在。
2． 检索是为了在文件中寻找满足一定条件的记录而设置的操作。检索可以按_____检索。也可以按_____检索；按_____检索又可以有_____检索和_____检索。
【答案】关键字；记录号；记录号；顺序；直接
3． 模式串的next 函数值序列为_____。
【答案】01122312
4． 有向图G=（V ，E ）, 其中V （G ）=[0, 1，2，3，4, 5}, 用
【答案】50; 4
5． 在有n 个顶点的有向图中，每个顶点的度最大可达。
【答案】2（n-l ）
【解析】当有向图为完全连通图时每个顶点的度达到最大，出度入度均为n-1。
6． 文件可按其记录的类型不同而分成两类，即_____和_____文件。
【答案】操作系统文件；数据库
7． 下面描述的是一种构造最小生成树算法的基本思想。设要处理的无向图包括n
个顶点
用相邻矩阵A 表示，边的权全是正数。请在下列划线处填上正确叙述。
（1）若是边，则的值等于_____，若不是边，则的值是一个比任何边的权，矩阵的对角线元素全为0。
（2）构造最小生成树过程中，若顶点Vi 已包括进生成树，就把相邻矩阵的对角线元素A （i , i ）置成若
【答案】（1） 已包括进生成树，就把矩阵元素A （i ，j ）置成 边上的权值；都大的数；（2）1; 负值；（3）为负；边
第 2 页，共 39 页 （3）算法结束时，相邻矩阵中。
8． 抽象数据类型的定义仅取决于它的一组_____，而与_____无关, 即不论其内部结构如何变化，只要它的_____不变，都不影响其外部使用。
【答案】逻辑特性；在计算机内部如何表示和实现；数学特性
9． —棵有个结点的满二叉树有_____个度为1的结点、有_____个分支（非终端）结点和_____个叶子，该满二叉树的深度为_____。 【答案】
或
【解析】满二叉树没有度为1的结点，度为0的结点等于度为2的结点个数+1。
10．设二维数组A 的行和列的下标范围分别为和每个元素占2个单元，按行优先顺序存储，第一个元素的存储起始位置为b ，则存储位置为
【答案】
时，则i=2，j=3。
当其值为处的元素为_____。 【解析】令这个元素的行标为i ，列标为j 。则它的存储位置是二、判断题
11．循环队列也存在空间溢出问题。（ ） 【答案】
【解析】循环队列的存储空间也是有限的，因此也存在空间溢出问题。
12．算法的优劣与算法描述语言无关，但与所用计算机有关。（ ） 【答案】
【解析】算法的优劣和它的时间复杂度和空间复杂度有关，与算法描述语言和所用计算机都无关。
13．为提高排序速度，进行外排序时，必须选用最快的内排序算法。（ ）
【答案】×
【解析】外部排序算法最常用的是多路归并，即将原文件分解成多个能够一次性装人内存的部分，分别把每一部分调入内存完成排序。然后，对已经排序的子文件进行归并排序。
14．设模式串的长度为m , 目标串的长度为n ，当且处理只匹配一次的模式时，朴素的匹配（即子串定位函数）算法所花的时间代价可能会更为节省。（ ） 【答案】
【解析】因为两个字符串的长度几乎相等，因此，在进行相应的匹配时，只需要定位父串的前几位即可。
第 3 页，共 39 页
15．负载因子（装填因子）是哈希表的一个重要参数，它反映哈希表的装满程度。（ ）
【答案】√
【解析】查找过程中需和给定值进行比较的关键字的个数取决于三个因素：哈希函数，处理冲突的方法和哈希表的装填因子。其中装填因子标志哈希表的装满程度。
16．栈和队列都是限制存取点的线性结构。（ ） 【答案】
17．在索引顺序表中，实现分块查找，在等概率查找情况下，其平均查找长度不仅与表中元素个数有关，而且与每块中元素个数有关。（ ）
【答案】√
【解析】在进行分块查找时，首先查找元素在哪一块，然后在确定的块中查找元素，因此，在索引顺序表中，进行分块查找的平均查找长度不仅与表中元素的个数有关，而且与每块中的元素个数有关。
18．数据的逻辑结构是指数据的各数据项之间的逻辑关系。（ ） 【答案】
【解析】数据的逻辑结构是指数据元素之间的逻辑关系。
19． 数组可看成线性结构的一种推广，因此与线性表一样，可以对它进行插入，删除等操作。（ ）
【答案】×
【解析】数组在维数和界偶确定后，其元素个数已经确定，不能进行插入和删除运算。
20．对于有n 个结点的二叉树，其高度为（ ）
【答案】×
【解析】例如n 结点的单枝树，高度就为n 。
三、算法设计题
21．图G 有n 个点，利用从某个源点到其余各点最短路径算法思想，设计一产生G 的最小生成树的算法。
【答案】算法如下：
//利用从源点v0到其余各点的最短路径的思想，产生以邻接矩阵表示的图G 的最小生成树
数组存放生成树
//s数组存放顶点是否找到最短路径
第 4 页，共 39 页 |//初始化, 设顶点信息就是编号
相关内容
相关标签