Data Structures/Data Structures & Algorithms/Data Structures and Algorithm Msc IT 3 Semester/Term University Of Sargodha (UOS) 2024

" ges ©

University of Sargoqna S00

aii

Subject: L.T Paper: Data Structures g Aleorithms (CMP-3112

Time Allowed: 02:30 Hours Maximum Marks: 60

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

Objective Part \ (Compulsory)

, Rh CR

3 . answer sheet. (2*12)

Q.1. Write short answers of the following in 2-3 ineskec h on RR er sheet

i. Using syntax of java, define structure of a node of oubly linked Ast.

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

|

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

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

a) Tree

b) Circular queue.

v. What is prefix expression of A/B * C § D? (The symbol $ indicates the exponentiation operator).

vi. Write the name of two necessary conditions in recursion?

vii. Which sorting technique that uses the concept of pivot element?

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

7.

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

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

xi. What is special in binary search tree?

xii. What is associativity of assignment operator?

University of Sargodpa 00

M.Sc. 3" Term ExaMinatio, 9024

Vie iinti ¥

Subject: LT Paper: Data Structures & Algorithms (CMP-3112

h

Objective Part (Compulsory)

4 : Bp 2412)

Q.1. Write short answers of the following in'2-3 ineskach S-JOUr SRsUE sheet. y

Using syntax of java, define structure ofa node o oubly linked list.

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

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

v. What is prefix expression of A /B * C $ D? (The symbol § indicates the exponentiation operator).

vii. ~~ Which sorting technique that uses the concept of pivot element?

Subjective Part (3*12)

on that accepts a reference of fist node of a singly linked list and display them recursively

re is no to create a class, Only down the relevant function

b) Write down the function that accepts an array ahd sorts it by using insertion soit

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.

Q4.

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

traversal,

In order traversal: A, H, F, LK, G

Preorder traversal: IL 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.

Q.5.

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

583,013 :

Q.6.

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

(A+B)*(CS(D-E)+F)-G )

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

Ec 1

G01

OE

LK-6449/09-05-24 —.

1