一、单选题(前10题，每题2分;后10题，每题3分;共50分。选对得满分，选错倒扣1分，不选德得0分)

　　1.假设一个主机的IP地址为192.168.5.121，而子网掩码为255.255.255.248。那么该主机的网络号部分(包括子网号部分)为              。

　　A. 192.168.5.12 B. 192.168.5.121 C. 192.168.5.120D.192.168.5.32

　　2.64位系统上，定义变量int*a[2][3]占据              字节。

　　A.4 B.12 C. 24 D.48

　　3.Linux中使用df –h/home和du –sh/home所查看到的已使用的磁盘容量不同，可能的原因是              。

　　A.命令不同，所以结果肯定不同 B.两个命令所用的参数有问题

　　C.运行中的进程打开文件被删除导致 D. Linux的特性导致的

　　4.一个C语言程序在一台32位及其上运行。程序中定义了三个变量xyz，其中x和z是int型，y为short型。当x=127,y=-9时，执行赋值语句z=x+y后，xyz的值分别是              。

　　A. x=0000007FH, y=FFF9H, z=00000076H

　　B. x=0000007FH, y=FFF9H, z=FFFF0076H

　　C. x=0000007FH, y=FFF7H, z=FFFF0076H

　　D. x=0000007FH, y=FFF7H, z=00000076H

　　5.有如下数组定义，

　　int [][] myArray = new int [3][] { new int[3]{5, 6, 2},

　　new int[5]{6, 9, 7, 8, 3},

　　new int[2]{3,2}};

　　则，myArray[2][2]的值是              。

　　A. 9 B. 2 C. 6 D.越界

　　6.快速排序的期望运行时间复杂度是              。

　　A. O(n2) B. O(nlogn) C. O(n) D.O(2n)

　　7.在一个长度为n的顺序表中删除第i个元素，要移动 个元素。如果在第i个元素前插入一个元素，要后移              个元素。

　　A. n-i, n-i+1 B. n-i+1, n-i C. n-i, n-i D. n-i+1, n-i+1  ///不知道这题答案

　　8.下面C++程序的输出是              。

　　void f(char *x)

　　{

　　x++;

　　*x = ‘a’;

　　}

　　int main()

　　{

　　char str [ sizeof (“hello”)];

　　strcpy( str, “hello”);

　　f(str);

　　cout << str;

　　return 0;

　　}

　　A. hello B. hallo C. allo D.以上都不是

　　9.有以下程序，其执行结果是              。

　　char fun(char x, char y)

　　{

　　if(x) return y;

　　}

　　int main()

　　{

　　int a = ‘0’, b = ‘1’, c = ‘2’;

　　printf(“%c\n”, fun(fun(a, b), fun(b, c)));

　　}

　　A.函数调用出错 B.2 C.0 D.1

　　10.当n=6时，下列函数的返回值是              。

　　int foo (int n)

　　{

　　if(n <= 2) return n;

　　return foo(n-1) + foo(n-2);

　　}

　　A.1 B. 8 C. 13 D.21

　　(以下每题3分)

　　11.在一台主流配置的PC机上，调用f(35)所用的时间大概是              。

　　A. 几毫秒 B. 几秒 C.几分钟 D.几小时

　　12.在一棵度为4的树T中，有20个度为4的节点，10个度为3的节点，1个度为2的节点，10个度为1的节点，则树T的叶子个数为              。

　　A.41 B. 82 C. 113 D.122

　　13.有堆栈S，按顺序ABCD进栈，则出栈顺序不可能存在的是              。

　　A. DCBA B. BACD C. BADC D. CABD

　　14. 使用二分查找在有序数组a[n]中查找一个元素x的时间复杂度              。

　　A. O(n) B. O(n2) C. O(log n) D. O(n logn)

　　15. 图中标出了每条有向公路最大流量，请问从S到T最大流量是              。

　　A.46 B. 47 C. 54 D.77

　　16. 一天，有为年轻人来到张老板的店里花80元买了件原价为160元的纪念品。这件礼物的成本是65元。结账时，年轻人掏出一张100元，张老板当时没有零钱，就用那100元向隔壁店家换了零钱，找给年轻人20元。但是隔壁店家后来发现那100元是假钞，张老板无奈还了100元。那么，张老板在这次交易中实际损失了              元钱。

　　A. 65 B. 85 C. 100 D.185

　　17. 2^100 mod 7 =              。

　　A. 2 B. 3 C. 4 D.5

　　18. 某公司在华东和华南两大区域开展业务，年底汇总业绩的时候发现，两大区域的月度客户转化率(=成为会员的客户数/访问店铺的客户数)分别提高了10%和5%，以下描述中正确的是              。

　　A.尽管各自的月度转化率都有提高，但公司的整体月度转化率仍有可能降低

