BSc.CSIT 3rd Semester Data Structure and Algorithms Old Questions

BSc.CSIT 3rd Semester Old Questions

Subject: Data Structure and Algorithms

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

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

1. What do you mean by binary tree? Explain the binary search tree with example.
2. What do you mean by recursion? Explain the implementation of factorial and Fibonacci sequences
   with example.
3. Explain the implementation of stack and queue with example.
   Section B

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

4. What are the difference between two dimension array and multidimension array?
5. What are the major characteristics of algorithms?
6. How can you convert from infix to post fix notation?
7. How can you use Queue as ADT?
8. What is Post-order traversal?
9. What is sorting? Describe the Insertion.
10. Explain the binary searching.
11. Differentiate between Pre-order and In order traversal.
12. Explain the tower of Hanoi algorithm.
13. 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)

1. Write a menu program to demonstrate the simulation of stack operations in array implementation.
2. 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.
3. 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)

4. 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‟);

5. “To write an efficient program, we should know about data structures.” Explain the above
   statement.
6. Write C function to display all the items in a circular queue in array implementation. Write
   assumptions, you need.
7. Explain Divide and Conquer algorithm taking reference to Merge Sort.

8. Trace Binary Search algorithm for the data:
   21, 36, 56, 79, 101, 123, 142, 203
   And Search for the values 123 and 153.
9. Differentiate between tree and graph. What are spanning forest and spanning tree. Explain MST
   (Minimum cost Spanning Tree) problem.
10. 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
11. Explain the use of Big O notation in analyzing algorithms. Compare sorting time efficiencies of
    Quick-Sort and Merge-Sort.
12. Explain CLL, DLL, DCLL (Circular, Doubly, Doubly Circular Linked List).
13. 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)

1. Define stack as ADT. Describe its primitive operations on Array implementation and linked list
   implementation.
2. Describe properties of Binary Search Tree. Write recursive algorithms for constructing BST and its traversals.
   Illustrate them with an example.
3. 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)

4. Write recursive algorithm to get Fibonacci term. Illustrate it drawing recursion tree.
5. Construct an expression tree from the following postfix:
   AB + C*DC – -FG + $
6. Differentiate between Singly linked list, DLL, CLL and DCLL.
7. Describe circular Queue operations in array implementation.
8. Compare and Contrast between Binary searching and Binary tree searching.
9. State collision resolution techniques in hashing. Explain double hashing and quadratic probing techniques.
10. State MST (Minimum Cost Spanning Tree) problem and shortest path (single source and all other
    destination) problem. Name the algorithms for solving these problems.
11. Justify the statement: “To write an efficient program, we should know about data structures and
    algorithms”.
12. Discuss the merits and demerits of contiguous list and linked list.
13. 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:

1. Define Queue as an ADT. Write a program for basic operations in Linear queue in array implementation.
2. 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.
3. 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)

4. Explain Kruskal’s algorithm with example.
5. Write a program in C for bubble sorting.
6. Differentiate between contiguous list and linked list with examples.
7. Explain binary search. Illustrate it with example.
8. Explain hashing with example.
9. Explain why linked list is called dynamic list? Write the algorithm for deleting a new node before a node.
10. Explain the characteristics of Huffman’s algorithm and its application.
11. Write merits and demerits of recursive function over non-recursive function.
12. Write the steps involved in deleting a node in a Binary selection tree.
13. 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:

1. Define Queue as ADT. Describe its primitive operation on array implementation and linked list
   implementation.
2. 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.
3. 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)

4. State TOH problem. Write recursion tree when no. of disks are four.
5. Write about applications of Binary trees.
6. Compare partition strategies of Merge sort and Quick sort.
7. Explain Bubble sort algorithm. Illustrate it with an example.
8. How do you insert a nodes at last in doubly linked list? Explain.
9. Describe recursive procedure of Binary searching technique? Discuss about efficiency of Binary searching.
10. What are Hashing and collision? Write about any three hashing algorithms.
11. What is Big ‘O’ notation? Analyze any one sorting algorithm.
12. Describe strong and weekly connected graphs with examples. What is weighted graph?
13. 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:

1. 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.
2. 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.
3. 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)

4. Write C function to insert an item circular queue in array implementation. Write assumptions, you need.
5. What is an algorithm? What is to analyze in algorithm? Define Big C = Oh notation for time complexity
   measurement of algorithm.
6. State TOH problem. Explain a recursive algorithm to solve the problem.
7. Trace selection – sort algorithm for the following data:
   42, 23, 74, 11, 65, 58, 94, 86
8. What is Hashing? What collision means? State collision resolution techniques. Explain one of them in brief.
9. What is weighted graph? Explain Depth-first traversal of a graph.
10. 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:

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

Section (B)

Attempt any eight questions:

(8×5=40)

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

16 7 31 2 9 41 -10

13. 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)

1. What is binary search tree? Explain with an example. Write an algorithm to search, insert and delete node in
   binary search tree.
2. 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) + −
3. What is circular queue? Write an algorithm and C function to implement Circular queue.

Section B

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

4. What is Recursion? Write a recursive algorithm to implement binary search.
5. Differentiate between array and pointer with example.
6. What is an algorithm? Write down the features of an algorithm.
7. How stack as ADT? Explain with example.
8. Write an algorithm and C function to delete node in singly link list.
9. Write an algorithm and C function for merge sort.
10. What do you mean by graph traversal? Explain primes algorithm with example.
11. Differentiate between selection sort and bubble sort.
12. Write an algorithm to implement tower of Hanoi.
13. Write short notes on
    a) Hashing
    b) Doubly Link list