Consider the following prototype for adding an edge to a full undirected graph: "void InsertEdge(Graph &g, int n, int &e, int d1, int d2);" What does the parameter "e" most likely represent?

The identifier of the edge being added.

A flag indicating whether the insertion succeeded.

The maximum possible number of edges.

In the function "void Func(Graph &g, int n, int &e){ for(int i=1; i Next = NULL; } e=0; }" what is the effect of the statement "e=0"?

It resets the edge count of the graph to zero.

It deallocates memory for all nodes.

It clears all adjacency lists of the graph.

What is the primary advantage of choosing the table size M as a prime number for a hash table that uses the modulo hash function HF(k) = k % M?

It guarantees O(1) lookup time regardless of load factor.

It allows keys to be stored without any collisions.

It eliminates the need for a secondary hash function.

In the context of recursion, which of the following correctly identifies the base case for the factorial function defined as: if(n==0) return 1; else return n*factorial(n-1);

When n exceeds the stack limit.

Which of the following correctly describes the effect of the statement "p = new int[10];" in C++?

It dynamically allocates memory for an array of 10 integers.

It declares a static array of 10 integers on the stack.

It creates a pointer to a single integer initialized to 10.

It frees previously allocated memory for an integer array.

Data Structures and Algorithms Fundamentals | Free quiz

Introduction to Data Structures and Algorithms Fundamentals

Understanding the core concepts of data structures and algorithms is essential for any computer science student or software developer. This course explores hash tables, collision‑resolution strategies, graph representations, open addressing, and recursion fundamentals. Each topic is explained in depth, reinforced with examples, and optimized for search engines using relevant keywords.

Hash Tables and Separate Chaining

A hash table stores key‑value pairs in an array indexed by a hash function. When multiple keys map to the same index, a collision occurs. One common technique to handle collisions is separate chaining, where each array slot contains a linked list of entries.

Worst‑Case Search Complexity

In a poorly distributed hash table, all keys may end up in the same bucket. The linked list then contains all N elements, and searching for a key becomes linear in the number of stored items.

Best case: O(1) when the key is in the first node of its bucket.
Average case (good distribution): O(N/M), where M is the table size.
Worst case: O(N) when the list length equals the total number of keys.

Therefore, the correct answer to the quiz question is O(N).

Collision‑Resolution Methods

When using open addressing, all entries reside directly in the hash table array. The algorithm probes alternative slots until an empty one is found. Different probing strategies define how the next slot is chosen.

Double Hashing

Double hashing employs a secondary hash function to compute the step size for each probe. The probe sequence is:

h(k) + i·h₂(k) (mod M)

Because the step size varies with the key, double hashing reduces clustering compared to linear or quadratic probing.

Other Methods

Separate chaining: Uses linked lists; not an open‑addressing method.
Linear probing: Uses h(k) + i (mod M).
Quadratic probing: Uses h(k) + i² (mod M).

The quiz correctly identifies double hashing as the technique that uses a secondary hash function.

Graph Representations and Edge Counters

Graphs can be represented in many ways, such as adjacency matrices, adjacency lists, or edge lists. When working with an adjacency‑list representation, it is common to keep a counter that tracks the current number of edges.

Understanding Function Parameters

Consider the prototype:

void InsertEdge(Graph &g, int n, int &e, int d1, int d2);

The parameter e is passed by reference (&), indicating that the function may modify its value. In the context of adding an edge, e most logically represents the current number of edges in the graph, which is incremented after a successful insertion.

Resetting the Edge Counter

In the function:

void Func(Graph &g, int n, int &e){
    for(int i=1; i<=n; i++) {
      g[i] = new Node;
      g[i]->Next = NULL;
    }
    e = 0;
  }

The statement e = 0; resets the edge count to zero, effectively indicating that the newly created graph currently has no edges. It does not deallocate memory or clear adjacency lists; those actions are performed by the new Node allocations and pointer assignments.

Open Addressing with Quadratic Probing

Quadratic probing resolves collisions by moving through the table using a quadratic function of the probe number. The general formula for the i‑th probe is:

h(k) + i² (mod M)

Here, h(k) is the primary hash function, i starts at 0 and increments with each collision, and M is the table size. This approach reduces primary clustering, though secondary clustering may still occur.

Choosing a Prime Table Size

