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

信息学奥赛-提高级 题库

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

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

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

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

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

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

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

汇编语言( )。

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

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

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

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


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

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

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

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

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

为计算机网络中进行数据交换而建立的规则、标准或约定的集合称为网络协议。下列英文缩写中,( )是网络协议

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

平面图可以在画在平面上,且它的边仅在顶点上才能相交的简单无向图。4个顶点的平面图至少有6条边,如右图所示。那么,5个顶点的平面图至少有         条边。

答案与解析
参考答案

9

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

定义一种字符串操作,一次可以将其中一个元素移到任意位置。举例说明,对于字符串“BCA”可以将 A 移到 B 之前,变字符串“ABC”。如果要将字符串“DACHEBGIF”变成“ABCDEFGHI”最少需要________次操作。

答案与解析
参考答案

4

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

(大整数开方) 输入一个正整数n(1≤n≤10100),试用二分法计算它的平方根的整数部分。

#include<iostream>

#include<string>

using namespace std;


const int SIZE=200;

struct hugeint{

int len,num[SIZE];

};

//其中 len 表示大整数的位数;num[1]表示个位,num[2]表示十位,以此类推


hugeint times(hugeint a,hugeint b)

// 计算大整数 a 和 b 的乘积

{

int i,j;

hugeint ans;

memset(ans.num,0,sizeof(ans.num));

for(i=1;i<=a.len;i++)

for(j=1;j<=b.len;j++)

         ①       +=a.num[i]*b.num[j]; 

for(i=1;i<=a.len+b.len;i++){

ans.num[i+1]+=ans.num[i]/10;

                 ②             ; 

}

if(ans.num[a.len+b.len]>0)

ans.len=a.len+b.len;

else

ans.len=a.len+b.len-1;

return ans;

}


hugeint add(hugeint a,hugeint b)

//计算大整数 a 和 b 的和

{

int i;

hugeint ans;

memset(ans.num,0,sizeof(ans.num));

if(a.len>b.len)

ans.len=a.len;

else

ans.len=b.len;

for(i=1;i<=ans.len;i++){

ans.num[i]+=     ③      ; 

ans.num[i+1]+= ans.num[i]/10;

ans.num[i]%=10;

}

if(ans.num[ans.len+1]>0)

ans.len++;

return ans;

}


hugeint average(hugeint a,hugeint b)

//计算大整数 a 和 b 的平均数的整数部分

{

int i;

hugeint ans;

ans=add(a,b);

for(i=ans.len;i>=2;i--){

ans.num[i-1]+=(      ④      )*10; 

ans.num[i]/=2;

}

ans.num[1]/=2;

if(ans.num[ans.len]==0)

ans.len--;

return ans;

}


hugeint plustwo(hugeint a)

// 计算大整数 a 加 2 之后的结果

{

int i;

hugeint ans;

ans=a;

ans.num[1]+=2;

i=1;

while( (i<=ans.len)&&(ans.num[i]>=10) ){

ans.num[i+1]+=ans.num[i]/10;

ans.num[i]%=10;

i++;

}

if(ans.num[ans.len+1]>0)

           ⑤       ; 

return ans;

}


bool over(hugeint a,hugeint b)

// 若大整数 a>b 则返回 true,否则返回 false

{

int i;

if(      ⑥      ) 

return false;

if( a.len>b.len )

return true;

for(i=a.len;i>=1;i--){

if(a.num[i]<b.num[i])

return false;

if(a.num[i]>b.num[i])

return true;

}

return false;

}

int main()

{

string s;

int i;

hugeint target,left,middle,right;

cin>>s;

memset(target.num,0,sizeof(target.num));

target.len=s.length();

for(i=1;i<=target.len;i++)

target.num[i]=s[target.len-i]-      ⑦      ;

memset(left.num,0,sizeof(left.num));

left.len=1;

left.num[1]=1;

right=target;

do{

middle=average(left,right);

if(over(      ⑧      ))

right=middle;

else

left=middle;

}while(!over(plustwo(left),right) );

for(i=left.len;i>=1;i--)

cout<<left.num[i];

return 0;

}

答案与解析
参考答案

① ans.num[i + j - 1]

② ans.num[i] %= 10(或 ans.num[i] = ans.num[i] % 10) ③ a.num[i] + b.num[i]

④ ans.num[i] % 2(或 ans.num[i] & 1)

⑤ ans.len++(或 ++ans.len 或 ans.len += 1 或 ans.len = ans.len + 1)

⑥ a.len < b.len

⑦ '0'(或 48)

⑧ times(middle, middle), target

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

