CC4 Mid 1, 2, 3

Question 1

Get me from home to work​

Balance my checkbook​

Simulate a jet engine​

Graduate from SPU

Answer 1

Solving Problems

Question 2

Designing programs (architecture, algorithms)​

Writing programs​

Verifying programs​

Documenting programs​

Answer 2

Using a computer to help solve problems

Question 3

Data Structure and Algorithm Design Goals

Answer 3

Correctness
Efficiency
Robustness
Reusability
Adaptability

Question 4

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.​

Answer 4

Data Representation

Question 5

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

Answer 5

Data Encapsulation or Information Hiding

Question 6

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

Answer 6

Data Abstraction

Question 7

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

Primitive ​

Composite​

Answer 7

Data Type

Question 8

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

Answer 8

Data Structure

Question 9

are used for manipulation of data.​

Answer 9

Algorithms

Question 10

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.)​

Answer 10

Traversing

Question 11

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

Answer 11

Searching

Question 12

Adding new records to the structure.​

Answer 12

Inserting/Append

Question 13

Removing a record from the structure.​

Answer 13

Deleting

Question 14

Used by OS, compilers, DBMS, data communications​

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

Answer 14

Usage of Data Structures / Data Structures +Algorithm

Question 15

Mainly to represent data containing a hierarchical relationship between elements

Answer 15

Tree
Graph

Question 16

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

Answer 16

Array
Stack
Queue
Linked List

Question 17

Quick insertion, very fast access if index is known

Answer 17

Arrays

Question 18

Quicker search than unsorted array.

Answer 18

Ordered Array

Question 19

Provides last in first out access

Answer 19

Stack

Question 20

Provides first in first out access

Answer 20

Queue

Question 21

Quick insertion and quick deletion

Answer 21

Linked List

Question 22

Quick search, insertion and deletion if tree remains balance

Answer 22

Binary Trees

Question 23

Very fast access if key known, Fast insertion

Answer 23

Hash Table

Question 24

Fast insertion, deletion. Access to largest item

Answer 24

Heap

Question 25

Models real world situation

Answer 25

Graph

Question 26

Zero or more quantities are externally supplied

Answer 26

Input

Question 27

At least one quantity is produced​

Answer 27

Output

Question 28

Each instruction is clear and unambiguous

Answer 28

Definiteness

Question 29

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

Answer 29

Finiteness

Question 30

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.​

Answer 30

Effectiveness

Question 31

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

Answer 31

Natural Language

Question 32

flowcharts (only for small and simple algorithms)​

Answer 32

Graphic Representation

Question 33

low level implementation must be ​ removed and replaced by natural language​

Answer 33

Programming languages

Question 34

'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.'' ​

Answer 34

Theorem

Question 35

the amount of memory needed by a program to​ run to completion​

Answer 35

Space Complexity

Question 36

the amount of computer time needed by a ​ program to run to completion ​

Answer 36

Time complexity

Question 37

a PRIORI estimates; ​

Answer 37

Performance Analysis

Question 38

a POSTERIORI testing.​

Answer 38

Performance Measurement

Question 39

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.​

Answer 39

A Priori Analysis

Question 40

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.

Answer 40

A Posterior Analysis

Question 41

independent of the characteristics (e.g. number, size) of ​ the inputs and outputs ​ instruction space (space of the code itself) ​ space for constants, ... –​

Answer 41

Fixed Part

Question 42

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).​

Answer 42

Variable Part

Question 43

Types of Analysis

Answer 43

Worst Case Running Time Average Case Running Time Best Case Running Time

Question 44

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

Answer 44

Worst Case Running

Question 45

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

Answer 45

Average Running Time

Question 46

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

Answer 46

Best Case Running Time

Question 47

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.​

Answer 47

Time Space Tradeoff

Question 48

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

Answer 48

Array

Question 49

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

Answer 49

Homogenous

Question 50

Means that elements are organized in sequence

Answer 50

Finite

Question 51

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

Answer 51

Primitive data type

Question 52

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

Answer 52

True

Question 53

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

Answer 53

True

Question 54

T or F The elements on an array can be manipulated easily using an index

Answer 54

True

Question 55

T or F It is easy to create and initialize an array

Answer 55

True

Question 56

T or F Arrays are good at implementing iterative algorithms

Answer 56

True

Question 57

T or F Number dimensional arrays facilitate grouping of data collection into hierarchical structure

Answer 57

True

Question 58

T or F Array size cannot be undressed or decreased during runtime

Answer 58

True

Question 59

T or F Insertion and deletion in arrays are not efficient

Answer 59

True

Question 60

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

Answer 60

True

Question 61

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

Answer 61

Index

Question 62

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

Answer 62

Index Set

Question 63

Smallest value in of index is called ____ and largest ____

Answer 63

Lower bound, Upper bound

Question 64

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

Answer 64

Array name, array index

Question 65

Represents arrangement of data elements in the MEMORY

Answer 65

Storage structure

Question 66

ADDRESS of the first elements is called

Answer 66

Base address

Question 67

Retrieving, it is also called

Answer 67

Accessing

Question 68

The last element points to

Answer 68

NULL

Question 69

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

Answer 69

Delete List

Question 70

returns the NUMBER of elements in the list​

Answer 70

Count

Question 71

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

Answer 71

Dynamic Array

Question 72

Advantage of linked lists is that they can​ be expanded in

Answer 72

constant time

Question 73

Disadvantage of linked lists is 

Answer 73

access time to individual elements

Question 74

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

Answer 74

List Length