When the hash function is defined as HF(k) = k % M, selecting M as a prime number has a significant impact on key distribution.


  
    Prime M ensures that the modulo operation spreads keys more uniformly, especially when keys share common factors.
    It reduces the likelihood of patterns that cause clustering, leading to faster average‑case lookups.
    While it does not guarantee constant‑time lookup for any load factor, it improves overall performance compared to composite table sizes.
  
  The quiz answer highlights this advantage: It reduces clustering and improves uniform key distribution.




  Recursion Basics: Factorial Example
  Recursion solves problems by calling a function within itself. A well‑defined base case stops the recursion and prevents infinite loops.
  int factorial(int n) {
    if (n == 0) return 1; // base case
    else return n * factorial(n - 1);
}
  In this implementation, the base case occurs when n equals 0. Once the function reaches this condition, it returns 1 and unwinds the call stack, producing the final factorial value.



  Dynamic Memory Allocation in C++
  C++ provides the new operator to allocate memory on the heap at runtime. The statement:
  p = new int[10];
  performs the following actions:
  
    Allocates a contiguous block of memory sufficient to store ten int objects.
    Returns a pointer (p) to the first element of that block.
    Ensures the memory persists until it is explicitly released with delete[] p;.
  
  This is a classic example of dynamic allocation, as opposed to static or stack allocation.



  Key Takeaways
  
    Separate chaining can degrade to O(N) search time in the worst case.
    Double hashing uses a secondary hash function to compute probe steps, improving distribution.
    In graph functions, a reference parameter like e typically tracks the current edge count.
    Quadratic probing follows the formula h(k) + i² (mod M).
    Choosing a prime table size for modulo hashing reduces clustering and yields a more uniform distribution.
    The base case for a factorial recursion is when n == 0.
    new int[10] dynamically allocates an array of ten integers on the heap.
  
  By mastering these concepts, learners build a solid foundation for more advanced algorithmic design and efficient data‑structure implementation.

Data Structures and Algorithms Fundamentals

In a linked‑list implementation of a hash table (separate chaining), what is the worst‑case time complexity for searching a key when the table is poorly distributed?

Which collision‑resolution method uses a secondary hash function to compute the probe step size?

Consider the following prototype for adding an edge to a full undirected graph: "void InsertEdge(Graph &g, int n, int &e, int d1, int d2);" What does the parameter "e" most likely represent?

In the function "void Func(Graph &g, int n, int &e){ for(int i=1; i<=n; i++) { g[i] = new Node; g[i]->Next = NULL; } e=0; }" what is the effect of the statement "e=0"?

When using open addressing with quadratic probing, what is the probing sequence formula for the i‑th probe?

What is the primary advantage of choosing the table size M as a prime number for a hash table that uses the modulo hash function HF(k) = k % M?

In the context of recursion, which of the following correctly identifies the base case for the factorial function defined as: if(n==0) return 1; else return n*factorial(n-1);

Which of the following correctly describes the effect of the statement "p = new int[10];" in C++?

Introduction to Data Structures and Algorithms Fundamentals

Hash Tables and Separate Chaining

Worst‑Case Search Complexity

Collision‑Resolution Methods

Double Hashing

Other Methods

Graph Representations and Edge Counters

Understanding Function Parameters

Resetting the Edge Counter

Open Addressing with Quadratic Probing

Choosing a Prime Table Size

Recursion Basics: Factorial Example

Dynamic Memory Allocation in C++

Key Takeaways

Data Structures and Algorithms Fundamentals

In a linked‑list implementation of a hash table (separate chaining), what is the worst‑case time complexity for searching a key when the table is poorly distributed?

Which collision‑resolution method uses a secondary hash function to compute the probe step size?

Consider the following prototype for adding an edge to a full undirected graph: "void InsertEdge(Graph &g, int n, int &e, int d1, int d2);" What does the parameter "e" most likely represent?

In the function "void Func(Graph &g, int n, int &e){ for(int i=1; i<=n; i++) { g[i] = new Node; g[i]->Next = NULL; } e=0; }" what is the effect of the statement "e=0"?

When using open addressing with quadratic probing, what is the probing sequence formula for the i‑th probe?

What is the primary advantage of choosing the table size M as a prime number for a hash table that uses the modulo hash function HF(k) = k % M?

In the context of recursion, which of the following correctly identifies the base case for the factorial function defined as: if(n==0) return 1; else return n*factorial(n-1);

Which of the following correctly describes the effect of the statement "p = new int[10];" in C++?

Introduction to Data Structures and Algorithms Fundamentals

Hash Tables and Separate Chaining

Worst‑Case Search Complexity

Collision‑Resolution Methods

Double Hashing

Other Methods

Graph Representations and Edge Counters

Understanding Function Parameters

Resetting the Edge Counter

Open Addressing with Quadratic Probing

Choosing a Prime Table Size

Recursion Basics: Factorial Example

Dynamic Memory Allocation in C++

Key Takeaways

Your next clickstarts here.

Your next click
starts here.