Brainscape's Knowledge GenomeTM

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


See full index

Computer Science: Frankie > SLR14 > Flashcards

SLR14 Flashcards

You may prefer our related Brainscape-certified flashcards:
Biology 101 flashcards
1
Q

What’s are the characteristics of Lists as a data type

A
  • mutable
  • ordered collection of items
  • items can be changed or replaced
  • can store more than one data type
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

What’s are the characteristics of an array as a data type

A
  • mutable
  • ordered collection of items
  • items can be changed or replaced
  • can only store one data type
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

What’s are the characteristics of a Tulpe as a data type

A
  • immutable
  • unordered collection of items
  • items cannot be changed or replaced
  • can store more than one data type
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

What’s are the characteristics of a record as a data type

A
  • mutable
  • ordered collection of items
  • items can be changed or replaced
  • can store more than one data type
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

What does LIFO stand for

A

Last In First Out

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

What structure do stacks function in

A

LIFO

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

How many pointers does a stack have a where are they?

A

One and the top node

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

What happens when you try to remove an item from an empty stack

A

Underflow error

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

What happens when trying to add an item to a full stack

A

An overflow error

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

What are stacks used for

A
  • user inputs
  • back tracking algorithms
  • evaluating mathematical equations without brackets
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

What are the three operations of a stack

A
  • push
  • pop
  • peek
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

What does the push operation do in a stack

A

Adds a new item to the top of a stack

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

What does the pop operation do in a stack

A

Removes the top item off of the stack

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

What does the peek operation do in a stack

A

Returns the value of the top item in a stack without removing or deleting it

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

What is the process of enqueuing in an array

A

Adding an item to the back of a queue

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

What is the process of dequeuing in an array

A

Removing the item from the front of the queue

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

What will happen if you try and remove an item from an empty queue in an array

A

An underflow error

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

What will happen if you try an add an item to a full queue in an array

A

An overflow error

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

In what way does a queue in an array operate

A

FIFO

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

What does FIFO stand for

A

First In First Out

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

What does FIFO stand for

A

First In First Out

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

What are the three operations in a queue in an array

A
  • enqueue
  • dequeue
  • peek
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
23
Q

What is the process of enqueuing in an array

A

Adding an item to the back of a queue

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

What is the process of dequeuing in an array

A

Removing an item from the from of a queue

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

What is the process of peeking in a queue in an array

A

Returning the value of the item at the front of the queue without removing or deleting it

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

What type of data structure is a queue

A

A linear data structure

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

As Queues are a FIFO structure what does this allow us to do that you can’t do with a stack

A

Add priority

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

What does priority do

A

Allows items to skip the queue or part of the queue based on there importance

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

How many pointers does a queue have and where are they

A

Two and at the back and the front

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

Where can queues be implemented

A
  • in an array
  • Object-Orientated Programming
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
31
Q

What are the front and back pointers also known as

A

Head and tail pointers

32
Q

When are the head and tail pointers moving

A

I’m circular queues

33
Q

What can queues be used for

A
  • process scheduling
  • transferring data between processors and printers
  • performing breadth-first searches on graph data structures
34
Q

How are linked lists made

A

Attaching two nodes together with a pointer

35
Q

How can linked lists become circular

A

By having the last node have a pointer back to the first node

36
Q

What effect do linked lists have on run times and why

A

Dramatically changing run times because they are a dynamic data structure meaning data is not stored in order

37
Q

Where are linked lists used

A
  • Operating systems
  • Image viewers
  • Music players
  • Web browsers
  • Hash table collision resolution
  • Maintaining a file allocation
38
Q

What are the 5 operations of a linked list and what do they do

A
  • ADD: add a node to the linked list
  • DELETE: remove a node from the linked list
  • NEXT: moves to the next item in the linked list
  • PREVIOUS: moves to the previous item in a doubly liked list
  • TRAVERSE: a linear search through the linked list
39
Q

How are linked lists made in graphs

A

Nodes / vertices
Pointers / edges

40
Q

In graphs do edges have direction or not

A

Either

41
Q

How can graphs be weighted

A

Each edges has its own value which can be represented as many things such as distance, time and bandwidth

42
Q

What are weighted graphs used for

A

Mapping roads
Storing social network data
Resource allocation in OS
Representing molecular structures and geometry

43
Q

How are graphs stored in an array

A

[( [0, 1, 1, 1, 0],
[0, 0, 1, 0, 1,],
[0, 1, 0, 0, 1],
[1, 0, 0, 1, 0],
[0, 0, 1, 0, 0] ])

44
Q

What does a tree consist of

A

Nodes and pointers

45
Q

Where is the trees root node

A

At the top of the tree

46
Q

What is at the bottom of a tree

A

The left nodes

47
Q

What are the typical uses of rooted trees

A

Storing and managing file and folder structures
Implementations of the A* pathfinding algorithm
Any form of hierarchical data like family trees, corporate structure

48
Q

What are the typical uses of binary trees

A

Database applications
Wireless networking and router cables
OS scheduling process
Huffman coding
Cryptography (GMM)

49
Q

What are the 7 operations of trees

A

Add
Delete
Binary search
Pre-order traversal
In-order traversal
Post-order traversal
Breadth-first search

50
Q

What is the priority system in a depth-first traversal graph

A

LIFO

51
Q

What are the two main stages in a depth-first search

