信息学奥赛-提高级 题库
本题中,我们约定布尔表达式只能包含 p, q, r 三个布尔变量,以及“与”(∧)、“或”(∨)、“非”(¬)三种布尔运算。如果无论 p, q, r 如何取值,两个布尔表达式的值总是相同,则称它们等价。例如,(p∨q)∨r 和 p∨(q∨r)等价,p∨¬p 和 q∨¬q 也等价;而 p∨q 和 p∧q 不等价。那么,两两不等价的布尔表达式最多有 个。
256
对于一棵二叉树,独立集是指两两互不相邻的节点构成的集合。例如,图1有5个不同的独立集(1个双点集合、3个单点集合、1个空集),图2有14个不同的独立集。那么,图3有 个不同的独立集。

5536
(排列数)输入两个正整数 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
(新壳栈)小 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)
现有一段文言文,要通过二进制哈夫曼编码进行压缩。简单起见,假设这段文言文只由 4 个汉字“之”、“乎”、“者”、“也”组成,它们出现的次数分别为 700、600、300、400。那么,“也”字的编码长度可能是( )。
生物特征识别,是利用人体本身的生物特征进行身份认证的一种技术。目前,指纹识别、虹膜识别、人脸识别等技术已广泛应用于政府、银行、安全防卫等领域。以下属于生物特征识别技术及其应用的是(ABD)。
