Programming midterm 2

What is the “head” of a linked list?

The first node where traversal starts

What does each node (Node) of a singly linked list store?

A value and a pointer to the next node

What is the correct declaration of a function that takes a string by const reference and returns the count of a character?

size_t countChar(const std::string& text, char ch);

What task uses the bracket balance checking algorithm with a stack?

Verifying brackets are correctly matched

How does BFS (Breadth-First Search) differ from DFS (Depth-First Search) in terms of data structure used?

BFS uses a FIFO queue to expand nodes level by level, while DFS uses a stack or recursive calls instead

How to correctly print odd numbers from 1 to 9 using a for loop?

for (int i = 1; i <= 9; i += 2) cout << i;

What is the “stability” of a sorting algorithm?

Equal elements keep their order

What does “call stack” mean in the context of program execution?

Stores per-call frames with locals

What is the working principle of the Queue data structure?

FIFO order

What does the method c_str() of a std::string object return?

A const char* to internal buffer

What is the “interface” of a subroutine?

Name, parameter list, and return type

How is a 2D array int A[3][4] stored in memory in C++?

Row-major: rows stored sequentially

What is a DAG (Directed Acyclic Graph)?

A directed graph that contains no cycles of any kind, often used to model dependencies between tasks

What is “alignment” in the context of C++ structs?

Each field of type T must be placed at a memory address that is a multiple of sizeof(T)

What does the “degree” deg(v) of a vertex characterize in an undirected graph?

The number of edges incident to the vertex, which equals the number of its neighbors in the graph

What happens when an argument is passed to a function by value (T)?

A full copy is created on the stack

What happens if a large string is passed by value (std::string s) to a function?

A full copy is made; this is slow

How do you access a struct field through a pointer to that struct?

Using the arrow operator: ptr->field

What is the invariant of Bubble Sort after each full pass?

Largest remaining element is placed at end

What is the bool swapped flag used for in Bubble Sort?

Early exit on no swaps

What is the operation of adding an element to a queue called?

enqueue

What does “connected graph” mean?

For any pair of vertices in the graph there exists at least one path connecting them through edges

What does the following code print: for (int i = 0; i < 10; i++) { if (i % 2 == 0) continue; if (i == 7) break; cout << i << “ “; }

1 3 5

What is the scope of a local variable declared inside a function?

Only inside that function

What does a struct definition without creating a variable — e.g., struct Student { string name; int age; }; — mean?

It declares a new type only; no storage is allocated until a variable of that type is actually created

What happens to performance when traversing a 1000x1000 matrix with the outer loop over columns in C++?

Significant slowdown from cache misses

What is a union in C++?

A type in which all fields share the same memory region; the size equals the size of the largest field

What should be used instead of union for type-safe storage of values of different types in C++17?

std::variant

What is the result of isPalindrome(“ARURA”) with a correct two-pointer implementation?

true

How are tensors used in neural networks?

Image batches are stored as 4D tensors; matrix multiplication is used for fully-connected layers and convolution for features

Which rule minimizes padding (filler bytes) when declaring a struct?

Declare struct fields from largest type size down to smallest, which minimizes padding between fields

What does the following fragment print in its first line: for (int i = 1; i <= 5; i++) { for (int j = 0; j < i; j++) cout << i; cout << endl; }

1

What happens when you write to one field of a union and read from another?

Undefined behavior in standard C++; only the most recently written field can be read back portably

In which real application is the Queue (FIFO) data structure used?

Print job buffer in printers

What does the declaration void replaceAll(std::string& text, char old, char newCh) mean in terms of parameter passing?

Modifies the string in place

Which tree traversal algorithm uses a queue and visits nodes level by level?

Breadth-First Search (BFS), also known as level-order traversal because it visits nodes level by level

What happens if the counter variable is modified inside a for loop body: for (int i = 0; i < 10; i++) { i += 2; cout << i; }

The loop completes in fewer total iterations than the original ten because i advances faster

When is it recommended to use a for loop instead of while?

When the iteration count is known in advance

What is the complexity of checking whether edge (u, v) exists using an adjacency matrix?

O(1) because checking the existence of edge (u,v) is just a direct lookup of the matrix cell A[u][v]

What is a sign of an infinite while loop in C++?

The variable in the condition is never modified

What is the last number printed by: int x = 5; do { cout << x << “ “; x–; } while (x > 0);

1

What is the main advantage of a linked-list-based queue over an array-based queue?

Dynamic size with no fixed limit

What type is used in C++ to store container sizes (the result of .size())?

size_t

What is recursion in programming?

A technique in which a function calls itself in order to solve a smaller instance of the same problem

Which data structure underlies the “Undo” (Ctrl+Z) operation in text editors?

Stack — pop the latest action