JNTU ONLINE BITS FOR BTECH I YEAR (UNIT WISE)

UNIT-8
Trees And Graphs
Q.1 The _________ of a tree is the number of levels in it.
(a) Height (b) Depth
(c) Height or Depth
Q.2 The _________ of an element is the number of children it has
(a) Height (b) Depth
(c) Degree
Q.3 The degree of a leaf is
(a) 0 (b) 2
(c) 1 (d) 3
Q.4 A binary tree cannot be empty
(a) True (b) False
Q.5 A tree cannot be empty
(a) True (b) False
Q.6 Each element in a tree can have any number of sub trees
(a) True (b) False
Q.7 The drawing of every binary tree with n elements, n > 0, has exactly… edges.
(a) n (b) n - 1
(c) n - 2
Q.8 A binary tree of height h, h >= 0 has at least_________ elements in it
(a) h (b) h - 1
(c) h - 2
Q.9 A binary tree of height h, h>=0 has at most_________ elements in it
(a) 2 ^ h (b) 2 ^ h - 3
(c) 2 ^ h- 1
Q.10 The height of a binary tree that contains n, n >= 0, elements is at most
(a) n - 1 (b) n
(c) n + 1
Q.11. The height of a binary tree that contains n, n>=0, elements is at least
(a) log n (b) log(n - 1)
(c) log(n + 1)
Q.12 A binary tree of height h that contains exactly 2^h-1 elements is called a
(a) Complete binary tree (b) Full binary tree
(c) Compound binary tree
Q.13 The height of a complete binary tree that contains n elements is
(a) log (n + 1) (b) log n
(c) log (n - 1)
113
Q.14 There are _________ common ways to traverse a binary tree.
(a) 1 (b) 3
(c) 4 (d) 2
Q.15 The _________ form of an expression is the form in which we normally write
an expression.
(a) prefix (b) pos fix
(c) infix
Q.16 In _________ form each operator comes immediately before its operands.
(a) prefix (b) postfix
(c) infix
Q.17 In _________form each operator comes immediately after its operands
(a) prefix (b) post fix
(c) infix
Q.18 An edge with an orientation is called_________ edge.
(a) directed (b) undirected
(c) Bibirectional
Q.19 An edge with no orientation is called_________edge.
(a) directed (b) undirected
(c) Bibirectional
Q.20 A directed graph is also called
(a) bigraph (b) digraph
(c) Directing graph
Q.21 A self-edge is also called
(a) directed edge (b) undirected edge
(c) loop
Q.22 A simple path is a path in which all vertices except possibly the first and last are
(a) different (b) same
(c) may not be different
Q.23 A subgraph of a graph 'G' that contains all the vertices of G and is a tree is a
(a) Bipartite graphs (b) spanning tree
(c) both
Q.24 The_________ of a vertex of an unidirected graph is the no of edges incident on
vertex
(a) degree (b) order
(c) height
Q.25 A n-vertex undirected graph with n*(n-1)/2 edges is a_________ graph
(a) subgraph (b) full graph
(c) complete graph
114
Q.26 The _________ of a vertex is the number of edges incident to vertex ‘i’
(a) in degree (b) out degree
(c) subdegree
Q.27 The _________of a vertex is the number of edges incident from vertex ‘i’
(a) in degree (b) out degree
(c) subdegree
Q.28 A complete digraph on n vertices contains exactly _________directed edges.
(a) n (b) 0 n*(n - 1)/2
(c) n*(n - 1)
Q.29 How many graph search methods are there?
(a) 1 (b) 3
(c) 2
Q.30. Which graph search method is used more frequently?
(a) Breadth first search (b) depth first search
(c) both
Q.31 The method of starting at a vertex and identifying all vertices reachable from it
is called
(a) Depth first search (b) breadth first search
(c) Horizontal search
Q.32_________ is quite similar to pre-order traversal of a binary tree.
(a) Breadth-first search (b) Depth-first search
(c) Horizontal search
Q.33 Of the following tree structures, which is more efficient considering space and time
complexities?
(a) Incomplete Binary Tree (b) Complete BinaryTree
(c) Full Binary Tree d) none
Q.34 What is the order of complexity for binary search tree?
(a) log n2 (b) n log n
(c) log n (d)none
Answers
1. (c) 2. (c) 3. (a) 4. (b)
5. (a) 6. (a) 7. (b) 8. (a)
9. (c) 10. (b) 11. (c) 12. (a)
13. (a) 14. (c) 15. (c) 16. (a)
17. (b) 18. (a) 19. (b) 20. (b)
21. (c) 22. (a) 23. (b) 24. (a)
25. (c) 26. (a) 27. (a) 28. (c)
29. (c) 30. (b) 31. (b) 32. (b)
33. (b) 34. (a)
115
Data Structures
Q. How to distinguish between a binary tree and a tree?
Ans: A node in a tree can have any number of branches, while a binary tree is a tree
structure in which any node can have at most two branches. For binary trees, we
distinguish between the subtree on the left and subtree on the right, whereas for
trees the order of the subtrees is irrelevant.
Consider the following figure...
Fig.
This above figure shows two binary trees, but these binary trees are different. The
first has an empty right subtree while the second has an empty left subtree. If the
above are regarded as trees (not the binary trees), then they are same despite the fact
that they are drawn differently. Also, an empty binary tree can exist, but there is no
tree having zero nodes.

