CC4 Mid 1, 2, 3 Flashcards

1
Q

Get me from home to work​

Balance my checkbook​

Simulate a jet engine​

Graduate from SPU

A

Solving Problems

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

Designing programs (architecture, algorithms)​

Writing programs​

Verifying programs​

Documenting programs​

A

Using a computer to help solve problems

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

Data Structure and Algorithm Design Goals

A

Correctness
Efficiency
Robustness
Reusability
Adaptability

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

A computer is a machine that manipulates data.​

The prime aim of data structure includes to study how data is organized in a computer, how it is manipulated, how it is retrieved, and how it can be utilized, resulting in more efficient programs.​

A

Data Representation

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

the concealing of the implementation details of data object from the outside world​

A

Data Encapsulation or Information Hiding

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

the SEPARATION between specification of a data object and its implementation​

A

Data Abstraction

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

a collection of objects and set of operations that act on those objects​

Primitive ​

Composite​

A

Data Type

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

Data may be organized in many different ways, the logical or mathematical model of a particular organization of data in memory or on disk is called

A

Data Structure

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

are used for manipulation of data.​

A

Algorithms

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

Accessing each record exactly once so that certain items in the record may be processed.(This accessing or processing is sometimes called ‘visiting” the records.)​

A

Traversing

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

FINDING the location of the record with a given key value, or finding the locations of all records, which satisfy one or more conditions.​

A

Searching

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

Adding new records to the structure.​

A

Inserting/Append

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

Removing a record from the structure.​

A

Deleting

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

Used by OS, compilers, DBMS, data communications​

Image processing, digital signal processing, simulations, numerical computations, cryptography, data compressions and genetic studies​

A

Usage of Data Structures / Data Structures +Algorithm

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

Mainly to represent data containing a hierarchical relationship between elements

A

Tree
Graph

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

Its elements form a sequence or in other words a linear list.

A

Array
Stack
Queue
Linked List

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q

Quick insertion, very fast access if index is known

A

Arrays

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
18
Q

Quicker search than unsorted array.

A

Ordered Array

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
19
Q

Provides last in first out access

A

Stack

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
20
Q

Provides first in first out access

A

Queue

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
21
Q

Quick insertion and quick deletion

A

Linked List

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
22
Q

Quick search, insertion and deletion if tree remains balance

A

Binary Trees

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
23
Q

Very fast access if key known, Fast insertion

A

Hash Table

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
24
Q

Fast insertion, deletion. Access to largest item

A

Heap

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
25
Q

Models real world situation

A

Graph

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
26
Q

Zero or more quantities are externally supplied

A

Input

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
27
Q

At least one quantity is produced​

A

Output

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
28
Q

Each instruction is clear and unambiguous

A

Definiteness

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
29
Q

If we trace out the instructions of an algorithm, then, for all cases, the algorithm terminates after a FINITE number of steps​

A

Finiteness

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
30
Q

every instruction must be basic enough to be carried out, in principle, by a person using only pencil and paper. Its not enough that each operation be definite as in (3): it also must be feasible.​

A

Effectiveness

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
31
Q

must be well defined and unambiguous (what about portability?)​

A

Natural Language

32
Q

flowcharts (only for small and simple algorithms)​

A

Graphic Representation

33
Q

low level implementation must be ​

removed and replaced by natural language​

A

Programminglanguages

34
Q

‘Any program that can be written using assignment,​

the if else statement and the while statement can also be written using assignment, if-­else and recursion.’’ ​

A

Theorem

35
Q

the amount of memory needed by a program to​

run to completion​

A

Space Complexity

36
Q

the amount of computer time needed by a ​

program to run to completion ​

A

Time complexity

37
Q

a PRIORI estimates; ​

A

Performance Analysis

38
Q

a POSTERIORI testing.​

A

Performance Measurement

39
Q

This is a THEORITICAL analysis of an algorithm. Efficiency of an algorithm is measured by assuming that all other factors, for example, processor speed, are constant and have no effect on the implementation.​

A

A Priori Analysis

40
Q

This is an EMPIRICAL analysis of an algorithm. The selected algorithm is implemented using programming language. This is then executed on target computer machine. In this analysis, actual statistics like running time and space required, are collected.

A

A Posterior Analysis

41
Q

independent of the characteristics (e.g. number, size) of ​

the inputs and outputs ​

instruction space (space of the code itself) ​

space for constants, … –​

A

Fixed Part

42
Q

dependent on the particular problem instance being ​

solved, hence on the inputs and outputs characteristics​

variables whose size depends on inputs/outputs, ​

recursion stacks (when it depends on inputs/outputs).​

A

Variable Part

43
Q

Types of Analysis

A

Worst Case Running Time

Average Case Running Time

Best Case Running Time

44
Q

is the longest running time for any input of size n​

A

Worst Case Running

45
Q

Often it is assumed that all inputs of a given size are equally likely.​

A

Average Running Time

46
Q

rarely occurs in practice comparatively with the first and second case.

A

Best Case Running Time

47
Q

is a way of solving a problem or calculation in less time by using more storage space (or memory), or by solving a problem in very little space by spending a longtime.​

A

Time Space Tradeoff

48
Q

Is a conclusion of homogenous, ordered, and finite set of elements

A

Array

49
Q

Implies all elements must be off the SAME TYPE and have the same structure

A

Homogenous

50
Q

Means that elements are organized in sequence

A

Finite

51
Q

Are BUILT into a programming language with no extra definition needed in the part of the programmer

A

Primitive data type

52
Q

T or F

An array uses a single variable to represent a large set of homogenous data collection

A

True

53
Q

T or F

An array provides direct access to a storage area for an element

A

True

54
Q

T or F

The elements on an array can be manipulated easily using an index

A

True

55
Q

T or F

It is easy to create and initialize an array

A

True

56
Q

T or F

Arrays are good at implementing iterative algorithms

A

True

57
Q

T or F

Number dimensional arrays facilitate grouping of data collection into hierarchical structure

A

True

58
Q

T or F

Array size cannot be undressed or decreased during runtime

A

True

59
Q

T or F

Insertion and deletion in arrays are not efficient

A

True

60
Q

For every large data sets the may run out of the storage space

A

True

61
Q

In an array the position of an element is identified by a variable called

A

Index

62
Q

The range of values is for the INDEX is referred to as

A

Index Set

63
Q

Smallest value in of index is called ____ and largest ____

A

Lower bound, Upper bound

64
Q

Individual elements of an array are identified by an ____ and _____

A

Array name, array index

65
Q

Represents arrangement of data elements in the MEMORY

A

Storage structure

66
Q

ADDRESS of the first elements is called

A

Base address

67
Q

Retrieving, it is also called

A

Accessing

68
Q

The last element points to

A

NULL

69
Q

removes all elements of the list (disposes the list)​

A

Delete List

70
Q

returns the NUMBER of elements in the list​

A

Count

71
Q

also called as growable array, resizable array, DYNAMIC table, or array list

A

Dynamic Array

72
Q

Advantage of linked lists is that they can​

be expanded in

A

constant time

73
Q

Disadvantage of linked lists is

A

access time to individual elements

74
Q

function takes a linked list as input and counts the number of nodes in the LIST.​

A

List Length

75
Q
A