不是VIP会员,不能显示答案,请在后台“我的信息” 在线升级 VIP

一、单项选择题(共15题,每题2分,共计30分;每题有且仅有一个正确选项)

1. 在以下各项中,( )不是CPU的组成部分。

  • A.控制器
  • B.运算器
  • C.寄存器
  • D.主板

2. (2017)8+(1234)10的结果是( )。

  • A.(8E2)16
  • B.(100011100001)2
  • C.(8E0)16
  • D.(100011100011)2

3. 设A=B=True,C=D=False,逻辑运算表达式值为假的是( )。

  • A.(¬A∧B)∨(C∧D∨A)
  • B.¬((A∧B)∧C)∧D)
  • C.A∧(B∨C∨D)∨D
  • D.(A∧(D∨C))∧B

4. 若已知一个栈的人栈序列是1,2,3,...,n,输出序列为p1,p2,p3,...,pn,若p1=n,则pi为( )

  • A.i
  • B.n-i
  • C.n-i+1
  • D.不确定

5. 设S= “abbcce”,不同的非空子串个数有( )个 。

  • A.19
  • B.17
  • C.16
  • D.18

6. C++中,125^2的值是( ) 。

  • A.127
  • B.128
  • C.15625
  • D.126

7. 设某算法的计算时间表示为递推关系式T(n) =2T(n/2)+n(n为正整数)及T(O)=1,则该算法的时间复杂度为( ) 。

  • A.O(n)
  • B.O(n^2)
  • C.(nlogn)
  • D.(logn)

8. 下列有关二叉树的叙述,不正确的是( ) 。

  • A.二叉树的深度为k,那么最多有2^k-1个节点(k>=1)
  • B.在二叉树的第i层上,最多有2^(i-1)个节点(i>=1)
  • C.完全二叉树一定是满二叉树
  • D.堆是完全二又树

9. 下列排序算法中,平均时间复杂度是O(n^2)的是() 。

  • A.快速排序
  • B.插人排序
  • C.归并排序
  • D.堆排序

10. 下列哪些图一定可以进行黑白染色,使得相邻节点的颜色不同( ) 。

  • A.树
  • B.基环树
  • C.连通图
  • D.欧拉图

11. 下列不是操作系统的有( ) 。

  • A.Linux
  • B.Windows
  • C.Android
  • D.Wps

12. 下列关于算法的叙述中,错误的是( ) 。

  • A.算法代表着用系统的方法描绘解决问题的策略机制。
  • B.一个算法的好坏,只需要从时间复杂度这一方面进行考虑
  • C.一个算法必须具有有穷性、可行性、正确性、输入和输出
  • D.对于一些np完全问题,现在未能找到有效的算法解决

13. 下列叙述中正确的是( ) 。

  • A.线性表是线性结构
  • B.栈与队列是非线性结构
  • C.线性链表是非线性结构
  • D.二叉树是线性结构

14. 链表的( )操作需要O(n)的时间复杂度实现。

  • A.插人
  • B.定位
  • C.删除
  • D.合并

15. NOI比赛,下列选项中可以带入考场的是( )。

  • A.健盘
  • B.参考书籍
  • C.U盘
  • D.铅笔

二、阅读程序(程序输入不超过数组或字符串定义的范围;除特殊说明外,判断题1.5分,选择题4分,共计40分)

1.

#include <iostream>
using namespace std;
int n,k,ans;
int main()
{
cin>>n>>k;
int ans=0;
while(n)
{
if(n%k>0) ans++;
n/=k;
}
cout<< ans<< endl;
return 0;
}

判断题

1) (1分)把第10行n%k>0改成n%k不影响程序运行结果。( )
2) 输入的k需要大于1。 ( )
3) 输入的n需要大于0。( )
4) 该算法的时间复杂度为O(log n)。( )


选择题

5) 输入125 5的输出结果为( )
6) 当n在int范围内时,输出的最大值为( )。

2.

#include<iostream>
using namespace std;
int equationCount(int n,int m)
{
if(n==1||m==1)
return 1;
else if(n<m)
return equationCount(n,n);
else if(n==m)
return 1+ equationCount(n,n-1);
else
return equationCount(n,m-1)+equationCount(n-m,m);
}
int main()
{
int n;
cin>>n;
cout<< equationCount(n,n) << endl;
return 0;
}

判断题

1) (1分)输入的n必须为正整数。( )
2) 把第9行的"else if(n==m)"和第10行的"return 1 + equationCount(n,n-1);"去掉,不影响程序运行结果。( )
3) 把第18行的“n,n”改成“n,n+1”不影响程序运行结果。( )
4) 把第7行的"else if(n<m)"和第8行的"return equationCount(n,n);"去掉,不影响程序运行结果。( )

选择题

5) 输入7的输出结果为().
6) 该算法的时间复杂度为()。

3.

#include<iostream>
using namespace std;
const int maxn=100000;
int a[maxn], b[maxn],n;
int Search(int num, int low, int high)
{
int mid;
while(low<=high)
{
mid=(low+ high)/2;
if(num>=b[mid]) low=mid+1;
else high=mid-1;
}
return low;
}
int main()
{
int len, pos;
cin>>n;
for(int i=1; i<=n; i++)
cin>>a[i];
b[1]=a[1];
len=1;
for(int i=2; i<=n; i++)
{
if(a[i]>=b[len])
{
len++;
b[len]=a[i];
}
else
{
pos=Search(a[i],1,len);
b[pos]=a[i];
}
}
cout<<len<<endl;
return 0;
}

判断题

1) (1分)输入的a[i]必须在[1,n]范围内。( )
2) (1分)把第11行的“mid+1” 改成“mid”不影响程序运行结果。( )
3) 当数组a单调不降时输出为1。( )
4) 数组b内的元素始终单调不降。()


