NOIP2015提高组C试题.pdf

第二十一届全国青少年信息学奥林匹克联赛初赛 提高组C 语言试题 竞赛时间：2015 年10 月11 日14:30~16:30 选手注意：  试题纸共有9 页，答题纸共有2 页，满分100 分。请在答题纸上作答，写在试题纸上的 一律无效。  不得使用任何电子设备（如计算器、手机、电子词典等）或查阅任何书籍资料。 一、单项选择题（共15 题，每题1.5 分，共计22.5 分；每题有且仅有一个正确 选项） 1. 在计算机内部用来传送、存贮、加工处理的数据或指令都是以 （ ）形式进行的。 A. 二进制码 B. 八进制码 C. 十进制码 D. 智能拼音码 2. 下列说法正确的是 （ ）。 A. CPU 的主要任务是执行数据运算和程序控制 B. 存储器具有记忆能力，其中信息任何时候都不会丢失 C. 两个显示器屏幕尺寸相同，则它们的分辨率必定相同 D. 个人用户只能使用Wifi 的方式连接到Internet 3. 与二进制小数0.1 相等的十六进制数是 （ ）。 A. 0.8 B. 0.4 C. 0.2 D. 0.1 4. 下面有四个数据组，每个组各有三个数据，其中第一个数据为八进制数，第二个数据为 十进制数，第三个数据为十六进制数。这四个数据组中三个数据相同的是 （ ）。 A. 120 82 50 B. 144 100 68 C. 300 200 C8 D. 1762 1010 3F2 5. 线性表若采用链表存储结构，要求内存中可用存储单元地址 （ ）。 A. 必须连续 B. 部分地址必须连续 C. 一定不连续 D. 连续不连续均可 6. 今有一空栈S，对下列待进栈的数据元素序列a,b,c,d,e,f 依次进行进栈，进栈，出栈， 进栈，进栈，出栈的操作，则此操作完成后，栈S 的栈顶元素为 （ ）。 A. f B. c C. a D. b CCF NOIP2015 初赛提高组C 语言试题 第1 页，共9 页 7. 前序遍历序列与后序遍历序列相同的二叉树为 （ ）。 A. 非叶子结点只有左子树的二叉树 B. 只有根结点的二叉树 C. 根结点无右子树的二叉树 D. 非叶子结点只有右子树的二叉树 8. 如果根的高度为1，具有61 个结点的完全二叉树的高度为 （ ）。 A. 5 B. 6 C. 7 D. 8 9. 6 个顶点的连通图的最小生成树，其边数为 （ ）。 A. 6 B. 5 C. 7 D. 4 10. 设某算法的计算时间表示为递推关系式T(n) = T(n - 1) + n （n 为正整数）及T(0) = 1 ，则 该算法的时间复杂度为 （ ）。 2 A. O(log n) B. O(n log n) C. O(n) D. O(n ) 11. 具有n 个顶点，e 条边的图采用邻接表存储结构，进行深度优先遍历和广度优先遍历运 算的时间复杂度均为 （ ）。 2 2 A. Θ(n ) B. Θ(e ) C. Θ(ne) D. Θ(n + e) 12. 在数据压缩编码的应用中，哈夫曼（Huffman）算法是一种采用了 （ ）思想的算法。 A. 贪心