题目二： 　　1写出下列算法的时间复杂度。 　　(1)冒泡排序; 　　(2)选择排序; 　　(3)插入排序; 　　(4)快速排序; 　　(5)堆排序; 　　(6)归并排序; 　　2写出下列程序在X86上的运行结果。 　　struct mybitfields 　　{ 　　unsigned short a : 4; 　　unsigned short b : 5; 　　unsigned short c : 7; 　　}test 　　void main(void) 　　{ 　　int i; 　　test.a=2; 　　test.b=3; 　　test.c=0; 　　i=*((short *)&test); 　　printf("%d ",i); 　　} 　　3写出下列程序的运行结果。 　　unsigned int i=3; 　　cout< 　　4写出下列程序所有可能的运行结果。 　　int a; 　　int b; 　　int c; 　　void F1() 　　{ 　　b=a*2; 　　a=b; 　　} 　　void F2() 　　{ 　　c=a+1; 　　a=c; 　　} 　　main() 　　{ 　　a=5; 　　//Start F1,F2 in parallel 　　F1(); F2(); 　　printf("a=%d ",a); 　　} 　　5考察了一个CharPrev()函数的作用。 　　6对 16 Bits colors的处理，要求： 　　(1)Byte转换为RGB时，保留高5、6bits; 　　(2)RGB转换为Byte时，第2、3位置零。 　　7一个链表的操作，注意代码的健壮和安全性。要求： 　　(1)增加一个元素; 　　(2)获得头元素; 　　(3)弹出头元素(获得值并删除)。 　　8一个给定的数值由左边开始升位到右边第N位，如 0010<<1 == 0100 或者 0001 0011<<4 == 0011 0000 　　请用C或者C++或者其他X86上能运行的程序实现。 　　附加题(只有在完成以上题目后，才获准回答) 　　In C++, what does "explicit" mean? what does "protected" mean? 　　题目三： 　　某栋写字楼6层，有1部电梯，请编写一个电梯仿真程序 　　A.考虑如下条件 　　1.每层楼都有上行和下行两个按键 　　2. 电梯一开始停在1层 　　3. 电梯可以容纳8个人 　　4. 乘坐电梯的客人的请求频率，时间间隔和到达楼层是随机的 　　5. 电梯的上下一层需要1秒 　　6. 电梯空间有限，同时只能容纳一定数量的客人，如果已经达到人数额度，电梯将不理会任何请求 　　7.不考虑客人请求当前楼层和不请求楼层的情况 　　8. 电梯的响应延迟为0(比如，电梯往3楼上行，3楼的客人在电梯到达3楼之前按上行键，程序有权调度电梯在3楼开门) 　　9. 电梯的开关门时间和客人上下电梯时间为0，匀速运行 　　10. 电梯调度算法不能预读尚未发生的请求(比如在10秒的时候电梯无法预知11秒时某层客人的请求) 　　11.客人请求发生在整数秒 　　B.目标 　　1. 在运送所有客人到达目标楼层的前提下电梯的总行程尽可能小 　　2. 设计一个接口，实现调度算法的可替换性(比如，通过重新实现该接口可以使系统使用其它算法) 　　C. 输入和输出 　　输入: 　　input.txt 　　客人的请求序列，格式为到达时间，所在楼层，请求楼层，假设该输入是按照时间递增的 　　比如： 　　input.txt 　　1 2 3 　　2 3 1 　　在1秒的时候有客人请求从2层到3层，2秒的时候有客人请求从3层到1层 　　输出: 设计一种简单实用的输出可以清晰地反映电梯的运转情况 　　题目四： 　　选择题部分 　　1. 以下哪些不是栈的基本操作 　　A. push 　　B. pop 　　C. 判断栈是否为空 　　D. 栈排序 　　2.两个有序数组 大小都是 n，现在要对它们进行合并排序。 问最坏情况下，需要比较多少次? 　　A. 2n+1 　　B. 2n 　　C.2n-1 　　D…记不清了 　　3. (an 表示第 n 个常数， x^5 表示 x 的 5 次方) 　　f(x)= a0*x^0 + a1*x^1+a2*x^2+……an*x^n 　　对于固定的 n，f(x)的时间复杂度以及空间复杂度分别是多少? 　　A. o(n^2)，o(n) 　　B.o(n)，o(1) 　　C 　　D 都记不住了 　　4.是个概率题，大概意思是这样的 　　现在有 800 个人，但是只有 400 份奖品，有一对夫妇都参加抽奖，但是他们最多抽到一份奖，现在问 　　他们俩能抽到一份奖的概率是多少? 　　A.0.5 　　B.0.75 　　C. (0.5,0.75) 　　D. (0.75,1) 　　5. 现有一链表当前指示节点为 currentNode, 生成了一个新节点 newNode,问要把 newNode 插入到currentNode 之后 ，该怎么做? 　　A… 　　B… 　　C. newNode->next = currentNode->next, currentNode->next = newNode. 　　D… 　　6. 问以下哪些特征不是 interpreted language(解释型语言)所独有的： 　　(我们知道一般分为两种：解释型语言 VB,Shell,批处理等;编译型语言，C，java 等。各有优点 ) 　　A. 平台无关性。(明显不对，因为 java 才是平台无关的) 　　B. 执行速度较快(这个问题，以前做作业时就没争论清楚，自己感觉解释型语言不需要编译，速度能快一些，但是重复执行时，编译型语言只需要编译一次，效率高……) 　　C. 可以定义动态变量(应该两种都可以) 　　D.以上都不对 　　7.给了一个二叉树，让求后序遍历的结果。 　　这个题如果知道后序遍历，肯定就可以做出来了。 　　尽管不难 还是要搞清楚三者的区别(哈哈) 　　先序 左根右 　　中序 根左右 　　后序 左右根 　　8.问以下几种排序方法，在最坏情况下时间复杂度小于 o(n^2)的是哪一种(这个题目记得不是很清楚了) 　　A.快排 　　B.插入排序 　　C.合并排序 　　D.栈排序 　　9. 现有 n+1 这么大的存储空间(可以理解有这么一个大小为 n+1 的数组)，中间存了[1,n+1]范围内的n 个数，说明丢失了一个数，现在要找出这个丢失的数，问最好情况下时间复杂度是多少 　　A.o(1) 　　B.o(n) 　　C.o(n^2) 　　D.o(nlogn) 　　10.是一道程序题，由于太长，无从记忆…… 　　编程题部分用 C,C++,C#,或 Java 中的一种来编写以下程序。 　　现在给你一个 字符串，其中特殊的字符只有两种 space(空格)(" ")，newline(换行)(/n)。 现在让你来去除其中多余的空格。具体要求 　　1.连续的空格只能当保留其中一个 　　2. 该字符串的开头不能有空格 　　3. 该字符串的结尾不能有空格 　　4. 任何/n 的前面或才后面都不能存在多余的空格 　　为了得到很高的分数，还需要满足以下条件 　　1.不能申请新的字符串空间 　　2.对给出的字符串只能遍历一遍 　　不能使用任何库函数。 　　我们给了两个供你调用的函数 　　int intIsSpace(char str)() 　　当字符不为空格时，将返回 0 　　当字符为空格时，将返回其它任意非 0 值 　　int intIsNewLine(char str)()当字符不为换行时，将返回 0 　　当字符为换行时，将返回其它任意非 0 值 　　程序编写完成后，请编写测试用例，并说明它完成的作用。