cs p1

Define stack.

"LIFO data structure; push adds to top

Define queue.

"FIFO data structure; enqueue adds to rear/back

State two typical uses of a stack.

Holding return addresses/function calls; expression evaluation/conversion; string reversal; interrupt handling; undo/redo; backwards browser navigation; backtracking; DFS; reversing a queue.

State two typical uses of a queue.

"Print spooling/print queue; scheduling/ready queue; buffering (keyboard

What does isEmpty() return for a stack or queue?

"Boolean True if size is 0

Why check isEmpty() before pop()?

To prevent underflow/error when trying to pop from an empty stack.

Define circular queue (array-based).

Queue implemented in fixed-size array where rear wraps to front using modulo; front and rear pointers track positions; reuses freed array cells.

Describe the structure of a linked list.

Chain of nodes; external head pointer points to first node; each node has a data field and a pointer to the next node; last node's pointer is null/nil/none.

Describe a doubly linked list.

Each node has data and two pointers: one to the next node and one to the previous node; allows traversal in both directions.

Describe a circular linked list.

Nodes with data and pointer field; last node's pointer points to the head node rather than null; no null pointers in the list.

State two applications of circular linked lists.

Implementing a queue/deque; media player playlist; image gallery; multiplayer game turn rotation; navigation/simulation of circular routes.

Outline one advantage of a linked list over an array.

Dynamic size; memory allocated at run-time; nodes inserted/removed without shifting elements; efficient use of RAM.

Outline one disadvantage of a linked list over an array.

No direct access to elements; must be traversed sequentially from the head; higher memory overhead due to pointers.

Algorithm: traverse a linked list until value X is found.

"curr = head; loop while curr != null; if curr.data == X then exit; previous = curr; curr = curr.next; end loop."

Define a binary tree.

"Hierarchical data structure; each node has at most two children (left and right); one root node; nodes with no children are leaves."

Define a binary search tree (BST).

"Ordered binary tree; for every node

List the three binary tree traversals.

"Inorder (left

Inorder traversal of a BST outputs what?

Nodes in ascending/sorted order.

Explain recursive inorder traversal.

Traverse left subtree (recursive call); visit/output root; traverse right subtree (recursive call); base case: empty subtree returns.

"Given a BST

how do you insert a new value?"

Define array.

Static data structure; fixed-size contiguous block of memory; stores elements of the same data type; accessed by index.

Describe a two-dimensional array.

Array of arrays; elements accessed by two indices [row][column]; rows and columns fixed at compile time.

Algorithm: sum all elements of a 2D array A[R][C].

"total = 0; loop i from 0 to R-1; loop j from 0 to C-1; total = total + A[i][j]; end loop; end loop; output total."

Algorithm: count occurrences of value V in array A of size N.

"count = 0; loop i from 0 to N-1; if A[i] == V then count = count + 1; end loop; output count."

Identify three functions of the control unit (CU).

"Fetch instructions from memory; decode instructions; execute instructions; coordinate activity of ALU and registers; control data flow within CPU."

State the purpose of the memory address register (MAR).

Holds the address of the memory location to be read from or written to.

State the purpose of the memory data register (MDR).

Holds data being transferred to or fetched from primary memory.

Define the ALU.

"Arithmetic logic unit; performs arithmetic operations (add

Outline the fetch-decode-execute cycle.

Fetch: CU fetches instruction from memory via MAR/MDR; Decode: CU decodes instruction; Execute: ALU/CU executes instruction; PC increments; cycle repeats.

Convert 122 (decimal) to binary.

01111010.

Convert 00011100 (binary) to hexadecimal.

1C.

Convert binary to hex method.

"Group binary digits into fours from right; convert each group to hex digit (0-9

List four functions of an operating system.

Managing memory; managing peripherals; processor/process management; scheduling; resource allocation; security; file management; providing user interface.

Outline the role of virtual memory.

"Uses secondary storage as extension of RAM; allows more processes to run simultaneously; OS moves pages between RAM and disk (paging); prevents 'out of memory' errors."

Define sensor.

"Input device/transducer that measures a physical quantity (temperature

State two types of sensor used to detect vehicles.