A
  1. Visited nodes are pushed onto the stack
  2. When there are no nodes left to visit the nodes get popped off the stack
52
Q

What are the steps of an iterative approach to a depth-first traversal graph (6)

A
  1. Set the root node as the current node
  2. Add the current node to the list of visited nodes if it isn’t already in the list
  3. Follow every edge connected to the node
    If the connected node is not in the visited list push the linked node on to the stack
  4. Pop the stack and set the removed item as the current node
  5. Repeat from step two until there are no nodes left to visit
  6. Output all visited nodes
53
Q

What are the steps of a recursive approach to a depth-first traversal graph (4)

A
  1. Set the root vertex as the current vertex
  2. Output the vertex
  3. Add the vertex to the list of all visited vertices
  4. If the vertex has an edge that has not been visited
    - follow the edge and make that vertex become the current vertex
    - repeat from step 2
54
Q

What is the breadth-first traversal method used for

A

Finding the shortest path through a graph

55
Q

What type of data structure is breadth-first traversal graph

A

FIFO

56
Q

What is the method for a breadth-first traversal graph (6)

A
  1. Set the root node as the current vertex
  2. Add the current vertex to the list of visited if not already on the list
  3. For every edge connected to the vertex
    - if the connected node is not in the visited list, enqueue the linked node
  4. Dequeue and set the vertex that’s been removed at the current vertex
  5. Repeat from step 2 until the queue is empty
  6. Output all visited vertices
57
Q

How many children can each binary trees node have

A

Either 0, 1, 2

58
Q

Where can binary trees be used

A

Dictionary’s
Arrays
Objects

59
Q

Where are binary search tree used

A

In database applications where efficient searching is needed

60
Q

How many directions does a 1D array, 2D array, 3D Array, 4D Array, 5D Array grow in

A

One
Two
Three
One with a full 3D array in each
Two with a full 4D Array in each

61
Q

How do you input data in an empty binary tree

A
  1. First check if there is free memory if not output and error
  2. Create a new node and insert the data into it
  3. If the binary tree is empty: the new node becomes the root node along with a starter pointer pointing to it
62
Q

How do you input data into a binary tree that’s not empty (3(4))

A
  1. First check if there is a free memory if not output an error
  2. Create a new node and insert the data into it
  3. If the tree isn’t empty:
  4. Start at the root node
  5. If the new node should be placed before / after the current node follow the left / right pointer
  6. Repeat step 2 until until a leaf node is reached
  7. Decide weather the new node should come before or after the left node and go left or right accordingly
63
Q

How do you delete data from a binary tree if the node that is being deleted has no children

A
  1. Start with the root node a set it as the current node
  2. While the current node exists and is not the root the to be deleted:
    1. Set the previous node to be the same as the current node
    2. If the item to be deleted is less than/ greater then the current node follow the left / right pointer and set the discovered node as the current node
  3. If the node to be deleted has no children: the previous nodes pointer is set to null
64
Q

How do you delete data from a binary tree if the node being deleted has one child

A
  1. Start with the root node a set it as the current node
  2. While the current node exists and is not the root the to be deleted:
    1. Set the previous node to be the same as the current node
    2. If the item to be deleted is less than/ greater then the current node follow the left / right pointer and set the discovered node as the current node
  3. If the node to be deleted has one child: if the current node is less / greater than the previous nodes left / right pointer to the nodes left / right child
65
Q

How do you delete data from a binary tree if the node to be deleted has 2 children

A
  1. Start with the root node a set it as the current node
  2. While the current node exists and is not the root the to be deleted:
    1. Set the previous node to be the same as the current node
    2. If the item to be deleted is less than/ greater then the current node follow the left / right pointer and set the discovered node as the current node
  3. If the node to be deleted has two children:
    1. If the right node exists and it has a left sub tree find the smallest leaf node in the right sub tree
    1. Changes the current node to be the smallest left node
    2. Remove the smallest left node
    2. If the right node exists and it has no left subtree
    1. Set the current node to be the current nodes right pointer
    2. Set the current nodes right pointer to be null
66
Q

What is the main goal of a hash table

A

To be impossible to reverse engineer

67
Q

What are hash tables used for

A

To find something from a sorted or unsorted listed

68
Q

What are hash tables used for in programming

A

To implement a dictionary data structure

69
Q

Why are hash tables often much larger than what they need to be

A

To make sure no value is returned more than once

70
Q

What is it known as when two things output the same value in a hash table or occupy the same space in a hash table

A

A collision

71
Q

What are hashing functions used for

A

Calculating the position of an item in a hash table

72
Q

What should a good hashing function include (3)

A
  1. Be calculated a quick as possible
  2. Result in as few collisions as possible
  3. Use as little memory as possible
73
Q

What happens when there are to many items in a hash table for it to handle

A

Clustering (2D hash table with an overflow table)

74
Q

How does an overflow hashing table function

A

As a linked list where items in a hash table can be stored while there isn’t a place to store them

75
Q

How do you add an item to a hash table

A
  1. Calculate the position of the item in the hash table
  2. If the calculated position is empty then insert the item and stop
  3. If the calculated position is not empty then check the first position in the overflow table
    1. If empty then stop
    2. If not check the next position in the overflow table
    3. Repeat until the item is inserted or the table is full

Computer Science: Frankie (25 decks)

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