北京理工大学ACM CLUB2019级新生有基础组能力测试题解

Author： xzm2019
发布时间：October 7, 2019
1531views
No comments
9583字数
Categories：算法

## 选择题

> 逻辑表达式$(A \wedge B) \wedge \neg A$的值为（）
>
> ```
> A.B
> B.¬B
> C.恒真
> D.恒假
> ```

| Info.        | Num                       |
| ------------ | ------------------------- |
| AC rate      | $77.3\%$ |
| Ans.         | D                         |
| Reason       | $A \wedge \neg A = false$ |

> 在一个含有10个元素的集合里，其非空子集的数量是（）
>
> ```
> A.1024
> B.1025
> C.1023
> D.512
> ```

| Info.        | Num                 |
| ------------ | ------------------- |
| AC rate      | $97.7\%$ |
| Ans.         | C                   |
| Reason       | $2^{10} - 1 = 1023$ |

> 在10000以内，不能被3整除也不能被2整除的数有（）个
>
> ```
> A.6667
> B.5000
> C.8334
> D.3333
> ```

| Info.        | Num                                                          |
| ------------ | ------------------------------------------------------------ |
| AC rate      | $79.5\%$ |
| Ans.         | D                                                           |
| Reason       | $10\,000-\lfloor \frac{10\,000}{2} \rfloor-\lfloor \frac{10\,000}{3} \rfloor+\lfloor \frac{10\,000}{6} \rfloor=3\,333$ |
|Attention|这题一开始出了一点小错误，选项打成了3334，后来做了修改，会有较少的同学收到影响，再次表示深深的歉意。|

> 二进制$(1110110101101111)_2$转化为8进制的结果为？
>
> ```
> A.(732671)_8
> B.(166557)_8
> C.(60703)_8
> D.(ED6F)_{16}
> ```

| Info.        | Num                  |
| ------------ | -------------------- |
| AC rate      | $86.4\%$ |
| Ans.         | B                    |
| Reason       | 从低到高三为一变即可 |

> 表达式`a*b+c*(d+e)`的前缀形式是
>
> ```
> A.+*ab*c+de
> B.*+ab*c+de
> C.a*b+c*(d+e)
> D.++*ab*cde
> ```

| Info.        | Num                            |
| ------------ | ------------------------------ |
| AC rate      | $56.8\%$ |
| Ans.         | A                              |
| Reason       | 根据前缀表达式的定义去计算即可 |

> 有如下说明语句`char str1[80]="abce",str2[80]="1234",str3[80]="ABCD";执行strcat(str1,strcat(str3,str2));`后，下面说法正确的是？
>
> ```
> A.str1="abceABCD1234" str2="1234" str3="ABCD1234"
> B.str1="abce" str2="1234ABCD" str3="1234ABCDabce"
> C.str1="abceABCD" str2="1234" str3="ABCD1234"
> D.str1=abce" str2="1234abceABCD" str3="ABCD"
> ```

| Info.   | Num                                                          |
| ------- | ------------------------------------------------------------ |
| AC rate | $93.2\%$                                                     |
| Ans.    | A                                                            |
| Reason  | `strcat`函数从内到外执行，相当于str2不变，str3+=str2，str1+=str3 |

> 一棵深度为 $K(K \geq 0)$ 的完全二叉树最少有（）个结点（规定只有根的树的深度为0）：
>
> ```
> A.2^K-1
> B.2^K
> C.2^{K-1}
> D.2* K – 1
> ```

| Info.   | Num                                                          |
| ------- | ------------------------------------------------------------ |
| AC rate | $40.9\%$                                                     |
| Ans.    | B                                                            |
| Reason  | 完全二叉树说明前$K-1$层都是满的，最后一层至少一个。为$1 + 2 + \cdots + 2^{K - 1} + 1= 2^K$ |

> 现在有一个含有N个数的无序数组，如果想快速找到第K(K<=N)大的数，最低的时间复杂度是（）
>
> ```
> A.O(N)
> B.O(K)
> C.O(N log N)
> D.O(K log N)
> ```

| Info.   | Num                             |
| ------- | ------------------------------- |
| AC rate | $20.5\%$                        |
| Ans.    | A                               |
| Reason  | `nth_element`的时间复杂度是O(n) |

> 12 个顶点的连通图的最大生成树，其边数为（）：
>
> ```
> A.132
> B.11
> C.66
> D.110
> ```

| Info.   | Num                    |
| ------- | ---------------------- |
| AC rate | $40.9\%$               |
| Ans.    | B                      |
| Reason  | 树的边数永远是点数减一 |

