Unit 2

Question 1

array

Answer 1

data structure which contains several items of the same data type
-can be thought of as table, with bounds (0-n) and index/subscript

Question 2

tuple

Answer 2

ordered list of elements

Question 3

initializing an array

Answer 3

amount of space needed has to reserved
+change bounds to change num of elements
+declare elements in one statement
+loop structures for quick proccessing
+single identifier

Question 4

list

Answer 4

abstract data structure and dynamic

Question 5

records

Answer 5

different data types, data structure which consists of a collection of elements, each separate item is a field (fixed length)

Question 6

file

Answer 6

each row is a record, each separate item (piece of data) in record is called field
-all records have the same number of fields and all fields have same fata type
-need a key field or primary key

Question 7

initializing an array

Answer 7

int[] Votes = new int[4]

Question 8

static

Answer 8

cannot change size while program is running (array)

Question 9

dynamic

Answer 9

can change size as program is running (linked list, tree)

Question 10

data held serially

Answer 10

points to next item in list

Question 11

data held sequentially

Answer 11

points to next item of data in alphabetical order

Question 12

pointer

Answer 12

indicating the address of the start of the list

Question 13

linked list

Answer 13

not all space in use,free space indicated as list and used for other things

Question 14

heap

Answer 14

memory space allocated for data structure to grow

Question 15

queue

Answer 15

first in first out data structure, front and rear pointer (when empty rear pointer is -1), circular queues override date, priority queue

Question 16

stack

Answer 16

last in first out

Question 17

graph

Answer 17

dynamic data structure commonly used to represent several types of data network

Question 18

dense

Answer 18

more edges than nodes

Question 19

sparse

Answer 19

more nodes than edges

Question 20

weighted

Answer 20

edges are given values

Question 21

directed

Answer 21

edges given direction

Question 22

node

Answer 22

the point with the information you want to get

Question 23

edges

Answer 23

how you get from one node to the next (lines)

Question 24

degree

Answer 24

how many edges come off a node

Question 25

bidirectional

Answer 25

edges without arrows

Question 26

adjacency matrix

Answer 26

stores graphs as matrix (symmetrical for undirected graph) +simple to implement as 2D array +quick to add edges and check for existence +best for dense graphs with changing edges -static

Question 27

adjacency list

Answer 27

stores graph as list +memory efficient for large sparse graphs +easy to add and delete nodes

Question 28

tree

Answer 28

connected, undirected graph without cycles

Question 29

root

Answer 29

parent node, parent-child relationship with all other nodes

Question 30

binary tree

Answer 30

rooted with each node having at most two children

Question 31

traverse

Answer 31

if lower than current root: left, if higher: right and then insert data at correct place

Question 32

deleting nodes

Answer 32

mark as deleted to keep structure or delete and copy into new tree

Question 33

hash table

Answer 33

data structure which creates a mapping between keys and values, used when data needs to be found quickly

Question 34

hashing algorithm

Answer 34

decides location in which item gets stored -each item stored in a numbered or indexed slot

Question 35

collision

Answer 35

when hashing algorithm produces 2 same key values for different things

Question 36

what to do with collision

Answer 36

-linked list (chaining), a overflow structure -rehashing, another hashing algorithm or next available space, can take up processing time

Question 37

adding items with hashing algorithm

Answer 37

input item, perform the algorithm, output hash value h as storage location and store item there

Question 38

searching for item with hashing algortihm

Answer 38

input s to find, perform algorithm on s, output h as storage location, if item there matches s, output required data

Question 39

dictionaries

Answer 39

a collection of key-value pairs in which the value is accessed via associated key -more abstract than hashing algorithm -built in data types -data in pairs, first item is key, the other item is the value