计算机技术相关知识

有关计算机技术的相关知识。

资料

HTML

1
2
https://www.w3school.com.cn/html/index.asp
https://developer.mozilla.org/zh-CN/docs/Learn/HTML/Introduction_to_HTML/Getting_started

Java

1
https://github.com/akullpp/awesome-java

Arduino

1
https://www.w3cschool.cn/arduino/arduino_for_loop.html

软件源代码集合

1
http://www.columbia.edu/kermit/archive.html

学习资料

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
https://cn.dolphin-emu.org/
http://ebadillo_computacion.tripod.com/
https://www.examcoo.com/index/ku
https://github.com/greyireland/algorithm-pattern/
https://oi-wiki.org/
https://github.com/neolee/wop-ecnu-pub/blob/master/HOWTO.md
https://github.com/cucygh/fe-material
https://github.com/JacksonTian/fks
https://github.com/oldratlee/translations
https://github.com/ahangchen/How-to-Be-A-Programmer-CN
https://github.com/euphrat1ca/security_w1k1
https://github.com/prakhar1989/awesome-courses
https://github.com/No-Github/1earn
https://www.mooc.cn/
https://www.icourse163.org/
https://www.imooc.com/
https://www.waitsun.com/
https://refactoringguru.cn/
https://www.felix021.com/blog/
http://www.dxzy163.com/
https://hoochanlon.github.io/fq-book/#/abc/3vm
https://www.cnblogs.com/hustskyking/p/hosts-modify.html
https://gitee.com/wanzheng_96/Modules-Learn/tree/master

iOS逆向

1
http://www.iosre.com/

DOS文件配置

1
https://www.cubic.org/docs/configuring.htm

各校课程共享计划

北京大学

1
2
3
4
https://github.com/martinwu42/project-hover/tree/legacy/project-hover
https://github.com/tongtzeho/PKUCourse
https://github.com/lib-pku/libpku
https://lib-pku.github.io/

清华大学

1
2
https://github.com/PKUanonym/REKCARC-TSC-UHT
https://rekcarc-tsc-uht.readthedocs.io/en/latest/

浙江大学

1
2
3
https://github.com/QSCTech/zju-icicles
https://qsctech.github.io/zju-icicles/
https://github.com/LeadroyaL/ZJU_ISEE_Project

东南大学

1
https://github.com/zjdx1998/seucourseshare

中国科学技术大学

1
2
3
https://github.com/ustcwpz/USTC-CS-Courses-Resource
https://github.com/USTC-Resource/USTC-Course
https://ustc-resource.github.io/USTC-Course/

上海交通大学

1
https://github.com/c-hj/SJTU-Courses

中山大学

1
https://github.com/sysuexam/SYSU-Exam

南京大学

1
https://github.com/idealclover/NJU-Review-Materials

郑州大学

1
https://github.com/CooperNiu/ZZU-Courses-Resource

华南师范大学

1
https://www.yuque.com/0xffff.one/cs-learning

广东工业大学

1
2
https://github.com/brenner8023/gdut-course
https://brenner8023.github.io/gdut-course/

北京林业大学

1
https://github.com/bljx/BFU-leaf

山东科技大学

1
https://github.com/deepwzh/sdust-examination-materials

数据结构

算法分析

基础知识

算法分析的主要任务是分析时间复杂度和空间复杂度。

算法可以没有输入,但应该要有输出。

使用的存储结构会影响算法的复杂度。

常见模型

最大子序列问题。

习题

判断题

1
The Fibonacci number sequence {F​N} is defined as: F0=0, F​1​=1, F​N​​=F​N−1+F​N−2, N=2, 3, .... The time complexity of the function which calculates FN recursively is Θ(N!). (F)

时间复杂度:(3/2)^N,空间复杂度:求FN,需要从F0到FN的值,需要O(N)。

选择题

1
2
3
4
5
6
7
8
9
10
The recurrent equations for the time complexities of programs P1 and P2 are:

P1: T(1)=1,T(N)=T(N/3)+1
P2: T(1)=1,T(N)=3T(N/3)+1

Then the correct conclusion about their time complexities is: (B)
A.they are both O(logN)
B.O(logN) for P1, O(N) for P2
C.they are both O(N)
D.O(logN) for P1, O(NlogN) for P2

P1的加号左边经过logN次递归等式计算恒等于1,而右边每次递归等式都加1,经过logN次计算最后为logN,两边取大是logN;
P2加号的左边经过logN次递归等式计算是N,右边每次递归等式都加1,经过logN次计算最后为logN,两边取大总体为N。

