Data structures Exam Prep Part 1- Recursion, Algorithm Analysis & Stack Questions with

Data structures Exam Prep Part 1- Recursion, Algorithm Analysis & Stack Questions with Answers Data structures can be said to be an ADT's ______. 1 specifications 2 implementation 3 abstraction 4 definition - Correct Answers: 2 implementation The specifications of an ADT's operations indicate ______. 1 what the operations do 2 how to store the data in the ADT 3 how to carry out the operations 4 how to implement the operations - Correct Answers: 2 what the operations do Which of the following is not an primitive data type in C++? 1 string 2 char 3 bool 4 double - Correct Answers: 1 string In a recursive solution to a problem, we solve a problem P(n) by solving another problem P(k) where 1 P(k) is smaller than P(n) 2 P(k) is same as P(n) 3 P(k) is the hardest part of P(n) 4 P(k) is a larger problem than P(n) - Correct Answers: 1 P(k) is smaller than P(n) A(n) ______ is a C++ construct that enables a programmer to define a new data type. 1 data field 2 object 3 method 4 class - Correct Answers: 4 class The function int fact (int k) { return k * fact(k-1); if (k == 0) return 1; } 1 computes the factorial on an integer k passed to it as parameter 2 works for all non-negative values of k, but not for negative numbers. 3 returns the value 1 if it is passed a value of 0 for the parameter k 4 does not correctly handle its base case - Correct Answers: 4 does not correctly handle its base case When a function contains a function call to itself, such function is _____. 1 self-reference 2 reciprocal 3 repetitive 4 recursive - Correct Answers: 4 recursive The factorial of n is equal to 1 factorial (n-1) 2 n - factorial (n-1) 3 n * factorial (n-1) 4 n - 1 - Correct Answers: 3 n * factorial (n-1) When a programmer writes a definition to make a new type to be used for a declaration, the new type is called a: 1 programmer-defined type 2 struct-defined type 3 client-defined type 4 primitive data type - Correct Answers: 1 programmer-defined type How many times is the following code invoked by the call recursive(4)? void recursive( int i ) { if (i < 8) { cout << i << " "; recursive(i); } } 1 4 2 This is an infinite recursion 3 8 4 2 - Correct Answers: 2 This is an infinite recursion When an algorithm has an upper limit to the number of instructions, regardless of the size of n, it is referred to as a(n) ______________ algorithm. 1 limited 2 time complex 3 constant time 4 instruction-truncated - Correct Answers: 3 constant time A stack is initially empty, then the following commands are performed: push 7, push 5, pop, push 10, pop, push 6 which of the following is the correct stack after those commands (assume the top of the stack is on the left)? 1 6 7 2 6 10 5 7 3 6 10 4 10 7 - Correct Answers: 1 6 7 If the array 6, 2, 7, 13, 8, 5 is added to a stack, in the order given, which number will be the first number to be removed from the stack? 1 8 2 2 3 6 4 5 - Correct Answers: 4 5 Which of the following is a good analogy of the ADT Stack? 1 a group of people playing musical chairs 2 a paper bag with colored poker chips 3 a pile of textbooks on your desk 4 people standing in a cafeteria line - Correct Answers: 3 a pile of textbooks on your desk We can measure the complexity of an algorithm that solves a computational problem by determining the number of ___ for an input of size n. 1 basic steps it requires 2 output statements it has 3 input statements it has 4 variables it uses - Correct Answers: 1 basic steps it requires All of the following operations of the ADT stack take no parameters except? 1 pop 2 push 3 isEmpty 4 top or peek - Correct Answers: 2 push The following code segment has ______ time complexity? for(int i = 0; i < n; i++){ for(int j = 0; j < n: j=j*2){ int val = (j*i); cout << val; } } 1 O(log n) 2 O(1) 3 O(n log n) 4 O(n) - Correct Answers: 3 O(n log n) Big-oh notation of a time complexity applies when: 1 an algorithm's time complexity changes with the number of elements 2 an algorithm's time complexity is always the same 3 an algorithm's time complexity can vary, but it won't be any worse than its big-oh time complexity 4 an algorithm's time complexity can vary, but it won't be any better than its big-oh time complexity - Correct Answers: 3 an algorithm's time complexity can vary, but it won't be any worse than its big-oh time complexity ____ allows retrieving an element from a stack without removing it. 1 top or peek 2 traverse 3 push 4 pop - Correct Answers: 1 top or peek Software must make efficient use of resources such as _______ and _______ . 1 Memory, Hard Drive 2 CPU time, Memory 3 Hard Drive, Video Card 4 CPU time, Video Card - Correct Answers: 2 CPU time, Memory If keyboard entry is treated as an stack ADT and the backspace key is pressed when the stack ADT is empty, which of the following is the most reasonable action for the stack ADT to take? 1 display an error message 2 ignore the backspace and continue 3 display a symbol for the backspace 4 terminate the program and write an error message - Correct Answers: 2 ignore the backspace and continue A ______ can be used to reverse the order of a set of data. 1 Stack 2 Software 3 Heaps 4 Queue - Correct Answers: 1 Stack What behavior does the ADT stack exhibit? 1 first in, first out 2 last-in, first-out 3 first in, never out 4 last in, last out - Correct Answers: 2 last-in, first-out A recursive function should be designed to stop making recursive calls when it reaches its 1 base case 2 last parameter 3 closing curly brace 4 return statement - Correct Answers: 1 base case Which of the following construct does not allow programmer to define a new type in C++? 1 struct 2 array 3 class 4 typedef - Correct Answers: 2 array The ______ operation of the ADT stack retrieves and then removes the top of the stack. 1 pop 2 getTop 3 createStack 4 push - Correct Answers: 1 pop Which of the following is a good analogy of the ADT Stack? 1 a paper bag with colored poker chips 2 a group of people playing musical chairs 3 a pile of textbooks on your desk 4 people standing in a cafeteria line - Correct Answers: 3 a pile of textbooks on your desk The Big-Oh notation depicts the ____ case scenario of an algorithm. 1 ordinary 2 best 3 average 4 worst - Correct Answers: 4 worst The item that is removed first from a stack is called the ______ of the stack. 1 base 2 top 3 front 4 prime - Correct Answers: 2 top A practical application of the stack is 1 all of these 2 the storage of local variables in a function call 3 the tracking of the order of calls and returns of functions in a program. 4 the tracking of the order of entry into and exit from nested loops - Correct Answers: 1 all of these The ______ operation of the ADT stack adds an item to the top of the stack. 1 push 2 pop 3 getTop 4 createStack - Correct Answers: 1 push If you implement a stack using an array, where would be the more appropriate place for the bottom element of the stack? 1 mid array for a binary search 2 at the end of the array 3 at the first element of the array 4 it doesn't matter - Correct Answers: 3 at the first element of the array