一、单选题（每题2分，共30分）

第1题. 下⾯C++代码⽤于求斐波那契数列，该数列第1、2项为1，以后各项均是前两项之和。下⾯有关说法错误的是( )。

int fiboA(int N){
	if(N==1 || N==2)
		return 1;
	return fiboA(N-1) + fiboA(N-2);
}
int fiboB(int N){
	if(N==1 || N==2)
		return 1;
	int last2=1, last1=1;
	int nowVal = 0;
	for(int i=2; i<N ;i++){
		nowVal = last1+last2;
		last2 = last1;
		last1 = nowVal;
	}
	return nowVal;
}

{{ select(1) }}

• fiboA( ) ⽤递归⽅式， fiboB() 循环⽅式
• fiboA( ) 更加符合斐波那契数列的数学定义，直观易于理解，⽽ fiboB() 需要将数学定义转换为计算机程序实现
• fiboA( ) 不仅仅更加符合数学定义，直观易于理解，且因代码量较少执⾏效率更⾼
• fiboB( ) 虽然代码量有所增加，但其执⾏效率更⾼

第2题. 下⾯C++代码以递归⽅式实现合并排序，并假设 merge (int T[], int R[], int s, int m, int t) 函数将有序（同样排序规则）的T[s..m]和T[m+1..t]归并到R[s..t]中。横线处应填上代码是( )。

void mergeSort(int SList[],int TList[], int s,int t,int len){
	if(s==t){
		TList[s] = SList[s];
		return ;
	} 
	int *T2 = new int[len]; //保存中间结果 
	int m = (s+t)/2;
	________;
	merge(T2, SList, s, m, t);
	delete T2;
	return ;
}

{{ select(2) }}

• mergeSort(SList, T2, s, m,len), mergeSort(SList, T2, m,t,len)
  

• mergeSort(SList, T2, s, m-1,len), mergeSort(SList, T2, m+1,t,len)
  

• mergeSort(SList, T2, s, m,len), mergeSort(SList, T2, m+1,t,len)
  

• mergeSort(SList, T2, s, m-1,len), mergeSort(SList, T2, m-1,t,len)
  

第3题. 阅读下⾯的C++代码，执⾏后其输出是( )。

#include<iostream>
using namespace std;
int stepCount = 0;
int fracA(int N){
	stepCount += 1;
	cout<<stepCount<<"->";
	int rtn = 1;
	for(int i=1;i<=N;i++)
		rtn *=i;
	return rtn;
}
int fracB(int N){
	stepCount += 1;
	cout<<stepCount<<"->";
	if(N==1)
		return 1;
	return N*fracB(N-1); 
}
int main(){
	cout<<fracA(5);
	cout<<"<===>";
	cout<<fracB(5);
	return 0;
}

{{ select(3) }}

• 1->120<===>2->120
  

• 1->120<===>1->120
  

• 1->120<===>1->2->3->4->5->120
  

• 1->120<===>2->3->4->5->6->120
  

第4题. 下⾯的C++⽤于对 lstA 排序，使得偶数在前奇数在后，横线处应填⼊( )。

bool isEven(int N){
	return N%2==0;
}
void swap(int &a,int &b){
	int t;
	t=a,a=b,b=t;
	return;
}
void sortA(int lstA[],int n){
	int i,j,t;
	for(int i=n-1; i>0; i--)
		for(int j=0;j<i;j++)
			if(________)
				swap(lstA[j], lstA[j+1]);
	return;
}

{{ select(4) }}

• !isEven(lstA[j]) && isEven(lstA[j+1])
• isEven(lstA[j]) && !isEven(lstA[j+1])
• lstA[j] > lstA[j+1]
• lstA[j] < lstA[j+1]

第5题. 下⾯的C++代码⽤于将字符串保存到带头节点的双向链表中，并对重复的串计数，然后将最新访问的串的节点放在链头便于查找。横线处应填⼊代码是（ ）。

typedef struct Node{
	string str;
	int ref;
	struct Node *next, *prev;
}Node;
Node *Insert(Node *pHead, string s){
	Node *p = pHead->next;
	Node *q;
	while(p){
		if(p->str == s){
			p->ref++;
			p->next->prev = p->prev;
			p->prev->next = p->next;
			break;
		}
		p = p->next;
	}
	if(!p){
		p = new Node;
		p->str = s;
		p->ref = 0;
		p->next = p->prev = NULL;
	}
	________
	pHead->next = p, p->prev = pHead;
	return pHead;
}

{{ select(5) }}

• if(pHead) {p->next = pHead->next, pHead->next->prev = p;}
  