JNTU ONLINE BITS FOR BTECH I YEAR (UNIT WISE)

UNIT-7
Q.1 Is a linked list a linear or non-linear data structure?
(a) Linear (b) Non-linear
(c) Can’t say (d) None
Q.2 How can I search for data in a linked list?
(a) Non-linear search (b) Linear search
(c) Can’t say (d) None
Q.3 What is each entry in a linked list called?
(a) Element (b) Node
(c) Value (d) None
Q.4 The value of the first linked-list index is ____________
(a) –1 (b) 0
(c) 1 (d) none
Q.5 ____________ form of access is used to add and remove nodes from a queue.
(a) FIFO (b) LIFO
(c) FILO (d) None
Q.6 New nodes are added to the ____________ of the queue.
(a) front (b) back
(c) middle (d) none
Q.7 A dequeue (or double-ended queue) is a sequence of elements with the property that
elements can be added, inspected, and removed at ____________
(a) either end (b) one end
(c) both ends (d) none
Q.8 What is the benefit of using a queue linked list?
(a) Queue for scheduling (b) Queue is faster than stack
(c) Both (d) None
Q.9 The StackLinkedList class inherits the LinkedList class
(a) True (b) False
(c) Can’t say (d) None
Q.10 The stack top is initialized to____________ value.
(a) 0 (b) 1
(c) –1 (d) none
Q.11 Convert the infix expression (A – B) * C + D to postfix.
(a) A B – C * D + (b) AB-CD+*
(c) AB–CD*+ (d) none
Q.12 Entries in a stack are ‘ordered’. What is the meaning of this statement?
(a) A collection of stacks can be sorted.
(b) Stack entries may be compared with the ‘<’ operation.
106
(c) The entries must be stored in a linked list.
(d) There is a first entry, a second entry, and so on.
Q.13 The operation for adding an entry to a stack is traditionally called
(a) add (b) append
(c) insert (d) push
Q.14 The operation for removing an entry from a stack is traditionally called
(a) delete (b) peek
(c) pop (d) remove
Q.15 Which of the following stack operations could result in stack underflow?
(a) is_empty (b) pop
(c) push (d) Two or more of the above answers
Q.16 Which of the following applications may use a stack?
(a) A parentheses balancing program
(b) Keeping track of local variables at run time
(c) Syntax analyzer for a compiler
(d) All of the above
Q.17 In the linked-list implementation of the stack class, where does the push method
place the new entry on the linked list?
(a) At the head
(b) At the tail
(c) After all other entries that are greater than the new entry
(d) After all other entries that are smaller than the new entry
Q.18 Convert (6 + 2) * 5 – 8 / 4 into postfix.
(a) 62+584/–* (b) 62+5*84–/
(c) 6 2 + 5 * 8 4 / – (d) None
Q.19 Convert the expression ((A + B) * C – (D – E) ^ (F + G)) to equivalent polish
notation.
(a) –^*+ABC–DE+FG (b) ^ – * +ABC – DE + FG
(c) ^*–+ABC–DE+FG (d) None
Q.20 Convert the expression ((A + B) * C – (D – E) ^ (F + G)) to equivalent reverse
polish notation.
(a) AB+C*DE-FG+^– (b) AB+CDE*--FG+^
(c) AB + C * DE - - FG + ^ (d) None
Q.21 The minimum number of queues needed to implement the priority queue are
(a) one (b) two
(c) can’t say (d) none
Q.22 In tree construction which is the suitable efficient data structure?
(a) Array (b) Linked list
(c) Stack (d) Queue
107
Q.23 The first operation performed on a stack is____________
(a) deletion (b) insertion
(c) both (d) none
Q.24 Stack is said to be overflow when____________
(a) top=max–1 (b) top=max
(c) top=–1 (d) none
Q.25 The process of allocating memory at run time is called____________
(a) run time allocation (b) compile time allocation
(c) dynamic memory allocation (d) both a and c
Q.26 Local variables are stored in____________
(a) stack (b) heap
(c) memory (d) none
Q.27 Operations performed on a linked list is/are____________
(a) traversing the list (b) inserting an item
(c) creating a list (d) All the above
Q.28 The free memory region is called____________
(a) heap (b) stack
(c) both (d) none
Q.29 A block of memory can be requested at run time using____________
(a) malloc (b) calloc
(c) both (d) none
Q.30 Multiple blocks of memory can be allocated using____________
(a) malloc (b) calloc
(c) can’t say (d) both
Q.31 Memory space must be explicitly released in dynamic run-time allocation.
(a) True (b) False
(c) Can’t say (d) None
Q.32 Realloc is used for____________
(a) Reallocation of memory (b) free memory space
(c) none (d) can’t say
Q.33 A double-linked list is said to be empty when____________
(a) rear=front–1 (b) rear =front=0
(c) rear=front (d) none
Q.34 A double-linked list is said to be overflow when____________
(a) rear=front (b) rear>=max–1
(c) none
Q.35 Evaluate the postfix expression 22*1+
(a) 6 (b) 4
108
(c) 5 (d) 7
Q.36 Convert a$b*c-d+e/f/(g+h) into a postfix expression.
(a) ab$cd-* ef/gh+/+ (b) ab$c*d-ef/gh/++
(c) ab$c*d-ef/gh+/+ (d) None
Q.37 A circular queue is said to be underflow when____________
(a) (rear+1)%max=front (b) (front+1)%max=rear
(c) rear=front (d) none
Q.38 A ___________ is a way of organizing data that considers not only the items stored,
but also their relationship to each other.
(a) linked list (b) data structure
(c) both (d) none
Q.39 The areas in which data structures are applied extensively are
(a) Numerical Analysis, (b) Graphics,
(c) Artificial Intelligence (d) All
Q.40 A circular queue is said to be overflow when____________
(a) (rear+1)%max=front (b) (front+1)%max=rear
(c) rear=front (d) none
Q.41 The highest precedence operator is____________
(a) $ (b) ^
(c) * (d) ()
Q.42 Among the following which is fastest to implement?
(a) Array (b) Linked list
(c) Depends on application (d) Both a and b
Q.43 To place the elements in a particular place ____________ is used.
(a) array (b) linked list
(c) both (d) can’t say
Q.44 In an input restricted deque elements are insert from____________
(a) left (b) right
(c) either side (d) none
Q.45 Convert abc$+ into infix.
(a) a$b+c (b) a+b$c
(c) a$bc+ (d) None
Q.46 The data structures used to perform recursion are
(a) queue (b) stacks
(c) both (d) none
Q.47 Evaluate the postfix expression 23+5*.
(a) 11 (b) 25
(c) 13 (d) None
Q.48 Stacks are used in____________
(a) calculators (b) computers
109
(c) both (d) none
Q.49 Convert ab$c*d-ef/gh+/+ into infix.
(a) a*b$c-d+e/f/(g+h) (b) a$b*c+d-e/f/(g+h)
(c) a$b*c-d+e/f/(g+h) (d) none
Q.50 Structures which contain a member field that points to the same structure type are
called-____________
(a) self-referential structure (b) recursive structure
(c) both (d) none
Answers
1. (a) 2. (b) 3. (b) 4. (d)
5. (a) 6. (b) 7. (c) 8. (c)
9. (a) 10. (c) 11. (a) 12. (d)
13. (d) 14. (c) 15. (a) 16. (d)
17. (a) 18. (c) 19. (b) 20. (c)
21. (b) 22. (b) 23. (b) 24. (a)
25. (d) 26. (a) 27. (d) 28. (a)
29. (c) 30. (b) 31. (a) 32. (a)
33. (a) 34. (b) 35. (c) 36. (c)
37. (a) 38. (b) 39. (d) 40. (a)
41. (d) 42. (c) 43. (b) 44. (b)
45. (b) 46. (b) 47. (b) 48. (c)
49. (c) 50. (a)
Q.51 Which of the following is the feature of stack? All operations are at one end and it
cannot reuse its memory
Ans: Any element can be accessed from it directly.
Q.52 When stacks created, they are…
Ans: initially empty
Q.53 What is time required to insert an element in a stack with linked implementation?
Ans: (log 2n)
Q.54 The time taken for addition of an element in a queue is
Ans: (log n)
Q.55 When is a linear queue said to be empty? Front==rear
Ans: Front=rear
Q.56 When queues are created, they are
Ans: initially empty
Q.57 What is the type of algorithm used in solving the 8 Queens problem?
(a) Queues (b) Semaphores
(c) Backtracking (d) Dijkstra
Q.58 In which data structure, elements can be added or removed at either end, but not in
110
the middle?
(a) Linked List (b) Double ended Queue
(c) stack (d) none
Q.59 Which sort shows the best average behavior?
(a) Quick sort (b) Bubble sort
(c) Insertion sort (d) Heap sort
Q.60 Which data structure is needed to convert infix notations to post fix notations?
(a) stack (b) queue
(c) linked list (d) d-queue
Q.61 What data structure would you mostly likely see in a non recursive implementation
of a recursive algorithm?
(a) queue (b) linked list
(c) stack (d) double linked list
Miscellaneous Questions
Q.1 What is a data structure?
Ans: A data structure is a way of organizing data that considers not only the items stored,
but also their relationship to each other. Advance knowledge about the relationship
between data items allows designing of efficient algorithms for the manipulation of
data.
Q.2 List the areas in which data structures are applied extensively?
Ans: Compiler Design, Operating System, Database Management System, Statistical
analysis package, Numerical Analysis, Graphics, Artificial Intelligence, Simulation
Q.3 What are the major data structures used in the following areas: RDBMS, Network
data model and Hierarchical data model?
Ans: RDBMS-Array (i.e., Array of structures)
Network data model-Graph
Hierarchical data model-Trees
Q.4 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 and pointer to connect them. It is not possible to use ordinary pointers for this.
So we go for void pointer. A void pointer is capable of storing a pointer to any type
as it is a generic pointer type.
Q.5 What is the 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.
Q.6 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
111
function has its equivalent iterative (non-recursive) function. Even when such
equivalent iterative procedures are written, an explicit stack is to be used.
Answers
57. (c) 58. (b) 59. answer missing 60. (a)
61. (c)

