1. 在二进制下，$1011001+(\ \ \ )=1100110$。{{ select(1) }}

• $1011$
• $1101$
• $1010$
• $1111$

2. 字符 A 的 ASCII 码为十六进制 $41$，则字符 Z 的 ASCII 码为十六进制的（ ）。{{ select(2) }}

• $(66)_{16}$
• $(5\text{A})_{16}$
• $(50)_{16}$
• 视具体的计算机而定

3. 下图是一棵二叉树，它的先序遍历是（ ）。{{ select(3) }}

• $\texttt{ABDEFC}$
• $\texttt{DBEFAC}$
• $\texttt{DFEBCA}$
• $\texttt{ABCDEF}$

4. 寄存器是（ ）的重要组成部分。{{ select(4) }}

• 硬盘
• 高速缓存
• 内存
• 中央处理器（CPU）

5. 广度优先搜索时，需要用到的数据结构是（ ）。{{ select(5) }}

• 链表
• 队列
• 栈
• 散列表

6. 在使用高级语言编写程序时，一般提到的“空间复杂度”中的空间是指（ ）。{{ select(6) }}

• 程序运行时理论上所占的内存空间
• 程序运行时理论上所占的数组空间
• 程序运行时理论上所占的硬盘空间
• 程序源文件理论上所占的硬盘空间

7. 应用快速排序的分治思想，可以实现一个求第 $k$ 大数的程序。假定不考虑极端的最坏情况，理论上可以实现的最低的算法时间复杂度为（ ）。{{ select(7) }}

• $\Theta(n^2)$
• $\Theta(n \log n)$
• $\Theta(n)$
• $\Theta(1)$

8. 为解决 web 应用中的不兼容问题，保障信息的顺利流通，（ ）制定了一系列标准，涉及 HTML、XML、CSS 等，并建议开发者遵循。{{ select(8) }}

• 微软
• 美国计算机协会（ACM）
• 联合国教科文组织
• 万维网联盟（W3C）

9. 体育课的铃声响了，同学们都陆续的奔向操场，按老师的要求从高到低站成一排。每个同学按顺序来到操场时，都从排尾走到排头，找到第一个比自己高的同学，并站在他的后面。这种站队的方法类似于（ ）算法。{{ select(9) }}

• 快速排序
• 插入排序
• 冒泡排序
• 归并排序

10. 1956年（ ）授予肖克利（William Shockley）、巴丁（John Bardeen）和布拉顿（Walter Brattain）{{ select(10) }}

• 诺贝尔物理学奖
• 约翰·冯·诺依曼奖
• 图灵奖
• 高德纳奖 （Donald E. Knuth Prize）

11. 如果根结点的深度记为 $1$，则一棵恰有 $2011$ 个叶子结点的二叉树的深度可能是（ ）。{{ multiselect(11) }}

• $10$
• $11$
• $12$
• $2011$

12. 在布尔逻辑中，逻辑“或”的性质有（ ）。{{ multiselect(12) }}

• 交换律：$P∨Q=Q∨P$
• 结合律：$P∨(Q∨R)=(P∨Q)∨R$
• 幂等律：$P∨P=P$
• 有界律：$P∨1=1$

13. 一个正整数在十六进制下有 $100$ 位，则它在二进制下可能有（ ）位。{{ multiselect(13) }}

• $399$
• $400$
• $401$
• $404$

14. 汇编语言（ ）。{{ multiselect(14) }}

• 是一种与具体硬件无关的程序设计语言
• 在编写复杂程序时，相对于高级语言而言代码量大，且不易调试
• 可以直接访问寄存器、内存单元、I/O 端口
• 随着高级语言的诞生，如今已被完全淘汰，不再使用

15. 现有一段文言文，要通过二进制哈夫曼编码进行压缩。简单起见，假设这段文言文只由 $4$ 个汉字“之”、“乎”、“者”、“也”组成，它们出现的次数分别为 $700,600,300,400$。那么，“也”字的编码长度可能是（ ）。{{ multiselect(15) }}

• $1$
• $2$
• $3$
• $4$

16. 生物特征识别，是利用人体本身的生物特征进行身份认证的一种技术。目前，指纹识别、虹膜识别、人脸识别等技术已广泛应用于政府、银行、安全防卫等领域。以下属于生物特征识别技术及其应用的是（ ）。{{ multiselect(16) }}

• 指静脉验证
• 步态验证
• ATM机密码验证
• 声音验证

17. 对于序列 $7,5,1,9,3,6,8,4$，在不改变顺序的情况下，去掉（ ）会使逆序对的个数减少 $3$。{{ multiselect(17) }}

• $7$
• $5$
• $3$
• $6$

18. 计算机中的数值信息分为整数和实数（浮点数）。实数之所以能够表示很大或者很小的数，是由于使用了（ ）。{{ multiselect(18) }}

