Database Algorithm midterm

Question 1

Data Encapsulation:
The separation of the representation of data from the applications that use the data at a logical level

Answer

true

Question 2

Abstract data type (ADT)
A data type whose properties (domain and operations) are specified independently of any particular implementation

Answer

true

Question 3

Data structure
A collection of data elements whose organization is characterized by accessing operations that are used to store and retrieve the individual data elements

Answer

true

Question 4

[blank_start]ADT[blank_end] is a high-level description: the logical picture of the data and the operations that manipulate them.

[blank_start]Data Structure[blank_end] is concrete: a collection of data elements and the operations that store and retrieve individual elements.

ADT is implementation [blank_start]independent[blank_end], whereas a data structure is implementation [blank_start]dependent[blank_end].

A data structure is how we implement the data in an ADT whose values have component parts. The operations on an ADT are translated into algorithms on the data structure.

Accepted Answer

ADT

Accepted Answer

Data Structure

Accepted Answer

independent

Accepted Answer

dependent

Question 5

Composite data type
A data type that allows a collection of values to be associated with an object of that type

Composite data types come in two forms: 
unstructured 
structured.

An unstructured composite type is a collection of components that are not organized with respect to one another.

A structured data type is an organized collection of components in which the organization determines the method used to access individual data components.

Answer

true

Question 6

[blank_start]Encapsulation[blank_end] This is the practice of keeping fields within a class private, then providing access to them via public methods

[blank_start]Inheritance[blank_end] It lets programmers create new classes that share some of the attributes of existing classes

[blank_start]Polymorphism[blank_end] This Java OOP concept lets programmers use the same word to mean different things in different contexts

[blank_start]method overriding[blank_end] when the different meanings are implied by the values of the supplied variables

Accepted Answer

Encapsulation

Accepted Answer

Inheritance

Accepted Answer

Polymorphism

Accepted Answer

method overriding

Question 7

Stack
Visualize stack as a deck of cards. The current top card represents the current scope of the program, usually the function that is currently being execute

Last in First out

Answer

true

Question 8

Heap/Queue
The heap is an area of memory that is completely independent of the current function or stack frame
The heap is less structured than the stack. You can think of it as just a pile of bits. Your program can add new bits to the pile at any time or modify bits that are already in the pi

First in First out

Answer

true

Question 9

C++ allows you to mark a class as final, which means trying to inherit from it will result in a compiler error. A class can be marked as final with the final keyword right behind the name of the class

Answer

true

Question 10

AlgorithmarrayMax(A, n)                         # operations
      currentMax←A[0]                                [blank_start]2[blank_end]
      for i ← 1 to n − 1 do                            [blank_start]1 +n[blank_end]
                  if A[i] > currentMax then       [blank_start]2(n−1)[blank_end]
                  currentMax ← A[i]                  2(n−1)
                  { increment counter i}           2(n−1)
     return currentMax                              [blank_start]1[blank_end]
                                                                    Total [blank_start]7n−2[blank_end]
Running time: [blank_start]O(n)[blank_end]

Accepted Answer

2

Accepted Answer

1 + n

Accepted Answer

2(n−1)

Accepted Answer

1

Accepted Answer

7n−2

Accepted Answer

O(n)

Question 11

Linear ≈ n
Quadratic ≈ n^2
Cubic ≈ n^3

Answer

true

Question 12

3 n^3+ 20 n^2+ 5
3 n^3+ 20 n^2+ 5 is O(n^3)
need c > 0 and n 0 ≥ 1 such that 3 n^3 + 20 n^2 + 5 ≤ c• n^3 for n ≥ n 0
this is true for c = 4 and n0 = 21

*simple add 1 to constant factors

Answer

true

Question 13

Algorithm prefixAverages1(X, n)
Input array X of n integers
Output array A of prefix averages of X
A ← new array of n integers 
for i ← 0 to n−1 do 
s ← X[0] 
for j ← 1 to i do [blank_start]1 + 2 + ...+(n−1)[blank_end]
s ← s + X[j]
A[i] ← s / (i+1) 
return A

Running Time: [blank_start]O(n^2)[blank_end]

Accepted Answer

O(n^2)

Accepted Answer

1 + 2 + ...+(n−1)

Answer

O(n)

Answer

O(n^3)

Question 14

[blank_start]push(object)[blank_end]: inserts an element
[blank_start]object pop()[blank_end]: removes and returns the last inserted element
[blank_start]object top()[blank_end]: returns the last inserted element without removing it

Accepted Answer

push(object)

Accepted Answer

object pop()

Accepted Answer

object top()

Question 15

Review this lecture for stack using array implementation:
https://slate.sheridancollege.ca/d2l/le/content/563008/viewContent/7718650/View