1
2
3
4
5
6
To merge two singly linked ascending lists, both with N nodes, into one singly linked ascending list, the minimum possible number of comparisons is: (B)

A.1
B.N
C.2N
D.NlogN

至少遍历完一个链表。

表/栈/队列

基本知识

若代表队列的数组大小为Size,那么只能存放Size-1个元素。

常见模型

后缀表达式(遇到当前运算符优先级低于或等于栈顶时,弹出栈顶运算符;对于括号,在左括号入栈后,未遇到右括号前都不会出栈)。

基础知识

总是可以用一维数组表示一棵树。

在任何二叉树中,空指针的数目永远比非空指针多。

普通树转二叉树

左儿子,右兄弟(每个点的左儿子是它的第一个儿子,右儿子是它从左往右数的第一个兄弟)。

也可以在所有兄弟结点之间加一连线,对每个结点除保留与其第一个儿子的连线外,去掉该结点与其它孩子的连线。

普通树的后序遍历等于该二叉树的中序遍历。

线索二叉树

对于左/右孩子为空的节点来说,若左孩子为空,将其指向中序遍历的前驱;若右孩子为空,将其指向中序遍历的后继。

不可有松散的线索,因此必须要有头节点head。中序遍历的第一个节点的左孩子指向头节点head,最后一个节点的右节点指向NULL。

二叉查找树

基本知识

左孩子中的所有数比它自身小,右孩子中的所有数比它自身大。

同一级的所有节点,从左到右按升序排列。

中序遍历可以获得一个升序序列。

若二叉查找树为完全二叉树,则最小值必定在叶节点(因为是完全二叉树,必然有最左边),中间值必定在根节点或左子树,但最大值不一定都在叶节点(可能没有最右边)。

假设4,5,6这三个数字都在二叉查找树中,且4和6在同一级,那么5不一定是它们的父亲,只需4和6不在一个子树就可以。

1
2
3
4
5
   5
/ \
3 7
/ \ / \
2 4 6 8

删除节点时,若为树叶可直接删除。若有一个孩子则让父节点绕过要删除的节点,让其孩子指向要删除节点的子节点。若有两个孩子,取右子树中的最小数据以取代要删除的节点,然后再删除右子树中该最小数据,也可以是左子树中的最大数据。

判定树

二叉查找判定树描述了查找一个数的过程。以{1,2,3,4,5,6,7,8,9,10}为例,每次折半比较,故根节点为5。若小于5,则落入左孩子,左孩子的范围为{1,2,3,4},否则落入右孩子,范围为{6,7,8,9,10}。若无法整除则取整。

1
2
3
4
5
6
7
8
9
10
11
12
13
         5
4/ \6
/ \
/ \
/ \
/ \
2 8
1/ \3 7/ \9
/ \ / \
1 3 6 9
\4 \7 \10
\ \ \
4 7 10

习题

判断题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
There exists a binary tree with 2016 nodes in total, and with 16 nodes having only one child. (F)

全满二叉树,设高度为h,则节点总数为2^h-1,最后一层的节点数为2^(h-1)
2^h-1>=2016,h的最小值为11,此时节点总数为2047,2047-2016=31,需要移除31个节点
在移除节点时,会移除该节点连带着的树,所以移除任意一个节点所带来的节点的减少=一棵满二叉树的节点数=2^m-1(m等于移除的节点与最底层节点的层数之差+1),因此可以是1、3、7、15、31、...,每移除一个子树可以带来一个只有一个孩子的节点
现在需要移除31个节点,有16个只有一个孩子的节点,所以移除16棵子树
1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1=16
1+1+1+1+1+1+1+1+1+3+3+3+3+3+3+3=30
无法到达31(因为把1换成3/7等等,增加的都是偶数,永远无法到达奇数)

The number of degree 3 nodes in a ternary tree (三叉树) is only related to the number of degree 2 nodes and that of leaf nodes, i.e it has nothing to do with the number of degree 1 nodes. (T)

对于树:度为孩子数目,对于图:度为入度+出度
设0/1/2/3度节点数量为n0(即叶节点)、n1、n2、n3,有
节点总数:n=n0+n1+n2+n3=n1+2n2+3n3+1(1为根节点)
可知n0=n2+2n3+1,即n3=(n0-n2-1)/2,与n1无关


选择题

1
Among the following binary trees, which one can possibly be the decision tree (the external nodes are excluded) for binary search? (A)

A.
B.
C.
D.

1
2
3
4
5
6
7
8
9
In a complete binary tree with 1238 nodes, there must be ____ leaf nodes. (C)