• 阶码
• 补码
• 反码
• 较长的尾数

19. 对下图使用 Dijkstra 算法计算 $S$ 点到其余各点的最短路径长度时，到 $B$ 点的距离 $d_B$ 初始时赋为 $8$，在算法的执行过程中还会出现的值有（ ）。{{ multiselect(19) }}

• $3$
• $7$
• $6$
• $5$

20. 为计算机网络中进行数据交换而建立的规则、标准或约定的集合称为网络协议。下列英文缩写中，（ ）是网络协议。{{ multiselect(20) }}

• HTTP
• TCP/IP
• FTP
• WWW

21. 平面图可以在画在平面上，且它的边仅在顶点上才能相交的简单无向图。$4$ 个顶点的平面图至少有 $6$ 条边，如下图所示。那么，$5$ 个顶点的平面图至少有 {{ input(21) }} 条边。

22. 定义一种字符串操作，一次可以将其中一个元素移到任意位置。举例说明，对于字符串 $\texttt{BCA}$ 可以将 $\texttt{A}$ 移到 $\texttt{B}$ 之前，变字符串 $\texttt{ABC}$。如果要将字符串 $\texttt{DACHEBGIF}$ 变成 $\texttt{ABCDEFGHI}$ 最少需要 {{ input(22) }} 次。
23. 读程序写结果

#include<iostream>
#include<cstring>
using namespace std;
const int SIZE = 100;
int main()
{
	int n,i,sum,x,a[SIZE];
	
	cin>>n;
	memset(a,0,sizeof(a));
	
	for(i=1;i<=n;i++){
		cin>>x;
		a[x]++;
	}
	i=0;
	sum=0;
	while(sum<(n/2+1)){
		i++;
		sum+=a[i];
	}
	cout<<i<<endl;
	return 0;
}

输入：

11
4 5 6 6 4 3 3 2 3 2 1

输出：{{ input(23) }}

24. 读程序写结果

#include<iostream>
using namespace std;
int n;
void f2(int x,int y);
void f1(int x,int y)
{
	if(x<n)
		f2(y,x+y);
}
void f2(int x,int y)
{
	cout<<x<<' ';
	f1(y,x+y);
}
int main()
{
	cin>>n;
	f1(0,1);
	return 0;

	return 0;
}

输入：30

输出：{{ input(24) }}

25. 读程序写结果

#include<iostream>
using namespace std;
const int V=100;
int n,m,ans,e[V][V];
bool visited[V];
void dfs(int x,int len)
{
	int i;
	visited[x]= true;
	if(len>ans)
	   ans=len;
	for(i=1;i<=n;i++)
	   if( (!visited[i]) && (e[x][i]!=-1) )
		  dfs(i,len+e[x][i]);
	visited[x]=false;
}
int main()
{
	int i,j,a,b,c;
	cin>>n>>m;
	for(i=1;i<=n;i++)
	   for(j=1;j<=m;j++)
		  e[i][j]=-1;
	for(i=1;i<=m;i++)
	{
		cin>>a>>b>>c;
		e[a][b]=c;
		e[b][a]=c;
	}
	for(i=1;i<=n;i++)
	   visited[i]=false;
	ans=0;
	for(i=1;i<=n;i++)
	   dfs(i,0);
	cout<<ans<<endl;
	return 0;
}

输入：

4 6
1 2 10
2 3 20
3 4 30
4 1 40
1 3 50
2 4 60

输出：{{ input(25) }}

26. 读程序写结果

#include<iostream>
#include<cstring>
#include<string>
using namespace std;
const int SIZE=10000;
const int LENGTH=10;
int n,m,a[SIZE][LENGTH];
int h(int u,int v)
{
    int ans,i;
    ans=0;
    for(i=1;i<=n;i++)
       if( a[u][i]!=a[v][i])
           ans++;
    return ans;
}
int main()
{
    int sum,i,j;
    cin>>n;
    memset(a,0,sizeof(a));
    m=1;
    while(1)
    {
        i=1;
        while( (i<=n) && (a[m][i]==1) )
            i++;
        if(i>n)
           break;
        m++;
        a[m][i]=1;
        for(j=i+1;j<=n;j++)
           a[m][j]=a[m-1][j];
    }
    sum=0;
    for(i=1;i<=m;i++)
       for(j=1;j<=m;j++)
          sum+=h(i,j);
    cout<<sum<<endl;
    return 0;
}

输入：7

输出：{{ input(26) }}

27. 完善程序

大整数开方：输入一个正整数 $n\ (1\le n\le 10^{100})$，试用二分法计算它的平方根的整数部分。

