18.10.26

CS301 Mid Term Papers

Getting ready for the midterm of CS301 (Data Structures)? Here is everything in one place: 198 solved MCQs, 63 subjective questions and 51 short notes, gathered from past papers and files shared by students. Duplicates are removed, and wherever a shared answer key turned out to be wrong it has been corrected, so you can trust what you revise. Use the Objective and Subjective buttons above to switch between the two sections, and tap Show answer only after you have tried the question yourself. Best of luck with your exam!

Part 1: MCQs

Q1. The data of the problem is of 2GB and the hard disk is of 1GB capacity, to solve this problem we should

  1. Use better data structures
  2. Increase the hard disk space
  3. Use the better algorithm
  4. Use as much data as we can store on the hard disk
Show answer

Answer: (b) Increase the hard disk space
Note: Taken from the course handout (page 5): when the data is larger than the disk, the space constraint is met by increasing the disk space.

Q2. An array is a group of consecutive related memory locations.

  1. True
  2. False
Show answer

Answer: (a) True

Q3. In an array we can store data elements of different types.

  1. True
  2. False
Show answer

Answer: (b) False

Q4. Which of the following is "TRUE" about arrays,

  1. We can increase the size of arrays after their creation.
  2. We can decrease the size of arrays after their creation.
  3. We can increase but can't decrease the size of arrays after their creation.
  4. We can neither increase nor decrease the array size after their creation.
Show answer

Answer: (d) We can neither increase nor decrease the array size after their creation.

Q5. Which one of the following statements is correct?

  1. Array size is fixed once it is created
  2. Link List size is fixed once it is created.
  3. Binary Search Tree size is fixed once it is created
  4. AVL Tree size is fixed once it is created
Show answer

Answer: (a) Array size is fixed once it is created

Q6. A subscript of an array may be an integer or an integer expression.

  1. True
  2. False
Show answer

Answer: (a) True

Q7. In the statement int x[6]; we cannot assign any value to x (for example x = 10;) because x is not an lvalue.

  1. True
  2. False
Show answer

Answer: (a) True
Note: Two shared keys said False, but the array name x is not an lvalue (it is not a variable you can assign to), so the statement is True.

Q8. In an array list the current element is

  1. The first element
  2. The middle element
  3. The last element
  4. The element where the current pointer points to
Show answer

Answer: (d) The element where the current pointer points to
Note: One shared key marked 'the first element'; the current element is the one the current pointer points to.

Q9. Which one of the following statements is NOT correct?

  1. Array size can be changed after its creation.
  2. Link List size can be changed after its creation
  3. Binary Search Tree size can be changed after its creation
  4. AVL Tree size can be changed after its creation
Show answer

Answer: (a) Array size can be changed after its creation.

Q10. Is a data structure that can grow easily dynamically at run time without having to copy existing elements?

  1. Array
  2. List
  3. Both of these
  4. None of these
Show answer

Answer: (b) List

Q11. Which of the following abstract data types are NOT used by Integer Abstract Data type group?

  1. short
  2. Int
  3. float
  4. long
Show answer

Answer: (c) float

Q12. Which one of the following is correct about pointers?

  1. They always point to different memory locations
  2. They may point to a single memory location
  3. The address of two pointer variables is same
  4. None of these
Show answer

Answer: (b) They may point to a single memory location

Q13. Suppose a pointer has been declared in main but has not assigned any variable address then

  1. That pointer points to First byte in main function
  2. That pointer contains a NULL value
  3. None of these
  4. That pointer points to any memory address
Show answer

Answer: (d) That pointer points to any memory address
Note: An uninitialized pointer holds a garbage address, it is not automatically NULL.

Q14. Which of the following is a non linear data structure?

  1. Linked List
  2. Stack
  3. Queue
  4. Tree
Show answer

Answer: (d) Tree

Q15. A Linear Data Structure is the data structure in which data elements are arranged in a sequence or a linear list. Which of the following is Non Linear Data Structure?

  1. Arrays
  2. LinkLists
  3. Binary Search Trees
  4. None of these
Show answer

Answer: (c) Binary Search Trees

Q16. Which of the following abstract data types are NOT used by the Integer abstract data type group?

  1. short
  2. int
  3. float
  4. long
Show answer

Answer: (c) float

Q17. Which one of the following statement is NOT correct .

  1. In linked list the elements are necessarily to be contiguous
  2. In linked list the elements may locate at far positions in the memory
  3. In linked list each element also has the next to it
  4. In an array the elements are contiguous
Show answer

Answer: (a) In linked list the elements are necessarily to be contiguous

Q18. Which one is a self- referential data type?

  1. Stack
  2. Queue
  3. Link list
  4. All of these
Show answer

Answer: (c) Link list
Note: One shared key said 'All of these'. A linked-list node holds a pointer to a node of its own type, which is what 'self-referential' means; stack and queue are not themselves self-referential.

Q19. Each node in doubly link list has,

  1. 1 pointer
  2. 2 pointers
  3. 3 pointers
  4. 4 pointers
Show answer

Answer: (b) 2 pointers

Q20. Doubly Linked List always has one NULL pointer.

  1. True
  2. False
Show answer

Answer: (b) False
Note: A doubly linked list has two NULL pointers: prev of the first node and next of the last node.

Q21. Suppose currentNode refers to a node in a linked list (using the Node class with member variables called data and nextNode). What statement changes currentNode so that it refers to the next node?

  1. currentNode ++;
  2. currentNode = nextNode;
  3. currentNode += nextNode;
  4. currentNode = currentNode->nextNode;
Show answer

Answer: (d) currentNode = currentNode->nextNode;

Q22. Suppose currentNode refers to a node in a linked list (using the Node class with member variables called data and nextNode). What boolean expression will be true when cursor refers to the tail node of the list?

  1. (currentNode == null)
  2. (currentNode->nextNode == null)
  3. (nextNode.data == null)
  4. (currentNode.data == 0.0)
Show answer

Answer: (b) (currentNode->nextNode == null)
Note: One shared key marked (currentNode == null), which is true after you have run off the end of the list, not when you are at the tail node.

Q23. Linked lists are collections of data items "lined up in a row" , insertions and deletions can be made only at the front and the back of a linked list.

  1. True
  2. False
Show answer

Answer: (b) False

Q24. In the linked list implementation of the stack class, where does the push member function places the new entry on the linked list?

  1. At the head
  2. At the tail
  3. After all other entries that are greater than the new entry.
  4. After all other entries that are smaller than the new entry.
Show answer

Answer: (a) At the head

Q25. Next item in a linked list is known as:

  1. Index
  2. Item
  3. Node
  4. Child
Show answer

Answer: (c) Node

Q26. Each entry which points to a null value in a singly linked list is known as:

  1. Node
  2. First Node
  3. Last Node
  4. Head Node
Show answer

Answer: (c) Last Node

Q27. The list abstract data type (ADT) is used to work with ordered or unordered sequences of items such as numbers or strings. Which implementation of the list ADT is best for answering questions such as "What is the item at position n?"

  1. Lists implemented with an array.
  2. Doubly-linked lists.
  3. Singly-linked lists.
  4. Doubly-linked or singly-linked lists are equally good.
Show answer

Answer: (a) Lists implemented with an array.

Q28. It will be efficient to place stack elements at the start of the list because insertion and removal take time.

  1. Variable
  2. Constant
  3. Inconsistent
  4. None of the above
Show answer

Answer: (b) Constant

Q29. The operation for adding an entry to a stack is traditionally called :

  1. add
  2. append
  3. insert
  4. push
Show answer

Answer: (d) push

Q30. The operation for removing an entry from a stack is traditionally called:

  1. delete
  2. peek
  3. pop
  4. remove
Show answer

Answer: (c) pop

Q31. is the maximum number of nodes that you can have on a stack-linked list ?

  1. Zero
  2. 2n (where n is the number of nodes in linked list)
  3. Any Number
  4. None of these
Show answer

Answer: (c) Any Number

Q32. Which of the following can be used to reverse a string value?

  1. Stack
  2. Queue
  3. Both of these
  4. None of these
Show answer

Answer: (a) Stack

Q33. Parameters in function call are passed using,

  1. Stack
  2. Queue
  3. Binary Search Tree
  4. AVL Tree
Show answer

Answer: (a) Stack

Q34. Which of the following stack operations could result in stack underflow?

  1. is empty
  2. pop
  3. push
  4. Two or more of the above answers
Show answer

Answer: (b) pop

Q35. Given a stack of n items, how many POP and PUSH operations need to be performed to remove the item at its bottom?

  1. 0 POP operation and 0 PUSH operation
  2. 1 POP operation and 1 PUSH operation
  3. n POP operations and n PUSH operations
  4. n POP operations and n-1 PUSH operations
  5. Unknown
Show answer

Answer: (d) n POP operations and n-1 PUSH operations
Note: You must pop all n items to reach the bottom one, then push the remaining n-1 items back.

Q36. The Bag ADT is like the List ADT. It does not store items in any particular order and it allows duplicates. The Bag class is efficiently implemented with a fixed array of capacity 4000, and insert appends the new item at the end of the array. After Bag b; b.insert(5); b.insert(4); b.insert(6); what are the values of b.size and b.data?

  1. b.size is 3, b.data[0] is 4, b.data[1] is 5, b.data[2] is 6
  2. b.size is 3, b.data[0] is 5, b.data[1] is 4, b.data[2] is 6
  3. b.size is 3, b.data[0] is 6, b.data[1] is 4, b.data[2] is 5
  4. b.size is 3, b.data[0] is 6, b.data[1] is 5, b.data[2] is 4
Show answer

Answer: (b) b.size is 3, b.data[0] is 5, b.data[1] is 4, b.data[2] is 6

Q37. "Entries in a stack are ordered." What is the meaning of this statement?

  1. A collection of stacks can be sorted.
  2. Stack entries may be compared with the < operation.
  3. The entries must be stored in a linked list.
  4. There is a first entry, a second entry, and so on.
Show answer

Answer: (d) There is a first entry, a second entry, and so on.

Q38. Which of the following applications may use a stack?

  1. A parentheses balancing program.
  2. Keeping track of local variables at run time.
  3. In-order traversal of a binary tree.
  4. All of the above.
Show answer

Answer: (d) All of the above.

Q39. ______ only removes items in the reverse order as they were entered.

  1. Stack
  2. Queue
  3. Both of these
  4. None of these
Show answer

Answer: (a) Stack

Q40. Consider the following pseudo code: declare a stack of characters while (there are more characters in the word to read) { read a character; push the character on the stack } while (the stack is not empty) { pop a character off the stack; write the character to the screen } What is written to the screen for the input "carpets"?

  1. serc
  2. carpets
  3. steprac
  4. ccaarrppeettss
Show answer

Answer: (c) steprac

Q41. Consider the following pseudo code: declare a stack of characters; while (there are more characters in the word to read) { read a character; push the character on the stack } while (the stack is not empty) { pop a character off the stack; write the character to the screen }. What is written to the screen for the input "apples"?

  1. selpa
  2. selppa
  3. apples
  4. aaappppplleess