(笛卡尔树)对于一个给定的两两不等的正整数序列,笛卡尔树是这样的一棵二叉树:首先,它是一个最小堆,即除了根结点,每个节点的权值都大雨父节点的权值;其次,它的中序遍历恰好就是给定的序列。例如,对于序列7、2、12、1、10、5、15、3,下图就是一棵对应的笛卡尔树。现输入序列的规模n(1≤n<100)和序列的 n 个元素,试求其对应的笛卡尔树的深度 d(根节点深度为1),以及有多少个叶子节点的深度为d。


#include<iostream>


using namespace std;


const int SIZE=100+5;

const int INFINITY=1000000;

int n,a[SIZE],maxDeep,num;


void solve(int left,int right,int deep)

{

int i,j,min;

if(deep>maxDeep){

maxDeep=deep;

num=1;

}

else if(deep==maxDeep)

         ①         ; 

min= INFINITY;

for(i=left;i<=right;i++)

if(min>a[i]){

min=a[i];

           ②            ; 

}

if(left<j)

             ③       ; 

if(j<right)

               ④       ; 

}

int main()

{

int i;

cin>>n;

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

cin>>a[i];

maxDeep=0;

solve(1,n,1);

cout<<maxDeep<<' '<<num<<endl;

return 0;

}

答案与解析
参考答案

① num++

② j = i

③ solve(left, j – 1, deep + 1)

④ solve(j + 1, right, deep + 1)

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

假设输入的n和d[i]都是不超过10000的正整数,完成下面的判断题和单 选题:

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

假设输入的n, k和d[i]都是不超过10000的正整数,且k不超过n,并 假设rand()函数产生的是均匀的随机数,完成下面的判断题和单选题:

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

(2.5分)当输入的d[i]是严格单调递增序列时,第17行的 “swap”平均执行次数是()。

答案与解析
正确答案:A,B,C,D
这道题暂未补解析。
题目详情
597 简答题 偏难 信息学奥赛 ·信息学奥赛-提高级 · 1.4 并查集

01 #include <iostream>

02 #include <queue>

03 using namespace std;

04

05 const int max1 = 2000000000;

06

07 class Map (

08 struct item {

09 string key; int value;

10} d[max1];

11int cnt;

12public:

13int find(string x) {

14for (int i = 0; i < cnt; ++i)

15if (d[i].key == x)

16return d[i].value;

17return -1;

18}

19static int end() { return -1; } 

20void insert(string k, int v) {

21d[cnt].key = k; d[cnt++].value = v; 

22}

23} s[2];

24

25class Queue {

26string q[max1];

27int head, tail;

28public:

29void pop() { ++head; }

30string front() { return q[head + 1]; } 

31bool empty() { return head == tail; } 

32void push(string x) { q[++tail] = x; } 

33} q[2];

34

35string st0,stl;

36int m;

37

38string LtoR(string s, int L, int R) { 

39string t = s;

40char tmp = t[L];

41for (int i = L; i < R; ++i)

42t[i] = t[i + 1];

43t[R] = tmp;

44return t;

45}

46

47string RtoL(string s, int L,int R) { 

48string t = s;

49char tmp = t[R];

50for (int i = R; i > L; --i)

51t[i] = t[i - 1];

52t[L] = tmp;

53return t;

54}

55

56bool check(string st, int p,int step) { 

57if (s[p].find(st) != s[p].end()) 

58return false;

59++step;

60if (s[p ^ 1].find(st) == s[p].end()) { 

61s[p].insert(st, step); 

62q[p].push(st);

63return false;

64}

65cout << s[p ^ 1].find(st) + step << end1; 

66return true;

67}

68

69int main() {

70cin >> st0 >> stl;

71int len = st0.length();

72if (len != stl.length()) { 

73cout << -1 << end1; 

74return 0;

75}

76if (st0 == st1) { 

77cout << 0 << end1; 

78return 0;

79}

80cin >> m;

81s[0].insert(st0, 0); s[1].insert(st1, 0); 

82q[0].push(st0); q[1].push(st1);

83for (int p = 0;

84!(q[0].empty() && q[1].empty());

85p ^=1) {

86string st - q[p].front(); q[p].pop();

87int step = s[p].find(st);

88if ((p == 0 &&

89(check(LtoR(st,m, len - 1), p, step) || 

90check(RtoL(st, 0, m), p, step)))

91|| 

92(p == 1 &&

93(check(LtoR(st,0, m), p, step) || 

94check(RtoL(st, m, len - 1), p, step)))) 

95return 0;

96}

97cout << -1 << end1; 

98return 0;

99}

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

(分数背包)小S有n块蛋糕,编号从1到n第i块蛋糕的价值是wi, 体积是vi。他有一个大小为B的盒子来装这些蛋糕,也就是说装入盒子的 蛋糕的体积总和不能超过B。

他打算选择一些蛋糕装入盒子,他希望盒子里装的蛋糕的价值之和尽量 大。

