1_COP 4530 Exam 1 practice quiz

Description

accumulation of practice exam questions
Tracy Dash
Quiz by Tracy Dash, updated more than 1 year ago More Less
E S
Created by E S almost 8 years ago
Tracy Dash
Copied by Tracy Dash over 7 years ago
41
1

Resource summary

Question 1

Question
Write a traversal loop for an fsu::Vector object v .
Answer
  • for (size_t i = 0; i <= size; ++i) { /* whatever */ }
  • for (size_t i = 0; i < v.Size(); ++i) { /* whatever */ }
  • for (size_t i = 0; i < size; ++i) { /* whatever */ }
  • None of the other choices
  • for (size_t i = 0; i <= v.Size(); ++i) { /* whatever */ }

Question 2

Question
To find a pointer max to the largest element in the array a we can use the following generic algorithm call (there are size elements in a)
Answer
  • None of the other choices
  • max = fsu::g_max_element ( a, a + size );
  • max = fsu::g_max_element ( a.Begin() );
  • max = fsu::g_max_element (a);
  • max = fsu::g_max_element ( a.Begin(), a.End() );

Question 3

Question
Consider the following implementation of an fsu::List operation:
Answer
  • Empty
  • Size
  • Reverse
  • Clear
  • Includes
  • None of the other choices

Question 4

Question
Consider the following code implementing an fsu::List operation: Select the missing line of code from the choices below.
Answer
  • newLink->prev_ = location;
  • newLink->prev_ = location->next_;
  • newLink->next_ = location->prev_;
  • None of the other choices
  • newLink->prev_ = location->prev_;

Question 5

Question
This is an illustration of a vector of characters to be used in answering the question: element: B D F F F H K Q W Y index: 0 1 2 3 4 5 6 7 8 9 What is the return value of the call upper_bound('F') ?
Answer
  • 1
  • 2
  • 3
  • 4
  • 5
  • D
  • F
  • H

Question 6

Question
Declare a vector object widgetVector with elements of type Widget, size 15, and initial element values equal to ZED.
Answer
  • fsu::Vector<Widget> widgetVector (15,ZED);
  • WidgetVector widgetVector (15,ZED);
  • fsu::Vector<Widget>(15,ZED) widgetVector;
  • None of the other choices
  • fsu::Vector<Widget(15,ZED)> widgetVector;

Question 7

Question
Which of the following are required (but often only implictly given) components of an algorithm? Selected
Answer
  • Body: A recipe or set of instructions for a computation
  • Assumptions: Things that are assumed to be true prior to executing the body
  • Outcomes: Things that are true after executing the body (assuming the assumptions)
  • RunTime Estimate: Statement of the runtime of the algorithm body, in asymptotic notation, as a function of input size
  • RunSpace Estimate: Statement of the algorithm runspace requirements, in asympotic &quot;+&quot; notation, as a function of input size
  • Correctness Proof: THEOREM. If the assumptions hold and the algorithm body is executed then the outcomes are true.
  • RunTime Proof: THEOREM.  If the assumptions hold then the asserted runtime estimates are correct.
  • RunSpace Proof: THEOREM.  If the assumptions hold then the asserted

Question 8

Question
Necessary components in a recursive function implementation are (select all that apply):
Answer
  • A recursive call: in which the function itself is called, either directly or indirectly
  • A base case: in which no recursive call is made and the process terminates normally in a return
  • The use of a stack as part of the algorithm
  • A dimensional reduction: an assignment of a local variable to itself with smaller variable

Question 9

Question
The following represents output from the call d.Dump() from the fsu::Deque<char> object d: What is the result of the following output statement? std::cout << d[5];
Answer
  • A
  • B
  • C
  • D
  • E
  • F
  • G
  • H
  • I
  • J

Question 10

Question
Select the most appropriate statement for the asymptotic runtime for the binary_search algorithm with input size n.
Answer
  • O(log n)
  • Θ(log n)
  • O(n)
  • Θ(n)

Question 11

Question
Select a minimal set of operations that distinguish fsu::Deque from other fsu:: sequential containers. (Here i is an iterator, t is a container element, and n is an integer.)
Answer
  • PushFront(t)
  • PushBack(t)
  • Insert(i,t)
  • [n] (bracket operator)
  • SetSize(n)
  • Front()
  • Back()
  • Begin()

Question 12

Question
To copy the elements from an fsu::Deque<> d to an fsu::Vector<> v we can use the following generic algorithm call:
Answer
  • fsu::g_copy (d.Begin(), d.End(), v.Begin(), v.End());
  • fsu::g_copy (d.Begin(), d.End(), v.Begin());
  • None of the other choices
  • fsu::g_copy (d.Begin(), d.End(), v, v + d.Size);
  • fsu::g_copy (d.Begin(), d.End(), v);

