additional midterm flashcard 2

Question 1

What is an interface in Java?

Answer 1

A collection of abstract methods and constants that establishes a set of methods that a class must implement

Question 2

What are the key differences between interfaces and classes?

Answer 2

1. Cannot instantiate an interface 2. No constructors 3. All methods are abstract 4. Only static and final fields allowed 5. Classes implement interfaces rather than extend them

Question 3

What is an Abstract Data Type (ADT)?

Answer 3

A collection of data items together with the operations that can be performed on that data, specifying WHAT operations do but not HOW they do it

Question 4

When should you use interfaces in Java?

Answer 4

1. When you have multiple implementations for the same ADT 2. To expose simple public methods while hiding implementation details 3. To provide a template for classes that must be followed

Question 5

What is abstraction in programming?

Answer 5

The separation of purpose (what something does) from implementation (how it does it), allowing users to use functionality without knowing internal details

Question 6

What are generics in Java?

Answer 6

A feature that allows classes, interfaces, and methods to be written as templates that can work with any data type while maintaining type safety at compile time

Question 7

Why can’t primitive types be used directly with generics?

Answer 7

Primitive types cannot be used directly in angle brackets (like ). Instead, wrapper classes must be used (like )

Question 8

How do you make a class generic?

Answer 8

Add a type parameter in angle brackets after the class name (e.g., class Name) and use that parameter as a type within the class

Question 9

What is a data structure?

Answer 9

A particular way of organizing data in a computer so that it can be used efficiently, with different structures suited to different applications

Question 10

What are the key characteristics of an algorithm?

Answer 10

1. Unambiguous description 2. Defined set of inputs and outputs 3. Guaranteed to terminate 4. Produces a defined result

Question 11

What is a linked structure?

Answer 11

A collection of objects (nodes) storing data and links to other objects, where each node contains both data and references to other nodes

Question 12

What are the advantages of arrays?

Answer 12

1. Random quick access to elements 2. Groups like information together 3. Efficient direct access to elements

Question 13

What are the disadvantages of arrays?

Answer 13

1. Fixed size requiring recreation for resizing 2. Insertion/deletion requires shifting elements 3. Memory must be contiguous

Question 14

What is the difference between == and .equals() for objects?

Answer 14

== compares if two references point to the same object in memory, while .equals() compares the actual content/values of the objects

Question 15

What is a node in the context of linked structures?

Answer 15

An object in a linked structure that contains both data and references (links) to other nodes of the same type

Question 16

What happens if you lose the first reference in a linked structure?

Answer 16

You lose access to the entire chain of nodes since there’s no way to reach them without the first reference

Question 17

What are wrapper classes used for in Java?

Answer 17

To convert primitive data types into objects, allowing them to be used with generics and collections (e.g., Integer for int, Double for double)

Question 18

What is the purpose of type parameters in generic classes?

Answer 18

To allow the class to work with different data types while maintaining type safety, using placeholders like or that are replaced with actual types when used

Question 19

What is a Stack and what principle does it follow?

Answer 19

A Stack is a collection whose elements are added and removed from the same end (top). It follows LIFO (Last In, First Out) principle

Question 20

What are the primary operations of a Stack ADT?

Answer 20

1. push (add element to top) 2. pop (remove and return top element) 3. peek (view top without removing) 4. isEmpty (check if stack empty)

Question 21

What is a Queue and what principle does it follow?

Answer 21

A Queue is a collection where elements are added at rear and removed from front. It follows FIFO (First In, First Out) principle

Question 22

What are the primary operations of a Queue ADT?

Answer 22

1. enqueue (add to rear) 2. dequeue (remove from front) 3. first (view front without removing) 4. isEmpty (check if queue empty)

Question 23

What are the differences between array and linked implementations of a Stack?

Answer 23

Array implementation: Push O(n)* due to resizing, Pop O(1). Linked implementation: Both Push and Pop are O(1), but uses more memory for links

Question 24

What are the key differences between ArrayQueue and LinkedQueue?

Answer 24

ArrayQueue: enqueue/dequeue O(n) due to shifting. LinkedQueue: both operations O(1). Array implementation uses less memory but has fixed size initially

Question 25

What is a CircularArrayQueue and why use it?

Answer 25

A queue implementation using an array that wraps around to the beginning when reaching the end, making enqueue/dequeue operations more efficient (O(1)) by avoiding shifting

Question 26

What is a Linked List and what are its key characteristics?

Answer 26

A data structure composed of nodes where each node contains data and reference(s) to other nodes. Can grow dynamically, efficient insertion/deletion, but sequential access

Question 27

What are the three main types of Linked Lists?

Answer 27

1. Singly Linked (one directional links) 2. Circular (last node links to first) 3. Doubly Linked (bidirectional links)

Question 28

What are the advantages of Linked Lists over Arrays?

Answer 28

1. Dynamic size (can grow as needed) 2. Efficient insertion/deletion 3. No need to shift elements 4. Memory allocation as needed

Question 29

What are the disadvantages of Linked Lists?

Answer 29

1. No random access (sequential access only) 2. Extra memory needed for storing references 3. Not cache-friendly due to non-contiguous memory

Question 30

How does garbage collection work with Linked Lists in Java?

Answer 30

Java automatically reclaims memory from objects that have no references pointing to them. To 'delete' a node, simply remove all references to it

Question 31

What is the time complexity for searching in a Linked List?

Answer 31

O(n) - must traverse the list sequentially from the beginning to find an element

Question 32

What is the time complexity of adding to front vs end of Linked List?

Answer 32

Front: O(1) - just update head pointer. End: O(n) - must traverse entire list (unless tail pointer maintained)

Question 33

What real-world examples use Stack data structure?

Answer 33

1. Browser back button history 2. Undo operations in text editors 3. Expression evaluation 4. Function call stack in programming

Question 34

What real-world examples use Queue data structure?

Answer 34

1. Print queue for documents 2. Keyboard input buffer 3. Customer service systems 4. Process scheduling in operating systems

Question 35

What is the purpose of a moving reference in Linked Lists?

Answer 35

A temporary reference that traverses the list to access or modify nodes without losing the reference to the start of the list

Question 36

How does a CircularArrayQueue handle the 'wraparound' at array end?

Answer 36

Uses modulo arithmetic (%) with array length to cycle back to beginning when reaching end, making it appear circular

Question 37

What is the main difference between Stack and Queue order?

Answer 37

Stack (LIFO) reverses the order of elements when they're retrieved, while Queue (FIFO) maintains the original order

Question 38

What happens during ArrayStack expansion?

Answer 38

When array is full, creates new array (typically 2x size), copies all elements to new array, updates reference to new array. O(n) operation