CSP-J 初赛模拟卷一满分100分 考试时间120分钟一、单项选择题共15题每题2分共计30分每题有且仅有一个正确选项1.在计算机的内存储器中每个存储单元都被赋予一个唯一的序号称为 。A. 下标 B. 地址 C. 指针 D. 索引2.二进制数(110101)₂与十六进制数(1A)₁₆的和对应的十进制值是 。A. 67 B. 75 C. 79 D. 833.在 C 中若希望函数内的局部变量在多次函数调用之间保留上一次的值应使用哪个关键字 A. const B. static C. extern D. register4.一张分辨率为 800×600 的 BMP 图片若每个像素用 24 位表示那么这张图片所占用的存储空间最接近 。A. 1400KB B. 750KB C. 600KB D. 1000KB5.若某算法的计算时间表示为递推关系式 T(n) 2T(n/2) 2nT(1) 1则其时间复杂度为 。A. O(log n) B. O(n log n) C. O(n) D. O(n²)6.下列关于栈的说法中正确的是 。A. 栈是一种先进先出的数据结构B. 栈只能在栈底进行插入和删除操作C. 栈的典型应用包括函数调用和表达式求值D. 栈中元素的数量是固定的7.已知一棵二叉树的前序遍历序列为 A B D E C F中序遍历序列为 D B E A C F则其后序遍历序列为 。A. D E B F C A B. D B E F C A C. E D B F C A D. D E B C F A8.一个空栈依次将 1, 2, 3, 4, 5 入栈下面哪个序列不可能作为出栈序列 A. 2, 1, 4, 5, 3 B. 3, 2, 1, 5, 4 C. 4, 1, 3, 2, 5 D. 1, 2, 3, 4, 59.在 C 中表达式(char)(A 5)的值是 。A. E B. F C. G D. 510.下列关于排序算法的描述中错误的是 。A. 冒泡排序是稳定的排序算法B. 快速排序的平均时间复杂度为 O(n log n)C. 选择排序在任何情况下时间复杂度都是 O(n²)D. 归并排序的空间复杂度为 O(1)11.后缀表达式3 4 5 * 6 -对应的中缀表达式是 。A. 3 4 × 5 − 6 B. (3 4) × (5 − 6) C. (3 4) × 5 − 6 D. 3 4 × (5 − 6)12.一个有 8 个顶点、10 条边的无向连通图至少删除多少条边后可以变成一棵树 A. 1 B. 2 C. 3 D. 413.关于哈夫曼编码下列说法正确的是 。A. 哈夫曼编码是一种前缀码不存在任一代码是另一代码的前缀B. 哈夫曼编码要求所有字符的权值频率相等C. 哈夫曼编码生成的码长与字符出现频率无关D. 哈夫曼编码不保证最优平均码长14.有 4 名男生和 3 名女生从中选出 3 人组成小组要求至少有 1 名女生共有多少种选法 A. 21 B. 28 C. 31 D. 3515.一个字长为 8 位的整数的补码为11111001则它的原码是 。A. 10000111 B. 11111001 C. 10000110 D. 00000111二、阅读程序共3题判断题每题1.5分选择题每题3分共计40分1cpp#include iostream #include cstring using namespace std; bool check(char s[], int l, int r) { while (l r) { if (s[l] ! s[r]) return false; l; r--; } return true; } int main() { char str[100]; cin str; int len strlen(str); int ans 0; for (int i 0; i len; i) { for (int j i; j len; j) { if (check(str, i, j)) ans; } } cout ans endl; return 0; }判断题若输入abcba程序输出 7。 若将第 4 行的while (l r)改为while (l r)程序的输出结果不会改变。 若输入字符串长度为 n则 check 函数在最坏情况下的时间复杂度为 O(n)。 选择题若输入aaaa程序的输出是 。A. 4 B. 6 C. 10 D. 16该程序的功能是 。A. 统计字符串中不同字符的个数B. 统计字符串中回文子串的个数C. 判断字符串是否为回文串D. 统计字符串中最长回文子串的长度2cpp#include iostream using namespace std; int gcd(int a, int b) { if (b 0) return a; return gcd(b, a % b); } int main() { int n; cin n; int ans 0; for (int i 1; i n; i) { for (int j 1; j n; j) { if (gcd(i, j) 1) ans; } } cout ans endl; return 0; }判断题若输入 n 3程序输出 7。 将第 7 行的gcd(b, a % b)改为gcd(a, a % b)后程序仍能正确运行。 该程序的时间复杂度为 O(n² log n)。 选择题若输入 n 5程序的输出是 。A. 9 B. 11 C. 13 D. 15该程序的功能是 。A. 统计 1 到 n 中所有互质数对的个数B. 统计 1 到 n 中所有数的约数个数之和C. 求 1 到 n 的最大公约数之和D. 判断 1 到 n 中哪些数互质3cpp#include iostream using namespace std; int fib(int n) { if (n 1) return n; return fib(n - 1) fib(n - 2); } int main() { int n; cin n; cout fib(n) endl; return 0; }判断题若输入 n 6程序输出 8。 将第 4 行的if (n 1) return n;改为if (n 0) return 0; if (n 1) return 1;程序的输出结果不变。 fib(5) 在递归过程中fib(2) 被调用了 3 次。 选择题若输入 n 10程序的输出是 。A. 34 B. 55 C. 89 D. 144该程序的时间复杂度为 。A. O(n) B. O(n log n) C. O(2ⁿ) D. O(n²)三、完善程序共2题每空3分共计30分1二分查找以下程序实现在有序数组中用二分查找算法查找目标值 x若找到则返回其下标否则返回 -1。请完善程序。cpp#include iostream using namespace std; int binary_search(int a[], int n, int x) { int left 0, right n - 1; while (____①____) { int mid ____②____; if (a[mid] x) return mid; else if (a[mid] x) ____③____; else ____④____; } return -1; } int main() { int a[] {1, 3, 5, 7, 9, 11, 13, 15}; int n 8; int x; cin x; cout binary_search(a, n, x) endl; return 0; }①处应填 A. left right B. left right C. left ! right D. left right②处应填 A. (left right) / 2 B. (left right) 1 C. left (right - left) / 2 D. 以上均可③处应填 A. left mid B. left mid 1 C. right mid D. right mid - 1④处应填 A. left mid B. left mid 1 C. right mid D. right mid - 12求最大值以下程序从 n 个数中找出最大值。请完善程序。cpp#include iostream using namespace std; int main() { int n; cin n; int max_val ____①____; for (int i 0; i n; i) { int x; cin x; if (____②____) { max_val x; } } cout ____③____ endl; return 0; }①处应填 A. 0 B. -1 C. -2147483648 D. 2147483647②处应填 A. x max_val B. x max_val C. x max_val D. x max_val③处应填 A. max_val B. x C. n D. iCSP-J 初赛模拟卷二满分100分 考试时间120分钟一、单项选择题共15题每题2分共计30分每题有且仅有一个正确选项1.以下扩展名结尾的文件中不是多媒体文件的是 。A. .mp3 B. .avi C. .txt D. .wav2.计算机的中央处理器CPU的组成部件是 。A. 控制器和存储器 B. 运算器和存储器 C. 控制器、存储器和运算器 D. 运算器和控制器3.在 C 中以下关于引用的说法正确的是 。A. 引用一旦初始化后可以重新指向另一个变量B. 引用是变量的别名不占用额外的内存空间C. 引用可以为空nullD. 引用的类型必须与所引用变量的类型完全一致4.一个正整数在十六进制下有 200 位则它在二进制下最多可能有 位。A. 801 B. 798 C. 799 D. 8005.深度优先搜索DFS时控制与记录搜索过程通常使用的数据结构是 。A. 队列 B. 栈 C. 链表 D. 哈希表6.以下哪个操作运算符的优先级最高 A.B.C.后缀 D.7.无向完全图 G 有 10 个顶点它有 条边。A. 45 B. 90 C. 72 D. 368.在 8 位二进制补码中10110110表示的是十进制下的 。A. -202 B. -74 C. 202 D. 749.关于链表和数组的描述中错误的是 。A. 数组支持通过下标随机访问B. 链表插入和删除元素比数组更高效C. 数组的大小在定义后可以动态改变D. 链表的存储空间不需要连续10.如果根结点的深度是 1则一棵恰好有 2025 个叶子结点的二叉树的深度不可能是 。A. 11 B. 12 C. 13 D. 202511.在 C 语言中数组定义为int a[6] {1, 2, 3, 4, 5, 6};指针定义为int *p a[3];则执行a[2] * *p;后数组 a 中的值变为 。A. {1, 2, 4, 4, 5, 6} B. {2, 2, 3, 4, 5, 6} C. {1, 2, 12, 4, 5, 6} D. {1, 2, 3, 4, 5, 6}12.某二叉树的中序遍历序列为 BDCEAFHG后序遍历序列为 DECBHGFA其前序遍历序列为 。A. ABCDEFGH B. ABDCEFGH C. ABDCEGFH D. ABCDEGFH13.有 5 条线段长度分别为 1, 3, 5, 7, 9从中任取 3 条能构成一个三角形的概率为 。A. 1/10 B. 3/10 C. 2/5 D. 1/214.在 C 中表达式2022 0x618的值是 。A. (462)₁₀ B. (1DE)₁₆ C. (726)₈ D. (1110010110)₂15.以下关于算法的描述中正确的是 。A. 算法一定要用某种计算机语言写成程序才有价值B. 要想实现算法必须先画流程图C. 算法只需要用到数学的计算方法D. 算法是为解决问题而采取的方法与步骤二、阅读程序共3题判断题每题1.5分选择题每题3分共计40分1cpp#include iostream using namespace std; int main() { int n; cin n; int cnt 0; for (int i 2; i n; i) { bool flag true; for (int j 2; j * j i; j) { if (i % j 0) { flag false; break; } } if (flag) cnt; } cout cnt endl; return 0; }判断题若输入 n 10程序输出 4。 将第 7 行的j * j i改为j i / 2程序的运行结果不会改变。 将第 4 行的int i 2改为int i 1程序的输出结果不变。 选择题若输入 n 20程序的输出是 。A. 7 B. 8 C. 9 D. 10该程序的功能是 。A. 统计 1 到 n 中所有数的约数个数B. 统计 1 到 n 中所有质数的个数C. 判断 n 是否为质数D. 统计 1 到 n 中所有合数的个数2cpp#include iostream using namespace std; int main() { int n; cin n; int sum 0; for (int i 1; i n; i) { int t i; while (t 0) { sum t % 10; t / 10; } } cout sum endl; return 0; }判断题若输入 n 9程序输出 45。 该程序的时间复杂度为 O(n)。 将第 9 行的sum t % 10改为sum t程序输出的是 1 到 n 的和。 选择题若输入 n 11程序的输出是 。A. 55 B. 56 C. 57 D. 66该程序的功能是 。A. 计算 1 到 n 中所有数的和B. 计算 1 到 n 中所有数的各位数字之和C. 计算 1 到 n 中所有数的平方和D. 计算 n 的各位数字之和3cpp#include iostream using namespace std; int pow2(int n) { if (n 0) return 1; return 2 * pow2(n - 1); } int main() { int n; cin n; cout pow2(n) endl; return 0; }判断题若输入 n 5程序输出 32。 该程序的时间复杂度为 O(n)。 将第 4 行的if (n 0) return 1;改为if (n 1) return 2;输入 n 0 时程序输出 0。 选择题若输入 n 8程序的输出是 。A. 128 B. 256 C. 512 D. 64该程序的空间复杂度为 。A. O(1) B. O(n) C. O(n²) D. O(2ⁿ)三、完善程序共2题每空3分共计30分1冒泡排序以下程序实现冒泡排序算法将数组 a 中的 n 个元素按从小到大排序。请完善程序。cpp#include iostream using namespace std; void bubble_sort(int a[], int n) { for (int i 0; i n - 1; i) { for (int j 0; j ____①____; j) { if (____②____) { int temp a[j]; a[j] a[j 1]; a[j 1] temp; } } } } int main() { int a[] {5, 2, 8, 1, 9, 3}; int n 6; bubble_sort(a, n); for (int i 0; i n; i) cout a[i] ; return 0; }①处应填 A. n - i B. n - i - 1 C. n - 1 - i D. n - i 1②处应填 A. a[j] a[j 1] B. a[j] a[j 1] C. a[j] a[j 1] D. a[j] a[j 1]2阶乘以下程序计算 n 的阶乘n!。请完善程序。cpp#include iostream using namespace std; int factorial(int n) { if (____①____) return 1; return ____②____; } int main() { int n; cin n; cout factorial(n) endl; return 0; }①处应填 A. n 0 B. n 1 C. n 1 D. 以上均可②处应填 A. n * factorial(n) B. n * factorial(n - 1) C. (n - 1) * factorial(n) D. factorial(n - 1)若将程序改为迭代循环实现以下哪个是正确的循环体 A.cppint ans 1; for (int i 1; i n; i) ans * i;B.cppint ans 0; for (int i 1; i n; i) ans i;C.cppint ans 1; for (int i 0; i n; i) ans * i;D.cppint ans n; for (int i 1; i n; i) ans * i;参考答案明天发