NOIP2011年提高组初赛真题

ID: 2377

客观题

尝试: 0

已通过: 0

难度: (无)

上传者:

stong9070

标签>

2011

NOIP

初赛真题

提高组

一、选择题（共 20 题，每题 1.5 分，共计 30 分；有单选和多选题）

第 1 题在二进制下，1011001 + （）= 1100110。 {{ select(1) }}

1011
1101
1010
1111

第 2 题字符 $\texttt A$ 的 ASCII 码为十六进制 41，则字符 $\texttt Z$ 的 ASCII 码为十六进制的（）。 {{ select(2) }}

66
5A
50
视具体的计算机而定

第 3 题下图是一棵二叉树，它的先序遍历是（）。

$\texttt{ABDEFC}$
$\texttt{DBEFAC}$
$\texttt{DFEBCA}$
$\texttt{ABCDEF}$

第 4 题寄存器是（）的重要组成部分。 {{ select(4) }}

硬盘
高速缓存
内存
中央处理器（CPU）

第 5 题广度优先搜索时，需要用到的数据结构是（）。 {{ select(5) }}

链表
队列
栈
散列表

第 6 题在使用高级语言编写程序时，一般提到的“空间复杂度”中的空间是指（）。 {{ select(6) }}

程序运行时理论上所占的内存空间
程序运行时理论上所占的数组空间
程序运行时理论上所占的硬盘空间
程序源文件理论上所占的硬盘空间

第 7 题应用快速排序的分治思想，可以实现一个求第 $K$ 大数的程序。假定不考虑极端的最坏情况，理论上可以实现的最低的算法时间复杂度为（）。 {{ select(7) }}

$( n^{2})$
$O(nlogn)$
$O(n)$
$O(1)$

第 8 题为解决 web 应用中的不兼容问题，保障信息的顺利流通，（）制定了一系列标准，涉及 HTML、XML、CSS 等，并建议开发者遵循。 {{ select(8) }}

微软
美国计算机协会（ACM）
联合国教科文组织
万维网联盟（W3C）

第 9 题体育课的铃声响了，同学们都陆续的奔向操场，按老师的要求从高到低站成一排。每个同学按顺序来到操场时，都从排尾走到排头，找到第一个比自己高的同学，并站在他的后面。这种站队的方法类似于（）算法。 {{ select(9) }}

快速排序
插入排序
冒泡排序
归并排序

第 10 题 1956年（）授予肖克利（William Shockley）、巴丁（John Bardeen）和布拉顿（Walter Brattain） {{ select(10) }}

诺贝尔物理学奖
约翰·冯·诺依曼奖
图灵奖
高德纳奖（Donald E. Knuth Prize）

第 11 题如果根结点的深度记为 1，则一棵恰有 2011 个叶子结点的二叉树的深度可能是（）。 {{ multiselect(11) }}

10
11
12
2011

第 12 题在布尔逻辑中，逻辑“或”的性质有（）。 {{ multiselect(12) }}

交换律：P∨Q=Q∨P
结合律：P∨(Q∨R)=(P∨Q)∨R
幂等律：P∨P=P
有界律：P∨1=1（1 表示逻辑真）

第 13 题一个正整数在十六进制下有 100位，则它在二进制下可能有（）位。 {{ multiselect(13) }}

第 14 题汇编语言（）。 {{ multiselect(14) }}

是一种与具体硬件无关的程序设计语言
在编写复杂程序时，相对于高级语言而言代码量大，且不易调试
可以直接访问寄存器、内存单元、I/O 端口
随着高级语言的诞生，如今已被完全淘汰，不再使用

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

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

指静脉验证
步态验证
ATM 机密码验证
声音验证

第 17 题对于序列7,5,1,9,3,6,8,4，在不改变顺序的情况下，去掉（）会使逆序对的个数减少 3。 {{ multiselect(17) }}

第 18 题计算机中的数值信息分为整数和实数（浮点数）。实数之所以能够表示很大或者很小的数，是由于使用了（）。 {{ multiselect(18) }}

