首页 › 题库 › 信息学奥赛 › 信息学奥赛-提高级

信息学奥赛-提高级 题库

共 842 道题 ,第 36 / 43 页 · 按题型筛选,点「查看答案」核对解析
701 简答题 偏难 信息学奥赛 ·信息学奥赛-提高级 · 综合练习

逻辑异或(⊕)是一种二元运算,其真值表如下所示。

以下关于逻辑异或的性质,正确的有( )。

答案与解析
正确答案:A,B
这道题暂未补解析。
题目详情
702 简答题 偏难 信息学奥赛 ·信息学奥赛-提高级 · 综合练习

十进制下的无限循环小数(不包括循环节内的数字均为 0 或均为 9 的平凡情况),在二进制下有可能是( )。

答案与解析
正确答案:A
这道题暂未补解析。
题目详情
703 简答题 偏难 信息学奥赛 ·信息学奥赛-提高级 · 综合练习

以下( )属于互联网上的 E-mail 服务协议。

答案与解析
正确答案:C,D
这道题暂未补解析。
题目详情
704 简答题 偏难 信息学奥赛 ·信息学奥赛-提高级 · 8.1 复杂度分析

以下关于计算复杂度的说法中,正确的有( )。

答案与解析
正确答案:B,D
这道题暂未补解析。
题目详情
705 简答题 偏难 信息学奥赛 ·信息学奥赛-提高级 · 综合练习

本题中,我们约定布尔表达式只能包含 p, q, r 三个布尔变量,以及“与”(∧)、“或”(∨)、“非”(¬)三种布尔运算。如果无论 p, q, r 如何取值,两个布尔表达式的值总是相同,则称它们等价。例如,(p∨q)∨r 和 p∨(q∨r)等价,p∨¬p 和 q∨¬q 也等价;而 p∨q 和 p∧q 不等价。那么,两两不等价的布尔表达式最多有         个。

答案与解析
参考答案

256

题目详情
706 简答题 偏难 信息学奥赛 ·信息学奥赛-提高级 · 1.1 树与二叉树

对于一棵二叉树,独立集是指两两互不相邻的节点构成的集合。例如,图1有5个不同的独立集(1个双点集合、3个单点集合、1个空集),图2有14个不同的独立集。那么,图3有       个不同的独立集。

答案与解析
参考答案

5536

题目详情
707 简答题 偏难 信息学奥赛 ·信息学奥赛-提高级 · 6.2 字符串哈希
#include <iostream> 
using namespace std;

int n, i, temp, sum, a[100];

int main()
{
	cin>>n;
	for (i = 1; i <= n; i++) 
		cin>>a[i];
	for (i = 1; i <= n - 1; i++) 
		if (a[i] > a[i + 1]) {
			temp = a[i]; 
			a[i] = a[i + 1]; 
			a[i + 1] = temp;
		}
	for (i = n; i >= 2; i--)
		if (a[i] < a[i - 1]) { 
			temp = a[i];
			a[i] = a[i - 1];
			a[i - 1] = temp;
		}
	sum = 0;
	for (i = 2; i <= n - 1; i++) 
		sum += a[i];
	cout<<sum / (n - 2)<<endl; 
	return 0;
}

输入:

8

40 70 50 70 20 40 10 30

输出:

                   

答案与解析
参考答案

41

题目详情
708 简答题 偏难 信息学奥赛 ·信息学奥赛-提高级 · 6.2 字符串哈希
#include <iostream> 
using namespace std;

int n, i, ans;

int gcd(int a, int b)
{
	if (a % b == 0) 
		return b;
	else
		return gcd(b, a%b);
}
int main()
{
	cin>>n; 
	ans = 0;
	for (i = 1; i <= n; i++) 
		if (gcd(n,i) == i)
			ans++; 
	cout<<ans<<endl;
}

输入:120 

输出:            

答案与解析
参考答案

16

题目详情
709 简答题 偏难 信息学奥赛 ·信息学奥赛-提高级 · 6.2 字符串哈希
#include <iostream> 
using namespace std;

const int SIZE = 20;

int data[SIZE]; 
int n, i, h, ans;

void merge()
{
	data[h-1] = data[h-1] + data[h]; 
	h--;
	ans++;
}
int main()
{
	cin>>n; 
	h = 1;
	data[h] = 1;
	ans = 0;
	for (i = 2; i <= n; i++)
	{
		h++;
		data[h] = 1;
		while (h > 1 && data[h] == data[h-1]) 
			merge();
	}
	cout<<ans<<endl;
}

