CS paper 1..

Question 1

Subroutines and stack frames

Answer 1

-Each time a subroutine Is called the program jumps to a different part
-Once subroutine completes program needs to return to where it left off
-Before program jumps off subroutines needs to know where to return to and restore values of any local variables and parameters when returning
-This is achieved with a stack frame

Question 2

before calling subroutine (what system needs to do)

Answer 2

-construct stack frame
-add return address to stack frame
-add local variables to stack frame
-push completed stack from onto stack

Question 3

data structures

Answer 3

stacks,queues,graphs,trees,
hash tables,dictionaries ,vectors

Question 4

arrays

Answer 4

-variable that can contain more than one data item
-allocating a contiguous part of memory for the purpose of storing that data
-contiguous = data is stored together, 1 elements after the other
-starts at index 0
-static data structure

Question 5

list vs array vs tuple

Answer 5

list: mutable,items can be changed or replaced, store
> 1 data type
array: mutable, items can be changed or replaced, only store 1 data type
tuple: immutable, items cannot be changed or replaced, store > 1 data type

Question 6

File handling

Answer 6

Refers to the opening, closing, reading from and writing to files by program code

Question 7

Binary file

Answer 7

-Contains records with many different data types

A 15 figure number will occupy 15 bytes in standard text, but it would take up less space stored as a pure binary number

Reading binary file is language specific but requires you to know the exact structure of the file e.g. field sizes

Question 8

Static data structure

Answer 8

-Is fixed in size and cannot free up memory while program is running
-An array is suitable for storing a fixed number of items e.g. months of the year
-The disadvantage is that the size of the array has to be decided in advance And if items fill up, the array no more can be added
- Also memory, which has been allocated to the array cannot be reallocated
-But no pointers or ther data about structure needs to be stored

Question 9

dynamic data structure

Answer 9

• Collection of data, in memory that can grow or shrink in size
  -Does this with aid of the heap
• Useful for implementing data structures, e.g. queues when the maximum size of data structure is not know
  -Unused memory reallocated As required while program running

Question 10

stack operation

Answer 10

-push(item) = add item
-pop() = remove item
-peek() =return top value without removing
-isEmpty()
-isFull()

Question 11

queue

Answer 11

• First in first out, data structure
  -New element added to end of queue
  -back pointer, point to last item
  -front pointer, poin tto first item

Question 12

Queue operations

Answer 12

• enQueue(item) = add new item to rear of queue
• deQueue() = remove front item from queue and return it
• isEmpty() = test whether queue is empty
• isFull() = test whether queue is full

Question 13

circular queues

Answer 13

• When Array Fills up and rear pointer points to last element (e.g. q[5]) It will be made to the first element, (q0), when next person joins queue
  -Requires extra effort for programmer and less flexible than dynamic data structure

Question 14

application of queues

Answer 14

-processer schelduling
-Transferring data between processor and printer spooling
-Performing breadth-first searches on graph data structures

Question 15

adding item to stack

Answer 15

-check if stack is already full
-increment stack pointer so it points to next available space in array
-push (insert) new items

Question 16

add items to queue

Answer 16

-Check if Q is already full
-Increment back pointer so it points to next available space in arrray
-Insert (enqueue) new item at position pointed by back pointer

Question 17

graph

Answer 17

data structure consisting of nodes and edges
can have more then 2 edges and point to any vertex
graphs can be weighted with edges givena value
edges can:
point in 1 direction (directed)
not specify a direction (undirected)

Question 18

adjacency matrix

Answer 18

-a table that shows the relationship between vertices in a graph
-checking for presence/absence of edge requires accessing corresponding element in matrix
-sparse graph with many nodes but few edges, most cells empty, and bigger graphs means greater potential for wasted memory
-If using static 2D array, it can be harder to delete/add nodes

Question 19

Adjacency list

Answer 19

• a data structure that stores the relationship between vertices in a graph
  -checking for presence/absence of edge requires traversing list of corresponding vertex (O(k) time)
  -space efficient wat to implement sparsely connected graph
  -much less memory used

Question 20

graph applications

Answer 20

-mapping road networks for navigation systems
-storing social network data
-resource allocation in operating systems