## BSc.CSIT 3rd Semester Old Questions

## Subject: Data Structure and Algorithms

- Subject: Data Structure and Algorithms
- Year: 2065 B.Sc.CSIT 3rd Semester Data Structure and Algorithms Old Questions
- B.Sc.CSIT 3rd Semester Data Structure and Algorithms Old Questions of Year : 2066
- B.Sc.CSIT 3rd Semester Data Structure and Algorithms Old Questions of Year : 2067
- Year : 2068 B.Sc.CSIT 3rd Semester Data Structure and Algorithms Old Questions
- B.Sc.CSIT 3rd Semester Data Structure and Algorithms Old Questions of Year : 2069
- Year : 2070 B.Sc.CSIT Data Structure and Algorithms Old Questions
- Year : 2071 B.Sc.CSIT 3rd Semester Old Questions
- Year : 2072 Old Questions of B.Sc.CSIT 3rd Semester Data Structure and Algorithms

### Year: 2065 B.Sc.CSIT 3rd Semester Data Structure and Algorithms Old Questions

Attempt any TWO questions: (10×2=20)

- What do you mean by binary tree? Explain the binary search tree with example.
- What do you mean by recursion? Explain the implementation of factorial and Fibonacci sequences

with example. - Explain the implementation of stack and queue with example.

Section B

Attempt any EIGHT questions: (8×5=40)

- What are the difference between two dimension array and multidimension array?
- What are the major characteristics of algorithms?
- How can you convert from infix to post fix notation?
- How can you use Queue as ADT?
- What is Post-order traversal?
- What is sorting? Describe the Insertion.
- Explain the binary searching.
- Differentiate between Pre-order and In order traversal.
- Explain the tower of Hanoi algorithm.
- Explain the Kruskal‟s algorithm.

### B.Sc.CSIT 3rd Semester Data Structure and Algorithms Old Questions of Year : 2066

Attempt any TWO questions. (10×2=20)

- Write a menu program to demonstrate the simulation of stack operations in array implementation.
- State relative merits and demerits of contiguous list and Linked list. Explain the steps involved in

inserting and deleting a mode in singly linked list. - A binary tree T has 12 nodes. The in-order and pre-order traversals of T yield the following

sequence of nodes:

In-order : VPNAQRSOKBTM

Pre-order : SPVQNARTOKBM

Construct the Binary tree T showing each step. Explain, how you can arrive at solution in brief?

Section B

Attempt any EIGHT questions. (8×5=40)

- Consider the function:

Void transfer (int n, char from, char to, char temp)

{ if (n > 0)

{ transfer ( n – 1, from, temp, to_;

Print if ( “In Move Disk % d from % C to % C” N, from, to);

Transfer ( n – 1, temp, to, from);

}

Trace the output with the function Cell!

Transfer ( 3, „R‟, „L‟, „C‟);

- “To write an efficient program, we should know about data structures.” Explain the above

statement. - Write C function to display all the items in a circular queue in array implementation. Write

assumptions, you need. - Explain Divide and Conquer algorithm taking reference to Merge Sort.

- Trace Binary Search algorithm for the data:

21, 36, 56, 79, 101, 123, 142, 203

And Search for the values 123 and 153. - Differentiate between tree and graph. What are spanning forest and spanning tree. Explain MST

(Minimum cost Spanning Tree) problem. - A file contains 100 symbols in which following character with their probability of occurrence.

Build a Huff man tree according to Greedy Strategy.

a 48

b 11

c 9

d 14

e 7

f 11 - Explain the use of Big O notation in analyzing algorithms. Compare sorting time efficiencies of

Quick-Sort and Merge-Sort. - Explain CLL, DLL, DCLL (Circular, Doubly, Doubly Circular Linked List).
- Write Short notes on (any two):

a) Hash function

b) External Sorting

c) ADT.

### B.Sc.CSIT 3rd Semester Data Structure and Algorithms Old Questions of Year : 2067

Attempt any two questions. (2×10=20)

- Define stack as ADT. Describe its primitive operations on Array implementation and linked list

implementation. - Describe properties of Binary Search Tree. Write recursive algorithms for constructing BST and its traversals.

Illustrate them with an example. - What are external and internal sorting? Explain partition strategies of Merge sort and Quick sort.

Trace these sort algorithms for following data:

11 45 61 33 55 9 83 25

Section B

Attempt any eight questions. (8×5=40)

- Write recursive algorithm to get Fibonacci term. Illustrate it drawing recursion tree.
- Construct an expression tree from the following postfix:

AB + C*DC – -FG + $ - Differentiate between Singly linked list, DLL, CLL and DCLL.
- Describe circular Queue operations in array implementation.
- Compare and Contrast between Binary searching and Binary tree searching.
- State collision resolution techniques in hashing. Explain double hashing and quadratic probing techniques.
- State MST (Minimum Cost Spanning Tree) problem and shortest path (single source and all other

destination) problem. Name the algorithms for solving these problems. - Justify the statement: “To write an efficient program, we should know about data structures and

algorithms”. - Discuss the merits and demerits of contiguous list and linked list.
- What is priority queue? How it is best implemented?

### Year : 2068 B.Sc.CSIT 3rd Semester Data Structure and Algorithms Old Questions

Attempt any two questions:

- Define Queue as an ADT. Write a program for basic operations in Linear queue in array implementation.
- Why recursion is required? Explain with Tower-of-Hanoi example. How recursive algorithm makes program

