信息学奥赛-提高级 题库
(双栈模拟数组)只使用两个栈结构stack1和stack2,模拟对数组的随机读取。作为栈结构,stack1和stack2只能访问栈顶(最后一个有效元素)。栈顶指针top1和top2均指向栈顶元素的下一个位置。
输入第一行包含两个整数,分别是数组长度n和访问次数m,中间用单个空格隔开。
第二行包含n个整数,依次给出数组各项(数组下标从0到n-1)。第三行包含m个整数,需要访问的数组下标。对于每次访问,输出对应的数组元素。(前两空每空2.5分,其余每空3分,共14分)
#include <iostream>
using namespace std;
const int SIZE = 100;
int stack1[SIZE], stack2[SIZE];
int top1, top2;
int n, m, i, j;
void clearStack() {
int i;
for (i = top1; i < SIZE; i++)
stack1[i] = 0;
for (i = top2; i < SIZE; i++)
stack2[i] = 0;
}
int main() {
cin >> n >> m;
for (i = 0; i < n; i++)
cin >> stack1[i];
top1 = (1) ;
top2 = (2) ;
for (j = 0; j < m; j++) {
cin >> i;
while (i < top1 - 1) {
top1--;
(3) ;
top2++;
}
while (i > top1 - 1) {
top2--;
(4) ;
top1++;
}
clearStack();
cout << stack1[ (5) ] << endl;
}
return 0;
}
(1)n
(2)0
(3)stack2[top2]=stack1[top1]
(4)stack1[top1]=stack2[top2]
(5)top1-1
(最大子矩阵和)给出 m 行 n 列的整数矩阵,求最大的子矩阵和(子矩阵不能为空)。
输入第一行包含两个整数 m 和 n,即矩阵的行数和列数。之后 m 行,每行 n 个整数,描述整个矩阵。程序最终输出最大的子矩阵和。(第一空 2 分,其余 3 分,共 14分)
#include <iostream>
using namespace std;
const int SIZE = 100;
int matrix[SIZE + 1][SIZE + 1];
int rowsum[SIZE + 1][SIZE + 1]; //rowsum[i][j]记录第 i 行前 j 个数的和
int m, n, i, j, first, last, area, ans;
int main() {
cin >> m >> n;
for (i = 1; i <= m; i++)
for (j = 1; j <= n; j++)
cin >> matrix[i][j];
ans = matrix (1) ;
for (i = 1; i <= m; i++)
(2) ;
for (i = 1; i <= m; i++)
for (j = 1; j <= n; j++)
rowsum[i][j] = (3) ;
for (first = 1; first <= n; first++)
for (last = first; last <= n; last++) {
(4) ;
for (i = 1; i <= m; i++) {
area += (5) ;
if (area > ans)
ans = area;
if (area < 0)
area = 0;
}
}
cout << ans << endl;
return 0;
}
(1)[1][1]
(2)rowsum[i][0]=0
(3)rowsum[i][j-1]+matrix[i][j]
(4)area=0
(5)rowsum[i][last]-rowsum[i,first-1]
以 A0 作为起点,对下面的无向图进行深度优先遍历时(遍历的顺序与顶点字母的下标无关),最后一个遍历到的顶点可能是( )。

某系统自称使用了一种防窃听的方式验证用户密码。密码是n个数s1,s2,…,sn,均为0或1。该系统每次随机生成 n 个数 a1,a2,…,an,均为 0 或 1,请用户回答(s1a1+s2a2+…+snan)除以2的余数。如果多次的回答总是正确,即认为掌握密码。该系统认为,即使问答的过程被泄露,也无助于破解密码——因为用户并没有直接发送密码。
然而,事与愿违。例如,当 n=4 时,有人窃听了以下 5 次问答:

就破解出了密码 s1=_________,s2=_________,s3=_________,s4=_________。
s1 = 0,s2 = 1,s3 = 1,s4 = 1
现有一只青蛙,初始时在 n 号荷叶上。当它某一时刻在 k 号荷叶上时,下一时刻将等概率随机跳到1,2,…,k 号荷叶之一上,直至跳到1号荷叶为止。当n=2 时,平均一共跳2次;当 n=3 时,平均一共跳 2.5 次。则当 n=5 时,平均一共跳_________次。
![]()
37/12
(两元序列)试求一个整数序列中,最长的仅包含两个不同整数的连续子序列。如有多个子序列并列最长,输出任意一个即可。例如,序列“1 1 2 3 2 3 2 3 3 1 1 1 3 1”中,有两段满足条件的最长子序列,长度均为7,分别用下划线和上划线标出。
#include <iostream>
using namespace std;
int main()
{
const int SIZE = 100;
int n, i, j, a[SIZE], cur1, cur2, count1, count2,
ans_length, ans_start, ans_end;
//cur1, cur2 分别表示当前子序列中的两个不同整数
//count1, count2 分别表示 cur1, cur2 在当前子序列中出现的次数
cin>>n;
for (i = 1; i <= n; i++)
cin>>a[i];
i = 1;
j = 1;
//i, j 分别表示当前子序列的首尾,并保证其中至多有两个不同整数
while ((j <= n) && (a[j] == a[i]))
j++;
cur1 = a[i];
cur2 = a[j];
count1 = (1) //(3 分)
count2 = 1;
ans_length = j - i + 1;
while (j < n) {
j++;
if (a[j] == cur1)
count1++;
else if (a[j] == cur2)
count2++;
else {
if (a[j - 1] == (2) ) { //(3 分)
while (count2 > 0) {
if (a[i] == cur1)
count1--;
else
ount2--;
i++;
}
cur2 = a[j];
count2 = 1;
}
else {
while (count1 > 0) {
if (a[i] == cur1)
(3) //(2 分)
else
(4) //(2 分)
i++;
}
(5) //(3 分)
count1 = 1;
}
}
if (ans_length < j - i + 1) {
ans_length = j - i + 1;
ans_start = i;
ans_end = j;
}
}
for (i = ans_start; i <= ans_end; i++)
cout<<a[i]<<' ';
return 0;
}
(1)j - 1
(2)cur1
(3)count1--(或 count1 = count1 – 1,或--count1)
(4)count2--(或 count2 = count2 – 1,或--count2)
(5)cur1 = a[j]
从顶点 A0出发,对有向图( )进行广度优先搜索(BFS)时,一种可能的遍历顺序是 A0, A1, A2, A3, A4。
如果一个栈初始时为空,且当前栈中的元素从栈底到栈顶依次为a, b, c(如右图所示),另有元素 d 已经出栈,则可能的入栈顺序有( )。

本题中,我们约定布尔表达式只能包含 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
(新壳栈)小 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)