Show answer

Answer: (b) selppa

Q42. A ______ is a linear list where ______ and ______ take place at the same end. This end is called the ______. Choose the correct words for the blanks.

  1. (i) queue (ii) insertion (iii) removals (iv) top
  2. (i) stack (ii) insertion (iii) removals (iv) bottom
  3. (i) stack (ii) insertion (iii) removals (iv) top
  4. (i) tree (ii) insertion (iii) removals (iv) top
Show answer

Answer: (c) (i) stack (ii) insertion (iii) removals (iv) top

Q43. Consider the following sequence of push operations in a stack: stack.push(1); stack.push(2); stack.push(3); stack.push(4); stack.push(5); stack.push(6). You may insert as many stack.pop() calls as you like between the pushes to get a desired output. Which of the following can NOT be an output?

  1. 1 2 3 4 5 6
  2. 3 2 5 4 1 6
  3. 3 4 2 5 6 1
  4. 3 4 2 6 1 5
  5. 3 4 2 1 6 5
Show answer

Answer: (d) 3 4 2 6 1 5
Note: After 3, 4, 2 are popped and 6 is pushed and popped, the stack holds 1 (bottom) and 5 (top), so 5 must come out before 1. Every other order is possible.

Q44. In the linked list implementation of the stack class, where does the push member function place the new entry on the linked list?

  1. At the head
  2. At the tail
  3. After all other entries that are greater than the new entry.
  4. After all other entries that are smaller than the new entry.
Show answer

Answer: (a) At the head

Q45. Queue follows,

  1. Last in First out
  2. First in Last out
  3. First in First out
  4. None of these
Show answer

Answer: (c) First in First out

Q46. A queue where the de-queue operation depends not on FIFO, is called a priority queue

  1. False
  2. True
Show answer

Answer: (b) True

Q47. We can add elements in QUEUE From

  1. Front
  2. Rear
  3. From Both Rare and Front
  4. None of these
Show answer

Answer: (b) Rear
Note: Items are added at the rear and removed from the front. Two shared keys marked 'Front'.

Q48. A queue is a----- data structure, whereas a stack is a ----- data structure.

  1. FIFO, LIFO
  2. LIFO,FIFO
  3. none of these
  4. both of these
Show answer

Answer: (a) FIFO, LIFO

Q49. Suppose we have a circular array implementation of the queue class, with ten items in the queue stored at data[2] through data[11]. The CAPACITY is 42, i.e., the array has been declared to be of size 42. Where does the push member function place the new entry in the array?

  1. data[1]
  2. data[2]
  3. data[11]
  4. data[12]
Show answer

Answer: (d) data[12]
Note: The array is circular: the rear is at data[11], so the next free slot is data[12].

Q50. I have implemented the queue with a linked list, keeping track of a front pointer and a rear pointer. Which of these pointers will change during an insertion into an EMPTY queue?

  1. Neither changes
  2. Only front pointer changes.
  3. Only rear pointer changes.
  4. Both change.
Show answer

Answer: (d) Both change.
Note: Inserting into an empty queue makes the new node both the front and the rear. One shared key said 'only rear'.

Q51. In the linked list implementation of the queue class, where does the insert member function place the new entry on the linked list?

  1. At the head
  2. At the tail
  3. After all other entries that are greater than the new entry.
  4. After all other entries that are smaller than the new entry.
Show answer

Answer: (b) At the tail

Q52. I have implemented the queue with a linked list, keeping track of a front pointer and a rear pointer. Which of these pointers will change during an insertion into a NONEMPTY queue?

  1. Neither changes
  2. Only front pointer changes.
  3. Only rear pointer changes.
  4. Both change.
Show answer

Answer: (c) Only rear pointer changes.

Q53. The following are statements related to queues. (i) The last item to be added to a queue is the first item to be removed (ii) A queue is a structure in which both ends are not used (iii) The last element hasn’t to wait until all elements preceding it on the queue are removed (iv) A queue is said to be a last-in-first-out list or LIFO data structure. Which of the above is/are related to normal queues?

  1. (iii) and (ii) only
  2. (i), (ii) and (iv) only
  3. (ii) and (iv) only
  4. None of the given options
Show answer

Answer: (d) None of the given options
Note: None of the four statements describes a normal queue: a queue is FIFO, both ends are used, and the last element has to wait for all earlier ones.

Q54. The following are linear data structures:

  1. Stacks
  2. Queues
  3. Both a & b
  4. None of the above
Show answer

Answer: (c) Both a & b

Q55. In the call by value methodology, a copy of the object is passed to the called function.

  1. False
  2. True
Show answer

Answer: (b) True

Q56. Consider the function X as under int X (int& Value) { return Value; } Now a and b are integers in a calling function. Which one of the following is a valid call to the above function X.

  1. a = X (b) ;
  2. a = X (&b) ;
  3. a = X (*b) ;
  4. None of the given options
Show answer

Answer: (a) a = X (b) ;
Note: With a reference parameter you pass the variable itself, so X(b) is the valid call. X(&b) would pass an address.

Q57. When should you use a const reference parameter?

  1. Whenever the parameter has huge size.
  2. Whenever the parameter has huge size, the function changes the parameter within its body, and you do NOT want these changes to alter the actual argument.
  3. Whenever the parameter has huge size, the function changes the parameter within its body, and you DO want these changes to alter the actual argument.
  4. Whenever the parameter has huge size, and the function does not change the parameter within its body.
Show answer

Answer: (d) Whenever the parameter has huge size, and the function does not change the parameter within its body.
Note: A const reference avoids copying a big object when the function does not need to change it. One shared key picked the 'function changes the parameter' option, which is not what const reference is for.

