2018年西安工业大学光电学院807数据结构与程序设计之数据结构考研核心题库
● 摘要
一、单项选择题
1． 在一个有N 个元素的有序单链表中查找具有给定关键字的结点，平均情况下的时间复杂性为（ ）。
A.O(1)
B.O(N)
C.O(N2) D.
【答案】B
【解析】二分查找的时间复杂度为。在一个用N 个元素的有序单链表中查找具有给定
关键字的结点，因为查找是从头结点开始的，需要使用指针顺序往下查找，因此时间复杂度为0(N)。
2． 已知循环队列存储在一维数组中, 且队列非空时front 和rear 分别指向队头元素和队尾元素。若初始时队列为空, 且要求第1个进入队列的元素存储在
的值分别是（ ）。
A.0, 0
B.0, n-1
C.n-1, 0
D.n-1, n-1
【答案】B
【解析】题目要求队列非空时front 和rear 分别指向队头元素和队尾元素, 若初始时队列为空, 且要求第1个进入队列的元素存储在A[0]处, 则此时front 和rear 的值都为0。由于进队操作要执
行
3． 求整数, 则初始时front 的值为0、rear 的值为n-1。 阶乘的算法如下, 其时间复杂度是（ ）。
处, 则初始时front 和rear
A.
B.0(n) C. 2D.O(n)
【答案】B 。
【解析】设fact(n)的运行时间函数是T(n)。
该函数中语句①的运行时间是0(1), 语句②的运行时间是
算的时间。
因此, 当
则,
时
, ; 。
即fact(n)的时间复杂度为O(n)。
当11>1时, , 其中O(1)为乘法运
通过上表可以看出, 显然转换过程中同时保存在栈中的操作符的最大个数是5。
4． 下列关于UDP 协议的叙述中, 正确的是（ ）
Ⅰ提供无连接服务
Ⅱ提供复用/分用服务
Ⅲ通过差错校验, 保障可靠数据传输
A. 仅Ⅰ
B. 仅Ⅰ、Ⅱ
C. 仅Ⅱ、Ⅲ
D. Ⅰ、Ⅱ、Ⅲ
【答案】B
UDP 无连接创建, 提供多路复用服务。【解析】虽然有差错检验, 但是不能保证可靠数据传输,
所以Ⅲ错误。
5． ARP 协议的功能是（ ）。
A. 根据IP 地址查询MAC 地址
B. 根据MAC 地址查询IP 地址
C. 根据域名查询IP 地址
D. 根据IP 地址查询域名
【答案】A 。
【解析】ARP 协议是网络层协议, 因此只能和传输层和数据链路层有关系, 从这一点出发, 域名是应用层的范畴, 选项C 和D 是不正确的, 根据MAC 地址查询IP 地址是RARP 协议的功能, 因此进而得出正确答案是A 。
6． 下列关于无向连通图特性的叙述中，正确的是（ ）.
(1)所有的顶点的度之和为偶数
(2)边数大于顶点个数减1
(3)至少有一个顶点的度为1
A. 只有(1)
B. 只有(2)
C. (1)和(2)
D.(1)和(3)
【答案】A
【解析】在图中，
顶点的度之和与边的数目满足关系式：(n为图的总结点数，e 为总边数) ，因此， (1)项正确. 对于(2)、(3)项中的特性不是一般无向连通图的特性，可以轻松地举出反例.“至少有一个顶点的度为1”的反例如下图1所示，“边数大于顶点个数减1”