Kingdom of Saudi Arabia

‫المــمـــــــــلكــــة العـربية الســــــعودية‬

Royal Commission at Yanbu
Colleges & Institutes Division ‫الـــــــهـــــــــــيـــــئة الملــــــكـــــــية بــينبع‬
‫قــــطـــاع الـكــــــــــــلــيات والـمــعــاهـد‬
Yanbu University College ‫كـــــلية ينبع الجــــــــــــــــامـــــــــــعية‬
Computer Science & Engineering Dept. ‫قسم علوم وهندسة الحاسب األلي‬
Information & Computer Technology Dept. ‫قسم تقنية المعلومات والحاسب اآللي‬
MIDTERM EXAMINATION

ACADEMIC YEAR 1442/1443 H (2021/2022 G), SEMESTER II (212)

DATA STRUCTURES
CS204
START TIME: 8.30AM
DATE: Monday, 21 March, 2022
FINISH TIME: 10.00AM
STUDENT NAME: _________________________________________________________

STUDENT ID: SECTION: ______

FOR INSTRUCTOR USE ONLY GENERAL INSTRUCTIONS

MAX MARKS  Write your name and I.D. number in the space
Q. No. CLOs
MARK OBTAINED provided above.
A(1-13) 1.01 13  Support materials are not allowed in the examination
(D/4) Hall except those provided by instructor.
A(14-15) 1.02 2  Do not use digital or printed dictionary.
(A/1)  Do not use pencils for answering except for drawing.
B1 2.02 8  Read each question carefully before answering.
(B/6)
 Number shown on the right-hand side against each
B2 1.02 4
(A/1) question is the mark allocated.
C1 2.01 5
(B/1)

TOTAL MARKS
30

INVIGILATOR’S SIGNATURE:

MARKED BY: Signature:

CHECKED BY: Signature:

 Data Structures CS204 Monday, 21 March, 2022

PART A: MULTIPLE CHOICE QUESTIONS (15 marks)

1. Big O notation tells _____________.

a. how the speed of an algorithm relates to the number of items
b. the running time of an algorithm for a given data structure
c. the running time of an algorithm for a given number of items
d. how the size of a data structure relates to the number of items

2. Given the following arrays;

int count = 0;
for(i=1; i < intArray.length; i++) {
if (intArray[i] > intArray[i-1])
count++;
}
System.out.println("Count: " + count);

What will the output display if the array is [1, 12, 23, 3, 4, 14, 4, 5] ?
a. 9
b. 6
c. 4
d. 5

3. Consider binary search algorithm is executed using the following array. How many comparisons
needed to find 61?
int list[ ] = {20, 33, 36, 41, 54, 60, 61};

a. 7
b. 3
c. 8
d. 5

Page 2 of 8
 Data Structures CS204 Monday, 21 March, 2022

4. _____________ and swapping are the two main processes in sorting.

a. Insertion
b. Comparison
c. Deletion
d. Iteration

5. The result evaluating the postfix expression: 2 3 1 * + 9 -

a. 4
b. -4
c. -2
d. 3

6. Say that the following queue allows a maximum of 7 elements, with the following data:

What will be the value of front and rear after enqueue(F) takes place?
a. front = 2; rear = 5
b. front = 0; rear = 4
c. front = 0; rear = 6
d. front = 2; rear = 4

7. What would be the time complexity to find an element in the linked list?
a. O(1)
b. O(n)
c. O(n2)
d. O(n log n)

8. How many comparisons would the Selection Sort make on 5 elements that is already in ascending
order?
a. 0
b. 5
c. 14
d. 15
Page 3 of 8
 Data Structures CS204 Monday, 21 March, 2022

9. Linked list are best suited ____

a. for relatively permanent collections of data
b. for the size of the structure and the data in the structure are constantly changing
c. for both of above situation
d. for none of above situation

