Question Bank
Subject :- Data Structure Class:- S.Y.B.Sc.
Chapter 1 :- Introduction to Data Structures
1) Define the following terms:-
a) Data Type b) Data Object c) Data Structure d)ADT(Oct.09)
Ans:- Only Definitions
2) What is the need of Data Structure and its advantages.
Ans:- Explain point wise Needs and advantages .
3) Explain the difference between logical and physical data structure.
Ans:- Two differences are enough for 1 mark question
Chapter 2:-Algorithm Analysis
1) Define the following terms and explain with example:-
a) Time Complexity b) Space Complexity c) Big O Notation d) Frequency
Count e) Step Count f) Algorithm(Ans:- Only Definitions)
2) Define O , Theta ,Omega Notations.
Long answer Question :-
1) What is an Algorithm? Write the essential properties and the performance measures of an algorithm.
Ans:- Definition and at least 5 Characteristics
2)Explain the term analysis of Algorithm.
Ans:- Definition and performance measure.
Chapter 3:- Linear Data Structure.
A) Short Answers (for 1 Marks)
1) How array is implemented in C.
Ans:- Expalin in 2-3 sentence with example
2) Compare the efficiency of Bubble Sort and Counting sort
Ans:- Sentence form diffence is allowed
3) What is the efficiency of Binary Search.
Ans:- Explain efficiency in terms of formula and with best ,average and worst case
4) What is the Best case and worst case for insertion sort?(Apr ,Oct. 2009-1 M)
Ans:- Meaning and example
5) Give the data structure for Representing Sparse Matrix
Ans:- Representation of Sparse matrix is expected.
B) Subjective (For 5 Marks)
1) Explain Bubble Sort Method and write a program for the same?
Ans:- Explain purpose ,method with example, and program.
2) Bubble sort is used to sort the array of integers shown below into ascending
Order. What would be the order of the numbers after two passes of sort?
12, 37, 42, 9, 5,7,50. How many passes and comparisons are required for
Complete sorting? (Oct. 2009)
Ans:- Solve the given example using the above said method.
3) How can efficiency of bubble sort is improved?
Ans:-Discuss the efficiency with best ,average, worst case
4) What is Sparse Matrix? How can it be represented?
Ans:- Definitions and representations
5) Write an algorithm for adding two sparse matrices.
Ans:- Algorithmic steps
6) Explain the Binary Search Method and its program.
Ans:- Discuss the method and write a program
7)Consider the Declaration of array A[5……10,-5….10] of integers .Assuming A
is stored in a row major order with first element of A is at address 100 and each
integer occupying 4 bytes . What would be the lowest byte address of the
element A[6,0]? (Oct. 06-5M)
8) What do u mean by a stable sorting method?
Ans:-Only meaning and example.
9) Write short note on Quick Sort Algorithm with suitable example
Ans:- Discuss the method and write a program
10) Write short note on Searching methods.
Ans:- Definition, pupose, example
11) Which of the sorting algorithm has the best performance in the terms of storage and time complexity? Justify your answers.
Ans:- discuss every method and tell how one is different by other.
12) Trace the Quick sort algorithm for the following data.
a)1,2,3,4,5,6,7,8,912,11,10
b) 7,9,8,10,4,6,2
13 ) Sort the following sequence using merge sort.
9,10,3,11,5,7,8,4
Chapter 4:- Linked List
A)Short Answers :-
1. How is an element in an array different from the element in a linked list?
2. What are the fields of a node in a linked list?
3. What is the function of the pointer field in a linked list?
4. How do you point to the first node in a linked list?
5. What is a singly linked list?.
6. In most programming languages, an array is a static data structure. When you define an
array, the size is fixed. What problem will this restriction create?
7. A linked list is a dynamic data structure. The size of linked list can be changed
dynamically (during program execution). How does this feature benefit L programmer?
8. Which operation do you think is easier, adding an element to an array, orac an element
to a linked list ? Justify your answer.
9. Which operation do you think is easier, deleting an element to an array, deleting an
element to a linked list ? Justify your answer.
10. Which operation do you think is easier, accessing an element to an array, accessing an
element to a linked list ? Justify your answer.
11. Which operation do you think is easier, sorting an element to an array, or sorting. an
element to a linked list ? Justify your answer.
12. What is a linked list ? How is it represented?
13. What is dynamic memory allocation ? How does it help in building corn- programs?
14. What is the principal difference between the functions malloc and calloc?
15. Why a linked list is called a dynamic data structure ? What are the advantage using
linked lists over arrays?
16. Describe different type of linked lists.
17. Write a program that reads the name, age and salary of 10 persons and m them in a
linked list sorted by name.
18. There are two linked lists A and B containing the following data:
A : 3, 7, 10, 15, 16, 9, 22, 17, 32
B :16,2,9,13,37,8,10,1,28
Write a program to create:
• A linked list C that contains only those elements that are common in linked lists A and B.
• A linked list D which contains all elements of A as well as B ensuring that there is no repetition of elements.
19. Assume a singly linked list containing integers. Write a function move() which would
move a node forward n positions in the linked list.
20. A linked list contains some positive numbers and some negative numbers. Using this
linked list write a program to create two more linked list, one containing all positive
numbers and the other containing all negative numbers.
21. Create two linked lists to represent the following polynomials:
3x2y÷9xy3+l5xy+3
13 xy2 + 7x2y +22 xy +9y3
Write a function add( ) to add these polynomials and print the resulting linked
list.
22.Compute length, Reverse list, Print in Reverse order, Insert/Delete node, Search a node, Print list, Create sorted list, Concatenate two lists.
23.Evaluate a polynomial of a single variable.
24. Compute addition, subtraction and multiplication of two po’ynomials.
25. Read and Print sparse matrix.
26.Store string and Compute length, Reverse string from a particular character, search and change substring, Insert/Delete character, Search a character; Sort the string without using another list, Concatenate two strings, Compare two strings.
27. Compute l’s complement and 2’s complement of a binary number.
28. Add any two binary numbers.
29. Appointment scheduling for a day : Set bounds by taking starting time and ending time of a day. Display free slots. Ask for a new appointment. Check for validity and insert. Delete cancelled appointment. Display all appointments of a day.
30.Sort a list using pointer manipulation.
31.. Merge two sorted lists into third.
32. Merge second sorted list into first sorted list.
33. Create sorted list and insert element in the same.
34. Check whether string stored is palindrome or not.
35. Create two lists to store two sets. Compute intersection, Union , difference, and symmetric difference of the same. Compute power set of a set.
36. Represent following polynomials using GLL.
(a) x3(y3(3z4 — yz3 + z) — y(z2 + z) xyz
(b) x’°y3z2 + x4y4z + 2yz
(c) x4+5x3+7x2+6x)y4
(d) —x3y2z4 + xz2x3y — xyz + zy3
37. Write an algorithm to do the following operations on circular single linked (with head nodes): (i) Delete a node, (ii) Concatenate two circular lists to form a third list which is also circular(considering all special cases that may arise.) Give ‘C’ language declarations for the header node and list nodes.
38. Write short note on generalized linked-list.
39. What is generalized linked list? Represent the following polynomial generalized linked list:
GP (a, b, c) = a’°b3c2 + 2a8b3c2 + 3a8b2c2 + a4b4c + 6a3b4c + 2bc.
40. Differentiate singly linked list and doubly linked list. Write a function to insert node before and after any node in doubly linked list.
41. Write short note on ADT for linked list.
42. Explain how circularly linked list cart be erased in a fixed amount of time.
43. Differentiate between static and dynamic implementation of singly linked list
B). University Questions:
1. Define linked list. Define node structure of linked list. [April 05:1]
2. Write a C function to delete a node at any position P in single linked list.
[April 06:5]
3. Write a C function to reverse a list. [Oct. 06:3]
4. Write a C function to split a singly linked list into two lists such a manner first linked list contains odd number nodes and second contains even number .[April09: 5]
5. Write a function for insertion and deletion of an element at any position
doubly linked list. [April 05, Oct. 05,06]
6. Write a function to create a singly circular linked list. [Oct. 05]
7. Define generalized linked list with example. [April 04, 06, Oct. 03:1]
Chapter 5:- STACK.
A) Short Answers (for 1 Marks)
1. What is stack Ans:- Definition
2. How to represent a stack. Ans:- Syntax
B) Subjective
1. Give an algorithm to evaluate postfix expressions. Ans:- Only Algorithm
2. Give an algorithm to evaluate prefix expressions. Ans:- Only Algorithm
3. Give an algorithm to convert an expression in infix from into postfix
form. Ans:- Only Algorithm
4. Transform the following infix expressions into their equivalent pt expressions:
(A_B)*(D/E)
(A+B”D) / (E—F)+G
A*(B+D) /EF*(G+H/K)
5. Transform each of the following prefix expression into infix expression
+A-BC
+lA_*$BCD/+EPGHI
+$ABC*D**EFG
6. Transform each of the following postfix expression into infix expression
ABC+
AB—C+DEF-+$
ABCDE+$*EF*_
7. Explain the concept of multiple stacks with an example.
Ans:- Meaning ,use, and diagrammatic representation in memory, example.
8. Write a program to implement Stack using singly linked list. Ans:- Only Program
C). University Questions
1. Give reverse polish notation for the following infix notation.
(((A+ (B’C)—D) ) *(E_(A/C))) [Oct.03 : 3 M]
Ans. Reverse polish notation is *+A-^BCD-E/AC
2. Show how stack is used in recursive function for calculating factorial.[OCT.03:- 3 M]
Ans:- Show with example and diagrams
3.What are various applications of stack. [April 04&05: 3M]
Ans:- State the application in a sentences .
4. List the different stack operations. [April 05, Oct.05 :1M]
Ans:- Push ,Pop, Insert an item ,Delete an item,IsEmpty,IsFull
5.What are different forms to write an expression. Explain with suitable example.
Ans:-Infix, Postfix, Prefix Expressions. Give one example with all 3 forms
· Write an algorithm to evaluate even postfix expression. [Oct. 05:5M]
Ans:- Consider one example and evaluate and show with program .
6. If the postfix form of a string is, [Oct. 06 : 1 M]
AB $ CD*_EF/GH+/+ What is the infix string.
Ans. ((A $ B) — (C * D)) + ((E/F) / (G + H))
7. Show the stack contents and output while converting the following infix string
to postfix. [Oct. 06: 1. M] A/B$C+D*E_A*C
8. Give the infix expression for the following prefix string $ + A * BC + * ABC
[AprilO7:1M]
Ans. (A + CB * C) $ ((A * B) ± C)
9. Write short notes on: [Dec. 01 : 10 M]
(i) Applications of Stack Ans:- state the various applications
(ii) Use of stack in expression conversion Ans:-State with one of the example
10. Convert the following expression into postfix form (show stack steps). Evaluate
the expression after conversion: A +B*C A (D + E) * (-F)
Given: A=2,B=3,C=4,D=1,E=1,F=5.
Ans:- Push ,Pop, Insert an item ,Delete an item,IsEmpty,IsFull
12. Write the node structure of stack element in case of dynamic implementation of
stack. [April 09: 1 M]
13. List applications of stack. [April 04, 05, 06 : 1 M] Ans:- state the various
applications
14. Evaluate the postfix expression, show the contents of stack ((A + B) * (C — D)) / E
if A=5,B=3,C=9,D=2andE=4 V [AprilO4:3M]
15. Write an algorithm for prefix to infix conversion for an expression.
[April 05 : 3 M] Ans:-Only Algorithm is expected
16. What are different forms to write an expression? Explain with suitable example, write
an algorithm to evaluate given postfix expression. [Oct. 05: 5 M]
Ans:- Forms of Expressions:- Infix,Postfix,Prefix.Give one example and convert
In various forms .Write only algorithm
17. Evaluate the following expression using stack. A+B*C_D with
A=4,B=3,C=5dD=1 [AprilO6:5M]
18.What is the use of a multiple stack. :-Ans:-Explain use in at least 8 -10 Statements
19.How the stack is useful to convert recursive procedure into non-recursive procedures.
Ans:-Difference is expected.
20.Write a function to evaluate given postfix expression[April 08:- 5M]
Ans:- Function block is expected only.
21.Show how stack is used in recursive function for calculating factorial.[Oct.03 3M]
Ans:- show with diagrammatic manner
22.Show the stack contents and output while converting the following infix string to
postfix A/B $C+D*E-A*C [Oct.06:-1M]
23.If the postfix form of a string is AB$C*D-EF/GH+/+ Then what is the actual infix
string? [Oct.06:-1M]
Chapter: 6 QUEUE
A) Short Questions:-
1.Define queue. Ans:- Definition
2.What are the applications of queue. Ans:-Various uses of Queue
3. What is priority queue ? How they are implemented?
Ans:- Meaning of Priority Queue and syntax
4. What are advantages of sorted list implementation of priority queue.
Ans:-State in 1-4 Statements
5. State the operations perform on priority queue.
Ans:- Operations on a priority Q. Not Example, Statement forms
6. Write necessary functions in C to implement circular queue in an array. Assume
rear, front = 0 initially.
7. Explain the concept of priority queue with a suitable example.
Ans:- Meaning and Example
8. What is multi-queue? Ans: - Explain concept.
B) University Questions:-
1. Name the various operations performed in a queue.[Apr. 05,Oct.04:- 1 M]
Ans:- Insert Delete, Isfull, IsEmpty, create, Initialize
2. What is circular queue? [Apr. 05:- 1 M] Ans:-Definition
3. What is DeQue? [Apr. 06:- 1 M] Ans:- Definition
4.Write a C function named delete Q,which deletes an element from a linked queue of
integers .The prototype of the function should be int delete Q(struct Q node *)
Ans:-Use the same name for function given in a que. and write the procedure
5. Write C function to delete an element from linear queue. .[Apr. 09:- 5M]
Ans:- write the procedure in a function
6. Define priority queue. What are the different types of priority queue? .[Apr. 09:- 1 M]
Ans:- Definition and types.
Chapter 7:-TREES
A) Short Questions:
1. Describe array and linked representation of binary tree.
Ans:- Meaning and its description using the both is expected .
2. Write non-recursive function to perform in order traversal of a binary tree structure.
3. Define:
a)Binary tree b)External node c)Internal node d)Height of tree
e)Level of tree f)Complete binary tree g)Binary tree h)Binary search tree
Ans:- Only write the definitions
4. Write a program to construct binary search tree of given numbers (data).
Ans:- A demo program with correct syntax is expected
5. Root of a binary tree is an ancestor of every node, comment. Ans:- Give Justification
how it is imp.
6. Define data structure. :-Ans:- Definition
7. Write any two traversal techniques for trees. Ans:- Traversal techniques
8. Write a function to count the number of leaf nodes of a given tree.Ans:- Only function
block is imp.
9. Explain heap sort algorithm for following:
(i) 30, 49, 36, 15, 76, 85, 25, 90 (ii) 33, 13, 25, 85, 30, 10, 25, 95
Ans:- Solve it showing every steps.
10. Write a function for postorder and preorder traversal of binary tree. Ans:- Both
Functions are needed.
11. What is threaded binary tree ? Give its advantages? Ans:- Meaning and advantages
12. Define height balance tree (AVL).Ans:- definitions of AVL
13. Explain RR, RL, LL, LR rotations of AVL with an examples.
14. Define binary tree and its types. Ans:- Def. and Types
15. Write a function in C to find no. of levels in the given tree using breadth L search
technique.
16. Write a ‘C’ program to create a tree and count total number of nodes in a tree.
Ans:- Program
17. Write notes on:
(i) Construction of heap
(ii) Threaded binary tree
(iii) BFS and DFS
(iv) Tree Traversal
Ans:-Explain in detail with example
18. Define an AVL tree. Insert nodes on following keys in an AVL tree:
A,Z,B,Y,C,X
19.Write a recursive function in C that creates a mirror image of a binary tree.
20.What is the number of binary trees with 3 nodes which when traverse in
postorder give the sequence A, B, C ? Draw all these binary trees.
21.Write a function to traverse a give tree in order.
B)University Questions
1. Construct Binary search tree for the following data and give inorder, preorder
and postorder tree traversal. [April 08: 5 M]
Ans. 20, 30, 10, 5, 16, 21, 29, 45, 0, 15, 6.
2.Write a C function to print minimum and maximum element from a given
binary search tree. [Oct. 03: 3 M]
3. Write a ‘C’ function for implementing binary search algorithm.[Oct. 03 : 3 M]
4. Define : Balance tree. . [Oct. 03 : 1 M] Ans:- Definitions
5. Explain sequential representation of binary tree. [April 04: 3 M]:- Meaning ,Purpose ,diagram with example
6. Sort the following sequence of numbers using heap sort method 12, 30, 10, 8, 15, 100, 2, 33, 67, 5. [April 04 : 3 M] Ans:- Stepwise . sorting by applying method
7. Explain any two traversal technique. [April 04: 3 M]
8. Define:
(i) Expression Tree [April 04 : 1 M]
(ii) Balance factor of AVL tree. [April 04, 08 : 1 M]
(iii) Binary search tree. [Oct. 04 : 1 M]
9. Define:
(i) Complete binary tree. [Oct. 04: 1 M]
(ii) Strictly binary tree [Oct. 04, April 06: 1 M]
10. Write an algorithm to count leaf nodes in a tree. [Oct. 04, April 05: 3 M]
11. Sort the following numbers using heap sort 25, 57, 48, 37, 12, 92, 86, 33. [Oct. 04]. Ans:-Sorting by applying method
12. Construct AVL tree for the following data: Mon Sun Tue Fri Sat Wed Tue [Oct. 04]
13. What is complete binary tree. [April 05: 1 M] Ans:- Definition
14. What are different tree traversal methods ? Explain with example. [April 05 : 3 M]
Ans:- Inorder,Postorder,Preorder ,Give Examples
15. How many nodes will be present on level i of a full binary tree? [April 05: 5 M]
16. Construct AVL tree for the following data.
50, 40, 20, 100, 80, 200, 150
17. Sort the following number using heap sort. [April 06:5 M]
24, 4, 75, 2, 60, 10, 80, 12
18. Construct binary tree for the following keys: [April 07: 5 M]
50, 40, 60, 50, 70
19. Write an algorithm for non-recursive postorder traversal. [April 09: 3 M]
20. Evaluate the following postfix expression:
xyzw — + *
wherex=4, y=3, z=5, w=2[April 09: 3 M]
21. Construct AVL tree for the following: [April 09: 5 M]
35, 40, 10, 50, 15, 100, 90
22. Write ‘C’ function to create a mirror image of a binary tree. [April 09: 5 M]
23. Construct binary search tree for the following data and give and postorder tree traversal.20 30 10 5 16 21 29 45 0 15 6 [April 08: 5 M]
24. Construct on AVL tree for the following:
35, 40, 10, 50, 15,. 100, 90[April09: 5 M]
Chapter 8:-GRAPH
1. Show that all vertices in an undirected finite graph cannot have distinct degrees, if the graph has atleast two vertices.
2. A complete, undirected, weighted graph C is given on the vertex set {0, 1, ... n — 1) for any fixed n. Draw the minimum spanning tree of C if,
(a) the weight of the edge(u,v)is u—vI. (b) the weight of the edge (u, v) is u + v.
3. Write pseudo C algorithms for:
(a) BPS
(b) DFS
(c) Dijktra’s algorithm
4. Consider the following graph and traverse the graph using BFS and BPS.
5. Define:
(i)Vertex
(ii)Edges
(iii) Indegree
(iv) Outdegree
7. Define graphs:
(i) Undirected graphs
(ii) Directed graphs
(iii) Weighted graphs
(iv) Multi graphs
8. What are the different representations of graph ? Explain adjacency matrix representation of graph.
9. What is a path matrix.
10. What do you mean by traversal of any graph.
11. ‘What is critical path.
12. Explain BFS algorithm for the traversal of any graph with suitable example. Define time complexity of the algorithm.
13. Explain any one shortest path algorithm.
14. Explain adjacency matrix and adjacency list with suitable example.
V. University Questions:
1. Define:
Vertex Edges, Isolated vertex, Pendant vertex, Complete graph, Acyclic graph
Cycle,Critical path, Multigraph , AOE network, Indegree ,Out degree, Adjacency matrix
Complete graph
2. List any two graph traversal techniques and the data structure used in them:
[April 04 : 3 M]
3. Explain AOE network with example. [April 04:3 M]
4. Give various methods of representing graphs.
5. Find critical path for the following diagram.
Ans. Vi -4 V2 —* V3 — V4 —+ V5 —> V6 = 22
6. What are the various applications of graph.
7. Consider an undirected graph G whose edges are
(V1. V2) (V11 V3) (V2. V3) (V2. V4) (V31 V4)
What is DFS and BFS of graph G.
8. Explain graph traversal methods with algorithm.
9. Give adjacency list representation of following graph.
10. Apply DFS to complete undirected graph of four vertices. List the vertices in the
order they would be visited. [Oct. 06, April 07: 3 M]
11. Explain BFS with example. [Oct. 06:3 M]
12. Give total degree of each node of the following graph:
Total degree of A =2 B =3 C=1
13. Apply BFS to complete undirected graph of 4 vertices. Ans.
[April 07: 1 Ml
14. The number of edges in a ‘n’ vertex complete graph is n(n+ 1)• Justify.
15. Consider the following graph and traverse using BFS and DFS. [April 09: 1 M]
Ans.
16. What is the total number of edges in complete directed graph and completed
undirected graph. [April 08 : 1 M]
No comments:
Post a Comment