fundamentals of data structures

Question 1

data structure

Answer 1

the arrangment of data

Question 2

one dimensional array

Answer 2

stores data in one direction

useful way of representing a vector

Question 3

two dimensional array

Answer 3

stores data horizontally and vertically

useful way of representing a matrix

example:

triplets = [[a,b,c], [d,e,f], [g,h,i]]

triples[2,1] = h

Question 4

binary files

Answer 4

formatted so only one a program can read them

Question 5

text files

Answer 5

contain characters structured as lines of text

Question 6

why files must be closed

Answer 6

closing free up resources, preventing corruption and ‘flushes’ the buffer

Question 7

record

Answer 7

usually for a single entity

heterogenous

Question 8

subprogram

Answer 8

an ‘out of line’ block that performs a specific task

(can be ither user written or pre existing)

Question 9

how can subprogram be used

Answer 9

by calling their name in a statement causing them to be executed

Question 10

how can data be passed in to a sub routine

Answer 10

through parameters (variables used for the input to the subroutine)

Question 11

two types of subprograms

Answer 11

procedure (doesn’t return a value)
functions (returns a value

Question 12

structured programming

Answer 12

improves the quality and clarity of code

Question 13

pros for structured programming

Answer 13

code is more readable and easier to understand

easier to test

modules can be reused

Question 14

steps in adding a record to a hash table

Answer 14

1. apply hash function to calculate the hash value for the key .
2. use the hash value to find the index in the hash table so that the new record could be stored.
3. check if there is a record at the index. if yes, use a collision resolution technique.
4. insert the new record at the index in the hash table and update the number of records in the hash table.

Question 15

two components of a stack frame

Answer 15

local variables and parameters

Question 16

operation of a stack frame and test whether if empty or full

Answer 16

1. initialize an empty stack
2. push values onto a stack from left hand side.
3. for each number in the expression; push it onto a stack. for each operator; pop the top two numbers off the stack.
4. after both have been processed, the stack should contain only one value, which is the result of the expression.
5. check if empty by comparing the stack pointer to the initial address of the stack
6. check if full by comparing the stack pointer to the max address of the stack

Question 17

Describe the method that would need to be followed to attempt to remove an item from a queue

Answer 17

1. check if the queue is empty by comparing the front and rear pointer. if equal, the queue is empty and no item can be removed.
2. if not empty, remove the front item from the front of the queue.
3. update the front pointer to the next item in the queue. if the front pointer exceeds the size of the array, reset it to 0.
4. reduce the count of items in the queue by 1

Question 18

Describe the method that would need to be followed to attempt to add an item to a queue

Answer 18

1. Check if the number of elements in the queue is equal to the maximum capacity. If it is, the queue is full.
2. If it is not full, increment the count of elements in the queue.
   Insert the item at the next available position in the queue.
3. Check if the number of elements in the queue is equal to the maximum capacity. If it is, the queue is full. If it is not full, return false or display an appropriate message.

Question 19

three differences between dynamic and static data structures

Answer 19

static data structures memory are allocated at compile time/dynamic data structure memory are allocated at run time.

static data structure size is fixed and cannot change during runtime/ dynamic data structure size can be changed during runtime

static data structure memory is managed by compiler/ dynamic data structure memory is managed by the programmer

Question 20

explain how a single stack can be used to reverse the order of the items in a queue

Answer 20

1. deque all the items from the queue and push them onto the stack
2. pop them off one by one and enqueue them back into the original queue
3. the order of the items in the queue will be reversed

Question 21

when does collision occur

Answer 21

when two key values compute the same hash.

Question 22

dictionary

Answer 22

A collection of key-value pairs in which the value is accessed via the associated key.

Question 23

application of dictionaries

Answer 23

information retrieval

Question 24

what does vector addition and multiplication achieve

Answer 24

addition achieves translation and multiplication achieves scaling.

Question 25

applications of dot product

Answer 25

Finding the angle between two vectors.

Question 26

graph

Answer 26

data structure used to represent more complex relationships.

Question 27

use of adjacency list instead of an adjacency matrix

Answer 27

when there are few edges between vertices
when edges are rarely changed

Question 28

weighted graph

Answer 28

a graph where each edge has a weight

Question 29

how do you know if a graph isnt a tree

Answer 29

if it contains a cycle

Question 30

tuple

Answer 30

an ordered list of elements

Question 31

tree

Answer 31

a connected, undirected graph with no cycles

does not have a root

Question 32

binary tree

Answer 32

rooted tree in which each node has at most two children.

Question 33

concept and use of a queue

Answer 33

linear data structure that follows the First-In-First-Out (FIFO) principle

used for tasks such as managing processes or handling requests in a sequential and ordered manner.

Question 34

concept and use of stack

Answer 34

follows the Last-In-First-Out (LIFO) principle

used for function calls, recursion, and managing program execution.

Question 35

peek or top

Answer 35

return the value of the top element without removing it

Question 36

use of rooted tree

Answer 36

to represent family trees or file
systems on a computer’s hard drive

Question 37

how are collision handled using rehashing

Answer 37

finding an available
position by moving to the next position until an available one is found.