1218: 2023CSP-J初赛模拟试题
题目描述
一、 选择题（每题2分，共30分）
1、计算机系统应包括（）
A.运算器、存储器、控制器 B.外部设备和主机
C.主机和应用程序 D.配套的硬件设备和软件系统
2、下列关于CPU存取速度的比较中，正确的是（）
A.Cache>内存>寄存器 B.Cache>寄存器>内存
C.寄存器>Cache>内存 D.寄存器>内存>Cache
3、设x=true，y=true，z=false，以下逻辑表达式值为真的是（）
A.(x∨y)^z B.x^(z∨y)Λz
C.(x∨y)^(x∨z) D.(y∨z)^x^z
4、在高速缓存系统中，主存容量为12MB，Cache容量为400KB，则该存储系统的容量为（）
A.12MB+400KB B.12MB
C.12MB-12MB+400KB D.12MB-400KB
5、插入排序算法的代码如下：
template<class Item>
void InsertionSort(Itema[],int l,int r)s
{
int i,j; Item t;
for(i=l+1; i<=r; ++i){
for(j=i-1, t=a[i]; j>=0 && t<a[j]; j--)
a[j+1] = a[j];
a[j+1] = t;
}
}
对n个数用以上插入排序算法进行排序，最少需要比较（）次。
A.n B.n-2
C.n^2 D.n-1
6、考虑下面的算法：
long long fib_NRcv(long n){
if((n==0)||(n==1)) return n;
long f2=0,f1=1,current;
for(int i=2;i<=n;i++){
current=f1+f2;
f2=f1;
f1=current;
}return current;
}
当n的值为8时，程序的返回值是多少（）
A.21 B.23
C.25 D.27
7、在非空的双向链表中由q所指向的结点右边插入一个由p所指向的结点，其动作依次为：
p->left=q; p->right=q->right; q->right=p;()
A.q->left=p; B.q->right->left=p;
C.p->right->left=p; D.p->left->left=p;
8、一个具有n个顶点的无向图最多有（）条边
A.n(n-1)/2 B.n(n-1)
C.n(n+1)/2 D.n^2
9、十进制数11转换为二进制数为（）
A.11 B.1010
C.1011 D.1100
10、用0到9这十个数字能组成多少个没有重复的四位偶数（）
A.1374 B.2296
C.3523 D.4048
11、设n个元素的入栈序列是1，2，3，...，n，出栈序列为p1，p2，...，pn，若p1=n，则pi（1≤i≤n）的值为（）
A.i B.n-i
C.n-i+1 D.有多种可能
12、独根树的深度为1，对于一棵具有n个结点，度为4的树（）
A.树的深度至多是n-4
B.树的深度至多是n-3
C.第i层上至多有4(i-1)个结点
D.最少在某一层上正好有4个结点
13、长度为n的顺序表L，删除其中一个元素的时间复杂度为（）
A.O(1) B.O(n)
C.O(n2) D.O(logn)
14、现有八人排成一排照相，其中甲乙丙三人不能相邻的排法有（）种
A.A(6,3)*A(5,5) B.A(8,8)-A(6,6)*A(3,3)
C.A(5,3)*A(3,3) D.A(8,8)-A(6,4)
15、（）是一种通用的字符编码，它为世界上绝大部分语言设定了统一并且唯一的二进制编码，以满足跨语言、平台的文本交换。目前它已经收录了超过十万个不同字符。
A.ASCII B.Unicode
C.GBK 2312 D.BIG5
二、 阅读程序（判断题每题3分，选择题每题3分，共30分）
1、阅读下列程序并回答问题。
16、输入的三个数中，第二个数应是[0,11]上的整数，否则会出现数组越界的问题。（）
A.√ B.×
17、输入1900 3 2和输入2000 3 1，输出结果是相同的。（）
A.√ B.×
18、将第9行改成”return(year-2000)%4==0”,其他地方不做改动，对程序最终的输出结果没有影响。（）
A.√ B.×
19、若输入的三个数为1990 9 20，则输出为（）
A.253 B.263
C.273 D.283
20、若输入的三个数为2000 5 1，则输出为（）
A.122 B.123
C.124 D.125
2、阅读下列程序并回答问题。
21、该算法的时间复杂度是O(mlogn)。（不考虑第39行的排序）（）
A.√ B.×
22、将第14行的代码改成while(left<right)，其他地方不做改动，对程序最终的输出结果没有影响。（）
A.√ B.×
23、将第16行的代码改成int middle = (left + right) >> 1, 其他地方不做改动，对程序最终的输出结果没有影响。（）
A.√ B.×
24、将第39行代码改成把arr数组中的元素从大到小排序的代码，其他地方不做改动，对程序最终的输出结果没有影响。（）
A.√ B.×
25、若输入如下数据：5 1 5 2 4 3 3 2 5 6 则输出结果为(用空格表示换行)：（）
A.YES YES YES
B.YES NO YES
C.YES YES NO
D.NO NO NO
三、 完善程序（每题4分，共40分）
1、快速幂就是快速算底数的n次幂，快速幂算法的核心思想就是每一步都把指数分成两半，而相应的底数做平方运算。这样不仅能把非常大的指数给不断变小，所需要执行的循环次数也变小，而最后表示的结果却一直不会变。
int FastExponentiation (int a, int b, int mod)
int answer = ①;
while (b != 0)
{
if (②){
answer*= a ;
③;
}
b /= 2;
④;
a %= mod;
}
return answer;
}
int main(){
int a, b;
scanf("%d %d",&a，&b);printf("%d\n",⑤);
return 0;
}
26、①处应填（）
A.0 B.1
C.1000 D.-1
27、②处应填（）
A.b%2==1 B.b%2==0
C.b==1 D.b==0
28、③处应填（）
A.answer*=mod B.answer/=mod
C.answer%=mod D.answer*=answer
29、④处应填（）
A.a*=a B.a*=b
C.b*=a D.b*=b
30、⑤处应填（）
A.FastExponentitation(b,a,1000)
B.FastExponentitation(a,b,1000)
C.FastExponentitation(b,a,3)
D.FastExponentitation(a,b,3)
2、（链表反转）单向链表反转是一道经典算法问题，比如有一个链表是这样的，1->2->3->4->5，反转后成为 5->4->3->2->1。现给定如下链表节点的定义：
struct li
int value;
li
非递归实现：
li
if (header == NULL || header->next == NULL) {
return header;
}
li
pre->next = NULL;
while(cur != NULL) {
li
② = pre;
pre = cur;
cur = next;
}
return pre;
}
递归实现：
li
if (head == NULL || head->next == NULL) {
return head;
}
li
④ = head;
head->next = ⑤;
return newhead;
}
31、上述程序①中应该填写()
A.pre-> next B.cur-> next
C.header-> next D.NULL
32、上述程序②中应该填写()
A.pre-> next B.cur-> next
C.header-> next D.NULL
33、上述程序③中应该填写()
A.ReverseList(head) B.ReverseList(pre)
C.ReverseList(cur) D.ReverseList(head->next)
34、上述程序④中应该填写()
A.pre-> next->next B.cur-> next->next
C.header-> next->next D.NULL
35、上述程序⑤中应该填写()
A.pre-> next B.cur-> next
C.header-> next D.NULL