• if(pHead->next) {p->next = pHead->next, pHead->next->prev = p;}
  

• p->next = pHead->next, pHead->next->prev = p;
  

• 触发异常，不能对空指针进⾏操作

第6题. 有关下⾯C++代码说法正确的是（ ）。

int rc;
int foo(int x,int y){
	int r;
	if(y==0)
		r=x;
	else{
		r = foo(y,x%y);
		rc++;
	}
	return r;
}

{{ select(6) }}

• 如果 x ⼩于10， rc 值也不会超过20
• foo 可能⽆限递归
• foo 可以求出 x 和 y 的最⼤公共质因⼦
• foo 能够求出 x 和 y 的最⼩公倍数

第7题. 下⾯的C++代码实现对list的快速排序，有关说法，错误的是（ ）。

vector<int> operator +(vector<int>lA, vector<int>lB){
	vector<int>lst;
	for(int i=1; i<lA.size();i++)
		lst.push_back(lA[i]);
	for(int i=1; i<lB.size();i++)
		lst.push_back(lB[i]);
	return lst;
}
vector<int> qSort(vector<int>lst){
	if(lst.size()<2)
		return lst;
	int pivot = lst[0];
	vector<int>less, greater;
	for(int i=1; i<lst.size();i++)
		if(lst[i] <= pivot) less.push_back(lst[i]);
		else greater.push_back(lst[i]);
	for(int i=1; i<lst.size();i++)
		if(lst[i] <= pivot) less.push_back(lst[i]);
		else greater.push_back(lst[i]);
	return ________;
}

{{ select(7) }}

• qSort(less) + qSort(greater) + (vector<int>)pivot
  

• (vector<int>)pivot + (qSort(less) + qSort(greater))
  

• (qSort(less) + (vector<int>)pivot + qSort(greater))
  

•   qSort(less) + pivot + qSort(greater)
  

第8题. 下⾯C++代码中的 isPrimeA() 和 isPrimeB() 都⽤于判断参数N是否素数，有关其时间复杂度的正确说 法是（ ）。

bool isPrimeA(int N){
	if(N<2)
		return false;
	for(int i=2; i<=N/2; i++)
		if(N%i==0)
			return false;
	return true;
}
bool isPrimeB(int N){
	if(N<2)
		return false;
	for(int i=2; i<=sqrt(N);i++)
		if(N%i==0)
			return false;
	return true; 
}

{{ select(8) }}

• isPrimeA( ) 的最坏时间复杂度是$O({N\over2})$ ， isPrimeB( ) 的最坏时间复杂度是$O(log N)$ ， isPrimeA() 优于 isPrimeB()
• isPrimeA() 的最坏时间复杂度是$O({N\over2})$ ， isPrimeB( ) 的最坏时间复杂度是$O(N^{1\over2})$ ， isPrimeB() 绝⼤多数情况下优于 isPrimeA()
• isPrimeA() 的最坏时间复杂度是$O(N^{1\over2})$ ， isPrimeB( ) 的最坏时间复杂度是 $O(N)$， isPrimeA( ) 优于isPrimeB( )
• isPrimeA() 的最坏时间复杂度是$O(log N)$ ， isPrimeB( ) 的最坏时间复杂度是 $O(N)$， isPrimeA() 优于isPrimeB( )

第9题. 下⾯C++代码⽤于有序 list 的⼆分查找，有关说法错误的是（ ）。

int _binarySearch(vector<int> lst, int Low, int High, int Target){
	if(Low > High)
		return -1;
	int Mid = (Low+High)/2;
	if(Target == lst[Mid])
		return Mid;
	else if (Target < lst[Mid])
		return _binarySearch(lst, Low, Mid-1, Target);
	else 
		return _binarySearch(lst, Mid+1, High, Target); 
}
int bSearch(vector<int>lst, int Val){
	return _binarySearch(lst, 0, lst.size(), Val);
}

{{ select(9) }}

• 代码采⽤⼆分法实现有序 list 的查找
• 代码采⽤分治算法实现有序 list 的查找
• 代码采⽤递归⽅式实现有序 list 的查找
• 代码采⽤动态规划算法实现有序 list 的查找

第10题. 在上题的 _binarySearch 算法中，如果 lst 中有 N 个元素，其时间复杂度是（ ）。

{{ select(10) }}

• $O(N)$
• $O(log N)$
• $O(N log N)$
• $O(N^2)$

第11题. 下⾯的C++代码使⽤数组模拟整数加法，可以处理超出⼤整数范围的加法运算。横线处应填⼊代码是（ ）。

