一 不定向选择题 18分
1. 一个栈的入栈队列 a,b,c,d,e 则栈的不可能的输出序列是______。
A. edcba
B. dceab
C. decba
D. abcde
E. 以上都不是
2. 在定点二进制运算器中，减法运算一般通过______来实现。
A 原码运算的二进制减法器
B 补码运算的二进制减法器
C 原码运算的十进制加法器
D 补码运算的二进制加法器
3. 主存贮器和CPU之间增加cache的目的是______。
A 解决CPU和主存之间的速度匹配问题
B 扩大主存贮器容量
C 扩大CPU中通用寄存器的数量
D 既扩大主存贮器容量，又扩大CPU中通用寄存器的数量
4. CRT的分辨率为1024×1024像素，像素的颜色数为256，则刷新存储器的容量为______。
A 512KB B 1MB C 256KB D 2MB
5. 文法G：S -> xSx | y 所识别的语言是______。
A.xy*x B.(xyx)* C.xx*yxx* D.x*yx*
6.每个进程在操作系统中用进程控制块(process control block，PCB)来表示，请找出以下不属于进程控制块中的信息______。 A. 进程PID
B. 进程优先级
C. 进程间通信方式
D. 进程的执行时间
二 简答题 30分
1. 使用大O标记法写出下列算法的时间复杂度。(6分)
(1)冒泡排序;O(n2 )
(2)选择排序;O(n2 )
(3)插入排序;O(n2 )
(4)快速排序;O(nlogn)
(5)堆排序;O(nlogn)
(6)归并排序：O(nlogn)
2. 以知cache 命中率 H=0.98，cache的存取速度是主存的4倍，以知主存存取周期为200ns，求平均访问时间。(4分)
3.有1000个苹果，分别装在10个箱子里。任意给出1到1000之间的一个整数，都可以用某几个箱子中的苹果数量相加获得此数。请列出这10个箱子中分别有多少个苹果： (5分)
4. 有一种体育竞赛共含M个项目，有运动员A，B，C三人参加，在每一项目中，第一,第二,第三名分别得X，Y，Z分，其中X,Y,Z为正整数且X>Y>Z。最后A得22分，B与C均得9分，B在百米赛中取得第一。
求M的值( )(5分)
在跳高中谁得第二名( ) (5分)
5. 以A、B表为例，主外键为id。简述INNER JOIN、LEFT JOIN和RIGHT JOIN的区别(5分)
A INNER JOIN B：返回A和B中符合on条件式的记录
A LEFT JOIN B:返回A中的所有记录和B中符合on条件式的记录
A RIGHT JOIN B：返回B中的所有记录和A中符合on条件式的记录