2017年太原科技大学交通与物流学院828数据结构考研导师圈点必考题汇编
● 摘要
一、选择题
1． 数组通常具有的两种基本操作是（ ）。
A. 查找和修改 B. 查找和索引 C. 索引和修改 D. 建立和删除 【答案】A
【解析】数组中的元素是顺序存放的，通过下标可以很好地查找数组元素，同时通过对应的指针可以修改数组元素的值，因此数组通常具有的两种基本操作是查找和修改。根据数组的性质，数组通常具有的两种基本运算是排序和查找。
2． 单处理机系统中，可并行的是（ ）。
I. 进程与进程 II. 处理机与设备 III. 处理机与通道 IV . 设备与设备 A.I 、II 和III B.I 、II 和IV C.I 、III 和IV D.II 、III 和IV 【答案】D
【解析】注意区分并发和并行。在单处理机系统中，进程只能并发。微观上同一时刻占用处理机的进程只有一个，因此，进程之间不是并行的。通道是独立于CPU 控制的输入/输出的设备，处理机与通道两者是可以并行。显然，设备和设备之间也是可以并行的。
3． ARP 协议的功能是（ ）。
A. 根据IP 地址查询MAC 地址 B. 根据MAC 地址查询IP 地址 C. 根据域名查询IP ±也址 D. 根据IP 地址查询域名 【答案】A 。
【解析】ARP 协议是网络层协议，因此只能和传输层和数据链路层有关系，从这一点出发，
域名是应用层的范畴，选项C 和D 是不正确的，根据MAC 地址查询IP 地址是RARP 协议的功能，因此进而得出正确答案是A 。
4． 下列介质访问控制方法中，可能发生冲突的是（ ）
A.CDMA B.CSMA C.TDM AC D.FDMA 【答案】B
【解析】介质访向控制协议中能够发生冲突的是CSMA 协议，答案为B 。
5． float 型整数据常用IEEE754单精度浮点格式表示，假设两个float 型变量x 和y 分别在32为寄存器
和中，若
A. B. C. D.
且符号相同
且符号不同
且符号相同
且符号不同
则x 和y 之间的关系为：（ ）
【答案】A
【解析】两个数对应的IEEE754的标准形式为；
将IEEE754单精度形式的二进制转化为浮点数公式为由于
的符号位都是1, 所以fl ，f2符号相同，而阶码上
所以fl 的绝对
值比f2大，而他们都是负数，所以所以选A
6． 对给定的关键字序列110, 119, 007, 911，114，120, 122进行基数排序，则第2趟分配收集后得到的关键字序列是（ ）
A. B. C. D.
【答案】C
【解析】基数排序的第1趟排序是按照个位数字来排序的，第2趟排序是按然十位数字的大小进行排序的，故答案是C 选项。
7． 采用简单选择排序，比较次数与移动次数分别为（ ）。
【答案】C
【解析】简单选择排序只在要交换的时候交换位置，及移动位置，共需移动n 次。而需要比 较的次数为
8． 已知两个长度分别为m 和n 的升序链表，若将它们合并为一个长度为m+n的降序链表，则最坏情况下的时间复杂度是（ ）
A.
B.
C.
D. 【答案】D
【解析】m 和n 是两个升序链表长度分别为m 和n ，在合并过程中最坏的情况是两个链表中的元素依次进行比较，比较的次数是m 和n 中的最大值。
9． 假定有k 个关键字互为同义词，若用线性探测法把这k 个关键字存入哈希表中，至少要进行多少次探测？（ ）
【答案】D
【解析】至少探测次数
10．设二维数组
在一维数组B 中的下标为（ ）。
【答案】A 【解析】
前
的元素个数为
所以二维数组元素
在一维数组B
中的下标为
需要注意数组B 的下标是从0开始，还是从1开始。
（即m 行n 列）按行存储在数组
中，
则二维数组元素
二、判断题
11．顺序存储方式的优点是存储密度大，且插入、删除运算效率高。（ ）
【答案】
【解析】前者正确，后者错误。顺序存储方式在插入、删除元素时需要挪动大量的元素，执行效率较低。
12．取线性表的第i 个元素的时间同i 的大小有关。（ ）
【答案】
【解析】不一定，如果是顺序存储结构，它访问数据元素时的时间效率都是0（1）。
13．折半查找与二元查找树的时间性能在最坏的情况下是相同的。（ ）
【答案】×
【解析】不是，当二元查找树是一棵单支树时，时间性能是
而折半查找依然是
相关内容
相关标签