2017年河北大学电信学院893数据结构考研题库
● 摘要
一、选择题
1． 设置当前工作目录的主要目的是（ ）。
A. 节省外存空间
B. 节省内存空间
C. 加快文件的检索速度
D. 加快文件的读/写速度
【答案】C
【解析】工作目录只是指出了当前操作的默认目录，使得在每次访问的时候不需要由根目录
一层一层地解析，在文件路径比较长时，可以节省许多解析的时间，从而加快了文件的检索速度。
2． 下列说法不正确的是（ ）。
A. 图的遍历是从给定的源点出发每个顶点仅被访问一次
B. 遍历的基本方法有两种：深度遍历和广度遍历
C. 图的深度遍历不适用于有向图
D. 图的深度遍历是一个递归过程
【答案】C
【解析】图的遍历是指从图中的某一个顶点出发，按照某种搜索算法沿着图中的边对图中的所有顶点访问一次且仅访问一次。图的深度遍历类似于树的先序遍历，不仅适合无向图，也适合于有向图。
3． 已知一个长度为16的顺序表L , 其元素按关键字有序排列。若采用折半查找法查找一个L 中不存在的元素，则关键字的比较次数最多是（ ）。
A.4
B.5
C.6
D.7
【答案】B
【解析】折半查找法在查找不成功时和给定值进行比较的关键字个数最多为（l 〇g2n ） +1，在本题中，n=16, 故比较次数最多为5。
4． 假定编译器将赋值语句“x=x+3; ”转换为指令” add xaddt, 3”，其中xaddt 是x 对应的存储单元地址，若执行该指令的计算机采用页式虚拟存储管理方式，并配有相应的TLB ，且Cache 使用直写（Write Through）方式，则完成该指令功能需要访问主存的次数至少是（ ）。
A.0
B.1
C.2
D.3
【答案】C
【解析】采用页式虚拟存储管理方式时，若页表全部放在内存中，则存取一个数据最少要访问两次内存：第一次是访问页表，得到所存取的数据或指令的物理地址；第二次根据该地址存取数据或指令。在配有TLB 的页式虚拟管理方式中，如果给出的地址在TLB 中，则直接根据该地址取数据或指令，仅需要一次访问内存。Cache 使用直写方式时，计算完需要将数据写回到内存中，因此完成整个指令功能至少需要访问主存2次。
5． 关键路径是AOE 网中（ ）。
A. 从始点到终点的最短路径
B. 从始点到终点的最长路径
C. 从始点到终点的边数最多的路径
D. 从始点到终点的边数最少的路径
【答案】B
【解析】在AOE-网中有些活动可以并行地进行，所以完成工程的最短时间是从开始点到完成点的最长路径的长度（这里所说的路径长度是指路径上各活动持续时间之和，不是路径上弧的数目）。路径长度最长的路径称作关键路径（critical path）。
6． 静态链表中指针表示的是（ ）。
A. 下一元素的地址
B. 内存储器的地址
C. 下一元素在数组中的位置
D. 左链或右链指向的元素的地址
【答案】C
【解析】静态链表的一般结构为：
这种结构是预先分配一个较大的空间，类似于一次申请一个较大的数组，但是元素的增删操作都不会移动元素，只需要移动next 成员就行。因此，静态链表中的指针实际上表示的就是下一个元素在数组中的位置。
7． 算法的计算量的大小称为计算的（ ）。
A. 效率
B. 复杂性
C. 现实性
D. 难度
【答案】B
【解析】算法复杂度通常分为时间复杂度和空间复杂度，算法的计算量的大小可以用时间复
杂度衡量，即可以称为计算的复杂度。
8． 主机甲通过1个路由器个路由器（存储转发方式）与主机乙互联，两段链路的数据传输速率均为10Mbps ，主机甲分别采用报文交换和组大小为10kb 的分组交换向主机乙发送1
个大小为
的报文。若忽略链路传播延迟、分组头开销和拆装时间，则两种交换方式完成该
报文传输所需的总时间分别为（ ）
A.800ms> 1600ms
B.801ms 、1600ms
C.1600ms 、800ms
D.1600ms 、801ms
【答案】D
【解析】不进行分组时，发送一个报文的时延是
的时延也是800ms 共计1600ms 。进行分组后发送一个报文的时延是在接收端接收此报文件接收一个报文的时延也是1ms ，但是在发送第二个报文时，第一个报文已经开始接收。共计有800个分组，总时间为801 ms。
9． 在采用中断I/O方式控制打印输出的情况下，CPU 和打印控制接口中的I/O端口之间交换的信息不可能是（ ）。
A. 打印字符
B. 主存地址
C. 设备状态
D. 控制命令
【答案】B
【解析】I/O接口的功能包括：①选址功能；②传送命令功能；③传送数据功能；④反映I/O设备工作状态功能。A 项为数据，C 项为设备状态，D 项为命令。B 项，主存地址在中断方式控制下是不需要的，因此，它不可能是CPU 和打印控制接口中的I/O端口之间交换的信息。
10．有两个并发执行的进程P1和P2, 共享初值为1的变量x 。P1对x 加1, P2对x 减1。加1和减1操作的指令序列分别如下所示。
//取x 到寄存器R1中
两个操作完成后，2的值（ ）。
A. 可能为-1或3
B. 只能为1
C. 可能为0、1或2
相关内容
相关标签