首页 › 试卷 › 信息学奥赛 › 信息学奥赛-提高级 › 2015年第二十一届NOIP信息学奥赛提高组初赛C++试题

2015年第二十一届NOIP信息学奥赛提高组初赛C++试题 VIP

信息学奥赛-提高级 共 28 题 2015 年 含标准答案与解析
返回试卷列表
本页为整卷浏览:先自己做一遍,再展开「查看答案与解析」核对。

一、单选题

1. 单选题

在计算机内部用来传送、存贮、加工处理的数据或指令都是以( )形式进行的。(2015年提高组)

  • A 二进制码
  • B 八进制码
  • C 十进制码
  • D 智能拼音码
查看答案与解析
答案:A
这道题暂未补解析。
2. 单选题

下列说法正确的是( )。

  • A CPU 的主要任务是执行数据运算和程序控制
  • B 存储器具有记忆能力,其中信息任何时候都不会丢失
  • C 两个显示器屏幕尺寸相同,则它们的分辨率必定相同
  • D 个人用户只能使用 Wifi 的方式连接到 Internet
查看答案与解析
答案:A
这道题暂未补解析。
3. 单选题

与二进制小数 0.1 相等的十六进制数是( )。

  • A 0.8
  • B 0.4
  • C 0.2
  • D 0.1
查看答案与解析
答案:A
这道题暂未补解析。
4. 单选题

下面有四个数据组,每个组各有三个数据,其中第一个数据为八进制数,第二个数据为十进制数,第三个数据为十六进制数。这四个数据组中三个数据相同的是( )。

  • A 120 82 50
  • B 144 100 68
  • C 300 200 C8
  • D 1762 1010 3F2
查看答案与解析
答案:D
这道题暂未补解析。
5. 单选题

线性表若采用链表存储结构,要求内存中可用存储单元地址( )。(2015年提高组)

  • A 必须连续
  • B 部分地址必须连续
  • C 一定不连续
  • D 连续不连续均可
查看答案与解析
答案:D
这道题暂未补解析。
6. 单选题

今有一空栈S,对下列待进栈的数据元素序列a,b,c,d,e,f依次进行进栈,进栈,出栈,进栈,进栈,出栈的操作,则此操作完成后,栈S的栈顶元素为( )。

  • A f
  • B c
  • C a
  • D b
查看答案与解析
答案:B
这道题暂未补解析。
7. 单选题

前序遍历序列与后序遍历序列相同的二叉树为( )。

  • A 非叶子结点只有左子树的二叉树
  • B 只有根结点的二叉树
  • C 根结点无右子树的二叉树
  • D 非叶子结点只有右子树的二叉树
查看答案与解析
答案:B
这道题暂未补解析。
8. 单选题

如果根的高度为1,具有61个结点的完全二叉树的高度为( )。(2015年提高组)

  • A 5
  • B 6
  • C 7
  • D 8
查看答案与解析
答案:B
这道题暂未补解析。
9. 单选题

6 个顶点的连通图的最小生成树,其边数为( )。

  • A 6
  • B 5
  • C 7
  • D 4
查看答案与解析
答案:B
这道题暂未补解析。
10. 单选题

设某算法的计算时间表示为递推关系式 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)
查看答案与解析
答案:D
这道题暂未补解析。
11. 单选题

具有n个顶点,e条边的图采用邻接表存储结构,进行深度优先遍历和广度优先遍历运算的时间复杂度均为( )。

  • A Θ(n2)
  • B Θ(e2)
  • C Θ(ne)
  • D Θ(n + e)
查看答案与解析
答案:D
这道题暂未补解析。
12. 单选题

在数据压缩编码的应用中,哈夫曼(Huffman)算法是一种采用了( )思想的算法。

  • A 贪心
  • B 分治
  • C 递推
  • D 回溯
查看答案与解析
答案:A
这道题暂未补解析。
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;
查看答案与解析
答案:D
这道题暂未补解析。
14. 单选题

对图G中各个结点分别指定一种颜色,使相邻结点颜色不同,则称为图G的一个正常着色。正常着色图 G 所必需的最少颜色数,称为G的色数。那么下图的色数是( )。

  • A 3
  • B

    4

  • C

    5

  • D

    6

