Brainscape's Knowledge GenomeTM


Top Flashcards (Certified)
All Flashcards

SCC 121 > Data Structures > Flashcards

Data Structures Flashcards

(75 cards)

Start Studying
1
Q

Define an interface

A

A set of procedures that operate on the data structure

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

Why is an abstract data type ‘abstract’?

A

Because we are not concerned with the implementation of the data structure but rather what operations we can perform using the data structure

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

Define strong encapsulation in terms of ADTs

A

Encapsulation is strong if details of how the data structure is stored is completely hidden from the user because it means the user has no conceptual idea of how the ADT is stored and implemented

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

Define a queue

A

An ordered collection of items which are added at the tail and removed from the head

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

Why are queues beneficial?

A

They provide FIFO functionality meaning that items can be easily reversed and traced back

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

How do you use a structure in C to define a queue?

A

You create a structure which has two properties, one being the data contained in that position in the queue and the second being a pointer to the next item in the queue

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

How do you add an item to a queue in C?

A
  1. Check whether the queue is full
  2. Check whether the head pointer is NULL
  3. If the head pointer is NULL then set the head pointer equal to the element you want to add
  4. If the head pointer is not NULL then determine the position of the tail of the queue and reassign that pointer so it points to the element you want to add
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

Define homogeneous

A

Consists of elements with all the same data type

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

Define heterogeneous

A

Consists of elements of different data types

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

Describe byte addressable memory

A

Memory can be represented as an array of bytes with each cell having a unique address written in hexadecimal

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

What is a word?

A

The smallest unit of addressable memory in a computer

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

What is the size of a word?

A

The size of a word varies from machine to machine but we assume a word is 32 bits long

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

How many bits are required to store an integer?

A

32

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

What are the 3 aspects of a variable?

A
  1. A symbolic name given by the programmer
  2. The value is contains
  3. An address where it resides in memory
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

Define variable scope

A

The functions of a program in which a variable can be accessed

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

Why do we have to use pointers in C?

A

We can only return one variable from a function in C so, in order to change variables in other scopes in a function, we use pointers to the variables

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

What is indirection?

A

A method of referring to an item without referring to the item itself .e.g. referring to the memory address in which a variable is stored rather than referring to the variable itself

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

What does ‘*’ mean?

A

This is the dereferencing operator because it returns the value stored at the address contained within the operand

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

What does ‘&’ mean?

A

This is the address-of operator and it returns the address of its operand

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

What does it mean if an operator is unary?

A

It only takes one input

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

What are the three stages to evaluating an operation?

A
  1. Fetch
  2. Evaluate
  3. Store
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
21
Q

Define record

A

A heterogeneous compound item

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

What is the disadvantage of using arrays?

A

Arrays are homogeneous meaning that you cannot model any entities that consist of values of different data types using arrays

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

What is a field?

A

