跳转至

信息学奥林匹克竞赛提高组笔试复习题

一、计算机理论知识

  1. 一个字节（byte）由（ 8 ）个二进制位组成。

  2. 一个 32 位整型变量占用（ 4 ）个字节。

  3. Linux下可执行文件的默认扩展名为（ D ）

    A. exe B. com C. dll D. 以上都不是

  4. 提出“存储程序”的计算机工作原理的是（ D ）

    A. 克劳德·香农 信息论 B. 戈登·摩尔 Intel创始人，摩尔定律 C. 查尔斯·巴比奇 差分机与分析机 D. 冯·诺依曼 存储程序与程序控制

  5. 1948 年，（ D ）将热力学中的熵引入信息通信领域，标志着信息论研究的开端。

    A. 冯·诺伊曼（John von Neumann） B. 图灵（Alan Turing） C. 欧拉（Leonhard Euler） D. 克劳德·香农（Claude Shannon）

  6. 主存储器的存取速度比中央处理器（CPU）的工作速度慢很多，从而使得后者的效率受到影响。而根据局部性原理，CPU所访问的存储单元通常都趋于聚集在一个较小的连续区域中。于是，为了提高系统整体的执行效率，在CPU中引入了（ B ）。

    A. 寄存器 B. 高速缓存 C. 闪存 D. 外存

    寄存器是中央处理器内的组成部分。寄存器是有限存贮容量的高速存贮部件，它们可用来暂存指令、数据和位址。 闪存（Flash Memory）是一种长寿命的非易失性（在断电情况下仍能保持所存储的数据信息）的存储器由于其断电时仍能保存数据，闪存通常被用来保存设置信息，如在电脑的BIOS 外储存器是指除计算机内存及CPU缓存以外的储存器，此类储存器一般断电后仍然能保存数据。常见的外储存器有硬盘、软盘、光盘、U盘等。 “高速缓存”的目的是为了让数据访问的速度适应CPU的处理速度，其基于的原理是内存中“程序执行与数据访问的局域性行为”，即一定程序执行时间和空间内，被访问的代码集中于一部分。

  7. 目前计算机芯片（集成电路）制造的主要原料是（ 硅 ），它是一种可以在沙子中提炼出的物质。

  8. （ 浏览器 ）是主要用于显示网页服务器或者文件系统的 HTML 文件内容，并让用户与这些文件交互的一种软件。

  9. （ CPU ）厂商包括（ AMD、Intel）等。

  10. 分辨率为1600x900，16位色的位图，存储图像信息所需的空间为（ 2812.5KB ）。

  11. 2020年10月1日是星期四，1949年10月1日是（ 星期六 )。

  12. 地址总线的位数决定了 CPU 可直接寻址的内存空间大小，例如地址总线为 16 位，其最大的可寻址空间为 64KB。如果地址总线是 32 位，则理论上最大可寻址的内存空间为（ D ）。

    A. 128KB B. 1MB C. 1GB D. 4GB

  13. 某计算机的CPU和内存之间的地址总线宽度为32位（bit），这台计算机最多可以使用（ B ）的内存。

    A. 2GB B. 4GB C. 8GB D. 16GB

  14. IPv4 协议使用 32 位地址，随着其不断被分配，地址资源日趋枯竭。因此，它正逐渐被使用（ D ）位地址的 IPv6 协议所取代。

    A. 40 B. 48 C. 64 D. 128

    IPV6地址大小为128位，表示法为x:x:x:x:x:x:x:x，每个x是地址的8个16位部分的十六进制值。地址范围从0000:0000:0000:0000:0000:0000:0000:0000 至 ffff:ffff:ffff:ffff:ffff:ffff:ffff:ffff

  15. 下面哪个是面向对象的高级语言（ B ）。

    A. 汇编语言 B. C++ C. Fortran D. Basic

    面向对象的语言有 C++, Java, C#, Python等。

  16. 1TB代表的字节数量是（ D ）。

    A. 2的10次方 B. 2的20次方 C. 2的30次方 D. 2的40次方

    \({1TB=2^{10}GB=2^{10}*2^{10}MB=2^{10}*2^{10}*2^{10}KB=2^{10}*2^{10}*2^{10}*2^{10}B}\)

  17. TCP协议属于哪一次协议（ B ）。

    A. 应用层 B. 传输层 C. 网络层 D. 数据链路层

    TCP/IP四层模型中，TCP协议处于传输层，IP协议处于网络层。与邮件相关的协议有SMTP（简单邮件传输协议）、POP3（邮局协议）、IMAP（Internet消息访问协议）。

  18. 以下几个32位IP地址中，书写错误的是（ C ）。

    A. 162.105.142.27 B. 192.168.0.1 C. 256.256.129.1 D. 10.0.0.1

    32位的IP地址是由点号分开的四个部分，每个部分用8位二进制表示，所以这四个部分的取值范围是0～255。

  19. 在数据压缩编码的应用中，哈夫曼（Huffman）算法是一种采用了（ A ）思想的算法。

    A. 贪心 B. 分治 C. 递推 D. 回溯

  20. 从（ C ）年开始，NOIP竞赛将不再支持Pascal语言。

    A. 2020 B. 2021 C. 2022 D. 2023

    CCF关于NOI系列赛事程序设计语言变更的公告-2016.11.01

    1.2020年开始，除NOIP以外的NOI系列其他赛事（包括冬令营、CTSC、APIO、NOI）将不再支持Pascal语言和C语言；

    2.从2022年开始，NOIP竞赛也将不再支持Pascal语言。即从NOIP2022开始，NOI系列的所有赛事将全部取消Pascal语言。

    3.在无新增程序设计语言的情况下，NOI系列赛事自NOIP2022开始将仅支持C++语言。

