Brainscape's Knowledge GenomeTM

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


See full index

Computing > Data Structures (unit 7) (Finished) > Flashcards

Data Structures (unit 7) (Finished) Flashcards

1
Q

(7.1)What is an array?

A

An array is a set number of elements of the same type. (A list can have different data types in it)

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

(7.1)What is a 2d array?

A

a grid (or table) with rows and columns version of an array

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

(7.2) What is a queue?

A

A queue is a first in first out data structure, where elements can only be added to the end of the queue

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

(7.2)What are the 4 operations that can be performed on a queue?

A

Add item to the rear of the queue​ (enQueue(item))

Remove item from the front of the queue​ (deQueue())

Check if the queue is empty​ (isEmpty())

Check if the queue is full (isFull())

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

(7.2) What are pointers and how do they work?

A

Pointers are used to identify which is the next value in a queue that should be visited

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

(7.2) What is the difference between a circular queue and a normal queue

A

in a circular queue, the front and rear depend on which one was put in last or first entirely, not the place value it holds. an example of this is that the value in [0] could be the rear, while the value in [4] could be the front

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

(7.2)write functions to check if a queue is empty, or a queue is full

A 
function isEmpty ​
if size == 0:​
  return True​
else​
  return False​
function isFull​
if size == maxSize:​
   return True​
else:​
   return False
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

(7.2)Write a function to enqueue an item

A 
function enqueue(newItem):​
   if size == maxSize:​
      print ("Queue full")​
   else:​
      rear = (rear + 1):​
      queue[rear] = newItem​
      size = size + 1
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

(7.2)Write a function to enqueue an item

A 
function enqueue(newItem):​
   if size == maxSize:​
      print ("Queue full")​
   else:​
      rear = (rear + 1):​
      queue[rear] = newItem​
      size = size + 1
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

(7.2)Write a function to dequeue an item

A 
function dequeue():​
   if size == 0:​
      print ("Queue empty")​
   else:​
      front = (front + 1):​
      size = size - 1
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

(7.2)What is a priority queue?

A

a priority queue allows some elements of the list to skip forward depending on the attributes they hold

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

(7.2) What are the differences between a dynamic and static data structure?

A

Static data structures are fixed in size​:
cannot grow, shrink, or be freed up during execution​,
an array is a static data structure​

Dynamic data structures can grow and shrink​:
allocates and deallocates memory from the heap (an area of memory especially used for this purpose)​
excessive allocation of memory, without deallocation, may cause overflow (exceeding maximum memory limit)​

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

(7.3) what is abstraction?

A

abstraction is the process of filtering out the unneeded parts to concentrate on what is needed

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

(7.3)What are some examples of Abstract Data Types? (adt)

A

Queues

Lists

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

(7.3)What is an abstract data type?

A

A data type that isnt built into the programming language but is still used

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

(7.3) What are some examples of languages with dynamic list support?

A

Python
Java
vb.net
delphi

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

(7.3) what is a linked list?

A

a linked list is a dynamic data structure which is implemented as a normal list/array (with pointers)

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

(7.3) What are some applications of lists?

A

List of students in a class and their marks, ​
Component parts of a product, ​
Songs in a music library, ​
Friends on a social media platform, etc.

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

(7.3) How are nodes deleted in linked lists?

A

Node is deleted, pointers are adjusted to skip the value that the deleted node once occupied

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

(7.4) What is a stack?

A

LIFO (last in first out) data structure

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

(7.4) What are some examples of stacks being used?

A

Towers of Hanoi game
websites visited (so that you can go back to the previous page)
Contents of the CPU

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

(7.4) What functions can be used in a stack?

A

Push
Pop
Check size of the stack
peek (check the size of the stack if empty/full)

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

(7.4) What operations can be performed on a stack?

A

Push(item)
pop()
isfull()
isempty()

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

(7.4) How can a list be reversed using a stack?

A

put the list into a stack, then take it out, will come out reversed as stacks are FILO

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

(7.4) What is the main disadvantage of a stack?

A

the main disadvantage of a stack is that the first job may never get popped/done

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

(7.4) What is overflow?

A

attempting to push onto a stack that is full

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

(7.4) What is underflow?

A

attempting to pop from a stack that is empty

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

(7.4) How do functions within functions know where to return their data?

A

Through stacks, which can tell the function where it originally came from

29
Q

(7.4) What is a call stack?

A

system level data structure

It provides the mechanism for passing parameters and return addresses to subroutines

30
Q

(7.5) What are some examples of searching methods?

A

Linear

Binary

31
Q

(7.5) What is a hash table?

A

Hash Table is a data structure which stores data in an associative manner.

In a hash table, data is stored in an array format, where each data value has its own unique index value.

Access of data becomes very fast if we know the index of the desired data.

32
Q

(7.5) What is Hashing?

A

the process of translating a given key into a code

substitutes the information with a newly generated hash code

33
Q

(7.5) What is a collision?

A

When an algorithm generates the same address for two different pieces of data

34
Q

(7.5) How are collisions usually dealt with?

A

Collisions are usually solved by placing the overlapping data into the next free slot

