Data Structures Quiz
48 Questions
0 Views

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 does the pop algorithm do when the stack is empty?

  • Returns an error message
  • Stores the value of stack[top]
  • Decrements top
  • Returns nothing (correct)

    • The size of an array in C can be altered after its declaration.

    False

    What is the base value when calculating the position of elements in an array?

    0

    A static array allocates memory at __________ time.

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

    Match the following stack operations with their description:

    <p>pop = Removes the top element from the stack Top = Returns the top element of the stack isEmpty = Checks if the stack has any elements increment = Increases the top index of the stack</p> Signup and view all the answers

    Which of the following statements is true regarding static arrays?

    <p>They are allocated memory at compile time</p> Signup and view all the answers

    In the algorithm for Top, if there are elements in the stack, it returns the element at the index specified by top.

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

    What does the isEmpty function return if the top index is less than 1?

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

    What does the last node in a linked list point to?

    <p>It points to None.</p> Signup and view all the answers

    Reversing a linked list is possible for cycled linked lists.

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

    What is the time complexity of reversing a linked list using a stack?

    <p>O(N)</p> Signup and view all the answers

    The factorial of 6 is equal to ____.

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

    Which of the following is a characteristic of a stack?

    <p>Last-In-First-Out (LIFO)</p> Signup and view all the answers

    Match the following descriptions with their terms:

    <p>Stack = Last-In-First-Out data structure Factorial = Multiplication of all positive integers up to a number Linked List = Data structure consisting of nodes None = Indicates the end of a linked list</p> Signup and view all the answers

    What is the maximum number of children a node in a binary tree can have?

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

    An empty linked list can be reversed.

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

    In a full binary tree, all internal nodes must have either one child or two children.

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

    What is the base case for the Tower of Hanoi algorithm?

    <p>Moving one disk directly to the destination peg</p> Signup and view all the answers

    What formula gives the number of internal nodes in a full binary tree with n total nodes?

    <p>(n-1)/2</p> Signup and view all the answers

    What is the initial action taken when reversing a linked list?

    <p>Check if the linked list is empty or has a single node.</p> Signup and view all the answers

    The minimum number of nodes possible at the height h of a binary tree is given by ____.

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

    The nth disk is always moved before the n-1 disks in the Tower of Hanoi algorithm.

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

    What is the purpose of the auxiliary peg in the Tower of Hanoi problem?

    <p>To temporarily hold disks while moving the other disks between the source and destination pegs.</p> Signup and view all the answers

    Which of the following is true about the height of a binary tree with L leaf nodes?

    <p>Height is L + 1</p> Signup and view all the answers

    Match the types of binary trees with their descriptions:

    <p>Full Binary Tree = Each internal node has zero or two children Complete Binary Tree = Elements arranged without missing any sequence Perfect Binary Tree = All levels are completely filled Binary Search Tree = Left child nodes are smaller than the parent node</p> Signup and view all the answers

    The algorithm requires moving disks from the source peg to the destination peg using the __________ peg as a temporary holding area.

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

    In a binary tree, the number of nodes at each level doubles as you move down the tree.

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

    Match the following steps of the Tower of Hanoi algorithm to their descriptions:

    <p>Base Case = When only one disk needs moving Recursive Case Step 1 = Moving n-1 disks to the auxiliary peg Moving nth Disk = Moving the largest disk to its destination Recursive Case Step 2 = Moving the n-1 disks to the destination peg</p> Signup and view all the answers

    What is the relationship between the number of leaf nodes (L) in a full binary tree with respect to its height?

    <p>Height is L + 1</p> Signup and view all the answers

    In the pseudocode, what occurs when the function TowerOfHanoi is called with n=1?

    <p>A disk is printed to be moved.</p> Signup and view all the answers

    The Tower of Hanoi algorithm requires that no disk is placed on top of a smaller disk.

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

    Describe the first action taken by the Tower of Hanoi algorithm when n > 1.

    <p>Move the top n-1 disks from the source peg to the auxiliary peg.</p> Signup and view all the answers

    What is the primary function of the Bubble Sort algorithm?

    <p>To sort a list in ascending order</p> Signup and view all the answers

    Bubble Sort requires additional memory space for sorting.

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

    What is the time complexity of Bubble Sort?

    <p>O(N^2)</p> Signup and view all the answers

    In Bubble Sort, if the current element is greater than the next element, we __________.

    <p>swap both elements</p> Signup and view all the answers

    Match the following characteristics with their respective sorting algorithm:

    <p>Bubble Sort = Stable sorting algorithm Insertion Sort = Simulates sorting playing cards Selection Sort = Not covered in this content Quick Sort = Efficient for large datasets</p> Signup and view all the answers

    How many iterations are needed to sort a list of size n using Bubble Sort?

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

    In Bubble Sort, the smallest element gets bubbled to the top in every iteration.

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

    What happens to elements with the same key value during Bubble Sort?

    <p>They maintain their relative order.</p> Signup and view all the answers

    What action is taken when deleting the first node of a circular linked list with multiple nodes?

    <p>The last-&gt;next pointer is updated to skip the head node.</p> Signup and view all the answers

    In a circular linked list, if the list is empty, we can still delete a node.

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

    What should be done if the key matches the single node in a circular linked list?

    <p>Delete that node and set last to nullptr.</p> Signup and view all the answers

    To delete the last node in a circular linked list, we must first find the __________ node.

    <p>second last</p> Signup and view all the answers

    Match the deletion tasks with their corresponding actions:

    <p>Delete the first node = Update last-&gt;next pointer to skip head Delete a specific node = Use curr and prev pointers Delete the last node = Find the second last node Searching in the list = Traverse until the value is found or return to start</p> Signup and view all the answers

    What is returned after deleting a node from a circular linked list?

    <p>The updated last pointer.</p> Signup and view all the answers

    If a circular linked list has only one node and that node is deleted, the last pointer is set to a valid node.

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

    Searching in a circular linked list involves starting at a given node and __________ until the target value is found.

    <p>traversing the list</p> Signup and view all the answers

    Study Notes

    Data Structure - "Stack"

    • A data structure is a way of arranging data on a computer for efficient access and updating.
    • Linear Data Structure: Data elements arranged sequentially, with each connected to its previous and next elements.
    • Examples: Array, stack, queue, linked list.
    • Static Data Structure: Fixed memory size. Easier to access elements.
    • Example: Array
    • Dynamic Data Structure: Size not fixed. Can be updated randomly during runtime. Efficient memory usage.
    • Examples: Queue, stack
    • Non-linear Data Structure: Data elements not arranged sequentially. Not traversed in a single run.
    • Examples: Trees, graphs
    • Stack: Linear data structure where insertion and removal of elements happen at the same end (top of the stack).
    • Follows LIFO (Last-In, First-Out) principle.

    Introduction to Stack

    • The element inserted last is the first one to be removed.
    • To implement a stack, maintain a pointer to the top of the stack.
    • Key Differences between Arrays and Stacks
    • Stacks are limited-access data structures.
    • Arrays don't have the LIFO principle.

    Stack Operations

    • push(): Adds an element to the top of the stack.
    • pop(): Removes an element from the top of the stack.
    • top(): Returns the top element of the stack without removing it.
    • isEmpty(): Checks if the stack is empty.
    • size(): Returns the number of elements in the stack.

    Classification of Data Structures

    • Static
    • Dynamic
    • Linear
    • Non-linear

    Algorithm for Push Operation

    • Check if the stack is full.
    • If it is full, then it's a stack overflow.
    • Otherwise, increment top(top = top + 1) and insert the new value at the top position.
    • Continue pushing elements until the stack capacity is reached.

    Algorithm for Pop Operation

    • Check if the stack is empty.
    • If it's empty, then it's a stack underflow.
    • Otherwise, take the value at the top.
    • Decrement the top (top = top - 1).
    • Return the value that was stored at the top.

    Types of Stacks

    • Fixed Size Stack
    • Dynamic Size Stack

    Algorithm for isFull Operation

    • Check if the top equals capacity - 1
    • If true, return true, otherwise, return false

    Algorithm for isEmpty Operation

    • Check if top equals -1
    • If true, return true, otherwise, return false

    Algorithm for Top Operation

    • Check if the stack is empty.
    • If it is empty, print "Stack is empty".
    • Otherwise, return the element stored at index top.

    Array

    • Collection of elements of the same data type stored at contiguous memory locations.
    • Position of each element calculated with an offset to a base value.
    • Base value is index 0.
    • Size is fixed in C language - cannot be changed after creation. (Static Array)

    Types of Arrays

    • Static Array
    • Dynamic Array

    Implementation of Stack Using Array

    • Initialize an array.
    • Treat one end of the array as the top of the stack.
    • Implement push, pop, peer operations.

    Advantages of Array Implementation

    • Easy to implement
    • Memory is saved

    Disadvantages of Array Implementation

    • Not dynamic - size is fixed at compile time.

    Trees

    • Hierarchical data structure composed of nodes.
    • Topmost node is the root.
    • Nodes below are child nodes.
    • Child nodes can have multiple child nodes, forming a recursive structure.

    Technical Definition of a Tree

    • A connected acyclic undirected graph.
    • One unique path between any node pairs.
    • Number of vertices (n) - 1 = number of edges

    Properties of a Tree

    • Number of edges: A tree with N nodes has N - 1 edges.
    • Depth of a node: The number of edges in the path from the root to the node.
    • Height of a node: The length of the longest path from the node to a leaf node in the tree.
    • Height of the Tree: Length of the longest path from the root to a leaf.
    • Degree of a node: The number of children of a node. A leaf node has a degree of 0.

    Types of Trees

    • Binary Tree
    • Ternary Tree
    • N-ary Tree (Generic Tree)

    Properties of Binary Tree

    • Each node can have a maximum of two children.
    • Full binary tree has either 0 or 2 children for each internal node
    • Complete binary tree has elements in a sequential manner.
    • Perfect Binary Tree: All internal nodes have exactly two children; all leaf nodes are at the same level.
    • Degenerate Binary tree each node can have a maximum of one child.

    Balanced Binary Tree

    • Height of left and right subtree differ by 0 or 1

    Application of Tree Data Structure

    • File Systems
    • Data Compression
    • Compiler Design
    • Database Indexing

    Graph

    • Non-linear data structure consisting of vertices and edges.
      • Vertices (nodes)
      • Edges (line/arcs) connecting vertices

    Graph Representations

    • Adjacency Matrix
    • Adjacency List

    Adjacency Matrix

    • 2D matrix (n x n)
    • 1 indicates an edge, 0 if no edge.

    Adjacency List

    • Array of lists.
    • Each index represents a vertex
    • Contains a list of adjacent vertices for that vertex.

    Breadth-First Search (BFS)

    • Traverses a graph level-by-level.
    • Uses a queue data structure.
    • Processes all the nodes at a level before moving to the next level.
    • Ensures that each vertex is visited once.

    Depth First Search (DFS)

    • Explores the graph as deeply as possible along each branch before backtracking to other branches.
    • Uses a stack data structure.
      • Nodes are processed in a LIFO (last-in-first-out) manner.

    Applications of BFS

    • Finding Shortest Path
    • Peer-to-peer networks
    • Web Crawling
    • Garbage collection
    • Computing maximum flow

    Applications of DFS

    • Topological sorting
    • Cycle detection
    • Solving puzzles
    • Bipartite check

    Priority Queue

    • A data structure that maintains elements in a way that the element with the highest priority is removed first.
    • Useful in cases where elements need to be processed based on their priority.

    Types of Priority Queue

    • Ascending Order Priority Queue
    • Descending Order Priority Queue

    Operations of Priority Queue

    • enQueue: Inserting an element into a priority queue.
    • deQueue: Removing the highest priority element from a priority queue.
    • peek: Getting the highest priority element without removing it.

    Definitions

    • Graph: A graph is a data structure that consists of vertices (or nodes) and edges connecting pairs of vertices. Graphs can be used to model many real world problems (e.g. social networks, road maps, etc.)
    • Vertex: A vertex, also known as a node, is a fundamental unit of a graph. It is often represented as a point, circle or a labeled entity.
    • Edge: An edge is a connection/link between two vertices
    • Directed Graph: In a directed graph, the edges are oriented; they specify a direction of traverse between the vertices.
    • Undirected Graph: In an undirected graph edges are not oriented, there is no direction of traverse.

    Dijkstra's Algorithm

    • Finds the shortest path between a source vertex and all other vertices in a graph.

    Kruskal's Algorithm

    • Finds the minimum spanning tree (MST).

    Hashing

    • Process of generating a value from text using a hash function.
    • Maps a significant number or string to a small integer.
    • The hash value can be used to locate data quickly in a hash table.

    Types of Hash Function

    • Division
    • Mid-square

    Collision Resolution Techniques

    • Separate Chaining (Open Hashing)
    • Open Addressing (Closed Hashing): Linear probing, Quadratic probing, and Double hashing.

    Studying That Suits You

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

    Quiz Team

    Related Documents

    DSA Notes III Sem -1 PDF

    Description

    Test your knowledge on fundamental concepts of data structures with this quiz. It covers topics like stacks, linked lists, and binary trees, providing a mix of theoretical and practical questions. Challenge yourself and see how well you understand these crucial programming concepts!

    More Like This

    Use Quizgecko on...
    Browser
    Open
    Browser
    Browser