错题本
8月15日
一.单项选择题
1.以下不属于面向对象程序设计语言的是( ).
A. C++
B. Python
C. Jave
D. C
解析: 不知道的知识,需记.
面对过程:C, Pascal
面对对象:C++，C#, Java,Python,go,script,swift
2.以比较作为基本运算,在N个数中找出最大数,最坏情况所需要的最少的比较次数为( ).
A. N^2
B. N
C. N-1
D. N+1
解析:
没看到所需要的最少的比较次数,只看到最坏情况了
为什么是N-1,见下图
9 1 2 3 4 5 ......... 7 8
1次 1 9 2 3 4 5 ......... 7 8
2次 1 2 9 3 4 5 ......... 7 8
3次 1 2 3 9 4 5 ......... 7 8
4次 1 2 3 4 9 5 ......... 7 8
5次 1 2 3 4 5 9......... 7 8
.....
i 次 移到第i个后面 是第i+1个数
n-1次 移到第n-1个后面 是第n-1+1个数即第n个数
3, 对于有n个顶点,m条边的无向连通图(m>n),需要删掉( )条边才能使其成为一棵树.
A.n-1
B.m-n
C.m-n-1
D.m-n+1
解析: 误认为 m-(m-n-1)=n-1了
一棵n个结点的树有n-1条边
m-(m-n+1)=m-m+n-1=n-1
m-(m-n-1)=m-m+n+1=n+1
太粗心了
4,如果一棵二叉树只有根结点,那么这棵二叉树高度为1.请问高度为5的完全二叉树有( )种不同的形态?
A. 16
B. 15
C. 17
D. 32
不知道的知识点
完全二叉树:如果一棵二叉树最多只有最下面两层结点度数可以小于2
满二叉树:除了最后一层其他结点都有两条子树
可以删1-15个点,(0个也可以, 满二叉树也是完全二叉树)
15+1=16
5. 6个人,两个人组成一队,总共组成三队,不区分队伍编号.不同的组队情况有( )种.
A. 10
B. 15
C. 30
D. 20
排列组合题,(￣_,￣ )公式忘了...
我们选出前两队,第三队就固定了
我们只需要在6个人里选4个,再在4个人里选2个,就行了,但是由于不用管队伍的编号,还需要除以3的阶乘
公式
$$C_N^M=N!\div M!\times (N-M)! \\ \\ C_6^4\times C_4^2\div 3! \\ =6!\div (4!\times (6-4)!)\times 4!\div (2!\times (4-2)!)\div 3\times 2\times 1 \\ =(720\div (24\times 2)\times 24\div 2\times 2)\div 6 \\ =720\div 48\times 24\div 4\div 6\\=15$$6.在数据压缩编码中的哈夫曼编码方法,在本质上是一种( )的策略
A.枚举
B.贪心
C.递归
D.动态规划
解析: 不知道的知识,需记.
7.考虑如下递归算法则调用solve(7)得到的返回结果为( )。
solve(n)
if n<=1 return 1
else if(n>=5) return n*solve(n-2)
else return n*solve(n-1)
A. 105
B. 840
C. 210
D. 420
解析:多乘了一个4
solve(7)
=7 solve(5)
=7 5 solve(3)
=7 5 3 solve(2)
=7 5 3 2 1
=210
太粗心了
8.有四个人要从A点坐一条船过河到B点,船一开始A点.该船一次最多可坐两个人.已知这四个人中每个人独自坐船的过河时间分别为 1,2,4,8, 且两个人坐船的过河时间我两人独自过河时间的较大者.则最短( )时间可以让四个人都过河到B点(包括从B点把船开回A点的时间).
A. 14
B. 15
C. 16
D. 17
解析: 不会
核心思想 最大的要和次大的在一条船上.
但开始不能运8和4(因为这样回去需要4),要运1,2 1回来 4,8过去 2回来 1,2 过去
图示:
[ ]
[1,2,4,8 ]
. . .
[ 1 2 ]2
[4,8 ]
. . .
[ 2 ]2]
[1,4,8 ]1
. . .
[ 2,4,8 ]2 8
[1 ] 1
. . .
[4,8 ] 2 8
[1,2 ]1 2
. . .
[ 1 2 4 8]2 2 8
[ ]1 2
1+2+2+2+8=15
8月17日
一.单项选择题
1.假设字母表{a,b,c,d,e} 在字符串出现的频率分别为10%,15%,30%,16%,29%.若使用哈夫曼编码方式对字母进行不定长的二进制编码,字母d的编码长度为( )位.
A. 1
B. 2
C. 2或3
D. 3
解析: 画一个树就好了
100
0/ \1
41 59
0/ \1 0/ \1
25 16 29 30
0/ \1
10 15
可知是2 (粗心,写错了树)
2.以下对数据结构的表述不恰当的一项为
A.图的深度优先遍历算法常使用的数据结构为栈.
B.栈的访问原则为后进先出,队列的访问原则为先进先出.
C.队列常常被用于广度优先算法.
D. 栈与队列存在本质不同,无法用栈实现队列
解析:用两个栈即可实现. (小知识)
课后小习题
1 打表如下
| n\m | 1 | 2 | 3 |
|---|---|---|---|
| 1 | 0 | 1 | |
| 2 | 3 | 4 | |
| 3 | 7 | 12 | |
| 4 | 15 | 32 | |
| 5 | 31 | 80 | |
| 6 | 63 | 192 | |
| 7 | 127 | 448 | |
| 8 | 255 | 1024 | |
规律
8月19日
一.单项选择题
1. 假设有一组字符{g,h,i,j,k,l}, 它们对应的频率分别为 8%,14%,17%,20%,23%,18%. 请问以下哪个选项是字符 g,h,i,j,k,l 分别对应一组哈夫曼编码? ( )
A . g: 1100, h: 1101, i: 111, l: 10, k: 00, j: 01
B . g: 0000, h: 001, i: 010, l: 001, k: 10, j: 11
C . g: 111, h: 110, i: 101, l: 100, k: 01, j: 00
D . g: 110, h: 111, i: 101, l: 100, k: 0, j: 01
解析: (小知识) 哈夫曼编码不唯一, 长度唯一
2. 将3个相同的红球和3个相同的黑球装入三个不同的袋中,每袋均装2个球,则不同的装法总数为( ).
A. 7
B. 8
C. 9
D. 10
解析:
枚举即可(没看到不同的袋子)
红红 红黑 黑黑 1
红红 黑黑 红黑 2
红黑 红红 黑黑 3
红黑 黑黑 红红 4
黑黑 红黑 红红 5
黑黑 红黑 红红 6
红黑 红黑 红黑 7
3. 奇偶校验编码是常见的校验编码方式. 对于二进制编码, 奇偶校验编码在编码的最后增加一位校验位 G, 并将原编码与校验位作为整体发送. 校验位分为奇校验位和偶校验位, 奇校验位保证 $A_{n}xorA_{n-1}xorA_{n-2}xor......xorA_{2}xorA_{1}xorG=1$, 偶校验位保证 $A_{n}xorA_{n-1}xorA_{n-2}xor......xorA_{2}xorA_{1}xorG=0$. 下列编码与校验位对应正确的是( ).
A. 编码 11100111 奇校验位0
B. 编码 01100010 偶校验位0
C .编码 00010010 奇校验位1
D. 编码 11100010 偶校验位1
解析: 全部异或即可(看错了(￣_,￣ ))
1xor1xor1xor0xor0xor1xor1xor1 xor0=0 0!=1
0xor1xor1xor0xor0xor0xor1xor0 xor0=1 1!=0
0xor0xor0xor1xor0xor0xor1xor0 xor1=1 1==1
1xor1xor1xor0xor0xor0xor1xor0 xor1=0 1!=0
8月20日
一.单项选择题
1.[流程结构] 是编程中用于控制程序执行流程的一种方式. 它包括顺序结构, 分支机构和循环结构. 在一些诗歌作品中, 也有对[流程结构]的体现. 下列诗歌片段中体现循环结构的是( ).
A. 如果还能找到你, 就让风儿告诉你. __《Artificial Emotions》
B. 只要我还能够行走， 只要我还能够张望， 只要我还能够呼吸， 就一直走向前方。——《Πесня отревожной молодости》
C.昔闻洞庭水，今上岳阳楼。 ——《登岳阳楼》
D. 啊如果我在，战斗中牺牲，啊朋友再见吧，再见吧，再见吧！如果我在，战斗中牺牲，你一定把我来埋葬。——《Bella Ciao》
解析：其他都是如果（if) 只有B是“只要…..一直”（while),所以选B。
2. 观察下列代码
int a[]={5,4,3,2,1};
auto p = a+3;
auto q = &p;
(*q)++;
auto k=*p;
其中， 的类型以及 的值分别为（ ）。
A. int 类型，值为 1
B. int 类型，值为 3
C. int 指针类型， 值为 数组的下标为 3 的元素的地址
D.int 指针类型，值为 数组的下标为 4 的元素的地址
解析：p是指针类型,指向a[0+3]的地址，q是指针类型指向a[0+3]地址的地址，+1后p指向a[0+3+1]的地址,也就是a[4]的地址，把赋值为a[4]的值就是1
3. 以下程序片段的时间复杂度为（ )
int cnt=0;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j+=i)
{
for(int k=1;k<=n;k+=j)
{
++cnt;
}
}
}
提示：$\frac{n}{1^1}+\frac{n}{2^1}+\frac{n}{3^1}+...+\frac{n}{n^1} ≈ C1\times log_2n$
$\frac{n}{1^2}+\frac{n}{2^2}+\frac{n}{3^2}+...+\frac{n}{n^2} ≈ C2$
其中，均为常数。
A.
B.
C.
D.
解析：提示是为了误导我们
只要考虑最坏情况就行了
当i=1时， 最坏为
**4.依次抛出四个六面骰子，按照抛出顺序将骰子上的数值记为 . 则 <; >; < 同时成立的概率 **
A. 95/648
B.4/27
C.5/27
D.1/6
解析：直接枚举
当a=1时 有
$$b=2 \ \ 5\\ b=3 \ \ 5 \ 4\\ b=4 \ \ 5 \ 4 \ 3\\ b=5 \ \ 5 \ 4 \ 3 \ 2\\ b=6 \ \ 5 \ 4 \ 3 \ 2 \ 1\\$$当a=2时 有
$$b=3 \ \ 5 \ 4\\ b=4 \ \ 5 \ 4 \ 3\\ b=5 \ \ 5 \ 4 \ 3 \ 2\\ b=6 \ \ 5 \ 4 \ 3 \ 2 \ 1\\$$可以发现有规律
$$5\\ 5 \ 4\\ 5 \ 4 \ 3\\ 5 \ 4 \ 3 \ 2\\ 5 \ 4 \ 3 \ 2 \ 1\\ 5 \ 4\\ 5 \ 4 \ 3\\ 5 \ 4 \ 3 \ 2\\ 5 \ 4 \ 3 \ 2 \ 1\\ 5 \ 4 \ 3\\ 5 \ 4 \ 3 \ 2\\ 5 \ 4 \ 3 \ 2 \ 1\\ 5 \ 4 \ 3 \ 2\\ 5 \ 4 \ 3 \ 2 \ 1\\ 5 \ 4 \ 3 \ 2 \ 1\\$$加起来是190 190/1296
约分一下 95/648
5. 已知某种可用来维护序列的数据结构,支持向某个位置后面插入元素，查询某个元素的排名，遍历整个序列，那么用上述三种操作实现插入排序的时间复杂度最坏为( )
A.
B
C.
D.
解析：上面的都是迷惑我们的
就是插入排序最坏时间复杂度
6.今天是CCF(中国计算机学会) 第( ）次举办 CSP-J/S (计算机非专业级别的软件能力认证)？
A. 27
B. 28
C. 5
D. 4
解析：小知识
CSP-J/S 是2019年由NOIP更名而来
所以是 2023-2019+1=5
8月21日
一.单项选择题
1.阅读下列代码， 请问修改data 的 value 成员以存3. 14， 正确的方式是( ).
union Data{
int num;
float value;
char symbol;
};
union Data data;
A.data.value = 3.14
B.value.data = 3.14
C. data->value =3.14
D.value->data = 3.14
解析：->是指针变量，可排除c.d
.value是data里的，不是data是value里的 (本作者被wy带偏)(╬▔皿▔)╯
2. 假设有一个链表的结点定义如下：
struct Node
{
int data;
Node*next;
}
现在有一个指向链表头部的指针：Node*next。如果想要在链表中插入一个新节点，成员data 的值为42，并使新节点成为链表的第一个节点，下面哪个操作是正确的？( )
A. Node*newNode=new Node; newNode->data=42; newNode->next=head; head=newNode;
B. Node*newNode=new Node; head->data=42; newNode->next=head; head=newNode;
C. Node*newNode=new Node; newode->data=42; head->next=newNode;
D. Node*newNode=new Node; newNode->data=2; newNode->next=head;
解析：
C,D一个newNode写成nowode，一个42写成2 排除
B. head的值是42??? 排除
所以是A
（作者误以为head->data是 head的右边是data了）
3. 以下关于高精度运算的说法错误的是( )
A.高精度计算主要是用来处理大整数或需要保留多位小数的运算
B.大整数除以小整数的处理方式的步骤可以是，将被除数和除数对齐，从左到右逐位尝试将除数乘以某个数，通过减法得到新的被除数，并累加商。
C. 高精度乘法的运行时间只与参加运算的两个整数中长度较长者的位数有关
D.高精度加法运算的关键在于逐位相加并处理进位。
解析：
高精度乘法是高精乘高精，时间是
不只跟较长的位数有关
