Computer Science Fundamentals: C++, Data Structures, Sorting, and Searching

Comprehensive review flashcards covering C++ basics, fundamental data structures, stacks, queues, sorting algorithms, binary search trees, and searching methods.

Who developed the C++ programming language, and what is its relationship to the C language?

It was developed by Bjarne Stroustrup as an extension to the C language.

In C++, what do std::cout and std::cin represent, and which stream operators are used with each?

std::cout stands for Character Output and uses the << operator to push data to the screen; std::cin stands for Character Input and uses the >> operator to pull typed keyboard input into a storage variable.

What are the rules for naming variables in C++?

Variable names can contain letters, digits, and underscores; must begin with a letter or an underscore (_); are case-sensitive; cannot contain whitespaces or special characters (such as !, #, %); and cannot use reserved C++ keywords (such as int).

Given the integers x = 10 and y = 3 in C++, what are the outputs of (x / y) and (x % y)?

(x / y) outputs $3$ due to integer division truncation, and (x % y) outputs $1$ as the modulo remainder.

What is the difference between variable declaration, variable assignment, and variable initialization in C++?

Declaration creates the memory storage box and specifies its type (e.g., int age;); assignment places a value into an existing variable (e.g., age = 18;); and initialization combines declaration and assignment into one step (e.g., int age = 18;).

According to the student grading logic in the lecture, what letter grade and status result from a numerical mark of 65?

The letter grade is "Grade: D" (scale 60 to 69) and the status is "Student has failed the subject" (since the mark is below 70).

Under the movie theater ticket pricing logic presented, what is the ticket category, final price, and access status for a 12-year-old customer?

Category: Child Discount (25% OFF), Final Ticket Price: $9$ dollars (base price is $12$ dollars), and Access Status: Restricted to PG and G rated movies only.

How is a data structure defined in computer science?

Conceptual and concrete ways to organize data for efficient storage and efficient manipulation, implemented using the data types, references, and operations provided by a programming language.

What are the requirements listed in the lecture for good software?

Clean Design, Easy maintenance, Reliable (no core dumps), Easy to use, Fast algorithms, Efficient data structures, and Efficient algorithms.

What is the historical origin of the word "algorithm"?

It comes from "algorism," which derives from the name of the Persian textbook author Abu Jáfar Muhammed ibn Musâ Al-Khwârizmî (born about 780 in Baghdad, died about 850).

Which book by Abu Jáfar Muhammed ibn Musâ Al-Khwârizmî is the source of the word "algebra"?

The book ilm al jabr w’al muqabala (The Science of Transposition and Cancellation).

What mathematical problem does Euclid's Algorithm solve, and where did it first appear?

It calculates the greatest common divisor of two integers and first appeared in Euclid's Elements, book vii, propositions i and ii (c. 300 B.C.).

What are the five essential characteristics of an algorithm?

Input, Output, Definiteness, Effectiveness, and Termination.

According to this diagram, how do human language, pseudocode, and high-level programming languages compare in expressiveness and precision?

Human language descriptions are the most easily expressed but least precise; pseudocode provides an intermediate balance; high-level programming languages are the most precise but least easily expressed in natural human terms.

What are the six main steps of problem solving in algorithm development?

Problem definition, Algorithm design or specification, Algorithm analysis, Implementation, Testing, and Maintenance.

In algorithm analysis, how do the fixed part and the variable part of space complexity differ?

The fixed part is the size required to store data and variables that is independent of the problem size, while the variable part is the space needed by variables whose size depends directly on the problem size.

What access principles define a stack data structure?

LIFO (Last In, First Out) and FILO (First In, Last Out), meaning entries can only be inserted and removed at one end called the top.

What conditions define Stack Underflow and Stack Overflow?

Stack Underflow is the condition resulting from trying to pop or remove an item from an empty stack; Stack Overflow is the condition resulting from trying to push or add an item onto a full stack.

What is the optimal solution formula for the minimum number of moves required to solve the Tower of Hanoi puzzle with $n$ disks?

$2^n - 1$ moves.

Starting from an empty stack, what are the contents from top to bottom after executing: Push(15), Push(25), Push(35), Pop(), Push(45), Push(55), Pop(), Push(65)?

[65], [45], [25], [15].

How does a queue differ from a stack in terms of data insertion and removal points?

A queue is a FIFO (First In, First Out) structure where elements are inserted only at the rear (tail/back) and removed only at the front (head), whereas a stack inserts and removes elements from the same end (the top).

What are the specific definitions of Enqueue and Dequeue?

Enqueue is the procedure for adding an entry to the rear of the queue ("entering the queue"); Dequeue is the procedure for removing an entry from the front of the queue ("deleting from the queue").

How is a queue utilized in computer simulation models?

It models waiting lines where transactions or customers arrive and wait for service; tracking clock times across interarrival, arrival, service start, duration, and completion allows observers to analyze real-world system behavior without physical testing.

How does Selection Sort operate, and what is its worst-case time complexity?

It repeatedly scans the unsorted part of the list to pick the smallest element and swaps it to the front of the unsorted boundary; its worst-case time complexity is $O(n^2)$ and it runs in-place.

How does Bubble Sort sort elements, and why is it unsuitable for large data sets?

It compares adjacent elements and swaps them if they are out of order so that the largest value settles at the end after each pass; it is unsuitable for large datasets because its average and worst-case time complexity is $O(n^2)$.

How does Insertion Sort organize elements, and what is its memory requirement?

It keeps an always-sorted sub-list at the left, takes each successive element, and swaps it leftward into its correct position; it operates in-place with a worst-case time complexity of $O(n^2)$.

How does Merge Sort work, and what are its worst-case time and extra memory requirements?

It uses a divide-and-conquer approach by dividing the array in halves recursively until single values remain, then merging them in sorted order; its worst-case time complexity is $O(n \times \text{log}(n))$ and it needs extra memory (a second array).

How do stacks and queues differ from trees and graphs in terms of structural linearity?

Stacks, queues, and lists are linear (one item follows another), whereas trees and graphs are non-linear (one item can lead to many).

What is the formal definition of a binary tree?

A finite set of elements that is either empty or divided into three disjoint subsets: the root, the left subtree, and the right subtree.

What topological characteristics invalidate a graph from being a tree?

The presence of cycles (such as a child node having two parents) or multiple edges connecting the same two nodes.

How are the level of a node and the depth of a binary tree determined?

The root is at level $0$, and any other node's level is its parent's level $+ 1$; the depth of the tree is the maximum level of any leaf in the tree.

What is the distinction between a strictly binary tree and a complete binary tree?

A strictly binary tree has non-empty left and right subtrees for every non-leaf node (no node has exactly one child); a complete binary tree is a strictly binary tree where all leaves reside at the exact same level d.

In a complete binary tree, how many nodes exist at level 3, and what is the total node count for a complete binary tree of depth 3?

Level 3 contains $2^3 = 8$ nodes, and a complete tree of depth 3 contains a total of $15$ nodes ($2^0 + 2^1 + 2^2 + 2^3 = 1 + 2 + 4 + 8 = 15$).

What are the node insertion rules used to locate duplicates when building a Binary Search Tree (BST)?

Compare the new number with the current node: if equal, it is a duplicate; if smaller, branch left; if larger, branch right; if an empty spot is reached, insert the new node there.

What are the Pre-order, In-order, and Post-order traversal sequences for this binary tree?

Pre-order (Node, Left, Right): 14, 4, 3, 9, 7, 5, 15, 18, 16, 17, 20. In-order (Left, Node, Right): 3, 4, 5, 7, 9, 14, 15, 16, 17, 18, 20. Post-order (Left, Right, Node): 3, 5, 7, 9, 4, 17, 16, 20, 18, 15, 14.

Which searching algorithm calculates its probe index using the formula shown in this image?

Interpolation Search, which uses pos = low + \frac{(target - A[low])(high - low)}{A[high] - A[low]}.

What are the index update rules used during a step of Binary Search?

Set mid = (low + high) / 2 (rounded down). If key > array[mid], set low = mid + 1; if key < array[mid], set high = mid - 1; if high < low, halt because the key is not present.

When executing a binary search on a 16-element array (indices 0 to 15) for key = 22, what sequence of mid index values is calculated?

Step 1 evaluates mid = $7$, Step 2 evaluates mid = $11$, Step 3 evaluates mid = $9$, and Step 4 evaluates mid = $10$, where key 22 is found.

Under what condition does the Binary Search algorithm stop and declare a key "not found"?

When high < low.