查看答案与解析
答案:A
这道题暂未补解析。
15. 单选题

在NOI系列赛事中参赛选手必须使用由承办单位统一提供的设备。下列物品中不允许选手自带的是( )。

  • A 鼠标
  • B 笔
  • C 身份证
  • D 准考证
查看答案与解析
答案:A
这道题暂未补解析。

二、简答题

16. 简答题

以下属于操作系统的有( )。

查看答案与解析
答案:A,B,C,D
这道题暂未补解析。
17. 简答题

下列属于视频文件格式的有( )。

查看答案与解析
答案:A,B,C
这道题暂未补解析。
18. 简答题

下列选项不是正确的IP地址的有( )。

查看答案与解析
答案:A,C,D
这道题暂未补解析。
19. 简答题

下列有关树的叙述中,叙述正确的有( )。

查看答案与解析
答案:A,B
这道题暂未补解析。
20. 简答题

以下图中一定可以进行黑白染色的有( )。(黑白染色:为各个结点分别指定黑白两种颜色之一,使相邻结点颜色不同。)

查看答案与解析
答案:A,C
这道题暂未补解析。
21. 简答题

在1和2015之间(包括1和2015在内)不能被4、5、6三个数任意一个数整除的数有_________个。

查看答案与解析
答案:<div> <p>1075</p></div>
这道题暂未补解析。
22. 简答题

结点数为5的不同形态的二叉树一共有_________种。(结点数为2的二叉树一共有2种:一种是根结点和左儿子,另一种是根结点和右儿子。)

查看答案与解析
答案:<div> <p>42</p></div>
这道题暂未补解析。
23. 简答题
#include <iostream>
using namespace std;
struct point {
	int x;
	int y;
};
int main() {
	struct EX{
		int a;
		int b;
		point c;
	} e;
	e.a = 1;
	e.b = 2;
	e.c.x = e.a + e.b;
	e.c.y = e.a * e.b;
	cout << e.c.x << ',' << e.c.y << endl;
	 return 0;
}

输出:_________

查看答案与解析
答案:<div> <p>3,2</p></div>
这道题暂未补解析。
24. 简答题
#include <iostream>
using namespace std;

void fun(char *a, char *b) {
	a = b;
	(*a)++;
}
int main() {
	char c1, c2, *p1, *p2;
	c1 = 'A';
	c2 = 'a';
	p1 = &c1;
	p2 = &c2;
	fun(p1, p2);
	cout << c1 << c2 << endl;
	return 0;
}

输出:_________

查看答案与解析
答案:<div> <p>Ab</p></div>
这道题暂未补解析。
25. 简答题
#include <iostream>
#include <string>
using namespace std;
int main() {
	int len, maxlen;
	string s, ss;
	maxlen = 0;
	do {
		cin >> ss;
		len = ss.length();
		if (ss[0] == '#')
			break;
		if (len > maxlen) {
			s = ss;
			maxlen = len;
		}
	} while (true);
	cout << s << endl;
	return 0;
}

输入:

I

am

a

citizen

of

China

#

输出:_________

查看答案与解析
答案:<div> <p>citizen</p></div>
这道题暂未补解析。
26. 简答题
#include <iostream>
using namespace std;
int fun(int n, int fromPos, int toPos) {
	int t, tot;
	if (n == 0)
		return 0;
	for (t = 1; t <= 3; t++)
		if (t != fromPos && t != toPos)
			break;
	tot = 0;
	tot += fun(n - 1, fromPos, t);
	tot++;
	tot += fun(n - 1, t, toPos);
	return tot;
}

int main() {
	int n;
	cin >> n;
	cout << fun(n, 1, 3) << endl;
	return 0;
}

输入:5

输出:_________

查看答案与解析
答案:<div> <p>31</p></div>
这道题暂未补解析。
27. 简答题

双子序列最大和)给定一个长度为n(3≤n≤1000)的整数序列,要求从中选出两个连续子序列,使得这两个连续子序列的序列和之和最大,最终只需输出这个最大和。一个连续子序列的序列和为该连续子序列中所有数之和。要求:每个连续子序列长度至少为1,且两个连续子序列之间至少间隔1个数。(第五空4分,其余 2.5分)

