Small knowledge, big challenge! This article is participating in the creation activity of “Essential Tips for Programmers”.

This article has participated in the “Digitalstar Project” and won a creative gift package to challenge the creative incentive money.

408 contains four subjects, including a variety of basic computer theory, even if you do not take the postgraduate entrance examination, it is good to know some basic knowledge. Welcome to me and my column 🔥

Borrow a big man’s words: for a programmer, the basic knowledge of the computer is internal power, is our professional accomplishment, only deep internal power can walk the river’s lake less.

Programmers can go far, can write high-quality code, can quickly find the bottleneck of the system, can quickly find the core functions of the system, and our professional literacy must be related. Only if you know the basics well enough, can you be truly proficient in your work and solve problems more efficiently and gracefully.

🚀 Data structure

Given a balanced binary tree of depth K, where the balance factor of each non-leaf node is 0, the total number of nodes in the tree is ___. (Beijing Jiaotong University, 2006)

A. 2^k-1 B. 2^k-1+1 C. 2^k-1 D. 2^k+1Copy the code

parsing

Answer: C

🎯 The balance factor of each non-leaf node is 0, indicating that the balanced binary tree is a full binary tree, so the total number of nodes is 2k-1.

The depth difference between the left subtree and the right subtree of a node is the balance factor of the node. There is no node whose balance factor is greater than 1 in the balanced binary tree. In a balanced binary tree, the balance factor of a node can only be 0, 1 or -1, which correspond to the equal heights of the left and right subtrees respectively. The left and right subtrees are higher and higher, respectively.

📺 Operating system

Generally, a user logs into a computer system through password authentication, so the following is the safest way to save password authentication information for an operating system: ___. (University of Chinese Academy of Sciences, 2018)

A. Save the plaintext in A file that only root can read B. Save the plaintext in A file as ciphertext generated by one-way functions C. Stored in a database system that requires authentication D. Plaintext stored in a file that only each user can readCopy the code

parsing

Answer: B

🎯 is more secure than setting permissions.

🚁 Computer network

3 bits Continuous ARQ protocol. The maximum number of sending Windows is ___. (Beijing University of Posts and Telecommunications in 2005)

A. 2 B. 3 C. 7 D. 8Copy the code

parsing

Answer: C

🎯 Continuous ARQ protocol (Automatic Repeat Request Automatic retransmission Request) includes two protocols: back N frames and selective retransmission. In 3bit continuous ARQ protocol, when the back N frame protocol is used, the maximum value of the sending window is 23-1=7. If the selected retransmission protocol is used, the maximum value of the sending window is 23-1=4. Therefore, C is selected.

🛸 Computer composition principle

A CERTAIN CPU uses a 3-level instruction pipeline, and the events of the three flow sections are 2ns, 2ns and 1ns respectively. (University of Chinese Academy of Sciences, 2016)

A. 500ns
B. 200ns
C. 204ns
D. 203ns
Copy the code

parsing

The answer:

🎯 draw a picture and so on:

After an instruction is executed, 2+2+1=5ns. After the instruction is executed through the pipeline, the next instruction can be executed every 2ns. The total time is: 5+2(100−1)=203ns5+2(100 −1)=203ns5+2(100 −1)=203ns

The exercises come from @Wangdao Weibo

The analysis is written by myself, if there are any questions or mistakes, please comment.

I am Mancuoj, welcome to pay attention to me and my computer entrance examination column (≧∇ Blue)