noip2015提高组c++试题.docx

第二十一届全国青少年信息学奥林匹克联赛初赛提高组 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 的方式连接到 Internet3.与二进制小数 0.1 相等的十六进制数是（）。A.0.8B.0.4C.0.2D.0.14.下面有四个数据组，每个组各有三个数据，其中第一个数据为八进制数，第二个数据为 十进制数，第三个数据为十六进制数。这四个数据组中三个数据相同的是（）。A.120 82 50B.144 100 68C.300 200 C8D.1762 1010 3F25.线性表若采用链表存储结构，要求内存中可用存储单元地址（）。A.必须连续B.部分地址必须连续C.一定不连续D.连续不连续均可6.今有一空栈 S，对下列待进栈的数据元素序列 a,b,c,d,e,f 依次进行进栈，进栈，出栈， 进栈，进栈，出栈的操作，则此操作完成后，栈 S 的栈顶元素为（）。A.fB.cC.aD.b7.前序遍历序列与后序遍历序列相同的二叉树为（）。A.非叶子结点只有左子树的二叉树B.只有根结点的二叉树C.根结点无右子树的二叉树D.非叶子结点只有右子树的二叉树8.如果根的高度为 1，具有 61 个结点的完全二叉树的高度为（）。A.5B.6C.7D.89.6 个顶点的连通图的最小生成树，其边数为（）。A.6B.5C.7D.410. 设某算法的计算时间表示为递推关系式 T(n) = T(n - 1) + n（n 为正整数）及 T(0) = 1，则 该算法的时间复杂度为（）。A.O(log n)B.O(n log n)C.O(n)D.O(n2)11. 具有 n 个顶点，e 条边的图采用邻接表存储结构，进行深度优先遍历和广度优先遍历运 算的时间复杂度均为（）。A.Θ(n2)B.Θ(e2)C.Θ(ne)D.Θ(n + e)12. 在数据压缩编码的应用中，哈夫曼（Huffman）算法是一种采用了（）思想的算法。A.贪心B.分治C.递推D.回溯13. 双向链表中有两个指针域，llink 和 rlink，分别指回前驱及后继，设 p 指向链表中的 一个结点，q 指向一待插入结点，现要求在 p 前插入 q，则正确的插入为（）。A.p-llink = q; q-rlink = p;p-llink-rlink = q; q-llink = p-llink;B.q-llink = p-llink; p-llink-rlink = q; q-rlink = p; p-llink = q-rlink;C.q-rlink = p; p-rlink = q;p-llink-rlink = q; q-rlink = p;D.p-llink-rlink = q; q-rlink = p;q-llink = p-llink; p-llink = q;14. 对图 G 中各个结点分别指定一种颜色，使相邻结点颜色不同，则称为图 G 的一个正常 着色。正常着色图 G 所必需的最少颜色数，称为 G 的色数。那么下图的色数是（）。A.3B.4C.5D.615. 在 NOI 系列赛事中参赛选手必须使用由承办单位统一提供的设备。下列物品中不允许选 手自带的是（）。A.鼠标B.笔C.身份证D.准考证二、不定项选择题（共 5 题，每题 1.5 分，共计 7.5 分；每题有一个或多个正确 选项，多选或少选均不得分）1.以下属于操作系统的有（）。A.Windows XPB.UNIXC.LinuxD.Mac OS2.下列属于视频文件格式的有（）。A.AVIB.MPEGC.WMVD.JPEG3.下列选项不是正确的 IP 地址的有（）。A.202.300.12.4B.192.168.0.3C.100:128:35:91D.111-103-35-214.下列有关树的叙述中，叙述正确的有（）。A.在含有 n 个结点的树中，边数只能是(n-1)条B.在哈夫曼树中，叶结点的个数比非叶结点个数多 1C.完全二叉树一定是满二叉树D.在二叉树的前序序列中，若结点 u 在结点 v 之前，则 u 一定是