1.4.2 Data Structures Flashcards

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

Which of the following data structures are ordered?

  • List
  • Record
  • Tuple
  • Array
A

List
Array
Tuple

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

Which of the following data structures can store multiple data types?

  • List
  • Record
  • Tuple
  • Array
A

List
Record
Tuple

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

Which of the following data structures are immutable (read-only)?

  • List
  • Record
  • Tuple
  • Array
A

Tuple

Contents cannot be modified at run-time

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

Which of the following data structures have no predefined scope?

  • List
  • Record
  • Tuple
  • Array
A

List

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

Which of the following data structures can store multiple values under one identifier?

  • List
  • Record
  • Tuple
  • Array
A

All of them

List
Record
Tuple
Array

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

Which of the following data structures are accessed using an index?

  • List
  • Record
  • Tuple
  • Array
A

List
Tuple
Array

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

Which of the following data structures can have multiple dimensions?

  • List
  • Record
  • Tuple
  • Array
A

Array

2D | 3D

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

How many pointers are used in a queue?

A

2 - Front and Rear

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

How many pointers are used in a stack?

A

1 - Top

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

What pointer is impacted when you enqueue an item

A

Rear/Tail - Incremented by one

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

What pointer is impacted when you dequeue an item

A

Front/Head - incremented by one

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

Which data structure operates on a FIFO basis?

A

Queue

First in first out

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

Which data structure operates on a LIFO basis?

A

Stack

Last in first out

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

Where might a queue be used?

A

Printer Queue

Keyboard Buffer

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

Where might a stack be used?

A

Web Browser History

Undo button in a word processor

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

What is the process for pushing an item to a stack?

A
  • If stack is full then report error and stop.
  • Else increment pointer
  • Add data item at position ‘pointer’
17
Q

What type of error could occur if an item is added to a full stack or queue?

A

Overflow Error

18
Q

What type of error could occur if an item is removed from to an empty stack or queue?

A

Underflow Error

19
Q

What is the process for enqueuing an item to a queue?

A
  • If queue is full then report error and stop.
  • If not full then increment tail by 1
  • Add item to tail index
20
Q

What is the process for dequeuing an item from a queue?

A
  • Check if the queue is empty, If it is then output message reporting an error.
  • If it is not empty, then output the element located at the head
  • Increment head by 1
21
Q

What is the process for popping an item from a stack?

A
  • If stack is empty then report error & stop.
  • Else output the data at the top
  • decrement the top pointer.
22
Q

Which data structure allows direct access to a record, and takes the same time to search no matter how big it gets?

A

Hash Table

23
Q

What is linear probing?

A

Used if a collision/synonym occurs (same hash value created as something that already exists)

Linear probing could be used to move through the hash table one space at a time to find the next free space.

24
Q

What keywords can be used to describe a binary search tree?

A
  • Ordered Data Structure
  • Child Node
  • Parent Node
  • Root
  • Branch
  • Leaf Node
  • Sub-Tree
25
Q

How is data found when searching a BST?

A
  • Start at the root node
  • If a search item is less than a root node, then go left.
  • If a search item is greater than a root node, then go right
  • REPEAT until found of leaf node reached
26
Q

Why can a BST be searched quicker than an array?

A

Each node does not need to be searched

List is split every time a direction is chosen (left if less, right if more)

27
Q

What is a linked list? What is it made up of?

A

A dynamic data structure

Made up of nodes

Each node consists of data and pointer

Pointer gives location of next node.

28
Q

As it grows in size, why does it take longer to search a linked list?

A

Requires every node to be checked (following pointers) until the desired record is found or the end is reached.

29
Q

What types of edges can be used in a graph?

A
  • Directed
  • Undirected
  • Weighted
  • Unweighted

Edges in a directed graph only go in one direction. Undirected edges can go in both directions.

30
Q

How do you differentiate between a tree and a graph?

A

Graph can have cycles/loops and a tree cannot

31
Q

What keywords describe a multi-branch tree?

A

A dynamic data structure

Consists of nodes that have sub nodes (children)

First node is called the root

Lines that join nodes are called branches (one directional)

Can have more than two child nodes

32
Q

How does a binary tree differ from a multi-branch tree?

A

Binary Tree cannot have more than two child nodes per parent.

Binary Tree is ordered

33
Q

What keywords can be used to describe a multi-branch tree?

A
  • Dynamic Data Structure
  • Child Node
  • Parent Node
  • Root
  • Branch
  • Leaf Node
  • Sub-Tree