Subject: L.T Time Allowed: 02:30 Hours University of Sargodha M.Sc. 3d Term Examination 2024

Subject: L.T

Time Allowed: 02:30 Hours

University of Sargodha

M.Sc. 3d Term Examination 2024

Paper: Data Structures & Algorithms (CMP-3112)

30610

Maximum Marks: 60

Note: Objective part is compulsory. Attempt any three questions from subjective part.

Q.1.

i.

ii.

iii.

iv.

V.

vi.

vii.

vili.

ix.

X.

XI.

xii.

Q.2.

Q.3.

Objective Part

(Compulsory)

Write short answers of the following in 2-3 lines each on your answer sheet.

Using syntax of java, define structure of a node of doubly linked list.

How many references are usually used to maintain a singly linked list?

What is postfix of A + B - C / D?

Which of the following is a linear or a non-linear data structure?

a) Tree

b) Circular queue.

What is prefix expression of A / B * CS D? (The symbol S indicates the exponentiation operator).

Write the name of two necessary conditions in recursion?

Which sorting technique that uses the concept of pivot element?

How many leaves are there in a strictly binary tree if total number of nodes are

7.

What is height of a node in a binary tree? Give an example.

In which sorting algorithms there are more number of swaps? Selection or Bubble.

What is special in binary search tree?

What is associativity of assignment operator?

(2*12)

Subjective Part (3*12)

a) Write a function that accepts a reference of first node of a singly linked list and display them recursively

Note: there is no need to create a class. Only write down the relevant function.

b) Write down the function that accepts an array and sorts it by using insertion sort

Traverse the following graph using BFS and DFS in ascending alphabetical order. (that is node B should be

traversed before node

C). Take start from node A.

Q.4.

a) A binary tree has following in order and pre order traversal. Make the tree and write down its post order

Q.5.

Q.6.

traversal.

In order traversal: A, H, F, 1, K, G

Preorder traversal: 1, H, K, F, G, A

b) Write down a recursive function that finds sum of first ten odd numbers.

Note: Only write the recursive function and don't write the complete class.

a) Suppose there are six keys with numbers as 21, 56, 8, 10, 18 and 2 and four hash addresses available. Try to

accommodate them in available slots using chaining technique if collision takes place where h(k) - key % 3

b) Create a max heap from following data

5, 8, 3, 6, 1, 3

a) Convert the following infix expression to postfix expression using stack.

(A +

B) * (C $ (D -

E) +

F) - G

b) Draw a picture of the directed graph that has following adjacency list representation.

- LK-6449/09-05-24