Answer

true

Question 16

[blank_start]enqueue(object)[blank_end]: inserts an element at the end of the queue
[blank_start]dequeue()[blank_end]: removes and returns the element at the front of the queue
[blank_start]object front()[blank_end]: returns the element at the front without removing it

Accepted Answer

enqueue(object)

Accepted Answer

dequeue()

Accepted Answer

object front()

Question 17

The Vector ADT (similar to Queue ADT) extends the notion of array by storing a sequence of arbitrary objects
An element can be accessed, inserted or removed by specifying its index

Answer

true

Question 18

Review Queue using array based implementation:
https://slate.sheridancollege.ca/d2l/le/content/563008/viewContent/7737114/View

Answer

true

Question 19

A singly linked list is a concrete data structure consisting of a sequence of nodes

Usually made as a struct

Each node stores:
element
link to the next node

struct node {
int value
node* next
}

Answer

true

Question 20

The List ADT models a sequence of positions storing arbitrary objects
It establishes a before/after relation between positions

Answer

true

Question 21

A doubly linked list provides a natural implementation of the List ADT

Nodes implement Position and store:
element
link to the previous node
link to the next node

created as a struct

Answer

true

Question 22

A tree consists of nodes with a parent-child relation

[blank_start]Root[blank_end]: node without parent (A)
[blank_start]Internal[blank_end] node: node with at least one child
[blank_start]External[blank_end] node: node without children
[blank_start]Depth of a node[blank_end]: number of parents
[blank_start]Height of a tree[blank_end]: maximum depth of any node

Accepted Answer

Root

Accepted Answer

Internal

Accepted Answer

External

Accepted Answer

Depth of a node

Accepted Answer

Height of a tree

Question 23

Traversal of tree
visits the nodes of a tree in a systematic manner
a node is visited before its descendants

What order type is this:

Accepted Answer

preorder

Question 24

a node is visited after its descendants

what order type is this:

Accepted Answer

postorder

Question 25

A node is visited after its left subtree and before its right subtree

what order type is this?

Accepted Answer

inorder

Question 26

A priority queue stores a collection of items
An item is a pair(key, element)

[blank_start]insertItem(k, o)[blank_end] inserts an item with key k and element o
[blank_start]removeMin()[blank_end] removes the item with smallest key and returns its element
[blank_start]minKey()[blank_end] returns, but does not remove, the smallest key of an item
[blank_start]minElement()[blank_end] returns, but does not remove, the element of an item with smallest key

Accepted Answer

insertItem(k, o)

Accepted Answer

removeMin()

Accepted Answer

minKey()

Accepted Answer

minElement()

Question 27

review lecture on different priority queue sorting:
https://slate.sheridancollege.ca/d2l/le/content/563008/viewContent/7772392/View

Answer

true

Question 28

Method insertItem of the priority queue ADT corresponds to the insertion of a key k to the heap

The insertion algorithm consists of three steps:
Find the insertion node z (the new last node)
Store k at z and expand z into an internal node
Restore the heap-order property

Answer

true

Question 29

Upheap: (done after an insert node)
restores the heap-order property by swapping k along an upward path from the insertion node
 terminates when the key k reaches the root or a node whose parent has a key smaller than or equal to k

Answer

true

Question 30

remove from a heap:
removeMin of the priority queue ADT corresponds to the removal of the root key from the heap

The removal algorithm consists of three steps:
Replace the root key with the key of the last node w
Compress wand its children into a leaf
Restore the heap-order property

Answer

true

Question 31

Downheap (done after removing a node or replacing the root key):
restores the heap-order property by swapping key k along a downward path from the root
 terminates when key k reaches a leaf or a node whose children have keys greater than or equal to k

Answer

true

Question 32

The dictionary ADT models a searchable collection of key-element items
The main operations of a dictionary are searching, inserting, and deleting items
Multiple items with the same key are allowed

Answer

true

Question 33

In hash tables:
Collisions occur when different elements are mapped to the same cell

can be fixed by increasing prime number

Answer

true

Question 34

review lecture on hash tables and practice allocating keys based on prime number given:
https://slate.sheridancollege.ca/d2l/le/content/563008/viewContent/7784971/View

Answer

true

Question 35

Binary search performs operation findElement(k) on a dictionary implemented by means of an array-based sequence, sorted by key

similar to the high-low game
at each step, the number of candidate items is halved
terminates after O(log n) steps

Answer

true

Question 36

review this lecture on  binary tree searching/deleting/inserting:
https://slate.sheridancollege.ca/d2l/le/content/563008/viewContent/7789913/View

Answer

true

Database Algorithm midterm

Preguntas del test (36)

Información

Escríbenos

¿Qué te parece el nuevo diseño?