Data Structures - Multiple Choice Questions

Choose a study mode

Play Quiz
Study Flashcards
Spaced Repetition
Chat to Lesson

Podcast

Play an AI-generated podcast conversation about this lesson

Questions and Answers

What is the primary purpose of using two additional stacks to reverse the order of elements on a stack S?

  • To maintain the order of elements (correct)
  • To allow for faster retrieval of elements
  • To allow elements to be inserted in sorted order
  • To increase the stack size

A quick sort algorithm has a worst-case time complexity of O(n^2).

True (A)

Describe how values are hashed using the division method of hashing.

Values are hashed by dividing the key by the table size and using the remainder as the index.

Dijkstra's algorithm is primarily used for finding the _____ path in graphs.

<p>shortest</p> Signup and view all the answers

Match the following sorting techniques with their key characteristics:

<p>Quick Sort = Divides and conquers method based on pivot Merge Sort = Stable sort using dividing and merging Bubble Sort = Simple but inefficient comparison sort Heap Sort = Utilizes a binary heap data structure</p> Signup and view all the answers

Which of the following is not a method of collision resolution in hashing?

<p>Direct mapping (B)</p> Signup and view all the answers

What is an expression tree for the infix expression: ((a + b) + c * (d + e) + f) * (g + h)?

<p>The expression tree has '*' at the root, with left subtree as '((a + b) + c * (d + e) + f)' and right as '(g + h)'.</p> Signup and view all the answers

In an array implementation of a double ended queue, elements can only be added at one end.

<p>False (B)</p> Signup and view all the answers

Which data structure may give an overflow error, even if the current number of elements is less than its size?

<p>Stack (C)</p> Signup and view all the answers

A fully parenthesized infix expression requires precedence rules for evaluation.

<p>False (B)</p> Signup and view all the answers

List three major applications of stack.

<p>Function call management, Backtracking algorithms, Expression evaluation and conversion.</p> Signup and view all the answers

The ______ of a queue is calculated by tracking the index of the first element.

<p>front</p> Signup and view all the answers

The number of comparisons needed in the worst case by merge sort for two sorted lists of size m and n is:

<p>m + n - 1 (C)</p> Signup and view all the answers

What is the primary data structure used for recursion?

<p>Stack</p> Signup and view all the answers

Match the following data structures with their typical applications:

<p>Stack = Function call management Queue = Order processing systems Linked List = Dynamic memory allocation Binary Tree = Hierarchical data representation</p> Signup and view all the answers

In an AVL tree, balancing is performed when the height difference between the left and right subtrees exceeds ______.

<p>1</p> Signup and view all the answers

What is the minimum number of queues needed to implement a priority queue?

<p>23 (C)</p> Signup and view all the answers

A linked list is considered a non-linear data structure.

<p>False (B)</p> Signup and view all the answers

What is a header linked list?

<p>A header linked list is a linked list that includes a special header node to simplify list operations.</p> Signup and view all the answers

In C language, to implement a heterogeneous linked list, one should use a __________ pointer type.

<p>void</p> Signup and view all the answers

Match the following terms to their definitions:

<p>Abstract Data Type (ADT) = A model for data types based on their behavior and operations Doubly Linked List = A linked list where each node has pointers to both next and previous nodes Sparse Matrix = A matrix predominantly composed of zero elements Garbage Collection = The process of reclaiming memory by removing unreachable objects</p> Signup and view all the answers

What are the advantages of a doubly linked list over a singly linked list?

<p>All of the above (D)</p> Signup and view all the answers

What is insertion sort and how many key comparisons does it make in its worst case?

<p>Insertion sort is a simple sorting algorithm that builds the final sorted array one item at a time. In its worst case, it makes $O(n^2)$ key comparisons.</p> Signup and view all the answers

The expression P: (A+B)/(C-D) can be converted to __________ and __________ notation.

<p>prefix, postfix</p> Signup and view all the answers

Flashcards

Singly Linked List

A linear data structure where elements are stored sequentially in a series of nodes, each holding data and a pointer to the next node.

Header Linked List

A data structure that uses a pointer to its first node, referred to as the header, to facilitate efficient access and traversal.

Doubly Linked List

A data structure where nodes have pointers to both the next and previous nodes, allowing traversal in both directions.

Binary Search Tree

A tree-based data structure where each node holds a value, and child nodes are always greater or less than their parent, depending on the order of comparison. This structure allows for efficient searching.

Signup and view all the flashcards

Polynomial Representation using Linked List

A data structure that represents a mathematical polynomial, where each node represents a term with its coefficient and exponent.

Signup and view all the flashcards

Garbage Collection

A system for storing and managing memory, automatically reclaiming unused portions of memory for later use.

Signup and view all the flashcards

Polish Notation (Prefix Notation)

A method of expressing mathematical expressions where operators precede their operands.

Signup and view all the flashcards

Postfix Notation

A method of expressing mathematical expressions where operators follow their operands.

Signup and view all the flashcards

Stack

A data structure which follows Last In, First Out (LIFO) principle. New elements are added to the top and removed from the top. It has operations like push, pop, peek, and isEmpty.

Signup and view all the flashcards

Preorder Traversal

A recursive traversal of a binary tree in which the root is visited first, followed by visiting the left subtree and then the right subtree. This process is repeated for each subtree.

Signup and view all the flashcards

Quick Sort

A method of sorting where a pivot is chosen and elements are partitioned into two sub-arrays: one containing elements smaller than the pivot and the other with elements larger than the pivot. This process is recursively applied to the sub-arrays until the entire array is sorted.

Signup and view all the flashcards

