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 –
- Please write your name, student number, and study programme on this page.
- The fifirst part of the exam consists of 10 multiple choice questions. Read carefully each question and the four options, and select the option that answers the question correctly. When more than one option answers the question correctly, select the most informative option.
Provide your answers for the multiple choice questions in the table below.
- The second part of the exam consists of 2 open problems. Read carefully each problem and write your answers in the boxes below the problems.
Please work out your answer on scratch paper, and only write the fifinal version on the exam.
- Your exam grade is computed as follows. For every correct answer to the multiple choice questions, you will earn 4 points. For each of the 2 open problems you can earn maximally 30 points. Your exam grade is 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, int n) {
2 List li1;
3 if ( li == NULL || n < li->item ) {
4 return addItem(n,li);
5 }
6 if ( n == li->item) {
7 return li;
8 }
9 li1 = li;
10 while ( li1->next != NULL && (li1->next)->item < n ) {
11 li1 = li1->next;
12 }
13 if ( ??? ) {
14 li1->next = addItem(n,li1->next);
15 }
16 return li;
17 }
18
19 List addItem(int n, List li) {
20 List newList = malloc(sizeof(struct ListNode));
21 assert(newList!=NULL);
22 newList->item = n;
23 newList->next = li;
24 return newList;
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代写
h codei ::= h number0 i h wordi [ h wordi ] h number1 i .
h number0 i ::= { h evendigiti } .
h number1 i ::= { h evendigiti | hodddigiti } h odddigiti .
h wordi ::= h letter i h letter i .
h letter i ::= ’A’ | ’B | ’C’ .
h evendigiti ::= ’0’ | ’2’ | ’4’ | ’6’ | ’8’ .
h odddigiti ::= ’1’ | ’3’ | ’5’ | ’7’ | ’9’ .
Which string is a production of h codei ?
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 2n 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:
algorithm Dijkstra (G, v) input connected weighted graph G with node v output function d yielding for every node the length of a shortest path to v S ← nodes(G) forall u ∈ nodes(G) do d[u] ← if u=v then 0 else ∞ while S is not empty do u ← node in S with minimal value of d remove u from S forall nodes z adjacent to u do if ??? then d[z] ← d[u] + weight[u][z] return d
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 struct ListNode* List;
struct ListNode {
int item;
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 struct TreeNode *Tree;
struct TreeNode {
int item;
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.
