Data Structure and Algorithm and microprocessor

Bernhardt College

Subject: Data Structure and Algorithm      

[Question Set-A]                              

Full Marks: 60

                                                                                                                        Pass Marks: 24

Time: 3 hours

Candidates are required to give their answers in their own words as for as practicable.

Section A

Attempt any TWO questions: (10x2=20)

1.      Write the Dijkstra’s algorithm for calculating the shortest path between two nodes in a graph. Give suitable example to apply Dijkstra’s algorithm to calculate the shortest path.

2.      Define recursion. Write a recursive function to calculate Factorial and Fibonacci number.

3.      Define stack as ADT. Write a menu driven program to demonstrate the simulation of stack operations in array implementation.

Section B

Attempt any EIGHT questions: (8x5=40)

4.      Explain the use of big Oh notation in analyzing algorithm? Write short note on Best, Worst, and Average-Case Complexity of an algorithm.

5.      Distinguish between stack and queue with suitable example.

6.      Explain hashing, hash collision, and state hash collision resolution techniques.

7.      Define searching. Write an algorithm to create binary search tree.

8.      Trace Merge sort algorithm on the following data and discuss about the case complexity.

      7, 2, 1, 8, 43, 4, 3, 11, 9, 23, 6, 2

9.      Explain CLL, DLL, DCLL (Circular, Doubly, Doubly Circular Linked List).

10.  Explain Divide and Conquer algorithm taking reference to Quick Sort.

11.  Write a program in C to implement recursive function for binary search.

12.  Discuss the Huffman encoding and decoding technique with suitable example.

13.  Write short notes on any two

a.       Applications of tree data-structure

b.      External and internal sorting

c.       Breadth First Search (BFS)

Bernhardt College

Subject: Data Structure and Algorithm      [Question Set-B]                              

Full Marks: 60

                                                                                                                        Pass Marks: 24

Time: 3 hours

Candidates are required to give their answers in their own words as for as practicable.

Section A

Attempt any TWO questions: (10x2=20)

1.      Write short notes on the Kruskal’s algorithm to construct Minimum cost Spanning Tree. Give suitable example to explain the algorithm

2.      Define recursion. Write a recursive function to calculate Factorial and Fibonacci number.

3.      State relative merits and demerits of contiguous list and Linked list. Explain the steps involved in inserting and deleting a node in singly linked list.

Section B

Attempt any EIGHT questions: (8x5=40)

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

5.      Define hashing, hash function and hash collision. State collision resolution techniques in hashing.

6.      Trace Quick sort algorithm on the following data and discuss about the case complexity.

      7, 2, 1, 8, 43, 4, 3, 11, 9, 23, 6, 2

7.      State TOH problem. Explain the Tower of Hanoi Algorithm (TOH).

8.      Explain CLL, DLL, DCLL (Circular, Doubly, Doubly Circular Linked List).

9.      Define binary tree? Draw a binary Tree for the expression : A * B - (C + D) * (P / Q)

10.  Explain Divide and Conquer algorithm taking reference to Merge sort.

11.  Discuss the Huffman encoding and decoding technique with suitable example.

12.  Write a function for selection sort and discuss about the case complexity.

13.  Write short notes on any two

a.       Abstract Data Type (ADT)

2. AVL balanced tree
3. Complete binary tree

Bernhardt College

Subject:microprocessor

Group A

1. Draw an architecture of SAP-2 and explain its components.Compare SAP-2 with SAP-1.

2. Explain different types of addressing modes with examples.

3. Ten byte of data are stored from address starting from 3000h.Transfer the datas to location starting from 4000h only if its bits A6 and A3 are reset.Write all necessary steps

Group B

4. Draw an architecture of Vonneumann computer system and explain its components.

5. What is instruction format?Explain three types of instruction format with examples.

6. Draw a timing diagram of instruction:MOV B,C

7. Write an  8- bit assembly language program to print Fibonacci series.

8. What is flag ?Explain 5 types of flag used in 8086.

9. Compare between 8085 microprocessor and 8086 microprocessor.

10. What is interrupt?what are the stpes in  interrupt processing.

11. What is DMA ?list its features and draw a timing of diagram of DMA.

12. Write an assembly language program to print string”The programming part of microprocessor is very difficult”

13. What is 8251?Draw its block diagram and explain each components.