#include<iostream>
#include<string>
using namespace std;
const int SIZE=200;
struct hugeint{
    int len,num[SIZE];
};
//其中len表示大整数的位数；num[1]表示个位，num[2]表示十位，以此类推
hugeint times(hugeint a,hugeint b)
// 计算大整数a和b的乘积
{
    int i,j;
    hugeint ans;
    memset(ans.num,0,sizeof(ans.num));
    for(i=1;i<=a.len;i++)
       for(j=1;j<=b.len;j++)
                  ①      +=a.num[i]*b.num[j];  
    for(i=1;i<=a.len+b.len;i++){
        ans.num[i+1]+=ans.num[i]/10;
                 ②         ; 
    }
    if(ans.num[a.len+b.len]>0)
        ans.len=a.len+b.len;
    else
        ans.len=a.len+b.len-1;
    return ans;
}
hugeint add(hugeint a,hugeint b)
//计算大整数a和b 的和
{
    int i;
    hugeint ans;
    memset(ans.num,0,sizeof(ans.num));
    if(a.len>b.len)
        ans.len=a.len;
    else
        ans.len=b.len;
    for(i=1;i<=ans.len;i++){
        ans.num[i]+=         ③       ; 
        ans.num[i+1]+= ans.num[i]/10;
        ans.num[i]%=10;
    }
    if(ans.num[ans.len+1]>0)
        ans.len++;
    return ans;
}
hugeint average(hugeint a,hugeint b)
//计算大整数a和b的平均数的整数部分
{
    int i;
    hugeint ans;
    ans=add(a,b);
    for(i=ans.len;i>=2;i--){
        ans.num[i-1]+=(     ④      )*10; 
        ans.num[i]/=2;
    }
    ans.num[1]/=2;
    if(ans.num[ans.len]==0)
        ans.len--;
    return ans;
}
hugeint plustwo(hugeint a)
// 计算大整数a加2之后的结果
{
    int i;
    hugeint ans;
    ans=a;
    ans.num[1]+=2;
    i=1;
    while( (i<=ans.len)&&(ans.num[i]>=10) ){
        ans.num[i+1]+=ans.num[i]/10;
        ans.num[i]%=10;
        i++;
    }
    if(ans.num[ans.len+1]>0)
              ⑤    ; 
    return ans;
}
bool over(hugeint a,hugeint b)
// 若大整数a>b则返回true，否则返回false
{
    int i;
    if(      ⑥     )  
        return false;
    if( a.len>b.len )
        return true;
    for(i=a.len;i>=1;i--){
        if(a.num[i]<b.num[i])
           return false;
        if(a.num[i]>b.num[i])
           return true;
    }
    return false;
}
int main()
{
    string s;
    int i;
    hugeint target,left,middle,right;
    cin>>s;
    memset(target.num,0,sizeof(target.num));
    target.len=s.length();
    for(i=1;i<=target.len;i++)
        target.num[i]=s[target.len-i]-      ⑦    ;
    memset(left.num,0,sizeof(left.num));
    left.len=1;
    left.num[1]=1;
    right=target;
    do{
        middle=average(left,right);
        if(over(       ⑧        ))
            right=middle;
        else
            left=middle;
    }while(!over(plustwo(left),right) );
    for(i=left.len;i>=1;i--)
       cout<<left.num[i];
    return 0;
}

①填 {{ input(27) }}

②填 {{ input(28) }}

③填 {{ input(29) }}

④填 {{ input(30) }}

⑤填 {{ input(31) }}

⑥填 {{ input(32) }}

⑦填 {{ input(33) }}

⑧填 {{ input(34) }}

28. 完善程序

笛卡尔树：对于一个给定的两两不等的正整数序列，笛卡尔树是这样的一棵二叉树：首先，它是一个最小堆，即除了根结点，每个节点的权值都大于父节点的权值；其次，它的中序遍历恰好就是给定的序列。例如，对于序列 $7,2,12,1,10,5,15,3$，下图就是一棵对应的笛卡尔树。现输入序列的规模 $n\ (1≤n<100)$ 和序列的 n 个元素，试求其对应的笛卡尔树的深度 $d$（根节点深度为 $1$），以及有多少个叶子节点的深度为 $d$。

#include<iostream>
using namespace std;
const int SIZE=100+5;
const int INFINITY=1000000;
int n,a[SIZE],maxDeep,num;
void solve(int left,int right,int deep)
{
	int i,j,min;
	if(deep>maxDeep){
		maxDeep=deep;
		num=1;
	}
	else if(deep==maxDeep)
		①;  
	min= INFINITY;
	for(i=left;i<=right;i++)
		if(min>a[i]){
			min=a[i];
			②;   
		}
	if(left<j)
	③; 
	if(j<right)
	④;	 
}
int main()
{
	int i;
	cin>>n;
	for(i=1;i<=n;i++)
		cin>>a[i];
	maxDeep=0;
	solve(1,n,1);
	cout<<maxDeep<<' '<<num<<endl;
	return 0;
}

①填 {{ input(35) }}

②填 {{ input(36) }}

③填 {{ input(37) }}

④填 {{ input(38) }}