一、单项选择题(共15题,每题2分,共计30分;每题有且仅有一个正确选项)
1.在内存储器中每个存储单元都被赋予一个唯一的序号,称为(
A.下标
B.地址
C.序号
D.编号
答案:B 解析:此时剩余的区间逐个选用,优先选用能和前一个区间连接的情况 下,右端点更靠右的区间
2.编译器的主要功能是()。
A.将源程序翻译成机器指令代码
B.将一种高级语言翻译成另一种高级语言
C.将源程序重新组合
D.将低级语言翻译成高级语言
答案 A: 解析:编译型:将源码直接转换为二进制代码,生成目标程序,然后将 目标程序连接成可执行的程序。流程为:高级语言源码—编译—>目标程序—连 接—>可执行程序
3.设 x=true,y=true,z=false,以下逻辑运算表达式值为真的是()。
A.(x∧y)∧z
B.x∧(zVy)∧z
C.(x∧y)V(zVx)
D.(yVz)AxAz
答案:C 解析:与:∧and&& 或:∨or|| 非:¬!NOT 异或:^ 优先级: 括号>非>与>异或,或
4.现有一张分辨率为2048x1024像素的32位真彩色图像。请问要存储这张图像,需要多大的存储空间?()。
A.4MB
B.8MB
C.32MB
D.16MB
解析:1 位为 1bit,1byte=8bit,2048*1024*32/8=8*(1024/1024)=8MB
5.冒泡排序算法的伪代码如下:
输入:数组L,n≥1。输出:按非递减顺序排序的L。
算法 Bubblesort:
FLAG ←n
while FLAG>1 do
k← FLAG -1
FLAG ←1
for j=1 to k do
if L(j)>L(j+1)then do
L(j)<> L(j+1)
FLAG← j
对n个数用以上冒泡排序算法进行排序,最少需要比较多少次?
A.n
B.n-2
C.n²
D.n-1
答案:D 解析:最少的比较次数就是数组本身已经有序,只需要比较 n-1 次;最 多的比较次数是 n*(n-1)/2;
6.设A是n个实数的数组,考虑下面的递归算法:
XYZ (A[1..n])
if n=l then return A[1]
else temp<XYZ(A[1..n-1])
if temp < A[n]
then return temp
else return A[n]
A请问算法 xYz的输出是什么?
A.A数组的平均
B.A数组的最小值
C.A数组的最大值
D.A数组的中值
7.链表不具有的特点是()
A.插入删除不需要移动元素
B.可随机访问任一元素
C.不必事先估计存储空间
D.所需空间与线性表长度成正比
答案:B 解析:可随机访问任一元素是线性表的特点。
8.有10个顶点的无向图至少应该有( )条边才能确保是一个连通图。
A.10
B.12
C.9
D.11
答案:C 解析:n 个顶点的无向图,至少需要 n-1 条边,才能构成连通图。
9.二进制数1011转换成十进制数是()。
A.10
B.13
C.11
D.12
答案:C 解析:1+2+8=11
10.五个小朋友并排站成一列,其中有两个小朋友是双胞胎,如果要求这两个双胞胎必须相邻,则有( )种不同排列方法
A.24
B. 36
C.72
D.48
答案:D 解析:捆绑法求解:两个双胞胎是一个单位,所以方案就是4 的全排列 4!==24,然后双胞胎自已的全排列是 2,得数是 24*2==48
答案:C 解析:简单数据结构常识题,典型的栈结构,先进后出 12.独根树的高度为 1。具有 61 个结点的完全二叉树的高度为(D)。
12.独根树的高度为1。具有61个结点的完全二叉树的高度为( )。
A.7
B.5
C.8
D.6
答案:D 解析:完全二叉树的性质:满二叉树是(2^高度-1),数一数也可以知道 了,floor(log2n)+1=6
13.干支纪年法是中国传统的纪年方法,由10个天干和12个地支组合成60个天干地支。由公历年份可以根据以下公式和表格换算出对应的天干地支。
天干=(公历年份)除以18所得余数
地支=(公历年份)除以12所得余数
例如,今年是 2020年,2020除以10余数为0,查表为“庚”:2020除以12余数为 4,查表为“子”,所以今年是庚子年。
请问1949年的天干地支是( )
A.己亥
B.已丑
C.已卯
D.已西
答案:B 解析:1949%10=9,因此是已 1949%12=5,因此是丑
14.10个三好学生名额分配到7个班级,每个班级至少有一个名额,一共有( )种不同的分配方案。
A.56
B.84
C.72
D.504
答案:B 解析:指“10个三好学生不加区分,分配进 7 个不同班级”,这样就是 插板法组合数 C 6 9 =84
15.有五副不同颜色的手套(共10只手套,每副手套左右手各1只),从中取6只手套,请问恰好能配成两副手套的不同取法有()种。
A.30
B.150
C.180
D.120
答案:D 解析:先从五双手套中取完整的两双,方案是组合数 C(5,2)==10; 然后,从剩下的三双中,取不同色的两只手段,是先从三双中取两双C(3,2)==3 然后,再从两双中各取一,是 C(2,1)*C(2,1)==4; 乘法原理,得数是 10*3*4=120
二、阅读程序(程序输入不超过数组或字符串定义的范围:判断题正确填√错误填x;除特殊说明外,判断题1.5分,选择题3分,共计40分)
#include <cstdlib>
#include <iostream>
char encoder[26]={'C','S','P',0};
char decoder[26];
string st;
int main(){
int k=0;
for(int i=0;i<26;++i)
if(encoder[i]!=0) ++k;
for(char x='A';x<='Z';++x){
bool flag=true;
for(int i=0;i<26;++i)
if(encoder[i]==x){
flag=false;
break;
}
if(flag){
encoder[k]=x;
++k;
}
}
for(int i=0;i<26;++i)
decoder[encoder[i]='A']=i+'A';
cin>>st;
for(int i=0;i<st.length();++i)
st[i]=decoder[st[i]-'A'];
cout<<st;
return 0;
}
判断题
1)输入的字符串应当只由大写字母组成,否则在访问数组时可能越界。
(true) 答案:true 解析:因为数组大小为 26,所以只能是大写字母,如果有小写字母 会越界。
2)若输入的字符串不是空串,则输入的字符串与输出的字符串一定不一样。
答案:false 根据 decoder 字符串的值,如果输入是 T~Z 之间的字母,输出是一 样的。
3)将第 12 行的“i<26”改为“i<16”,程序运行结果不会改变。
(true) 答案:true 解析:第 12 行是统计字符数,由于默认有 3 个字母,因此修改循环 的值不影响统计结果。
4)将第 26 行的“i<26”改为“i<16”,程序运行结果不会改变。
(false) 答案:false 解析:这个程序通过 encoder,decoder 两次转换产生一个乱序字符 串,利用乱序字符串加密 encoder="CSPABDEFGHIKLMNOQRTUVWXYZ" decoder="DEAFGHIKLMNOPQCRSBTUVWXYZ"
单选题
5)若输出的字符串为“ABCABCABCA",则下列说法正确的是(C)。
A.输入的字符串中既有 A 又有 P B.输入的字符串中既有 S 又有 B C.输入的字符串中既有 S 又有 P D.输入的字符串中既有 A 又有 B 答案:C 解析:输出中有 ABC,对应 decoder[2]、decoder[18]、decoder[15], 则输入的字符分别为字符 CSP。
6)若输出的字符串为“CSPCSPCSPCSP”,则下列说法正确的是(D)。
A.输入的字符串中既有 J 又有 RB.输入的字符串中既有 P 又有 K C.输入的字符串中既有 J 又有 KD.输入的字符串中既有 P 又有 R 答案:D 解析:输出中有 ABC,对应 decoder[15]、decoder[17]、decoder[13], 则输入的字符分别为字符 PRN。
#include<iostream>
using namespace std;
long long n,ans;
int k,len;
long long d[1000000];
int main()
{
cin>>n>>k;
d[0]=0;
len=1;
ans=0;
for(long long i=0;i<n;++i){
++d[0];
for(int j=0;j+1<len;++j){
if(d[j]==k){
d[j]=0;
d[j+1]+=1;
++ans;
}
}
if(d[len-1]==k){
d[len-1]=0;
d[len]=1;
++len;
++ans;
}
}
cout<<ans<<endl;
return 0;
}
假设输入的 n 是不超过 2^62 的正整数,k 都是不超过 10000 的正整数,完成下 面的判断题和单选题:
判断题
1)若 k=1,则输出 ans 时,len=n。
(false) 答案:false 解析:当 k 为 1 时,n 为 1,1 进制的 1,len 为 2,所以错误。
2)若 k>1,则输出 ans 时,len 一定小于 n。
(false) 答案:false 解析:输入 n 为 1 且 k>1 时,ans=n
3)若 k>1,则输出 ans 时,k^len 一定大于 n。(true) 代码的作用是十进制的 n 转换成 k 进制的数字,输出的 ans 为进位的次数,len 为结果的长度。
答案:true 解析:n转化为len位的k进制数字值最大值为k^len-1,因此k^len>n。 单选题
4)若输入的 n 等于 10^15,输入的 k 为 1,则输出等于(D)。 A.(10^30-10^15)/2 B.(10^30+10^15)/2 C.1 D.10^15
答案:D 解析:当输入的 k 为 1 时,会直接进位,len 为 2,但是后面触发不了 len++的条件,结果就是,len 一直是 2,每次 d[0]++都会进位,输出 ans=n
5)若输入的 n 等于 205,891,132,094,649(即 3^30),输入的 k 为 3,则输出等于 (A)。 A.(3^30-1)/2 B.3^30 C.3^30-1 D.(3^30+1)/2
答案:A 解析: 第 1 位,每 k 次运算进位 1 次; 第 2 位,每 k2 次运算进位 1 次; …… 因此第 1 位,会产生 3^30/3 次进位,第 2 位会产生 3^30/3^2 次进位……最后一 位,会产生 1 次进位。 因此答案=3^30/3+3^30/3^2+…+1 根据等比数列求和公式 Sn=(3^30–1)/(3-1)
6)若输入的 n 等于 100,010,002,000,090,输入的 k 为 10,则输出等于(D) A.11,112,222,444,543B.11,122,222,444,453 C.11,122,222,444,543D.11,112,222,444,453
答案:D 解析: 同上一问: 第 1 位进位次数=100010002000090/10 次 第 2 位进位次数=100010002000090/100 次 … 最后一位进位次数=1 次 对上述数值求和可得D
三、完善程序(单选题,每小题 3 分,共计 30 分)
1. (质因数分解)给出正整数 n,请输出将 n 质因数分解的结果,结果从小 到大输出。 例如:输入 n=120,程序应该输出 22235,表示 120=2*2*2*3*5。输入保证 2≤n≤ 10^9。 提示:先从小到大枚举变量 i,然后用 i 不停试除 n 来寻找所有的质因子。 试补全程序
1)处应填(D) A.n-1 B.0 C.1 D.2
答案:D 解析:因子最小为 2,所以选 i=2
2)处应填(D) A.n/I B.n/(i*i) C.i*i*I D.i*i
答案:D 解析:因子最大为根号 n 所以选 i*i
3)处应填(D) A.if(i*i<=n) B.if(n%i==0) C.while(i*i<=n) D.while(n%i==0)
答案:D 解析:由题目可知,一个因子可能被分解出好多次
4)处应填(A) A.n>1 B.n<=1 C.i+i<=n D.iA.n>1 B.n<=1 C.i+i<=n D.i<n/i
答案:A 解析:分解完成后,n 的值为 1 或者质数,判断剩余的是不是质数。
5)处应填(D) A.2 B.i C.n/I D.n
答案:D 解析:不是 1 的话需要单独输出
2.(最小区间覆盖)给出 n 个区间,第 i 个区间的左右端点是[a_i,b_i]。现在要 在这些区间中选出若干个,使得 区间[0,m]被所选区间的并覆盖(即每一个 0≤i≤m 都在某个所选的区间中)。保 证答案存在,求所选区间个数的最小值。 输入第一行包含两个整数 n 和 m(1≤n≤5000,1≤m≤10°)。 接下来 n 行,每行两个整数 ai,bi;(0≤ai,bi≤m)。 提示:使用贪心法解决这个问题。先用θ(n2)的时间复杂度排序,然后贪心选择 这些区间。 试补全程序
1)处应填(C) A.A[j].bA[j-1].b C.A[j].aA[j-1].a
答案:C 解析:按照区间起点进行排序
2)处应填(C) A.A[j-1]=A[j];A[j]=t; B.A[j+1]=A[j];A[j]=t; C.A[j]=A[j-1];A[j-1]=t; D.A[j]=A[j+1];A[j+1]=t;
答案:C 解析:变量交换代码
3)处应填(C)A.A[i].bA[i-1].bC.A[i].b>A[p-1].bD.A[i].b
答案:C解析:筛掉起点靠后同时终点靠前的区间,因为这样的区间完整的被前 面选中的区间包含了。
4)处应填(B) A.q+1<n&&A[q+1].b<=rB.q+1<n&&A[q+1].a<=rC.
答案:B 解析:此时剩余的区间逐个选用,优先选用能和前一个区间连接的情况 下,右端点更靠右的区间
5)处应填(B) A.r=max(r,A[q+1].a)B.r=max(r,A[q].b) C.r=max(r,A[q+1].b)D.q++
答案:B 解析:更新 r 为当前选中区间的右端点的