A.214
B.215
C.619
D.620

对于h层的完全二叉树,节点有2^h-1个,2^10-1=1023<1238,2^11-1=2047>1238,从第十层开始增加节点,需要增加1238-1023=215个
原本叶节点有2^(h-1)=512个,每连接两个节点上去,叶节点数+1,215/2=107,最后一个节点连接上去后叶节点数量不变,所以为512+107=619

优先队列(堆)

基础知识

对于以数列表示的完全二叉树,节点n的左孩子为2n,右孩子为2n+1。

堆是特殊的完全二叉树,最小堆:父亲<孩子,最大堆:父亲>孩子。

在最小堆中,从根节点到任意叶节点的任意一条路径都按照升序排列。

若一个d-heap以数组形式存储,则对于节点i,其父亲为⌊(i+d−2)/d⌋,第一个孩子为(i−1)d+2,最后一个孩子为id+1。

习题

选择题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
Using the linear algorithm to build a min-heap from the sequence {15, 26, 32, 8, 7, 20, 12, 13, 5, 19}, and then insert 6. Which one of the following statements is FALSE? (C)

A.The root is 5
B.The path from the root to 26 is {5, 6, 8, 26}
C.32 is the left child of 12
D.7 is the parent of 19 and 15

5
/ \
/ \
/ \
6 12
/ \ / \
/ \ 32 20
8 7
/ \ / \
26 13 19 15

Suppose that the level-order traversal sequence of a min-heap is { 2, 17, 5, 46, 22, 8, 10 }. Use the linear algorithm to adjust this min-heap into a max-heap, and then call DeleteMax. The postorder traversal sequence of the resulting tree is: ()

A.22, 17, 5, 2, 10, 8
B.5, 2, 17, 8, 10, 22
C.2, 8, 10, 5, 17, 22
D.2, 8, 17, 5, 10, 22

并查集

基础知识

在father[]数组中,正数表示该节点对应的父亲,负数代表该节点为根节点,且该树的大小为这个数的绝对值。若Union按照大小执行,则任何节点的深度都不会超过logN,即最高为log2(N)+1。

图论

基础知识

在有向图中,入度的和必须等于出度的和。

强连通和弱联通针对有向图而言,强连通从一个顶点可以到达其余任意顶点,弱联通将方向去掉后从一个顶点可以到达其余任意顶点。

(无向)联通和(有向)弱联通图中,若有V个节点,则至少有V-1条边。

最小生成树

最小生成树只有连通图才有,用于生成最小的连通图(再少一条边就不联通,多一条边就成圈)。

Prim算法:从已知节点出发找最小边
Kruskal算法:选择最小边直至图联通

欧拉回路

欧拉回路(Euler circuit)需要回到原点,不可有奇数度顶点;欧拉环游(Euler tour)可以不回到原点,允许0或2个奇数度顶点。

习题

判断题

1
2
3
4
5
In a weighted undirected graph, if the length of the shortest path from b to a is 12, and there exists an edge of weight 2 between c and b, then the length of the shortest path from c to a must be no less than 10. (T)

不小于10,不是不大于10


选择题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
If graph G is NOT connected and has 35 edges, then it must have at least ____ vertices. (D)

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

对于n个节点,若两两均有边连接,则边的数量为Cn,2,由于要未联通,因此需要多加一个独立的节点,而C9,2=36>35,9+1=10


A graph with 90 vertices and 20 edges must have at least __ connected component(s). (B)

A.69
B.70
C.84
D.85

connected component是指不联通的区域总数,对于20条边,每加一条边,可以减少一个连通区域(连接非该区域内的节点)或不减少连通区域(连接该区域内的节点),故最多可以减少20个连通节点,90-20=70


Given an undirected graph G with 16 edges, where 3 vertices are of degree 4, 4 vertices are of degree 3, and all the other vertices are of degrees less than 3. Then G must have at least __ vertices. (B)

A.10
B.11
C.13
D.15

