B.C.A. (Second Semester) 2010
Data Structure (BCA-205)
[2005, 2007, 2008, 2009.]
[Unit 1] Introduction, array, records, stack
1. What is Stack data structure? Where we can use stack data structure? [2005]
2. Explain Record data structure. [2005]
3. Write a pseudo code to remove duplicity of an element. [2005]
4. What is data structure? Explain different types of data structures along with their different operations that can be performed on that particular data structure? Also give one application of each, at least? [2005] [2008.1]
5. What is Linear Array? How it is represented in memory? [2005]
6. Explain how a postfix expression can be evaluated using a stack? Write algorithm for evaluating postfix expression. [2005]
7. Write algorithm for PUSH and POP operation on stack. [2005] [2007.3] [2008.2]
8. What do you mean by recursion? Which data structure is responsible for implementation of recursion? Explain in detail. [2005] [2007.1] [2008.2]
9. Explain polish notation and reverse polish notation with examples. [2005]
10. What do you understand by dynamic memory allocation? [2007]
11. Differentiate between array and record. [2007]
12. How are 2 dimensional arrays represented in memory? Also explain how the memory address of array elements determined. [2007]
13. Write an algorithm to check weather a given matrix is unit or not. [2007]
14. Write a recursive procedure to print n^{th} term of Fibonacci series. [2007]
15. Write an algorithm to reverse a string using stack. [2007]
16. Write a recursive procedure to print n^{th} term of Fibonacci series. [2008]
17. Write postfix expression of the following. Also write their prefix expression.
i) ( A – B ) * ( D / E )
ii) ( A + B ^ D ) / ( E – F ) + G
iii) A * ( B + D ) / E – F * ( G + H / K )
iv) ( ( A + B ) / D ^ ( ( E – F ) * G )
v) ( A – B ) / ( ( D + E ) * F )
18. What is memory allocation strategy? [2009]
19. Define infix, prefix and postfix notations giving examples of each.
20. Explain various applications of stack. [2008]
[Unit 2] Queues
1. Write a pseudo code for a function which returns TRUE, when QUEUE is full. And explain how queue is implemented using array. [2005]
2. What is circular queue? Write pseudo code to implement circular queue using array. [2005] [2007.1]
3. What is queue? How queues are represented in computer? Explain in detail. [2005]
4. Write an algorithm for inserting and deleting element in circular queue. [2007] [2008.3]
5. How queue is different from stack? Explain with the help of example. [2007]
6. What are the advantages of circular queue over simple queue? [2008]
7. Explain array representation of stack and queues. [2009]
[Unit 3]
Linked List
1. Compare singly and doubly linked List. [2005][2007.7]
2. What is difference between array and linked list? [2005]
3. What is Linked List? How a linked list is represented in memory. [2005]
4. What is circular linked list? Write an algorithm to insert a node before any specified node in a circular linked list. [2005]
5. Write an algorithm to search for an element in a ordered linked list. [2007]
6. Write an algorithm to print all elements in a circular linked list.
7. Suppose LIST is a linked list in memory consisting of numerical values. Write a procedure for each of the following.
i) Finding the maximum MAX of the values in the list.
ii) Finding the average of the values in the list. [2008]
8. Explain implementation of stack using linked list. [2008]
9. Explain various applications of linked list. [2009]
10. Discuss the Linked List and write a procedure for inserting an item in the list. [2009]
[Unit 4] Trees
1. Explain Linked List representation of Binary Tree. Write an algorithm to insert a node in a binary tree. [2005]
2. Give different tree traversal methods. What is advantage of Inorder traversal of tree? [2005] [2007] [2008]
3. Define leaf node, root node and level in a binary Tree.
12 |
9 |
20 |
11 |
18 |
Insert 10 and 30 in above binary search tree. [2005]
4. Write an algorithm to convert infix expression to postfix expression. [2007]
5. Create a binary search tree from the elements given below.
15, 10, 12, 7, 20, 25, 1, 19, 3, 4 [2007]
M |
F |
R |
B |
I |
L |
P |
6. Give the inorder, preorder and postorder traversal of the tree below.
A |
B |
G |
C |
D |
J |
I |
E |
K |
C |
H |
7. What is the difference between binary tree and binary search tree? [2008]
8. Generate binary search tree from the elements given below.
14, 10, 17, 12, 10, 11, 20, 12, 18, 25, 20, 8, 22, 11, 23. [2008]
9. Explain linear representation of binary tree. [2008]
10. Write preorder, inorder, postorder tree traversal. [2008] [2009]
11. What is complete binary tree? How it is different from binary tree? [2009]
[Unit 5] Graphs
1. How graphs are implemented in computer memory? Explain. [2005][2009][2009.8]
2. What is graph? What are its uses? [2005]
3. Explain in detail Breadth First Search (BFS) and Depth First Search (DFS). [2005] [2007.9][2008.7][2009.1]
4. Explain in detail Directed and Undirected Graph. [2005][2009.1]
5. Define path in graph and complete graph. [2007]
6. What is adjacency matrix? [2008]
7. Determine whether the graph Q and H are isomorphine through adjancency matrix.
8. What is spanning tree? [2008] [2009.7]
[Unit 6] Searching and sorting
1. Write down different sorting methods? Give the efficiency expression of each. [2005]
2. What are different searching methods available? Give the maximum number of comparison in each case. [2005]
3. What do you understand by hashing and hash function? [2005] [2007.4] [2008.1][2009.1]
5. What do you mean by internal and external sorting? Explain. [2005] [2007.7]
6. Explain insertion sorting technique? Write and algorithm for insertion sort. [2005]
7. How collisions are handled in hashing? [2005]
8. Differentiate between linear and binary search. [2007]
9. Explain selection sorting and discuss its efficiency. [2007]
10. Explain Binary Search method. [2007]
11. Explain quick sort and write its algorithm. [2008]
12. Write bubble sort algorithm with example. [2208]
13. Explain binary search. Write a recursive function in C to perform binary search. [2009]
14. Explain between complexities and comparison and selection sort. [2009]
15. What do you understand by garbage collection? [2008][2009.7]
16. What is analysis of algorithm? [2008]
17. Write a pseudo code to find Greatest Common Divisor (GCD) of two numbers. [2005]
18. What is the difference between local and global variables? [2009]