Bachelor of Computer Engineering Data Structure Flashcards

Which of the following best sums up an array?

Answer: Container of objects of similar types

An array is a fundamental data structure that stores a fixed-size sequential collection of elements of the same data type. All elements in an array are of the same type (e.g., all integers, all characters), and they are stored contiguously in memory, allowing for efficient access by index.

How can an array be initialized in C?

Answer: int arr[3] = {1,2,3};

In C programming, an array is initialized by declaring its type and size, followed by an equals sign and a list of initial values enclosed in curly braces `{}`. The syntax `int arr[3] = {1,2,3};` correctly declares an integer array named `arr` of size 3 and initializes its elements to 1, 2, and 3, respectively.

In Java, how do you create an array?

Answer: int arr[] = new int[3];

In Java, arrays are objects, so they must be created using the `new` keyword. The syntax `new int[3]` allocates memory for an array of 3 integers. The `int arr[]` part declares a variable `arr` that can hold an array of integers, and the assignment links it to the newly created array object.

Which of the following notions uses arrays the most?

Answer: Spatial locality

Spatial locality refers to the tendency of a program to access data items that are physically close to each other in memory. Arrays store elements in contiguous memory locations, which naturally promotes spatial locality. When an element in an array is accessed, it's highly probable that nearby elements will be accessed soon, making arrays highly beneficial for caching and memory optimization based on spatial locality.

The action of adding a stack member is known as .

Answer: Push

In a stack data structure, the operation of adding an element is known as 'push'. This operation places the new element at the top of the stack. Stacks follow a Last-In, First-Out (LIFO) principle, meaning the last element added is the first one to be removed.

The action of eliminating a stack element is known as .

Answer: Pop

In a stack data structure, the operation of eliminating an element is known as 'pop'. This operation removes the element that is currently at the top of the stack. Stacks adhere to the Last-In, First-Out (LIFO) principle, so the most recently added element is always the one removed by a pop operation.

It is known as ________ in a stack when a user attempts to remove an element from an empty stack.

Answer: Underflow

Attempting to remove an element from an empty stack is known as an 'underflow' condition. This is an error state because there are no elements available to be popped. Proper stack implementations typically check if the stack is empty before performing a pop operation to prevent underflow.

If you add one element to a stack that already has five elements and has a size of 5, the stack will become .

Answer: Overflow

When a user attempts to add an element to a stack that is already full (i.e., it has reached its maximum capacity), this condition is known as 'overflow'. In this scenario, the stack cannot accommodate any more elements. Proper stack implementations should check for overflow before performing a push operation to prevent data loss or program errors.

The term "linear list" refers to a collection of elements where deletions may only be made from one end (front) and insertions can only be made from the other end (rear).

Answer: Queue

A queue is a linear data structure that follows the First-In, First-Out (FIFO) principle. Elements are always added at one end, called the 'rear' (enqueue operation), and removed from the other end, called the 'front' (dequeue operation). This behavior perfectly matches the description of deletions only from the front and insertions only from the rear.

Another name for circular queue is

Answer: Ring Buffer

A circular queue is a linear data structure where the last element points back to the first element, forming a circle. This arrangement allows for efficient reuse of empty slots, preventing the need to shift elements after deletions. It is also commonly known as a 'Ring Buffer' due to its circular nature and buffering capabilities.

What is the name of a linear collection of data pieces where the linear node is indicated by a pointer?

Answer: Linked list

A linked list is a linear collection of data elements, called nodes, where each node contains both data and a pointer (or reference) to the next node in the sequence. This pointer-based structure allows elements to be stored non-contiguously in memory. Unlike arrays, linked lists do not require contiguous memory allocation and can grow or shrink dynamically.

Which of the following statements about the use of an array is false?

Answer: Accessing elements at specified positions

Arrays are highly efficient for accessing elements at specified positions using their index, which takes constant time (O(1)). This is a primary advantage and a fundamental 'use' of arrays, making the statement true. The question asks for a *false* statement about array use; therefore, 'accessing elements at specified positions' is the correct answer because it is a *true* and beneficial aspect, unlike the other options which describe limitations or potential drawbacks.

How long does it take to insert at the end of a dynamic array?

Answer: Either O(1) or O(n)

Inserting an element at the end of a dynamic array typically takes O(1) time on average (amortized constant time). However, if the array's underlying storage becomes full, a new, larger array must be allocated, and all existing elements copied over. This resizing operation takes O(n) time, where 'n' is the number of elements. Thus, the time complexity can be either O(1) in most cases or O(n) in the worst-case scenario during a resize.

How long does it take to count all the elements in the linked list?

Answer: O(n)

To count all the elements in a linked list, you must traverse the entire list from the head node to the tail node. This involves visiting each node exactly once to increment a counter. Therefore, the time complexity for this operation is directly proportional to the number of elements 'n' in the list, resulting in O(n) time.

What is a double linked list that uses little memory?

Answer: Each node has only one pointer to traverse the list back and forth

A memory-efficient doubly linked list, often called an XOR linked list, achieves its efficiency by storing only one pointer in each node. Instead of separate 'next' and 'previous' pointers, it stores the bitwise XOR of the addresses of the previous and next nodes. This allows traversal in both directions by using the address of the current node and the XOR sum to deduce the address of the other adjacent node, effectively reducing memory overhead.

What real-world situations from the list below would you identify with a stack data structure?

Answer: piling up of chairs one above the other

A stack data structure operates on a Last-In, First-Out (LIFO) principle, meaning the last item added is the first one to be removed. Piling up chairs one above the other perfectly illustrates this concept: you add new chairs to the top, and when you want to remove a chair, you typically take the one from the very top first. This mirrors the push and pop operations of a stack.