绷。
随便应付应付得了。
点击查看目录
CSP-S 2022
54pts。
- 你同时用 time 命令和秒表为某个程序在单核 CPU 的运行计时。假如 time 命令的输出如下：
real 0m30.721s
user 0m24.579s
sys 0m6.123s
以下最接近秒表计时的时长为（ ）。
A. 30s
B. 24s
C. 18s
D. 6s
ans：A
real 最接近真实值，user 是程序运行时间，sys 是因为各种因素用的时间。
- 考虑对 n 个数进行排序，以下最坏时间复杂度低于 \(O(n^2)\) 的排序方法是（ ）。
A. 插入排序
B. 冒泡排序
C. 归并排序
D. 快速排序
ans：C
回顾各种排序方式：
-
插入排序 \(O(n)-O(n^2)\)：把 \(n\) 个待排序的元素看成为一个有序表和一个无序表，开始时有序表中只包含一个元素，无序表中包含有 \(n-1\) 个元素，排序过程中每次从无序表中取出第一个元素，把它的排序码依次与有序表元素的排序码进行比较，将它插入到有序表中的适当位置，使之成为新的有序表。
-
冒泡排序 \(O(n)-O(n^2)\)：单次将最大的元素往前冒泡。
-
归并排序 \(O(n)-O(nlogn)\)：分治，将两个的有序数列合并成一个有序数列。
-
快速排序 \(O(n)-O(n^2)\)：分治，是冒泡排序的改进，通常时间复杂度低于 \(O(nlogn)\)。
- 计算机系统用小端（Little Endian）和大端（Big Endian）来描述多字节数据的存储地 址顺序模式，其中小端表示将低位字节数据存储在低地址的模式、大端表示将高位字节数 据存储在低地址的模式。在小端模式的系统和大端模式的系统分别编译和运行以下 C++代码段表示的程序，将分别输出什么结果？（ ）
unsigned x = 0xDEADBEEF;
unsigned char *p = (unsigned char *)&x;
printf("%X", *p);
A. EF、EF
B. EF、DE
C. DE、EF
D. DE、DE
ans：B
大端和小端是用于描述存储多字节数据在计算机内存中的字节顺序的概念。
-
在大端字节序中，高位字节被存储在较低的内存地址，而低位字节被存储在较高的内存地址。这就好像把多字节数据当作一个整数，高位字节在前，低位字节在后。
-
在小端字节序中，高位字节被存储在较高的内存地址，而低位字节被存储在较低的内存地址。这就好像把多字节数据当作一个整数，低位字节在前，高位字节在后。
- 每个顶点度数均为 2 的无向图称为“2 正规图”。由编号为从 1 到 n 的顶点构成的所有 2 正规图，其中包含欧拉回路的不同 2 正规图的数量为（ ）。
A. n!
B. (n-1)!
C. n!/2
D. (n-1)!/2