#include <iostream>

using namespace std;


const int MAXN = 1000;

int n, i, ans, sum;

int x[MAXN];

int lmax[MAXN];

// lmax[i]为仅含 x[i]及 x[i]左侧整数的连续子序列的序列和中,最大的序列和

int rmax[MAXN];

// rmax[i]为仅含 x[i]及 x[i]右侧整数的连续子序列的序列和中,最大的序列和


int main() {

cin >> n;

for (i = 0; i < n; i++)

cin >> x[i];

lmax[0] = x[0];

for (i = 1; i < n; i++)

if (lmax[i - 1] <= 0)

lmax[i] = x[i];

else

lmax[i] = lmax[i - 1] + x[i];

for (i = 1; i < n; i++)

if (lmax[i] < lmax[i - 1])

lmax[i] = lmax[i - 1];

                               (1)         ;

for (i = n - 2; i >= 0; i--)

if (rmax[i + 1] <= 0)

                            (2)          ;

else

                             (3)          ;

for (i = n - 2; i >= 0; i--)

if (rmax[i] < rmax[i + 1])

                            (4)           ;

ans = x[0] + x[2];

for (i = 1; i < n - 1; i++) {

sum =      (5)      ;

if (sum > ans)

ans = sum;

}

cout << ans << endl;

return 0;

}

查看答案与解析
答案:<p>(1)rmax[n-1]=x[n-1]</p><p>(2)rmax[i]=x[i]</p><p>(3)rmax[i]=rmax[i+1]+x[i]</p><p>(4)rmax[i]=rmax[i+1]</p><p>(5) lmax[i-1]+rmax[i+1]</p>
这道题暂未补解析。
28. 简答题

(最短路径问题)无向连通图G有n个结点,依次编号为0,1,2,...,(n-1)。用邻接矩阵的形式给出每条边的边长,要求输出以结点0为起点出发,到各结点的最短路径长度。

使用Dijkstra算法解决该问题:利用dist数组记录当前各结点与起点的已找到的最短路径长度;每次从未扩展的结点中选取dist值最小的结点v进行扩展,更新与v相邻的结点的dist值;不断进行上述操作直至所有结点均被扩展,此时dist数据中记录的值即为各结点与起点的最短路径长度。(第五空 2 分,其余 3 分)

#include <iostream>

using namespace std;


const int MAXV = 100;

int n, i, j, v;

int w[MAXV][MAXV]; // 邻接矩阵,记录边长

// 其中 w[i][j]为连接结点 i 和结点 j 的无向边长度,若无边则为-1

int dist[MAXV];

int used[MAXV]; // 记录结点是否已扩展(0:未扩展;1:已扩展)

int main() {

cin >> n;

for (i = 0; i < n; i++)

for (j = 0; j < n; j++)

cin >> w[i][j];

dist[0] = 0;

for (i = 1; i < n; i++)

dist[i] = -1;

for (i = 0; i < n; i++)

used[i] = 0;

while (true) {

                           (1)      ;

for (i = 0; i < n; i++)

if (used[i] != 1 && dist[i] != -1 && (v == -1 ||      (2)     ))

                                    (3)            ;

if (v == -1)

break;

                            (4)         ;

for (i = 0; i < n; i++)

if (w[v][i] != -1 && (dist[i] == -1 ||      (5)       ))

dist[i] = dist[v] + w[v][i];

}

for (i = 0; i < n; i++)

cout << dist[i] << endl;

return 0;

}

查看答案与解析
答案:<p>(1)v=-1</p><p>(2)dist[i]&lt;dist[v] 或 dist[v]&gt;dist[i] 或 dist[i]&lt;=dist[v] 或 dist[v]&gt;=dist[i]</p><p>(3)v=i</p><p>(4)used[v]=1</p><p>(5)dist[v]+w[v][i]&lt;dist[i] 或 dist[i]&gt;dist[v]+w[v][i] 或 dist[v]+w[v][i]&lt;=dist[i] 或 dist[i]&gt;=dist[v]+w[v][i]</p>
这道题暂未补解析。