首页 › 题库 › 信息学奥赛 › 1 数据结构进阶

信息学奥赛-提高级 题库

共 682 道题 ,第 29 / 35 页 · 按题型筛选,点「查看答案」核对解析
章节 1 数据结构进阶 清除
561 简答题 偏难 信息学奥赛 ·信息学奥赛-提高级 · 1.2 图

如图所示,图中每条边上的数字表示该边的长度,则从A到E的最短距离是_________。

答案与解析
参考答案

15

题目详情
562 简答题 偏难 信息学奥赛 ·信息学奥赛-提高级 · 综合练习

由数字1,1,2,4,8,8所组成的不同的四位数的个数是_________。

答案与解析
参考答案

102

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

(双栈模拟数组)只使用两个栈结构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

题目详情
564 简答题 偏难 信息学奥赛 ·信息学奥赛-提高级 · 综合练习

(最大子矩阵和)给出 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]

题目详情
565 简答题 偏难 信息学奥赛 ·信息学奥赛-提高级 · 综合练习

下列程序中,正确计算1,2,…,100 这100个自然数之和sum(初始值为 0)的是( )。

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

以 A0 作为起点,对下面的无向图进行深度优先遍历时(遍历的顺序与顶点字母的下标无关),最后一个遍历到的顶点可能是(  )。

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

( )属于 NP 类问题。

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

CCF NOIP 复赛考试结束后,因( )提出的申诉将不会被受理。

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

某系统自称使用了一种防窃听的方式验证用户密码。密码是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

题目详情
570 简答题 偏难 信息学奥赛 ·信息学奥赛-提高级 · 综合练习

现有一只青蛙,初始时在 n 号荷叶上。当它某一时刻在 k 号荷叶上时,下一时刻将等概率随机跳到1,2,…,k 号荷叶之一上,直至跳到1号荷叶为止。当n=2 时,平均一共跳2次;当 n=3 时,平均一共跳 2.5 次。则当 n=5 时,平均一共跳_________次。

答案与解析
参考答案

37/12

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

(两元序列)试求一个整数序列中,最长的仅包含两个不同整数的连续子序列。如有多个子序列并列最长,输出任意一个即可。例如,序列“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]

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

从顶点 A0出发,对有向图( )进行广度优先搜索(BFS)时,一种可能的遍历顺序是 A0, A1, A2, A3, A4。

答案与解析
正确答案:A,D
这道题暂未补解析。
题目详情
573 简答题 偏难 信息学奥赛 ·信息学奥赛-提高级 · 1.2 图

如果一个栈初始时为空,且当前栈中的元素从栈底到栈顶依次为a, b, c(如右图所示),另有元素 d 已经出栈,则可能的入栈顺序有( )。

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

一棵二叉树一共有 19 个节点,其叶子节点可能有( )个。

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

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

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

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

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

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

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

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

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

答案与解析
参考答案

256

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

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

答案与解析
参考答案

5536

题目详情
580 简答题 偏难 信息学奥赛 ·信息学奥赛-提高级 · 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)

题目详情