m2 Flashcards by Zeri Rondilla

How do you remove data from a singly linked list?

You can only remove the data in the middle of the list.

You can only remove the last data from the list.

You can only remove the first data from the list.

You can remove the first data, last data, or any data in the list by adjusting the pointers of the respective nodes.

How well did you know this?

Not at all

Perfectly

What are the operations used in linked list structures?

Traversing the list, inserting data, removing data, and retrieving data.

Sorting the list, merging lists, splitting the list, and reversing the list.

Adding elements to the list, updating elements in the list, and searching for elements in the list.

Finding the maximum element, finding the minimum element, and finding the length of the list.

Traversing the list, inserting data, removing data, and retrieving data.

How well did you know this?

Not at all

Perfectly

How do you retrieve data from a singly linked list?

Sort the list and compare the data field of each node to the value being searched for.

Reverse the list and compare the data field of each node to the value being searched for.

Skip every other node and compare the data field of each node to the value being searched for.

Traverse the list and compare the data field of each node to the value being searched for.

How well did you know this?

Not at all

Perfectly

How do you insert data into a singly linked list?

Always insert the new data in between the first and second nodes of the list.

Always insert the new data at the beginning of the list.

Always insert the new data at the end of the list.

If the list is empty, create the first node. Otherwise, find the right position to insert the new data (beginning, end, or in between nodes)`

If the list is empty, create the first node. Otherwise, find the right position to insert the new data (beginning, end, or in between nodes).

How well did you know this?

Not at all

Perfectly

What are the disadvantages of using a circular linked list?

It requires more complex implementation of operations on linked list structures.

It has limited functionality compared to other linked list structures.

It occupies more memory than other linked list structures.

It has slower traversal compared to other linked list structures

It requires more complex implementation of operations on linked list structures.

How well did you know this?

Not at all

Perfectly

How do you traverse a singly linked list?

Starting from the head, check if the next pointer is null. If not, move to the next node until the end of the list is reached.

Starting from a random position, check if the previous or next pointer is null. If not, move to the previous or next node depending on the condition.

Starting from the tail, check if the previous pointer is null. If not, move to the previous node until the start of the list is reached.

Starting from the middle, check if the previous or next pointer is null. If not, move to the previous or next node depending on the condition.

Starting from the head, check if the next pointer is null. If not, move to the next node until the end of the list is reached.

How well did you know this?

Not at all

Perfectly

How do you traverse and retrieve data from a circular linked list?

Skip every other node and compare the data field of each node to the value being searched for.

Reverse the list and compare the data field of each node to the value being searched for.

Sort the list and compare the data field of each node to the value being searched for.

Perform similar operations as with a singly linked list, but ensure the termination condition for traversal considers the circular nature of the list.

How well did you know this?

Not at all

Perfectly

What makes a doubly linked list different from a singly linked list?

A doubly linked list has a circular structure.

A doubly linked list allows bidirectional traversal.

A doubly linked list has three fields: data, previous, and next pointer.

A doubly linked list contains a reference to both the previous and next elements in the list.

How well did you know this?

Not at all

Perfectly

What is a singly linked list?

A data structure that consists of two fields: data and previous pointer.

A data structure that consists of a sequence of elements, each containing a reference to the previous element.

A data structure that consists of a sequence of elements, each containing a reference to the next element.

A data structure that contains a reference to both the previous and next elements.

A data structure that consists of a sequence of elements, each containing a reference to the next element.

How well did you know this?

Not at all

Perfectly

What are the advantages of using a circular linked list?

It uses less memory than other linked list structures.

It provides easy manipulation of the pointers and efficient searching.

It allows for faster insertion and deletion operations compared to other linked list structures.

It guarantees constant time complexity for all operations.

It provides easy manipulation of the pointers and efficient searching.

How well did you know this?

Not at all

Perfectly

What is the purpose of converting an infix expression to postfix notation using a stack?

To reverse the order of the operands and operators

To convert numbers from decimal to binary notation

To evaluate arithmetic expressions and handle operator precedence

To group the operands and operators in parentheses

To evaluate arithmetic expressions and handle operator precedence

How well did you know this?

Not at all

Perfectly

What are some of the applications that can be solved using Stack data structure?

Expression Evaluation, Function Call Stack, Undo Operations, Backtracking, Memory Management

Sorting Algorithms, Binary Search, Linked Lists

Looping, Conditional Statements, File Handling

Networking, Database Management, Artificial Intelligence

Expression Evaluation, Function Call Stack, Undo Operations, Backtracking, Memory Management

How well did you know this?

Not at all

Perfectly

Which operations can be used in the implementation of Stack data structure?

Append and Prepend

Push and Pop

Insert and Delete

Sort and Search

Push and Pop

How well did you know this?

Not at all

Perfectly

In a Stack data structure, where are elements inserted and removed?

Middle of the stack

Random positions in the stack

Bottom of the stack

Top of the stack

How well did you know this?

Not at all

Perfectly

Which notation places the operator before the operands in an arithmetic expression?

Postfix notation

Polish notation

Infix notation

Prefix notation

How well did you know this?

Not at all

Perfectly

What is the principle behind Stack data structure?

Last-in-First-Out (LIFO)

Random

First-in-First-Out (FIFO)

Priority-based

Last-in-First-Out (LIFO)

How well did you know this?

Not at all

Perfectly

What is the application of Stacks in memory management?

Managing activation records during program execution

Displaying graphics on computer screens

Storing data on hard disks

Accessing data from databases

Managing activation records during program execution

How well did you know this?

Not at all

Perfectly

What is the term used for inserting elements into a stack?

Insert operation

Append operation

Push operation

Add operation

Push operation

How well did you know this?

Not at all

Perfectly

Which data structure can be used to implement a Stack?

Arrays and Linked Lists

Queues and Graphs

Hash Tables and Trees

Sets and Matrices

Arrays and Linked Lists

How well did you know this?

Not at all

Perfectly

What is the term used for deleting elements from a stack?

Remove operation

Extract operation

Pop operation

Delete operation

Pop operation

How well did you know this?

Not at all

Perfectly

What is the function of the IsNull() operation in the Queue data structure?

Returns the size of the Queue

Evaluates if the queue is empty

Retrieves the element from the front of the Queue without removing it

Checks if the Queue is full or not

Evaluates if the queue is empty

How well did you know this?

Not at all

Perfectly

Which operation is used to store elements in the Queue?

Size

Peek

Dequeue

Enqueue

How well did you know this?

Not at all

Perfectly

Which operations can be used in the implementation of the Queue data structure?

Push and Pop

Enqueue and Dequeue

Sort and Search

Insert and Delete

Enqueue and Dequeue

How well did you know this?

Not at all

Perfectly

What is the function of the Peek() operation in the Queue data structure?

Get the element from the front of the Queue without removing it

Enqueue the element into the Queue

Dequeue the element from the Queue

Returns the size of the Queue

Get the element from the front of the Queue without removing it

How well did you know this?

Not at all

Perfectly

What is the function of the Size() operation in the Queue data structure? Retrieves the element from the front of the Queue without removing it Inserts the element into the Queue Checks if the Queue is empty or not Returns the size of the Queue

Returns the size of the Queue

What is the function of the IsFull() operation in the Queue data structure? Checks if the Queue is full or not Checks if the Queue is empty or not Returns the size of the Queue Retrieves the element from the front of the Queue without removing it

Checks if the Queue is full or not

Which operation is used to remove elements from the Queue? Size Enqueue Peek Dequeue

Dequeue

What is the principle behind the Queue data structure? Random access First In First Out (FIFO) Last In First Out (LIFO) Stack

First In First Out (FIFO)

What are some applications that can be solved using the Queue data structure? Sorting and Searching Job scheduling and Handling resource sharing Hashing and String Matching Graph Traversal and Shortest Path Finding

Job scheduling and Handling resource sharing

What are some of the variations of the Queue data structure? Circular Queue and Priority Queue Binary Tree and Heap Graph and Hash Table Stack and Linked List

Circular Queue and Priority Queue

What is a heap tree? A binary tree with only leaf nodes A binary tree with no nodes A complete binary tree where the key at the root node is either the greatest (Max-Heap) or the smallest (Min-Heap) among all its children A binary tree with only root nodes

A complete binary tree where the key at the root node is either the greatest (Max-Heap) or the smallest (Min-Heap) among all its children

What is the depth of a tree? The highest level of the tree The number of leaf nodes in the tree The number of edges in the tree The number of nodes in the tree

The highest level of the tree

What is a tree data structure? A finite collection of data arranged in a hierarchical fashion A linear collection of data arranged in a hierarchical fashion A random collection of data arranged in a hierarchical fashion An infinite collection of data arranged in a hierarchical fashion

A finite collection of data arranged in a hierarchical fashion

What is a subtree? A tree with only leaf nodes A tree with only root nodes A complete tree within the main tree A tree with no nodes

A complete tree within the main tree

What is the degree of a node? The value of the node The parent of the node The level of the node The number of child nodes

The number of child nodes

What is a leaf node? A node with no child nodes A node with a value of 0 A node with multiple child nodes There is no such thing as a leaf node

A node with no child nodes

What is a binary search tree (BST)? A binary tree with no sub-trees A binary tree with only one node An ordered binary tree where elements in the left sub-tree are less than the root, and elements in the right sub-tree are greater than or equal to the root A binary tree with no order

An ordered binary tree where elements in the left sub-tree are less than the root, and elements in the right sub-tree are greater than or equal to the root

What is the root node of a tree? There is no root node The middle node The topmost node The bottommost node

The topmost node

What is a binary tree? A tree with only one node A tree where each node can have at most 2 children A tree with no children A tree with unlimited children

A tree where each node can have at most 2 children

What is an AVL tree? A binary search tree with no balance factor A binary search tree with infinite nodes A binary search tree with no heights assigned A height-balanced binary search tree where each node is associated with a balance factor that equals the height of its left sub-tree minus the height of its right sub-tree

A height-balanced binary search tree where each node is associated with a balance factor that equals the height of its left sub-tree minus the height of its right sub-tree

What is a skewed binary tree? A binary tree in which the height is the maximum number of nodes A binary tree in which all nodes have only one child A binary tree in which the height is always equal to the number of nodes A binary tree in which the height is the maximum number of branches plus 1

A binary tree in which the height is the maximum number of branches plus 1

What is a binary tree? A tree in which the left subtree always has smaller values A tree in which every node has exactly two children A tree in which the right subtree always has larger values A tree in which no node can have more than two subtrees

A tree in which no node can have more than two subtrees

What is an almost complete binary tree? In the last level, the nodes will be as far left as possible and all other levels have maximum nodes A binary tree in which nodes are evenly distributed across all levels A binary tree in which the height is always equal to the number of nodes A binary tree in which all nodes have two children

In the last level, the nodes will be as far left as possible and all other levels have maximum nodes

What does In-order traversal mean? Traverse the right subtree first, then the root, and finally the left subtree Traverse the root first, then the right subtree, and finally the left subtree Traverse the left subtree first, then the root, and finally the right subtree Traverse the root first, then the left subtree, and finally the right subtree

Traverse the left subtree first, then the root, and finally the right subtree

What does Pre-order traversal mean? Traverse the right subtree, then left subtree, and finally root Traverse the left subtree, then right subtree, and finally root Traverse the right subtree, then root, and finally the left subtree Traverse the root first, then left subtree, and finally right subtree

Traverse the root first, then left subtree, and finally right subtree

What is a strictly binary tree? The degree of any node in the binary tree will be either 0 or 2 The degree of any node in the binary tree will be either 1 or 3 The degree of any node in the binary tree will be either 2 or 3 The degree of any node in the binary tree will be either 1 or 2

The degree of any node in the binary tree will be either 0 or 2

What is a complete binary tree? A binary tree that contains exactly 2^d nodes at each level between level 0 and d A binary tree in which the height is the maximum number of nodes A binary tree in which the height is the maximum number of levels A binary tree in which all nodes have exactly one child

A binary tree that contains exactly 2^d nodes at each level between level 0 and d

What are the characteristics of a binary tree data structure? A node can only have a right subtree A node can only have a left subtree A node always has exactly two subtrees A node can have zero, one, or two subtrees

A node can have zero, one, or two subtrees

What does Post-order traversal mean? Traverse the root first, then the right subtree, and finally the left subtree Traverse the right subtree first, then the left subtree, and finally the root Traverse the root first, then the left subtree, and finally the right subtree Traverse the left subtree first, then the right subtree, and finally the root

Traverse the left subtree first, then the right subtree, and finally the root

How do we traverse a binary tree? Pre-order, In-order, Post-order Only In-order traversal Only Post-order traversal Only Pre-order traversal

Pre-order, In-order, Post-order

What is the disadvantage of binary search? Requires additional memory for storing and manipulating the tree structure Not suitable for large datasets Requires the array to be sorted and requires elements to be comparable Slow searching process in comparison to arrays and linked lists

Requires the array to be sorted and requires elements to be comparable

How is a node searched in a binary search tree? The search is performed by traversing the tree in breadth-first order Starting from the root, the key value is compared with the node's value and the search continues in the left subtree if it's less or in the right subtree if it's greater Only the nodes in the lower levels of the tree are considered for search Starting from any leaf node, the key value is compared with the node's value and the search continues until the root is reached

Starting from the root, the key value is compared with the node's value and the search continues in the left subtree if it's less or in the right subtree if it's greater

What are the characteristics of a binary search tree? The values in the left subtree are greater than the root, and the values in the right subtree are less than the root The values in the left subtree are less than the root, and the values in the right subtree are greater than the root The tree has a balanced structure with equal number of nodes in each level The tree has a height of log(n), where n is the number of nodes

The values in the left subtree are less than the root, and the values in the right subtree are greater than the root

What are the operations that can be performed on a binary search tree? Finding the median of the elements, computing the sum of all elements Balancing the tree, merging two trees into one Sorting the tree in ascending order, finding the height of the tree Inserting a node, searching for a node, deleting a node, traversing the tree

Inserting a node, searching for a node, deleting a node, traversing the tree

What are some applications of binary search trees? Sorting elements in descending order Performing arithmetic operations on large numbers Building algorithms for machine learning, searching in computer graphics, searching in databases Storing and retrieving data from cache memor

Building algorithms for machine learning, searching in computer graphics, searching in databases

What is the expected result of an in-order traversal of a binary search tree? The nodes are visited in descending order of their values The nodes are visited in ascending order of their values The nodes are visited in a pre-determined order based on their level in the tree The nodes are visited in a random order

The nodes are visited in ascending order of their values

What is a binary search tree (BST)? A type of tree used for sorting elements in ascending order A type of binary tree with specific ordering properties A type of tree used for storing data in a balanced manner A type of search algorithm that uses a binary approach

A type of binary tree with specific ordering properties

How is a new node inserted in a binary search tree? The value is always inserted as the root node The value is compared with the root and inserted in the left subtree if it's less or in the right subtree if it's greater The value is inserted randomly in any subtree The value replaces the current root node and becomes the new root

The value is compared with the root and inserted in the left subtree if it's less or in the right subtree if it's greater

How is a node deleted in a binary search tree? The node is removed and the height of the tree is adjusted accordingly The node is replaced with the maximum value from the right subtree The node is replaced with the minimum value from the left subtree The node is replaced with either the in-order predecessor or the in-order successor, depending on the case

The node is replaced with either the in-order predecessor or the in-order successor, depending on the case

What is the advantage of using a binary search tree? Efficient storage of elements in contiguous memory locations Efficient searching, insertion, and deletion operations Efficient retrieval of an element at a specific index Efficient sorting of elements in ascending order

Efficient searching, insertion, and deletion operations

Which case of imbalance in an AVL tree requires a single left rotation? LL (Left-Left Imbalance) RL (Right-Left Imbalance) LR (Left-Right Imbalance) RR (Right-Right Imbalance)

RR (Right-Right Imbalance)

Which case of imbalance in an AVL tree requires a double rotation? LL (Left-Left Imbalance) LR (Left-Right Imbalance) RL (Right-Left Imbalance) RR (Right-Right Imbalance)

LR (Left-Right Imbalance) / RL (Right-Left Imbalance)

What are the procedures to maintain a balanced BST? Add nodes randomly to balance the tree Perform rotations to balance the tree Remove all nodes with balance factor greater than 1 Sort the elements in the tree in ascending order

Perform rotations to balance the tree

What is the balance factor (BF) of a node in an AVL tree? The minimum height of the left and right subtrees The difference between the height of the left subtree and the height of the right subtree The sum of the heights of the left and right subtrees The maximum height of the left and right subtrees

The difference between the height of the left subtree and the height of the right subtree

What is an AVL tree? A tree with arbitrary balance factors A tree with only left subtrees A tree with no balance factor A self-balancing binary search tree

A self-balancing binary search tree

Which case of imbalance in an AVL tree requires a single right rotation? LR (Left-Right Imbalance) LL (Left-Left Imbalance) RR (Right-Right Imbalance) RL (Right-Left Imbalance)

LL (Left-Left Imbalance)

What are the forms of a BST that are not balanced? Perfect binary trees Full binary trees Complete binary trees Left-skewed and right-skewed trees

Left-skewed and right-skewed trees

What are the characteristics of a balanced binary search tree? The heights of the left and right subtrees are determined randomly The heights of the left and right subtrees differ at most by 1 for every node The heights of the left and right subtrees are always the same The heights of the left and right subtrees can differ by any amount

The heights of the left and right subtrees differ at most by 1 for every node

What are the possible balance factors for a node in an AVL tree? Show answer choices −1, 0, 1, or 2 0, 1, or 2 −2, −1, 0, or 1 −1, 0, or 1

−1, 0, or 1

Which case of imbalance in an AVL tree requires a double rotation? RR (Right-Right Imbalance) RL (Right-Left Imbalance) LR (Left-Right Imbalance) LL (Left-Left Imbalance)

RL (Right-Left Imbalance) / LR (Left-Right Imbalance)

What are the characteristics of a heap tree data structure? It is used in Prim's algorithm. It has a binary tree structure. It allows elements to be accessed in constant time. It has a heap property that states the data value of any parent node is greater than or equal to the data value of its children.

It has a heap property that states the data value of any parent node is greater than or equal to the data value of its children.

What is the heap property in a max-heap? The tree follows a complete binary tree structure. The data value of any parent node is greater than or equal to the data value of its children. The data value of any parent node is less than or equal to the data value of its children. The root of the tree contains the largest data element.

The data value of any parent node is greater than or equal to the data value of its children.

What does the empty function on the vector indicate in a heap tree implementation? It checks if the vector is in a valid state. It checks if the vector is full and no more elements can be added. It checks if the heap is empty. It checks if the heap is full and needs resizing.

It checks if the heap is empty.

What are the steps involved in inserting a new data element in a heap tree? Append the new data to the end of the tree. Replace the data of the last (rightmost) leaf node with the new data. Check if the tree is empty before inserting the new data. Insert the new data as the next node, check if it violates the heap property, and make necessary swaps if required.

Insert the new data as the next node, check if it violates the heap property, and make necessary swaps if required.

What are the operations on a heap tree? Traversal and searching of data elements. Modification and sorting of data elements. Creation and manipulation of data elements. Insertion and deletion of data elements.

Insertion and deletion of data elements.

What is the heap property in a min-heap? The root of the tree contains the smallest data element. The data value of any parent node is less than or equal to the data value of its children. The data value of any parent node is greater than or equal to the data value of its children. The tree follows a binary search tree structure.

The data value of any parent node is less than or equal to the data value of its children.

How is the root element deleted in a max-heap? Replace the data of the root node with that of the last (rightmost) leaf node and perform heapifyDown to maintain the heap property. Delete the last leaf node of the tree. Swap the root element with its largest child. Perform heapifyUp on the root node.

Replace the data of the root node with that of the last (rightmost) leaf node and perform heapifyDown to maintain the heap property.

What is an application of a heap tree? Sorting using heap sort. Accessing the minimum or maximum element in constant time. Implementing priority queues. Finding the minimum cost edge in the Prim's algorithm. All of the above.

All of the above.

What is the purpose of a vector in a heap tree implementation? It maintains the heap property by comparing the value at a given index with its children nodes. It adds a new element to the heap by pushing it to the back of the vector and calling heapifyUp. It maintains the heap property by comparing the value at a given index with its parent node. It stores elements and allows fast random access to any element.

It stores elements and allows fast random access to any element.

What is a heap data structure? A type of sorting algorithm. A linear arrangement that allows fast random access to any element. A special type of tree structure that follows a heap property. A data structure used to maintain the heap property.

A special type of tree structure that follows a heap property.

What are some operations that can be used in the implementation of a graph data structure? Add vertex, add edge, remove vertex, remove edge, search for a node, and traverse the graph Push, pop, enqueue, and dequeue Sort, merge, and search Insert, delete, and search

Add vertex, add edge, remove vertex, remove edge, search for a node, and traverse the graph

What are the terminologies used in a graph data structure? Nodes and pointers Vertices and edges Leaves and parents Indexes and elements

Vertices and edges

What is an undirected graph? A graph where each node is connected with all other nodes A graph where each vertex has an in-degree and an out-degree A graph where the edges have no direction A graph where the edges form an ordered pair

A graph where the edges have no direction

What is a graph data structure? A linear data structure used to store a collection of elements. A data structure that stores data in a hierarchical manner. A finite collection of interlinked data represented by a set of vertices and edges. A data structure used to implement stacks and queues.

A finite collection of interlinked data represented by a set of vertices and edges.

What is a complete graph? A graph with two or more disconnected graphs A graph where the edges have no direction A graph where every node is connected with all other nodes A graph with a cycle consisting of a single arc

A graph where every node is connected with all other nodes

What are two common graph traversal algorithms? Selection Sort and Bubble Sort Insertion Sort and Merge Sort Breadth First Search (BFS) and Depth First Search (DFS) Linear Search and Binary Search

Breadth First Search (BFS) and Depth First Search (DFS)

What are some applications that can be solved using a graph data structure? Performing mathematical calculations Finding shortest routes, planning computer networks, social networking, representing website structures Storing and retrieving data Searching and sorting data

Finding shortest routes, planning computer networks, social networking, representing website structures

How do we represent a graph in a solution? By using an array By using an adjacency matrix or an adjacency list By using a hash table By using a linked list

By using an adjacency matrix or an adjacency list

What is a path in a graph? A sequence of nodes that are followed in order to reach some terminal node from an initial node A cycle in the graph A complete graph with all nodes connected A set of adjacent vertices

A sequence of nodes that are followed in order to reach some terminal node from an initial node

What is a cycle in a graph? A path consisting of at least three vertices that starts and ends with the same vertex A graph where all nodes are connected with all other nodes A set of disjoint graphs A loop in the graph

A path consisting of at least three vertices that starts and ends with the same vertex

m2 Flashcards

(90 cards)