B.Tech 2nd Year CSE student can download the Question Bank from this Link.
1. What is data structure?
Ans: The logical and mathematical model of a particular organization of data is called data structure. There are two types of data structure
i) Linear
ii) Nonlinear
2. What are the goals of Data Structure?
Ans: It must rich enough in structure to reflect the actual relationship of data in real world.
The structure should be simple enough for efficient processing of data.
3. What is the difference between a Stack and an Array?
Ans:
i) Stack is a ordered collection of items
ii) Stack is a dynamic object whose size is constantly changing as items are pushed and popped .
iii) Stack may contain different data types
iv) Stack is declared as a structure containing an array to hold the element of the stack, and an integer to indicate the current stack top within the array.
ARRAY
i) Array is an ordered collection of items
ii) Array is a static object i.e. no of item is fixed and is assigned by the declaration of the array
iii) It contains same data types.
iv) Array can be home of a stack i.e. array can be declared large enough for maximum size of the stack.
4. What do you mean by recursive definition?
Ans: The definition which defines an object in terms of simpler cases of itself is called recursive definition.
5. What is sequential search?
Ans: In sequential search each item in the array is compared with the item being searched until a match occurs. It is applicable to a table organized either as an array or as a linked list.
6. What actions are performed when a function returns?
Ans:
i) Return address is retrieved
ii) Function’s data area is freed
iii) Branch is taken to the return address
7. What is a linked list?
Ans: A linked list is a linear collection of data elements, called nodes, where the linear order is given by pointers. Each node has two parts first part contain the information of the element second part contains the address of the next node in the list.
8. What are the advantages of linked list over array (static data structure)?
Ans:
The disadvantages of array are
i) unlike linked list it is expensive to insert and delete elements in the array
ii) One can’t double or triple the size of array as it occupies block of memory space.
In linked list
i) each element in list contains a field, called a link or pointer which contains the address of the next element
ii) Successive element’s need not occupy adjacent space in memory.
9. What are the major data structures used in the following areas : network data model & Hierarchical data model.
Ans:
RDBMS – Array (i.e. Array of structures)
Network data model – Graph
Hierarchical data model – Trees
10. If you are using C language to implement the heterogeneous linked list, what pointer type will you use?
Ans: The heterogeneous linked list contains different data types in its nodes and we need a link, pointer to connect them. It is not possible to use ordinary pointers for this. So we go for void pointer. Void pointer is capable of storing pointer to any type as it is a generic pointer type.
11. Minimum number of queues needed to implement the priority queue?
Ans: Two. One queue is used for actual storing of data and another for storing priorities.
12. What is the data structures used to perform recursion?
Ans: Stack. Because of its LIFO (Last In First Out) property it remembers its ‘caller’ so knows whom to return when the function has to return. Recursion makes use of system stack for storing the return addresses of the function calls.
Every recursive function has its equivalent iterative (non-recursive) function. Even when such equivalent iterative procedures are written, explicit stack is to be used.
13. What are the notations used in Evaluation of Arithmetic Expressions using prefix and postfix forms?
Ans: Polish and Reverse Polish notations.
14. Convert the expression ((A + B) * C – (D – E) ^ (F + G)) to equivalent Prefix and Postfix notations.
Ans: Prefix Notation:
^ – * +ABC – DE + FG
Postfix Notation:
AB + C * DE – – FG + ^
15. Sorting is not possible by using which of the following methods?
(a) Insertion
(b) Selection
(c) Exchange
(d) Deletion
Ans: (d) Deletion.
Using insertion we can perform insertion sort, using selection we can perform selection sort, using exchange we can perform the bubble sort (and other similar sorting methods). But no sorting method can be done just using deletion.
16. List out few of the Application of tree data-structure?
Ans:
The manipulation of Arithmetic expression,
Symbol Table construction,
Syntax analysis.
17. List out few of the applications that make use of Multilinked Structures?
Ans: Sparse matrix, Index generation.
18. in tree construction which is the suitable efficient data structure?
(A) Array (b) Linked list (c) Stack (d) Queue (e) none
Ans: (b) Linked list
___________________________________________________________________________
Ans:
RDBMS – Array (i.e. Array of structures)
Network data model – Graph
Hierarchical data model – Trees
10. If you are using C language to implement the heterogeneous linked list, what pointer type will you use?
Ans: The heterogeneous linked list contains different data types in its nodes and we need a link, pointer to connect them. It is not possible to use ordinary pointers for this. So we go for void pointer. Void pointer is capable of storing pointer to any type as it is a generic pointer type.
11. Minimum number of queues needed to implement the priority queue?
Ans: Two. One queue is used for actual storing of data and another for storing priorities.
12. What is the data structures used to perform recursion?
Ans: Stack. Because of its LIFO (Last In First Out) property it remembers its ‘caller’ so knows whom to return when the function has to return. Recursion makes use of system stack for storing the return addresses of the function calls.
Every recursive function has its equivalent iterative (non-recursive) function. Even when such equivalent iterative procedures are written, explicit stack is to be used.
13. What are the notations used in Evaluation of Arithmetic Expressions using prefix and postfix forms?
Ans: Polish and Reverse Polish notations.
14. Convert the expression ((A + B) * C – (D – E) ^ (F + G)) to equivalent Prefix and Postfix notations.
Ans: Prefix Notation:
^ – * +ABC – DE + FG
Postfix Notation:
AB + C * DE – – FG + ^
15. Sorting is not possible by using which of the following methods?
(a) Insertion
(b) Selection
(c) Exchange
(d) Deletion
Ans: (d) Deletion.
Using insertion we can perform insertion sort, using selection we can perform selection sort, using exchange we can perform the bubble sort (and other similar sorting methods). But no sorting method can be done just using deletion.
16. List out few of the Application of tree data-structure?
Ans:
The manipulation of Arithmetic expression,
Symbol Table construction,
Syntax analysis.
17. List out few of the applications that make use of Multilinked Structures?
Ans: Sparse matrix, Index generation.
18. in tree construction which is the suitable efficient data structure?
(A) Array (b) Linked list (c) Stack (d) Queue (e) none
Ans: (b) Linked list
___________________________________________________________________________
Introduction
Short
Questions:-
1. Define data
structure.
2. Define algorithm.
3. List out areas in
which data structures are applied.
4. List out structure
of algorithm.
5. List out properties
of algorithm.
6. List out the steps
involved in the development of an algorithm.
7. Define Data Type.
8. List out the
classification of data structure.
9. What is
linear/primitive data structure?
10. What is
non-linear/non-primitive data structure?
11. Gives the names of
linear data structure.
12. Gives the names of
non-linear data structure.
13. Which are the
operations performed on data structure?
14. How to measure the
performance of algorithm?
15. What is time
complexity?
16. Define space
complexity.
17. When empirical
testing is used?
18. What is the use of
theoretical testing?
19. What is average,
best and worst case complexity?
20. Define O notation
of time complexity.
21. List out the
notation that used to express time complexity of algorithm.
Long
Questions:-
1. Explain the
classification of data structure.
2. Explain various
operations performed on data structures.
3. Write a short note
on abstract data type.
4. Explain the
properties of algorithm.
5. Explain the steps
for the development of algorithm.
6. Differentiate
between linear and non-linear data structure.
7. What do you mean by
algorithm? Give example.
8. Explain efficiency
of algorithm.
9. Write a short note
on asymptotic notations.
10. Distinguish between
best, worst and average case complexities of an algorithm.
11. What do you mean by
Time and Space complexity and how to represent these complexity?
12. Explain the concept
of data type.
13. Find the complexity
of following code.
for (int i = 0; i < n; i++) {
for(int j=I;j<n;j++)
printf(“%d”,j);
}
Arrays
Short
Questions:-
1. Define array.
2. List out application of Array.
3. Which operation is supported by an array
ADT?
4. What will happen in a C++ program when
you assign a value to an array element whose subscripts exceed the size of
array?
5. What is the index number of the last
element of an array with 20 elements?
6. List out the operations performed on
Array.
7. Give the number of elements in array
a[1:5].
8. Give the number of elements in array
a[1:5,1:4,1:3].
9. Give the number of elements in array
A[3][2].
10. What is row major order?
11. What is column major order?
12. Write formula to calculate address of
elements in one-dimensional array.
13. Write formula to calculate address of
elements in two-dimensional array.
14. Write formula to calculate address of
elements in three-dimensional array.
15. Define sparse matrix.
16. Define order-list matrix.
17. If the starting address of array a[-2,23]
is 100 then what will be the address of 16th element?
18. If the starting address of array
a[1:5,1:6] is 100 then what will be the address of a[3,4] element?
19. If the starting address of array
a[1:5,1:6,1:4] is 100 then what will be the address of a[3,4,5] element?
20. Write any one difference between row
major and column major.
21. What are the disadvantages of array?
Long
Questions:-
1. What is an array? Which operations can be
performed on Array? Explain with example.
2. How to calculate number of elements in
one dimensional array? Explain with example.
3. How to calculate number of elements in
two dimensional arrays? Explain with example.
4. How to calculate number of elements in
three dimensional arrays? Explain with example.
5. Explain one-dimensional array. How one
dimensional array can be represented in memory?
6. Explain two-dimensional array. How two
dimensional arrays can be represented in memory?
7. Explain three-dimensional array. How
three dimensional arrays can be represented in memory?
8. Explain any one method to calculate
memory location for different position in two-dimensional array.
9. What are the applications of an array?
Explain each with examples.
10. Explain sparse matrix. What are the
benefits of the sparse matrix?
11. Explain order-list matrix. What are the
benefits of the order-list matrix?
12. Write an algorithm for insert and delete
operation in array.
13. Write an algorithm to implement sparse
matrix.
14. Write an algorithm to search element in
array.
15. Write program to insert element at
position of user choice.
16. For the following array A, compute
a.
the
dimension of A
b.
the space
occupied by A in the memory
c.
the address
of A[7,2]
Array: A
Column Index: 0:5
Base address: 100 Size of memory
location: 4 bytes
Row Index: 0:15
17. Distinguish between the row major and
column major ordering of an array.
18. Suppose A is linear array with n numeric
values. Write procedure which finds the average of the values in A.
19. Write a program to find second highest
value from array elements.
20.
Write a
program to delete an element of array at position of user choice.
Stack and
Queue
Short
Questions:-
1.
Define
Stack.
2.
Give real
world example of stack.
3.
List the
operations on stack.
4.
List the
application on stack.
5.
Define push
operation on stack.
6.
Define pop
operation on stack.
7.
Define peep
operation on stack.
8.
When stack
is said to be overflow?
9.
Give
definition of infix, prefix and postfix notation.
10.
Define Tail
recursion.
11.
Identify
the types of expression whether it is infix, prefix or postfix.
a.
4,2$3*3-8,4/1,1+/+
b. PQ+R+-S↑UV+*
12.
Define
Queue.
13.
Give real
world example of Queue.
14.
List the
operations on Queue.
15.
List the
application on Queue.
16.
Define
Insertion operation on Queue.
17.
Define
Deletion operation on Queue.
18.
Define
Circular Queue.
19.
List out
limitation of linear queue.
20.
Write
algorithm to insert element into circular queue.
21.
What is Deques?
Explain with example.
22.
Define
priority queue.
Long
Questions:-
1. Explain Stack with its example.
2. Explain the operation performed on Stack.
3. Explain Push operation with algorithm.
4. Explain Pop operation with algorithm.
5. Explain Peep operation with algorithm.
6. Explain application of Stack.
7. Explain Evaluation of expressions on
stack.
8. Write pseudo-code for factorial
computation.
9. Evaluate following expression.
a. 10+3-2-8/2*6-7
b.
(12-(2-3)+10/2+4*2)
10. Convert following infix expression to
postfix expression:
a. ((a+b)/d-((e-f)+g)
b. 12/3*6+6-6+8/2
11. Convert following infix expression to
prefix expression:
a. ((a+b)/d-((e-f)+g)
b. 12/3*6+6-6+8/2
12. Convert following postfix expression to
infix expression:
c. 4,2$3*3-8,4/1,1+/+
d. PQ+R+-S↑UV+*
13. Convert following postfix expression to
prefix expression:
e. 4,2$3*3-8,4/1,1+/+
f. PQ+R+-S↑UV+*
14. Explain Queue with its example.
15. Explain the operation performed on Queue.
16. Explain insertion operation for queue
with algorithm.
17. Explain Deletion operation for queue with
algorithm.
18. Explain application of Queue.
19. Write short note on Deque.
20. Write short note on Priority Queue.
21. What are the difference between stack and
queue.
22. How to overcome limitation of linear
queue? Explain in detail.
Linked List
Short
Questions:-
1. What is the limitation of sequential data
structures?
2. What is linked list?
3. Give real world example of linked list.
4. What are the advantages of singly linked
list?
5. What are the disadvantages of singly
linked list?
6. Which are the operations performed in
singly linked list?
7. What is the need for linked
representation of lists?
8. Define circular linked list.
9. What are the advantages of circular
linked list?
10. What are the disadvantages of circular
linked list?
11. What is the node structure for circular
linked list?
12. Define doubly linked list.
13. What are the advantages of doubly linked
list?
14. What are the disadvantages of doubly
linked list?
15. List out operations performed in doubly
linked list.
16. List application of linked list.
17. What is the difference between circular
linked list and linear linked list?
18. What is the difference between array and
stack?
19. Define sparse matrix?
Long
Questions:-
1.
Write short
note on linked list.
2.
Explain
operation of singly linked list with algorithm.
3.
Explain
circular linked list.
4.
What are
the advantages of circular linked list over singly linked list?
5.
Write
pseudo code to add node at the end in circular linked list.
6.
Explain
doubly linked list with advantage and disadvantage of it.
7.
Write a
pseudo code to delete a node from doubly linked list.
8.
Explain
operation of doubly linked list with algorithm.
9.
Write short
note on multiply linked lists.
10. Explain application of linked list.
11. Write short note on polynomial manipulation.
12. Write short note on sparse matrix.
13. Explain operation of linked stack and linked queue.
14. Write algorithm for push/pop operation on a linked stack.
15. What are merit of linked stack and queues over their sequential
counterparts?
16. How are push and pop operations implemented on a linked stack?
17. Write algorithm for insertion/deletion operation on a linked
queue.
18. Write short note on Dynamic memory management.
19. Explain application of linked stack and linked queue.
20. Write a pseudo code for implementing stack using linked list.
21. Write a
pseudo code for implementing queue using linked queue.
Trees and Binary Trees
Short
Questions:-
1. Define tree.
2. What is degree of node?
3. Define sibling.
4. Define forest. Also give example of it.
5. Define binary tree.
6. List out type’s binary tree.
7. What is the difference between full binary tree & complete
binary tree?
8. List out different techniques to represent tree.
9. List out different operations you can perform on tree.
10. List out traversal of binary tree.
11. What is inorder traversal?
12. What is preorder traversal?
13. What is postorder traversal?
14. What is the maximum number of nodes in a binary tree of depth k?
15. Trace the binary tree of inorder traversal: BFGPRSTWYZ.
16. What are the applications of tree?
17. Trace the binary tree of preorder traversal: PFBHGSRYTWZ.
18. What do you mean by expression tree?
19. Define leaf node and siblings with example.
20. What is threaded binary tree?
Long
Questions:-
1. Explain tree data structure.
2. How to represent tree using linked list?
3. Explain binary tree with its representation including advantage and
disadvantage.
4. Write a code to insert a node in a binary tree.
5. Write a code to delete a node in binary tree.
6. Explain array representation of binary tree with example?
7. Explain linked representation of binary tree with example?
8. Explain traversal technique of binary tree.
9. Explain inorder traversal with example.
10. Explain preorder traversal with example.
11. Explain postorder traversal with example.
12. Explain application of binary tree.
13. Create a binary tree using inorder and preorder traversal
Inorder: D B H E A I F J C G, Preorder: A B D E H C F I J G
14. Create a binary tree using inorder and postorder traversal
Inorder: D B H E A I F J C G, Postorder: D H E B I J F G C A
15. Create a binary tree from the following sequence:
14, 34, 22, 44, 11, 24, 33
16. Using the following binary tree traverse it into inorder, preorder
and postorder:
17. Consider the following tree.
A
/ \
B C
/ \ / \
D E H I
/ /\
F J K
\
L
a. How many leaves does it have?
b. How many of the nodes have at least one sibling?
c. What is the value stored in the parent node of the node containing
30?
d. How many descendants does the root have?
e. What is the depth of the tree?
f. How many children does the root have?
18. What is inorder traversal of binary tree? Write inorder traversal
of given binary tree.
A
/\
B C
/ \
D E
/\
G F
19. Write
algorithm to perform inorder traversal of binary tree.
20. Write algorithm to perform preorder traversal of binary tree.
21. Write
algorithm to perform postorder traversal of binary tree.
Searching and Sorting
Short
Questions:-
1. Define ordered linear search.
2. Define unordered linear search.
3. Give any one difference between order linear searches and unordered
linear search.
4. Write down complexity of worst case and best case in ordered linear
search.
5. Write
down complexity of worst case and best case in unordered linear search.
6. Define binary search.
7. What are the difference between linear search and binary search?
8. In linked list, which searching technique is better linear search
or binary search?
9. What are the advantages of binary search over linear search?
10. Define sort.
11. Write down complexity of bubble sort and in which situation bubble
sort should be used?
12. Write down complexity of insertion sort and in which situation
bubble sort should be used?
13. Write down complexity of selection sort and in which situation
bubble sort should be used?
14. Write down complexity of quick sort and in which situation bubble
sort should be used?
15. Write down complexity of merge sort and in which situation bubble
sort should be used?
16. What is the time complexity of merge sort?
17. What is the time complexity of quick sort?
18. Can bubble sort ever perform better than quick sort?
19. Which sorting techniques are an example of divide and conquer?
20. Which sorting techniques is an application of recursion?
Long
Questions:-
1. Write short note on linear search with algorithm.
2. Write short note on binary search with algorithm.
3. What are the merits and demerits of binary search?
4. Write the pseudo-code for linear search using array and linked
list.
5. Write pseudo-code for binary search using array and linked list.
6. Explain decision tree for binary search.
7. Write short note on bubble sort with algorithm.
8. Write short note on insertion sort with algorithm.
9. Write short note on selection sort with algorithm.
10. Write short note on merge sort with algorithm.
11. Write short note on quick sort with algorithm.
12. Which sorting technique is more suitable to use? Explain in
detail.
13. Write pseudo-code for binary search using array and linked list.
14. Write down procedure for bubble sort.
15. Why is bubble sort stable?
16. Write down procedure for insertion sort.
17. Write down procedure for selection sort.
18. Write down procedure for merge sort.
19. Write down procedure for quick sort.
20. Trace
quick sort on the list L= {11, 34, 67, 78, 78, 78, 99}. What are your
observations?
No comments:
Post a Comment