Question 13

Question
Select a minimal set of operations that distinguish fsu::List from other fsu:: sequential containers. (Here i is an iterator, t is a container element, and n is an integer.)
Answer
  • PushBack(t)
  • PushFront(t)
  • Insert(i,t)
  • [n] (bracket operator)
  • SetSize(n)
  • Front()
  • Back()
  • Begin()

Question 14

Question
Select the answer that best describes the asymptotic runtime of the operation fsu::List::PushBack(t) Here t is an item of type  fsu::List::ValueType and n is the size of the list.
Answer
  • O(1)
  • Amortized O(1)
  • O(n)
  • Amortized O(n)

Question 15

Question
The following represents output from the call d.Dump() from the fsu::Deque<char> object d: What is the result of the following output statement? std::cout << d;
Answer
  • None of the other choices
  • G H I J A B
  • C D E F G
  • C D E F
  • G H I J A B C

Question 16

Question
You are given the declaration fsu::List<fsu::String> L; Write a client program fragment that inserts the strings"Help", "I", "May", "You" into L (in this order) so that L.Display(std::cout, ' '); results in the sentence "May I Help You".
Answer
  • L.PushFront("Help"); L.PushFront("I"); L.PushFront("May"); L.PushFront("You");
  • L.PushBack("Help"); L.PushFront("I"); L.PushFront("May"); L.PushBack("You";);
  • L.PushFront("Help"); L.PushBack("I"); L.PushFront("May"); L.PushBack("You");
  • None of the other choices
  • L.PushBack("Help"); L.PushBack("I"); L.PushBack("May"); L.PushFront("You");

Question 17

Question
Using a data stack to evaluate the postfix expression 1 2 3 + 4 5 6 + * + + what is the best representation of the stack during the evaluation?

Question 18

Question
Select a minimal set of operations that distinguish fsu::Deque from other fsu:: sequential containers. (Here i is an iterator, t is a container element, and n is an integer.)
Answer
  • PushBack(t)
  • PushFront(t)
  • Insert(i,t)
  • [n] (bracket operator)
  • SetSize(n)
  • Front()
  • Back()
  • Begin()

Question 19

Question
The following represents data of type char stored in a vector: With the initial search range for lower_bound underscored. Which if the following represents the search range after ONE iteration of the loop body in lower_bound(H) ?

Question 20

Question
Declare an fsu::List object L with elements of type fsu::String.
Answer
  • fsu::List<fsu::String> L;
  • L = fsu::List<fsu::String>;
  • None of the other choices
  • fsu::List L<fsu::String>;
  • L = new fsu::List<fsu::String>;

Question 21

Question
Select the most appropriate statement of the asymptotic runtime for the sequential_search algorithm with input size n.
Answer
  • O(log n)
  • Θ(log n)
  • O(n)
  • Θ(n)

Question 22

Question
This is an illustration of a vector of characters to be used in answering the question: What is the return value of the call lower_bound('F') ?
Answer
  • 1
  • 2
  • 3
  • 4
  • 5
  • D
  • F
  • H

Question 23

Question
Consider the following code implementing an fsu::List operation: Select the missing line of code from the choices below.
Answer
  • newLink->prev_ = location->prev_;
  • newLink->prev_ = location;
  • None of the other choices
  • newLink->prev_ = location->next_;
  • newLink->next_ = location->prev_;

Question 24

Question
Select the answer that best describes the asymptotic runtime of the operation    fsu::Deque:: bracket operator [i] Here i is an item of type size_t and n is the size of the deque.
Answer
  • O(1)
  • Amortized O(1)
  • O(n)
  • Amortized O(n)

Question 25

Question
The following illustrates the contents of the control stack S during a depth-first search of a tree [tree3], beginning at vertex R = root and searching for the vertex X = goal. (Search left before right, beginning at the root.) The search process is started but not complete.

Question 26

Question
An abstract data type [ADT] consists of the following (select all that apply):
Answer
  • A set of operations on the data
  • Axioms, or rules, governing the way operations interact
  • An implementation in a modern programming language
  • Theorems, or provable behaviors derived from the axioms
  • A collection of data of some type T

Question 27

Question
Select a minimal set of operations that distinguish fsu::Deque from other fsu:: sequential containers. (Here i is an iterator, t is a container element, and n is an integer.)
Answer
  • PushBack(t)
  • PushFront(t)
  • Insert(i,t)
  • [n] (bracket operator)
  • SetSize(n)
  • Front()
  • Back()
  • Begin()

Question 28

Question
The adaptor template defining fsu::Stack <T , C > defines an implementation of ADT Stack by re-defining the user interface of the container C. Which of the operations listed below must C possess for this adaptation to compile? (Check all that apply.)
Answer
  • PushBack(t)
  • PopBack()
  • PushFront(t)
  • PopFront()