二、进制问题

  1. 下列四个不同进制的数中，与其它三项数值上不相等的是（ D ）。

    A. \({(269)_{16}}\) B. \({(617)_{10}}\) C. \({(1151)_{8}}\) D. \({(1001101011)_{2}}\)

  2. 二进制数 11.01 在十进制下是（ A ）。

    A. \({3.25}\) B. \({4.125}\) C. \({6.25}\) D. \({11.125}\)

  3. 与16进制数 A1.2 等值的 10 进制数是（ C ）

    A. \({101.2}\) B. \({111.4}\) C. \({161.125}\) D. \({177.25}\)

  4. 如果在某个进制下等式 \({7*7=41}\) 成立， 那么在该进制下等式 \({12*12=}\)（ B ）也成立。

    A. \({100}\) B. \({144}\) C. \({164}\) D. \({196}\)

  5. 在八位二进制补码中，10101011 表示的是十进制下的（ B ）。

    A. 43 B. -85 C. -43 D. -84

    补码=原码的反码+1，最高位为符号位（0表示正，1表示负）不变

三、数据结构问题

  1. 前缀表达式 \({+3*2+5 12}\) 的值是（ C ）

    A. 23 B. 25 C. 37 D. 65

  2. 表达式 \({a*(b+c)-d}\)的后缀表达形式为（ B ）。

    A. \({abcd*+-}\) B. \({abc+*d-}\) C. \({abc*+d-}\) D. \({-+*abcd}\)

  3. 表达式\({a*(b+c)*d}\)的后缀形式是（ B ）。

    A. \({abcd*+*}\) B. \({abc+*d*}\) C. \({a*bc+*d}\) D. \({b+c*a*d}\)

  4. 已知一棵二叉树有 2013 个节点，则其中至多有（ A ）个节点有 2 个子节点。

    A. 1006 B. 1007 C. 1023 D. 1024

  5. 二叉查找树具有如下性质：每个节点的值都大于其左子树上所有节点的值、小于其右子树上所有节点的值。那么，二叉查找树的（ B ）是一个有序序列。

    A. 先序遍历 B. 中序遍历 C. 后序遍历 D. 宽度优先遍历

  6. 在无向图中，所有的顶点的度数之和是边数的（ C ）倍。

    A. 0.5 B. 1 C. 2 D. 4

  7. G是一个非连通简单无向图，共有28条边，则该图至少有（ B ）个顶点。

    A. 10 B. 9 C. 8 D. 7

  8. 线性表若采用链表存储结构，要求内存中的可用存储单元地址（ D ）。

    A. 必须连续 B. 部分地址必须连续 C. 一定不连续 D. 连续不连续均可

  9. 有以下结构体说明和变量定义，如图所示，指针p、q、r分别指向一个链表中的三个连续节点。

        struct node {
        int data;
        node *next;
    } *p, *q, *r;

    现在将q和r所指结点的先后位置交换，同时要保持链表的连续，以下程序段中错误的是（ D ）。

    A. q->next = r->next; p->next = r; r->next = q;

    B. p->next = r; q->next = r->next; r->next = q;

    C. q->next = r->next; r->next = q; p->next = r;

    D. r->next = q; q->next = r->next; p->next = r;

  10. 双向链表中有两个指针域，llink 和 rlink，分别指回前驱及后继，设 p 指向链表中的一个结点，q 指向一待插入结点，现要求在 p 前插入 q，则正确的插入为（ D ）。

    A. p->llink = q; q->rlink = p; p->llink->rlink = q; q->llink = p->llink;

    B. q->llink = p->llink; p->llink->rlink = q; q->rlink = p; p->llink = q->rlink;

    C. q->rlink = p; p->rlink = q; p->llink->rlink = q; q->rlink = p;

    D. p->llink->rlink = q; q->rlink = p; q->llink = p->llink; p->llink = q;

  11. x

  12. 设G是有6个结点的完全图，要得到一棵生成树，需要从G中删去（ C ）条边。

    A. 6 B. 9 C. 10 D. 15

    完全图是一个简单的无向图，其中每对不同的顶点之间都恰连有一条边相连。对连通图进行遍历，过程中所经过的边和顶点的组合可看做是一棵普通树，通常称为生成树。

  13. 今有一空栈 S，对下列待进栈的数据元素序列 a,b,c,d,e,f 依次进行进栈，进栈，出栈，进栈，进栈，出栈的操作，则此操作完成后，栈 S 的栈顶元素为（ B ）。

    A. f B. c C. a D. b

  14. 对于入栈顺序为 \({a, b, c, d, e, f, g}\) 的序列，下列（ C ）不可能是合法的出栈序列。

    A. \({a, b, c, d, e, f, g}\) B. \({a, d, c, b, e, g, f}\) C. \({a, d, b, c, g, f, e}\) D. \({g, f, e, d, c, b, a}\)

  15. 前序遍历序列与后序遍历序列相同的二叉树为（ B ）。

    A. 非叶子结点只有左子树的二叉树 B. 只有根结点的二叉树 C. 根结点无右子树的二叉树 D. 非叶子结点只有右子树的二叉树

  16. 如果根的高度为 1，具有 61 个结点的完全二叉树的高度为（ B ）。

    A. 5 B. 6 C. 7 D. 8

  17. 6个顶点的连通图的最小生成树，其边数为（ B ）。

    A. 6 B. 5 C. 7 D. 4

  18. 设 G 是有 n 个结点、m 条边（ n <= m ）的连通图，必须删去 G 的（ A ）条边，才能使得 G 变成一棵树。

    A. m - n + 1 B. m - n C. m + n + 1 D. n - m + 1

  19. 由四个不同的点构成的简单无向连通图的个数为（ C ）。

    A. 32 B. 35 C. 38 D. 41