effective? Write the merits and demerits of recursion in Programming. - Explain In-fix to Postfix Conversion Algorithm. Illustrate it with an example. What changes should be made for

converting postfix to prefix.

Section B

Attempt any eight questions: (8×5=40)

- Explain Kruskal’s algorithm with example.
- Write a program in C for bubble sorting.
- Differentiate between contiguous list and linked list with examples.
- Explain binary search. Illustrate it with example.
- Explain hashing with example.
- Explain why linked list is called dynamic list? Write the algorithm for deleting a new node before a node.
- Explain the characteristics of Huffman’s algorithm and its application.
- Write merits and demerits of recursive function over non-recursive function.
- Write the steps involved in deleting a node in a Binary selection tree.
- Discuss merge sort. How you rate this sorting from selection sort?

### B.Sc.CSIT 3rd Semester Data Structure and Algorithms Old Questions of Year : 2069

Attempt any two questions:

- Define Queue as ADT. Describe its primitive operation on array implementation and linked list

implementation. - Describe the significance of Huffman tree. Describe procedure for construction of a Huffman tree. Illustrate

it with example. Describe different types of applications of Binary trees. - Explain the algorithms for infix to postfix conversion and evaluation of postfix expression. Trace the

algorithms with suitable example.

Section (B)

Attempt any eight questions:

(8×5=40)

- State TOH problem. Write recursion tree when no. of disks are four.
- Write about applications of Binary trees.
- Compare partition strategies of Merge sort and Quick sort.
- Explain Bubble sort algorithm. Illustrate it with an example.
- How do you insert a nodes at last in doubly linked list? Explain.
- Describe recursive procedure of Binary searching technique? Discuss about efficiency of Binary searching.
- What are Hashing and collision? Write about any three hashing algorithms.
- What is Big ‘O’ notation? Analyze any one sorting algorithm.
- Describe strong and weekly connected graphs with examples. What is weighted graph?
- State relative merits & demerits of contiguous list and linked list.

### Year : 2070 B.Sc.CSIT Data Structure and Algorithms Old Questions

Attempt any two questions:

- Trace out Infix to Postfix conversion algorithm with given Infix expression.

A + (((B-C) * (D-E) + F)/G) $ (H-I)

Evaluate the postfix expression acquired from above for the given values:

A = 6, B = 2, C = 4, D = 3, E = 8, F = 2, G = 3, H = 5, I = 1. - Explain the structure of Doubly Linked List (DLL). Differentiate the difference between DLL and Doubly Circular

Linked List (DCLL). Explain the procedures to insert a node in DLL at the beginning and at the last. - Define Binary Search Type (BST). Write an algorithm to insert a node in non-empty BST. Construct BST from

the data:

10, 20, 30, 25, 27, 7, 4, 23, 26, 21.

Section B

Attempt any eight questions: (5×8=40)

- Write C function to insert an item circular queue in array implementation. Write assumptions, you need.
- What is an algorithm? What is to analyze in algorithm? Define Big C = Oh notation for time complexity

measurement of algorithm. - State TOH problem. Explain a recursive algorithm to solve the problem.
- Trace selection – sort algorithm for the following data:

42, 23, 74, 11, 65, 58, 94, 86 - What is Hashing? What collision means? State collision resolution techniques. Explain one of them in brief.
- What is weighted graph? Explain Depth-first traversal of a graph.
- Create a Huffman tree for the following set of data:

Characters a b c d e f

Probability 48 13 11 16 07 05

Encode 0 101 100 111 1101 1100

### Year : 2071 B.Sc.CSIT 3rd Semester Old Questions

Attempt any two questions:

- What is stack? How is it different from queue? Write a program to implement all stack operations.
- What is linked list? Explain the process of inserting and removing nodes from a linked list.
- What is graph traversal? Discuss depth-first traversal technique with suitable example.

Section (B)

Attempt any eight questions:

(8×5=40)

- Discuss array as an ADT.
- Transform the postfix expression AB − C + DEF − + $ to infix.
- What is recursion? Write a recursive program to find factorial of a number.
- Explain almost complete binary tree with example.
- Write a program to sort an array using selection sort.
- Discuss binary search technique along with its efficiency.
- Why do we need Hashing? Discuss linear probing in detail.
- How to find complexity of algorithms? Explain.
- Hand test the insertion sort algorithm with following array of numbers.

16 7 31 2 9 41 -10

- Write short notes on:

a. Tree traversal

b. Circular queue

### Year : 2072 Old Questions of B.Sc.CSIT 3rd Semester Data Structure and Algorithms

Attempt any TWO questions: (2×10=20)

- What is binary search tree? Explain with an example. Write an algorithm to search, insert and delete node in

binary search tree. - What is Postfix expression? Write an algorithm to evaluate value of postfix expression. Trace the following

expression into postfix expression.

(A+B*C) D E/ F) + − - What is circular queue? Write an algorithm and C function to implement Circular queue.

Section B

Attempt any EIGHT questions: (8×5=40)

- What is Recursion? Write a recursive algorithm to implement binary search.
- Differentiate between array and pointer with example.
- What is an algorithm? Write down the features of an algorithm.
- How stack as ADT? Explain with example.
- Write an algorithm and C function to delete node in singly link list.
- Write an algorithm and C function for merge sort.
- What do you mean by graph traversal? Explain primes algorithm with example.
- Differentiate between selection sort and bubble sort.
- Write an algorithm to implement tower of Hanoi.
- Write short notes on

a) Hashing

b) Doubly Link list