2018年河北科技大学信息科学与工程学院841数据结构考研强化五套模拟题
● 摘要
一、填空题
1． 已知如下程序段:
语句1执行的时间复杂度为_____:语句2执行的时间复杂度为_____:语句3执行的时间复杂度为_____:语句4执行的时间复杂度为_____。
【答案】(1)n＋1 (2)n
(3)n(n＋3)/2 (4)n(n＋l)/2
【解析】语s 句1执行到不符合条件情况下，执行了n ＋1次。当语句1不符合条件了是不会执行语句2的，所以语句2被执行了n 次。语句3每次都要执行到不符合条件，故为2＋3＋4...... ＋(n＋l) 加起来就是n(n＋3)/2。语句3不符合条件了是不会执行语句4的。所以语句4被执行了1＋2＋3...... ＋n 即n(n＋l)/2。
2． n 个顶点的有向图用邻接矩阵array 表示，下面是其拓扑排序算法，试补充完整。
注:(1)图的顶点号从0开始计；
(2)indegree是有n 个分量的一维数组，放顶点的入度， (3)函数crein 用于记算顶点入度； (4)有三个函数回1，否则0) 。
第 2 页，共 37 页
其含义为数据data 入栈，出栈和测试栈是否空(不空返
("图有回路") ;
【答案】
【解析】有向图用邻接矩阵表示时，顶点i 的入度等于第i 列的所有元素之和。拓扑排序过程:首先将入度为0的顶点全部进栈。然后弹出栈顶结点，并将与弹出的顶点相连的其它顶点的入度 减一，然后判断这些顶点的入度是否为零，如果为零，继续进栈，重复这些操作，完成拓扑排序。
3． 文件由_____组成；记录由_____组成。
【答案】记录；数据项
4． 在哈希函数
中，p 值最好取_____。
【答案】小于等于表长的最大素数或不包含小于20的质因子的合数
【解析】在使用除留余数法时，对除数P 的选择很重要。若P 选的不好，容易产生同义词。一般情况下，可以选P 为质数或不包含小于20的质因素的合数。
5． 假定有k 个关键字互为同义词，若用线性探测再哈希法把这k 个关键字存入哈希表中，至少要进行_____次探测。
【答案】
【解析】当该关键字发生冲突时，用线性探测不会遇到别的关键字冲突，这个时候需要探测的次数最小。总次数为。
6． 如果按关键码值递增的顺序依次将关键码值插入到二叉排序树中，则对这样的二叉排序树检索时，平均比较次数为_____。
【答案】序查找效率一样为
。
【解析】如果关键码是排好序的，构建二叉排序树就会形成一个单支树，它的查找效率和顺
二、单项选择题
7． 设有一棵3阶B 树, 如下图所示。删除关键字78得到一棵新B 树, 其最右叶结点所含的关键字是（ ）。
图 3二叉树图
第 3 页，共 37 页
A.60 B.60, 62 C.62, 65 D.65 【答案】D 。
【解析】本题主要考查B 树删除操作。即被删关键字所在的结点中的关键字个数等于而与该结点相邻的右兄弟(或左兄弟) 结点中的关键字数目大于
(或最大) 的关键字上移至双亲结点中, 而将双亲结点中小于(或大于) 且紧靠该上移关键字的关键字下移至被删关键字所在结点中。题目中删除关键字78得到一棵新B 树如下, 其最右叶结点所含的关键字是65。
,
, 则需将其兄弟结点中最小
8． 设有数组A[i，j]，数组的每个元素长度为3字节，i 的值为1到8，j 的值为1到10，数组从内存首地址BA 开始顺序存放，当用以列为主存放时，元素A[5，8]的存储首地址为（ ）。
A.BA+141 B.BA+180 C.BA+222 D.BA+225 【答案】B
【解析】在计算中，可以考虑按照列存放时，A[5，8]在内存的位置，比较容易计算元素的首地址。比如A[5，8]顺序存放时，它是第7*8＋5＝61个元素，由于首地址为BA ，所以它的存储首地址为BA ＋(61﹣1)*3＝180+BA。
9． 在一个采用CSMA/CD协议的网络中，传输介质是一根完整的电缆，传输速率为1Gbps ，电缆中的信号传播速度是200000km/s.若最小数据帧长度减少800bit ，则最远的两个站点之间的距离至少需要（ ）.
A. 增加160m B. 增加80m C. 减少160m D. 减少80m 【答案】D
【解析】以太网采用CSMA/CD访问协议，在发送的同时要进行冲突检测，这就要求在能检测出冲突的最大时间内数据包不能够发送完毕，否则冲突检测不能有效地工作。所以，当发送的数据包太短时必须进行填充。最小帧长度＝碰撞窗口大小×报文发送速率，本题最小数据帧长度
89
减少800b , 那么碰撞的窗口也要减少，因此距离也要减少，从而(800×2×l0)/(l×l0) ＝160m ，由于
第 4 页，共 37 页
相关内容
相关标签