You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

二 程序设计基础

2.1 程序基本知识

1),【NOIP1998提高组】表达式(4 %(-3))与(-4% 3)的值为( ) {{ select(1) }}

• -1,-1
• 1,-1
• –1,1
• 1,1

2), 【NOIP2002】一个向量第一个元素的存储地址是100,每个元素的长度是2,则第5个元素的地址是( )。{{ select(2) }}

• 110
• 108
• 100
• 109

3),【NOIP2001】]下面关于算法的错误说法是() {{ select(3) }}

• 算法必须有输出
• 算法必须在计算机上用某种语言实现
• 算法不一定有输入
• 算法必须在有限步执行后能结束

4), 【NOIP2006普及组】在下列各种排序算法中,不是以"比较"作为主要排作的算法是() {{ select(4) }}

• 选择排序
• 冒泡排序
• 插入排序
• 基数排序

5),【NOIP2000】某数列有1000个各不相同的单元,由低至高按序排列。现要对该数列进行二分法查找(binary search),在最坏的情况下,须检视( )个单元。 {{ select(5) }}

• 1000
• 10
• 100
• 500

6), 【NOIP2001】在顺序表(2,5,7,10,14, 15, 18, 23,35,41,52)中,用二分法查找12,所需的关键码比较的次数为( ) {{ select(6) }}

• 2
• 3
• 4
• 5

7),【NOIP2004提高组】由3个a,5个b和2个c构成的所有字符串中,包含子串"abc"的共有（)个。{{ select(7) }}

• 40320
• 39600
• 840
• 780
• 60

8),【NOIP2005提高组】字符串"ababacbab"和字符串"abcba"的最长公共子串是() {{ select(8) }}

• abeba
• cba
• abe
• ab
• beba

9),【NOIP2000】电线上停着两种鸟(A,B) ,可以看出两只相邻的鸟就将电线分为了一个线段。这些线段可分为两类:一类是两端的小鸟相同;另一类则是两端的小鸟不相同。已知:电线两个顶点上正好停着相同的小鸟,试问两端为不同小鸟的线段数目一定是()。{{ select(9) }}

• 奇数
• 偶数
• 可奇可偶
• 数目固定

10), 【NOIP2000】线性表若采用链表存储结构,要求内存中可用存储单元地址() {{ select(10) }}

• 必须连续
• 一定不连续
• 部分地址必须连续
• 连续不连续均可

11), 【NOIP2000】下列叙述中,正确的是() {{ select(11) }}

• 线性表的线性存储结构优于链表存储结构
• 队列的操作方式是先进后出
• 栈的操作方式是先进先出
• 二维数组是指它的每个数据元素为一个线性表的线性表

12), 链表不具有的特点是（）。{{ select(12) }}

• 可随机访问任一元素
• 不必事先估计存储空间
• 插入删除不需要移动元素
• 所需空间与线性表长度成正比

13), 设有100个已排好序的数据元素，采用折半查找时，最大比较次数为（）{{ select(13) }}

• 7
• 10
• 6
• 8

14), 链表不具有的特点是（）{{ select(14) }}

• 插入删除不需要移动元素
• 不必事先估计存储空间
• 所需空间与线性表长度成正比
• 可随机访问任一元素

15), 以下排序算法中，不需要进行关键字比较操作的算法是（ ）。{{ select(15) }}

• 基数排序
• 冒泡排序
• 堆排序
• 选择排序

16), 下面的故事与（ ）算法有着异曲同工之妙。

从前有座山，山里有座庙，庙里有个老和尚在给小和尚讲故事：“从前有座山，山里有座庙，庙里有个老和尚在给小和尚讲故事：‘从前有座山，山里有座庙，庙里有个老和尚给小和尚讲故事……’”{{ select(16) }}

• 枚举
• 递归
• 贪心
• 分治

17), 若串 S = “copyright”，其子串的个数是（ ）。{{ select(17) }}

• 72
• 45
• 46
• 36

18), 某算法的计算时间表示为递推关系式 T(n)=T(n-1)+n(n 为正整数)及 T(0)=1，则该算法的时间复 杂度为( )。{{ select(18) }}

• O(logn)
• O(nlogn)
• O(n)
• O(n^2)

19), 下面的故事与（ ）算法有着异曲同工之妙。 从前有座山，山里有座庙，庙里有个老和尚在给小和尚讲故事：从前有座山，山里有座庙，庙里有个老和尚在给小和尚讲故事：‘从前有座山，山里有座庙，庙里有个老和尚给小和尚讲故事....’ {{ select(19) }}

• 枚举
• 递归
• 贪心
• 分治

20), （ ）的 平均时间复杂度为 O(n log n)，其中 n 是待排序的元素个数。{{ select(20) }}

• 快速排序
• 插入排序
• 冒泡排序
• 基数排序

21), 使用冒泡排序对序列进行升序排列，每执行一次交换操作系统将会减少1个逆序对，因此序列 5，4，3，2，1需要执行（ ）次操作，才能完成冒泡排序。{{ select(21) }}

• 0
• 5
• 10
• 15

22),（ ）就是把一个复杂的问题分成两个或更多的相同类似的子问题，再把子问题分解成更小的子问题……直到最后的子问题可以简单地直接求解。而原问题的解就是子问题解的并。{{ select(22) }}

• 动态规划
• 贪心
• 分治
• 搜索

23), 原字符串中任意一段连续的字符所组成的新字符串称为子串。则字符“AAABBBCCC”共有（ ）个不同的非空子串。{{ select(23) }}

• 3
• 12
• 36
• 45

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

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

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

• 链表
• 队列
• 栈
• 散列表

26), 设字符串S=”Olympic”，S的非空子串的数目是（ ）。{{ select(26) }}

• 28
• 29
• 16
• 17

27), 对有序数组{5, 13, 19, 21, 37, 56, 64, 75, 88，92，100}进行二分查找，成功查找元素19的查找长度（比较次数）是（ ）。{{ select(27) }}

• 1
• 2
• 3
• 4

28), 假设某算法的计算时间表示为递推关系式 T(n) = 2T(n/4)+sqrt(n), T(1) = 1T(1)=1 则算法的时间复杂度为（ ）。{{ select(28) }}

• O(n)
• O(sqrt(n))
• O(sqrt(n)*logn)
• O(n^2)

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

• Θ(n)
• Θ(n log n)
• Θ(n^2)
• Θ(n^2 log n)