Final Exam Flashcards
(31 cards)
What is the definition of Big-Oh notation?
The order or an algorithm. Describes the upper bound of the algorithm.
The amount of memory needed to perform the algorithm
The Average case scenario.
Describes the best possible outcome.
The order or an algorithm. Describes the upper bound of the algorithm.
What is meant by the term big Omega of an algorithm?
The worst-case scenario
The average case scenario
The mean time scenario
A formal way to express the lower bound of an algorithm’s running time.
A formal way to express the lower bound of an algorithm’s running time.
There are four general rules for calculating run times for for loops, nested loops, consecutive statements and if/else. Which one applies to Consecutive Statements?
Rule 1
Rule 3
Rule 4
Rule 2
Rule 3
What , in general, is the order of a binary search algorithm?
O(nlog(n))
What is the big O or order of a bubble sort?
O(log(n))
O(n2)
O(Log(n2))
O(n2)
O(n2)
What does ADT stand for?
American Distinct Telegram
Abstract Data Type
Abstract Digital Template
Abnormal Digital Template
Abstract Data Type
Which of the following statements is true about a list ADT?
At least a single linked list must be used.
It can be implemented using an Array.
The list must be dynamically allocated.
Neither a doubly or singly linked list can be used because an array is direct access.
It can be implemented using an Array.
How do you insert into a single linked list?
There are no insertions once the list is initially created. To insert a record you have to create a new list.
Insertions are always done at the end of the list.
You must keep track of the record after and before of where it goes so you can change the links.
Insertions are always done at the beginning of the list
You must keep track of the record after and before of where it goes so you can change the links.
What is the relationship between a vector and a list?
Lists cannot be searched, vectors can.
Records in the List ADT can cheaply be inserted and deleted, The vector ADT can be indexed in constant time.
The list uses doubly linked lists, the vector uses arrays.
They are the same.
Records in the List ADT can cheaply be inserted and deleted, The vector ADT can be indexed in constant time.
Which ADT would be most commonly used to evaluate postfix notations?
Queue
Stack
Binary Tree
Dequeue
Stack
What is the definition of a binary tree?
A tree in which no node may have more than two children.
A tree with only two nodes
A tree that must have either one or two nodes
A tree that can only go up and down
A tree in which no node may have more than two children.
An arithmetic expression is usually expressed in human terms as what type of notation?
Inorder
Postorder
Aft Order
stern order
Inorder
The average depth of a binary search tree, based upon the number of nodes (N) is?
O(log(N))
O(N )
O(Nlog(N))
O(N2)
O(log(N))
What does AVL stand for?
Adelson-Velskii and Landis Tree
Automated Directed Landis Tree
A latin term meaning balanced tree
Advanced-Data structure linear
Adelson-Velskii and Landis Tree
What is a major characteristic of a B tree?
The data is stored in leaves.
All of the data is in the left child.
All of the data is in the right child.
The root is never a leaf.
The data is stored in leaves.
Each key of a record or group of data is mapped into some number that ranges from 0 to the Tablesize-1 and placed in the appropriate cell. The mapping is called a _______________________.
Table Function
Boolean Function
Mapping Function
Hash Function
Hash Function
When two keys generate the same hash it is called a ___________________.
Merger
Meeting
Hashed
Collision
Collision
A hash function should have certain desirable properties. What is one of them?
They should always use the MOD function.
They should not create randomly distributed values.
The function should create an even distribution of hash values.
They should never use more than the first three characters of the key
The function should create an even distribution of hash values.
What did the book say about English?
English is not a second language
English is not random.
English is non-ambiguous.
Words in the English Language are good values for hash functions
English is not random.
What is separate chaining
To keep a list of all elements that hash to the same value.
A priority Queue is a data structure that allows at least the following operations: add and remove both front and back insert and delete insert and deleteMin addback and removefront
insert and deleteMin
What is a graph?
Any data structure
A graphical image
A graph G = (V,E) where V stands for vertices and E stands for Edges
ny vector
A graph G = (V,E) where V stands for vertices and E stands for Edges
What statement best describes a path?
The distance from one not to another
A sequences of vertices w1, w2, w3 .. wn such that (wi, wi+1) is contained in E.
The method of accessing an individual node.
Any sequence of indexes that allow you to iterate through the list
A sequence of vertices w1, w2, w3 .. wn such that (wi, wi+1) is contained in E.
A simple path is one where all vertices are________.
the same
distinct
obtuse
intrusive
distinct