其余节点需要为2个度,这样才能让节点数最少
先从一条链开始,注意只在外面加节点,不考虑链间节点连接,因为链长度不确定,可以直接缩短链,如:
1---2---1
首尾相连变为:
2---2---2
| |
---------
等同于:
1---1
在外面加一个节点:
2
/ \
2---2
从2个度开始,慢慢加边(数字代表该节点的度),头尾不相连的话必会出现度为1的情况:
1---2---2---2---2...---2---2---1
在外面加一个节点,让头尾的度变为2,同时因为需要度为3的节点,因此分别再连接一个节点:
2 2
/ \ / \
2---3---2---2---2...---2---3---2
假设继续连:
3 3
/ | \ / | \
/ | \ / | \
2---3---3---2---2...---3---3---2
需要有度为4的节点,但现在度为3的节点太多了,需要将上面两个节点进行连接:
4 -------------------- 4
/ | \ / | \
/ | \ / | \
2---3---3---2---2...---3---3---2
少了一个度为4的节点,且已经没办法修改(没有多余的度),因此需要多加一个节点:
4 -------- 2 -------- 4
/ | \ / | \
/ | \ / | \
2---3---3---2---2...---3---3---2
需要度为4的节点做出调整:
3 ---- 4 ----------- 3
/ | / | | \
/ | / | | \
2---3---3---3---2...---2---3---2
最后两个度为3的节点连接,完成:
------------------------
| |
4 ---- 4 ----------- 4
/ | / | | \
/ | / | | \
2---3---3---3---2...---2---3---2

DFS

基础知识

DFS先标记自己为已访问(防止循环),然后对于每一个邻接且未被访问的节点递归调用自身。

习题

选择题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
Given the adjacency matrix of a graph as shown by the figure. Then starting from V5, an impossible DFS sequence is: (C)

0 1 1 0 1 0
1 0 0 1 0 0
1 0 0 0 1 1
0 1 0 0 1 0
1 0 1 1 0 1
0 0 1 0 1 0

A.V5, V6, V3, V1, V2, V4
B.V5, V1, V2, V4, V3, V6
C.V5, V1, V3, V6, V4, V2
D.V5, V3, V1, V2, V4, V6

邻接情况:
5-1,3,4,6
1-2,3,5
对于C:5先标记自己visited,然后DFS(1),1去DFS(3),倒回来1
这个时候DFS(1)还没结束,会去DFS(2),而不会一步回到5
所以应该是:
V5, V1, V3, V2, V4, V6
--> -->
<--
-------> -->
<---------------
------------------->

排序

基础知识

插入排序:第P趟保证0-P上的元素已排序(移动第P个位置上的元素到适当位置)。链表会比数组快。

选择排序:第P趟选择从P-1位置开始到最后的数字中的最小者放到位置P-1中。链表会比数组快。

归并排序:对前半部分和后半部分分别归并排序,然后合并两个数组,时间复杂度O(NlogN)。

Shell排序:相隔k的元素得到排序,k从大变小。数组会比链表快。

堆排序:建立堆后执行DeleteMin。数组会比链表快。

快速排序:选枢纽元-分割-对另外两部分快速排序,时间复杂度最好情况O(NlogN),最坏情况O(N^2)。

基数排序,LSD/MSD:最低位/最高位优先,从最低位/最高位开始将各数字放入0-9的bucket中,完成后将数列串起来,变成一个新的数列,再从第二低位/第二高位放置bucket,循环直至结束。

习题

判断题

1
2
3
During the sorting, processing every element which is not yet at its final position is called a "run". To sort a list of integers using quick sort, it may reduce the total number of recursions by processing the small partion first in each run. (F)

递归的总数是不变的

选择题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
To sort N elements by heap sort, the extra space complexity is: (A)

A.O(1)
B.O(logN)
C.O(N)
D.O(NlogN)

用大顶堆删最大元素法,不需要额外空间。


During the sorting, processing every element which is not yet at its final position is called a "run". Which of the following cannot be the result after the second run of quicksort? ()

A.5, 2, 16, 12, 28, 60, 32, 72
B.2, 16, 5, 28, 12, 60, 32, 72
C.2, 12, 16, 5, 28, 32, 72, 60
D.5, 2, 12, 28, 16, 32, 72, 60

已经在正确位置上(左边比它小,右边比它大)的为pivot
第一趟:一分为二,一个pivot
第二趟:两边一分为二,多出来两个pivot,一共有三个pivot,但第一趟有可能有特殊情况
对A:
5 2 16 12 28 60 32 72
| |
第二趟 第一趟(只需管左边的)
对B:
2 16 5 28 12 60 32 72
| |
第二趟 第一趟(只需管左边的)
对C:
2 12 16 5 28 32 72 60
| |
第一趟 第二趟
(只需管右边的)
对D:
5 2 12 28 16 32 72 60
| |
假设第一趟为32,第二趟时32左侧有pivot为12,但右侧没有

散列

基础知识

在散列中搜索一个值的时间复杂度不确定。

若散列表大小为质数且仅为半满,则必定可以用平方探测法寻找到元素插入位置。

