BCSP-X 初中组 C++基础知识测评 样卷

第 1 页 / 共 14 页 BCSP初中组基础知识测评样卷 （C++语言 满分：100分 考试时间： 120分钟） 一. 单项选择题（每题只有一个正确选项，每题 2分，共30分) 1.世界上第一台电子计算机诞生于（） A.1945年 B.1949年 C.1942年 D.1948年 E.1946年 F.1951年 2.盒子里面有 5 个黄球， 5 个蓝球， 5 个红球，这 15 个球形状完全相同，现 在要从盒子中依次取出 4 个球(每次取完会放回 )，并且要满足取出的这 4个球 中至少有一个红球，方案数是（） A. 120 B. 32 C. 56 D. 92 E.108 F.65 3. 以下关于 C++类的成员函数的表述中，哪一个是正确的？（） A. 构造函数可以有返回值，且可以被重载。 B. 纯虚函数必须在派生类中实现，使得基类成为抽象类。 C. 静态成员函数只能通过对象调用，而不能通过类名调用。 D. 析构函数可以重载，以处理不同的清理需求。 E. 构造函数必须定义，不能缺省。 F. 成员函数一定是内联函数。 4.（ ）的每一次操作，其均摊复杂度和最坏复杂度是同阶的。 A. std::vector的 插入 B. 斜堆的合并 C. 二分的单调队列的插入 D. splay实现的平衡树的插入 E. 栈的 push 操作 F. 哈希表的查找操作 5. 若元素a, b, c, d, e, f, g依次进栈，栈的大小为 3，以下哪一种出栈顺序是不可 能的？（） A. c, b, a, d, e, f, g B. b, c, d, a, f, e, g C. b, d, c, e, g, f, a D. a, d, e, b, c, g, f E. c, d, e, f, g, b, a F. c, b, d, e, f, g, a 第 2 页 / 共 14 页 6.关于最小生成树，下列说法正确的是（ ） A. 最小生成树唯一，当且仅当边权两两不相等。 B. 使用完全二叉堆优化的 Prim 算法，复杂度为 Θ(|E|+|V|log|V|)。 C. 使用 Borůvka 算法，并查集使用最佳的优化，复杂度为 Θ*(|V|+|E|)α(|V|)+。 D. 先用 Prim 算法加入若干点和边，将这些点和边视为一个点，再对未被加入 最小生成树的边用 Kruskal 算法，能求出最小生成树。 E. 所有权值最小的边一定会出现在所有的最小生成树中 F. 使用普里姆（ Prim）算法从不同顶点开始得到的最小生成树一定相同 7. 对于一个二叉树，其前序遍历为 A, B, D, E, C, F, G，其后序遍历为 D, E, B, G, F, C, A，其可能对应的二叉树的数量是多少？（） A. 1 B. 5 C. 3 D. 6 E. 7 F. 4 8.当 n≤10 ! 时，算法需要执行的指令数量为 nlogn 条，该算法的时间复杂度 是