数据结构guide(有答案)

●Code an algorithm

●Analyze the time complexity of your algorithm

●Familiar with the operations of BST and AVL trees

●The answer or solution should begin with “Answer:”/“Ans:”/“Solution:”/“Sol:”

Sample questions

Part 1

1.A non-circular doubly linked list can best and most generally be defined as 

a.a linear sequence of elements chained together with pointers 

b.a linear sequence of elements in sequential memory locations 

c.a set of elements chained together with pointers 

d.a set of elements in sequential memory locations 

2.A recursive function can cause an infinite sequence of function calls if 

a.the problem size is halved at each step 

b.the termination condition is missing 

c.no useful incremental computation is done in each step 

d.a and c 

3.Which of these is the correct big-O expression for 1+2+3+...+n? 

a.O(log n) 

b.O(n) 

c.O(n log n) 

d.O(n²) 

4.Here is some code for an integer variable n: 

while (n > 0)

{

n = n/10; // Use integer division

}

What is the worst-case time analysis for the above loop? 

a.O(1) 

b.O(log n) 

c.O(n) 

d.O(n²) 

5.Consider the following statements: 

int i = 42;

int j = 80;

int *p1;

int *p2;

p1 = &i;

p2 = &j;

*p1 = *p2;

cout << i << j << endl;

What numbers are printed by the output statement? 

a.42 and then another 42 

b.42 and then 80 

c.80 and then 42 

d.80 and then another 80 

6.What kind of list is best to answer questions such as "What is the item at position n?" 

a.Lists implemented with an array. 

b.Doubly-linked lists. 

c.Singly-linked lists. 

d.Doubly-linked or singly-linked lists are equally best 

7.Suppose we have an array implementation of the stack class, with ten items in the stack stored at data[0] through data[9]. Where does the push member function place the new entry in the array? 

a.data[0] 

b.data[1] 

c.data[9] 

d.data[10] 

8.Is it possible for a member function of a class to access another member function of the same class? 

a.No. 

b.Yes, but only public member functions. 

c.Yes, but only private member functions. 

d.Yes, both public and private member functions can be accessed within another member function. 

1.Circular linked lists are more efficient for some operations  √ 

2.Every linked list has to have at least one external pointer  √  

3.If d is a dynamic array we can delete it with "delete d"   *   

4.An AVL tree with n elements has a worst-case time of O(log n) for individual search operations  √ 

5.If the characters 'D', 'C', 'B', 'A' are placed in a queue (in that order), and then removed one at a time in the order of “ABCD”  *  

6.Suppose T is a binary tree with 14 nodes. The minimum possible depth of T is 4        *  

7.Suppose you run a O(log n) algorithm with an input size of 1000 and the algorithm requires 110 operations. When you double the input size to 2000, the algorithm now requires 120 operations. The best guess for the number of operations required is 140 when you again double the input size to 4000   *  

8.Every node in a binary tree has at most two children  √

Part 3

1.Write a recursive C function to compute the average of the elements of an array. Note that you should write only one function and the length of the array is assumed to be unknown. The upper bound of the length is N, but the length is not necessarily equal to N. 

#define  N  100

int a[N] ; /* the array storing the element */ 

2.Consider inserting the keys 8, 10, 9, 5, 1, 7, 6, 4, 12, 3, and 2 in order into an AVL tree. Initially the tree is empty. Please draw the resulting tree.

3.Given the preorder and inorder traversals of a binary tree, please determine the binary tree. The preorder sequence is ABCDEFGHI, and the inorder sequence is BCAEDGHFI

4.Given an M-ary B+ tree, where M=4 and L=3. Please determine the resulting B+ tree after inserting X and T sequentially. (10 point)