选择题

5) 当输入第一行为20,第二行为 1 20 2 19 3 18 4 17...9 12 10 11时,输出为( )。
6) 该算法的时间复杂度为( )。

三、完善程序(单选题,每题3分,共计30分)

1. 完善程序(单选题,每题3分,共计30分)
1.给一个矩阵N* M,给你第i行1的个数和位置,让你选些行精确覆盖 M列(精确覆盖:每列有且只有1个1)。
例如:如下的矩阵:
11100001
10001110
10010110
00010010
00001100
就包含了这样一个集合(第1,4,5行)。
Input
多组数据,对于每组数据:
第一行两个整数N, M;
楼下来N行,每行开头一个整数x.表示该行上1的个数,接下来x个整数,每个1的位置。
Output
如果有解随意输出组集合,否则输出NO,中间空格隔开。

# include<bits/stdc++.h>
using namespace std;
# define ll long long
# define inf 10000000000
# define N 2005
# define M 2000005
int read()
{
int x=0,f=1; char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-') f=-1; ch=getchar();}
while(ch>='0'&&ch<='9') {x=x*10+ch-'0'; ch=getchar();}
return x*f;
}
int n,m;
int h[N],s[N],q[N];
int u[M],d[M],L[M],R[M],C[M],X[M];
void del(int c) //delete ROW C
{
___(1)___;
___(2)___;
for(int i=d[c]; i!=c; i=d[i])
for(int j=R[i]; j!=i; j=R[j])
u[d[j]]= u[j],d[u[j]]=d[j],s[C[j]]--;
}
void add(int c)
{
L[R[c]]= R[L[c]]=c;
for(int i=u[c]; i!=c; i=u[i])
for(int j=L[i]; j!=i; j=L[j])
u[d[j]]= d[u[j]]=j,s[C[j]]++;
}
void link(int r,int c)
{
static int size=0;size++;
X[size]=r;C[size]=c;
s[c]++;
d[size]= d[c]; u[size]=c;
u[d[size]]=size;
d[u[size]]=size;
if(h[r]==-1)
h[r]=L[size]=R[size]=size;
else
{
R[size]=R[h[r]];
L[size]= h[r];
L[R[size]]=size;
R[L[size]]= size;
}
}
bool dance(int k)
{
if(R[0]=0)
{
printf("%d" ,k);
for(int i=1; i<=k; i++)
printf(" %d",X[q[i]]);
puts("");
return 1;
}
int mn=inf,c;
for(int i= R[0]; i; i=R[i])
if(s[i]<mn) mn=s[i],c=i;
___(3)___;
for(int i=d[c]; i!=c; i=d[i])
{
q[k+1]=i;
for(int j=R[i]; j!=i; j=R[j]) ___(4)___;
if(dance(k+1)) return 1;
for(int j=L[i]; j!=i; j=L[j]) ___(5)___;
}
add(c);
return 0;
}
int main()
{
while(scanf("%d%d",&n,&m)!=EOF)
{
for(int i=0; i<=m; i++)
{
d[i]=u[i]=i;
L[i+1]=i;R[i]=i+1;
s[i]=0;
}
R[m]=0; size=m;
int x,y;
for(int i=1; i<=n; i++)
{
h[i]=-1;
x=read();
while(x--)
{
y=read();
link(i,y);
}
}
if(!dance(0)) puts("NO");
}
return 0;
}

选择题

1) ①处应填( )
2) ②处应填( )
3) ③处应填( )
4) ④处应填( )
5) ⑤处应填( )

2. (树的直径)给定一颗n个节点的树,每条边有个长度wi,求这棵树直径的长度。树的直径是指树的最长简单路。
做法:两次BFS。开始任选一点u作为起点进行BFS,找到最远的一点s,再从s再次BFS找到最远的一点t。s-t两点的路径长度就是直径的长度。

# include <iostream>
# include <cstring>
using namespace std;
const int inf= 0x3f3f3f3f; //假设的无穷大值,具体数值为1061109567
const int maxn=1005;
struct Node{
int to,w,next; //临接表节点,to表示这条边的终点,w表示这条边的长度,next表示下一条边的编号
} edge[maxn*2];
int head[maxn],tot; //head[u]表示u的临接表头节点的标号
int n; //节点树
int dis[maxn]; //离起点的距离
bool vis[maxn]; //某个点是否已经拜访过
int que[maxn],first,last; //队列
void init()
{
memset(head,-1,sizeof(head));
tot=0;
}
void addedge(int u,int v,int w)
{
edge[tot].to=v;
edge[tot].w= w;
edge[tot].next=head[u];
head[u]=tot++;
}
int BFS(int u)
{
first=last=0;
memset(dis,inf,sizeof(dis));
memset(vis,0, sizeof(vis));
dis[u]=0;
vis[u]=1;
que[last++]=u;
while(___(1)___)
{
u=que[first++];
for(int i=head[u]; i!=-1; i=edge[i].next)
{
int v=dege[i].to;
if(___(2)___)
{
vis[v]=1;
que[last++];
___(3)___;
}
}
}
int tmp=1;
for(int i=2; i<=n; i++)
if(___(4)___) tmp=i;
return tmp;
}
int main()
{
int u,v,w,s,t;
cin>>n;
init();
for(int i=1; i<n; i++)
{
cin>>u>>v>>w;
addedge(u,v,w);
addedge(v,u,w);
}
s=BFS(1);
___(5)___;
cout<< dis[t] << endl;
return 0;
}


选择题

1) ①处应填( )
2) ②处应填( )
3) ③处应填( )
4) ④处应填( )
5) ⑤处应填( )