CSP-S2019初赛易错题解析

发布时间 2023-08-27 15:16:22作者: 天雷小兔
一.6.由数字 1, 1, 2, 4, 8, 8 所组成的不同的 4 位数的个数是()

 102  98   100

错误原因:遗漏答案

正解:

使用穷举法,第一种ABCD型,共有A(4,4)=24种,第二种AABC型,共有A(4,2)*C(3,2)*2=72种,第三种AABB型,共有6种,总共是102种。

 

8.G 是一个非连通无向图(没有重边和自环),共有 28条边,则该图至少有 ()个顶点

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

错误原因:计算错误

正解:

共有28条边的图至少有8个点,但是是一个非连通图,所以有9个点

 

11.设 A 和 B 是两个长为 的有序数组,现在需要将 A 和 B 合并成一个排好序的数组,问任何以元素比较作为基本运算的归并算法,在最坏情况下至少要做多少次比较?()

A.n2  B.n log n C.2n-1  D.2n

错误原因:没读懂题

正解:

两两比较,最后两次比较一次就够了,所以是2n-1次

 

二.2.6.此程序的时间复杂度是()

A.O(n*n)  B.O(log n)  C.O(n)  D.O(n log n)

错误原因:并查集不带路径压缩的复杂度是O(n)的