算法与复杂度（二） - 题目详情 - tarjanoj

ID: 35

客观题

难度: 2

上传者:

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

$0$
$5$
$10$
$15$

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

动态规划
贪心
分治
搜索

在程序运行过程中，如果递归调用的层数过多，会因为（）引发错误。 {{ select(3) }}

系统分配的栈空间溢出
系统分配的堆空间溢出
系统分配的队列空间溢出
系统分配的链表空间溢出

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

$3$
$12$
$36$
$45$

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

枚举
递归
贪心
分治

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

$x\bmod 11$
$x^2\bmod 11$
$(2x)\bmod 11$
$\lfloor\sqrt{x}\rfloor\bmod 11$ ，其中 $\lfloor\sqrt{x}\rfloor$ 表示 $\sqrt{x}$ 下取整

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

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

下面是根据欧几里得算法编写的函数，它所计算的是 $a$ 和 $b$ 的（）。

int euclid(int a, int b)
{
	if (b == 0)
		return a;
	else
		return euclid(b, a % b);
}

{{ select(8) }}

最大公共质因子
最小公共质因子
最大公约数
最小公倍数

下列程序中，正确计算 $1,2,\ldots,100$ 这 $100$ 个自然数之和 sum （初始值为 $0$ ）的是（）。 {{ select(9) }}

i = 1; do{ sum += i; i++; } while(i <= 100);
i = 1; do{ sum += i; i++; } while(i > 100);
i = 1; while(i < 100){ sum += i; i++; }
i = 1; while(i >= 100){ sum += i; i++; }

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

$O(\log n)$
$O(n\log n)$
$O(n)$
$O(n^2)$

如果开始时计算机处于小写输入状态，现在有一只小老鼠反复按照CapsLock、字母键 A、字母键 S 和字母键 D 的顺序循环按键，即 CapsLock、A、S、D、CapsLock、A、S、D、……，屏幕上输出的第 $81$ 个字符是字母（）。 {{ select(11) }}

$A$
$S$
$D$
$a$

若有如下程序段，其中 $s、a、b、c$ 均已定义为整型变量，且 $a、c$ 均已赋值（ $c$ 大于 $0$ ）。

s = a;
for (b = 1; b <= c; b++ )
	s = s + 1;

则与上述程序段修改 $s$ 值的功能等价的赋值语句是（）。 {{ select(12) }}

s = a + b;
s = a + c;
s = s + c;
s = b + c;

有以下程序：

#include <iostream>
using namespace std;
int main()
{
    int k = 4, n = 0;
    while (n < k)
    {
        n++;
        if (n % 3 != 0)
            continue;
        k--;
    }
    cout << k << "," << n << endl;
    return 0;
}

程序运行后输出的结果是（）。 {{ select(13) }}

$2,2$
$2,3$
$3,2$
$3,3$

对于给定的序列 $a$ ，我们把 $(i, j)$ 称为逆序对当且仅当 $i < j$ 且 $a_i > a_j$ 。那么序列 $1, 7, 2, 3, 5, 4$ 的逆序对数为（）个。 {{ select(14) }}

$4$
$5$
$6$
$7$

若串 S = "copyright"，其子串的个数是（）。 {{ select(15) }}

$72$
$45$
$46$
$36$

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

基数排序
冒泡排序
堆排序
直接插入排序

给定一个含 $N$ 个不相同数字的数组，在最坏情况下，找出其中最大或最小的数，至少需要 $N - 1$ 次比较操作。则最坏情况下，在该数组中同时找最大与最小的数至少需要（）次比较操作。（⌈ ⌉表示向上取整，⌊ ⌋表示向下取整） {{ select(17) }}

$\lceil \frac{3N}{2}\rceil - 2$
$\lfloor\frac{3N}{2}\rfloor - 2$
$2N - 2$
$2N - 4$

设 A 是 $n$ 个实数的数组，考虑下面的递归算法：

XYZ (A[1..n])
            1.  if n= 1 then return A[1]
            2.   else temp ← XYZ (A[l..n-1])
            3.         if temp < A[n]
            4.         then return temp
            5.         else return A[n]

请问算法 XYZ 的输出是什么？（）。

{{ select(18) }}

$A$ 数组的平均
$A$ 数组的最小值
$A$ 数组的中值
$A$ 数组的最大值

在数据压缩编码中的哈夫曼编码方法，在本质上是一种（）的策略。 {{ select(19) }}

枚举
贪心
递归
动态规划

运行以下代码片段的行为是（）。

int x = 101;
int y = 201;
int *p = &x;
int *q = &y;
p = q;

{{ select(20) }}

将 $x$ 的值赋为 $201$
将 $y$ 的值赋为 $101$
将 $q$ 指向 $x$ 的地址
将 $p$ 指向 $y$ 的地址

以下排序算法的常见实现中，哪个选项的说法是错误的：（）。 {{ select(21) }}

冒泡排序算法是稳定的
简单选择排序是稳定的
简单插入排序是稳定的
归并排序算法是稳定的

以下对递归方法的描述中，正确的是：（）。 {{ select(22) }}

递归是允许使用多组参数调用函数的编程技术
递归是通过调用自身来求解问题的编程技术
递归是面向对象和数据而不是功能和逻辑的编程语言模型
递归是将用某种高级语言转换为机器代码的编程技术

阅读下面代码，请问修改 data 的 value 成员以存储 3.14, 正确的方式是（）。

union Data {
    int num;
    float value;
    char symbol;
};
union Data data;

{{ select(23) }}

data.value = 3.14;
value.data = 3.14;
data->value = 3.14;
value->data = 3.14;

以下关于高精度运算的说法错误的是（）。 {{ select(24) }}

高精度计算主要是用来处理大整数或需要保留多位小数的运算
大整数除以小整数的处理的步骤可以是，将被除数和除数对齐，从左到右逐位尝试将除数乘以某个数，通过减法得到新的被除数，并累加商
高精度乘法的运算时间只与参与运算的两个整数中长度较长者的位数有关
高精度加法运算的关键在于逐位相加并处理进位

假设有序表中有 $1000$ 个元素，则用二分法查找元素 $x$ 最多需要比较（）次。 {{ select(25) }}

$25$
$10$
$7$
$1$