Cavendish University Uganda – Examination, 2021 Page 1 of 6
Faculty of Science and Technology
OPENBOOK EXAM: COM 212 Data Structures and Algorithms
TIME ALLOWED:.
AVAILABLE FROM: Date: Wednesday, 16th June 2021 Time: 09.00 a.m.
TO:
(UPLOAD DEADLINE): Date: Sunday, 27th June 2021 Time: 23.59 p.m..
INSTRUCTIONS TO CANDIDATES
This paper consists of a Case Study which you are expected to read carefully and
understand before attempting to answer the accompanying questions.
The paper consists of two sections A and B. Section A is compulsory. Attempt any one
question from section B
Read the following before answering the examination questions.
1. Clearly indicate the following on the Answer Booklet: Course Code and Course
Name, e.g., COM121 Linear Programming.
2. Write/Type your Name and Student ID (Registration Number) on each and every
page of the Answer Booklet, preferably as a Header.
3. Read each question carefully before you answer.
4. Answer the questions in the downloaded Answer Booklet (offline) as a typed
Microsoft Word document.
5. If the paper is a mathematics paper, and you cannot type your answers using the
Microsoft Word Equation Editor:
Cavendish University Uganda – Examination, 2021 Page 2 of 6
(i) Hand-write your answers using the downloaded Answer Booklet. Please
write as neatly as possible as illegible handwriting cannot be marked.
(ii) After, scan/photocopy each and every page of your Answer Booklet using a
photocopier scanner or your phone camera.
(iii)Combine all the scanned pages into a single document (format: pdf, image
(JPEG, PNG, TIFF, etc.)) that can be uploaded on the CULP System.
6. Upload your Answer Booklet on/before the stated date and time.
7. Firstly answer the questions that you feel can obtain the most marks for you but, if
there are any compulsory questions, you must ensure that you attempt these.
8. Number the answers to the questions clearly before answering.
CASE STUDY:
The Data Structures and Algorithms course to undergraduate students of Computer
Science covers topics such as: Data Structures Versus Algorithms;
Primitive/Basic/In-Built Data Structures; Structure Data Structures; Abstract Data
Structures; Arrays; Structures, Union and Sets; Recursion, Linked Lists; Stacks and
Queues; Trees; Graphs; Searching Algorithms; Sorting Algorithms, Hash Tables,
etc. For every data structures studied the emphasis is on:
1. Features (Characteristics, Properties) of a data structure
2. Declaring and defining a data structure in a chose programming language
3. Inputting data in/into a chosen data structure
4. Outputting data in a chosen data structure
5. Deleting data from a chosen data structure.
There are operations normally carried out on data structures which include
1. copying data from one data structure to another
2. Concatenating/joining two or more data structures
3. Determining the number of elements in a data structure (length of a data
structure), etc.
Application of data structures and algorithms are given in the below.
Cavendish University Uganda – Examination, 2021 Page 3 of 6
Section A: Compulsory
Question 1
In the Faculty of Science Technology, three programmes are offered by students: 1-
Computer Science, 2-Information Technology, 3-Computer Engineering, 4-
Software Engineering, 5-Information systems. There are 25 students doing computer
science, 40 students doing information technology, 30 students offering Computer
engineering, 60 students offering software engineering and 20 students offering
information systems. Each student does five (5) courses in a semester.
The Faculty wants to design a program in C for processing the above information
using an appropriate data structure.
| (a) | Declare a data structure in either C or C++ which can be used to store the above information. (5 marks) Give the main features of the data structures declared in (a). (5 marks) Write a program in either C or C++ to input (read in/capture) and output (print / write /display) the information stated above. (15 marks) |
| (b) (c) |
Total 25 marks
Section B: Attempt any one (1) question from Section B
Question 2:
The following example shows the number of fruits (in tonnes) sold on particular
days from commercial agricultural farm.
The farm wants to develop an application to store the information shown in the
matrix example above. The application should use a data structure that is mapped
onto RAM (memory) which is in the vector form.
T =
Cavendish University Uganda – Examination, 2021 Page 4 of 6
Let MEMStart be the Starting address of the array that stores the above matrix in
MEMmory (Base address)
Let T(R,C) be the element of T in the Rth row and Cth column
Let ADDT(R, C) be the ADDress of T(R,C) in memory.
Show that
| (a) | the row-by-row mapping gives ADDT(R,C) = MEMStart + N(R-C) + (C-1). |
| (8 marks) | |
| (b) | the column-by column mapping gives ADDT(R,C) = MEMStart + (R-1) +M(C-1). (8 marks) |
| Where | N = number of columns M = number of rows |
(c) Insertions and deletions in the data structure used to store the above
information in the matrix may at times present some challenges. Give and
discuss these challenges associated with insertions and deletions.
Total 25 marks
Question 3
(a) A polynomial of degree n has the form:
anxn +an-1xn-1 + an-2xn-2 + ….+ a1x +a0
where ai , i = 1, 2, …n, are numeric constants called coefficients of the
polynomial and an 0.
Consider the following polynomial declaration:
struct polynomial {
| int int |
coefficient; exponent; |
| }; | |
| struct polynomial Data; |
struct Node {
struct polynomial Data;
struct Node *Nextptr;
};
Cavendish University Uganda – Examination, 2021 Page 5 of 6
struct Node *head = NULL;
(a) develop an ordered linked list that can represent a polynomial of degree
n. (8 marks)
(b) Let CURRNODE be the node in the linked list in a(i) and let CURRPTR
be its pointer.
Let PREVNODE be the node preceding CURRNODE and let
PREVPTR be its pointer.
Let NEXTNODE be the node immediately after CURRNODE and let
NEXTPTR be its pointer.
Illustrate with diagrams, how a node which is neither at the beginning
nor at the end of the linked list may be deleted from the linked list (Hint
n 3). (7 marks)
(c) Hence design a pseudocode in C or C++ for deleting a node from the
linked list above. (10 marks)
Question 4
Descriptions of jobs waiting in a computer for the printer are generally kept in a
queue. We want to keep track of the printing jobs recorded by a user name and
anticipated printer time (in seconds) for the job. Add jobs to the queue as printouts
are requested and remove them from the queue as they are serviced.
| (i) | Determine whether an array-implementation or a dynamically-linked list implementation (of a queue) is appropriate in this case. Why and /or why not? (3 marks) Illustrate your implementation choice in (a) (i) diagrammatically. (5 marks) Illustrate the addition and deletion of jobs diagrammatically and hence |
| (ii) | |
| (iii) |
design a pseudocode for adding and removing the jobs to and from the
queue. (5 marks)
(b) (i) Write notes on the following (give three examples for each)
Prefix notation
Infix notation
Suffix (postfix / Reverse Polish(RPN)) notation. (2 marks @)
(ii)Use associated stack manipulations to evaluate the following Reverse Polish
(RPN) Expression: 2 3 * 4 5 * + 1 – (6 marks)
(Hint : Each operand is a single digit number between 0 and 9 )
Cavendish University Uganda – Examination, 2021 Page 6 of 6
Question 5
(a) State whether a queue or a stack or neither structure would be appropriate for
each of the following tasks. Indicate why or why not.
| (i) (ii) (iii) |
A waiting list of customers to be seated in a restaurant. A group of students’ tests waiting to be graded. An address book listing names and telephone numbers in alphabetical order. Patients waiting for service in a doctor’s office. ( 3marks @) |
| (iv) |
(b) In recursive functions, the parameters are usually stored on a stack. For example,
when the function
int factorial (int n)
{
int fact;
if (n = = 0)
fact = 1;
else
fact = m * factorial (n – 1);
return fact;
}
is called, the successive values of the parameter n are stored on a stack. For
example, if the initial call were : value = factorial (5), then 5 would be pushed
on to the stack for n.
The next call to factorial would push 4, then 3, and so on, until the parameter
value of 0 is pushed. Then the values would be popped one at time and multiplied
by the previous product until the stack is empty.
Use a stack to illustrate how the above procedure would be used to evaluate
factorial (7). (5 marks)
(c) Convert the following infix expression to Reverse Polish Notation(RPN). (8
marks)
Total 25 marks
7* 9 9 53 6