一、单选题(每题 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;
}
A. fiboA( ) ⽤递归⽅式,fiboB() 循环⽅式 B. fiboA( ) 更加符合斐波那契数列的数学定义,直观易于理解,⽽fiboB() 需要将数学定义转换为计算机程序实现 C. fiboA( ) 不仅仅更加符合数学定义,直观易于理解,且因代码量较少执⾏效率更⾼ D. fiboB( ) 虽然代码量有所增加,但其执⾏效率更⾼ 【答案】C 【考纲知识点】算法知识点 【解析】fiboA 是很好理解的,但是执行效率不高,有的计算是重复的,导致效率低。 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 ;
}
A. mergeSort(SList, T2, s, m,len), mergeSort(SList, T2, m,t,len) B. mergeSort(SList, T2, s, m-1,len), mergeSort(SList, T2, m+1,t,len) C. mergeSort(SList, T2, s, m,len), mergeSort(SList, T2, m+1,t,len) D. mergeSort(SList, T2, s, m-1,len), mergeSort(SList, T2, m-1,t,len) 【答案】C 【考纲知识点】算法知识点 【解析】本题考察归并排序。归并排序需要先将排序序列一分为二,左边的元素的区间是[s,m],右边元素区间是[m+1,t],然后递归排序两个子序列后,将有序的子序列合并。 3、阅读下⾯的 C++代码 ,执⾏后其输出是( )。
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;
}
A. 1->120<===>2->120 B. 1->120<===>1->120 C. 1->120<===>1->2->3->4->5->120 D. 1->120<===>2->3->4->5->6->120 【答案】D 【考纲知识点】算法知识点 【解析】本题考察递归算法。输出 fracA 函数,是先输出1,再输出5 的阶乘,120;23行代码,执行fracB函数,此时stepCount从2开始计数,依次输出2/3/4/5/6,再输出 5 的阶乘 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(i=n-1;i>0;i--){
for(j=0;j<i;j++){
if(_______){ //在此处填写代码
swap(lstA[j],lstA[j+1]);
}
}
}
return;
}
A. !isEven(lstA[j]) && isEven(lstA[j+1]) B. isEven(lstA[j]) && !isEven(lstA[j+1]) C. lstA[j] > lstA[j+1] D. lstA[j] < lstA[j+1] 【答案】A 【考纲知识点】排序算法知识点 【解析】本题考察排序算法。前一个数字,下标是 j 的数字是偶数,后面的数字下标是 j+1 的是奇数,按照要求,偶数在奇数的后面,要交换。A 符合题意条件。 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;
}
A. if(pHead) {p->next = pHead->next, pHead->next->prev = p;} B. if(pHead->next) {p->next = pHead->next, pHead->next->prev = p;} C. p->next = pHead->next, pHead->next->prev = p; D. 触发异常 ,不能对空指针进⾏操作。 【答案】B 【考纲知识点】指针知识点 【解析】本题考察双链表知识点。每个节点需要 2 个指针,指向前驱节点和后继节点。按照要求,新的节点要求插入到链表头部。头节点和新插入的节点都需要修改。B 选项能够完成新节点的插入。 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;
}
A. 如果 x ⼩于 10, rc 值也不会超过 20 B. foo 可能⽆限递归 C. foo 可以求出 x 和 y 的最⼤公共质因⼦ D. foo 能够求出 x 和 y 的最⼩公倍数 【答案】A 【考纲知识点】数学知识点 【解析】本题考察数学算法,求最大公约数。这是典型的最大公约数写法的变形。排除法选 A。 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______________________;
}
A. qSort(less) + qSort(greater) + (vector)pivot B. (vector)pivot + (qSort(less) + qSort(greater)) C. (qSort(less) + (vector)pivot + qSort(greater)) D. qSort(less) + pivot + qSort(greater) 【答案】C 【考纲知识点】排序算法知识点 【解析】本题考察快速排序。Less 数组保存的是小于等于pivot,然后加上pivot元素,再加上大于等于 pivot 的数组。 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;
}
A. isPrimeA( ) 的最坏时间复杂度是 O(N/2),isPrimeB( ) 的最坏时间复杂度是O(logN),isPrimeA() 优于 isPrimeB() B. isPrimeA() 的最坏时间复杂度是 0(N/2),isPrimeB( ) 的最坏时间复杂度是O(N12),isPrimeB() 绝⼤多数情况下优于 isPrimeA() C. isPrimeA() 的最坏时间复杂度是 0(N1/2) ,isPrimeB( ) 的最坏时间复杂度是O(N),isPrimeA( ) 优于 isPrimeB( ) D. isPrimeA() 的最坏时间复杂度是 0(logN) ,isPrimeB( ) 的最坏时间复杂度是 O(N),isPrimeA() 优于 isPrimeB( ) 【答案】B 【考纲知识点】数学知识点 【解析】本题考察数学知识,判断质数。A 函数时间复杂度是O(n/2),B 函数算法是 O(sqrt(n)),大部分情况后者是优的,值更小。 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);
}
A. 代码采⽤⼆分法实现有序 list 的查找 B. 代码采⽤分治算法实现有序 list 的查找 C. 代码采⽤递归⽅式实现有序 list 的查找 D. 代码采⽤动态规划算法实现有序 list 的查找 【答案】D 【考纲知识点】算法知识点 【解析】本题考察算法知识点。二分法每次规模减半,查找平均时间复杂度是B。 10、在上题的_binarySearch 算法中,如果 l st 中有 N 个元素,其时间复杂度是()。 A. O(N) B. O(logN) C. O(NlogN) D. O(N2) 【答案】B 【考纲知识点】算法知识点 【解析】本题考察算法知识点。二分法每次规模减半,单词查找平均时间复杂度是 B。 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;
}
A. c.push_back(t % 10), t = t % 10; B. c.push_back(t / 10), t = t % 10; C. c.push_back(t / 10), t = t / 10; D. c.push_back(t % 10), t = t / 10; 【答案】D 【考纲知识点】算法知识点 【解析】本题考察高精度知识点。每次保存对应位和的最低位数字,去掉最低位数字后,保持进位,循环执行。 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);
}
A. 上述代码构成单向链表 B. 上述代码构成双向链表 C. 上述代码构成循环链表 D. 上述代码构成指针链表 【答案】B 【考纲知识点】链表知识点 【解析】本题考察链表知识点。每个节点指向自己前一个节点和后一个节点,因此是双向链表。 13、通讯卫星在通信⽹络系统中主要起到() 的作⽤。 A. 信息过滤 B. 信号中继 C. 避免攻击 D. 数据加密 【答案】B 【考纲知识点】计算机基础知识 【解析】本题考察计算机基础知识。通信卫星可以转发无线电信号,实现通信地球站间或地球站与航天器间的无线电通信,因此具有信号中继作用。选B。 14、⼩杨想编写⼀个判断任意输⼊的整数 N 是否为素数的程序,下⾯哪个⽅法不合适? ( ) A. 埃⽒筛法 B. 线性筛法 C. ⼆分答案 D. 枚举法 【答案】C 【考纲知识点】数学知识 【解析】本题考察数学知识。线筛和埃筛都可以判断素数,枚举也可以,二分规模减半,不能合理判断。 15、下⾯的排序算法都要处理多趟数据 ,哪种排序算法不能保证在下⼀趟处理时从待处理数据中选出最⼤或最 ⼩的数据? ( ) A. 选择排序 B. 快速排序 C. 堆排序 D. 冒泡排序 【答案】B 【考纲知识点】排序算法知识 【解析】本题考察排序算法知识。需要了解每种排序算法的特点。快速排序是选定一个数字,每次把比它小的放在左边,比元素大的放在右边,不能确定最值。
(责任编辑:lizq) |