2018年东南大学学习科学中心935计算机专业基础之数据结构考研强化五套模拟题
● 摘要
目录
2018年东南大学学习科学中心935计算机专业基础之数据结构考研强化五套模拟题（一） ... 2 2018年东南大学学习科学中心935计算机专业基础之数据结构考研强化五套模拟题（二） . 12 2018年东南大学学习科学中心935计算机专业基础之数据结构考研强化五套模拟题（三） . 23 2018年东南大学学习科学中心935计算机专业基础之数据结构考研强化五套模拟题（四） . 34 2018年东南大学学习科学中心935计算机专业基础之数据结构考研强化五套模拟题（五） . 43
第 1 页，共 53 页
一、单项选择题
1． 在文件的索引节点中存放直接索引指针10个, 一级二级索引指针各1个, 磁盘块大小为1KB 。每个索引指针占4个字节。若某个文件的索引节点已在内存中, 到把该文件的偏移量(按字节编址) 为1234和307400处所在的磁盘块读入内存。需访问的磁盘块个数分别是（ ）。
A.1, 2
B.1, 3
C.2, 3
D.2, 4
【答案】B
【解析】文件的索引结点的直接索引指针有10个, 因此直接索引的偏移量范围是0〜2559, 一级索引的偏移量范围是2560〜65791, 二级索引访问的偏移量范围是65792〜45183907。偏移量1234可以通过直接索引得到在磁盘块的地址, 因此需要一次访问, 307400需要通过二级索引查找其在磁盘的位置, 需要分别访问存放二级索引的两个索引块以及对应的数据块。
2． 假定主存地址为32位, 按字节编址, 主存和Cache 之间采用直接映射方式, 主存块大小为4个字, 每字32位, 采用回写(Write Back) 方式, 则能存放4K 字数据的Cache 的总容量的位数至少是（ ）。
A.146k
B.147K
C.148K
D.158K
【答案】B
【解析】Cache 和主存直接映射方式的规则为:主存储器分为若干区, 每个区与缓存容量相同; 每个区分为若干数据块, 每个块和缓存块容量相同; 主存中某块只能映象到Cache 的一个特定的块中。本题中, Cache 总共存放4K 字数据, 块大小为4个字, 因此cache 被分为
要包含所存的数据4个字, 每个字32位, 18位标记位和一个有效位, 因此总容量为:
。
3． 程序P 在机器M 上的执行时间是20秒, 编译优化后, P 执行的指令数减少到原来的70%而CPI 增加到原来的
A. 秒
第 2 页，共 53 页 个块, 由10位表示。块内共16字节, 所以由4位表示, 于是标记位为32-10-14=18位。所以, Cache 的每一行需倍, 则P 在M 上的执行时间是（ ）
B.
D. 秒 秒 C.14秒 【答案】D 【解析】
4． 在系统总线的数据线上, 不可能传输的是（ ）。
A. 指令
B. 操作数
C. 握手(应答) 信号
D. 中断类型号型号
【答案】C
【解析】握手(应答) 信号属于通信联络控制信号应该在通信总线上传输, 不可能在数据总线上传输。而指令、操作数和中断类型码都可以在数据线上传输。
5． 采用简单选择排序，比较次数与移动次数分别为（ ）。 A. B. C. D.
【答案】C
【解析】简单选择排序只在要交换的时候交换位置，及移动位置，共需移动n 次。而需要比较的次数为、
6． 用不带头结点的单链表存储队列，其队头指针指向队头结点，队尾指针指向队尾结点，则在进行出队操作时（ ）。
A. 仅修改队头指针
B. 仅修改队尾指针
C. 队头、队尾指针都可能要修改
D. 队头、队尾指针都要修改
【答案】C
【解析】用不带头结点的单链表存储队列，一般删除操作仅修改队头指针，但当队列中只有一个结点时，进行删除操作要将队头、队尾指针都修改成NULL 。
7． 假定编译器将赋值语句“x=x+3; ”转换为指令”add xaddt, 3”, 其中xaddt 是x 对应的存储单元地址, 若执行该指令的计算机采用页式虚拟存储管理方式, 并配有相应的TLB , 且Cache 使用直写(Write Through)方式, 则完成该指令功能需要访问主存的次数至少是（ ）。
A.0
第 3 页，共 53 页
B.1
C.2
D.3
【答案】C
【解析】采用页式虚拟存储管理方式时, 若页表全部放在内存中, 则存取一个数据最少要访问两次内存:第一次是访问页表, 得到所存取的数据或指令的物理地址; 第二次根据该地址存取数据或指令。在配有TLB 的页式虚拟管理方式中, 如果给出的地址在TLB 中, 则直接根据该地址取数据或指令, 仅需要一次访问内存。Cache 使用直写方式时, 计算完需要将数据写回到内存中, 因此完成整个指令功能至少需要访问主存2次。
8． 对有2个顶点e 条边且使用邻接表存储的有向图进行广度优先遍历, 其算法时间复杂度是（ ）。 A. B. C. D.
【答案】C 。
【解析】遍历图的过程实质上是对每个顶点查找其邻接点的过程。其耗费的时间则取决于所采用的存储结构。当用二维数组表示邻接矩阵图的存储结构时,
查找每个顶点的邻接点所需时间为
, 其中n 为图中顶点数。而当以邻接表作图的存储结构时, 找邻接点所需时间为0(e), 其中e 为无向图中边的数或有向图中弧的数。由此, 当以邻接表作存储结构时, 深度优先搜索遍历图的时间复杂度为。即可得出正确答案。
9． 对于栈操作数据的原则是（ ）
A. 先进先出
B. 后进先出
C. 后进后出
D. 不分顺序
【答案】B
【解析】先进先出是队列操作数据的原则。先进后出是栈操作数据的原则，栈限定在表尾进行插入和删除。
10．输入序列为ABC ，可以变为CBA 时，经过的栈操作为（ ）。
A.push ，pop ，push ，pop ，push ，pop
B.push ，push ，push ，pop ，pop ，pop
C.push ，push ，，pop ，pop ，push ，pop
D.push ，pop ，push ，push ，pop ，pop
【答案】B
【解析】根据输入序列和输出序列可知，输入序列全部进找，然后再出找。从中可以看出，
第 4 页，共 53 页