Heap

A binary tree whose nodes satisfy the heap property: the value of each node is greater than or equal to the values of its children. This is useful for finding the maximum or minimum value in a set efficiently. A heap has operations like insert, deleteMin, and heapify.

Signup and view all the flashcards

Division Method Hashing

A technique used to map keys to indices in a hash table. The division method calculates the index by dividing the key value by the size of the hash table and taking the remainder. Collision resolution techniques are used to handle situations where two keys map to the same index.

Signup and view all the flashcards

Adjacency Matrix

A method of representing a graph where each edge is explicitly represented by its vertices. The matrix is an n x n square matrix, where n is the number of vertices. A value of 1 in the matrix represents an edge between the corresponding vertices, while 0 represents no edge.

Signup and view all the flashcards

Asymptotic Notation

A representation of the complexity of an algorithm using mathematical notation. The notation focuses on the growth rate of the algorithm's performance as the input size increases. It helps compare algorithms based on their efficiency and scalability.

Signup and view all the flashcards

Circular Queue

A circular queue is a queue data structure implemented as a fixed-size array where the last element is followed by the first element, making it circular.

Signup and view all the flashcards

Hierarchical Data Model

A data structure used for storing and organizing information in a hierarchical manner. Each node has a parent and may have multiple children representing the relationships between different data elements.

Signup and view all the flashcards

Relational Database Management System (RDBMS)

A data structure that uses a table to store data where each row represents a unique entity or record, and each column represents a specific attribute or field of that entity.

Signup and view all the flashcards

Queue

A linear data structure that follows the First In, First Out (FIFO) principle, where elements are added at the rear (enqueue) and removed from the front (dequeue).

Signup and view all the flashcards

Binary Search Tree (BST)

A tree data structure where all nodes have a maximum of two children, representing the left and right subtree. The left subtree contains values smaller than the parent node, and the right subtree contains values larger than the parent node.

Signup and view all the flashcards

Game Tree

A graph that represents all possible states of a game, where each node represents a state and edges represent possible moves. Used for analysis and strategy in games.

Signup and view all the flashcards

Column Major Ordering

In a 2D array, column-major refers to the storage order where elements in the same column are stored consecutively in memory.

Signup and view all the flashcards

Study Notes

Data Structures - Multiple Choice Questions

  • Memory Allocation: The operating system (OS) periodically collects free memory space to form contiguous blocks. This process is known as dynamic memory allocation.
  • Direct Search Techniques: Binary Search, Linear Search, Tree Search, and Hashing are direct search techniques.
  • Binary Tree Deletion: Nodes with two children (in a binary tree) are replaced by either their inorder predecessor or inorder successor.
  • Data Structures Model: A collection of operations defined on a mathematical model is called a data structure.
  • Graph Vertex Degree: The sum of the degree of each vertex in an undirected graph with n vertices and e edges equals 2e.
  • Full Binary Tree Nodes: A full binary tree with 2n+1 nodes contains n-1 non-leaf nodes.
  • Linear Lists: A linear list in which deletion occurs from one end (front) and insertion from the other end (rear) is called a queue.
  • Postfix Expression: The postfix form of -A/BC$DE is ABC$ED/-.
  • Full Binary Tree Leaves: A full binary tree with n leaves contains 2n-1 nodes.
  • Graph Traversal Data Structure: A queue is used for Breadth-First Traversal of a graph.
  • Hashing Collisions: The expected number of collisions when hashing n keys into a table of size m (where n < m) is less than 1.
  • Adjacency Matrix: The i,jth entry in an adjacency matrix A of graph G gives the number of paths of length K from vertex Vi to vertex Vj.

Data Structures - Short Answer Questions

  • Data Structures Applications: Data structures are used extensively in databases, networks, hierarchical data models.
  • Array Vs Variable: An array is a collection of variables of the same data type stored in contiguous memory locations, unlike a single variable that stores a single value.
  • Abstract Data Type (ADT): A mathematical model of a user-defined type along with the set of operations that can be performed on that type.
  • Column Major Ordering: Elements in a multi-dimensional array are stored in columns first, then subsequent columns.
  • Queue as Linear: A queue is considered a linear data structure as the elements are arranged in a sequential manner, where the first element inserted is the first to be removed.
  • Postfix Expression: The postfix expression for A+B/C is A B+ C/.
  • Binary Search Tree (BST): BSTs are used for efficient searches, insertions, and deletions of data.
  • Stack Operations: Stack operations include pushing new elements onto the stack and popping elements off the stack.
  • Queue Front Calculation: The front of a queue is calculated as the index of the first element in the array that stores the queue.
  • Queue and Array Relationship: A queue is implemented using an array; elements are added to the end of the array and deleted from the front.
  • Spanning Tree: A connected, acyclic graph.
  • Hash Function Types: Hashing functions can be categorized based on the methods used to derive the key value from the input.
  • Collision Resolution Methods: Collision resolution techniques are strategies used in hashing to manage when different keys map to the same slot within the hash table.
  • Recursion Data Structure: A stack is often used to support recursion.
  • AVL Tree Balancing: AVL trees balance themselves after insertions or deletions, using rotations to ensure that the height difference between subtrees is always at most one.
  • RDBMS Data Structure: RDBMS use a variety of data structures to represent relationships, potentially using trees, graphs, or other structured forms, in the internal storage representation.

Studying That Suits You

Use AI to generate personalized quizzes and flashcards to suit your learning preferences.

Quiz Team

Related Documents

Data Structures Past Paper 2018 PDF

More Like This

Use Quizgecko on...
Browser
Open
Browser
Browser