数据结构与算法习题答案

1. Fill the blank with correct C++ codes:

(1) Given an array storing integers ordered by distinct value without duplicate, modify the binary

search routines to return the position of the integer with the smallest value greater than K when K itself does not appear in the array. Return ERROR if the greatest value in the array is less than K: (12 scores)

// Return position of smallest element >= K int newbinary(int array[], int n, int K) { int l = -1;

int r = n; // l and r beyond array bounds while (l+1 != r) { // Stop when l and r meet

___ int i=（l+r）/2_____; // Look at middle of subarray if (K < array[i]) __ r=i ___; // In left half if (K == array[i]) __ return i ___; // Found it if (K > array[i]) ___ l=i ___ // In right half }

// K is not in array or the greatest value is less than K

if K<= array[n-1] （or r!=n） // the greatest value in the array is not less than K with r updated

return r ; // when K itself does not appear in the array

else return ERROR; // the integer with the greatest value less than K }

(2) The height of a complete binary tree with k nodes is 「log2(k+1)︱(1 node tree has hight 1)

(3) The number of different shapes of binary trees with 5nodes is _42_.

2. A certain binary tree has the preorder enumeration as ABECDFGHIJ and the inorder enumeration as EBDCAFIHGJ. Try to draw the binary tree and give the postorder enumeration. (The process of your solution is required!!!) A A A A

B F B F B F EBDC FIHGJ

E IHGJ E C G E C G CD

J IH J H D D Postorder enumeration: EDCBIHJGFA

I

3. Determine Θ for the following code fragments in the average case. Assume that all variables are of type int. (1) sum=0;

for (i=0; i<5; i++) for (j=0; j

sum++; solution : Θ___(n)_______

(2) sum = 0;

for(i=1;i<=n;i++) for(j=n;j>=i;j--)

sum++; solution : Θ__(n2)________

(3) sum=0;

if (EVEN(n))

for (i=0; i

sum=sum+n; solution : Θ___(n)_____

4. Trace by hand the execution of creation a binary search tree with the input sequence as : {46，25，78，62，12，37，70，29} which is empty tree initially. Solution: BST obtained with data inserted one by one

46

25 78 12 37 62 29 70

5. Design an algorithm to transfer the score report from 100-point to 5-point, the level E corresponding score<60, 60～69 being D, 70～79 being C, 80～89 as B，score>=90 as A. The distribution table is as following. Please describe your algorithm using a decision tree and give the total path length.

Score in 100-point Distribution rate

0-59 5%

60-69 10%

70-79 45%

80-89 25%

90-100 15%

solution:

the design logic is to build a Huffman tree

100% 0 1

55% 45% 100 1 0 C 30% 25% 0 1 B 15% 15% A 0 1 D 5% 10% D E

Total length: 4 + 4 + 3 + 2 + 1= 14, Average length: 4 * 5% +10% * 4 + 15 %* 3 + 25% * 2 + 45% = 2.00, the 0-false,1-true as the logic branches.

6. Assume a disk drive is configured as follows. The total storage is approximately 1.35G divided among 15 surfaces. Each surface has 612 tracks; there are 144 sectors/track, 1024 byte/sector, and 16 sectors/cluster. The interleaving factor is four. The disk turns at 7200rmp (8.33 ms/r). The track-to-track seek time is 20 ms, and the average seek time is 80 ms. Now how long does it take to read all of the data in a 360 KB file on the disk? Assume that the file’s clusters are spread randomly across the disk. A seek must be performed each time the I/O reader moves to a new track. Show your calculations. (The process of your solution is required!!!)

Solution：

The first question is how many clusters the file requires?

A cluster holds 16*1K = 16K. Thus, the file requires 360/16=22.5 clusters=22complete cluster and 8k（8 sectors） The time to read a cluster is seek time to the

cluster+ latency time + (interleaf factor × rotation time).

Average seek time is defined to be 80 ms. Latency time is 0.5 * 8.33 ms (60/7200≈8.33ms), and cluster rotation time is 4* (16/144)*8.33. Seek time for the total file read time is

22* (80 + 0.5 * 8.33+ 4 * (16/144)*8.33 ) +(80 + 0.5 * 8.33+ 4 * (8 /144)*8.33 )≈2019.095ms

7. Using closed hashing, with double hashing to resolve collisions, insert the following keys into a hash table of eleven slots (the slots are numbered 0 through 10). The hash functions to be used are H1 and H2, defined below. You should show the hash table after all eight keys have been inserted. Be sure to indicate how you are

using H1 and H2 to do the hashing. ( The process of your solution is required!!!) H1(k) = 3k mod 11 H2(k) = 7k mod 10+1

Keys: 22, 41, 53, 46, 30, 13, 1, 67. Solution：

H1(22)=0, H1(41)=2, H1(53)=5, H1(46)=6, no conflict

When H1(30)=2, H2(30)=1 （2+1*1）=3，so 30 enters the 3rd slot; H1(13)=6, H2(13)=2 (6+1*2)=8, so 13 enters the 8th slot;

H1(1)=3, H2(1)=8 (3+5*8)= 10 so 1 enters 10 (pass by 0, 8, 5, 2 ); H1(67)=3, H2(67)=10 (3+2*10)= 1 so 67 enters 1(pass by 2) 22 67 41 30 53 46 13 1 0 1 2 3 4 5 6 7 8 9 10

8. You are given a series of records whose keys are integers. The records arrive in the following order: C, S, D, T, A, M, P, I, B, W, N, G, U, R. Show the 2-3 tree that results from inserting these records. （the process of your solution is required!!!） Solution：

MS

BD P U A C GI N R T W 9.

The following graph is a communication network in some area, whose edge presents the channel between two cities with the weight as the channel’s cost. How to choose the cheapest path that can connect all cities? And how to get cheapest paths connecting each city-pair? You can draw all choices if there is more than one path.

1 B 5 5 3 D 4 8 A 2 C 6 7 E G 3 F 1 B 2 5 3 D 4 3 Solution： Draw the MST: It is not a Hamilton path. Get the shortest paths between pairs. A B 1 5 C: 8 C 5 3 4 D C: 8; 3 C:7; C:9 E C:9; 4 C:7; C:10 F A C F E G G BC:13 7 C:10; 3 C:13; A B 1 C B: 6 D BC:9 F 2 G BC:13 B: 6 BC:9 BC: 10; 2 6 C:9 C:10 A: 3; C:12; E BC: 10; C:9; A: 3; 6 C:12; 7 C:10; 3 C:13;

本文来源：https://www.bwwdw.com/article/a5vp.html