2017年北京联合大学软件工程803软件基础之数据结构考研题库
● 摘要
一、填空题
1． 如果按关键码值递増的顺序依次将关键码值插入到二叉排序树中，则对这样的二叉排序树检索时，平均比较次数为_____。
【答案】
【解析】如果关键码是排好序的，构建二叉排序树就会形成一个单支树，它的查找效率和顺 序查找效率一样为
2． 属于不稳定排序的有_____。
【答案】希尔排序、简单选择排序、快速排序、堆排序等
3． 应用prim 算法求解连通网络的最小生成树问题。
（1）针对如图所示的连通网络，试按如下格式给出在构造最小生成树过程中顺序选出的各条边。
〔始顶点号，终顶点号，权值）
（2）下面是Prim 算法的实现，中间有5个地方缺失，请阅读程序后将它们补上。
的值在〈limits •h>中
//图的顶点数，应由用户定义
//用二维数组作为邻接矩阵表示
//生成树的边结点
//边的起点与终点
//边上的权值
//最小生成树定义
//从顶点rt 出发构造图G 的最小生成树T ，rt 成为树的根结点
//初始化最小生成树
T
//依次求MST 的候选边
//遍历当前候选边集合
//选具有最小权值的候选边
//图不连通，出错处理
//修改候选边集合
【答案】（1）（0，3，1）; （3，5, 4）; （5，2，2）; （3，1, 5）; （1，4，3） （2）①T[k]; tovex=i②min=Maxint③mispos=i④exit （O ）⑤T[i]; fromvex=v
【解析】Prim 算法的执行类似于寻找图的最短路径的Dijkstra 算法。假设N={V，E}是连通图
，是N
上最小生成树边的集合。算法从属于
为止。
4． 克鲁斯卡尔算法的时间复杂度为_____，它对_____图较为适合。
【答案】O （eloge ）; 边稀疏
5． VSAM 系统是由_____、_____、_____构成的。
【答案】索引集；顺序集；数据集
6． 在循环队列中，队列长度为n ，存储位置从0到，
【答案】
7． 在哈希函数
中，P 值最好取_____。
编号，以rear 指示实际的队尾元素，现
E T 开始，重复执行下述操作：在所有u
属于
加入集合
同时将
并入
v
直到
的边（u ，v ）属于E
中找一条代价最小的边
要在此队列中插入一个新元素，新元素的位置是（ ）。
【答案】小于等于表长的最大素数或不包含小于20的质因子的合数
【解析】在使用除留余数法时，对除数P 的选择很重要。若P 选的不好，容易产生同义词。一般情况下，可以选P 为质数或不包含小于20的质因素的合数。
8． 实现字符串拷贝的函数strcpy 为：
【答案】
9． —棵左子树为空的二叉树在前序线索化后，其中的空链域的个数为 _____。
【答案】2
【解析】只有根结点的做指针为空和最右边的叶结点的右指针为空。
10．顺序查找n 个元素的顺序表，若查找成功，则比较关键字的次数最多为_____次；当使用监视哨时，若查找失败，则比较关键字的次数为_____。
【答案】视哨。
【解析】最多的情况就是把整个表遍历了一遍。使用监视哨时，需要多一个存储空间来存监
二、选择题
11．下列有关总线定时的叙述中，错误的是（ ）。
A. 异步通信方式中，全互锁协议最慢 B. 异步通信方式中，非互锁协议的可靠性最差 C. 同步通信方式中，同步时钟信号可由多设备提供 D. 半同步通信方式中，握手信号的采样由同步时钟控制 【答案】C
【解析】A 项正确，异步通信方式中，全互锁协议最慢，主从模块都需要等待确认后才能撤销其信号；B 项正确，异步通信方式中，非互锁协议没有相互确认机制，因此可靠性最差；C 项错误，同步通信要遵循统一的时钟信号，不能由多设备提供；D 项正确，半同步通信方式中，握手信号的采样由同步时钟控制。
12．n 个结点的正则二叉树中有每个结点的度或者为0或者为2的二叉树称为正则二叉树。（ ）个叶子。
【答案】D
【解析】二叉树结点总数
分别代表度为0，度为1，度为2的结点数）。
又在非空二叉树中
：且本题所给树为正则二叉树
，所
以因
此
13．某计算机主存容量为64KB , 其中ROM 区为4KB , 其余为RAM 区，按字节编址。现要用2Kx8位的ROM 芯片和4Kx4位的RAM 芯片来设计该存储器，则需要上述规格的ROM 芯片数和RAM 芯片数分别是（ ）。
A.1、15 B.2、15