comp 2503 midterm

Question 1

What is computational complexity?

Answer 1

The amount of resources (time and space) required by an algorithm to solve a problem as a function of input size

Question 2

What is Big-O notation used for?

Answer 2

To describe the upper bound or worst-case growth rate of an algorithm’s resource usage

Question 3

What is the difference between LIFO and FIFO?

Answer 3

LIFO (Last In First Out) is used by stacks where the last element added is the first removed. FIFO (First In First Out) is used by queues where the first element added is the first removed

Question 4

What are the main operations of a Stack?

Answer 4

push (add to top), pop (remove from top), peek (view top without removing), isEmpty

Question 5

What are the main operations of a Queue?

Answer 5

enqueue (add to rear), dequeue (remove from front), peek (view front without removing), isEmpty

Question 6

What makes Binary Search more efficient than Linear Search?

Answer 6

Binary Search divides the search space in half each time (O(log n)), while Linear Search checks each element sequentially (O(n))

Question 7

What is the purpose of generics in Java?

Answer 7

To enable classes to work with different data types while maintaining type safety at compile time

Question 8

What is the Comparable interface used for?

Answer 8

To define a natural ordering for a class by implementing the compareTo method

Question 9

What is the Comparator interface used for?

Answer 9

To define multiple different ways to compare objects of a class without modifying the class itself

Question 10

What are the key differences between arrays and linked lists?

Answer 10

Arrays have fixed size and continuous memory with direct access, while linked lists have dynamic size, scattered memory, and sequential access

Question 11

What is the time complexity of adding to the front of an array vs. linked list?

Answer 11

Array: O(n) due to shifting elements, Linked List: O(1) by changing the head pointer

Question 12

What is the time complexity of accessing an element by index in array vs. linked list?

Answer 12

Array: O(1) direct access, Linked List: O(n) must traverse from start

Question 13

What are traversal pointers in linked lists used for?

Answer 13

To move through the list one node at a time, often used to search, modify, or perform operations on nodes

Question 14

What is the difference between Singly and Doubly Linked Lists?

Answer 14

Singly Linked Lists have nodes with one pointer to the next node, Doubly Linked Lists have nodes with pointers to both next and previous nodes

Question 15

Why use a Doubly Linked List over a Singly Linked List?

Answer 15

Doubly Linked Lists allow backward traversal and easier deletion of nodes, but use more memory per node

Question 16

What is the advantage of implementing a Stack with a linked list vs. array?

Answer 16

Linked list implementation can grow dynamically without needing to resize, while array implementation may need to resize

Question 17

What problem can be solved using two stacks?

Answer 17

Evaluating arithmetic expressions, implementing undo/redo functionality, or validating matching parentheses

Question 18

What is the key difference in memory usage between arrays and linked lists?

Answer 18

Arrays use contiguous memory blocks and have memory overhead for resizing, linked lists use scattered memory with overhead for node pointers

Question 19

How does Java Collections sort method work with custom objects?

Answer 19

Objects must either implement Comparable interface or a separate Comparator must be provided

Question 20

What is standard input/output in Java?

Answer 20

System.in for input stream (keyboard by default) and System.out for output stream (console by default)

Question 21

In what scenarios would you choose an array over a linked list?

Answer 21

When you need constant-time access to elements, fixed size is acceptable, and frequent insertion/deletion at arbitrary positions isn’t needed

Question 22

What is a moving reference in linked list traversal?

Answer 22

A temporary pointer that moves through the list to access or modify nodes without losing the reference to the head of the list

Question 23

How does a circular array implementation of a queue work?

Answer 23

Uses modulo arithmetic to wrap around array indices, making efficient use of space by reusing empty positions at the start

Question 24

What are the advantages of implementing a queue using a linked list?

Answer 24

No size limitation, efficient enqueue and dequeue operations (O(1)), no need to shift elements

Question 25

How do you handle edge cases in linked list operations?

Answer 25

Check for null pointers, empty lists, single-element lists, and maintain proper links when adding/removing at start/end of list