题目系个人错题整理，处于无序状态，可ctrl+F搜索需要的题目，有疑问请在评论区提出，如果本文对您有帮助，请转发向朋友推荐~

  • T(n)表示某个算法输入规模为 n 时的运算次数。如果 T(1)为常数，且有递归式 T(n) = 2*T(n / 2) + 2n，那么 T(n) = （ ）。

A. Θ(n)
B. Θ(n log n)
C. Θ(n2)
D. Θ(n2 log n)

相当于归并排序，每次把n分成两个子问题（n/2），合并的代价为n，共有logn层，每层需 O （ n ） O（n） O（n）,故答案为B

  • （ ）的平均时间复杂度为 O(n log n)，其中 n 是待排序的元素个数。

A. 快速排序
B. 插入排序
C. 冒泡排序
D. 归并排序
正确答案： AD

AD的时间复杂度为 O （ n l o g n ） O（nlogn） O（nlogn）,冒泡和插入为 O ( n 2 ) O(n^2) O(n2) ( 选 择 排 序 也 是 O （ n 2 ） (选择排序也是O（n^2） (选择排序也是O（n2）

  • 以 A_0A （NOIP2013：18）
    0
    ​ 作为起点，对下面的无向图进行深度优先遍历时（遍历的顺序与顶点字母的下标无关），最后一个遍历到的顶点可能是（ ）。

A. A_1A
1
​
B. A_2A
2
​
C. A_3A
3
​
D. A_4A
4
​
要遍历到a4肯定先过a1，所以A不可能

要遍历到a2：

  • 先到a1，那么此时a3是最后的
  • 先到a3，那么此时a4是最后的
    所以a2也不可能

CD都可能

  • （ ）属于 NP 类问题。

A. 存在一个 P 类问题
B. 任何一个 P 类问题
C. 任何一个不属于 P 类的问题
D. 任何一个在（输入规模的）指数时间内能够解决的问题

P类问题都属于NP类问题。

不属于P类问题的不一定是NP

指数时间不一定是NP

TCP协议属于哪一层协议( ).

A. 应用层
B. 传输层
C. 网络层
D. 数据链路层

TCP属于传输层协议（T->transfer）

下列几个32位IP地址中，书写错误的是( ).

A. 162.105.128.27
B. 192.168.0.1
C. 256.256.129.1
D. 10.0.0.1

32位IP地址四个位置都在0~255之间

对长度位n的有序单链表，若检索每个元素的概率相等，则顺序检索到表中任一元素的平均检索长度为( ).

A. n/2
B. (n+1)/2
C. (n-1)/2
D. n/4
正确答案： B

平 均 检 索 长 度 为 （ 1 + 2 + 3 + 。 。 。 + n ） / n = ( n + 1 ) / 2 平均检索长度为（1+2+3+。。。+n）/n=(n+1)/2 平均检索长度为（1+2+3+。。。+n）/n=(n+1)/2

若有变量 int a, float x, y, 且 a=7, x=2.5, y=4.7, 则表达式 x+a%3*(int)(x+y)%2/4的值大约是( ).

A. 2.500000
B. 2.750000
C. 3.500000
D. 0.000000

x+a%3*(int)(x+y)%2/4=2.5+1*1/4=2.5+0=2.5

故选A

第 11 题
有以下结构体说明和变量定义，如图所示，指针p、q、r分别指向一个链表中的三个续结点。

struct node {
int data;
struct node *next;
} *p,*q,*r;
现要将q和r所指结点的先后位置交换，同时要保持链表的连续，以下程序段中错误的是( )

A. q->next = r->next; p-> next = r; r->next = q;
B. p->next = r; q->next = r->next; r->next = q;
C. q->next = r->next; r->next = q; p->next = r;
D. r->next = q; q->next = r->next; p->next = r;

D中r的next已经更新了，下一步q的next就不能指过去了

同时查找2n 个数中的最大值和最小值，最少比较次数为( ).

A. 3(n-2)/2
B. 4n-2
C. 3n-2
D. 2n-2
现将数字两两比较分成两组：n

每一组中比较n-1次分别找到最小值或最大值

答案为： n + n − 1 + n − 1 = 3 n − 2 n+n-1+n-1=3n-2 n+n−1+n−1=3n−2

下列( )软件属于操作系统软件。

A. Microsoft Word
B. Windows XP
C. Android
D. Mac OS X
E. Oracle
正确答案： BCD

E是数据库，A是Microsoft Office Word是微软公司的一个文字处理器应用程序。并非软件。

在数据压缩编码的应用中，哈夫曼（Huffman）算法是一种采用了（ ）思想的算法。

A. 贪心
B. 分治
C. 递推
D. 回溯
正确答案： A

哈夫曼算法用了贪心思想

以下属于操作系统的有（ ）。

A. Windows XP
B. UNIX
C. Linux
D. Mac OS
正确答案： ABCD

第 9 题
9.某计算机的 CPU 和内存之间的地址总线宽度是 32 位（bit），这台计算机最多可以使用（ ）的内存。

A. 2GB
B. 4GB
C. 8GB
D. 16GB
正确答案： B

内存是2^32

因为1GB=2^30

所以 4 G B = 2 30 × 4 = 2 32 4GB=2^{30}\times4= 2^{32} 4GB=230×4=232

以下属于无线通信技术的有（ ）。

A. 蓝牙
B. WiFi
C. GPRS
D. 以太网

ABC

GPRS是通用分组无线服务技术。

第 3 题
分辨率为 1600x900、16 位色的位图，存储图像信息所需的空间为（ ）。

A. 2812.5KB
B. 4218.75KB
C. 4320KB
D. 2880KB
正确答案： A

8位一个字节，然后有16位，说明有两个字节，然后

1600 × 900 × 2 1024 = 2814.5 1600 \times 900 \times \frac{2}{1024}=2814.5 1600×900×10242​=2814.5

第 9 题
将 7 个名额分给 4 个不同的班级，允许有的班级没有名额，有（ ）种不 同的分配方案。

A. 60
B. 84
C. 96
D. 120
正确答案： D

这种问题是允许有些组中分到的元素为“0”，也就是组中可以为空的。对于这样的题，我们就首先将每组都填上1个，这样所要元素总数就m个，问题也就是转变成将（n+m）个元素分到m组，并且每组至少分到一个的问题，也就可以用插板法来解决。
所以总名额为:7+4x1=11;
得c(11-1,4-3) ，120种方法.

第 2 题
下列属于解释执行的程序设计语言是

A. C
B. C++
C. Pascal
D. Python
正确答案： D

其他三项都是编译执行。

编译执行是指最后都写完了统一编译一下，解释执行是写一行执行一行。