An item which makes up a record

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
24
Define a record
A heterogeneous compound item made up of fields
25
What are the two ways of selecting a field in a record?
1. Using a . if it is declared directly 2. Using an -> if it declared indirectly as a pointer
26
What does malloc stand for?
Memory allocation
27
What does malloc do?
Dynamically assigns memory to an object
28
What memory section does malloc access?
The heap
29
What is the heap?
A section of memory which is assigned to a program and made available for use by the programmer
30
How is malloc implemented?
Malloc assigns an address from the memory in the heap to a pointer in your program which then becomes the base address for the item you are creating in your program, you then access memory for that object using the pointer
31
What is the difference between a table and a matrix?
A table has a single variable on one axis where as a matrix has two variables on two axis'
32
How do you define a 2D array?
[][]
33
What are the advantages of array?
1. We can use a single name to represent multiple data items of the same data type 2. They have very fast random access as opposed to sequential access
34
What are the disadvantages of arrays?
1. The size of an array is initialised at runtime and cannot be changed 2. Insertions and deletions from an array are costly
35
Define stack underflow
When you try and pop from an empty stack
36
Define stack overflow
When you try and push to a full stack
37
Define an unbounded stack
A stack that has an infinite size
38
Define a bounded stack
A stack that has a limited size
39
What are some common uses of stacks?
1. Call stacks 2. Checking syntax and semantics 3. Searching 4. Mathematics .e.g. determining the result of postfix equations
40
What is a call stack?
When a new function is called a stack frame is pushed to the stack which includes information including the return address, arguments, and local variables. This allows the program to return to where it was once the program has been executed and in the same state as before
41
Programming question: write a program that checks whether there are matching pairs of brackets and braces in a statement
Create a stack and each time you encounter an open parentheses push to the stack and when you encounter a close parentheses pop from the stack. If you encounter a stack underflow error or the stack is not empty at the end of the statement then there is an unbalanced number of parentheses.
42
How do you use stacks for searching?
If you're doing a depth first search you need to retrace your steps and you do this by popping things from the stack
43
Define a list
An ADT that stores a set of items in a linear order
44
What is a singly linked list?
A list that consists of element which each have a pointer to the next element
45
What is a doubly linked list?
A list that consists of elements which each have a point to the next element and the previous element
46
How are storage and retrieval linked?
If the storage process is fast then the retrieval is slow and vice versa (indirectly proportional)
47
Define theoretical time complexity
The relationship between the size of the input and algorithm running time
48
Time complexity of binary search
O(log n)
49
Time complexity of linear search
O(n)
50
Define recursive function
A function that calls itself
51
What is the logic behind a recursive function?
The function will call itself and apply the same logic to progressively smaller pieces of input until it reaches the base case (unless it throws an error)
52
What happens in the call stack when a recursive function reaches its base case?
The call stack will unravel and track back through all of the recursive calls of the same function and execute all of the statements after the recursive statement
53
What are the advantages of an iterative function?
1. Memory usage is controlled explicitly 2. Less chance of stack overflow 3. Can execute more quickly as there is no overhead from stack frame creation/destruction
54
What are the disadvantages of iterative functions?
1. Naturally recursive functions are harder to understand in their iterative form
55
What are the advantages of recursive functions?
1. Naturally recursive function are more concise 2. Languages that support tail recursion can eliminate some of the extra cost to performance
56
What are the disadvantages to recursion?
1. Difficult to code if it is not a naturally recursive function 2. Stack overflow 3. No explicit control over memory
57
What is tail recursion?
When the recursive call is after the contents of the function
58
What is head recursion?
When the recursive call is before the contents of the function
59
Define key
A unique name or identifier for each object
60
What does indexed retrieval use?
It uses keys to store and retrieve objects/records
61
What is a collision?
When two elements need to be stored in the same location
62
How can we solve a collision?
Indexed retrieval or chaining
63
How do we solve a collision using indexed retrieval?
We have a set of lists stored in that section where more than one element needs to be stored so then we can store multiple elements in one location
64
How do we solve a collision with chaining?
We can create a singly linked list in the location
65
What are the advantages of chaining over indexed retrieval?
It is more memory efficient and chains are dynamic where as lists are not
66
What does hashing do?
A hash function will convert a key to an integer and this integer will then be used for indexing a storage array
67
Why is using a hash function effective for storage?
We are not restricted by basic indexing methods so the data is spread out across a larger array and we are not likely to end up with collisions
68
Define uniform hashing
Evenly distributing the elements across the hash table
69
What is the general hash function?
index = rawIndex % size
70
Why do we use % size in a hash function?
So the index does not exceed the size of the hash table
71
What is the downside of hashing?
Retrieval requires two steps: to perform the hash function to find the index and then search any existing chain for a match
72
Why is it better to use shifting than multiplication?
Shifting is a more efficient operation
73
What is an easy way to distinguish between two elements with the same hash?
A key-pair value
74
How should we counteract long chains?
Allocate an array double the size of the current arrays that puts each key-value pair in the current array into a larger array to reduce chain length

SCC 121 (4 decks)

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