Data Structures and Algorithms Classic Example Answers

Posted on by itadmin itadmin

Find the answers to the following data structures test questions…

I.

1,Complexity 2.Linear structure Non-linear structure

3. Can be accessed randomly by sequence number 4.Data elements

5.LIFO 6.n 7. Can only be done at the head of the queue

9.Length 1 Depth 1

10 -+A*BC/DE

11

12 The vertex Vp to the vertex The path between Vq is the specified sequence Vp, Vi1, Vi2 — Vim, Vq.

13 n(n-2)/2 14 n-1 15 2n-1

17 A storage structure

19 It is possible to traverse the entire chained table starting from any node in the table; operations are performed on the head and tail of the chained table using only a finger pointing to the tail node, improving efficiency.

20 A stack is a linear table with restricted operations of insertion and deletion only at one end of the table.

II.

1 Time complexity and space complexity of algorithms

2. Queue

3.

4 Nested set representation, generalized table representation, concave representation

5. 45 6. S(1) X(1) S(2) S(3) X(3) S(4) X(4) X(2)

7 (1) O(nˆ 2)

(2) O(nˆ2)

8.

Huffman Tree:

WPL=2*5+4*5+5*4+16*3+8*3+7*3+30=173

9.Neighborhood Matrix:

Neighborhood Tables:

10.Bifurcation Tree:

Precedence: ABCEFD

Middle order: BEFCDA

Post-order: FEDCBA

What are the answers to the following questions on data structures and algorithms in computing?

(1) Handle conflicts by linear probing open address method;

H(Jan)=10/2=5;

H(Feb)=6/2=3;

H(Mar)=13/2=6;

H(Apr)=1/2=0;

H(May)=13/2=6; Conflict;H1=6+1=7;

H(June)=10/2=5; Conflict;H1=5+1=6; Conflict;H2=7;H3=8;

H(July)=5;H1=6;H2=7;H3=8;H4=9

H(Aug)=0;H1=1;

H(Sep)= 9;H1=10;

H(Oct)=7;H1=8;H2=9;H3=10;H4=11;

H(Nov)=7;H1=8;H2=9;H3=10;H4=11;H5=12

H(Dec)=2

ASL=(1+2+1+1+1+1+2+2+) 4+5+2+5+6)/12=31/12

(2) Handling conflicts by chain address method

H(Jan)=5;

H(Feb)=3;

H(Mar)=6;

H(Apr)=0;

H(May)=6

H(June )=5;

H(July)=5;

H(Aug)=0;;

H(Sep)=9;

H(Oct)=7;

H(Nov)=7;

H(Dec)=2

0->Apr->Aug

< p>1->

2->Dec

3->Feb

4->

5->Jan->June->July

6->Mar->May

7->Oct-& gt;Nov

8->

9->Sep

ASL=(1+2+1+1+1+2+3+1+2+1+2+1)/12=18/12

Related Posts