vector<int> operator +(vector<int> a, vector<int> b){
	vector<int> c;
	int t=0;
	for(int i=0;i<a.size() || i<b.size();i++){
		if(i<a.size()) t = t+a[i];
		if(i<b.size()) t = t+b[i];
		________
	}
	if(t) c.push_back(t);
	return c;
}

{{ select(11) }}

• c.push_back(t % 10), t = t % 10;
  

• c.push_back(t / 10), t = t % 10;
  

• c.push_back(t / 10), t = t / 10;
  

• c.push_back(t % 10), t = t / 10;
  

第12题. 有关下⾯C++代码的说法正确的是（ ）。

class Node{
	public:
		int Value;
		Node* Prev;
		Node* Next;
		Node(int Val, Node* Prv=NULL, Node* Nxt=NULL);
};
Node::Node(int Val, Node* Prv, Node* Nxt){
	this->Value = Val;
	this->Prev = Prv;
	this->Next = Nxt;
}
int main(){
	Node firstNode = Node(10);
	firstNode.Next = new Node(100, &firstNode);
	firstNode.Next->Next = new Node(111, firstNode.Next);
	return 0;
}

{{ select(12) }}

• 上述代码构成单向链表
• 上述代码构成双向链表
• 上述代码构成循环链表
• 上述代码构成指针链表

第13题. 通讯卫星在通信⽹络系统中主要起到（）的作⽤。

{{ select(13) }}

• 信息过滤
• 信号中继
• 避免攻击
• 数据加密

第14题. ⼩杨想编写⼀个判断任意输⼊的整数N是否为素数的程序，下⾯哪个⽅法不合适（）。

{{ select(14) }}

• 埃⽒筛法
• 线性筛法
• ⼆分答案
• 枚举法

第15题. 下⾯的排序算法都要处理多趟数据，哪种排序算法不能保证在下⼀趟处理时从待处理数据中选出最⼤或最⼩的数据（ ）。

{{ select(15) }}

• 选择排序
• 快速排序
• 堆排序
• 冒泡排序

二、判断题（每题2分，共20分）

第16题. 归并排序的时间复杂度是$O(N log N)$。（ ） {{ select(16) }}

• √
• ×

第17题. ⼩杨在⽣⽇聚会时拿⼀块H*W的巧克⼒招待来的K个⼩朋友，保证每位⼩朋友⾄少能获得⼀块相同⼤⼩的巧克⼒。那么⼩杨想分出来最⼤边长的巧克⼒可以使⽤⼆分法。（ ） {{ select(17) }}

• √
• ×

第18题. 以下C++代码能以递归⽅式实现斐波那契数列，该数列第1、2项为1，以后各项均是前两项之和。（ ）

int Fibo(int N){
	if(N==1 || N==2)
		return 1;
	else{
		int m=fiboA(N-1);
		int n=fiboB(N-2);
		return m+n;
	}
}

{{ select(18) }}

• √
• ×

第19题. 贪⼼算法可以达到局部最优，但可能不是全局最优解。（ ）

{{ select(19) }}

• √
• ×

第20题. ⼩杨设计了⼀个拆数程序，它能够将任意的⾮质数⾃然数N转换成若⼲个质数的乘积，这个程序是可以设计出来的。（ ）

{{ select(20) }}

• √
• ×

第21题. 插⼊排序有时⽐快速排序时间复杂度更低 。（ ）

{{ select(21) }}

• √
• ×

第22题. 下⾯的C++代码能实现⼗进制正整数N转换为⼋进制并输出。（ ）

char s[10];
int main(){
	int N;
	cin>>N;
	string rst="";
	while(N!=0){
		s[0]=N%8+'0';
		rst += string(s);
		N /= 8;
	}
	cout<<rst<<endl;
}

{{ select(22) }}

• √
• ×

第23题. 对数组 int arr[] = {2, 6, 3, 5, 4, 8, 1, 0, 9, 10} 执⾏ sort(arr, arr+10) ，则执⾏后 arr 中的数据调整为 {0, 1, 2, 3, 4, 5, 6, 8,9, 10}。（ ）

{{ select(23) }}

• √
• ×

第24题. ⼩杨想写⼀个程序来算出正整数N有多少个因数，经过思考他写出了⼀个重复没有超过N/2次的循环就能够算出来了。（ ）

{{ select(24) }}

• √
• ×

第25题. 同样的整数序列分别保存在单链表和双向链中，这两种链表上的简单冒泡排序的复杂度相同。（ ）

{{ select(25) }}

• √
• ×