2018年扬州大学信息工程学院834软件基础之数据结构考研核心题库
● 摘要
一、单项选择题
1． ARP 协议的功能是（ ）。
A. 根据IP 地址查询MAC 地址
B. 根据MAC 地址查询IP 地址
C. 根据域名查询IP 地址
D. 根据IP 地址查询域名
【答案】A 。
【解析】ARP 协议是网络层协议, 因此只能和传输层和数据链路层有关系, 从这一点出发, 域名是应用层的范畴, 选项C 和D 是不正确的, 根据MAC 地址查询IP 地址是RARP 协议的功能, 因此进而得出正确答案是A 。
2． 循环两列放在一维数组中, end1指向队头元素, end2指向队尾元素的后一个位置。假设队列两端均可进行入队和出队操作, 队列中最多能容纳M-1个元素。初始时为空, 下列判断队空和队满的条件中, 正确的是（ ）
A. 队空:endl==end2; 队满:endl==(end2+l)modM
B. 队空Gendl==end2; 队满:Gend2==(endl+1)mod(M-1)
C. 队空Gend2==(endl+1)modM; 队满:Gendl==(end2+l)modM
D. 队空:
【答案】A
【解析】在循环队列中, 在少用一个元素空间的前提下, 可约定入队前, 测试尾指针在循环意义下加1后是否等于头指针, 若相等, 则队满。而队空的条件还是首尾指针是否相等。
3． 线性表的顺序存储结构是一种（ ）。
A. 随机存取的存储结构
B. 顺序存取的存储结构
C. 索引存取的存储结构
D.Hash 存取的存储结构
【答案】A
【解析】线性表包括顺序存储结构和链式存储结构，顺序存储结构能够随机存取表中的元素，但插入和删除操作较麻烦，链式存储结构不能随机访问表中的元素，但是能够表示元素之间的先后次序，而且插入和删除操作较容易。
第 2 页，共 45 页 队满:
4． 在一株高度为2的5阶B 树中, 所含关键字的个数最少是（ ）
A.5
B.7
C.8
D.14
【答案】A
【解析】根据B 树的定义可知, 跟结点最少含有max(2, (m-1))个关键字, 高度为2的阶B 树最少有(5-1)+1=5个关键字, 其中根节点含有(5-1)个关键字, 第2层结点含有1个关键字。
5． 某字长为8位的计算机中, 已知整型变量x 、y 的机器数分别为
, A.11000000
B.00100100
C.10101010
D. 溢出
【答案】A
【解析】将x 左移一位, y 右移一位, 两个数的补码相加的机器数为11000000, 故答案选择A 。
6． 一个具有1025个结点的二叉树的高h 为（ ）。
A.11
B.10
C.11至1025之间
D.10至1024之间
【答案】C
【解析】当一棵树是完全二叉树时，其高度最低，此时高度为11，当一棵树的结点在一条线上时，此时最高，这时二叉树的高度是1025。
7． 某系统正在执行三个进程P1、P2和P3, 各进程的计算(CPUCPUCPU)时间和
如下表所示。
。若整型变量, 则z 的机器数为（ ） 时间比例
为提高系统资源利用率, 合理的进程优先级设置应（ ） A. B. C. D.
【答案】B
【解析】为了合理地设置进程优先级, 应该将进程的CPU 利用时间和
第 3 页，共 45 页 时间做综合考虑, 故
答案选B 。
8． 若对如下的二叉树进行中序线索化, 则结点x 的左、右线索指向的结点分别是（ ）
A.e , c
B.e , a
C.d , c
D.b , a
【答案】D
【解析】此二叉树的中序遍历序列为:debxac , 由于节点x 左右孩子都为空, 所有进行中序线索化时, 它的左右孩子指针分别指向它的中序遍历序列的直接前驱结点b 和直接后继结点a , 所以选D
9． 无向图G=(V，E) ，其中:
，
对该图进行深度优先遍历，得到的顶点序列正确的是（ ）。
A.a , b , e , c , d , f
B.a , c , f , e , b , d
C.a , e , b , c , f , d
D.a , e , d , f , c , b
【答案】D
【解析】图的深度优先遍历过程是:从图中某个初始顸点v 出发，首先访问初始顶点v ，然后选择一个与顶点V 相邻且没被访问过的顶点U 为初始顶点。再从U 出发进行深度优先搜索，直到图中与当前顶点V 邻接的所有顶点都被访问过为止。
根据
关系。依据
上面的原则遍历，得出遍历顺序a ，e ，d ，f ，c ，b 。
第 4 页，共 45 页 可知各顶点之间的邻接