Pressure/weight sensor embedded in road; infrared sensor; induction loop; camera with image recognition; ultrasonic/motion sensor.

Define actuator.

"Output transducer; converts electrical signals from microprocessor into physical action (movement

Describe the role of a microprocessor in a control system.

Receives inputs from sensors (via ADC); compares readings with preset values; executes stored control program; sends signals to actuators to maintain desired state.

Loop to traverse a collection C.

"loop while C.hasNext(); X = C.getNext(); // process X; end loop."

Loop to process all elements of array A of size N.

"loop i from 0 to N-1; // process A[i]; end loop."

Define recursion.

A method/function that calls itself during its execution; must have a base case (terminating condition) and a recursive case that moves toward the base case.

Identify two essential features of a recursive algorithm.

Base/terminating case; recursive call that approaches the base case.

State two applications suited to recursion.

"Tree traversal; factorial; Fibonacci; divide-and-conquer (merge sort

"Trace fun(N) where fun returns (N mod 10) + fun(N div 10) with N=1216."

fun(1216) = 6 + fun(121) = 6+1+fun(12) = 6+1+2+fun(1) = 6+1+2+1+fun(0) = 6+1+2+1+0 = 10 (sums digits of N).

State one disadvantage of recursion.

Uses stack memory for each call (risk of stack overflow); often slower than iteration due to function call overhead.

Apply inorder traversal to a BST.

"Recursively traverse left subtree

Given nodes inserted in order and asked to sketch a BST.

"Insert each in turn: first value is root; for each subsequent value go left if smaller

Compare static and dynamic data structures.

"Static: fixed size set at compile time

Outline the purpose of a VPN.

Virtual private network; creates an encrypted tunnel over a public network; allows secure remote access to a private network; authenticates users before connection.

Outline two reasons for using a VPN.

Encryption of transmitted data so intercepted traffic is unreadable; authentication of users; allows remote workers to access internal resources as if on the internal network; hides user's real IP.

Compare extranet and VPN.

"VPN: fully encrypted

Identify four causes of data loss.

Software corruption/malware/viruses; hardware failure (disk crash); human error (accidental deletion); power failure; theft; natural disaster; migration errors.

Describe one method to prevent data loss.

Regular backups to separate media; store backup off-site; version control; RAID redundancy; UPS for power failures.

Outline what is meant by an interrupt.

Signal sent to the CPU by hardware or software; alerts the CPU to suspend the current program; transfers control to the interrupt handler which services the interrupt then resumes the suspended program.

Explain how the microprocessor handles an interrupt.

Saves state of current program on stack; identifies source of interrupt; executes corresponding interrupt service routine (ISR); restores saved state and resumes original program.

Outline polling.

CPU continuously/sequentially checks the status of devices to see if they need attention; wastes CPU cycles; no priority; implemented as a software loop.

Compare polling and interrupts.

"Interrupts are hardware-driven and priority-based

Define embedded system.

"Computer system designed to perform a specific/dedicated function; physically part of a larger system (e.g. washing machine

State two advantages of a wireless network.

Increased mobility; convenience (no cables); easier installation in existing buildings; allows many devices to connect simultaneously; lower cabling cost.

State two disadvantages of a wireless network.

Lower security (signal can be intercepted); slower speeds than wired; signal can be blocked by walls/interference; limited range.

Compare LAN and WAN.

"LAN: small geographic area (one building)

Define a collection.

"Abstract data structure storing a group of elements; dynamic size; provides methods to add

Compare lossy and lossless compression.

"Lossy: discards data

Outline the need for protocols.

Protocols are sets of rules for transmitting data correctly between devices; ensure both sender and receiver interpret data the same way; enable interoperability between different systems.

State three pieces of information in a data packet.

Source IP address; destination IP address; packet number/sequence; protocol; payload/data; checksum/CRC; header/trailer.

Outline packet switching.

Data is broken into packets; each packet is sent individually; packets may take different routes; packets may arrive out of order and are reassembled at destination; re-routing possible if a route fails.

Outline the purpose of a prototype.

Simple representation of a system; demonstrates functionality/UI to the client; allows user testing and feedback; refines requirements during development.

Outline the purpose of cache memory.