四、数学（排列组合、概率论、数论、离散等）、算法问题

  1. 排列公式： \({\displaystyle A_n^m=\frac{n!}{(n-m)!}}\)

  2. 组合公式： \({\displaystyle C_n^m=\frac{n!}{m!(n-m)!}}\)

  3. 等差数列求和公式： \({\displaystyle \frac{n(a_1+a_n)}{2}}\)

  4. 等比数列求和公式：\({\displaystyle \frac{a_1(1-q^n)}{1-q}}\)

  5. 图论常用算法及简介

算法名称 实现策略 简介
Dijkstra算法 贪心 迪杰斯特拉算法(Dijkstra)是由荷兰计算机科学家狄克斯特拉于1959 年提出的，因此又叫狄克斯特拉算法。是从一个顶点到其余各顶点的最短路径算法，解决的是有权图中最短路径问题。迪杰斯特拉算法主要特点是从起始点开始，采用贪心算法的策略，每次遍历到始点距离最近且未访问过的顶点的邻接节点，直到扩展到终点为止。
Floyd算法 动态规划 Floyd算法又称插点法，是一种利用动态规划的思想寻找给定的加权图中多源点之间最短路径的算法，与Dijkstra算法类似。该算法名称以创始人之一、1978年图灵奖获得者、斯坦福大学计算机科学系教授罗伯特·弗洛伊德命名。
Prim算法 贪心 普里姆算法（Prim算法），图论中的一种算法，可在加权连通图里搜索最小生成树。意即由此算法搜索到的边子集所构成的树中，不但包括了连通图里的所有顶点（英语：Vertex (graph theory)），且其所有边的权值之和亦为最小。该算法于1930年由捷克数学家沃伊捷赫·亚尔尼克（英语：Vojtěch Jarník）发现；并在1957年由美国计算机科学家罗伯特·普里姆（英语：Robert C. Prim）独立发现；1959年，艾兹格·迪科斯彻再次发现了该算法。因此，在某些场合，普里姆算法又被称为DJP算法、亚尔尼克算法或普里姆－亚尔尼克算法。
Kruskal算法 贪心 克鲁斯卡尔算法是求连通网的最小生成树的另一种方法。与普里姆算法不同，它的时间复杂度为O（eloge）（e为网中的边数），所以，适合于求边稀疏的网的最小生成树。

  1. 以下逻辑表达式的值恒为真的是（ A ）

    A. \({P ∨ (┐P ∧ Q) ∨ (┐P ∧ ┐Q)}\)

    B. \({Q ∨ (┐P ∧ Q) ∨ (P ∨ ┐Q)}\)

    C. \({P ∨ Q ∨ (P ∧ ┐Q)∨(┐P ∧ Q)}\)

    D. \({P ∨ ┐Q ∨ (P ∧ ┐Q) ∨ (┐P ∧ ┐Q)}\)

  2. 同时查找2n个数中最大值和最小值，最少的比较次数是（ C ）。

    A. \({3(n-2)/2}\) B. \({4n-2}\) C. \({3n-2}\) D. \({2n-2}\)

  3. 以下时间复杂度不是\({O(n^2)}\)的排序方法是（ B ）。

    A. 插入排序 B. 归并排序 分治算法 C. 冒泡排序 D. 选择排序

  4. 以下排序算法在最坏情况下时间复杂度最优的有（ CD ）。

    A. 冒泡排序 B. 快速排序 C. 归并排序 D. 堆排序

  5. 下列算法中，（ D ）是稳定的排序算法。

    A. 快速排序 B. 堆排序 C. 希尔排序 D. 插入排序

