Data structure and Algorithm

Prime College
Presemester  Examination -2013
Time: 3 hours
Full Marks: 60
 Pass Marks: 24

       Set-A

   Candidates are required to answer the question in their own words as far as possible
Group-A
Long answer Question: (Any Two) [2x10=20]
1. Define list, circular linked list, and doubly linked list. What are the advantages of doubly linked list? How doubly linked list is represented in C language? Write an algorithm to insert a new node at the end of the doubly linked list.
2. What is a stack? What are the applications of stack data structure? Write an algorithm to evaluate the postfix notation.
3. What is an expression tree? Write postorder , preorder and inorder tree traversal algorithms. Construct an expression tree of the given expression and traverse it using   preorder, inorder and postorder algorithm.   (A+B*C)$((A+B)*C)


Group-B
Short answer question (Any Eight) [8x5=40]
4. What are graph applications? Define Graph as ADT.

5. What is searching? Write binary search algorithm with example.
6. Write an algorithm or C function to print all the elements of the singly linked list.
7. What is postfix expression? Convert the given infix expression in  to postfix  (A+B*C)$((A+B)*C)
8. What is recursion? Write an algorithm to solve TOH problem.
9. What is priority queue? Explain unordered array implementation of priority queue.
10. What are the applications of tree data structure? How do you represent binary tree in memory?
11. What is an Array?  Define array as ADT.
12. What is hashing collision? Explain hash collision resolution methods.
13. Explain quick sorting algorithm with example.

*****


Prime College

Presemester  Examination -2013
          Time: 3 hours
       Full Marks: 60
Pass Marks: 24
    Set-B
   Candidates are required to answer the question in their own words as far as possible

Group-A
   Long answer question (Any Two) [2x10=20]
1. What are the applications of stack? Write an algorithm to convert infix expression to postfix expression and then trace the algorithm for the given expression: A+B*C-D/(E+F)
2. What do you mean by binary search tree? Write algorithms to perform search, insertion  and deletion operations in the binary search tree.
3. Define circular queue with an example. What are the advantages of Circular queue over linear queue? Write an algorithm or C function to perform insertion and deletion operations in a circular queue.


Group-B
  Short answer questions (Attempt any Eight Questions) [8x5=40]
4. What is graph? Explain BFS algorithm with example
5. What is a tree? Define tree as ADT.
6. What is recursion? Explain types or recursion.
7. What is list? Write an algorithm or C function to add a new node at the last of a singly linked list.
8. Write an algorithm or C function to count the number of elements in a linear queue.
9. Write an algorithm or C function to Perform push and pop operations on a stack.
10. What is doubly linked list? What are the advantages of doubly linked list over the singly linked  list?
11. What do you mean by expression tree? Explain
12. Write binary search algorithm and it with sequential search.
13. What do you mean by merging? Write merge sort algorithm and illustrate with example.


*****

Pre-Semester Examination-2070

Set A

Bachelor Level/First Year/Second Semester/Science
Digital Logic(CSC-151)
Candidates are required to give their answers in their own words as far as practicable. The figures in the margin indicate full marks.

Long Answer Questions.
Attempt any two questions. ( 2x 10 =20)
1. Design a 4 bit Asynchronous counter using JK Flip Flop. Draw its timing diagram.
2. Design a BCD adder with logical diagram and truth table.
3. Solve the following
F(w,x,y,z)=w’xz +w’yz+x’yz’+wxy’z with don’t care condition as
D (w, x, y, z) =wyz
Reduce given Boolean Expression using K-Map and draw the suitable logic diagram and realize it with NAND gate.
Short Answer Questions.
Attempt any eight questions. (8 x5=40)
1. Given A=29 and B=26  represent them in binary and perform the following operations:
a. A-B (Using r’s complement method)
2. Convert the following as indicated.(i) (630.4) Octal to decimal (ii)(10000101)BCD to binary
3. Draw the circuit diagram of a J-K Flip Flop along with its Truth Table and Characteristic equation.
4. Mention different types of shift registers. Explain SISO in detail.
5. Simplify  and realize the equation using NOR gates only.
6. Design a 2 bit synchronous binary counter using JK Flip Flop. Draw its timing diagram
7. What is DMUX? Explain with circuit diagram of 1 to 4 DMUX.
8. Explain state diagram, state table, state reduction and state assignment with suitable example.
9. Explain Johnson Counter in detail.
10. Explain the terms:
a. Block diagram of Memory unit
b. Fanout
c. reflected code



Pre-Semester Examination-2070

Set B

Bachelor Level/First Year/Second Semester/Science
Digital Logic(CSC-151)
Candidates are required to give their answers in their own words as far as practicable. The figures in the margin indicate full marks.

Long Answer Questions.
Attempt any two questions. ( 2x 10 =20)
1. Design a 4 bit synchronous binary counter using JK Flip Flop. Draw its timing diagram.
2. Solve the following.
F (w, x, y, z) = ∑(1,3,7,11,15)
With don’t care condition as
D (w, x, y, z) = ∑(0,2,5)
Reduce it using K-map and Draw the suitable logic diagram and realize it with NAND gate.
3. What is a magnitude comparator? Explain 4-bit magnitude comparator in detail.
Short Answer Questions.
Attempt any eight questions. (8 x5=40)
1. Given A=36 and B=33  represent them in binary and perform the following operations:
a. A-B (Using (r-1)’s complement)
2. Convert the (23.6875)10 to Binary and to BCD.
3. Write about T flip flop with necessary circuit, block diagram, characteristic table and equation.
4. Simplify  and realize the equation using NOR gates only.
5. Mention different types of shift registers. Explain SIPO with diagram.
6. What is decoder? Describe the 3 to 8 line decoder circuit.
7. Explain state diagram, state table, state reduction and state assignment with suitable example.
8. Design a 2 bit asynchronous binary counter using T Flip Flop. Draw its timing diagram
9. Explain Ring Counter in detail.
10. Explain the terms:
a. Memory cell
b. Propagation delay
c. Error detection codes