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

The four subjects of 408 do not talk about the most important data structure and algorithm, the other subjects such as OS process management and memory management, the TCP/IP model in the computer network, the representation of data in the computer group and so on, each of which is the content that a qualified programmer should focus on mastering.

So: although you may not go to graduate school, but follow the topic to deepen understanding of the always right

I will be updating 2 or 3 posts a day until I catch up (last time I was up to 10 posts a day). Please follow me or my column.

The exercises come from @Wangdao Weibo

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

🔑 Data structure

An undirected graph with 6 nodes should have at least ____ edges to ensure a connected graph. (University of Chinese Academy of Sciences, 2012)

A. 5
B. 6
C. 7
D. 11
Copy the code

Answer and analysis

Answer: D

🔊 connected graph means that there is a path connected between any two nodes, as long as there is a connection can be connected. An undirected graph is completely undirected if there are edges between any two vertices.

Some of you might start with A, O-O-O-O-O-O, but obviously 6 points with at least 5 edges, but they say make sure it’s A connected graph.

To ensure, the most extreme case is considered, that is, five vertices form a completely undirected graph, and then the sixth vertex is connected to the connected graph, as follows:


C 5 2 + 1 = 5 ∗ 4 2 ∗ 1 + 1 = 11 C_5^2 + 1 = \frac{5*4}{2*1} +1 = 11

If the number of edges is less than 11, when 5 vertices form a completely undirected graph, the graph is not a connected graph, so choose D.

📠 Computer network

Which of the following statements about networks providing virtual circuit services is not true ____ (Beijing University of Posts and Telecommunications 2011)

A. Each packet has A complete destination address b. A connection needs to be established c. Packets belonging to the same virtual circuit are forwarded by the same route D. B. Reliable communication is guaranteed by the networkCopy the code

Answer and analysis

Answer: A,

🔊 Virtual circuit service: Before packet sending, the sender and receiver are required to establish a logical virtual circuit to fix the physical path corresponding to the virtual circuit.

It has the following characteristics:

  • Connections must be established to ensure that groups arrive in an orderly fashion.
  • The destination address is used only in the connection establishment phase. After that, each group uses A short virtual circuit number. Therefore, select A.
  • Packets belonging to the same virtual circuit are forwarded by the same route.
  • All virtual circuits that pass through the faulty node cannot work properly, and the reliability is guaranteed by the network.
  • The network or user host is responsible for error handling and flow control.

🏆 Computer composition principle

Multiple parts hooked on bus ___ (University of Science and Technology Beijing 2014)

A. Data can only be sent to and received from the bus in time-sharing mode B. Data can only be sent to and received from the bus in time-sharing mode C. Data can be sent to and received from the bus at the same time. D. Data can be sent to the bus at the same time, but data can only be received from the bus in time-sharingCopy the code

Answer and analysis

Answer: B

🔊 bus is a set of common information transmission lines that can be shared by multiple components in a time-sharing manner.

Time-sharing means that only one component is allowed to send information to the bus at the same time. If two or more components send information to the bus at the same time, signal conflicts are bound to occur.

Sharing means that multiple components can be connected to the bus, and the information exchanged between them can be transmitted through this set of public lines. Multiple components can receive the same information from the bus at the same time.

💻 Operating system

The ___ algorithm produces the least page missing rate, but it is not a practical page elimination algorithm (Beihang University, 2015)

A. FIFO
B. OPT
C. LRU
D. CLOCK
Copy the code

Answer and analysis

Answer: B

🔊 The best OPT(Optimal) replacement algorithm, which eliminates pages that will not be used in the future or for a long time, to minimize the page miss rate.

However, this is not possible because there is currently no way to predict which pages will not be used, so the OPT algorithm is more used to evaluate other algorithms.