Data Structure And Algorithm Flashcards
What is an array in C++?
A collection of elements of the same type, stored in contiguous memory locations.
What is the starting index of an array in C++?
0
How is the size of an array determined in C++?
At compile time (static size).
What happens if you access an out-of-bounds index in a C++ array?
It can cause undefined behavior.
How do you access an element in an array?
Using the syntax array_name[index].
What is a pointer in C++?
A variable that stores the memory address of another variable.
What symbol is used to declare and dereference a pointer?
*.
What symbol is used to get the address of a variable?
&.
Can a pointer point to any data type in C++?
Yes, it can point to any data type (e.g., int, char).
What is the purpose of the dereferencing operator (*) in pointers?
To access the value stored at the memory address held by the pointer.
What is a null pointer?
A pointer initialized to nullptr or NULL that doesn’t point to any valid address.
What is pointer arithmetic?
Operations like ptr++ to navigate through array elements.
What is recursion?
A technique in which a function calls itself to solve a problem.
Why is a base case important in recursion?
To avoid infinite recursion.
What are some common problems solved using recursive algorithms?
Factorial, Fibonacci, and tree traversals.
What is a base case in recursion?
The condition under which the recursion ends.
What is a recursive case?
The part of the function where the function calls itself with a reduced problem size.
What does the factorial function return when n is 0?
1, which is the base case.
What happens when recursion goes too deep?
It can exhaust the stack memory, leading to a Stack Overflow.
What principle does a stack follow?
Last In First Out (LIFO).
What operation adds an element to the top of the stack?
Push.
What operation removes the top element from the stack?
Pop.
What does the ‘Top’ operation do in a stack?
Returns the top element without removing it.
What is a key limitation of a stack implemented using arrays?
It has a fixed size.
What does the constructor in the Stack class initialize?
It initializes the top to -1.
What message is displayed when a stack overflow occurs?
“Stack Overflow”.
What message is displayed when a stack underflow occurs?
“Stack Underflow”.
What does the peek function return if the stack is empty?
-1 and displays “Stack is empty”.
What does the ‘Top’ refer to in a stack?
The current index of the last element inserted in the stack.
What happens during a stack overflow?
Trying to push an element when the stack is full.
What is stack underflow?
Trying to pop an element when the stack is empty.
What principle does a queue follow?
First In First Out (FIFO).
What operation adds an element to the queue?
Enqueue.
What operation removes an element from the queue?
Dequeue.
What do ‘Front’ and ‘Rear’ indicate in a queue?
The current front and rear positions in the array.
What is a limitation of the array implementation of a queue?
It has fixed capacity and requires checking for overflow.
What do ‘front’ and ‘rear’ indicate in a queue?
They indicate the beginning and end of the queue, respectively.
What does the function ‘isFull()’ check?
It checks if the queue is full by comparing ‘rear’ to 4.
What condition does ‘isEmpty()’ check for?
It checks if the queue is empty by verifying if ‘front’ is -1 or greater than ‘rear’.
What happens when ‘enqueue’ is called on a full queue?
It outputs ‘Queue Overflow’.
What does the ‘dequeue()’ function do?
It removes and returns the front element of the queue, or outputs ‘Queue Underflow’ if the queue is empty.
What does the ‘peek()’ function return?
It returns the front element of the queue without removing it, or -1 if the queue is empty.
What is ‘Queue Overflow’?
It occurs when trying to enqueue an element into a full queue.
What is ‘Queue Underflow’?
It occurs when trying to dequeue an element from an empty queue.
What is a linked list?
A dynamic data structure where elements, called nodes, are linked using pointers.
How is a linked list simulated using an array?
By managing pointers (or indices) within the array, where each node has data and a next index.
What are the two parts of each node in an array-based linked list?
Data (the value stored) and Next Index (the index to the next element).
What is the head in a linked list?
The first element (or node) in the list.
How is the end of the list indicated in an array-based linked list?
By a -1 in the next index, serving as the equivalent of nullptr.
What is a key property of an array-based linked list?
It uses an array to store both data and next pointers, but the size is fixed by the array’s size.
What operation inserts a new element at the head of the list?
Insert at the beginning.
What operation removes an element from the list?
Delete an element.
What does the traverse operation do in a linked list?
Visits each node in the list and prints its data.
What does the ‘freeIndex’ variable represent in the LinkedList class?
It points to the next free position in the array.
What does the line ‘list[MAX_SIZE - 1].next = -1
’ signify?
What happens when ‘freeIndex’ is -1 in the ‘insertAtBeginning’ function?
It indicates that the list is full.
What does ‘list[newIndex].next = head
’ do in the ‘insertAtBeginning’ function?
How does the ‘insertAtEnd’ function handle an empty list?
If the list is empty, the new node becomes the head.
What is the purpose of the ‘while’ loop in the ‘insertAtEnd’ function?
To traverse to the end of the list.
What does ‘list[newIndex].next = -1
’ signify in the ‘insertAtEnd’ function?
What does the ‘deleteAtBeginning’ function check before proceeding?
It checks if the list is empty by verifying if ‘head’ is -1.
What does the ‘head’ represent in a linked list?
The index of the first node in the list.
What is the purpose of the ‘next index’ in a linked list?
It stores the index of the next node in the list.
What does ‘free index’ point to in a linked list?
The next available spot in the array for inserting a new node.
How is the end of the linked list indicated?
By using -1 to mark the end (no next node).
What is linked list traversal?
The process of visiting each node in the list sequentially.
How does this array-based implementation simulate a linked list?
By manually managing indices instead of pointers.
What does each ‘node’ in the array hold?
Both the data and an index pointing to the next node.
What happens when a node is deleted from the beginning of the linked list?
The head moves to the next node and the old head is added to the free list.