> 假设我们用d=(a1,a2,a3,a4,a5),表示无向图G的5个顶点的度数，下面给出的哪组d值合理
>
> ```
> A.(3,3,3,2,2)
> B.(5,4,4,3,1)
> C.(5,4,3,2,1)
> D.(4,2,2,1,1)
> ```

| Info.   | Num                                                          |
| ------- | ------------------------------------------------------------ |
| AC rate | $56.8\%$                                                     |
| Ans.    | D                                                            |
| Reason  | 排除法，度数最大不会是5，同时我们没办法画出三个点度数都为3的图 |

> 已知数组A中，每个元素A（I，J）在存贮时要占3个字节，设I从1变化到8，J从1变化到10，分配内存时是从地址SA开始连续按行存贮分配的。试问：A（5，8）的起始地址为
>
> ```
> A.SA+144
> B.SA+141
> C.SA+222
> D.SA+225
> ```

| Info.   | Num                                |
| ------- | ---------------------------------- |
| AC rate | $56.8\%$                           |
| Ans.    | B                                  |
| Reason  | $(4 \times 10 + 7) \times 3 = 141$ |

> 一个三叉树（即每个节点最多有三个孩子）中，有k个孩子的节点数目表示为F(k),则下列关系一定成立的是
>
> ```
> A.F(0) > 2 * F(3) + F(2)
> B.F(0) = 2 * F(3) + F(2) – 1
> C.F(0) > 3 * F(3) + 2 * F(2) - 1
> D.F(0) <= 3 * F(3) + 2 * F(2)
> ```

| Info.   | Num                                                          |
| ------- | ------------------------------------------------------------ |
| AC rate | $29.5\%$                                                     |
| Ans.    | A                                                            |
| Reason  | $F(0) + F(1) + F(2) + F(3) = 1 + F(1) + 2 \times F(2) + 3 \times F(3)$<br />化简得$F(0)=1+F(2)+ 2 \times F(3)$ |

> 设a、b、c是三个bool型变量，若表达式$\mathrm{a} \wedge \neg \mathrm{b} \wedge \mathrm{c}$为true，则下列表达式一定为true的是
>
> ```
> A.(a∧(b∨c))∨(¬a)
> B.a∧b∧c
> C.(b∧a)∨(a∧c)∨(c∧b)
> D.(b∨a)∧(¬(a∨b))
> ```

| Info.   | Num                                                          |
| ------- | ------------------------------------------------------------ |
| AC rate | $74.4\%$                                                     |
| Ans.    | AC                                                           |
| Reason  | 由题，a，c为真，b为假。A选项左边（b∨c）为真，a为真，故左边括号为真，c也为真，故A正确。B显然，b为假，错误。C第二个括号（a∧c）为真，故正确。D右边括号为假，故错误 |

> 下列排序中，运用了归并思想的是
>
> ```
> A.快速排序
> B.归并排序
> C.堆排序
> D.希尔排序
> ```

| Info.   | Num                                                          |
| ------- | ------------------------------------------------------------ |
| AC rate | $23.3\%$                                                     |
| Ans.    | AB                                                           |
| Reason  | 快速排序的思想为通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序。将数据一分为二体现了分治思想。归并排序则是直接对半分，将两边的数列都排好序后再进行合并，标准的分治思想。堆排序利用堆这种数据结构进行排序，与分治无关。希尔排序同插入排序，逐个比较，与分治无关。 |

> 设想这样一个数据结构，它有PUSH和POP两个操作。其中PUSH操作就是将一个元素加入到这个数据结构中，二当第K次调用POP元素时（保证这个数据结构中有元素），选择其中一个元素返回并删除。若k是奇数，选择的是元素中的最大值，若k是偶数，选择的是元素中的最小值。如果调用PUSH操作放入数据结构中的元素依次是1、2、3、4、5、6，则下列序列中可能通过适当的POP操作产生的有：
>
> ```
> A.1、2、3、4、5、6
> B.1、2、3、4、6、5
> C.6、1、5、2、4、3
> D.2、1、6、3、5、4
> ```

| Info.   | Num                                                          |
| ------- | ------------------------------------------------------------ |
| AC rate | $53.5\%$                                                     |
| Ans.    | ABCD                                                         |
| Reason  | A：push 1 pop, push 2 pop …… push 6 pop<br />B：push 1 pop, push 2 pop …… push 5 push 6, pop pop<br />C: push 1 push 2 …… push 6 pop pop……<br />D: push 1 push 2 pop pop push 3 push 4 push 5 push 6 pop pop …… |

## 填空题

> 在一个箱子里有6根绳子，其中红色、蓝色、黄色各两根，现在从中抽取2根，颜色不同的概率是()。

| Info.   | Num                      |
| ------- | ------------------------ |
| AC rate | $86.0\%$                 |
| Ans.    | 4/5 0.8 80%              |
| Reason  | $1-\frac{3}{C(6,2)}=0.8$ |