排序算法 平均时间复杂度 最好情况 最坏情况 空间复杂度 排序方式 稳定性
冒泡排序 \({O(n^2)}\) \({O(n)}\) \({O(n^2)}\) \({O(1)}\) In-place 稳定
选择排序 \({O(n^2)}\) \({O(n^2)}\) \({O(n^2)}\) \({O(1)}\) In-place 不稳定
插入排序 \({O(n^2)}\) \({O(n)}\) \({O(n^2)}\) \({O(1)}\) In-place 稳定
希尔排序 \({O(n log n)}\) \({O(n log^2 n)}\) \({O(n log^2 n)}\) \({O(1)}\) In-place 不稳定
归并排序 \({O(n log n)}\) \({O(n log n)}\) \({O(n log n)}\) \({O(n)}\) Out-place 稳定
快速排序 \({O(n log n)}\) \({O(n log n)}\) \({O(n^2)}\) \({O(log n)}\) In-place 不稳定
堆排序 \({O(n log n)}\) \({O(n log n)}\) \({O(n log n)}\) \({O(1)}\) In-place 不稳定
计数排序 \({O(n + k)}\) \({O(n + k)}\) \({O(n + k)}\) \({O(k)}\) Out-place 稳定
桶排序 \({O(n + k)}\) \({O(n + k)}\) \({O(n^2)}\) \({O(n + k)}\) Out-place 稳定
基数排序 \({O(n \times k)}\) \({O(n \times k)}\) \({O(n \times k)}\) \({O(n + k)}\) Out-place 稳定

  1. \({T(n)}\)表示某个算法输入规模为 \({n}\) 时的运算次数。如果 \({T(1)}\) 为常数，且有递归式 \({T(n) =2*T(n / 2) + 2n}\)，那么 \({T(n) = }\)（ B ）。

    A. \({Θ(n)}\) B. \({Θ(nlogn)}\) C. \({Θ(n^2)}\) D. \({Θ(n^2logn)}\)

    1.猜 2.数学归纳法 3. 展开 4. 推导公式

  2. 设某算法的计算时间表示为递推关系式 \({T(n) = T(n - 1) + n}\)（\({n}\)为正整数）及 \({T(0) = 1}\)，则该算法的时间复杂度为（ D ）。

    A. \({O(log n)}\) B. \({O(nlogn)}\) C. \({O(n)}\) D. \({O(n^2)}\)

  3. 假设某算法的计算时间表示为递推关系式

    \({\displaystyle T(n)=2T(\frac{n}{4})+\sqrt{n}}\)

    \({T(1)=1}\)

    则算法的时间复杂度为（ C ）。

    A. \({O(n)}\) B. \({O(\sqrt{n})}\) C. \({O(\sqrt{n}logn}\) D. \({O(n^2)}\)

  4. 若某算法的计算时间表示为递推关系式：

    \({\displaystyle T(N)=2T(N/2)+NlogN}\)

    \({\displaystyle T(1)=1}\)

    则该算法的时间复杂度为（ C ）。

    A. \({O(N)}\) B. \({O(NlogN)}\) C. \({O(Nlog^2N)}\) D. \({O(N^2)}\)

  5. 在以比较作为基本运算，在\({N}\)个数中找最小数的最少运算次数为（ B ）。

    A. \({N}\) B. \({N-1}\) C. \({N^2}\) D. \({log N}\)

  6. 将\({(2, 6, 10, 17)}\)分别存储到某个地址区间为 \({0 \sim 10}\) 的哈希表中，如果哈希函数 h(x) = ( D )，将不会产生冲突，其中 a mod b 表示 a 除以 b 的余数。

    A. \({x mod 11}\) B. \({x^2 mod 11}\) C. \({2x mod 11}\) D. \({⌊\sqrt{x}}⌋\) mod 11，其中 \({ ⌊ \sqrt{} ⌋ }\) 表示 \({ \sqrt{} }\) 下取整

  7. 有7个一摸一样的苹果，放到3个一样的盘子中，一共有（ B ）种放法。

    A. \({7}\) B. \({8}\) C. \({21}\) D. \({3^7}\)

  8. 将7个名额分给4个不同的班级，允许有的班级没有名额，有（ D ）种不同的分配方案。

    A. 60 B. 84 C. 96 D. 120

    1. 枚举法 2. 插板法

  9. 若\({f[0]=0, f[1]=1}, f[n+1]=(f[n]+f[n-1])/2\)，随着 \({i}\) 的增大，\({f[i]}\) 将接近于（ B ）。

    A. \({1/2}\) B. \({2/3}\) C. \({\displaystyle \frac{\sqrt{5}-1}{2}}\) D. \({1}\)

五、其他问题

最后更新: 2021-09-08
Back to top