阶码
补码
反码
较长的尾数

第 19 题对下图使用 Dijkstra 算法计算 $S$ 点到其余各点的最短路径长度时，到 $B$ 点的距离 $d[B]$ 初始时赋为 8，在算法的执行过程中还会出现的值有（）。 {{ multiselect(19) }}

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

HTTP
TCP/IP
FTP
WWW

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

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

第 23 题

#include<iostream>
#include<cstring>
using namespace std;
const int SIZE = 100;
int main()
{
    int n,i,sum,x,a[SIZE];
    
    cin>>n;
    memset(a,0,sizeof(a));
    
    for(i=1;i<=n;i++){
        cin>>x;
        a[x]++;
    }
    i=0;
    sum=0;
    while(sum<(n/2+1)){
        i++;
        sum+=a[i];
    }
    cout<<i<<endl;
    return 0;
}

输入： 11 4 5 6 6 4 3 3 2 3 2 1 输出：___________

第 24 题

#include<iostream>
using namespace std;
int n;
void f2(int x,int y);
void f1(int x,int y)
{
    if(x<n)
        f2(y,x+y);
}
void f2(int x,int y)
{
    cout<<x<<' ';
    f1(y,x+y);
}
int main()
{
    cin>>n;
    f1(0,1);
    return 0;

    return 0;
}

输入：30 输出：_______________

第 25 题

#include<iostream>
using namespace std;
const int V=100;
int n,m,ans,e[V][V];
bool visited[V];
void dfs(int x,int len)
{
    int i;
    visited[x]= true;
    if(len>ans)
       ans=len;
    for(i=1;i<=n;i++)
       if( (!visited[i]) && (e[x][i]!=-1) )
          dfs(i,len+e[x][i]);
    visited[x]=false;
}
int main()
{
    int i,j,a,b,c;
    cin>>n>>m;
    for(i=1;i<=n;i++)
       for(j=1;j<=m;j++)
          e[i][j]=-1;
    for(i=1;i<=m;i++)
    {
        cin>>a>>b>>c;
        e[a][b]=c;
        e[b][a]=c;
    }
    for(i=1;i<=n;i++)
       visited[i]=false;
    ans=0;
    for(i=1;i<=n;i++)
       dfs(i,0);
    cout<<ans<<endl;
    return 0;
}

输入：

输出：______________

第 26 题

#include<iostream>
#include<cstring>
#include<string>
using namespace std;
const int SIZE=10000;
const int LENGTH=10;
int n,m,a[SIZE][LENGTH];
int h(int u,int v)
{
    int ans,i;
    ans=0;
    for(i=1;i<=n;i++)
       if( a[u][i]!=a[v][i])
           ans++;
    return ans;
}
int main()
{
    int sum,i,j;
    cin>>n;
    memset(a,0,sizeof(a));
    m=1;
    while(1)
    {
        i=1;
        while( (i<=n) && (a[m][i]==1) )
            i++;
        if(i>n)
           break;
        m++;
        a[m][i]=1;
        for(j=i+1;j<=n;j++)
           a[m][j]=a[m-1][j];
    }
    sum=0;
    for(i=1;i<=m;i++)
       for(j=1;j<=m;j++)
          sum+=h(i,j);
    cout<<sum<<endl;
    return 0;
}

输入：7 输出：_________

第 27 题完善程序（大整数开方）输入一个正整数 $n(1≤n≤10^{100})$ ，试用二分法计算它的平方根的整数部分。

#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;
}

1、{{ input(27) }}

2、{{ input(28) }}

3、{{ input(29) }}

4、{{ input(30) }}

5、{{ input(31) }}

6、{{ input(32) }}

7、{{ input(33) }}

8、{{ input(34) }}

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

1、{{ input(35) }}

2、{{ input(36) }}

3、{{ input(37) }}

4、{{ input(38) }}

#2377. NOIP2011年提高组初赛真题

状态

开发

支持

#2377. NOIP2011年提高组初赛真题

NOIP2011年提高组初赛真题

状态

开发

支持

登录