2018年江苏大学计算机科学与通信工程学院851数据结构之数据结构考研基础五套测试题
● 摘要
一、单项选择题
1． 下列关于图的叙述中, 正确的是（ ）。
Ⅰ. 回路是简单路径
Ⅱ. 存储稀疏图, 用邻接矩阵比邻接表更省空间
Ⅲ. 若有向图中存在拓扑序列, 则该图不存在回路
A. 仅Ⅱ
B. 仅Ⅰ、Ⅱ
C. 仅Ⅲ
D. 仅Ⅰ、Ⅲ
【答案】C
【解析】第一个顶点和最后一个顶点相同的路径称为回路; 序列中顶点不重复出现的路径称为简单路径; 回路显然不是简单路径, 所以选项Ⅰ错误。稀疏图用邻接表表示比邻接矩阵节省存储空间, 稠密图适合用邻接矩阵的存储表示, 所以选项Ⅱ错误。利用拓扑排序算法可以判断图中是否存在回路, 即在拓扑排序输出结束后所余下的顶点都有前驱, 则说明了只得到了部分顶点的拓扑有序序列, 图中存在回路。所以选项Ⅲ正确。
2． 用数组r 存储静态链表，结点的next 域指向后继，工作指针j 指向链中结点，使j 沿链移动的操作为（ ）。
A.j ＝r[j].next
B.j ＝j ＋l
C.j ＝j ﹣＞next
D.j ＝r[j]﹣＞next
【答案】A
【解析】因为是用数组存储，这里所说的工作指针j 相当于数组的下标，结点是存储一个值域和next 域，next 域就是存放下一个结点的下表，所以只要将next 域中的值赋给j 就可以实现j 沿链移动。
3． 若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（ ）存储方式最节省时间。
A. 顺序表
B. 双链表
C. 带头结点的双循环链表
D. 单循环链表
【答案】A
【解析】线性表采用顺序表，便于进行存取任一指定序号的元素；线性表采用链表，便于进
行插入和删除操作。但该题是在最后进行插入和删除运算，所以利用顺序表存储方式最节省时间。
4． 使用浏览器访问某大学Web 网站主页时, 不可能使用的协议是（ ）
A.PPP
B.ARP
C.UDP
D.SMTP
【答案】D
【解析】SMTP 是简单邮件传输协议, 访问主页时并不涉及邮件相关协议。
5． 下列选项中, 会导致用户进程从态切换到内核的操作是（ ）
Ⅰ. 整数除以零
Ⅱ.sin （ ）函数调用
Ⅲ.read 系统调用
A. 仅Ⅰ、Ⅱ
B. 仅Ⅰ、Ⅲ
C. 仅Ⅱ、Ⅲ
D. Ⅰ、Ⅱ和Ⅲ
【答案】B
【解析】对于Ⅰ, 系统发生异常, 需要进入内核态由操作系统进行处理, 而read 系统调用函数也是在内核态执行, sin （ ）就是普通的用户函数, 在用户态执行, 故答案为C 。
6． 下列关于最小生成树的叙述中, 正确的是（ ）。
Ⅰ. 最小生成树的代价唯一
Ⅱ. 所有权值最小的边一定会出现在所有的最小生成树中
Ⅲ. 使用普里姆(Prim)算法从不同顶点开始得到的最小生成树一定相同
IV. 使用普里姆算法和克鲁斯卡尔(Kmskal)算法得到的最小生成树总不相同
A. 仅Ⅰ
B. 仅Ⅱ
C. 仅Ⅰ、Ⅲ
D. 仅Ⅱ、Ⅳ
【答案】A 。
【解析】当图中存在相同权值的边时, 其最小生成树可能是不唯一的, 但最小生成树的代价一定是相同的, 所以说法Ⅰ正确。从n 个顶点的连通图中选取n-1条权值最小的边可能构成回路, 所以说法Ⅱ错误。
当某个顶点有权值相同的边, 使用普里姆(Prim)算法从不同顶点开始得到的最小生成树并不一定相同, 所以说法Ⅲ错误。当最小生成树不唯一时, 使用普里姆算法和克鲁斯卡尔(Kmskal)算法得到的最小生成树可能相同, 也可能不同, 所以说法Ⅳ错误。由此可得出正确答案。
7． 对于一个线性表既要求能够进行较快速地的插入和删除，又要求存储结构能反映数据之间的逻辑关系，则应该用（ ）。
A. 顺序存储方式
B. 链式存储方式
C. 散列存储方式
D. 以上均可以
【答案】B
8． 某容量为256M 的存储器, 由若干4M*8位的DRAM 芯片构成, 该DRAM 芯片的地址引脚和数据引脚总数是:（ ）
A.19
B.22
C.30
D.36
【答案】A
【解析】DREAM 地址线复用, 4M 为2的22次方, 因此除2为11根, 数据线8根。因此地址引脚和数据引脚总数为19根
9． 下列选项中，不属于网络体系结构中所描述的内容是（ ）.
A. 网络的层次
B. 每一层使用的协议
C. 协议的内部实现细节
D. 每一层必须完成的功能
【答案】C
【解析】体系结构仅规定协议的功能和消息格式，但对具体的实现细节由具体设备厂商来确定，对于网络的层次，以及每一个层次的协议及其功能都是网络体系结构所要描述的内容，因此答案为选项C.
10．某计算机的指令流水线由4个功能段组成，指令流经各功能段的时间(忽略各功能段之间的缓存时间) 分别为90ns 、80ns 、70ns 和60ns ，则该计算机的CPU 时钟周期至少是（ ）.
A.90ns