Linked list/ Trees and graphs

51問 • 1年前

問題一覧

is also one of the data structures that represent hierarchical data. is a nonlinear hierarchical data structure that consists of nodes connected by edges.

Tree

an entity that contains a key or value and pointers to its child.

Node

The last nodes of each path are called “___________ that do not contain a link/pointer to child nodes.

leaf nodes or external nodes

The node having at least a child node is called an _______.

internal node

It is the link between any two nodes.

Edge

It is the topmost node of a tree.

Root

the number of edges from the node to the deepest leaf (ie. the longest path from the node to a leaf node).

Height of a Node

is the number of edges from the root to the node.

Depth of a Node

is the height of the root node or the depth of the deepest node.

Height of a Tree

is the total number of branches of that node.

Degree of a Node

A collection of disjoint trees is called a forest.

True

A tree data structure in which each parent node can have at most two children.

Binary Tree

Each node of a binary tree consists of three items: data item address of left child address of right child

True

is a special type of binary tree in which every parent node/internal node has either two or no children

Full binary tree

a type of binary tree in which every internal node has exactly two child nodes and all the leaf nodes are at the same level.

Perfect binary tree

is just like a full binary tree, but with two major differences

Complete binary tree

is the tree having a single child either left or right.

Degenerate or Pathological Tree

is a pathological/degenerate tree in which the tree is either dominated by the left nodes or the right nodes.

Skewed Binary Tree

there are two types of skewed binary tree: left-skewed binary tree and right-skewed binary tree.

True

It is a type of binary tree in which the difference between the height of the left and the right subtree for each node is either 0 or 1.

Balanced Binary Tree

A data structure that quickly allows us to maintain a sorted list of numbers. It is called a binary tree because each tree node has a maximum of two children.

Binary search tree

A self-balancing binary search tree in which each node maintains extra information called a balance factor whose value is either -1, 0 or +1.

AVL tree

AVL tree got its name after its inventor Georgy Adelson-Velsky and Landis.

True

A special type of self-balancing search tree in which each node can contain more than one key and can have more than two children. It is a generalized form of the binary search tree. It is also known as a height-balanced m-way tree.

B-Tree

that refers to the process of visiting, verifying, and updating each node in a tree data structure just once. The order in which you examine the nodes of the tree is used to classify these traversals. 1. DFS (Depth First Search) 2. BFS (Breadth First Search)

tree Traversals

is a method of traversing or searching data structures composed of trees or graphs. Three orders execute tree traversal under this depth-first search algorithm. (a) In-order (Left, Root, Right): 4 2 5 1 3 (b) Pre-order (Root, Left, Right): 1 2 4 5 3 (c) Post-order (Left, Right, Root): 4 5 2 3 1

Depth First Search DFS

is a vertex-based method for determining the shortest path in a graph. It employs a queue data structure, where first in, it follows first out. , it visits one vertex and marks it at the time, after which it sees and queues its neighbors.

Breadth First or Level Order Traversal (BFS)

is a non-linear data structure. It contains a set of points known as nodes (or vertices) and a set of links known as edges (or Arcs).

Graph

is a collection of vertices and arcs in which vertices are connected with arcs.

Graph

Graph is a collection of nodes and edges in which nodes are connected with edges.

True

The interconnected objects are represented by points termed as vertices, and the links that connect the vertices are called _____

edges

Two node or vertices are adjacent if they are connected to each other through an edge.

Adjecency

represents a sequence of edges between the two vertices

Path

is represented using a matrix of size total number of vertices by a total number of vertices.

Adjacency matrix

is represented using a matrix of size total number of vertices by a total number of edges.

Incidence Matrix

The graph G=(V, E) is called a _______ if the number of vertices and edges in the graph is interminable.

Infinite graph

A graph G= (V, E) it contains only a single vertex and no edges.

Trivial Graph

If each pair of nodes or vertices in a graph G=(V, E) has only one edge, it is a simple graph. As a result, there is just one edge linking two vertices, depicting one-to-one interactions between two elements.

Simple graph

If there are numerous edges between a pair of vertices in a graph G= (V, E), the graph is referred to as a multigraph. There are no self-loops.

multi graph

It's a reworked version of a trivial graph. If several vertices but no edges connect them, a graph G= (V, E)

Null graph

If a graph G= (V, E) is also a simple graph. Using the edges, with n number of vertices must be connected. It's also known as a full graph because each vertex's degree must be n-1.

Complete graph

If a graph G= (V, E) contains a self-loop besides other edges.

Pseudo Graph

Each node of the graph is represented as

Vertex

represents a path between two vertices or a line between two vertices.

edge

is a bidirectional edge. If there is undirected edge between vertices A and B then edge (A , B) is equal to edge (B , A).

Undirected Edge

is a unidirectional edge. If there is directed edge between vertices A and B then edge (A , B) is not equal to edge (B , A).

Directed Edge

is an edge with value (cost) on it.

Weighted Edge

Algorithm In-order (tree)

Step 1 − Recursively traverse left subtree. Step 2 − Visit root node. Step 3 − Recursively traverse right subtree.

Algorithm Pre-order (tree)

Step 1 − Visit root node. Step 2 − Recursively traverse left subtree. Step 3 − Recursively traverse right subtree.

Algorithm Post-order (tree)

Step 1 − Recursively traverse left subtree. Step 2 − Recursively traverse right subtree. Step 3 − Visit root node.

Each node of a binary tree consists of three items: data item address of left child address of right child

true

Data Structure (history)

iam noone · 64問 · 1年前

Data Structure (history)