Q58. Here is the start of a C++ class declaration: class foo { public: void x(foo f); void y(const foo f); void z(foo f) const; ... Which of the three member functions can alter the PRIVATE member variables of the foo object that activates the function?

  1. Only x can alter the private member variables of the object that activates the function.
  2. Only y can alter the private member variables of the object that activates the function.
  3. Only z can alter the private member variables of the object that activates the function.
  4. Two of the functions can alter the private member variables of the object that activates the function.
Show answer

Answer: (d) Two of the functions can alter the private member variables of the object that activates the function.
Note: x and y are non-const member functions, so both can change the private data of the object that calls them; z is a const member function and cannot. (Only the const after the parameter list protects the calling object.)

Q59. What is the maximum depth of recursive calls a function may make?

  1. 1
  2. 2
  3. n (where n is the argument)
  4. There is no fixed maximum
Show answer

Answer: (d) There is no fixed maximum

Q60. Which one of the following calling methods does not change the original value of the argument in the calling function?

  1. None of the given options
  2. Call by passing the value of the argument
  3. Call by passing reference of the argument
  4. Call by passing the address of the argument
Show answer

Answer: (b) Call by passing the value of the argument

Q61. In a program a reference variable, say x, can be declared as

  1. int &x ;
  2. int *x ;
  3. int x ;
  4. None of the given options
Show answer

Answer: (a) int &x ;

Q62. Suppose that the class declaration of SomeClass includes the following function prototype. bool LessThan( SomeClass anotherObject ); Which of the following tests in the client code correctly compares two class objects alpha and beta?

  1. if (alpha < beta)
  2. if (alpha.LessThan(beta))
  3. if (LessThan(alpha, beta))
  4. if (LessThan(alpha).beta)
Show answer

Answer: (b) if (alpha.LessThan(beta))

Q63. Consider the following function: void test_a(int n) { cout << n << " "; if (n>0) test_a(n-2); } What is printed by the call test_a(4)?

  1. 4 2 0
  2. 0 2 4
  3. 0 2
  4. 2 4
Show answer

Answer: (a) 4 2 0

Q64. Here is a small function definition: void f(int i, int &k) { i = 1; k = 2; } A main program has two integer variables x and y, both with the value 0. It calls f(x, y). What are the values of x and y after f finishes?

  1. Both x and y are still 0.
  2. x is now 1, but y is still 0.
  3. x is still 0, but y is now 2.
  4. x is now 1, and y is now 2.
Show answer

Answer: (c) x is still 0, but y is now 2.
Note: i is passed by value (a copy), k is passed by reference.

Q65. In the following C++ code, how many function calls are made? int x, y, z; x = 2; y = 3 + x; z = foobar(x,y);

  1. 1
  2. 4
  3. 7
  4. 8
Show answer

Answer: (a) 1
Note: Only one function is called (foobar). The shared key marked 8, which the code does not support.

Q66. Consider this function: void quiz(int i) { if (i > 1) { quiz(i / 2); quiz(i / 2); } cout << "*"; } How many asterisks are printed by the call quiz(5)?

  1. 3
  2. 4
  3. 7
  4. 8
  5. Some other number
Show answer

Answer: (c) 7
Note: quiz(5) = quiz(2) + quiz(2) + 1 star; quiz(2) = quiz(1) + quiz(1) + 1 star = 3 stars; so 3 + 3 + 1 = 7.

Q67. When the compiler compiles your program, how is a recursive call treated differently than a non-recursive function call?

  1. Parameters are all treated as reference arguments
  2. Parameters are all treated as value arguments
  3. There is no duplication of local variables
  4. None of the above
Show answer

Answer: (d) None of the above

Q68. In which location do dynamic variables reside?

  1. The code segment.
  2. The data segment.
  3. The heap.
  4. The run-time stack.
Show answer

Answer: (c) The heap.

Q69. Non recursive calls are faster than the recursive calls.

  1. True
  2. False
Show answer

Answer: (a) True

Q70. Is it possible for a member function of a class to activate another member function of the same class?

  1. No.
  2. Yes, but only public member functions.
  3. Yes, but only private member functions.
  4. Yes, both public and private member functions can be activated within another member function.
Show answer

Answer: (d) Yes, both public and private member functions can be activated within another member function.

Q71. Consider this class definition: class quiz { public: quiz(); int f(); int g() const; private: double score; }; Which functions can carry out an assignment score = 1.0; to the private member variable score?

  1. Both f and g can carry out the assignment.
  2. f can carry out the assignment, but not g.
  3. g can carry out the assignment, but not f.
  4. Neither f nor g can carry out the assignment.
Show answer

Answer: (b) f can carry out the assignment, but not g.
Note: g is a const member function, so it cannot change the data members.

Q72. In C++, when allocating an array of objects, what constructor is used to initialize all of the objects in the array?

  1. The automatic copy constructor.
  2. The constructor specified at the declaration.
  3. The default constructor.
  4. None of the above.
Show answer

Answer: (c) The default constructor.

Q73. Given the class declaration class MyClass { public: ... void Func(); private: int n; }; what notation does the body of Func use to assign the value 3 to n?

  1. n = 3;
  2. MyClass.n = 3;
  3. MyClass::n = 3;
  4. someObject.n = 3;
  5. It can't be done, n is private.
Show answer

Answer: (a) n = 3;

Q74. The expression AB+C* is called?

  1. Prefix expression
  2. Postfix expression
  3. Infix expression
  4. None of these
Show answer

Answer: (b) Postfix expression

Q75. Each operator in a postfix expression refers to the previous operand(s).

  1. One
  2. Two
  3. Three
  4. Four
Show answer

Answer: (b) Two

Q76. “+” is a operator.

  1. Unary
  2. Binary
  3. Ternary
  4. None of the above
Show answer

Answer: (b) Binary

Q77. Which one of the following operators has higher priority than all of others?

  1. Multiplication operator
  2. Minus operator
  3. Plus operator
  4. Exponentiation operator
Show answer

Answer: (d) Exponentiation operator
Note: Exponentiation has the highest precedence. Some shared keys picked multiplication.

Q78. Consider the following infix expression. 5 + 6/2 If one converts the above expression into postfix, what would be the resultant expression?

  1. 56/ + 2
  2. 5 6 2 / +
  3. 5 6 / 2 +
  4. /62 + 5
Show answer

Answer: (b) 5 6 2 / +

Q79. What will be the postfix notation of 5+6/2?

  1. 56+/2
  2. 562+/
  3. 562/+
  4. 5+62/
Show answer

Answer: (c) 562/+

Q80. What will be postfix expression of the following infix expression? Infix Expression : a+b*c-d

  1. ab+c*d-
  2. abc*+d-
  3. abc+*d-
  4. abcd+*-
Show answer

Answer: (b) abc*+d-

Q81. What will be the valid postfix notation of A+B*C-D?

  1. ABC+*D-
  2. ABC*+D-
  3. ABCD+-*
  4. AB+D*C
Show answer

Answer: (b) ABC*+D-

Q82. Which one of the following is a valid postfix expression?

  1. ab+c*d-
  2. abc*+d-
  3. abc+*d-
  4. (abc*)+d-
Show answer

Answer: (b) abc*+d-
Note: Options (a), (b) and (c) are all well-formed postfix strings; the shared files keep (b). Option (d) is the only invalid one, because postfix never uses parentheses.

Q83. Consider the following infix expression: 3 + 5 * 6 – 7 * (8 + 5) Which of the following is a correct equivalent expression(s) for the above?

  1. 3 6 5 + * 7 5 8 + - *
  2. 3 6 5 7 5 8 + * + - *
  3. 3 5 6 + * 7 8 5 + - *
  4. 3 5 6 * + 7 8 5 + * -
Show answer

Answer: (d) 3 5 6 * + 7 8 5 + * -

Q84. When an operator is used in between two operands, which type of notation is this?

  1. Prefix
  2. Postfix
  3. Infix
  4. None of the above
Show answer

Answer: (c) Infix

Q85. The tree data structure is a

  1. Linear data structure
  2. Non-linear data structure
  3. Graphical data structure
  4. Data structure like queue
Show answer

Answer: (b) Non-linear data structure

Q86. The nodes with no successor are called

  1. Root Nodes
  2. Leaf Nodes
  3. Both of these
  4. None of these
Show answer

Answer: (b) Leaf Nodes

Q87. Consider the following statements. (i) A binary tree can contain at least 2L Nodes at level L. (ii) A complete binary tree of depth d is a binary tree that contains 2L Nodes at each level L between 0 and d, both inclusive. (iii) The total number of nodes (Tn ) in a complete binary tree of depth d is 2 d+1 - 1 . (iv) The height of the complete binary tree can be written as h = log 2 (Tn+1)-1 where Tn is Total number of Nodes. Which one of the following is correct in respect of the above statements regarding the Binary trees?

  1. (i) and (iii) only
  2. (i), (ii) and (iii) only
  3. (ii) and (iii) only
  4. (ii), (iii) and (iv) only
Show answer

Answer: (d) (ii), (iii) and (iv) only
Note: Statement (i) is wrong: a binary tree has AT MOST 2^L nodes at level L.

Q88. In which of the traversal method, the recursive calls can be used to traverse a binary tree ?

  1. In preorder traversal only
  2. In inorder traversal only
  3. In postorder traversal only
  4. All of the given options
Show answer

Answer: (d) All of the given options

Q89. is a binary tree where every node has a value, every node's left subtree contains only values less than or equal to the node's value, and every node's right subtree contains only values that are greater then or equal?

  1. Strictly Binary Tree
  2. Binary Search tree
  3. AVL tree
  4. All of these
Show answer

Answer: (b) Binary Search tree

Q90. Each node in Binary Search Tree has

  1. 1 pointer
  2. 2 pointers
  3. 3 pointers
  4. 4 pointers
Show answer

Answer: (b) 2 pointers

Q91. Which of the following statements regarding a binary tree is NOT correct?

  1. A binary tree can contain at least 2^L nodes at level L.
  2. A complete binary tree of depth d is a binary tree that contains 2^L nodes at each level L between 0 and d, both inclusive.
  3. The total number of nodes (Tn) in a complete binary tree of depth d is 2^(d+1) - 1.
  4. The height of a complete binary tree can be written as h = log2(Tn+1) - 1, where Tn is the total number of nodes.
Show answer

Answer: (a) A binary tree can contain at least 2^L nodes at level L.
Note: A binary tree has at most (not at least) 2^L nodes at level L.

Q92. Four statements about trees are below. Three of them are correct. Which one is INCORRECT?

  1. Trees are recursively defined multi-dimensional data structures tree
  2. The order of a tree indicates a maximum number of children allowed at each node of the
  3. A search tree is a special type of tree where all values (i.e. keys) are ordered
  4. If Tree1's size is greater than Tree2's size, then the height of Tree1 must also be greater than Tree2's height.
Show answer

Answer: (d) If Tree1's size is greater than Tree2's size, then the height of Tree1 must also be greater than Tree2's height.
Note: A tree with more nodes does not have to be taller (a wide, shallow tree can have more nodes than a tall, thin one).

Q93. Select the one FALSE statement about binary trees:

  1. Every binary tree has at least one node.
  2. Every non-empty tree has exactly one root node.
  3. Every node has at most two children.
  4. Every non-root node has exactly one parent.
Show answer

Answer: (a) Every binary tree has at least one node.
Note: The empty tree is also a binary tree. One shared key marked 'every non-empty tree has exactly one root node', which is true.

Q94. A binary tree with 33 internal nodes has ______ links to internal nodes.

  1. 31
  2. 32
  3. 33
  4. 66
Show answer

Answer: (b) 32
Note: Every internal node except the root has exactly one link coming into it, so 33 - 1 = 32.

Q95. If there are 23 external nodes in a binary tree, what will be the number of internal nodes in this binary tree?

  1. 23
  2. 24
  3. 21
  4. 22
Show answer

Answer: (d) 22
Note: In a binary tree where every internal node has two children, internal nodes = external nodes - 1.

Q96. If there are N external nodes in a binary tree, what will be the number of internal nodes in this binary tree?

  1. N - 1
  2. N + 1
  3. N + 2
  4. N
Show answer

Answer: (a) N - 1

Q97. Suppose T is a binary tree with 14 nodes. What is the minimum possible depth of T?

  1. 0
  2. 3
  3. 4
  4. 5
Show answer

Answer: (b) 3
Note: Levels 0 to 3 can hold 1 + 2 + 4 + 8 = 15 nodes, so 14 nodes fit in depth 3.

Q98. Suppose n is the number of nodes in a complete Binary Tree then maximum steps required for a search operation are,

  1. Log2 (n+1) -1
  2. Log2 (n+1)
  3. Log2 (n) – 1
  4. Log2 (n)
Show answer

Answer: (a) Log2 (n+1) -1
Note: For a complete binary tree with n nodes, the depth is log2(n+1) - 1.

Q99. Consider the following tree: 14 is the root with children 2 and 11; node 2 has children 1 and 3; node 11 has children 10 and 30; node 10 has a left child 7; node 30 has a left child 40. How many of the nodes have at least one sibling?

  1. 8
  2. 7
  3. 5
  4. 6
Show answer

Answer: (d) 6
Note: Nodes 2, 11, 1, 3, 10 and 30 have siblings. Nodes 7 and 40 are only children, and 14 is the root.

Q100. Consider the same tree (14 is the root with children 2 and 11; 2 has children 1 and 3; 11 has children 10 and 30; 10 has a left child 7; 30 has a left child 40). How many descendants does the root have?

  1. 5
  2. 6
  3. 7
  4. 8
Show answer

Answer: (d) 8
Note: Every other node is a descendant of the root: 9 nodes in total minus the root = 8.

Q101. The nodes of a binary tree have data 1, 2, 3, 4. The in-order traversal of the tree yields 2, 1, 4, 3. The postorder traversal is 2, 4, 3, 1. The root of the tree is at level 0. In this binary tree, which value is at the root?

  1. 1
  2. 2
  3. 3
  4. 4
  5. none
Show answer

Answer: (a) 1
Note: The last item of the postorder traversal is the root.

Q102. (Same tree: in-order 2, 1, 4, 3; postorder 2, 4, 3, 1.) Which value is in the left child of the root?

  1. 1
  2. 2
  3. 3
  4. 4
  5. none
Show answer

Answer: (b) 2

Q103. (Same tree: in-order 2, 1, 4, 3; postorder 2, 4, 3, 1.) Which value is in the right child of the root?

  1. 1
  2. 2
  3. 3
  4. 4
  5. none
Show answer

Answer: (c) 3

Q104. (Same tree: in-order 2, 1, 4, 3; postorder 2, 4, 3, 1.) Which value is in a node at level 2 and is the left child of a node at level 1?

  1. 1
  2. 2
  3. 3
  4. 4
  5. none
Show answer

Answer: (d) 4

Q105. (Same tree: in-order 2, 1, 4, 3; postorder 2, 4, 3, 1.) Which value is in a node at level 2 and is the right child of a node at level 1?

  1. 1
  2. 2
  3. 3
  4. 4
  5. none
Show answer

Answer: (e) none
Note: The tree is: root 1, left child 2, right child 3, and 3 has a left child 4. No level-2 node is a right child.

Q106. The difference between a binary tree and a binary search tree is that ,a binary search tree has

  1. two children per node whereas a binary tree can have none, one, or two children per node
  2. in binary search tree nodes are inserted based on the values they contain
  3. in binary tree nodes are inserted based on the values they contain
  4. none of these
Show answer

Answer: (b) in binary search tree nodes are inserted based on the values they contain
Note: A BST can also have zero, one or two children per node; what makes it a search tree is how values are placed. One shared key picked option (a).

Q107. A binary search tree should have a minimum of ______ node(s) at each level.

  1. One
  2. Two
  3. Three
  4. Four
Show answer

Answer: (a) One
Note: A degenerate BST (a chain) has exactly one node per level. Two shared keys marked 'Two', which does not hold for every BST.

Q108. Consider a binary search tree (BST) whose root is A. A has children B (left) and C (right); B has children D and E; C has children F and G; D has a right child H; E has a right child I; F has children J and K; G has children L and M. If node A is deleted, which two nodes are the candidates to take its place?

  1. J and I
  2. H and E
  3. D and E
  4. L and M
Show answer

Answer: (a) J and I
Note: The candidates are the in-order predecessor (the rightmost node of the left subtree: I) and the in-order successor (the leftmost node of the right subtree: J). The shared key said L and M.

Q109. Below is a binary search tree: root 50; 50 has children 20 and 80; 20 has children 10 and 40; 40 has a left child 30; 80 has children 60 and 90; 60 has a right child 70. If we delete the value 50 using the algorithm we discussed, what value will be in the root of the remaining tree?

  1. 50
  2. 60
  3. 70
  4. 80
Show answer

Answer: (b) 60
Note: The root is replaced by the smallest value of its right subtree, which is 60 (the largest value of the left subtree, 40, is the other legal choice but is not offered). Shared keys marked 70 and 80.

Q110. Is this a correct statement? "A node cannot be deleted when the node to be deleted has both left and right subtrees."

  1. Yes
  2. No
Show answer

Answer: (b) No
Note: It can: replace the node with its in-order successor (or predecessor).

Q111. Deleting a leaf node in a binary search tree involves setting ______ pointer(s) of that node's parent as null.

  1. 1
  2. 2
  3. 3
  4. 4
Show answer

Answer: (a) 1

Q112. Binary search is an algorithm of searching, used with the ______ data.

  1. Sorted
  2. Unsorted
  3. Heterogeneous
  4. Random
Show answer

Answer: (a) Sorted

Q113. What requirement is placed on an array so that binary search may be used to locate an entry?

  1. The array elements must form a heap.
  2. The array must have at least 2 entries.
  3. The array must be sorted.
  4. The array's size must be a power of two.
Show answer

Answer: (c) The array must be sorted.

Q114. BST is a ______ structure:

  1. Linear
  2. Non Linear
  3. Circular
  4. None of the above
Show answer

Answer: (b) Non Linear

Q115. We access elements in AVL Tree in,

  1. Linear way only
  2. Non Linear way only
  3. Both linear and non linear ways
  4. None of the given options.
Show answer

Answer: (b) Non Linear way only

Q116. AVL Tree is,

  1. Non Linear data structure
  2. Linear data structure
  3. Hybrid data structure (Mixture of Linear and Non Linear)
  4. None of the given options.
Show answer

Answer: (a) Non Linear data structure

Q117. Every AVL tree is a:

  1. Binary Tree
  2. Complete Binary Tree
  3. None of these
  4. Binary Search Tree
Show answer

Answer: (d) Binary Search Tree
Note: Every AVL tree is a binary search tree (and therefore also a binary tree); the most specific answer is Binary Search Tree.

Q118. A tree is an AVL tree if

  1. Any one node fulfills the AVL condition
  2. At least half of the nodes fulfill the AVL condition
  3. All the nodes fulfill the AVL condition
  4. None of the given options
Show answer

Answer: (c) All the nodes fulfill the AVL condition

Q119. Searching an element in an AVL tree take maximum in AVL tree,

  1. Log2(n+1) time (where n is no. of nodes
  2. Log2(n+1) -1
  3. 1.44 Log2n
  4. 1.66 Log2n
Show answer

Answer: (c) 1.44 Log2n
Note: The height of an AVL tree, and so a search, is at most about 1.44 log2 n.

Q120. To check the depth of an AVL tree, the following time will be taken:

  1. 1.66 Log2 n
  2. 1.44 Log2 n
  3. Log2 (n+1) - 1
  4. 1.66 Log2 n (n+1)
Show answer

Answer: (b) 1.44 Log2 n

Q121. There is/are case/s for rotation in an AVL tree,

  1. 1
  2. 3
  3. 2
  4. 4
Show answer

Answer: (d) 4
Note: The four cases are left-left, right-right (single rotation) and left-right, right-left (double rotation).

Q122. Let's call the node that requires re-balancing a. Consider the two cases: 1) an insertion into the left subtree of the left child of a, 2) an insertion into the right subtree of the right child of a. Which of the following statements is correct about these two cases?

  1. The insertion occurs outside (left-left or right-right) in cases 1 and 2, and a single rotation can fix the balance in these two cases.
  2. The insertion occurs inside in cases 1 and 2, and a single rotation cannot fix the balance in these two cases.
Show answer

Answer: (a) The insertion occurs outside (left-left or right-right) in cases 1 and 2, and a single rotation can fix the balance in these two cases.

Q123. In the worst case, deletion in an AVL tree requires:

  1. Only one rotation
  2. Rotation at each non-leaf node
  3. Rotation at each leaf node
  4. Rotations equal to log2 N
Show answer

Answer: (d) Rotations equal to log2 N
Note: After a deletion, imbalance can occur at every level on the way back to the root, so up to about log2 N rotations are needed.

Q124. Suppose you implement a heap (with the largest element on top) in an array. Which of the following arrays cannot possibly be a heap?

  1. 7 6 5 4 3 2 1
  2. 7 3 6 2 1 4 5
  3. 7 6 4 3 5 2 1
  4. 7 3 6 4 2 5 1
Show answer

Answer: (d) 7 3 6 4 2 5 1
Note: In the last array, node 3 has a child 4 that is larger than it.

Q125. Suppose you implement a min heap (smallest element on top) in an array. Which of the following arrays cannot possibly be a heap?

  1. 16, 18, 20, 22, 24, 28, 30
  2. 16, 20, 18, 24, 22, 30, 28
  3. 16, 24, 18, 28, 30, 20, 22
  4. 16, 24, 20, 30, 28, 18, 22
Show answer

Answer: (d) 16, 24, 20, 30, 28, 18, 22
Note: In the last array, node 20 (index 3) has a child 18 that is smaller than it.

Q126. Consider a min heap represented by the array 11, 22, 33, 44, 55. After inserting a node with value 66, which of the following is the updated min heap?

  1. 11, 22, 33, 44, 55, 66
  2. 11, 22, 33, 44, 66, 55
  3. 11, 22, 33, 66, 44, 55
  4. 11, 22, 66, 33, 44, 55
Show answer

Answer: (a) 11, 22, 33, 44, 55, 66
Note: 66 is larger than its parent (33), so it stays where it is inserted.

Q127. Consider a min heap represented by the array 3, 4, 6, 7, 5. After calling deleteMin(), which of the following is the updated min heap?

  1. 4, 6, 7, 5
  2. 6, 7, 5, 4
  3. 4, 5, 6, 7
  4. 4, 6, 5, 7
Show answer

Answer: (c) 4, 5, 6, 7
Note: Remove 3, move the last item (5) to the root, then percolate it down: swap with the smaller child 4, giving 4, 5, 6, 7.

Q128. We can build a heap in ______ time.

  1. Linear
  2. Exponential
  3. Polynomial
  4. None of the given options
Show answer

Answer: (a) Linear

Q129. Which formula is the best approximation for the depth of a heap with n nodes?

  1. log (base 2) of n
  2. The number of digits in n (base 10), e.g., 145 has three digits
  3. The square root of n
  4. n
Show answer

Answer: (a) log (base 2) of n

Q130. Which traversal gives a decreasing order of elements in a heap where the max element is stored at the top?

  1. post-order
  2. level-order
  3. inorder
  4. None of the given options
Show answer

Answer: (d) None of the given options
Note: No traversal of a heap lists the elements in sorted order.

Q131. Suppose we are sorting an array of eight integers using quick sort, and we have just finished the first partitioning with the array looking like this: 2 5 1 7 9 12 11 10. Which statement is correct?

  1. The pivot could be either the 7 or the 9.
  2. The pivot could be the 7, but it is not the 9.
  3. The pivot is not the 7, but it could be the 9.
  4. Neither the 7 nor the 9 is the pivot.
Show answer

Answer: (a) The pivot could be either the 7 or the 9.
Note: After partitioning, the pivot sits in its final place: everything to its left is smaller and everything to its right is larger. That holds for both 7 and 9.

Q132. Which one of the following is NOT a property of an equivalence relation?

  1. Reflexive
  2. Symmetric
  3. Transitive
  4. Associative
Show answer

Answer: (d) Associative

Q133. The definition of the transitivity property is:

  1. For all elements x member of S, x R x
  2. For all elements x and y, x R y if and only if y R x
  3. For all elements x, y and z, if x R y and y R z then x R z
  4. For all elements w, x, y and z, if x R y and w R z then x R z
Show answer

Answer: (c) For all elements x, y and z, if x R y and y R z then x R z

Q134. Union is a ______ time operation.

  1. Constant
  2. Polynomial
  3. Exponential
  4. None of the given options
Show answer

Answer: (a) Constant

Q135. Which of the following statements is correct?

  1. A threaded binary tree is a binary tree in which every node that does not have a left child has a THREAD (a link) to its INORDER successor.
  2. A threaded binary tree is a binary tree in which every node that does not have a right child has a THREAD (a link) to its PREORDER successor.
  3. A threaded binary tree is a binary tree in which every node that does not have a right child has a THREAD (a link) to its INORDER successor.
  4. A threaded binary tree is a binary tree in which every node that does not have a right child has a THREAD (a link) to its POSTORDER successor.
Show answer

Answer: (c) A threaded binary tree is a binary tree in which every node that does not have a right child has a THREAD (a link) to its INORDER successor.

Q136. By using a ______ we avoid the recursive method of traversing a tree, which makes use of stacks and consumes a lot of memory and time.

  1. Binary tree only
  2. Threaded binary tree
  3. Heap data structure
  4. Huffman encoding
Show answer

Answer: (b) Threaded binary tree

Q137. Which of the following statements is NOT true about a threaded binary tree?

  1. The right thread of the right-most node points to the dummy node.
  2. The left thread of the left-most node points to the dummy node.
  3. The left pointer of the dummy node points to the root node of the tree.
  4. The left thread of the right-most node points to the dummy node.
Show answer

Answer: (d) The left thread of the right-most node points to the dummy node.
Note: The left thread of the right-most node points to its in-order predecessor, not to the dummy node.

Q138. When an executable program is run, it is loaded in the memory and becomes a ______.

  1. Thread
  2. .h file
  3. Process
  4. None of the above
Show answer

Answer: (c) Process

Q139. Local variables of a function are stored in:

  1. Binary Search Tree
  2. Stack
  3. Queue
  4. AVL Tree
Show answer

Answer: (b) Stack

Q140. In ______ the 'next' returns false when it reaches the last node, because the next field of the last node is set to NULL.

  1. Circular linked list
  2. Triple linked list
  3. Singly linked list
  4. None of the above
Show answer

Answer: (c) Singly linked list

Q141. Compiler uses which one of the following in function calls?

  1. Stack
  2. Queue
  3. Binary Search Tree
  4. AVL Tree
Show answer

Answer: (a) Stack

Q142. Stack and Queue can be implemented using ______.

  1. Singly Link List
  2. Binary Tree
  3. Binary Search Tree
  4. AVL Tree
Show answer

Answer: (a) Singly Link List

Q143. Which boolean expression indicates whether the numbers in two nodes (p and q) are the same? Assume that neither p nor q is null.

  1. p == q
  2. p.data == q.data
  3. p.nextNode == q.nextNode
  4. p.data == q
Show answer

Answer: (b) p.data == q.data

Q144. Which of the following is not a data structure?

  1. Linked list
  2. Queue
  3. Stack
  4. Memory cell
Show answer

Answer: (d) Memory cell

Q145. In an array list, the worst case of removing an element is:

  1. To remove an element from the end of the list
  2. To remove an element from the middle of the list
  3. To remove an element from the start of the list
  4. We cannot remove an element from an array list
Show answer

Answer: (c) To remove an element from the start of the list
Note: Removing from the start shifts all the remaining elements.

Q146. In ______ a programmer uses two pointers in the node, one to point to the next node and the other to point to the previous node.

  1. Linked list
  2. Doubly linked list
  3. Array
  4. Structure
Show answer

Answer: (b) Doubly linked list

Q147. Which of the following is known as the 'Last-In, First-Out' (LIFO) data structure?

  1. Linked List
  2. Stack
  3. Queue
  4. Tree
Show answer

Answer: (b) Stack

Q148. In the calling function, after the execution of the called function, the program continues its execution from the ______ after the function call.

  1. Previous line
  2. Next line
  3. Beginning
  4. None of the above
Show answer

Answer: (b) Next line

Q149. The smallest value element in a binary search tree (each node with left and right pointers) lies at:

  1. Root node
  2. Left child of the root
  3. Right most node
  4. Left most node
Show answer

Answer: (d) Left most node

Q150. To represent a hierarchical relationship between elements, which data structure is suitable?

  1. Dequeue
  2. Priority queue
  3. Stack
  4. Tree
Show answer

Answer: (d) Tree

Q151. A binary tree whose every node has either zero or two children is called:

  1. Complete binary tree
  2. Binary search tree
  3. Strictly binary tree
  4. None of the above
Show answer

Answer: (c) Strictly binary tree

Q152. Which is the correct function call for the following function that calculates a cube? int cube(int& num)

  1. cube(&num)
  2. cube(&&num)
  3. cube(*num)
  4. cube(num)
Show answer

Answer: (d) cube(num)

Q153. In-order traversal of a binary search tree visits the data in:

  1. Non-sorted order
  2. Random order
  3. Sorted order
  4. None of the given
Show answer

Answer: (c) Sorted order

Q154. The ______ of a node in a binary tree is defined as the height of its left subtree minus the height of its right subtree.

  1. Height
  2. Balance
  3. Width
  4. None of the above
Show answer

Answer: (b) Balance

Q155. The order of operands in postfix is the ______ as that in infix.

  1. Different
  2. Same
  3. Unusual
  4. None of the above
Show answer

Answer: (b) Same

Q156. STL is a ______ that is a part of the official standard of C++.

  1. C program file
  2. .h file
  3. .cpp file
  4. Library
Show answer

Answer: (d) Library

Q157. The percolateDown procedure moves the smaller value ______ and the bigger value ______.

  1. left, right
  2. right, left
  3. down, up
  4. up, down
Show answer

Answer: (d) up, down

Q158. Suppose the values 20, 23, 25, 10, 12, 13 are inserted in this order in constructing an AVL tree. When will the first rotation take place?

  1. after inserting node 23
  2. after inserting node 25
  3. after inserting node 12
  4. after inserting node 10
Show answer

Answer: (b) after inserting node 25
Note: 20, 23, 25 forms a right-right chain, so node 20 becomes unbalanced as soon as 25 is inserted.

Q159. The new operation in C++ for dynamically allocating memory returns:

  1. Size of the memory it has allocated
  2. Pointer to the memory it has allocated
  3. Both size and pointer to the memory it has allocated
  4. Value of the memory it has allocated
Show answer

Answer: (b) Pointer to the memory it has allocated

Q160. The next field in the last node of a singly-linked list is set to ______.

  1. NAN
  2. 1
  3. NULL
  4. -1
Show answer

Answer: (c) NULL

Q161. A queue where the dequeue operation does not depend upon FIFO is called:

  1. enqueue
  2. simple queue
  3. stack
  4. priority queue
Show answer

Answer: (d) priority queue

Q162. a * (b + c) - d is an example of ______ expression.

  1. infix
  2. prefix
  3. postfix
  4. allfix
Show answer

Answer: (a) infix

Q163. Which of the following statements is NOT true for a reference variable?

  1. Once a reference is created, it cannot later be made to reference another object.
  2. References cannot be NULL.
  3. References can be uninitialized.
  4. It is not possible to refer directly to a reference object after it is defined.
Show answer

Answer: (c) References can be uninitialized.
Note: A reference must be initialised when it is declared.

Q164. In the post-order traversal of a binary search tree, nodes are processed as:

  1. Left-subtree, Right-subtree, Root
  2. Right-subtree, Root, Left-subtree
  3. Left-subtree, Root, Right-subtree
  4. Right-subtree, Left-subtree, Root
Show answer

Answer: (a) Left-subtree, Right-subtree, Root

Q165. The main use of an AVL tree is:

  1. Searching of data
  2. Storing of data
  3. Insertion of data
  4. Security of data
Show answer

Answer: (a) Searching of data

Q166. A queue is a data structure where elements are:

  1. inserted at the front and removed from the back.
  2. inserted and removed from the top.
  3. inserted at the back and removed from the front.
  4. inserted and removed from both ends.
Show answer

Answer: (c) inserted at the back and removed from the front.

Q167. If the numbers 5, 222, 4, 48 are inserted in a queue, which one will be removed first?

  1. 48
  2. 4
  3. 222
  4. 5
Show answer

Answer: (d) 5

Q168. Recursive function calls are implemented internally using a ______ data structure.

  1. Stack
  2. Link-List
  3. Tree
  4. Queue
Show answer

Answer: (a) Stack

Q169. Memory allocated using the new operator is released:

  1. When we set the pointer to NULL
  2. When our program terminates
  3. When we delete the memory using the delete operator
  4. When we set the pointer to zero
Show answer

Answer: (c) When we delete the memory using the delete operator

Q170. The 'function definition' is similar to the 'function call' except that a function call does not need:

  1. Number of arguments
  2. Type of arguments
  3. Order of arguments
  4. Return type
Show answer

Answer: (d) Return type

Q171. In a complete binary tree of depth 4, the number of non-leaf nodes is:

  1. 7
  2. 8
  3. 15
  4. 16
Show answer

Answer: (c) 15
Note: Levels 0 to 3 are all non-leaf: 1 + 2 + 4 + 8 = 15 (level 4 holds the 16 leaves).

Q172. Which statement is about the heap area when an executable is run?

  1. The operating system makes a process inside memory
  2. Contains the binary version of the actual code
  3. A section for static data including global variables
  4. Utilized at the time of memory allocation in a dynamic manner
Show answer

Answer: (d) Utilized at the time of memory allocation in a dynamic manner

Q173. A linked list always contains elements that can be described as:

  1. Redundant
  2. Recursive
  3. Self-referential
  4. Bidirectional
Show answer

Answer: (c) Self-referential

Q174. One difference between a queue and a stack is:

  1. Queues require dynamic memory, but stacks do not.
  2. Stacks require dynamic memory, but queues do not.
  3. Queues use two ends of the structure, stacks use only one.
  4. Stacks use two ends of the structure, queues use only one.
Show answer

Answer: (c) Queues use two ends of the structure, stacks use only one.

Q175. New items are added at the ______ of the stack.

  1. Bottom
  2. Middle
  3. Top
  4. Center
Show answer

Answer: (c) Top

Q176. Which of the following operations returns the 'most recently entered value' from the stack?

  1. Push
  2. Recent
  3. Top
  4. First
Show answer

Answer: (c) Top

Q177. Which of the following is correct about an AVL tree?

  1. It is identical to a BST except the heights of the left and right subtrees can differ by at least 1.
  2. It is identical to a BST except the heights of the left and right subtrees must differ by at least 1.
  3. It is not identical to a BST, it is a totally different kind of tree.
  4. It is identical to a BST except the heights of the left and right subtrees can differ by at most 1.
Show answer

Answer: (d) It is identical to a BST except the heights of the left and right subtrees can differ by at most 1.

Q178. In the statement int& a = b;

  1. a and b point to two different memory locations
  2. a and b are two different names of the same memory location
  3. a and b are two different variable names
  4. a holds the address of variable b
Show answer

Answer: (b) a and b are two different names of the same memory location

Q179. The variables which are destroyed automatically when a function's execution ends are:

  1. Global variables
  2. Local variables defined inside the function body
  3. Variables (objects) defined inside the function body dynamically
  4. Variables (objects) defined inside the function body statically
Show answer

Answer: (b) Local variables defined inside the function body

Q180. Insertion in a linked list can be done at:

  1. Front only
  2. Back only
  3. Somewhere in the middle only
  4. Front, back and somewhere in the middle
Show answer

Answer: (d) Front, back and somewhere in the middle

Q181. An array is a group of ______ memory locations.

  1. Scattered
  2. Isolated
  3. Random (non-consecutive)
  4. Consecutive
Show answer

Answer: (d) Consecutive

Q182. Non-recursive calls are faster than which of the following calls?

  1. Parameterized
  2. Recursive
  3. Function
  4. Non-Function
Show answer

Answer: (b) Recursive

Q183. The balance of a node is the result of 'height of left subtree' ______ 'height of right subtree'.

  1. Plus
  2. Minus
  3. Multiply
  4. Divided by
Show answer

Answer: (b) Minus

Q184. The simplest case in a BST to delete a node is when:

  1. the node to be deleted is the root node
  2. the node to be deleted has both left and right children
  3. the node to be deleted has only one child
  4. the node to be deleted is a leaf node
Show answer

Answer: (d) the node to be deleted is a leaf node

Q185. If class A defines class B as its friend, then:

  1. Class A can access private members of class B
  2. Class B can access only the public members of class A
  3. Class A can access only the public members of class B
  4. Class B can access private members of class A
Show answer

Answer: (d) Class B can access private members of class A

Q186. In a simple implementation of a stack, the isFull method is used due to:

  1. Limitation of array
  2. Strength of array
  3. Linked list connectivity
  4. Complexity of linked list
Show answer

Answer: (a) Limitation of array

Q187. What will be the result of the following postfix expression? 1 2 3 * + 2 -

  1. 3
  2. 4
  3. 5
  4. 10
Show answer

Answer: (c) 5
Note: 2 * 3 = 6; 1 + 6 = 7; 7 - 2 = 5.

Q188. While deleting a node from a Binary Search Tree (BST), how many cases do we have to take care of?

  1. 4
  2. 1
  3. 2
  4. 3
Show answer

Answer: (d) 3
Note: The node is a leaf, has one child, or has two children.

Q189. In the statement int& y = x;

  1. y is a pointer variable of type int
  2. y is a normal variable of type int
  3. y is an address variable
  4. y is a reference variable
Show answer

Answer: (d) y is a reference variable

Q190. Consider the following sequence of push operations in a stack: stack.push(7); stack.push(8); stack.push(9); stack.push(10); stack.push(11); stack.push(12). Pops may be inserted anywhere between the pushes. Which of the following can NOT be the order in which the items are popped?

  1. 7 8 9 10 11 12
  2. 9 8 11 10 7 12
  3. 9 10 8 11 12 7
  4. 9 10 8 12 7 11
Show answer

Answer: (d) 9 10 8 12 7 11
Note: After 9, 10 and 8 are popped, the stack holds only 7; then 11 and 12 are pushed, so 11 is above 7 and 7 cannot come out before 11. Every other order is possible.

Q191. A compound data structure can have multiple data items of the same type or of different types. Which of the following can be considered a compound data structure?

  1. Arrays
  2. Link Lists
  3. Binary Search Trees
  4. All of the given options
Show answer

Answer: (d) All of the given options

Answers to double-check

These questions are placed last because their answer keys could not be fully verified against the handouts. Confirm them from your own notes.

Q192. In C what is the operation that you can not do with primitive types?

  1. Assign a value to primitive type using a literal
  2. Declare primitive types to be constant using the Const keyword
  3. Create a new instance of primitive type with New keyword
  4. None of these
Show answer

Answer: (c) Create a new instance of primitive type with New keyword
Note: The question says C, but C has no new keyword at all, so 'create a new instance with new' is the operation that cannot be done. Source key agrees; wording is doubtful.

Q193. Addition of new items in a stack makes the pointer ______ by 2:

  1. Increment, bits
  2. Increment, bytes
  3. Decrement, bits
  4. Decrement, bytes
Show answer

Answer: (d) Decrement, bytes
Note: Taken from the paper's key. The stack grows downward in memory, so each push decrements the stack pointer; the 'by 2 bytes' detail comes from the paper and could not be checked against the handout.

Q194. The following is a segment of a C program. int pqr(BinaryNode t) { if (t == null) return -1; else return 1 + max(pqr(t.left), pqr(t.right)); } Identify what the above program intends to do.

  1. Compute the height of a binary tree using an in-order traversal
  2. Compute the height of a binary tree using a pre-order traversal
  3. Compute the depth of a binary tree using a pre-order traversal
  4. Compute the depth of a binary tree using a post-order traversal
Show answer

Answer: (d) Compute the depth of a binary tree using a post-order traversal
Note: The children are processed before the node itself, so it is a post-order computation. In the course, the depth of a tree is the maximum level of its leaves, which equals its height.

Q195. The ______ method of the list data structure removes the element residing at the current position.

  1. Next
  2. Remove
  3. Find
  4. Add
Show answer

Answer: (b) Remove
Note: The fourth option was cropped in the source; Remove is the list-ADT method that deletes the current element.

Q196. Write 5 * (9 - 7) in postfix form:

  1. 5 0 7 )*
  2. 5 9 * 7 -
  3. 5 9 7 - *
  4. 5 9 7 * -
Show answer

Answer: (c) 5 9 7 - *
Note: The last option was partly unreadable in the source; (c) is the correct postfix form.

Q197. Which one of the following is TRUE about a linked list?

  1. It can be taken as a special case of a binary tree
  2. It is a non-linear data structure
  3. Its nodes are stored at consecutive memory locations
  4. Its size cannot be changed after its creation
Show answer

Answer: (a) It can be taken as a special case of a binary tree
Note: A linked list is a tree in which every node has at most one child. The other three statements are false for a linked list.

Q198. ______ holds a pointer 'front' which can not be pointed backward.

  1. Stack
  2. Queue
  3. Queue and Stack
  4. Priority Queue
Show answer

Answer: (b) Queue
Note: The wording is odd in the source; 'front' is the queue's pointer, so Queue is the best match.

Part 2: Subjective Questions

Q1. Define a complete binary tree. (2 marks)

In the course, a complete binary tree of depth d is a strictly binary tree all of whose leaves are at level d, so it has 2L nodes at every level L from 0 to d and 2d+1 - 1 nodes in total. (Many textbooks use a slightly wider definition: every level is full except possibly the last, which is filled from the left.)

Q2. What is the functionality of the following BST method? TreeNode<int>* function(TreeNode<int>* tree) { if (tree == NULL) return NULL; if (tree->getLeft() == NULL) return tree; return function(tree->getLeft()); } (3 marks)

It returns a pointer to the node holding the smallest value in the binary search tree, because it keeps moving to the left child until a node has no left child. For an empty tree it returns NULL.

Q3. Determine what the following recursive function computes when given the root of a binary tree. int MFunc(bt_t *T) { int N1, N2; if (T == NULL) return -1; N1 = MFunc(T->left); N2 = MFunc(T->right); return (N1 > N2 ? N1 : N2) + 1; } (5 marks)

It computes the height of the binary tree. An empty tree gives -1, a single node gives 0, and any other node gives 1 + the larger of the heights of its two subtrees. It processes both children before the node, so it is a post-order computation.

Q4. What would the state of a stack be after the following operations: create stack; push A; push F; push X; pop; push B; pop; pop? (2 marks)

push A: [A]; push F: [A, F]; push X: [A, F, X]; pop removes X: [A, F]; push B: [A, F, B]; pop removes B: [A, F]; pop removes F: [A].

Only A remains on the stack.

Q5. What is the difference between call by value and call by reference? (2 marks)

In call by value the function receives a copy of the argument, so changes made inside the function do not affect the caller's variable. In call by reference the function receives the variable itself (an alias), so changes made inside the function change the caller's variable, and no copy is made. Example: void f(int i, int &k) changes only k in the caller.

Q6. (a) Write a C++ statement that declares a valid reference to int i. (b) What is the benefit of references? (3 marks)

(a) int &r = i;

(b) A reference is another name (alias) for the same variable. It lets a function change the caller's variable and avoids copying large objects when a const reference is used. A reference must be initialised when declared and cannot later be made to refer to another variable.

Q7. Why do we use reference variables? Give one example. (2 marks)

To pass arguments to a function without copying them and to let the function modify the original value. Example: void swap(int &a, int &b) { int t = a; a = b; b = t; } exchanges the caller's two variables.

Q8. How can we avoid the problem of a dangling reference? (2 marks)

Never return a reference to a local (automatic) variable from a function, because that variable is destroyed when the function ends and the reference would point to memory that no longer holds a valid object. Return by value, or return a reference to something that outlives the function (for example a member variable or a dynamically allocated object).

Q9. What is wrong in the following code? Comment each line. 1. void main(void) 2. { 3. int actual = 123; 4. int &other = actual; 5. 6. int natural = 456; 7. other = &natural; 8. } (5 marks)

Line 3: declares an int variable actual with value 123.
Line 4: declares a reference other, which is now another name for actual.
Line 6: declares an int variable natural with value 456.
Line 7: error. other is an int (it is an alias of actual), so the address &natural, which is a pointer, cannot be assigned to it. A reference also cannot be made to refer to a different variable after its declaration. The correct statement to copy the value would be other = natural; (this changes actual to 456).
Line 8: end of main.

Q10. The following function works on a singly linked list. What does it do? void LinkList::mystery() { Node *temp = headNode; int result = 0; while (temp->getNext() != NULL) { temp = temp->getNext(); int value = temp->get(); if (value % 2 == 0) { value++; temp->set(value); } } } (3 marks)

It walks along the list starting from the node after headNode, and adds 1 to every even value, so even numbers become odd and odd numbers stay as they are. The first node (headNode) is not examined. The variable result is declared but never used.

Q11. Why does a linked list waste less memory than an array? Why can the size of a list be changed after creation but an array's size cannot? (5 marks)

An array needs one contiguous block whose size is fixed when it is declared, so we usually reserve more than we need, and a very large array may not fit in memory at all. A linked list allocates one node at a time, only when needed, and nodes can lie anywhere in memory because each node stores the address of the next. That is why a list can grow or shrink at run time, and why inserting or deleting needs only a pointer change, whereas an array has to shift all later elements. The price of a list is the extra pointer in every node and the lack of direct access by index.

Q12. Describe how to add an element to a sorted (ascending) singly linked list. (3 marks)

Start at the head and move forward while the next node's value is smaller than the new value. Create a new node, set its next pointer to the node that follows the current one, then set the current node's next pointer to the new node. Special cases: if the list is empty or the new value is smaller than the first value, make the new node the new head.

Q13. What is a function call stack? (2 marks)

When a function is called, its arguments, local variables and the return address are pushed onto a stack as one block (a stack frame). When the function returns, that frame is popped and control goes back to the caller. Because the last function called is the first to finish, the stack (LIFO) is the natural structure for this, and it is also what makes recursion work.

Q14. Convert the infix expression A + B * C - D to postfix and show how a stack is used. (3 marks)

Scan left to right, send operands straight to the output, and push an operator after popping every operator of higher or equal precedence.

A      output: A
+      stack: +
B      output: A B
*      stack: + *      (* has higher precedence than +)
C      output: A B C
-      pop *, pop +, push -   output: A B C * +
D      output: A B C * + D
end    pop -  output: A B C * + D -

Postfix: A B C * + D -

Q15. Evaluate the postfix expression 6 2 3 + - 3 8 2 / + * 2 ^ 3 + and show the stack. (5 marks)

6 2 3 + -  : push 6, 2, 3; + gives 5; - gives 6 - 5 = 1
3 8 2 / +  : push 3, 8, 2; / gives 4; + gives 3 + 4 = 7
*          : 1 * 7 = 7
2 ^        : 7 ^ 2 = 49
3 +        : 49 + 3 = 52

Result: 52.

Q16. Traverse the tree 15 (left child 2, right child 11) in inorder and postorder. (2 marks)

Inorder (left, root, right): 2, 15, 11.
Postorder (left, right, root): 2, 11, 15.

Q17. Here is a small binary tree: 14 is the root with children 2 and 11; 2 has children 1 and 3; 11 has children 10 and 30; 10 has a left child 7; 30 has a left child 40. Write the order of the nodes visited in an in-order and in a pre-order traversal. (5 marks)

In-order: 1, 2, 3, 14, 7, 10, 11, 40, 30.
Pre-order: 14, 2, 1, 3, 11, 10, 7, 30, 40.

Q18. The nodes of a binary tree have data 1, 2, 3, 4. The in-order traversal is 2, 1, 4, 3 and the post-order traversal is 2, 4, 3, 1. Draw the tree. (3 marks)

The last value of the post-order is the root, 1. In the in-order, 2 lies to the left of 1 and 4, 3 to its right. So 2 is the left child of 1. For the right part (in-order 4, 3; post-order 4, 3) the root is 3 and 4 is its left child. Tree: 1 (left 2, right 3), and 3 has a left child 4.

Q19. Write a recursive function that, given a binary search tree and a low and a high value, prints all values that lie between them, visiting as few nodes as possible. (5 marks)

void PrintRange(Node* root, int low, int high) {
    if (root == NULL) return;
    if (low < root->data)                 // left subtree may hold values >= low
        PrintRange(root->left, low, high);
    if (low <= root->data && root->data <= high)
        cout << root->data << " ";
    if (high > root->data)                // right subtree may hold values <= high
        PrintRange(root->right, low, high);
}

A subtree is visited only when it can contain a value in the range, and the values are printed in ascending order. (The prototype in the paper says int, but the function does not need to return a value.)

Q20. What are the applications of a binary tree? (2 marks)

A binary tree suits problems where a two-way decision is made at each step. Examples: finding duplicates in a list (insert each number into a BST and check whether it is already present), sorting a list with a BST and an in-order traversal, searching quickly in ordered data, expression trees, and building Huffman codes for compression.

Q21. How can we delete a node with two children in a binary search tree using its right subtree? (2 marks)

Find the smallest value in the node's right subtree (go once to the right, then left as far as possible). Copy that value into the node being deleted, and then delete that smallest node from the right subtree. The smallest node has no left child, so deleting it is the easy case (a leaf or a node with one child). The BST property is preserved.

Q22. Define the height of a tree and the balance of a node. (3 marks)

Height: the maximum level of the leaves of a tree (the length of the longest path from the root to a leaf). A tree with only a root has height 0.

Balance of a node: height of its left subtree minus height of its right subtree. In an AVL tree the balance of every node must be -1, 0 or +1.

Q23. What normally is the sequence of operations while constructing an AVL tree? (3 marks)

Insert the new node exactly as in an ordinary binary search tree. Then go back up toward the root, updating heights and checking the balance of each node. At the first node whose balance becomes +2 or -2, restore the balance by a single rotation (left-left or right-right case) or a double rotation (left-right or right-left case). After that rotation the whole tree is balanced again.

Q24. In which cases of insertion do we need a double rotation to balance the tree? (2 marks)

When the new node goes into the inside subtree of the unbalanced node: into the right subtree of the left child (left-right case) or into the left subtree of the right child (right-left case). The outside cases (left-left and right-right) need only a single rotation.

Q25. Is the following statement correct? If not, correct it: "A tree is an AVL tree if at least half of the nodes fulfil the AVL condition." (2 marks)

No. A tree is an AVL tree only if every node fulfils the AVL condition (the heights of its left and right subtrees differ by at most 1).

Q26. Draw an AVL tree by inserting 78, 21, 25, 28, 38, 36, 75 in this order, showing the rotations. (10 marks)

Insert 78, 21         : 78 with left child 21
Insert 25             : 78 is unbalanced (left-right). Double rotation.
                        tree: 25 (21, 78)
Insert 28             : 28 goes under 78 (left). Tree: 25 (21, 78 (28, -)). Balanced.
Insert 38             : 38 goes right of 28. 78 is unbalanced (left-right). Double rotation at 78.
                        tree: 25 (21, 38 (28, 78))
Insert 36             : 36 goes right of 28. 25 is unbalanced (right-left). Double rotation at 25:
                        tree: 28 (25 (21, -), 38 (36, 78))
Insert 75             : 75 goes left of 78. All nodes balanced, no rotation.

Final tree: root 28; left child 25 (with left child 21); right child 38 with children 36 and 78; 78 has a left child 75.

Q27. Insert into a min heap and delete the minimum: what are the steps of insert and deleteMin? (3 marks)

Insert: put the new value in the next free place (the end of the array) and compare it with its parent; while it is smaller than the parent, swap them (percolate up).
deleteMin: remove the root (the minimum), move the last element to the root, and compare it with its children; while it is larger than the smaller child, swap with that child (percolate down). Both take O(log n) time.

Q28. Explain how Huffman encoding builds its code. (3 marks)

Each character starts as a one-node tree with its frequency. Repeatedly take the two trees with the lowest frequencies and join them under a new root whose frequency is the sum. Continue until one tree remains. Label left edges 0 and right edges 1; the code of a character is the path from the root to it. Frequent characters end up near the root and get short codes, rare characters get long codes, and no code is a prefix of another.

Q29. What is a threaded binary tree and why is it useful? (3 marks)

In a threaded binary tree, the otherwise empty right pointer of a node holds a thread to its in-order successor (and the empty left pointer a thread to its in-order predecessor). In-order traversal can then be done with a simple loop, without recursion or a stack, which saves memory and time.

Q30. Define the following terms: (1) Reference variable, (2) Dangling reference, (3) const keyword. (3 marks)

Reference variable: another name (alias) for an existing variable, declared with & and initialised when it is created, e.g. int &r = x;.

Dangling reference: a reference to a variable that no longer exists, for example a reference to a local variable returned from a function.

const: marks a value (or a parameter, reference or member function) as read-only, so any attempt to change it is a compile-time error.

Q31. Explain the logic of the following function. int& Fun(int& y) { y = 100; return y; } (3 marks)

The parameter y is a reference, so it is another name for the caller's variable. The function stores 100 in that variable and returns a reference to the same variable. So after a call such as Fun(a); the variable a holds 100, and the call itself can be used as an lvalue, for example Fun(a) = 5; changes a to 5. Returning y is safe because y refers to the caller's variable, not to a local one.

Q32. Show the result of inserting the values 35, 19, 41, 39, 37, 28, 31, 14 into an empty AVL tree (only the final tree is required). (5 marks)

Insert 35, 19, 41 : 35 (19, 41)
Insert 39         : 39 goes left of 41
Insert 37         : 37 goes left of 39; 41 is unbalanced (left-left) -> single right rotation: 39 (37, 41)
Insert 28         : right of 19
Insert 31         : right of 28; 19 is unbalanced (right-right) -> single left rotation: 28 (19, 31)
Insert 14         : left of 19. Balanced.

Final tree: root 35; left child 28 (children 19 and 31, and 19 has a left child 14); right child 39 (children 37 and 41).

Answers to double-check

These answers could not be fully verified against the handouts, so confirm them from your own notes.

Q33. What will the following program print? int valMinus3(int orgVal) { orgVal = orgVal - 3; return orgVal; } int refMinus3(int& orgVal) { orgVal = orgVal - 3; return orgVal; } In main: int pvalue = 20; returnVal = valMinus3(pvalue); print returnVal, pvalue; pvalue = 20; returnVal = refMinus3(pvalue); print returnVal, pvalue. (5 marks)

The first call passes a copy: returnVal = 17 and pvalue stays 20. The second call passes pvalue by reference: returnVal = 17 and pvalue becomes 17. Output order: 17, 20, 17, 17. (The code was cropped in the source image, so this assumes both functions subtract 3 as shown.)

Q34. How is a single left rotation performed in an AVL tree? (3 marks)

Let k1 be the unbalanced node and k2 its right child (the insertion went into the right subtree of the right child, an outside case). In a single left rotation k2 becomes the root of this subtree, k1 becomes the left child of k2, and the old left subtree of k2 becomes the right subtree of k1. The BST order is preserved and the heights are balanced again.

Q35. What is a binary tree? Explain briefly. (2 marks)

A binary tree is a finite set of elements that is either empty or is divided into three disjoint parts: a single element called the root, and two other binary trees called the left and the right subtree. Every node therefore has at most two children.

Q36. What is the difference between a binary tree and an AVL tree? What is the similarity between an AVL tree and a BST? (3 marks)

A binary tree only limits every node to at most two children. An AVL tree is a binary search tree (values ordered left < node < right) which is also height balanced: the heights of the left and right subtrees of every node differ by at most 1, and the height of an empty tree is defined as -1. An AVL tree is identical to a BST in structure and ordering; it differs only by the balance condition, which is kept by rotations after insertions and deletions.

Q37. Why is a queue a linear data structure? (2 marks)

Its items are arranged one after another in a line: items can only be inserted at one end (the rear) and removed from the other (the front). Unlike a stack, which is LIFO, a queue is FIFO.

Q38. Explain the two cases in which a double rotation is needed in an AVL tree. (3 marks)

A single rotation cannot fix the balance when the insertion is on the inner side of the unbalanced node X: (1) insertion into the right subtree of the left child of X (left-right case): rotate the left child to the left, then X to the right; (2) insertion into the left subtree of the right child of X (right-left case): rotate the right child to the right, then X to the left.

Q39. How can we perform a level-order traversal of a tree? (3 marks)

Visit the root, then all nodes one level below it from left to right, then the next level, and so on. This needs a queue: put the root in the queue; while the queue is not empty, remove a node, visit it, and add its left and right children to the queue.

Q40. What is the maximum number of comparisons during an insertion in a BST? (2 marks)

For a complete (or nearly complete) tree of n nodes the depth is log2(n + 1) - 1, so about log2 n comparisons are needed. For a degenerate (chain-like) tree it can be as many as n.

Q41. Give the names of the basic queue operations. (2 marks)

enqueue(X) places X at the rear of the queue; dequeue() removes the front element and returns it; front() returns the front element without removing it; isEmpty() returns true if the queue is empty.

Q42. Give one benefit of using a stack. (2 marks)

A stack is a LIFO structure with only two basic operations, push and pop, so the structure itself enforces the correct order of calls. It is what makes function calls, recursion, expression evaluation and parenthesis matching easy.

Q43. Describe any two uses of priority queues. (2 marks)

(1) Operating systems keep a queue of processes; a process with a higher priority is served first. (2) In a simulation, events are inserted in a priority queue and the event that will occur first in time is removed first.

Q44. Describe the use of queues. (3 marks)

One of the most important uses is simulation: a program that models a real-world situation (a bank, traffic, a computer network) puts customers, vehicles or packets in queues and serves them in order of arrival. Queues are also used for scheduling, buffering and level-order tree traversal.

Q45. How do we evaluate a postfix expression? (3 marks)

Scan from left to right. Each time an operand is read, push it on a stack. When an operator is read, pop the top two operands, apply the operator (the first popped is the right operand), and push the result back. At the end, the single value on the stack is the answer.

Q46. What is the function of the length() method of the Queue class? What is meant by an empty stack? (3 marks)

length() returns the number of elements currently in the queue (it simply returns the size variable), not the capacity of the underlying array. An empty stack is one that holds no element; isEmpty() returns true in that case and false otherwise, and pop on an empty stack causes underflow.

Q47. What is meant by the pre-order traversal of a binary search tree? (2 marks)

In a pre-order traversal each node is processed before its children: first the root, then the left subtree (recursively in pre-order), then the right subtree (recursively in pre-order). Order: Root, Left, Right.

Q48. Define a binary search tree. What are the level of a node and the depth of a tree? (3 marks)

A binary search tree (BST) is a binary tree in which, for every node, all values in the left subtree are smaller than the node's value and all values in the right subtree are larger (or equal). The level of a node is its distance from the root: the root is at level 0, its children at level 1, and so on. The depth (height) of a tree is the maximum level of its leaves. In a complete binary tree of depth d, the symbol d is exactly this maximum level.

Q49. The inorder traversal of a binary tree is L, C, A, D, F, M and its postorder traversal is L, C, D, F, M, A. Draw the tree. (5 marks)

The last node of the postorder is the root: A. In the inorder, the nodes before A (L, C) form the left subtree and the nodes after A (D, F, M) form the right subtree.

Left subtree: postorder L, C gives root C; in the inorder L is before C, so L is the left child of C.
Right subtree: postorder D, F, M gives root M; in the inorder D, F come before M, so they form its left subtree. Postorder D, F gives root F, and D is the left child of F.

Tree: A has the left child C (with left child L) and the right child M (with left child F, which has a left child D). The paper note said the sequence was not certain; this answer uses the sequence as written.

A
|-- C
|   |-- L
|-- M
    |-- F
        |-- D

Q50. Insert 2, 1, 4, 5, 9, 3, 6 into an empty AVL tree and show the rotations. (5 marks)

2, 1, 4, 5     : 2 (1, 4 (-, 5)), balanced
9              : 4 becomes unbalanced (right-right) -> left rotation: 2 (1, 5 (4, 9))
3              : goes left of 4; node 2 becomes unbalanced (right-left) -> double rotation:
                 4 (2 (1, 3), 5 (-, 9))
6              : goes left of 9; node 5 becomes unbalanced (right-left) -> double rotation:
                 4 (2 (1, 3), 6 (5, 9))

Final tree: root 4; left child 2 (children 1, 3); right child 6 (children 5, 9).

Q51. Use the values 14, 9, 18, 4, 13, 12 to make an AVL tree and draw the final diagram. (3 marks)

Insert 14, 9, 18, 4, 13: balanced (14 (9 (4, 13), 18)). Insert 12 as the left child of 13: node 14 becomes unbalanced (left-right case), so a double rotation is needed (left rotation at 9, then right rotation at 14).

Final tree: root 13; left child 9 (children 4 and 12); right child 14 (right child 18).

Q52. Use the values 17, 5, 18, 10, 14 to make a balanced (AVL) tree. (The paper listed 5 twice; the duplicate is ignored.) (3 marks)

Insert 17, 5, 18, 10, 14. When 14 is inserted as the right child of 10, node 5 becomes unbalanced (right-right), so a single left rotation at 5 is applied: 10 becomes the parent of 5 and 14.

Final tree: root 17; left child 10 (children 5 and 14); right child 18.

Q53. Make a binary search tree from 2, 6, 5, 4, 7, 9, 8 (only the final tree is required). (3 marks)

Insert in the given order: 2 is the root; 6 goes right of 2; 5 goes left of 6; 4 goes left of 5; 7 goes right of 6; 9 goes right of 7; 8 goes left of 9.

2
  \
   6
  / \
 5   7
/     \
4       9
       /
      8

Q54. (a) Make a binary search tree from 49, 30, 32, 43, 26, 45, 28. (b) If node 30 is removed, which node takes the 30th position? (5 marks)

(a) 49 is the root; 30 goes left; 32 goes right of 30; 43 goes right of 32; 26 goes left of 30; 45 goes right of 43; 28 goes right of 26. So: 49 -> 30 (left 26 with right child 28; right 32 with right child 43, which has a right child 45).

(b) Node 30 has two children. Using the right subtree, its place is taken by the in-order successor, the smallest value of its right subtree: 32 (then 43 takes the place of 32). If the left subtree is used, the in-order predecessor 28 takes its place.

Q55. Convert the sorted list 2, 10, 12, 13, 20, 25, 29, 31 into a balanced binary search tree. (5 marks)

Take the middle element as the root and repeat on both halves. Root 13; left half 2, 10, 12 gives 10 with children 2 and 12; right half 20, 25, 29, 31 gives 25 with left child 20 and right child 29, which has a right child 31.

Tree: 13 (10 (2, 12), 25 (20, 29 (-, 31))). Every node has subtree heights that differ by at most 1, so it is also an AVL tree.

Q56. How can we tell that a given binary search tree is an AVL tree? (3 marks)

Compute the balance of every node (height of the left subtree minus height of the right subtree). The tree is an AVL tree only if every node has balance -1, 0 or +1, and it is also a binary search tree. If even one node has balance +2 or -2, it is not an AVL tree, and the reason is that node; it is fixed by a rotation.

Q57. What are the disadvantages of an AVL tree? (2 marks)

Every node must store extra information (its height or balance), insertion and deletion are more complicated because rotations are needed to keep the tree balanced, and in the worst case a deletion can need up to about log n rotations. If the data changes often and searching is rare, the extra work can cost more than the benefit.

Q58. Describe the logic of the following function: int& Fun(int& y) { y = y + 100; return y; } (2 marks)

The parameter y is a reference to the caller's variable. The function adds 100 to that variable (not to a copy) and returns a reference to the same variable. So after Fun(a); the variable a has increased by 100, and the call can even appear on the left of an assignment. Returning y is safe because it refers to the caller's variable, not to a local one.

Q59. Describe the declaration const int &g(int &var); (2 marks)

g is a function that takes an int by reference (so no copy is made, and the function can change the caller's variable) and returns a constant reference to an int: the caller may read the returned value but cannot modify it through that reference.

Q60. We want a function to change the state of a large object without sending a copy to the function. Which is the better solution: pointers or pass by reference? Why? (3 marks)

Pass by reference is better. The object is not copied (saving time and memory), the function works on the original object, and the code stays simple: no address-of and dereference syntax, and a reference can never be NULL or point to a different object. Pointers also avoid the copy but make the code more error-prone. If the function should not change the object, use a const reference.

Q61. Write the signature of a function named Student which takes two reference parameters, an int Marks and a float CGPA, and returns nothing. (2 marks)

void Student(int &Marks, float &CGPA);

Both parameters are references, so any change to Marks or CGPA inside the function changes the caller's variables.

Q62. Which node's in-order successor is always NULL? (2 marks)

The right-most node of the tree (the node with the largest value in a BST), because no node comes after it in the in-order traversal. In a threaded binary tree its right thread therefore points to NULL (or the dummy node). For any other node the in-order successor is the leftmost node of its right subtree, or the first ancestor reached from a left child.

Q63. After deleting the root of a binary search tree, which node becomes the new root? (2 marks)

If the right subtree is used, the in-order successor takes the root's place: go to the right child, then keep going left to the smallest value. If the left subtree is used, the in-order predecessor (the largest value of the left subtree) takes its place.

Short Notes (Key Terms)

Abstract Data Type (ADT)
A set of data values and the operations on them, specified independently of any implementation.
Algorithm
A finite set of steps that achieves a desired result.
Ancestor / Descendant
An ancestor of a node is its parent, the parent of the parent, and so on up to the root. A descendant is a child, a child of a child, and so on.
Argument and Parameter
An argument is a value passed to a function by the caller; a parameter is the variable that receives it in the called function.
Array
A list of values of the same type stored in contiguous memory, each reached by an index.
AVL tree
A binary search tree in which the heights of the two subtrees of every node differ by at most one. Balance is restored by single or double rotations.
Balance of a node
Height of the left subtree minus height of the right subtree.
Big-O notation
A measure of how the time or memory needed by an algorithm grows with the input size n, ignoring constants.
Binary heap
A complete binary tree in which every node's key is greater than or equal to (max-heap) or less than or equal to (min-heap) the keys of its children.
Binary search
Searching a sorted list by comparing the target with the middle item and then continuing in the half where it must lie.
Binary search tree (BST)
A binary tree in which all values in a node's left subtree are smaller than the node and all values in its right subtree are larger (or equal).
Binary tree
A tree in which each node has at most two children, a left and a right.
Bounded queue
A queue limited to a fixed number of items.
Build-heap
Turning an array into a heap by applying heapify from the last parent back to the root; it takes O(n) time.
Child, Parent, Sibling
A child is a node referred to by another node (its parent). Nodes with the same parent are siblings. Every node except the root has one parent.
Circular list
A linked list in which the last node points back to the first.
Circular queue
An array implementation of a bounded queue in which the rear wraps around to the start of the array when it reaches the end.
Complete binary tree
In this course: a binary tree of depth d with all leaves at level d, so it has 2^L nodes at level L.
Data structure
The way data is organised in a program so that it can be used efficiently, for example lists, stacks, queues and trees.
Doubly linked list
A list in which each node has a pointer to the next and to the previous node.
Dynamic array
An array whose size can change while the program runs.
FIFO
First in, first out: items are processed in the order they arrive. A queue works this way.
LIFO
Last in, first out: the most recently added item is processed first. A stack works this way.
Full binary tree
A binary tree in which every node has either zero or two children.
Hash function
A function that maps a key to an array position (an integer), ideally spreading keys evenly.
Heap (memory)
An area of memory from which space for dynamic variables is allocated at run time.
Heapify
Restoring the heap property at a node by swapping it with its larger (max-heap) or smaller (min-heap) child and repeating down the tree.
Height of a tree
The maximum level of any leaf, i.e. the longest distance from the root to a leaf; a single-node tree has height 0.
Huffman encoding
A variable-length code built from character frequencies; frequent characters get short codes, rare ones long codes.
Infix, Prefix, Postfix
Infix puts the operator between the operands (A + B), prefix before them (+ A B) and postfix after them (A B +). Postfix and prefix need no parentheses.
In-order, Pre-order, Post-order traversal
In-order: left, root, right. Pre-order: root, left, right. Post-order: left, right, root. Level-order visits nodes level by level.
Internal node and Leaf
An internal node has at least one child; a leaf has no children.
Key
The part of a record used to sort, index or look it up.
Left / Right rotation
Operations that restore balance in a BST. A right rotation moves a node down to the right so that its left child takes its place; a left rotation does the opposite.
Linear search
Examining the items one by one until the target is found or the list ends.
Linked list
A list of nodes connected by pointers. A singly linked list has one pointer per node, a doubly linked list has two.
Max-heap and Min-heap property
In a max-heap each node is less than or equal to its parent, so the largest key is at the root. In a min-heap each node is greater than or equal to its parent, so the smallest key is at the root.
Merge sort
Splits the items into two groups, sorts each recursively and merges them into one sorted sequence.
Node
A unit of a data structure holding data and the links to other nodes.
Overloading
Using the same name for more than one function or operator, with different parameter types.
Perfect binary tree
A binary tree in which all leaves are at the same depth and every internal node has two children.
Queue
A FIFO structure with the operations enqueue (insert at the rear) and dequeue (remove from the front).
Quicksort
Picks a pivot, partitions the other items into smaller and larger ones, and sorts the two parts recursively. After partitioning the pivot is in its final position.
Recursion
A technique in which a function calls itself on a smaller part of the problem, with a base case that stops the calls.
Root
The first node of a tree; the only node without a parent.
Stack
A LIFO structure with the operations push (insert) and pop (remove), both at the top.
Strictly binary tree
A binary tree in which every non-leaf node has both a left and a right child.
Threaded tree
A binary tree in which empty child links are replaced by threads to the in-order predecessor or successor, allowing traversal without recursion or a stack.
Tree
A hierarchical data structure of nodes linked by parent-child relations, with one root.
Union
The union of two sets is the set of all members that are in either set.
Worst case
The input that makes an algorithm take the most time or resources.
at
Labels: , , , ,

No comments:

Post a Comment

Please give us your feedback & help us to improve this site.

CS301 Mid Term Papers