Could also be solved by adding increasing numbers to the slot it is going in, so it is more likely to find a free slot

35
Q

(7.5) What is alphanumeric data?

A

Letters and numbers

36
Q

(7.5) How is alphanumeric data hashed?

A

by getting the ASCII code for each character, then applying a hashing algorithm to the resulting numbers

37
Q

(7.5) How is deletetion done in a hash table?

A

the value is replaced with a dummy word (such as “deleted”)

if a new item is added, and the address is filled with a dummy word, it will be replaced by the new word

38
Q

(7.5) How are hash tables often stored?

A

In dictionaries

39
Q

(7.5) What is a dictionary?

A

Abstract Data Type made up of keys and values

python has dictionaries built into it

40
Q

(7.5) How are dictionaries used?

A

Used in applications where things need to be looked up such as:

In a computer system, the ASCII or Unicode table

In a translation program, a foreign language dictionary containing words and meanings

Other data structures such as trees and graphs may be implemented using a dictionary

41
Q

(7.5) What operations can be performed on a dictionary?

A

Add a new key:value pair to the dictionary

Detete a key:value pair from the dictionary

Amend the value in a key:value pair

Return the value associated with key k

Return True or False depending on whether the key is in the dictionary

Return the length of the dictionary

42
Q

(7.6) What is a graph?

A

Abstract Data Structure used to represent relationships between data

43
Q

(7.6) What do directed and undirected mean?

A

Directed means that there is a direction the system if forced to go along the graph

undirected means there isn’t

44
Q

(7.6) What do weighted and unweighted mean?

A

Weighted means that there is a value for the branches travelling between data

Unweighted means there isn’t

45
Q

(7.6) What are edges/branches in a graph?

A

The lines between the nodes

46
Q

(7.6) What is an adjacency matrix?

A

a table which defines a graph and it’s data

47
Q

(7.6) In a weighted, undirected graph what would the adjacency matrix look like?

A

symmetric (as no direction)

values in boxes represent the weights from value to value

48
Q

(7.6) What is an adjacency list?

A

an alternative to the adjacency matrix

each node points to a list of adjacent nodes

49
Q

(7.6) How are weighted graphs represented in adjacency lists?

A

the number is displayed after the nodes in the list for each node

Uses extra data

50
Q

(7.6) What are the advantages and disadvantages of an adjacency matrix?

A

Advantage: an adjacency matrix is convenient to work with, easy enough to understand and adding an additional edge is simple

Disadvantage: a sparse graph with not many connections (edges) will leave most of the cells empty, wasting a lot of memory space.

51
Q

(7.6) What are the advantages and disadvantages of an adjacency list?

A

It only uses storage for the connections that exist, so it is more space-efficient

It is a good way of representing a large, sparsely connected graph

No real disadvantages

52
Q

(7.6) What is a page rank algorithm?

A

determines what order pages should appear to the user based on relevance and popularity of the page

This is a form of graph

53
Q

(7.6) What are the applications of a graph?

A

Applications include
Computer networks, with nodes representing computers and weighted edges representing bandwidth between them
Social networks friends suggestions
Chemistry, with nodes as atoms, edges as connections
Project management, with nodes as tasks, edges representing sequence and weights, time or cost
Web pages and links.

54
Q

(7.7) What is a tree?

A

Abstract Data Type, has a root branches and leaves that allow it to display data

A tree is a connected, undirected and unweighted graph with no cycles

55
Q

(7.7) What is abstraction?

A

Simplifying/ filtering out the characteristics that aren’t needed in order to focus on the more important ones

56
Q

(7.7) What is a rooted tree?

A

one node is the root, which doesn’t have a parent node, but every other node does

57
Q

(7.7) What is a node?

A

a place to store data. This is shown using circles.

58
Q

(7.7) What is an edge?

A

A connection between nodes. Shown as a straight line.

59
Q

(7.7) What is a root?

A

the top node.

60
Q

(7.7) What is a child node?

A

Every node is a child except for the root/top node.

61
Q

(7.7) What is a parent node?

A

A node that has a node connected underneath it.

62
Q

(7.7) What is a subtree?

A

A part of the tree that still looks like a tree.

63
Q

(7.7) What is a leaf?

A

A node with no children. Usually the bottom nodes

64
Q

(7.7) What is a binary tree?

A

A binary tree is a tree in which each node has a maximum of two children

Consists of:
The data
a left pointer
a right pointer

65
Q

(7.7) How else can trees be stored

A

As arrays

66
Q

(7.7) What is the pre-order method of binary tree traversal?

A

Pre-order: Visit the root, then traverse the left sub-tree, then the right sub-tree

67
Q

(7.7) What is the in-order method of binary tree traversal?

A

In-order: Traverse the left sub-tree, then visit the root, then traverse the right sub-tree

68
Q

(7.7) What is the post-order method of binary tree traversal?

A

Post-order: Traverse the left sub-tree, then traverse the right sub-tree, then visit the root

69
Q

(7.7) What happens when a node is deleted in a binary tree?

A

if it is a leaf- is deleted
if it has a child- move the child into the deleted node’s position
if it has two children- move the next largest child into the position of the deleted node

Computing (14 decks)

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