Brainscape's Knowledge GenomeTM


Top Flashcards (Certified)
All Flashcards

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
(7.4) What is the main disadvantage of a stack?
the main disadvantage of a stack is that the first job may never get popped/done
26
(7.4) What is overflow?
attempting to push onto a stack that is full
27
(7.4) What is underflow?
attempting to pop from a stack that is empty
28
(7.4) How do functions within functions know where to return their data?
Through stacks, which can tell the function where it originally came from
29
(7.4) What is a call stack?
system level data structure It provides the mechanism for passing parameters and return addresses to subroutines
30
(7.5) What are some examples of searching methods?
Linear | Binary
31
(7.5) What is a hash table?
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
(7.5) What is Hashing?
the process of translating a given key into a code substitutes the information with a newly generated hash code
33
(7.5) What is a collision?
When an algorithm generates the same address for two different pieces of data
34
(7.5) How are collisions usually dealt with?
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
(7.5) What is alphanumeric data?
Letters and numbers
36
(7.5) How is alphanumeric data hashed?
by getting the ASCII code for each character, then applying a hashing algorithm to the resulting numbers
37
(7.5) How is deletetion done in a hash table?
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
(7.5) How are hash tables often stored?
In dictionaries
39
(7.5) What is a dictionary?
Abstract Data Type made up of keys and values python has dictionaries built into it
40
(7.5) How are dictionaries used?
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
(7.5) What operations can be performed on a dictionary?
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
(7.6) What is a graph?
Abstract Data Structure used to represent relationships between data
43
(7.6) What do directed and undirected mean?
Directed means that there is a direction the system if forced to go along the graph undirected means there isn't
44
(7.6) What do weighted and unweighted mean?
Weighted means that there is a value for the branches travelling between data Unweighted means there isn't
45
(7.6) What are edges/branches in a graph?
The lines between the nodes
46
(7.6) What is an adjacency matrix?
a table which defines a graph and it's data
47
(7.6) In a weighted, undirected graph what would the adjacency matrix look like?
symmetric (as no direction) | values in boxes represent the weights from value to value
48
(7.6) What is an adjacency list?
an alternative to the adjacency matrix each node points to a list of adjacent nodes
49
(7.6) How are weighted graphs represented in adjacency lists?
the number is displayed after the nodes in the list for each node Uses extra data
50
(7.6) What are the advantages and disadvantages of an adjacency matrix?
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
(7.6) What are the advantages and disadvantages of an adjacency list?
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
(7.6) What is a page rank algorithm?
determines what order pages should appear to the user based on relevance and popularity of the page This is a form of graph
53
(7.6) What are the applications of a graph?
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
(7.7) What is a tree?
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
(7.7) What is abstraction?
Simplifying/ filtering out the characteristics that aren't needed in order to focus on the more important ones
56
(7.7) What is a rooted tree?
one node is the root, which doesn't have a parent node, but every other node does
57
(7.7) What is a node?
a place to store data. This is shown using circles.
58
(7.7) What is an edge?
A connection between nodes. Shown as a straight line.
59
(7.7) What is a root?
the top node.
60
(7.7) What is a child node?
Every node is a child except for the root/top node.
61
(7.7) What is a parent node?
A node that has a node connected underneath it.
62
(7.7) What is a subtree?
A part of the tree that still looks like a tree.
63
(7.7) What is a leaf?
A node with no children. Usually the bottom nodes
64
(7.7) What is a binary tree?
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
(7.7) How else can trees be stored
As arrays
66
(7.7) What is the pre-order method of binary tree traversal?
Pre-order: Visit the root, then traverse the left sub-tree, then the right sub-tree
67
(7.7) What is the in-order method of binary tree traversal?
In-order: Traverse the left sub-tree, then visit the root, then traverse the right sub-tree
68
(7.7) What is the post-order method of binary tree traversal?
Post-order: Traverse the left sub-tree, then traverse the right sub-tree, then visit the root
69
(7.7) What happens when a node is deleted in a binary tree?
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.
© 2025 Bold Learning Solutions. Terms and Conditions