2016年陕西科技大学理学院902数据结构(同等学力加试)考研复试题库
● 摘要
一、选择题
1． 对任意一棵树，设它有n 个结点，这n 个结点的度数之和为（ ）。
A.n B. C. D.
答:C
【解析】每个结点（除根节点外）都是一个分支，即所有结点的度数之和等于分支个数等于总的结点数减一，即n-1。
2． 已知两个长度分别为m 和n 的升序链表，若将它们合并为一个长度为m+n的降序链表，则最坏情况下的时间复杂度是（ ） A. B. C. D.
答:D
【解析】m 和n 是两个升序链表长度分别为m 和n ，在合并过程中最坏的情况是两个链表中的元素依次进行比较，比较的次数是m 和n 中的最大值。
3． 图G 是n 个顶点的无向完全图，则下列说法不正确的是（ ）
A.G 的邻接多重表需要n （n-l ）个边结点和n 个顶点结点
B.G 的连通分量个数最少
C.G 为连通图
D.G 所有顶点的度的总和为n （n-1）
答:A
【解析】A 项中G 的邻接多重表中需要n （n-l ）/2个边结点和n 个顶点结点。此时连通分量最少为1。无向完全图中任意两个顶点之间都存在路径，则G 必为连通图。每个顶点的度为n-1，则n 个结点的度的总和为n （n-l ）。
4． ARP 协议的功能是（ ）。
A. 根据IP 地址查询MAC 地址
B. 根据MAC 地址查询IP 地址
C. 根据域名查询IP ±也址
D. 根据IP 地址查询域名
答:A 。
【解析】ARP 协议是网络层协议，因此只能和传输层和数据链路层有关系，从这一点出发，域名是应用层的范畴，选项C 和D 是不正确的，根据MAC 地址查询IP 地址是RARP 协议的功能，因此进而得出正确答案是A 。
5． 若用一个大小为6的数组来实现循环队列，且当前rear 和front 的值分别为0和3, 当从队列中删除一个元素，再加入两个元素后，rear ，front 的值分别为多少？（ ）
A.1和5
B.2和4
C.4和2
D.5和1
答:B
【解析】入队操作的主要步骤
：
个后
，
6． 在OSI 参考模型中，直接为会话层提供服务的是（ ）
A. 应用层
B. 表示层
C. 传输层
D. 网络层
答:C
【解析】OSI 参考模型中，下层直接为上层提供服务，而会话层的下层为传输层。
7． 已知一算术表达式的中缀表达式为其后缀形式为（ ）。
答:D
【解析】后缀表达式：在程序语言中，运算符位于两个操作数后面的表达式。
8． 在含有n 个关键字的小根堆（堆顶元素最小）中，关键字最大的记录有可能存储在（ ）位置上。
答:D
【解析】小根堆中，关键字最大的记录只能在叶结点上，故不可能在小于等于
上。
的结点加入一个后，再加入一删除一个后
，出队操作的主要步骤
：