**Exam Algorithms and Data Structures in C**

Data Structure代写 Please write your name, student number, and study programme on this page. The fifirst part of the exam consists of 10 multiple choice questions.

**Exam instructions Data Structure代写**

**– 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 Data Structure代写**

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

enqueue(8); enqueue(5); removeMax(); enqueue(2); enqueue(removeMax()); removeMax(); enqueue(3); removeMax();

What is the result of the last removeMax()?

A.2.

B.3.

C.5.

D.8.

- The function insertInOrder() inserts a number at the correct position in an increasingly ordered list. When the number already occurs in the list, the function does nothing. Consider the following code for insertInOrder, which uses the function addItem().

1 List insertInOrder(List li,intn) { 2 List li1; 3if( li == NULL || n < li->item ) { 4returnaddItem(n,li); 5 } 6if( n == li->item) { 7returnli; 8 } 9 li1 = li; 10while( li1->next != NULL && (li1->next)->item < n ) { 11 li1 = li1->next; 12 } 13if( ??? ) { 14 li1->next = addItem(n,li1->next); 15 } 16returnli; 17 } 18 19 List addItem(intn, List li) { 20 List newList = malloc(sizeof(structListNode)); 21 assert(newList!=NULL); 22 newList->item = n; 23 newList->next = li; 24returnnewList; 25 }

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

A.li1->next == NULL

B.n < (li1->next)->item

C.li1->next == NULL || n < (li1->next)->item

D.li1->next != NULL && n < (li1->next)->itemAlgorithms and Data Structures in C page 3 of 8 Thursday, April 13, 2017

#### 3.Consider the following grammar: Data Structure代写

hcodei::=hnumber0i hwordi[hwordi]hnumber1i.hnumber0i::= {hevendigiti} .hnumber1i::= {hevendigiti | hodddigiti}hodddigiti.hwordi::=hletteri hletteri.hletteri::= ’A’|’B|’C’ .hevendigiti::= ’0’|’2’|’4’|’6’|’8’ .hodddigiti::= ’1’|’3’|’5’|’7’|’9’ .

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

A.2240AAB05789

B.02222CC

C.666CB135798

D.BB36847

4.Consider the following two statements about binary trees.

S1. The number of nodes is equal to the number of edges plus one.

S2. When in inorder traversal the root is visited fifirst, the root is the only node.

A.Both statements are correct.

B.Both statements are incorrect.

C.S1 is correct, S2 is incorrect.

D.S1 is incorrect, S2 is correct.

#### 5.Let *T *be a binary tree containing in its 1000 nodes the numbers 1, 2, . . . up to 1000. Indicate which of the following statements is *false*.

A.If *T *is a search tree, then the number in the root is between 9 and 991.

B.If *T *is a search tree, then its height may be any value between 9 and 999.

C.If *T *is a heap, then the number 900 may be in a leaf. Data Structure代写

D.If *T *is a heap, then its height is 9.

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

A.ST has *n *leaves.

B.ST has at most 2*n *nodes.

C.If P occurs in T, there is a node in ST containing P.

D.ST enables checking whether P occurs in T in *O*(*m*) time.Algorithms and Data Structures in C page 4 of 8 Thursday, April 13, 2017

7.This question is about Dijkstra’s shortest path algorithm. Consider the following pseudocode:

algorithmDijkstra (G, v)inputconnected weighted graph G with node voutputfunction d yielding for every node the length of a shortest path to v S←nodes(G)forallu∈nodes(G)dod[u]←ifu=vthen0else∞whileS is not emptydou←node in S with minimal value of d remove u from Sforallnodes z adjacent to udoif???thend[z]←d[u] + weight[u][z]returnd

#### How to replace the condition ??? in order to obtain a correct algorithm? Data Structure代写

A.z *6∈ *S and d[z] = *∞ *

B.z *∈ *S or d[z] = *∞ *

C.z *6∈ *S or d[z] *> *d[u] + weight[u][z]

D.z *∈ *S and d[z] *> *d[u] + weight[u][z]

8.Let ST be the compressed suffiffiffix trie for the string MISSISSIPPI$. What is the number of nodes in ST?

A.17

B.18

C.19

D.20

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

A.If a graph is a tree, it has less edges that nodes.

B.If a graph contains a cycle, it is connected.

C.If all nodes in a graph have a positive degree, the graph is connected.

D.If a graph has nodes with odd degree, then it also has a node with even degree.

10.This question is about the application of the algorithm BFS (Breadth-First Search) to explore a graph G. Which of the following statements is **wrong**?

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

B.If BFS visits all edges, then G is connected.

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

D.If BFS visits all nodes, then G is connected.Algorithms and Data Structures in C page 5 of 8 Thursday, April 13, 2017

**Part II: Open Questions Data Structure代写**

- 30 points a. The type List is defifined by

typedef structListNode* List;structListNode {intitem; List next; };

Defifine a C function with prototype List strictOrder(List li) that, given an ordered list li, returns a maximal sublist of li that is strictly increasing, i.e. in which no number occurs more than once. Make sure that no memory leaks occur.

So e.g. when list li corresponds with the sequence (1,3,3,3,7,9,9,11,11) then strictOrder(li) corresponds with (1,3,7,9,11).

b.The type Tree is defifined by

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

Defifine a C function with prototype Int numberOfLeaves(Tree tr, **int **n) that, given a binary tree tr and an integer n, returns the number of leaves in tr at depth at most n.

- 30 points This problem is about cycles in simple connected graphs. A simple graph is a graph without loops and parallel edges. The length of a cycle is defifined as the number of edges in it.

A *simple *cycle is a cycle with length *> *0 in which all edges are difffferent.

a.Defifine in pseudocode an algorithm FindCycle that determines whether a graph contains a cycle. Do not forget to specify the input and the output of the algorithm.

Hint: you may use Depth-First Search or Breadth-First Search. When you use Breadth-First Search, you may use this solution as a starting point for part b.

b.Defifine in pseudocode an algorithm ShortestCycleLength that determines the length of a shortest simple cycle containing a given node v in a graph.

Hint: use FindCycle as starting point, but only identify simple cycles. This can be done by checking that the candidate cycle contains two *difffferent *edges connected to v.