> 懋懋要画一个电路图。这是一个很简单的电路图，所有的元件都是串联关系，从整体来看就是一个环状的结构。画电路图有很多要求，懋懋为了画得好看就又添加了一些额外的要求。所有要求归结起来有以下几点：
>
> - 这个环状电路上有𝑛个双端电路元件（即每个电路元件有两个连接导线的接头），其中只有一个直流电源；为了本题方便，其他n-1个元件都是一模一样的电阻。
>
> - 电流在电路图中每经过一个元件，就必须拐一个90°的弯；没有经过元件时不允许拐弯。参考下图。
>
> <img src="https://uploadfiles.nowcoder.com/images/20191004/320925_1570187828694_5EC4AF06A961DC0E89300A4D4819200C" alt="img" />
>
> - 从电路图整体上观察，电流沿顺时针方向流动，且电路不能自交。参考下图。
>
> <img src="https://uploadfiles.nowcoder.com/images/20191004/320925_1570187834709_82F47DDA3AF4782A624A09FF2BCC2F4B" alt="img" />
>
> - 如果一个符合题意的电路图，可以通过整体旋转一定的角度，再适当调整图中导线的长度，得到另外一个符合题意的电路图，则这两个电路图是相同的。参考下图。
>
> <img src="https://uploadfiles.nowcoder.com/images/20191004/320925_1570187840750_335DE3095C5CB95896851986FC7F833B" alt="img" />
>
> 当总共有12个电路元件时（包括电源），符合条件的电路图共有()种

| Info.   | Num                                                          |
| ------- | ------------------------------------------------------------ |
| AC rate | $9.8\%$                                                      |
| Ans.    | 495                                                          |
| Reason  | 不难发现，想象成从正极出发，回到负极，符合条件的电路图中，右转弯次数比左转弯多4次，所以答案为$C(12,4)=495$ |

## 编程题

### A. 宇宙跃迁

Average Score：8.4/10

签到题，按照图示画出对应的图形，分成上下两部分，先输出前面的空格（线性关系），再输出对应的星号（线性关系）

### B. 懋懋的黄金周

Average Score：7.0/10

显然这是一个排序之后从小到大做加法的题。
40%：使用时间复杂度为$O(n^2)$的排序方法（冒泡，选择，等）

另外的40%：可以使用桶排序

100%：使用时间复杂度为$O(n \log n)$的排序方法（快排，归并，sort）

### C. 最长括号子序列

Average Score：15.5/20

30%：dfs 暴力

50%：$O(n^2)$ 动态规划，$dp[i][j]$表示前$i$个符号，当前取的子序列合法的前缀和是$j$，然后去转移一下就行

90%：使用两个`set`等进行维护，复杂度$O(n \log n)$

100%：直接贪心，$O(n)$ 扫一遍序列，同时维护当前有多少个多余的左括号，当扫到右括号的时候，贪心地把多余的左括号给它，并加入到答案中

### D. 麻将推推

Average Score: 10.0/20

本题要干三件事，分别是：

1. 计算乘积时递推计算，即计算$[i,j]$到$[i,j+1]$时，不再重新计算，而是利用之前的结果乘$a[j]$得到$[i,j+1]$的积；

2. 由于给出字符串长度最长1e5，所以在当前$[l,r]$乘积超过1e5时，$[l,r+k](k>0)$一定不是满足条件的区间，也就不用继续枚举了；

3. 由2，我们发现，如果该串只有2~9，那么我们只需要枚举最长不超过约$\log 1e5$个单位长度的区间即可，那么对于1怎么处理呢？我们可以预处理出一个数组，该数组$suf[i]$含义为：如果$a[i]$非1，该位为0；如果$a[i]$为1，该位指向下一个非1数字。这样，我们对于一个确定的区间左端点l，只需枚举不超过$\log 1e5$个非1数字，就可以找出所有以l为区间左端点的符合条件的区间。

100%：如上，这三个东西都写到了，复杂度$O(n \log n)$；

65~70%：没有处理出上述的$suf$数组，直接两重循环，$O(n^2)$；

50%：在70%的基础上，没有在当前乘积超过1e5时跳出当前循环，$O(n^2)$；
20~30%：枚举每个区间分别求积，即写了三重循环，若有判断超过1e5时跳出，通过用例会比没有跳出的高5~10%，$O(n^3)$

Last modification：October 7th, 2019 at 11:17 pm

If you think my article is useful to you, please feel free to appreciate

Comment here is closed

北京理工大学ACM CLUB2019级新生有基础组能力测试题解

xzm2019 • 2019 年 10 月 07 日