JNTU ONLINE BITS FOR BTECH I YEAR (UNIT WISE)

UNIT-6
Searching And Sorting Techniques
Q.1 The __________ refers to the operation of arranging data in some given order, such
as increasing or decreasing.
(a) sorting (b) searching
(c) merging
Q.2 Which sorting technique needs to scan through the entire array and swap adjacent
elements whenever required?
(a) Bubble Sort (b) Selection Sort
(c) Insertion Sort
Q.3 The number of moves required for sorting an array using the Bubble Sort is
(a) O (n2) (b) O (Log (n)
(c) O (n)
Q.4 The technique which involves selecting the minimum element is
(a) Bubble Sort (b) Selection Sort
(c) Insertion Sort
Q.5 The number of moves required for sorting an array using the Selection Sort is
(a) O (n) (b) O (Log (n)
(c) O (n2)
Q.6 __________sort works by considering the elements one at a time and inserting the
element in its proper place among those already considered.
(a) Bubble Sort (b) Selection Sort
(c) Insertion Sort
Q.7 Factors that help in deciding the sorting algorithm to be used are
(a) Memory (b) Performance
(c) Flexibility (d) All
Q.8 Which Sorting technique is simplest to use?
(a) Bubble Sort (b) Selection Sort
(c) Insertion Sort (d) Quick Sort
Q.9 Which searching technique is the best among the three searching techniques?
(a) Quick Search (b) Binary Search
(c) Linear Search
Q.10.In __________search, as the number of elements increases, the time taken to perform
the search increases linearly.
(a) Quick Search (b) Binary Search
(c) Linear Search
Q.11 The linear search requires __________comparisons in the worst case.
(a) N (b) N*N
(c) log (N)
101
Q.12 __________search works by comparing your search element with the center element
of the array.
(a) Quick Search (b) Binary Search
(c) Linear Search
Q.14 The disadvantage of binary search is
(a) Takes more time (b) Complexity is high
(c) The array has to be in the sorted order
Q.14 Which sorting technique is the best one?
(a) Merge Sort (b) Quick Sort
(c) Selection Sort
Q.15 Which sorting technique makes use of a pivot element?
(a) Merge Sort (b) Quick Sort
(c) Selection Sort
Q.16 Which sorting technique is the fastest one?
(a) Quick Sort (b) Merge Sort
(c) Insertion Sort
Q.17 What is the best-case time complexity of linear search?
(a) 1 (b) O (log (n))
(c) O (n)
Q.18 What is the average-case time complexity of linear search?
(a) 1 (b) O (log (n))
(c) O (n)
Q.19 What is the worst-case time complexity of linear search?
(a) 1 (b) O(n)
(c) O(n2)
Q.20 What is the best-case time complexity of binary search?
(a) 1 (b) O (log (n))
(c) O (n2)
Q.21 What is the worst-case time complexity of binary search?
(a) 1 (b) O (log (n))
(c) O (n2)
Q.22 What is the average-case time complexity of binary search?
(a) 1 (b) O(log(n))
(c) O(n2)
Q.23 _________refers to finding whether a data item is present in the set of items or not.
(a) Searching (b) Sorting
(c) Merging
Q.24 The time required to search depends on the following factors:
(a) Whether the data is arranged in a particular order or not
(b) The location of the data to be searched
102
(c) The total number of searches to be done
(d) All
Q.25 When the data is arranged in a particular order then the time taken to search for the
item is
(a) more (b) less
(c) cannot say
Q.26 In __________.search, the searching process starts from the first item.
(a) binary (b) linear
(c) quick
Q.27 A__________search is a searching technique that can be applied only to a sorted list
of items.
(a) binary search (b) linear search
(c) quick search
Q.28 Which searching technique is also called dictionary search?
(a) Binary Search (b) Linear Search
(c) Quick Search
Q.29 Binary Search can be applied to sorted and unsorted lists.
(a) Yes (b) No
Q.30 _________searching technique can be applied to both sorted and unsorted list.
(a) Binary Search (b) Linear Search
(c) Quick Search
Q.31 Searching time is less for
(a) quick search (b) linear search
(c) binary search
Q.32 What is the average-case time complexity of bubble sort?
(a) 1 (b) O(log(n)
(c) O(n2)
Q.33 What is the worst-case time complexity of bubble sort?
(a) 1 (b) O(n)
(c) O(n2)
Q.34 What is the best-case time complexity of bubble sort?
(a) O(n) (b) O (nlog (n)
(c) O (n2)
Q.35 What is the worst-case time complexity of insertion sort?
(a) 1 (b) O(log(n)
(c) O(n2)
Q.36 What is the average-case time complexity of insertion sort?
(a) 1 (b) O (log(n)
(c) O(n2)
103
Q.37 What is the best-case time complexity of selection sort?
(a) 1 (b) O (nlog (n)
(c) O (n2)
Q.38 What is the average-case time complexity of selection sort?
(a) 1 (b) O (log (n))
(c) O (n2)
Q.39 What is the worst-case time complexity of selection sort?
(a) 1 (b) O (n)
(c) O (n2)
Q.40 What is the best-case time complexity of quick sort?
(a) 1 (b) O (nlog (n)
(c) O (n2)
Q.41 What is the average-case time complexity of quick sort?
(a) 1 (b) O (log (n)
(c) O (n2)
Q.42 What is the worst-case time complexity of quick sort?
(a) 1 (b) O (n)
(c) O (n2)
Q.43 What is the average- case time complexity of merge sort?
(a) 1 (b) O (nlog (n)
(c) O (n2)
Q.44 Merge sort is also called
(a) partition exchange Sort (b) exchange sort
(c) binary sort
Q.45 Bubble sort is also called
(a) partition exchange sort (b) exchange sort
(c) binary sort
Q.46 Time complexity is inversely proportional to
(a) space complexity (b) diverse complexity
(c) none
Q.47 What is the worst-case time complexity of merge sort?
(a) 1 (b) O (nlogn)
(c) O (n2)
Q.48 Bubble sort is yet another sorting technique which works on the design of
(a) Brute force (b) greedy technique
(c) divide and conquer (d) dynamic programming
Q.49 What are the methods available in storing sequential files?
(a) Straight merging
(b) Natural merging
(c) Polyphase sort
104
(d) Distribution of Initial runs
(e) All the above
Q.50 Linear search works on the principle of
(a) brute force (b) greedy technique
(c) divide and conquer (d) dynamic programming
Q.51 Linear search is also called
(a) sequential search (b) binary search
(c) both (d) none
Q.5 Binary search works on the strategy of
(a) divide and conquer (b) brute force
(c) greedy technique (d) dynamic programming
Q.53 Bubble sort is yet another sorting technique which works on the design of
(a) brute force (b) greedy technique
(c) divide and conquer (d) dynamic programming
Answers
1. (a) 2. (a) 3. (a) 4. (b)
5. (d) 6. (c) 7. (d) 8. (a)
9. (b) 10. (c) 11. (a) 12. (b)
13. (c) 14. (b) 15. (b) 16. (a)
17. (a) 18. (c) 19. (b) 20. (b)
21. (c) 22. (c) 23. (a) 24. (d)
25. (b) 26. (b) 27. (a) 28. (a)
29. (b) 30. (b) 31. (c) 32. (c)
33. (c) 34. (c) 35. (c) 36. (c)
37. (c) 38. (c) 39. (c) 40. (b)
41. (c) 42. (c) 43. (b) 44. (a)
45. (b) 46. (a) 47. (c) 48. (a)
49. (e) 50. (a) 51. (a) 52. (a)
53. (a)