Part A: Multiple Choice questions
1.
#include< stdio.h>
void function(int*);
int main(void){
int a = 10;
function(a);
printf("%dn", a);
return 0;
}
void function(int *a){
*a = *a - 1;
printf("%dn", *a);
}
According to the above program, which of the following is correct?
a)the first output is 10
b)the second output is 9
c)the first output is 9
d)the second output is 10
e)none of the above
2.
#include< stdio.h>
void function(int*);
int main(void){
int *a;
int b = 10;
a = &b;
function(a);
printf("%dn", a);
return 0;
}
void function(int *a){
*a = *a - 1;
printf("%dn", *a);
}
According to the above program, which of the following is correct?
a)the first output is 10
b)the second output is 9
c)the first output is 9
d)the second output is 10
e)none of the above
3.
#include< stdio.h>
void decode(char*);
int main(void){
char *s = "abcdefghijklmnopqrstuvwxyz";
decode(s);
return 0;
}
void decode(char *s){
int a[4] = {7, 4, 11, 15};
printf("The code is %cn", *(s + *(a + 2)));
}
According to the above program, which of the following is correct?
a)The code is a
b)The code is f
c)The code is i
d)The code is l
e)none of the above
Part B: Short Answer Questions
Question 1
What are the most two common basic operations on Stack ADT?
Question 2
Use stack to evaluate 3 4 2 * + 2 5 3 * 5 - * -, show all your steps to get full marks
Question 3
What is the BigO of T(N) = 3 + 3N + 6logN? (0.5 mark)
Question 4
Given the sorting algorithm below, show all your steps to find the worst case complexity.
1.Place the marker at the first element
2.If the marker is pointing at the last element, then stop. Otherwise continue.
3.Find the smallest element to the right of the marker
4.If this element is smaller than the element the marker is pointing at, then swap
5.Advance the marker to the element to the right
6.Go to step 2
Show your calculation steps here (0.5 mark)
Question 5
Given an array 7, 4, 6, 9, 5, 10, 8
a. Create a Binary Search Tree in Figure 1. (1 mark)
b. Which tree traversal can give the node data of a binary search tree in ascending order? (1 mark)
Question 6
Referring to Question 5,
a. Create a max-heap in Figure 2. (1 mark) Assume all data arrives as an array and use sift-down algorithm to create a max-heap.
Question 7
Traversing a graph see image.
What is the output if we perform the depth-first traversal starting from E?
Question 8
Hashing
Suppose the following keys come in the order given:
52, 33, 84, 43, 16, 59, 31, 22, 19
The hash function is key % 9 + 1 and location = location + 2 when collision occurs.
a.Show the array i.e. the hash table with proper initialization. (0 = empty, -1 = deleted)
b.Show the array after all the numbers have been inserted.
c.What is Secondary Clustering?
Part C: Programming
The following are the node and list structures of a pointer implemented list.
typedef struct{
int nodeCount;
Node *head;
Node *current;
Node *tail;
}List;
typedef struct node{
int num;
struct node *next;
}Node;
ListOne and listTwo are the instances of List, and both of them contain five nodes. We want to combine these two lists to form Clist as shown in Fig 1. see image.
In this question, write a function to combine listOne and listTwo to become one list named CList. The function prototype is void combineList(List*, List*, List*);