2018年南京师范大学教育科学学院821数据结构考研基础五套测试题
● 摘要
一、单项选择题
1． 某时刻进程的资源使用情况如下表所示
此时的安全序列是（ ）。 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的 分配, 亦即找不到能够安全运行的序列, 因此此时是处于不安全状态, 所以不存在这样的安全序列。
2． 对给定的关键字序列110, 119, 007, 911, 114, 120, 122进行基数排序, 则第2趟分配收集后得到的关键字序列是（ ）
A.007.110.119.114.911.120.122 B.007, 110, 119, 114, 911, 122, 120 C.007, 110, 911, 114, 119, 120, 122 D.110, 120, 911, 122, 114, 007, 119
【答案】C
【解析】基数排序的第1趟排序是按照个位数字来排序的, 第2趟排序是按然十位数字的大小进行排序的, 故答案是C 选项。
3． 下列关于银行家算法的叙述中, 正确的是（ ）
A. 银行家算法可以预防死锁
B. 当系统处于安全状态时, 系统中一定无死锁进程 C. 当系统处于不安全状态时, 系统中一定会出现死锁进程 D. 银行家算法破坏了死锁必要条件中的“请求和保持”条件 【答案】B
【解析】银行家算法是避免死锁的方法。利用银行家算法, 系统处于安全状态时没有死锁进程, 故答案选B 。
4． 某计算机主频为1.2GHz , 其指令分为4类, 它们在基准程序中所占比例及CPI 如下表所示。
该机的MIPS 数是（ ） A.100 B.200 C.400 D.600
【答案】C
【解析】基准程序的
。
, 为1200MHz , 该机器的MIPS 为计算机的主频为。
5． 有两个并发执行的进程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种了。
6． 假设栈初始为空, 将中缀表达式当扫描到f 时, 栈中的元素依次是（ ）
A. B. C. D. 【答案】B
【解析】中缀表达式转后缀表达式遵循以下原则: (1)遇到操作数, 直接输出; (2)栈为空时, 遇到运算符, 入栈; (3)遇到左括号, 将其入栈;
(4)遇到右括号, 执行出栈操作, 并将出栈的元素输出, 直到弹出栈的是左括号, 左括号不输出; (5)遇到其他运算符符入栈;
(6)最终将栈中的元素依次出桟, 输出。
所以扫描到‟/‟, 入栈„描到‟+‟, 由于‟+‟优先级比‟/'低, 所以将‟/‟弹出, ‟+‟入栈; 扫描到‟*,, 优先级比‟+‟高, 入栈; 扫描到‟(„, 入栈; 扫描到‟一„, 将栈中优先级更高的‟*‟弹出, „一, 入栈; 扫描到‟*‟, 优先级比‟一„高, 入栈。所以扫描至“f的时候, 栈中元素为:+(一*
7． 当字符序列 作为图输入时，输出长度为3的且可用作C 语言标识符的序列的有（ ）。
A.4个 B.5个 C.3个 D.6个
时, 弹出所有优先级大于或等于该运算符的栈顶元素, 然后将该运算
转换为等价后缀表达式的过程中,
相关内容
相关标签