Brainscape's Knowledge GenomeTM

Browse over 1 million classes created by top students, professors, publishers, and experts.


See full index

Computer Science > Unit 7 - Data Structures > Flashcards

Unit 7 - Data Structures Flashcards

1
Q

define array

A

a finite, ordered set of elements of the same type.

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

what is a 2-dimensional array

A

a collection of data elements arranged in a grid-like structure with rows and columns

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

define tuple

A

an ordered set of values, which could be elements of any type (images, sound files, strings,etc) that is immutable, which means that elements cannot be changed, and you cannot dynamically add elements or delete elements form a tuple.

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

what’s the difference between static and dynamic data types

A

dynamic data types - change size when required (lists grow when items are added and shrink when items are removed). it does this with the aid of heap (specific area of memory)
static data types - cannot change size (array)

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

what is an abstract data type

A

one that is created by a programmer
- a logical description of how the data is viewed and the operations that can be performed on it

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

what is an elementary data type

A

defined within the programming language

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

what are the four operations with a queue

A
  • enQueue(item)
  • deQueue
  • isEmpty
  • isFull
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

what is a queue

A

a queue is a first in first out data structure. new elements can only be added to the end of the queue, and elements may only be retrieved from the front of the queue

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

applications of queues

A
  • printing from computers (print queue)
  • typing on a keyboard
  • simulations
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

what does enQueue(item) do

A

add a new item to the rear of the queue

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

what does deQueue() do

A

remove the front item from the queue

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

what does isEmpty() for queues do

A

test to see whether the queue is empty

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

what does isFull() for queues do

A

test to see whether queue is full

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

what is a circular queue

A

one way of overcoming the limitation of a static data structure by reusing the spaces that have been freed by dequeuing from the front of the array. If you see a MOD and a length function when looking at lists you will know that it is a circular queue.

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

pseudocode to initialise a circular queue

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

pseudocode to test for an empty queue

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

pseudocode to test for a full queue

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

pseudocode to add an element to the queue

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

pseudocode to remove an item from the queue

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

what is a priority queue

A

it acts like a queue in that items are dequeue by removing them from the font of the queue. however, the logical order of items within the queue is determined by their priority, with the highest priority items at the front of the queue and the lowest priority items at the back.

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

what is a list

A

an abstract data type consisting of a number of items in which the same item may occur more than once

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

what are the main operations on lists

A
  • isEmpty()
  • append(item)
  • remove(item)
  • search(item)
  • length()
  • index(item)
  • insert(pos, item)
  • pop()
  • pop(pos)
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
23
Q

what does isEmpty() on lists do

A

test for empty list

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

what does append(item) do

A

add a new item to list to the end of the list

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

what does remove(item) do

A

remove the first occurrence of an item from list

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

what does search(item) do

A

search for an item in the list

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

what does length() do

A

return the number of items

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

what does index(item) do

A

return the position of item

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

what does insert(pos, item) do

A

insert a new item at position pos

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

what does pop() do

A

remove and return the last item in the list

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

what does pop(pos) do

A

remove and return the item at position pos

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

what is a linked list

A

a linked list is a dynamic data structure used to hold an ordered sequence
- items which form the sequence are not necessarily held in contiguous data locations
- each item in the list is called a node and contains a data field and a next address field called a link or pointer field
- the data field holds the actual data associated with the list item, and the pointer field contains the next item in the sequence
- the link field indicates that there are no further items by the use of a null pointer

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

pseudocode the enQueue() list

A

procedure enqueue(item)
if q.isFull() then
print (“queue full”)
else
q.append(item)
endif
endprocedure

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

pseudocode for deQueue(item) on lists

A

procedure dequeue(item)
if q.isEmpty() then
print(“queue empty”)
else
q.pop(0)
endif
endprocedure

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

pseudocode for isFull() on lists

A

function isFull()
return(len(q) == maxSize))
endfunction

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

pseudocode for isEmpty() on lists

A

isEmpty()
return(len(q) == 0)
endfunction

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

how to add nodes to a linked list

A

data is put into the node pointed to by the nextfree pointer

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

how to delete nodes from a linked list

A

adjust the nextfree pointer to the position of the deleted node

39
Q

how to peek ahead in linked lists

A

examine the data and the pointer in the current node p and the next one function

40
Q

define stack

A

a stack is a last in, first out data structure. this means that items are added to the top and removed from the top

41
Q

applications of stacks

A
  • calculations
  • return addresses when subroutines are called
  • back/undo button
42
Q

what type of data structure is a stack

A

static or dynamic

43
Q

5 main operations on stacks

A
  1. push(item)
  2. pop()
  3. peek()
  4. isEmpty()
  5. isFull()
44
Q

what does push(item) do on stacks

A

adds a new item to the top of the stack

45
Q

what does pop() do on stack

A

removed and returns the top item from the stack

46
Q

what does peek() do on stacks

A

returns the top item from the shack but does not remove jt

47
Q

what does isEmpty() do on stacks

A

tests to see whether the stack is empty, and returns a boolean value

48
Q

what does isFull() do on stacks

A

test to see whether the stack is fill, and returns a boolean value

49
Q

pseudocode for isEmpty() stacks

A
50
Q

pseudocode for isFull() stacks

A
51
Q

