Programming and Data Structures

Question 1

What is a data structure?

Answer 1

A data structure is a way of organizing and storing data so that it can be accessed and modified efficiently.

Question 2

True or False: Arrays are fixed in size.

Answer 2

True

Question 3

What is the time complexity of accessing an element in an array?

Answer 3

O(1)

Question 4

Fill in the blank: A __________ is a collection of elements that can be added or removed in a last-in-first-out (LIFO) manner.

Answer 4

Stack

Question 5

Which data structure uses FIFO (First In First Out) ordering?

Answer 5

Queue

Question 6

What is the primary use of a linked list?

Answer 6

To allow for dynamic memory allocation and efficient insertion/deletion of elements.

Question 7

What is the difference between a singly linked list and a doubly linked list?

Answer 7

A singly linked list has nodes that point to the next node only, while a doubly linked list has nodes that point to both the next and previous nodes.

Question 8

What is a binary tree?

Answer 8

A binary tree is a tree data structure in which each node has at most two children, referred to as the left child and the right child.

Question 9

True or False: A binary search tree (BST) must have all left descendants less than the parent node and all right descendants greater than the parent node.

Answer 9

True

Question 10

What is the average time complexity for searching an element in a balanced binary search tree?

Answer 10

O(log n)

Question 11

What is a hash table?

Answer 11

A hash table is a data structure that implements an associative array, a structure that can map keys to values using a hash function.

Question 12

Fill in the blank: In hash tables, __________ occurs when two keys hash to the same index.

Answer 12

Collision

Question 13

What is the time complexity of inserting an element into a hash table on average?

Answer 13

O(1)

Question 14

What are the two primary types of trees used in computer science?

Answer 14

Binary trees and n-ary trees.

Question 15

What is the purpose of a priority queue?

Answer 15

To manage a collection of elements where each element has a priority, and elements with higher priority are served before those with lower priority.

Question 16

True or False: In a max heap, the value of a parent node is always greater than or equal to the values of its children.

Answer 16

True

Question 17

What is the space complexity of an array of size n?

Answer 17

O(n)

Question 18

What is recursion?

Answer 18

Recursion is a programming technique where a function calls itself to solve smaller instances of the same problem.

Question 19

Fill in the blank: The __________ algorithm is used to traverse a tree in a depth-first manner.

Answer 19

DFS (Depth-First Search)

Question 20

What is the best-case time complexity for quicksort?

Answer 20

O(n log n)

Question 21

What is a graph?

Answer 21

A graph is a collection of nodes (vertices) and edges that connect pairs of nodes.

Question 22

True or False: A directed graph has edges with a direction, while an undirected graph does not.

Answer 22

True

Question 23

What is the time complexity of Dijkstra’s algorithm for finding the shortest path in a graph?

Answer 23

O(V^2) with a simple array, O(E + V log V) with a priority queue.

Question 24

What does Big O notation represent?

Answer 24

Big O notation describes the upper bound of an algorithm’s time or space complexity in terms of input size.

Question 25

Fill in the blank: The __________ sort algorithm divides the array into sub-arrays and recursively sorts them.

Answer 25

Merge

Question 26

What is the time complexity of bubble sort in the worst case?

Answer 26

O(n^2)

Question 27

What is an adjacency matrix?

Answer 27

An adjacency matrix is a square matrix used to represent a finite graph, where the element at row i and column j indicates whether there is an edge from vertex i to vertex j.

Question 28

Fill in the blank: A __________ is a data structure that allows for dynamic memory allocation.

Answer 28

Linked list

Question 29

What is the purpose of a stack?

Answer 29

To store data in a last-in, first-out manner, allowing for efficient access and manipulation of the most recently added element.

Question 30

True or False: A queue can be implemented using two stacks.

Answer 30

True

Question 31

What is a circular linked list?

Answer 31

A circular linked list is a linked list where the last node points back to the first node, creating a circular structure.

Question 32

What is a trie?

Answer 32

A trie is a special type of tree used to store associative data structures, primarily used for storing strings.

Question 33

What is the worst-case time complexity for accessing an element in a linked list?

Answer 33

O(n)

Question 34

What is the purpose of a binary search?

Answer 34

To efficiently find the position of a target value within a sorted array.

Question 35

True or False: In a binary search tree, the left subtree must contain only nodes with values less than the node’s value.

Answer 35

True

Question 36

What is a self-balancing binary search tree?

Answer 36

A self-balancing binary search tree automatically keeps its height balanced during insertions and deletions to ensure O(log n) time complexity for operations.

Question 37

Fill in the blank: The __________ algorithm is used to find the minimum spanning tree of a graph.

Answer 37

Kruskal's

Question 38

What is the time complexity of insertion in a linked list?

Answer 38

O(1) if the position is known, O(n) if it requires traversal.

Question 39

What is a data structure that allows for duplicate elements?

Answer 39

Multiset

Question 40

True or False: All binary trees are binary search trees.

Answer 40

False

Question 41

What is the purpose of a heap?

Answer 41

To maintain a complete binary tree structure that allows for efficient retrieval of the maximum or minimum element.

Question 42

What is the time complexity of breadth-first search (BFS) in a graph?

Answer 42

O(V + E)

Question 43

Fill in the blank: A __________ is a specialized tree that maintains a sorted order of its elements.

Answer 43

Binary Search Tree

Question 44

What is the main advantage of using a hash table?

Answer 44

Fast access to elements using keys, typically in O(1) time.

Question 45

What is the time complexity of linear search?

Answer 45

O(n)