为了使盒子里的蛋糕价值之和更大,他可以任意切割蛋糕。具体来说,他 可以选择一个a (0<a<l),并将一块价值是w,体枳为v的蛋糕切割成两 块.其中一块的价值是a・w,体枳是a・v,另一块的价值是(l-a)・w.体 积是(l-a)v。他可以重复无限次切割操作。

现要求编程输出最大可能的价值,以分数的形式输出。

比如n=3, B=8,三块蛋糕的价值分别是4、4、2,体枳分别是5、3、2。 那么最优的方案就是将休积为5的蛋糕切成两份,一份体积是3,价值是 2.4,另一份体积是2,价值是1.6,然后把休积是3的那部分和后两块蛋 糕打包进盒子。最优的价值之和是8.4,故程序输出42/5。

输入的数据范围为:1≤n≤1000,1≤B≤10^5;1≤wi,vi≤100。

提示:将所有的蛋糕按照性价比wi/vi从大到小排序后进行贪心选择。 

试补全程序。

#include <cstdio>

using namespace std;


const int maxn = 1005;


int n,B, w[maxn], v[maxn];


int gcd(int u, int v) {

if(v == 0)

return u;

return gcd(v, u % v);

}


void print(int w, int v) {

int d = gcd(w> v);

w = w / d;

v = v / d;

if(v == 1)

printf(”%d\n”, w);

else

printf(”%d/%d\n”, w, v);

}


void swap(int &x, int &y) { 

int t = x; x = y; y = t;

}


int main() {

scanf("%d %d", &n, &B);

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

scanf(”%d%d,&w[i], &v[i]);

}

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

for(int j = 1; j < n; j ++)

if(①){ 

swap(w[j], w[j + 1]); 

swap(v[j],v[j + 1]);

}

int curV, curW;

if(②) {

③

} else {

print(B * w[1], v[1]); 

return 0;

}


for(int i = 2; i <= n; i ++) 

if(curV + v[i] <= B) { 

curV += v[i]; 

curW += w[i];

} else {

print(④); 

return 0;

}

print (⑤);

return 0;

}


答案与解析
正确答案:(缺答案,待补录)
这道题暂未补解析。
题目详情
599 简答题 偏难 信息学奥赛 ·信息学奥赛-提高级 · 1.2 图

(最优子序列)取m=6,给出长度为n的整数序列a1,a2,……an(0 ≤ ai<2m)。对于一个二进制数x,定义其分值w(x)为x + popcnt(x),其中 popcnt(x)表示x二进制表示中1的个数。对于一个子序列b1,b2,…,bk,定 义其子序列分值S为w(b1㊉b2)+w(b2㊉b3)+w(b3㊉b4)+……+w(bk-1㊉bk)。其中㊉表示按位异或。对于空子序列,规定其子序列分值为0。求一个子序列使得其子序列分值最大,输出这个最大值。

输入第一行包含一个整数n(1 ≤ n ≤  40000).接下来一行包含n个整数 a1,a2,……,an。

提示:考虑优化朴素的动态规划算法,将前位和后位分开计算。

Max[x][y]表示当前的子序列下一个位置的高8位是X、最后一个位置的 低8位是y时的最大价值。

试补全程序。

答案与解析
正确答案:(缺答案,待补录)
这道题暂未补解析。
题目详情
600 简答题 偏难 信息学奥赛 ·信息学奥赛-提高级 · 1.2 图

(归并第 k 小)已知两个长度均为 n 的有序数组 a1 和 a2(均为递增序,但不保证严格单调递增),并且给定正整数 k(1≤k≤2n),求数组 a1 和 a2 归并排序后的数组里第 k 小的数值。

试补全程序。

#include <bits/stdc++.h> 

using namespace std; 


int solve(int *a1, int *a2, int n, int k) { 

  int left1 = 0, right1 = n - 1; 

  int left2 = 0, right2 = n - 1; 

  while (left1 <= right1 && left2 <= right2) { 

    int m1 = (left1 + right1) >> 1; 

    int m2 = (left2 + right2) >> 1; 

    int cnt =     ①     ; 

    if (     ②     ) { 

      if (cnt < k) left1 = m1 + 1; 

      else right2 = m2 - 1; 

    } else {

      if (cnt < k) left2 = m2 + 1; 

      else right1 = m1 - 1; 

    }

  }

  if (     ③     ) { 

    if (left1 == 0) {

      return a2[k - 1]; 

    } else {

      int x = a1[left1 - 1],      ④     ; 

      return std::max(x, y);

    }

  } else {

    if (left2 == 0) {

      return a1[k - 1]; 

    } else {

      int x = a2[left2 - 1],      ⑤     ; 

      return std::max(x, y);

    }

  }

} 

答案与解析
正确答案:(缺答案,待补录)
这道题暂未补解析。
题目详情