Section 7-Data structures
Study these flashcardsFree · spaced repetition · iPhone, Android, Mac & web
All cards
1
Image occlusion: name the hidden labels
2
1)Why does a subroutine use local variables in a stack
1)accessible and usable only within the subroutine and is quicker
much more efficient than using dynamic memory allocation, which uses heap space.
much more efficient than using dynamic memory allocation, which uses heap space.
3
1)Whats trasnposing in matrix
1)swap the rows and columns and put T in right hand corner to show
(6 4 24)T (6 1)
(1 -9 9) = ( 4 -9)
(24 8)
(6 4 24)T (6 1)
(1 -9 9) = ( 4 -9)
(24 8)
4
1)Whats the folding method?
2)How to deal with collison in hashing
2)How to deal with collison in hashing
1)divides the item into equal parts, and adds the parts to give the hash value.
2) size table designed so when all the items are stored, only 70% of the table's cells are occupied.
2) size table designed so when all the items are stored, only 70% of the table's cells are occupied.
5
1)Whats a use for a call stack?
2)What does a recursive subroutine do in a stack?
3)What happens when recurison ends?
2)What does a recursive subroutine do in a stack?
3)What happens when recurison ends?
1)store information about the active subroutines while a computer program is running.
2) may contain several calls to itself, so that with each call, a
new item (the return address) is pushed onto the stack
3) item popped one after the other, each time the end of the subroutine is reached.
2) may contain several calls to itself, so that with each call, a
new item (the return address) is pushed onto the stack
3) item popped one after the other, each time the end of the subroutine is reached.
6
1)Whats a adjaceny list
2)How does adjaceny list use dictonaries
3)does unweighted list use dictionary
2)How does adjaceny list use dictonaries
3)does unweighted list use dictionary
1) nodes created, each node points to a list of all the adjacent nodes to which it is directly linked
2)key in each dictionary being the node and the value, the edge weight.
3) not required here as there are no edge weights
2)key in each dictionary being the node and the value, the edge weight.
3) not required here as there are no edge weights
7
1)What is a free item in a linked list called as a pointer
1)nextfree
8
1)What if eges are weighted
1) to show there is a cost to go from one vertex to another e.g. distance
9
1)What does MOD mean?
2)Whats a hash table?
2)Whats a hash table?
1)Divide by
2) collection of items stored in such a way that they can quickly be located.
2) collection of items stored in such a way that they can quickly be located.
10
1)What does a record do?
2)Where is a record stored?
2)Where is a record stored?
1) contains a number of fields, each holding one item of data.
2) In a file
2) In a file
11
1)What data structure does a stack have?
2)Static or dynamic
2)Static or dynamic
1)Last In, First Out (LIFO) data structure.
2)Both
2)Both
12
1)Uses of a Hashing table?
2)Define dictonairy
2)Define dictonairy
1)index,look up peoples info,users codes /passwords
2)abstract data type consisting of associated pairs of items, where each pair consists of a key and a value.
2)abstract data type consisting of associated pairs of items, where each pair consists of a key and a value.
13
1)Pros of a adjacency matrix
2)Cons of adjacency matrix
2)Cons of adjacency matrix
1)very convenient to work with, adding edge is very simple
2)leaves most of the cells empty- larger graph, more memory space will be wasted.
harder to add or delete nodes.
2)leaves most of the cells empty- larger graph, more memory space will be wasted.
harder to add or delete nodes.
14
1)Problem with matrices
2)How add materices
2)How add materices
1)limited to only 2 dimensions
2)Add the number in matching postion:
(3 8) ( 4 0 ) = (7 8)
(4 6) + ( 1 -9) (5 -3)
2)Add the number in matching postion:
(3 8) ( 4 0 ) = (7 8)
(4 6) + ( 1 -9) (5 -3)
15
1)How to use a hash tabel
1)apply hashing algorithm to the key field of the item ,examine the resulting cell in the list
if item is there, return the item. if cell is empty, item is not in the table
if another item in that spot, keep moving forward until either the item is found or
blank cell is encountered, when it is apparent that the item is not in the table
if item is there, return the item. if cell is empty, item is not in the table
if another item in that spot, keep moving forward until either the item is found or
blank cell is encountered, when it is apparent that the item is not in the table
16
1)How to Post-order traversal
1)Draw an outline around the tree structure, starting to the left of the root.
As you pass to the right of anode (where the red dot is marked), output the data in that node.
As you pass to the right of anode (where the red dot is marked), output the data in that node.
17
1)How to Pre-order traversal
2)How to In-order traversal
2)How to In-order traversal
1)Draw an outline around the tree structure, starting to the left of the root.
pass to the left of a node(where the red dot is marked), output the data in that node
2)Draw an outline around the tree structure, starting to the left of the root.
pass underneath a node(where the red dot is marked), output the data in that node
pass to the left of a node(where the red dot is marked), output the data in that node
2)Draw an outline around the tree structure, starting to the left of the root.
pass underneath a node(where the red dot is marked), output the data in that node
18
1)How subtract materices
2)Subtract numbers in matching postion:
(3 8) ( 4 0 ) = (-1 8)
(4 6) - ( 1 -9) (3 15)
(3 8) ( 4 0 ) = (-1 8)
(4 6) - ( 1 -9) (3 15)
19
1)How store info about a graph
1)two-dimensional array -Each of the rows and columns represents
node, and a value stored in the cell at the intersection of row
node, and a value stored in the cell at the intersection of row
20
1)How is a call stack composed?
A call stack is composed of stack frames.
Each stack frame corresponds to a call to a subroutine which has not yet terminated
Each stack frame corresponds to a call to a subroutine which has not yet terminated
21
1)How deal with Negative matrix
-(2 -4) = (-2 4)
(7 10) (-7 -10)
-(2)=-2
(7 10) (-7 -10)
-(2)=-2
22
1)How are 3 dimensional arrays referred to?
3-dimensional array x, a particular element may be referred to as x [4, 5, 2],
23
1)Define Tuples
2)Problems of tuples
2)Problems of tuples
1)ordered set of values, which could be elements of any type
2)elements cannot be changed, and you cannot dynamically add elements to or delete elements from a tuple.
2)elements cannot be changed, and you cannot dynamically add elements to or delete elements from a tuple.
24
1)Define node
2)Define Edge
3)Define Root
2)Define Edge
3)Define Root
1)nodes contain the tree data
2)edge connects two nodes. everyone except root is connected exactly one edge from another node
3)the only node that has no incoming edges
2)edge connects two nodes. everyone except root is connected exactly one edge from another node
3)the only node that has no incoming edges
25
1)Define linked list
2)What does each item have on linked list
3)What does the item in list have
2)What does each item have on linked list
3)What does the item in list have
1)dynamic data structure used to hold an ordered sequence
2) data field and a next address field called a link /pointer field =actual data associated with the list item
and has address of next in list
3)use of a null pointer.
2) data field and a next address field called a link /pointer field =actual data associated with the list item
and has address of next in list
3)use of a null pointer.
26
1)Define Graph
2)what way are edges in a undirected graph
3)What call a gragh If the edges in a graph are all one-way
2)what way are edges in a undirected graph
3)What call a gragh If the edges in a graph are all one-way
1)graph is a set of vertices or nodes connected by edges or arcs. The edges may be one-way or two-way.
2)Bi-directional
3)the graph is said to be a directed graph or digraph.
2)Bi-directional
3)the graph is said to be a directed graph or digraph.
27
1)Define Child
2)Define Parent
3)Define subset
4)Define leaf node
2)Define Parent
3)Define subset
4)Define leaf node
1)set of nodes that have incoming edges from the same node
2)connects to with outgoing edges
3)set of nodes and edges comprised of a parent and all descendants of the parent
4) node that has no children
2)connects to with outgoing edges
3)set of nodes and edges comprised of a parent and all descendants of the parent
4) node that has no children
28
1)Define binary tree
2)When do u branch left?
3)When do u branch right?
2)When do u branch left?
3)When do u branch right?
1)rooted tree in which each node has a maximum of two children
2) if item is less than value of current node
3) if item is greater than value of current node.
2) if item is less than value of current node
3) if item is greater than value of current node.
29
1)Define a list
2)How insert item in a list
2)How insert item in a list
1)abstract data type consisting of a number of items in which the same item may occur more than once.
2)Test list if already full, print message if it is and quit
Determine where new item needs to be inserted
Starting at the end of the list, move other items along one place =Insert new item in correct place
2)Test list if already full, print message if it is and quit
Determine where new item needs to be inserted
Starting at the end of the list, move other items along one place =Insert new item in correct place
30
1)Define 1-dimensional arrays
2)How can 2 array dimensionals be shown?
3)is array static or dyanmic
2)How can 2 array dimensionals be shown?
3)is array static or dyanmic
1) finite, ordered set of elements of the same type, such as integer, real or char.
2)table, rather like a spreadsheet. with 3 rows and 4 columns.
3)Static
2)table, rather like a spreadsheet. with 3 rows and 4 columns.
3)Static
31
1) what does push(item) do in a stack
2) what does pop() do in a stack
3)what does peek() do in a stack
4)What does isEmpty() do ?
5)What does isFull() do?
2) what does pop() do in a stack
3)what does peek() do in a stack
4)What does isEmpty() do ?
5)What does isFull() do?
1)adds a new item to the top of the stack.
2)removes and returns the top item from the stack
3) returns the top item from the stack but does not remove it.
4)tests to see whether the stack is empty
5)tests to see whether the stack is full
2)removes and returns the top item from the stack
3) returns the top item from the stack but does not remove it.
4)tests to see whether the stack is empty
5)tests to see whether the stack is full
32
1) how Multiply constant in materices
This case is 2:
2x(4 0) = (8 0)
(1 -9) (2 -18)
2x(4 0) = (8 0)
(1 -9) (2 -18)
33
1) Define Depth-first traversal
2) Define Breadth-first search
2) Define Breadth-first search
1) go as far down one route before backtracking and taking the next route.
2)we visit all the neighbours of a node, and then all the neighbours of the first node visited
2)we visit all the neighbours of a node, and then all the neighbours of the first node visited