Two Data Structure Exercises High Score 100

I think you can read the book and make it up yourself, so why don't you think about it yourself, and then put your questions out to everyone.

I won't do that either, though, 2 points in hand!

1. Multiple choice questions.

1．c2．d

Analysis: a A full binary tree can be stored in an array, and the tree is a nonlinear structure.

b Linked lists, and the insertion and deletion are efficient.

c Linked lists also have bidirectionally linked lists with two pointer fields.

3 a4 a sequential tables provide random access to any element.

5 d6 Are you getting this question wrong?

7 d full binary tree: the total number of nodes n=2 h -1 h is the number height, and the total number of nodes is 255

Full binary tree, there are only nodes with degrees of 0 and degrees of 2, and nodes with degrees of 0 are equal to degrees of 1 and the number of nodes is +1 so d is chosen

8 c This problem can be made without drawing, the post-order traversal sequence is dabec,-- the root node is: c

pre-order traversal; Root left and right, so the first one must be c and only the a term is met.

9.A Although you don't give a diagram, it's generally a phase, because I've seen a lot of this problem, and the results of the middle order traversal and the hierarchical traversal are the same.

10.d In the worst-case scenario: the number of comparisons is n times from the first to the last for each lookup

The total number of comparisons is n*n, and the average number of comparisons is n

13.2. Fill in the blanks.

1 Out of the stack. 2．n/2+n/(n+1) 1+2+3……n+n)/(n+1)=．n/2+n/(n+1)

3 14 Let the keywords of the data elements to be sorted be (67,24,14,22,33,15,11,15), and use the selection method to sort them in ascending order, and the number of times to be compared is [ ].

7 15 Method Same as the multiple-choice question on the full binary tree.

8 No figures. 9.16 Same method as Question 7.

1 b2 a

3 b4 ？

5 c6 d

7 b8 c

9 c10 b

Refer to the answers of the first two and your own thoughts

I feel like the one on the first floor explains a lot.。。 But it's not very accurate.

2.Answer, a, this is based on the definition of a circular queue, and when dealing with the overflow of a circular queue, the textbook does not use empty digits, so the number of elements in the queue (rear-front+m)%m; The +m is because rear-front<0 is possible

3.For empty queues, front=0; at the beginningThat's fine. When the queue is not empty, the front and rear point to the head element and the tail element respectively, which is different from the pointer at the end of the queue in the book, so the number of elements in the queue is calculated as follows:

rear-front+1+n)%n;front=0;At first, there are no elements in the team, so rear=n-1; So choose B

The first thing you need to do is understand the characteristics of the "stack". "First in, last out".

5 into the stack, 2 into the stack, 4 into the stack, at this time [524.].After that, 4 is out of the stack, and at this time it is [52], in order to get the top element of the stack. So x is 2