2018年太原科技大学电子信息工程学院882数据结构考研强化五套模拟题
● 摘要
一、单项选择题
1． 无向图G=(V，E) ，其中:
，
对该图进行深度优先遍历，得到的顶点序列正确的是（ ）。
A.a , b , e , c , d , f
B.a , c , f , e , b , d
C.a , e , b , c , f , d
D.a , e , d , f , c , b
【答案】D
【解析】图的深度优先遍历过程是:从图中某个初始顸点v 出发，首先访问初始顶点v ，然后选择一个与顶点V 相邻且没被访问过的顶点U 为初始顶点。再从U 出发进行深度优先搜索，直到图中与当前顶点V 邻接的所有顶点都被访问过为止。
根据
关系。依据
上面的原则遍历，得出遍历顺序a ，e ，d ，f ，c ，b 。
2． 假定下列指令已装入指令寄存器。则执行时不可能导致CPU 从用户态变为内核态(系统态) 的是（ ）。 A.
B. ; 产生软中断 C. ; 寄存器R0的内容取非 可知各顶点之间的邻接
D.MOVRO , addr ; 把地址处的内存数据放入寄存器RO 中
【答案】C
【解析】A 项, 除法操作出现除数为零的情况时, 会产生内中断, CPU 切换为内核态进行中断处理; B 项, 直接产生中断, 会切换到内核态; D 项, addr 出现非法地址, 会出现中断, 进而切换到内核态。
3． 采用开址定址法解决冲突的哈希查找中，发生集聚的原因主要是（ ）。
A. 数据元素过多
B. 负载因子过大
C. 哈希函数选择不当
D. 解决冲突的算法选择不好
【答案】D
【解析】开放定址法就是从发生冲突的那个单元开始，按照一定的次序，从散列表中查找出一个空闲的存储单元，把发生冲突的待插入元素存入到该单元中的一类处理冲突的方法。
4． 冯•诺依曼计算机中指令和数据均以二进制形式存放在存储器中，CPU 区分它们的依据是（ ）.
A. 指令操作码的译码结果
B. 指令和数据的寻址方式
C. 指令周期的不同阶段
D. 指令和数据所在的存储单元
【答案】C
【解析】在冯•诺依曼结构计算机中指令和数据均以二进制形式存放在同一个存储器中，CPU 可以根据指令周期的不同阶段来区分是指令还是数据，通常在取指阶段取出的是指令，其他阶段(分析取数阶段、执行阶段) 取出的是数据. 所以，CPU 区分指令和数据的依据是指令周期的不同阶段.
5． 假定编译器将赋值语句“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次。
6． 某时刻进程的资源使用情况如下表所示
此时的安全序列是（ ）。
A.P1, P2, P3, P4
B.P1, P3, P2, P4
C.P1, P4, P3, P2
D. 不存在
【答案】D
【解析】典型的死锁避免算法, 银行家算法的应用。银行家算法是操作系统中的一个重点知识单元, 考生对此应该非常熟悉, 本题并无难点。分析一下下表, 可以看到, 经过P1, P4的运行以后, 可用资源是2, 2, 1, 而P2, P3所需资源分别是1, 3, 2和1, 3, 1。所以剩余资源已经不够P2或P3的
分配, 亦即找不到能够安全运行的序列, 因此此时是处于不安全状态, 所以不存在这样的安全序列。
7． 在下面的程序段中，对x 的赋值语句的时间复杂度为（ ）
A.O(2n)
B.O(n)
C.O(n2)
D.O(log2n )
【答案】C
【解析】两个循环嵌套，那么语句x :＝x+l:则被执行了n 次。
8． 设X 是树T 中的一个非根结点，B 是T 所对应的二叉树。在B 中，X 是其双亲的右孩子，2下列结论正确的是（ ）。
A. 在树T 中，X 是其双亲的第一个孩子
B. 在树T 中，X 一定无右兄弟
C. 在树T 中，X 一定是叶结点
D. 在树T 中，X 一定有左兄弟
【答案】D
【解析】由树和二叉树的转换关系可知，X 一定有左兄弟，X 是其双亲的第二个孩子，不能确定在树T 中，X 是否有右兄弟，是否是叶结点。
9． 设有向图G=(V, E) , 顶点集
边集,
,
若从顶点V0开始对图进行深度优先遍历, 则可能得到的不同遍历序列个数是（ ）。
A.2
B.3
相关内容
相关标签