微软校长笔试真题及答案(二)
更新时间：高考猫
题目二： 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\n",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\n",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. 问以下哪些特征不是 interPted 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 值 程序编写完成后，请编写测试用例，并说明它完成的作用。