在分离链接法中,插入一般比删除快。

在线性探测中,插入元素所需要的探测大于成功搜索到元素所需要的探测,因为有可能找不到插入的位置。

负载密度loading density=n/(B*S),其中n为使用的identifier个数,B为bucket数,S为每个bucket可容纳的元素数。

identifier density=n/T,T为表内存放的元素总数。

双散列:冲突解决函数为F(i)=i*hash(X),用散列函数作为冲突时需要移动到的位置。

习题

选择题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
Suppose that the numbers {4371, 1323, 6173, 4199, 4344, 9679, 1989} are hashed into a table of size 10 with the hash function h(X)=X%10, and hence have indices {1, 3, 4, 9, 5, 0, 2}. What are their indices after rehashing using h(X)=X%TableSize with linear probing? (C)

A.11, 3, 13, 19, 4, 0, 9
B.1, 3, 4, 9, 5, 0, 2
C.1, 12, 9, 13, 20, 19, 11
D.1, 12, 17, 0, 13, 8, 14

再散列后的表长应该是20,但是要取大于20的第一个素数,所以表长取23


Rehashing is required when an insertion to a hash table fails. Which of the following is NOT necessary to rehashing? ()

A.change the collision resolution strategy
B.use a new function to hash all the elements into the new table
C.build another table that is bigger than the original one
D.scan down the entire original hash table for non-deleted elements

汇编

资料

1
https://www.hack520.com/

调试器

TASM

1
https://cs.nyu.edu/courses/fall99/V22.0201-002/debug.html

机器学习

可使用sklearn框架。

以训练图片识别为例,需要提取特征、训练与测试。

提取特征

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
import sklearn

# 从文件夹中读取图片集,并收集其label
# label为每个图片的名称,一般需要提前对图片重命名为对应的实体,如飞机等
def load_data_from_folder(self, dir):
# read all images into an image collection
ic = io.ImageCollection(self.folder + dir + '*.bmp',load_func=self.imread_convert)

# create one large array of image data
data = io.concatenate_images(ic)

# extract labels from image names
labels = np.array(ic.files)
for i, f in enumerate(labels):
m = re.search('_', f)
labels[i] = (f[len(dir):m.start()]).split('/')[-1]

return(data,labels)

# 训练集
(train_raw, train_labels) = img_clf.load_data_from_folder('train/')
# 测试集
(test_raw, test_labels) = img_clf.load_data_from_folder('test/')


# HOG方法
# 具体参数参见以下链接
# https://blog.csdn.net/weixin_44791964/article/details/103549605
# https://scikit-image.org/docs/dev/api/skimage.feature.html#skimage.feature.hog
#
train_feature = sklearn.feature.hog(train_raw, ...)
test_feature = sklearn.feature.hog(test_raw, ...)
# Canny方法
# image_feature = sklearn.feature.canny(train_raw, ...)
# test_feature = sklearn.feature.canny(test_raw, ...)

训练与测试

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
# KNeighbors法
classifier = KNeighborsClassifier()
# MLP法
# classifier = MLPClassifier()

# 用训练集训练模型
# 具体参数参见以下链接
# https://scikit-learn.org/stable/modules/generated/sklearn.neighbors.KNeighborsClassifier.html#sklearn.neighbors.KNeighborsClassifier.fit
#
classifier.fit(train_feature, train_labels)

# 用测试集测试模型并得出识别结果
# 具体参数参见以下链接
# https://scikit-learn.org/stable/modules/generated/sklearn.neighbors.KNeighborsClassifier.html#sklearn.neighbors.KNeighborsClassifier.predict
#
predicted_labels = classifier.predict(test_feature)

# 根据识别出的结果和实际的结果,生成混淆矩阵
# 具体参数参见以下链接
# https://scikit-learn.org/stable/modules/generated/sklearn.metrics.confusion_matrix.html
# https://machinelearningmastery.com/confusion-matrix-machine-learning/
#
confusion_matrix = metrics.confusion_matrix(test_labels, predicted_labels)

# 根据混淆矩阵计算准确性
# 具体参数参见以下链接
# https://scikit-learn.org/stable/modules/generated/sklearn.metrics.accuracy_score.html
#
accuracy = metrics.accuracy_score(test_labels, predicted_labels)

# 根据混淆矩阵计算F1得分
# 具体参数参见以下链接
# https://scikit-learn.org/stable/modules/generated/sklearn.metrics.f1_score.html
#
f1 = sklearn.metrics.f1_score(test_labels, predicted_labels)