2003 system designer (advanced programmer) analysis of questions in the morning
- Data structure
Chen Zhizhen (chazg99@21cn.com)
The data structure has a large proportion in elevation exams, mastering data structures, which is undoubtedly internal cultivation for programmers. There are three main aspects of the data structure: the logical structure of the data; the physical storage structure of the data; the operation (or algorithm) of the data. Typically, the design of the algorithm depends on the logical structure of the data, and the implementation of the algorithm depends on the physical storage structure of the data. There are four basic types of logical structures: collection structure, linear structure, tree structure, and network structure. Tables and trees are the most commonly used high-efficiency data structures, many efficient algorithms can be designed with these two data structures. Table is a linear structure (full order relationship), tree (predecessor or hierarchical relationship) and diagram (local orchestration) is a non-linear structure. Master linear table, multidimensional array, array, stack, tree, binary tree, definition, storage, and operation, and common sorting and finding algorithms. The focus is a binary tree and a figure and the algorithm associated with it. The review requirements for the data structure have never been able to master every point of the textbook.
1. The key path refers to the __________________________________________________________________________________________________________________.
A. The longest loop B. the shortest circuit
C. The longest path from the source point to the coming point (end vertex)
D. The shortest path from the source point to the coming point (end vertex)
Answer: c
Analysis: The AOE network is a direction map, usually used to estimate the completion time of the project, the vertices in the figure indicate events, and the direction of the direction is active, and the right of the edge represents the time required to complete this activity. The AOE network does not have to circuit, there is a unique degree of starting vertex, and the only outset of zero. Two issues most concerned about the AOE network: How long does it take to complete the entire project? Those activities are the key to the progress of the project? This leads to two concepts: critical paths and key activities. The maximum path from the startset to the end of the vertex is a critical path, and the length of the path is also the minimum time of the completion. All activities on the key path are critical activities, the maximum feature of key activities is: the earliest start time of the activity is equal to the latest start time allowed by the activity. Key activities delay time, the entire project also delays the time. Seeking critical path only requires the maximum path to the end point, pay attention to the critical path is not unique.
Review Tip: Similar test sites are also: AOV network, shortest path, minimum tree.
2. It does not match the heap definition in the following sequence is ________.
A. (102, 87, 100, 79, 82, 62, 84, 42, 22, 12, 68)
B. (102, 100, 87, 84, 82, 79, 68, 62, 42, 22, 12)
C. (12, 22, 42, 62, 68, 79, 82, 84, 87, 100, 102)
D. (102, 87, 42, 79, 82, 62, 68, 100, 84, 12, 22)
Answer: D
Analysis: The method of judging the stack is to see the sequence as a fully binary tree. If the value of all the non-terminal nodes in the tree is not more than the value of the nodes of the left and right children, the sequence is a heap. . Review Tip: The definition must be clear during the examination of the candidates, which is the key to the score.
3. A complete binary tree with 767 nodes, the number of leaves nodes is ____.
A. 383 B. 384 C. 385 D. 386
Answer: B
Analysis: It can be derived according to the formula, assuming that N0 is the total number of nodes (i.e., the number of leaves nodes), N1 is a total number of nodes, N2 is the total number of nodes of 2, and by the nature of the binary tree : N0 = N2 1, then n = N0 N1 N2 (where n is the total number of nodes of the full binary tree), and the N2 is eliminated by the above formula: n = 2 N0 N1-1, since the total number of junctions in the full binary tree is only two May be 0 or 1, thereby obtaining N0 = (n 1) / 2 or N0 = N / 2, combined into a formula: N0 = ë (n 1) / 2 û, the leaf knot can be calculated according to the total number of nodes of the full binary tree. Point number. This topic is calculated: 384.
Review Tip: This remember the formula to remember, temporary derivation is also, but it is easy to delay the time.
4. If a non-connected non-connected direction of K strip is a forest (n> K), it will be ____ tree in the forest.
A. K B. N C. N-K D. N K
Answer: c
Analysis: Suppose there is S tree in the forest: T1, T2, ..., TS, and each Ti has ni nodes, ki strip (i = 1, 2, ..., s), by the tree, etc. The price can be known: ki = Ni-1, then k = k1 k2 ... ks = (n1-1) (N2-1) ... (NS-1) = n-s, so s = N -K, so there is a N-K tree in the forest.
Review Tip: This question can be easily solved if the equivalent condition of the tree is clear. If you don't know, you can't get started. However, the candidates can also draw a specific non-connected forest, such as: 5 of the 2 trees of the five knots 3, can also help judgment. Abstract issues are an important way to make a choice issue.