Question 29

Question
Select a minimal set of operations that distinguish fsu::List from other fsu:: sequential containers. (Here i is an iterator, t is a container element, and n is an integer.)
Answer
  • PushBack(t)
  • PushFront(t)
  • Insert(i,t)
  • [n] (bracket operator)
  • SetSize(n)
  • Front()
  • Back()
  • Begin()

Question 30

Question
The adaptor template defining fsu::Queue <T , C > defines an implementation of ADT Queue by re-defining the user interface of the container C. Which of the operations listed below must C possess for this adaptation to compile? (Check all that apply.)
Answer
  • PushBack(t)
  • PopFront()
  • PushFront(t)
  • PopBack()

Question 31

Question
Which of the following are optional (but very desirable) components of an algorithm?
Answer
  • Body: A recipe or set of instructions for a computation
  • Assumptions: Things that are assumed to be true prior to executing the body
  • Outcomes: Things that are true after executing the body (assuming the assumptions)
  • RunTime Estimate: Statement of the runtime of the algorithm body, in asymptotic notation, as a function of input size
  • RunSpace Estimate: Statement of the algorithm runspace requirements, in asympotic &quot;+&quot; notation, as a function of input size
  • Correctness Proof: THEOREM. If the assumptions hold and the algorithmn body is executed then the outcomes are true.
  • RunTime Proof: THEOREM.  If the assumptions hold then the asserted runtime estimates are correct.
  • RunSpace Proof: THEOREM.  If the assumptions hold then the asserted runspace estimates are correct.

Question 32

Question
Select the answer that best describes the asymptotic runtime of the operation fsu::List::PushBack(t) Here t is an item of type  fsu::List::ValueType and n is the size of the list.
Answer
  • O(1)
  • Amortized O(1)
  • O(n)
  • Amortized O(n)

Question 33

Question
Select the most appropriate statement of the asymptotic runtime for the sequential_search algorithm with input size n.
Answer
  • O(log n)
  • Θ(log n)
  • O(n)
  • Θ(n)

Question 34

Question
Select the answer that best describes the asymptotic runtime of the operation    fsu::List:: Destructor Here n is the size of the list.
Answer
  • O(1)
  • Amortized O(1)
  • O(n)
  • Amortized O(n)

Question 35

Question
Select the answer that best describes the asymptotic runtime of the operation    fsu::Vector::PushBack(t) Here t is an item of type  fsu::Vector::ValueType and n is the size of the vector.
Answer
  • O(1)
  • Amortized O(1)
  • O(n)
  • Amortized O(n)

Question 36

Question
This is an illustration of a vector of characters to be used in answering the question: What is the return value of the call lower_bound('Z') ?
Answer
  • 7
  • 8
  • 9
  • 10
  • K
  • Q
  • W
  • Y

Question 37

Question
Suppose the fsu::Deque<> d has elements in sorted order and we wish to insert the element x in correct order in d. The following generic algorithm call returns an iterator to the last correct location to insert x:
Answer
  • i = fsu::g_upper_bound(d.Begin(), d.End(), x);
  • i = fsu::g_upper_bound(d, x);
  • None of the other choices
  • i = fsu::g_lower_bound(d, x);

Question 38

Question
This is an illustration of a vector of characters to be used in answering the question: What is the return value of the call upper_bound('X') ?
Answer
  • 7
  • 8
  • 9
  • 10
  • K
  • Q
  • W
  • Y

Question 39

Question
Declare a Deque object d with elements of type String.
Answer
  • fsu::Deque < char > d;
  • d = new fsu::Deque< char >;
  • fsu::Deque< char , fsu::List < char >> d;
  • None of the other choices
  • d fsu::Deque < char >;

Question 40

Question
Suppose that we know Algorithm A has runtime Θ(n 2 ), where n is a measure of input size. Which of the following statements is also true? (Check all that apply.)(Not sure if this one is correct)
Answer
  • A has runtime Θ(3n^2  + 7n).
  • A has runtime Ω(n^2 ).
  • A has runtime O(n^2 ).
  • A has runtime Θ(n^3 ).
Show full summary Hide full summary

Similar

Data Structures & Algorithms
Reuben Caruana
F453 Data Structures - Stacks and Queues
harvs899
COP 4530 Exam 1 practice quiz
Tracy Dash
2_COP 4530 Exam 1 practice quiz
E S
F453 Data Structures - Binary Trees
harvs899
Computer Science: Structures: GCSE
louisewright528
Data representation, types and structures
bubblesthelabrad
Patient Record System- UOP-DBM/381-WEEK5
j03garcia
Glosario-EstructuraDeDatos
Eduardo Saldaña
Data types and structures, F452 Computing
Rakib
Data Structures - Abstract Data Types
Shaounak Nasikkar