Small fast memory between CPU and RAM; stores frequently accessed instructions/data; faster access than RAM; reduces average memory access time.

Outline a feedback loop in a control system.

"Sensor measures output; value fed back to microprocessor; compared to preset/desired value; if different

Outline beta testing.

Software released to a limited group of end-users outside the development team; users report bugs and usability issues in real environments; feedback used to fix issues before full release.

State one ethical issue with CCTV/camera monitoring.

Invasion of privacy; data may be used for purposes beyond stated one; risk of unauthorized access; potential for surveillance abuse; lack of informed consent.

Pseudocode: bubble sort of array A size N.

"loop i from 0 to N-2; loop j from 0 to N-2-i; if A[j] > A[j+1] then temp=A[j]; A[j]=A[j+1]; A[j+1]=temp; end if; end loop; end loop."

Pseudocode: linear search for V in array A size N.

"found = false; i = 0; loop while i < N and not found; if A[i] == V then found = true; else i = i + 1; end loop; if found output i else output 'not found'."

Pseudocode: binary search for V in sorted array A size N.

"low = 0; high = N-1; loop while low

Pseudocode: push value X onto stack S.

S.push(X).

Pseudocode: pop top of stack S into X (safe).

if not S.isEmpty() then X = S.pop().

"Pseudocode: enqueue X

dequeue into Y."

Pseudocode: transfer all items from stack S to queue Q.

"loop while not S.isEmpty(); X = S.pop(); Q.enqueue(X); end loop."

Pseudocode: find maximum in array A size N.

"max = A[0]; loop i from 1 to N-1; if A[i] > max then max = A[i]; end loop; output max."

Pseudocode: find minimum in array A size N.

"min = A[0]; loop i from 1 to N-1; if A[i] < min then min = A[i]; end loop; output min."

Pseudocode: read all items from collection C into array D.

"i = 0; loop while C.hasNext(); D[i] = C.getNext(); i = i + 1; end loop."

Pseudocode: recursive sum of linked list starting at head.

function sum(node); if node == null then return 0; else return node.data + sum(node.next); end.

Pseudocode: insert X at front of linked list with head H.

newNode = new Node(X); newNode.next = H; H = newNode.

Pseudocode: insert X at end of linked list with head H.

"newNode = new Node(X); if H == null then H = newNode else curr = H; loop while curr.next != null; curr = curr.next; end loop; curr.next = newNode."

Pseudocode: delete node with value X from linked list with head H.

"if H.data == X then H = H.next; else prev = H; curr = H.next; loop while curr != null and curr.data != X; prev = curr; curr = curr.next; end loop; if curr != null then prev.next = curr.next."

Pseudocode: count nodes in linked list with head H.

"count = 0; curr = H; loop while curr != null; count = count + 1; curr = curr.next; end loop; return count."

Pseudocode: recursive inorder traversal of binary tree node T.

procedure inorder(T); if T != null then inorder(T.left); output T.data; inorder(T.right); end if.

Pseudocode: recursive preorder traversal of binary tree node T.

procedure preorder(T); if T != null then output T.data; preorder(T.left); preorder(T.right); end if.

Pseudocode: recursive postorder traversal of binary tree node T.

procedure postorder(T); if T != null then postorder(T.left); postorder(T.right); output T.data; end if.

Pseudocode: iterate over 2D array with R rows and C columns.

"loop i from 0 to R-1; loop j from 0 to C-1; // process A[i][j]; end loop; end loop."

Compare array and linked list.

"Array: fixed size

Compare stack and queue.

"Stack: LIFO

Compare RAM and cache.

"Cache: smaller

Compare primary and secondary storage.

"Primary (RAM/cache/ROM): fast

Compare compiler and interpreter.

"Compiler: translates whole program into machine code before execution

Compare client-server and peer-to-peer.

"Client-server: central server provides resources/services

Compare symmetric and asymmetric encryption.

"Symmetric: single shared key for encrypt/decrypt

Command: State.

Give one-line answer only; no explanation needed; each distinct point gains a mark (; separates mark points).

Command: Identify.

"Give brief answer

Command: Outline.

Give a brief summary; 1-2 sentences per mark; include key features without deep explanation.