Quiz
D-Structures and Algorithms Midterm
This quiz has question types that open in the usual player.
Questions in this quiz (27)
1An algorithm is a step-by-step procedure for solving a problem in a finite amount of time.
- ATrue
- BFalse
2Algorithms (choose correct)
- Atransform input objects --> output objects
- Bruntime grows with input size
- CAverage case size difficult to determine, focus on WORST CASE RUN TIME
- DBest case size is most difficult to determine
3To compare two algorithms same hardware and software must be used. Implementing algorithms is important, but difficult.
- ATrue
- BFalse
4Theoretical Analysis of an algorithm
- Auses high level description of the algorithm instead of an implementation
- Bcharacterizes run time as f(x) of input size (n) and accounts for all possible inputs
- Cenables speed evaluation of algorithm independent of software/hardware
- Dunable to do speed evaluation of algorithm independent of software/hardware
5Pseudocode:
- Ahigh level description of an algorithm
- BMore structured than English prose, but less detailed than program
- Chides program design issues
- Dallows you to see program design issues.
6Primitive Operations
- Abasic computations performed by an algorithm
- Blargely independent of programming language
- Cassumed to take constant time in RAM model
- Didentifiable in pseudocode
7Growth Rate of Running Time
- Achanges with hardware/software
- BAffects T(n) by constant factor
- CAlters the growth rate of T(n)
- DDoes not alter the growth rate of T(n)
8The growth rate of an algorithm is
- Anot affected by constant factors
- Bnot affected by lower order terms
- Cis affected by constant factors
9Big-Oh notation: given f(n) and g(n), f(n) is O(g(n)) if positive constants c and n(v 0) such that:
f(n) <= cg(n) for n >= n(not)- ATrue
- BFalse
10Big Oh notation
- Agive upper bound on growth rate of fun
- Bfunctions are ranked according to growth rate:
11 f(n) is O(g(n)) g(n) is O(g(n))
g(n) grows more [blank_start]YES NO[blank_end]
g(n) grows more [blank_start]NO YES[blank_end]
same growth [blank_start]YES YES[blank_end]- AYES NO
- BNO
- CNO YES
- DYES YES
- EYES YES
- FNO NO
12What do we mean by data?
- Adata are the nouns of the programming world
- Bto separate the computer's view of data from our own view, we
use data abstraction to create other views. - CData abstraction The separation of a data type's logical properties from its implementation
- DData subtraction The separation of a data type's logical properties from its implementation
- Eyou simply use integers and what operations are allowed on integers
13Data Encapsulation is:
- Athe physical representation of a program's data is surrounded. The user of the data doesn't see the implementation, but deals with the data only in terms of its logical picture—its abstraction.
- BThe separation of a data type's logical properties from its implementation
- CDoes not include information hiding like protected, private.
14Abstract Data Type (ADT)
- AAbstract data type (ADT) A data type whose properties (domain and operations) are specified independently of any particular implementation
- BThe goal in design is to increase complexity through abstraction.
- CAbstract data type (ADT) A data type whose properties (domain and operations) are specified codependent of any particular implementation
15Data Structures:
- AData that have lots of parts, such as a list.
- BA collection of data elements whose organization is characterized by accessing operations that are used to store and retrieve the individual data elements;
- Cthe implementation of the composite data members in an abstract data type
16Difference between Abstract Data Type and Data Structures:
- AADT is a high-level description: the logical picture of the data and the operations that manipulate them.
- BData Structure is concrete: a collection of data elements and the operations that store and retrieve individual elements.
- CADT is implementation independent, whereas a data structure is implementation dependent.
- Dhow 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.
- EADT is implementation dependent
17What are the 3 Data Structure Levels?
- AApplication (or user) level: A way of modeling real-life data in a specific context; also called the problem domain (what do you want to do?)
- BLogical (or abstract) level: An abstract view of the data values (the domain) and the set of operations to manipulate them (UML diagrams)
- CImplementation level: A specific representation of the structure to hold the data items, and the coding of the operations in a programming language (if the operations are not already provided by the language)
- DRepresentation level: A way of modeling real-life data in a specific context; also called the problem domain (what do you want to do?)
18 Abstract Data Type Operation Categories are:
- AConstructor: creates new instance of a class
- BTransformer: changes the internal state of an
object - CObserver: operation that allows us to observe the state of an object without changing it
- DIterator: allows us to process all components in a data structure sequentially.
- EDeconstructor: creates new instance of a class
19Composite Data Types:
- Adata type that allows a collection of values to be associated with an object of that type
- Bstructured: d collection of components in which the organization determines the method used to access individual data components.
- Cunstructured : collection of components that are not organized with respect to one another.
20Composite Type Examples include:
- ARecords: structs and classes
- BOne dimensional or multidimensional arrays
- Cpython structure
21Three main categories of scope e
- Aclass scope
- Blocal scope { }
- Cglobal scope
- Dvariable scope
22Stack: The current top card represents the current scope of the program, usually the function that is currently being executed.
• All variables declared inside the current function will take up memory in the top stack frame, the top card of the deck.- ATrue
- BFalse
23The heap is an area of memory that is completely independent of the current function or stack frame.
- ATrue
- BFalse
24Heap:
- Avariables on the heap if you want them to exist even when the function in which they were created has completed.
- Bless structured than the stack.
- Cdeallocate (delete) any memory that you allocated on the heap.
- Dput anything on the heap by explicitly allocating memory for it using a pointer
- Eyou should always declare and initialize your pointers at the same time.
25Pointers
- Ain dereferencing youare not changing the pointer; you are changing the memory that it points to.
- Bdynamically allocate arrays. You use the new[]
26Use final to
- Aprevent inheritance
- Bub class tries to inherit from the Super class, but this will result in a compiler error because Super is marked as final.
27Structured components of the Standard Template library (3x)
- AContainers: manage objects of a certain kind: deque, list, vector, map
- BAlgorithms: initialization, sorting, searching, and transforming of the contents of containers.
- CIterators are used to step through the elements of collections of objects.
- DVectors to help with template sorting
Information
- Description
- Quiz on D-Structures and Algorithms Midterm, created by Upma Sharma on 11/01/2019.
- Author
- Upma Sharma
- Language
- English
- Views
- 2
- History
- Created on 11 Jan 2019 · updated on 21 Jan 2019
- Rating
- No ratings yet Rate this quiz