(1) 输入:8

输出:           (4 分)

(2) 输入:2012

输出:           (4 分

答案与解析
参考答案

(1)7

(2)2004

题目详情
710 简答题 偏难 信息学奥赛 ·信息学奥赛-提高级 · 6.2 字符串哈希
#include <iostream>
#include <string> 
using namespace std;

int lefts[20], rights[20], father[20]; 
string s1, s2, s3;
int n, ans;

void calc(int x, int dep)
{
	ans = ans + dep*(s1[x] - 'A' + 1);
	if (lefts[x] >= 0) calc(lefts[x], dep+1); 
	if (rights[x] >= 0) calc(rights[x], dep+1);
}
void check(int x)
{
	if (lefts[x] >= 0) check(lefts[x]); 
	s3 = s3 + s1[x];
	if (rights[x] >= 0) check(rights[x]);
}
void dfs(int x, int th)
{
	if (th == n)
	{
		s3 = "";
		check(0);
		if (s3 == s2)
		{
			ans = 0;
			calc(0, 1); 
			cout<<ans<<endl;
		}
		return;
	}
	if (lefts[x] == -1 && rights[x] == -1)
	{
		lefts[x] = th; 
		father[th] = x; 
		dfs(th, th+1); 
		father[th] = -1;
		lefts[x] = -1;
	}
	if (rights[x] == -1)
	{
		rights[x] = th; 
		father[th] = x; 
		dfs(th, th+1); 
		father[th] = -1;
		rights[x] = -1;
	}
	if (father[x] >= 0)
		dfs(father[x], th);
}
int main()
{
	cin>>s1; 
	cin>>s2;
	n = s1.size();
	memset(lefts, -1, sizeof(lefts));
	memset(rights, -1, sizeof(rights));
	memset(father, -1, sizeof(father));
	dfs(0, 1);
}

输入:

ABCDEF 

BCAEDF

输出:              

答案与解析
参考答案

55

题目详情
711 简答题 偏难 信息学奥赛 ·信息学奥赛-提高级 · 5.3 排列组合

(排列数)输入两个正整数 n, m (1 ≤ n ≤ 20, 1 ≤ m ≤ n),在 1~n 中任取 m 个数,按字典序从小到大输出所有这样的排列。例如

输入:3 2

输出:

1 2

1 3

2 1

2 3

3 1

3 2

#include<iostream>

#include<cstring> 

using namespace std;


const int SIZE = 25;


bool used[SIZE]; 

int data[SIZE];

int n, m, i, j, k; 

bool flag;


int main()

{

cin>>n>>m;

memset(used, false, sizeof(used)); 

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

{

data[i] = i; 

used[i] = true;

}

flag = true; 

while (flag)

{

for (i = 1; i <= m-1; i++) cout<<data[i]<<" "; 

cout<<data[m]<<endl;

flag =      ①      ;

for (i = m; i >= 1; i--)

{

                ②               ;

for (j = data[i]+1; j <= n; j++) if (!used[j])

{

used[j] = true; 

data[i] =       ③      ; 

flag = true;

break;

}

if (flag)

{

for (k = i+1; k <= m; k++)

for (j = 1; j <=      ④      ; j++) if (!used[j])

{

data[k] = j; 

used[j] = true; 

break;

}

              ⑤            ;

}

}

}

}

答案与解析
参考答案

①false

②used[data[i]] = false

③j

④n

⑤break

题目详情
712 简答题 偏难 信息学奥赛 ·信息学奥赛-提高级 · 1.2 图

(新壳栈)小 Z 设计了一种新的数据结构“新壳栈”。首先,它和传统的栈一样支持压入、弹出操作。此外,其栈顶的前 c 个元素是它的壳,支持翻转操作。其中,c > 2 是一个固定的正整数,表示壳的厚度。小 Z 还希望,每次操作,无论是压入、弹出还是翻转,都仅用与 c 无关的常数时间完成。聪明的你能帮助她编程实现“新壳栈”吗?

程序期望的实现效果如以下两表所示。其中,输入的第一行是正整数 c,之后每行输入都是一条指令。另外,如遇弹出操作时栈为空,或翻转操作时栈中元素不足 c 个,应当输出相应的错误信息。

#include <iostream> 

using namespace std;


const int

NSIZE = 100000,

CSIZE = 1000;


int n, c, r, tail, head, s[NSIZE], q[CSIZE];

//数组 s 模拟一个栈,n 为栈的元素个数

//数组 q 模拟一个循环队列,tail 为队尾的下标,head 为队头的下标

bool direction, empty;


int previous(int k)

{

if (direction)

return ((k + c - 2) % c) + 1; 

else

return (k % c) + 1;

}

int next(int k)

{

if (direction)

         ①        ;

else

return ((k + c - 2) % c) + 1;

}

void push()

{

int element;

cin>>element;

if (next(head) == tail) { 

n++;

                          ②        ;

tail = next(tail);

}

if (empty)

empty = false; 

else

head = next(head);

       ③        = element;

}

void pop()

{

if (empty) {

cout<<"Error: the stack is empty!"<<endl; 

return;

}

cout<<      ④       <<endl; 

if (tail == head)

empty = true; 

else {

head = previous(head); 

if (n > 0) {

tail = previous(tail);

                 ⑤            = s[n];

n--;

}

}

}

void reverse()

{

int temp;

if (      ⑥      == tail) { 

direction = !direction; 

temp = head;

head = tail; 

tail = temp;

}

else

cout<<"Error: less than "<<c<<" elements in the stack!"<<endl;

}

int main()

{

cin>>c; 

n = 0;

tail = 1;

head = 1; 

empty = true;

direction = true; 

do {

cin>>r; 

switch (r) {

case 1: push(); break;

case 2: pop(); break; 

case 3: reverse(); break;

}

} while (r != 0); 

return 0;

}

答案与解析
参考答案

①return (k % c) + 1

②s[n] = q[tail]

③q[head]

④q[head]

⑤q[tail]

⑥next(head)

题目详情
713 简答题 偏难 信息学奥赛 ·信息学奥赛-提高级 · 1.1 树与二叉树

如果根结点的深度记为 1,则一棵恰有 2011 个叶子结点的二叉树的深度可能是( )。

答案与解析
正确答案:C,D
这道题暂未补解析。
题目详情
714 简答题 偏难 信息学奥赛 ·信息学奥赛-提高级 · 综合练习

在布尔逻辑中,逻辑“或”的性质有( )。

答案与解析
正确答案:A,B,C,D
这道题暂未补解析。
题目详情
715 简答题 偏难 信息学奥赛 ·信息学奥赛-提高级 · 综合练习

一个正整数在十六进制下有 100 位,则它在二进制下可能有( )位。

答案与解析
正确答案:A,B
这道题暂未补解析。
题目详情
716 简答题 偏难 信息学奥赛 ·信息学奥赛-提高级 · 综合练习

汇编语言( )。

答案与解析
正确答案:B,C
这道题暂未补解析。
题目详情
717 简答题 偏难 信息学奥赛 ·信息学奥赛-提高级 · 1.1 树与二叉树

现有一段文言文,要通过二进制哈夫曼编码进行压缩。简单起见,假设这段文言文只由 4 个汉字“之”、“乎”、“者”、“也”组成,它们出现的次数分别为 700、600、300、400。那么,“也”字的编码长度可能是( )。

答案与解析
正确答案:B,C
这道题暂未补解析。
题目详情
718 简答题 偏难 信息学奥赛 ·信息学奥赛-提高级 · 综合练习

生物特征识别,是利用人体本身的生物特征进行身份认证的一种技术。目前,指纹识别、虹膜识别、人脸识别等技术已广泛应用于政府、银行、安全防卫等领域。以下属于生物特征识别技术及其应用的是(ABD)。 


答案与解析
正确答案:A,B,D
这道题暂未补解析。
题目详情
719 简答题 偏难 信息学奥赛 ·信息学奥赛-提高级 · 综合练习

对于序列“7、5、1、9、3、6、8、4”,在不改变顺序的情况下,去掉( )会使逆序对的个数减少 3。

答案与解析
正确答案:C,D
这道题暂未补解析。
题目详情
720 简答题 偏难 信息学奥赛 ·信息学奥赛-提高级 · 综合练习

计算机中的数值信息分为整数和实数(浮点数)。实数之所以能够表示很大或者很小的数,是由于使用了( )。

答案与解析
正确答案:A
这道题暂未补解析。
题目详情