设有带头结点的循环双链表表示的线性表L＝＝＝(a
1
，a
2
，……，a
n－1
，a
n
)。设计在时间和空间上都尽可能高效的算法，将L改造成L＝(a
1
，a
3
，……，a
n
……a
4
，a
2
)。要求：
(1)给出算法的基本设计思想。
(2)根据设计思想，采用C或C＋＋或JAVA语言描述算法，关键之处给出注释。
(3)说明你所设计算法的时间复杂度和空间复杂度。
某字长为8位的计算机中，已知整型变量x、y的机器数分别为[x]
补
1 1110100，[y]
补
=1 0110000。若整型变量z=2*x+y／2，则Z的机器数为_______。
判断有向图是否存在回路，除了可以利用拓扑排序外，还可以利用的是( )。
通道是一种IO设备，它主要用于传输的数据是位于( )。
地址总线为A
15
（高位）～A
0
（低位），若用1K×4位的存储芯片组成4KB的存储器，地址总线的高位做片选信号，则以下说法正确的是( )。
Ⅰ．加在各存储芯片上的地址线是A
11
～A
0
Ⅱ．加在各存储芯片上的地址线是A
9
～A
0
Ⅲ．—共需要使用8片1K×4位的存储芯片
Ⅳ．一共需要使用4片1K×4位的存储芯片
在一个分页存储管理系统中，地址空间分页(每页1K)，物理空间分块，设主存总容量为256KB，描述主存分配情况的位示图如下右图所示(0表示未分配，1表示已分配)，此时作业调度程序选中一个长为5．2K的作业投入内存。试问：
为实现快速排序算法，待排序序列宜采用的存储方式是_______。
考虑下面的基于动态改变优先级的可抢占式优先权调度算法。大的优先权数代表高优先级。当一个进程在等待CPU时（在就绪队列中，但未执行），优先权以α速率改变；当它运行时，优先权以p速率改变。所有的进程在进入就绪队列被给定优先权数为O。参数a和p可以设定给许多不同的调度算法。下列( )设定可以实现进程FIFO (First In First Out)。
下列说法中，正确的有( )。Ⅰ．清除内存、设置时钟都是特权指令，只能在内核态（系统态、管态）下执行Ⅱ．用零作除数将产生中断Ⅲ．用户态到内核态的转换是由硬件完成的Ⅳ．在中断发生后，进入中断处理的程序可能是操作系统程序，也可能是应用程序
B综合应用题41-47小题。/B
在Cache和主存构成的两级存储器中，Cache的存储时间是100ns，主存的存储时间是1000ns，如果希望有效存储时间不超过115ns，则Cache的命中率至少为( )。
下列说法中，错误的是( )。Ⅰ．设浮点数的基数为4，尾数用原码表示，则0．000010为规格化数Ⅱ．浮点数运算中，运算结果超出尾数表示范围则表示溢出Ⅲ．任何情况下，浮点数的右规操作最多只会进行一次
在n个结点的线性表的数组表示中，以下算法的时间复杂度是O(1)的操作是( )。Ⅰ．访问第i个结点(1＜=i＜=n)和求第i个结点的直接前驱(2＜=i＜=n)Ⅱ．在最后一个结点后插入一个新的结点Ⅲ．删除第一个结点Ⅳ．在第i个结点后插入一个结点(1＜=i＜=n)
在4位有效信息上增加3位校验位后得到码长7位的海明校验码，它的检、纠错能力是( )。
某机器采用16位单字长指令，采用定长操作码，地址码为5位，现己定义60条二地址指令，那么单地址指令最多有( )条。
一131的1字节、2字节补码分别是( )。
某计算机的存储系统由Cache．主存系统构成，Cache的存取周期为10ns，主存的存取周期为50ns。在CPU执行一段程序时，Cache完成存取的次数为4800次，主存完成的存取次数为200次，该Cache—主存系统的效率是( )。(设Cache和主存不能同时访问)
已知X＝－0．875×2
1
，Y＝0．625×2
2
，设浮点数格式为阶符1位，阶码2位，数符1位，尾数3位，通过补码求出Z—X—Y的二进制浮点数规格化结果是( )。
当向一棵m阶的B一树做插入操作时，若一个结点中的关键字个数等于( )，则必须分裂成两个结点，当向一棵m阶的B一树做删除操作时，若一个结点中的关键字个数等于( )，则可能需要同它的左兄弟或右兄弟结点合并成一个结点。
下列关于UDP协议的叙述中，正确的是_______。Ⅰ．提供无连接服务Ⅱ．提供复用份用服务Ⅲ．通过差错校验，保障可靠数据传输