当前位置：问答库＞考研试题

一、单项选择题

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． 假定有4个整数用8位补码分别表示为放在一个8位寄存器中, 则下列运算会发生溢出的是（ ）。

A. B. C. D. 【答案】B

【解析】用补码表示时8位寄存器所能表示的整数范围为数

,

, 在4个选项中, 只有

都未超过127, 不发生溢出

3． 静态链表中指针表示的是（ ）。

A. 下一元素的地址 B. 内存储器的地址 C. 下一元素在数组中的位置 D. 左链或右链指向的元素的地址

第 2 页，共 74 页

可知各顶点之间的邻接

。若将运算结果存

。现在4个整数都是负

, 结果溢出, 其余3个算式结果

【答案】C

【解析】静态链表的一般结构为:struct static_list{ElemType data；int next；}

这种结构是预先分配一个较大的空间，类似于一次申请一个较大的数组，但是元素的增删操作都不会移动元素，只需要移动next 成员就行。因此，静态链表中的指针实际上表示的就是下一个元素在数组中的位置。

4． 有两个并发执行的进程P1和P2, 共享初值为1的变量x 。P1对x 加1, P2对x 减1。加1和减1操作的指令序列分别如下所示。

两个操作完成后, 2的值（ ）。 A. 可能为-1或3 B. 只能为1 C. 可能为0、1或2 D. 可能为-1、0、1或2 【答案】C

【解析】这是在数据库中常有的操作。为保证数据的正确, 避免产生错误, 系统必须保证数据的同步。而保证数据的同步一般采取加锁的方法, 让进程P1和P2互斥访问共享变量X 。当然用信号量和P 、V 操作也是可以保证互斥操作, 达到数据同步的。

本例中, 由于没有采取保证数据同步的相应措施, 则最后结果就会出现差错。例如, 当正常情况下, 进程P1和P2先后对x 操作, 可以看到x 值的变化为初始则x 值的变化为初始

的过程, 若P2, P1先后操作,

, 这是正确的。若考虑一种并发的情况, 进程P1和P2先后执行了取数

load 的操作, 它们得到的x 值均为1, 运算后, P1和P2的x 值分别为2和0, 此时要看哪个进程后执行存数store 的操作了, 哪个进程后操作, 结果就是那个进程的x 值, 所以可能的结果为0或2, 加上前面正确的x 值1, 则可能的结果就有3种了。

5． 已知串其Next 数组值为（ ）。

A.0123 B.1123 C.1231 D.1211 【答案】A

【解析】KMP 算法的next 数组建立的原则

第 3 页，共 74 页

6． —个进程的读磁区操作完成后, 操作系统针对该进程必做的是（ ）

A. 修改进程状态为就绪态 B. 降低进程优先级 C. 进程分配用户内存空间 D. 增加进程的时间片大小 【答案】A

【解析】进程等待的操作完成便会从等待状态转移到就绪状态。

7． 将线性表的数据元素进行扩充，允许带结构的线性表是（ ）。

A. 串 B. 树 C. 广义表 D. 栈 【答案】C

【解析】串、树、桟中的数据元素都是属于非结构的原子类型，元素的值是不可分解的。数组和广义表都是允许带结构的线性表。

8． 假设磁头当前位于第105道，正在向磁道序号增加的方向移动. 现有一个磁道访问请求，序列为35，45，12，68，110，180，170，195，采用SCAN 调度(电梯调度) 算法得到的磁道访问序列是（ ）.

A.110， 170， 180， 195， 68， 45， 35， 12 B.110， 68， 45， 35， 12， 170， 180， 195 C.110， 170， 180， 195， 12， 35， 45， 68 D.12， 31， 45， 68， 110， 170， 180， 195

【答案】A

【解析】SCAN 算法类似电梯工作原理，即朝一个固定方向前进，经过的磁道有访问请求则马上服务，直至到达一端顶点，再掉头往回移动以服务经过的磁道，并这样在两端之间往返. 因此，当磁头从105道向序号增加的方向移动时，便会服务所有大于105的磁道号(从小到大的顺序) ；往回返时又会按照从大到小的顺序进行服务. 注意与循环扫描算法的区别，所以SCAN 算法的访问序列是：110， 170， 180， 195， 68， 45， 35， 12

9． 采用递归方式对顺序表进行快速排序。下列关于递归次数的叙述中, 正确的是（ ）。

A. 递归次数与初始数据的排列次序无关

第 4 页，共 74 页