5. Multiplexing the incremental order of the two lengths into a incremental order table for a length of 2N, and the keyword comparison is required.
A. 1 B. N-1 C. N D. 2N
Answer: c
Analysis: Candidates must first understand two premise: the two tables to be merged are increasing and the length is n, and the second is that the topic is asking for the least keyword comparison, that is, the best case Comparative number. The best situation should be: all keywords of a table are greater than all keywords on the other table, such as: (1 2 3 4) and (5 6 7 8). When compared, there are two pointers to point to the first element of the two tables, because a keyword is larger than the keyword of another table, so the element in the keyword is a table with keyword. After the first element is compared, it is first incorporated into a new table. At this time, the pointer of the keyword is still point to the first element, and simply copy the key to the new table to the new table. I.e. So the number of comparisons spend is the top length of the key, that is, n.
6. It is known that the vertices V1 to V7 in the AOE network represent seven events, and the arcs Al ~ A10 represent 10 activities, respectively, respectively, indicate the time spent on each activity, as shown below. Then, the key path of the network is __ (1) __, the relaxation time of the activity A6 (the latest start time of the event - the earliest start time of the activity) is __ (2) __.
(1) A. 7 B. 9 C. 10 D. 11
(2) A. 3 B. 2 C. 1 D. 0
Answer: (1) c (2) a
Analysis: (1) The key path is from the starting point to the longest path. Directly from the figure, V1 V4 V5 V7 is one, the length is 10. (2) It can be seen from the key path that V1 to V4 takes 6, and the activity A6 is at least after passing time 2, the latest start time is: 6-2 = 4, the activity A6 is loose The time is 4-2 = 2.
7. When n-element is rapidly sorted, the time complexity in the worst case is ____.
A. O (1OG2N) B. O (n) C. O (NLOG2N) D. O (n2)
Answer: D
Analysis: If the n elements for rapid sorting are ordered in ordered in the keyword, rapid sorting will degenerate into bubble sort, and the time complexity is O (N2).
Review Tip: This is a concept, and it is also a qualified question, and candidates must be clear.
8. Any algorithm based on "comparison" is sorted, and if the six elements are sorted, the number of comparisons required in worst cases is at least ____.
A. 10 B. 11 C. 21 D. 36
Answer: a
Analysis: In addition to the sorting internally sorting, it is sorted based on the "Comparison of Keywords". Any algorithm for sorting with "comparison", at least é1OG2 (N!) É1OG2 (N!) É1Og2 (N!) In worst cases. Specifically explains that candidates can refer to Yan Weimin and Wu Weimin's "Data Structure" 291 page.
9. If g is a non-connected non-directionless figure having 36 strips (excluding self-loop and multiple edges), Figure G is at least ___ top points. A. 11 B. 10 C. 9 D. 8 Answer: b Analysis: Because g is a non-connected map, there is at least two connecting subgraphs in G, since the question is at least a few vertices, and the picture does not contain itself The loop and multiple side, so a communication map can be seen as a point, and the other connectivity map can be seen as a full picture (because the full picture can get the number in the case of the least vertex), so that the problem is transformed How many vertices are available for this 36 side, can be known from the formula: 36 = n × (n-1) / 2, then n = 9, plus another over-pass figure (only one point), then Figure G at least There are 10 top points.