　　B.市场对业务认可度提高，越来越多访问店铺的客户成为会员

　　C.华东区的客户更容易被转化，该公司应该把业务重点放在这个区域

　　D.华南区的客户更需要提高转化，该公司应该把业务重点放在这个区域

　　19. 一次有8个人参加的网球比赛，根据选手的实力，分别编号为1至8，1号最强，8号最弱，而实力差距小于等于2才有可能出现爆冷。8人进行1/4决赛，胜出的4人继续半决赛，直到冠军产生，问有可能获得冠军的编号最大的选手是              。

　　A. 4 B. 6 C. 7 D. 8

　　20. 某国家非常重男轻女，若一户人家生了一个女孩，便再要一个，直到生下男孩为止，假设生男生女概率相等，请问平均每户人家有              个女孩。

　　A. 0.5 B. 2/3 C. 1 D. 4/3

　　二、不定向选择(4题，每题5分，每题有1-5个正确选项，完全正确计5分，漏选记2分，不选记0分，多选、错选记-2分)

　　21. 以下有关C语言的说法中，错误的是              。

　　A.内存泄露一般是只程序申请了一块内存，使用完后，没有及时将这块内存释放，从而导致程序占用大量内存。

　　B.无法通过malloc(size_t)函数调用申请超过该机器物理内存大小的内存块。

　　C. 无法通过内存释放函数free(void *)直接将某块已经使用完的物理内存直接归还给操作系统

　　D. 可以通过内存分配函数malloc(size_t)直接申请物理内存。

　　22.下面关于二叉搜索树正确的说法包括              。

　　A.待删除节点有左子树和右子树，只能使用左子树的最大值节点替换待删除节点

　　B. 给定一棵二叉搜索树的前序和后序遍历结果，无法确定这棵二叉搜索树

　　C. 给定一棵二叉搜索树，根据节点值大小排序所需时间复杂度是线性的

　　D. 给定一棵二叉搜索树，可以在线性时间复杂度内转化为平衡二叉搜索树

　　23. 被称为中国与人的周玮，仅仅使用1分钟的时间就可以对16位数字开14次方。那么以下数字中，              不可能称为其候选答案。

　　A. 11.0 B. 12.0 C. 13.0 D. 14.0 E. 15.0

　　24. 有3个包，每个包里各放了两个球。包A里的球都是白球，包B里的球都是黑球，包C里的球一黑一白。现随机取一个包，并从中随机取一个球，发现该球是白色的，那么这个包里剩下的球也是白色的概率是              。

　　A. 0 B. 0.33 C. 0.5 D. 0.66 E. 1

　　三、填空与问答(5题，共30分)

　　25. (4分)某电子眼镜的分辨率为640×360;相当于在距离2.5米左右观看一个25英寸大小的屏幕，其长宽比为16:9。已知蓝牙4.0技术工作在2.4GHz频带，理论最大带宽为24Mbps，请问该眼镜是否可以通过该技术将每秒50帧真彩(24bits，每8个bit用于传输三原色中一种颜色)画面传输至其他屏幕上?如果是，请说明原因。如果否，请说明理论上大约多久才能传送一帧真彩画面。

　　26.(4分)将N条长度均为M的有序链表进行合并，合并以后的链表也保持有序，时间复杂度为 。

　　27.(6分)有ABCD四人，要在夜里过一座桥。他们通过这座桥分别耗时1、2、5、10分钟，只有一只手电，并且同时最多只能两个人一起过桥，请你安排过桥方案，能够使这四个人都过桥，且总共花的时间最短。需要给出所花费的时间以及具体方案。

　　28. (8分)下列代码是实现有序证书数组的二分查找(也称为折半查找)，请指出其中的bug。

　　int binary_search( int *array, int length, int key){

　　int start = 0, end = length – 1;

　　while(end > start){

　　int middle = (start + end) / 2;

　　int tmp = array[middle];

　　if(tmp < key){

　　start = middle;

　　}else if(tmp > key){

　　end = middle;

　　}else{

　　return middle;

　　}

　　}

　　return -1;

　　}

　　29.(8分)有种数据结构叫做跳跃列表(Skip List)，它是基于并联的链表随机化数据结构，其效率可比拟于二叉查找树(对于大多数操作需要O(n logn)平均时间)。它是按层建造的，底层是一个普通的有序链表，每个更高层都充当下面列表的“快速跑道”，这里在层i中的元素按概率1/p出现在层i+1中。平均起来，每个元素都在p/(p-1)个列表中出现，而最高层的元素(通常是在跳跃列表前端的一个特殊的头元素)在O(logpn)个列表中出现，调节p的大小可以在内存消耗和时间消耗上进行折中。试分析在该数据结构中查找一个元素的平均时间复杂度。