pseudocode for push(item) stacks

A
52
Q

pseudocode for pop() function stack

A
53
Q

define hash tables

A
  • abstract data type
    large data sets can be organised so each record is assigned a unique address. this unique address is calculated using a hashing algorithm or hash function. the algorithm uses some part of the record (e.g. the primary key)) to map the record to a unique destination address. the resulting data structure used to store the data is called a hash table.
54
Q

what is a collision

A

happens when an algorithm generates the same address for different primary keys

55
Q

how to search for an item with hash tables

A
  • apply the hashing algorithm to the key field of the item
  • examine the resulting cell in the list
  • if the item is there, return the item
  • if there is another item in that spot, keep moving until either the item is found or blank cell is encountered, when it is apparent that the item is not in the table
56
Q

what is the address in a hashing table

A

key MOD (num slots)

57
Q

what is rehashing

A

finding an empty slot when a collision has occurred
• an alternative algorithm is to increment the ‘skip’ value by adding 1,3,5,7 etc. instead of repeatedly incrementing by 1 to find a free space – to do this, the size of the skip value must be such that all slots in the table will eventually be reached

58
Q

uses of hash tables

A
  • efficient lookup
  • dictionary
  • graphs
59
Q

what is the mid-square method for hash tables

A
  1. square the item (assume it is numeric)
  2. extract some portion of the resulting digits
  3. perform the mod (remainder) step to get an address
60
Q

what is the folding method for hash tables

A
  1. divide the item into equal-size pieces (the last piece may not be of equal size)
  2. add the pieces together
  3. perform the mod (remainder) step to get an address
61
Q

define graph

A

a set of vertices or nodes connected by edges or arcs.

62
Q

edges in an undirected graph

A

bidirectional

63
Q

edges in a directed graph

A

one-way

64
Q

what does it mean if an edge is weighted

A

there is a cost to from one node to another

65
Q

what is an adjacency matrix

A

2-D array can be used to site information about a graph. each of the rows and columns represent a node

66
Q

adjacency matrix of an undirected graph

A

symmetric

67
Q

advantage of a matrix

A
  1. an adjacency matrix is convenient to work with
  2. adding an edge is simple
68
Q

disadvantage of a matrix

A
  1. a sparse graph with not many connections (edges) will leave most of the cells empty wasting a lot of empty storage
69
Q

what is an adjacency list

A

an alternative way of representing a graph. a list of nodes is created, and each node points to a list of adjacent nodes

70
Q

advantage of adjacency list

A
  1. it uses storage for the connections that exist, so it is more space efficient
  2. it is a good way of representing a large sparsely connected graph
71
Q

how can a weighted graph be represented by a dictionary

A

a weighted graph can be represented as a dictionary of dictionaries, with each key in the dictionary being a node, and the value, a dictionary of adjacent edges and edge weights

72
Q

what are the two ways of traversing a graph

A

1.depth-first
2. breadth-first

73
Q

what is a depth-first traversal

A

go as far down one route before backtracking and taking the next riute

74
Q

what is a breadth-first traversal

A

visit all the neighbours of a node, and then the neighbours of the first node visited, all the neighbours of the second node and so on, before moving further away from the start node

75
Q

applications of graphs

A
  • computer networks
  • roads between towns
  • tasks in a project
  • web pages and links
76
Q

define tree

A

a tree is a connected data structure with no cycles – there is a unique path from each node to any other node.

77
Q

differences between trees and graphs

A
  1. a graph doesn’t have a route node, whereas a tree does not.
  2. a graph has cycles, where as a tree does not.
78
Q

what is a rooted tree

A

in a rooted tree, one node is identified as the root. every node except the root has one unique parent.

79
Q

applications of rooted trees

A
  • manipulating hierarchical data
  • making information easy to search
  • manipulating sorted lists of data
80
Q

what does a node consist of in a binary rooted tree

A
  • the data (primitive or complex)
  • a left pointer to a child
  • a right pointer to a child.
81
Q

define leaf node

A

node that has no children

82
Q

define edge

A

an edge connects two nodes. every node expect the root is connected by exactly one edge from another node

83
Q

what are three types of traversal

A
  1. pre-order
  2. in-order
  3. post-order
84
Q

what is a pre-order traversal

A

visit the root, then traverse the left sub-tree, then the right sub-tree.

85
Q

what is pre-order traversal normally used for

A

a pre-order traversal is used to produce pre-fix or Polish Notation for a mathematical expression

86
Q

what is an in-order traversal

A

traverse the left sub-tree, then visit the root, then traverse the right sub-tree (sequential order)

87
Q

what is a post-order traversal

A

traverse the left sub-tree, then traverse the right sub-tree, then visit the root.

88
Q

what is a post-order traversal used for

A

a post-order traversal is used to produce postfix or Reverse Polish Notation for an expression

89
Q

pseudocode for pre-order traversal

A
90
Q

pseudocode for in-order traversal

A
91
Q

pseudocode for post-order traversal

A
92
Q

what is the main programming feature of tree traversal algorithms

A

recursion

93
Q

use of in-order traversal

A

binary search tree, to perform an efficient search for any item

Computer Science (12 decks)

Brainscape helps you reach your goals faster, through stronger study habits.
© 2024 Bold Learning Solutions. Terms and Conditions