**Exam Algorithms and Data Structures**

算法和数据结构代写 Please write your name, student number, and study program on this page. The fifirst part of the exam consists of 10 multiple choice…

**Exam instructions **

**– please read carefully – **

Provide your answers for the multiple choice questions **in the table below**.

**Please work out your answer on scratch paper, and only write the fifinal ****version on the exam. **

*p/*10 where*p*is the number of points you earned.

**Answers to multiple choice questions **

Please use only the capitals A, B, C, D.

**Part I: Multiple Choice Questions 算法和数据结构代写**

- On an empty queue, the following actions are performed:

enqueue(8); enqueue(3); dequeue(); enqueue(2); enqueue(dequeue());

dequeue(); enqueue(5); dequeue(); dequeue();

What is the result of the last dequeue()?

A.2.

B.3.

C.5.

D.8.

- The function insertInOrder() inserts a number in an increasingly ordered list. When the number already occurs in the list, the function does nothing.

Consider the following code for insertInOrder:

1 list insertInOrder(list li,intn) { 2 List newList = NULL; 3if( ??? ) { 4 List newList = malloc(sizeof(structListNode)); 5 assert(newList!=NULL); 6 newList->item = n; 7 newList->next = li; 8returnnewList; 9 } 10if( li->item < n ) { 11 li->next = insertInOrder(li->next,n); 12 } 13returnli; 14 }

What should replace the condition ??? in line 3 in order to obtain a correct defifinition of insertInOrder?

A.li!=NULL && n <= li->item

B.li!=NULL && n < li->item

C.li==NULL || n <= li->item

D.li==NULL || n < li->itemAlgorithms and Data Structures in C page 3 of 8 Friday, April 8, 2016

#### 3.Consider the following grammar: 算法和数据结构代写

hcodei::=hnumberi hwordi.hnumberi::= {hdigiti} .hwordi::=hcapitali{hlowercasei} .hcapitali::= ’A’|’B|’C’ .hlowercasei::= ’a’|’b’|’c’ .hdigiti::= ’0’|’1’|’2’|’3’ .

Which string is **not **a production of *h **code**i *?

A.223Ccca

B.3212b

C.1B

D.Abc

4.Which of the following is a **correct **statement about binary trees T?

A.The number of edges in T is equal to the number of nodes plus one.

B.The number of leaves is even.

C.In postorder traversal, the root is visited last.

D.Every node except the root has a sibling.

5.When implementing a search tree in C, the pointer representation is generally preferred over the array representation. Which of the following statements is a **correct **argument for this preference?

A.The array representation may lead to ineffiffifficient memory usage.

B.The pointer representation admits recursive functions.

C.The array representation leads to programs with higher time complexity.

D.All of the above.

#### 6.Let T be a text with length *n*, and let ST be the suffiffiffix trie for text T. Moreover, let P be a pattern with length *m*. Which of the following statements is **correct**?

A.If P occurs in T, there is a node in ST containing P. 算法和数据结构代写

B.P occurs in T if and only if there is a path in ST from the root to a leaf that corresponds with P.

C.ST has *n *leaves and at most 2*n *nodes.

D.ST enables checking whether P occurs in T in *O*(1) time.Algorithms and Data Structures in C page 4 of 8 Friday, April 8, 2016

7.This question is about the algorithm Downheap for heaps where the largest value is in the root. Some occurrences of the node variables v, lc, rc are replaced by X, Y, Z.

**algorithm **Downheap(v)

**input **: node v in a heap, with possibly a conflflict

with the heap order between v and its children

**result **: heap order is restored

**if **v has at least one child **then **

lc *← *the left child of v

rc *← *the right child of v (or lc, when v has no right child)

**if **(value of lc) *> *(value of v) and (value of lc) *> *(value of rc) **then **

swap the values of X and Y

Downheap(X)

**else if **(value of rc) *> *(value of v) **then **

swap the values of Y and Z

Downheap(Z)

How to replace X, Y, Z in order to obtain a correct algorithm?

A.X by rc, Y by lc, Z by v.

B.X by rc, Y by v, Z by lc.

C.X by lc, Y by rc, Z by v.

D.X by lc, Y by v, Z by rc.

#### 8.Let ST be the standard trie for the collection *W *= *{*her, his, there, this*}*, and CT the compressed trie for *W*. Which of the following statements about the number of nodes in ST and CT is **correct**? 算法和数据结构代写

A.ST contains 12 nodes, CT contains 7 nodes.

B.ST contains 13 nodes, CT contains 7 nodes.

C.ST contains 12 nodes, CT contains 8 nodes.

D.ST contains 13 nodes, CT contains 8 nodes.

9.Which of the following statements about graphs is **wrong**?

A.If a graph contains less edges than nodes, it is not connected.

B.Every cycle in a graph is a path.

C.If a graph is connected and has no cycles, it is a tree.

D.If all nodes in a graph have an odd degree, then the number of nodes is even.

10.This question is about the application DFS(G,v) of the algorithm Depth-First Search to graph G and node v in G. Which of the following statements is **wrong**?

A.If G is connected, then DFS visits all edges.

B.If G is connected, then DFS visits all nodes.

C.If DFS visits all nodes, then G is connected.

D.If DFS visits all edges, then G is connected.Algorithms and Data Structures in C page 5 of 8 Friday, April 8, 2016

**Part II: Open Questions 算法和数据结构代写**

- 30 points The type Tree is defifined by

typedef structTreeNode *Tree;structTreeNode {intitem; Tree leftChild, rightChild; };

a.Defifine a C function with prototype Tree buildPerfectTree(**int **h) that, given a non-negative integer h, returns a perfect binary tree with height h in which every node contains an integer that indicates the depth of that node.

So e.g. buildPerfectTree(2) yields a binary tree of height 2 with seven nodes: the root contains 0, its children contain 1 and the other four nodes contain 2.

Hint: use an auxiliary function.

b.Defifine a C function with prototype Tree onlyLeft(Tree tr) that, given a binary tree tr, returns the subtree of tr that corresponds with the leftmost branch in tr. All nodes in tr that are not in the result are to be freed.

So e.g. onlyLeft(buildPerfectTree(2)) yields a tree with 3 nodes: the root contains 0 and only has a left child, which contains 1 and only has a left child that is a leaf and contains 2.

- 30 points a. Defifine in pseudocode an algorithm ShortestPathLength that determines the length of a shortest path between two (possibly equal) nodes in a connected simple graph G. The length of a path is defifined as the number of edges in it.

*Hint*: consider a variant of Breadth-First Search. Do not forget to specify the input and the output of the algorithm.

b.Indicate the time complexity of the algorithm, and motivate your answer.