1、计算机专业（基础综合）模拟试卷 22 及答案与解析一、单项选择题1-40 小题，每小题 2 分，共 80 分。下列每题给出的四个选项中，只有一个选项是最符合题目要求的。1 设 n 是描述问题规模的非负整数，下面程序片段的时间复杂度是( )。void fun(int n)int i，k；for(i=1；i路径长度最短的顶点 u 加入到集合 S 中，集合 S 每加入一个新的顶点 u，都要修改顶点 b到集合 T 中剩余顶点的最短路径长度值，集合 T 中各顶点新的最短路径长度值为原来的最短路径长度值与顶点“的最短路径长度值加上 u 到该顶点的路径长度值中的较小值。 (3) 此过程不断重复，直到集合 T
2、 的顶点全部加入到 S 中为止。42 【正确答案】 (1)算法的基本设计思想如解析所述。(2)用 C 语言算法描述如下：void Adjust(int A) 调整数组 A，使得 A 的左边为负整数，右边为正整数int i=1， j=n，temp；while(i0&ij)j-； Aj为正整数时， j 减 1if(ij)temp=Ai；Ai=Aj；Aj=temp； Ai为正整数、Aj 为负整数时，交换i+：j-；(3)算法的时间复杂度为 0(n)；算法的空间复杂度为 O(1)。【试题解析】 本题主要考查线性表的顺序存储结构(这里为数组)的应用。算法的基本设计思想是先设置好上、下界和轴值，然后分别从
3、数组前端查找正整数和从数组末端查找负整数，找到后进行交换，直到上、下界相遇。具体做法是：设置两个指示器 i 和 j，其中 i=1，j=n；当 Ai为正整数，Aj为负整数时，Ai 和 Aj交换；否则，Ai为负整数时，则 i+；Aj为正整数时，则j-。这样，可使算法的时间复杂度为 O(n)。43 【正确答案】 (1)变址寻址时，操作数 S=(Rx)+A)=(23AOH+001AH)=(23BAH)=1 748 H。 (2)间接寻址时，操作数 S=(A)=(001 AH)=(23AOH)=2600 H。 (3)转移指令使用相对寻址，转移地址=(PC)+A=1F05 H+001 AH=1F1FH。 因
4、为在本题中没有指出指令的长度，故此题未考虑 PC 值的更新。【试题解析】 前两个小题涉及数据寻址，其最终目的是寻找操作数，第 3 小题涉及指令寻址，其目的是寻找下一条将要执行的指令地址。44 【正确答案】 运算器的故障位置在多路开关 B，其输出始终为 R1 的值。 (1)R1(A)+R2(B)1010，输出结果错； (2)R 2(A)+R1(B)11 11，结果正确，说明 R2(A)，R1(B)无错； (3)R 1(A)+R1(B)1010，结果正确，说明 R1(A)，R 1(B)无错。由此可断定 ALU 和 BR 无错； (4)R 2(A)+R2(B)11 11。结果错。由于 R2(A)正确
5、，且R2(A) 1010，本应 R2 (B)一 101 0，但此时推知 R2(B)0101，显然，多路开关 B有问题； (5)R 2(A)+BR(B)=11 11，结果错。由于 R2(A)1010，BR(B)11 11，但现在推知 BR(B)0101，证明开关 B 输出有错； (6)R 1(A)+BR(B)1010，结果错。由于 R1(A)0101，本应 BR(B)11 11，但现在推知 BR(B)0101，再次证明开关B 出错。 综上所述，多路开关 B 输出有错。故障性质：多路开关 B 输出始终为0101。这有两种可能：一是控制信号 BS0，BS 1 始终为 01，故始终选中寄存器R1；二是
6、多路开关 B 电平输出始终处于在 0101 上。【试题解析】 根据已知的 6 步运算过程一步一步地分析，可知运算器的故障位置在多路开关 B。45 【正确答案】 根据题意，画出甘特图如下： 从运行的时序甘特图上可以看出：处理机在 200ms 到 300ms 之间是空闲的。因此，处理机的利用率可以计算出为：(200+300)600=833%。 进程 P0 运行过程中无等待现象，进程 P1 有等待现象，等待区间为 350400ms 之间。【试题解析】 本题考查进程调度的过程。解决这类题目的关键在于画出进程运行的时序图，若用条形来表示这种时序图就称为甘特图，然后再对其进行分析。绘图和分析过程中要注意题
7、目适用的调度算法，先来先服务最简单，按先来后到的次序进行调度，被调度的进程一般会占有处理机运行直到自己主动放弃；短进程优先算法在选取调度的进程时需要知道进程的预计执行时间，根据进程表里填写的进程预计执行时间，选取最短的进程调度其运行；高优先级优先的调度算法是根据进程表内赋予的优先级来调度，当然，优先级的确定可以有各种方法，可以在创建时确定，也可以根据程序的紧急程度确定，还可以根据收费多少确定，所以优先级的确定有许多灵活性，现行大部分操作系统均会采用高优先级优先的调度算法；时间片轮转的调度算法是由硬件时钟确定每一个进程占用处理机的时间的，进程按先来先服务排队，调度器调度进程队列中最先的进程运行，若分配的时间未到进程就主动放弃处理机，则会引起下一次调度，若分配的时间到，则不管进程是否运行完成，必须立即强制地出让处理机。在以上描述的各种调度算法既可以单独使用，也可以组合使用。不管采用什么算法，能否抢先是另一个调度的非常重要的因素，为适应不同用户的需求，也为改善计算机的性能，现代许多操作系统均采用抢先式调度算法，抢先式调度不能单独实施，一定是与上述各种调度算法相结合。处理机的调度相对