10. Suppose one element is dequeue from a Queue that is implemented using a circular array. Which of
the following reference (in the Queue class) will be updated because of this operation?
a. Front
b. Rear
c. Peek
d. None

11. Which sorting algorithm makes the fewest number of swap on a list where all elements are equal?
a. Selection Sort
b. Insertion Sort
c. Bubble Sort
d. Heap Sort

12. Which of the following operations is not efficiently supported by a singly-linked list?
a. Accessing the element in the current position
b. Insertion after the current position
c. Insertion before the current position
d. Moving to the position immediately following the current position

13. Which of the following is the advantage of linked list?

a. In unordered list, searching is slow
b. Insertion at any position is not possible.
c. Deletion at the beginning of list is difficult to perform.
d. Size of list is dynamic

Page 4 of 8
 Data Structures CS204 Monday, 21 March, 2022

14. Given the following code segment for Stack, what is the value at the top of the stack?
Stack color = new Stack(5);
color.push("blue");
color.push(color.pop());
color.push("green");
color.push("red");
color.push(color.top());

a. red
b. blue
c. green
d. stack underflow

15. “You need to develop a system that will display the leader-board of a game. The system will keep the
score and arrange them in descending order to clearly display the ranking of player in the game.”
Which data structure is the best option for the described scenario above?
a. Stack
b. Array
c. Queue
d. Linked list

Page 5 of 8
 Data Structures CS204 Monday, 21 March, 2022

PART B: SHORT ANSWER QUESTIONS (20 marks)

1. Given a list below. Sort this list using insertion sort. Outline the steps and identify how many
comparisons and swaps were conducted in order to get this list sorted in order.
200 150 260 90 100
(6 marks)
Answer:
step 1:

sorted unsorted
1. divides sort and unsorted sections by placing a marker
2. first number unsorted is 150
3. 1 comparison: 150<200.1 swap.
4. Advance marker to one position

Step 2

150 200

sorted unsorted
5. first number unsorted is 260
6. 1 comparison: 260>200 .No swap.
7. Advance marker to one position

Step 3

150 200 260

sorted unsorted
8. first number unsorted is 90
9. 3 comparisons: 90<260. 1 swap. 90 < 200 .1 swap. 90< 150. 1 swap.
10. Advance marker to one position

Step 4

90 150 200 260

sorted unsorted
11. first number unsorted is 100
12. 4 comparisons: 100<260. 1 swap. 100 < 200.1 swap. 100 < 150.1 swap. 100 > 90. No swap.
13. Advance marker to one position

Page 6 of 8
 Data Structures CS204 Monday, 21 March, 2022

2. Suppose that the following class is used to define a node in a linked list.
public class Listnode {
String name;
Listnode next;

public Listnode(String d) {
name = d;
}
}
Assume that a linked list has been created with 2 nodes - "sing" and "song"; and the beginning of
the list is pointed by first.

a. If the following code segments are executed, re-draw the linked list.
Listnode newLink = new Listnode (“sang”);
newLink.next = first;
first = newLink;
(2 marks)

b. If the following code segments are executed, re-draw the linked list (from answer a).
Listnode current = first;
Listnode previous = null;
while(current.next != null) {
previous = current;
current = current.next;
}
previous.next = null;
(2 marks)

Page 7 of 8
 Data Structures CS204 Monday, 21 March, 2022

PART C: PROGRAMMING QUESTIONS (5 marks)

Given the following class that describe object movie.

public class Movie {

String title;
int min;

public Film(String t, int s) {

title = t;
min = s;
}
}

Assume array film is declared as: Movie[] film = new Movie[10];. Answer the following
questions.

1. Write the statements that will insert the following movie data into index 5 and index 6: Luca 60;
and Snowhite 35;
(2 marks)
film[5] = new Movie(“Luca”, 60);
film[6] = new Movie(“Snowhite”, 35);

2. Write the statement that will display only the title of all movie.
(3 marks)
for (int i=0; i<10; i++) {
System.out.println(film[i].title);

Page 8 of 8