DSA FINAL LONG QUIZ

tree data structure

It is a collection of nodes that are

connected by edges and has a hierarchical relationship

between the nodes

root

topmost node of the tree is called the __

child nodes.

the nodes below it are called the __

True

The data in a tree are not stored in a sequential manner i.e.,

they are not stored linearly. T/F

predecessor

The node which is a

__ of a node is called the

parent node of that node.

immediate successor

The node which is the

__ of a node is

called the child node of that node

Leaf Node or External Node:

The

nodes which do not have any child

nodes are called __

siblings.

Children of the same parent

node are called ___

Level of node

The count of edges

on the path from the root node to

that node. The root node has level 0.

Internal node:

A node with at least

one child is called__

Subtree:

Any node of the tree along

with its descendant.

Number of edges:

An edge can be defined as the connection between two

nodes.

Depth of a node:

is defined as the length of the path from

the root to that node.

Height of a node:

can be defined as the length of the

longest path from the node to a leaf node of the tree

Height of the Tree

is the length of the longest path from

the root of the tree to a leaf node of the tree

A general tree

is a tree where each node may

have zero or more children (a binary tree is a

specialized case of a general tree).

General trees

are used to model applications

such as file systems.

Forest tree

can be defined as the set of disjoint trees

which can be obtained by deleting the root node and

the edges which connects root node to the first level

node

Tournament tree

_ are used to record the winner of

the match in each round being played between

two players.

selection

tree or winner tree

Tournament tree can also be called as

Expression trees

_ are used to evaluate the simple

arithmetic expressions

General trees

__ are unordered tree data

structures where the root node has

minimum 0 or maximum ‘n’ subtrees.

Binary Trees

__ are general trees in which

the root node can only hold up to

maximum 2 subtrees

A full binary tree

is a binary tree

type where every node has either

0 or 2 child nodes

A complete binary tree

is a binary tree

type where all the leaf nodes must be on

the same level. However, root and

internal nodes in a complete binary tree

can either have 0, 1 or 2 child nodes

A perfect binary tree

is a binary tree

type where all the leaf nodes are on

the same level and every node

except leaf nodes have 2 children

Tree traversal

is the process of visiting each node in the tree exactly once.

IN-ORDER TRAVERSAL

Algorithm:

▪ Step 1 − Recursively traverse left subtree.

▪ Step 2 − Visit root node.

▪ Step 3 − Recursively traverse right subtree.

PRE-ORDER TRAVERSAL

Algorithm:

▪ Step 1 − Visit root node.

▪ Step 2 − Recursively traverse left subtree.

▪ Step 3 − Recursively traverse right subtree.

POST-ORDER TRAVERSAL

Algorithm:

▪ Step 1 − Recursively traverse left subtree.

▪ Step 2 − Recursively traverse right subtree.

▪ Step 3 − Visit root node.

D → E → B → F → G → C → A

less

The data in the Binary Search Trees (BST) is always stored in such a way

that the values in the left subtree are always __ than the values in the

root node and the values in the right subtree are always greater than the

values in the root node, i.e. left subtree < root node ≤ right subtree.

greater

The data in the Binary Search Trees (BST) is always stored in such a way

that the values in the left subtree are always less than the values in the

root node and the values in the right subtree are always _ than the

values in the root node, i.e. left subtree < root node ≤ right subtree.

self-balancing,

AVL trees are ___ which means that the tree height is kept to a minimum so that a

very fast runtime is guaranteed for searching, inserting and deleting nodes, with time

complexity O(logn)O(logn)

AVL Trees

__ do rotation operations in addition, to keep the tree balance.

difference

A node's balance factor is the __ in subtree heights.

True

If the balance factor is less than -1, or more than 1, for one or more nodes

in the tree, the tree is considered not in balance, and a rotation operation is

needed to restore balance T/F

Graphs

_ are data structures that consist of nodes or

vertices linked by edges.

vertices(V) and a set of edges(E)

More formally a Graph is composed of a set of

__

G(V, E).

The graph is denoted by _

Nodes/Vertices:

Vertices are the fundamental units

of the graph. Sometimes, vertices are also known as

vertex or nodes. Every node/vertex can be labeled or

unlabelled

Edges/Arcs

Edges are drawn or used to connect two

nodes of the graph. It can be ordered pair of nodes in

a directed graph. Edges can connect any two nodes

in any possible way. There are no rules. Sometimes,

edges are also known as arcs. Every edge can be

labelled/unlabelled.

no direct

If two nodes are not connected by an edge, that means that there is __ connection between

them

= Total number of vertices (nodes) in the graph

|V|

|E|

= Total number of connections (edges) in the graph

directed graphs

In __, edges have a

direction. They go from one node to

another, and there is no way to return to

the initial node through that edge.

Directed Graph.

undirected

In this type of graph, edges are

__ (they do not have a specific

direction). Think of undirected edges as

two-way streets. You can go from one

node to another and return through that

same “path”

weighted graphs

In __, each edge has a value

associated with it (called weight). This

value is used to represent a certain

quantifiable relationship between the nodes

they connect

unweighted graphs

__ do not

have weights associated with their

edges. An example of this type of graph

can be found in social networks, where

edges represent the connection between

two users. The connection cannot be

quantified. Therefore, the edge has no

weight.

null

A graph is known as a null__ graph if there

are no edges in the graph.

Trivial Graph

Graph having only a single vertex, it is

also the smallest graph possible.

Undirected Graph

A graph in which edges do not have any

direction. That is the nodes are unordered

pairs in the definition of every edge.

Directed Graph

A graph in which edge has direction. That is

the nodes are ordered pairs in the definition

of every edge

connected

The graph in which from one node we can

visit any other node in the graph is known as

a __ graph

disconnected graph

The graph in which at least one node is not

reachable from a node is known as a

_

regular graph.

The graph in which the degree of every vertex

is equal to K is called K _

Complete Graph

The graph in which from each node there is

an edge to each other node.

Cycle Graph

▪ The graph in which the graph is a cycle in

itself, the degree of each vertex is 2

Cyclic Graph

▪ A graph containing at least one cycle is

known as a Cyclic graph.

Directed Acyclic Graph

▪ A Directed Graph that does not contain any

cycle

Bipartite Graph

▪ A graph in which vertex can be divided into

two sets such that vertex in each set does not

contain any edge between them

Trees

_ are the restricted types of graphs, just

with some more rules. Every tree will always

be a graph but not all graphs will be

trees

Adjacency Matrix

▪ In this method, the graph is stored in

the form of the 2D matrix where rows

and columns denote vertices.

Adjacency List

▪ This graph is represented as a

collection of linked lists. There is an

array of pointer which points to the

edges connected to that vertex.