Brainscape's Knowledge GenomeTM

Browse over 1 million classes created by top students, professors, publishers, and experts.


See full index

Data Structures and Algorithms - Midterms > Lesson 6: Trees > Flashcards

Lesson 6: Trees Flashcards

1
Q

Tree is a __________ data structure. (choices: linear, non-linear)

A

non-linear

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

Tree imposes a __________ structure, on a collection of items

A

Hierarchial

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

collection of nodes

A

Tree

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

If not empty, a tree consists of: (clue: RSE)

A

node R (the ROOT)
zero or more non-empty SUBTREES
each subtree is connected by a directed EDGE from R

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

[Tree Terminologies]
—mother node of a tree structure
—does not have parent
—first node in hierarchical arrangement

A

Root

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

[Tree Terminologies]
—stores the data and its role is the same as in the linked list
—connected by the means of links with other nodes

A

Node

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

[Tree Terminologies] immediate predecessor of a node

A

Parent

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

[Tree Terminologies] When a predecessor of a node is parent then all successor nodes are called __________ nodes.

A

Child

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

[Tree Terminologies]
—connects the two nodes
—pointer to node in a tree structure

A

Link/Edge

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

[Tree Terminologies]
—locates at the end of the tree
—does not have any child

A

Leaf

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

[Tree Terminologies] The highest number of nodes that is possible in a way starting from the first node (ROOT) to a leaf node

A

Height

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

[Tree Terminologies] rank of tree hierarchy

A

Level

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

[Tree Terminologies] the level of the root node

A

Level 0

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

[Tree Terminologies] The child node of same parent

A

Sibling

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

[Tree Terminologies] Another term for sibling nodes

A

Brother nodes

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

[Tree Terminologies] The maximum number of children that exists for a node

A

Degree of a Node

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q

[Tree Terminologies] The node with degree zero

A

Terminal node

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
18
Q

[Tree Terminologies] number of successive edges from source node to destination node

A

Path length

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
19
Q

[Tree Terminologies] maximum level of any leaf of a tree

A

Depth

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
20
Q

[Tree Terminologies] group of disjoint trees

A

Forest

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
21
Q

any node that has at least one non-empty child

A

internal node

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
22
Q

Simplest form of tree

A

Binary Tree

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
23
Q

A binary tree consists of: (clue: NS)

A

NODE (root node)
SUBTREES (left and right)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
24
Q

A tree is binary if each node has a maximum of __________ branches.

A

Two

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
25
Q

When every non-leaf node in binary tree is filled with left and right sub-trees, the tree is called ____________

A

Strictly binary tree

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
26
Q

A tree in which each level of the tree is completely filled, except the bottom level

A

Complete binary tree

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
27
Q

Operations on Binary Tree (clue: CELRPSIDSCT)

A

Create
Empty
Lchild
Rchild
Parent/Father
Sibling
Insert
Deletion
Search
Copy
Tree Traversal

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
28
Q

[Operations on Binary Tree] create an empty binary tree

A

Create

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
29
Q

[Operations on Binary Tree] return true when binary tree is empty, else return false

A

Empty

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
30
Q

[Operations on Binary Tree] A pointer is returned to left child of a node, when a node is without left child, NULL pointer is returned

A

Lchild

31
Q

[Operations on Binary Tree] A pointer is returned to right child of a node, when a node is without left child, NULL pointer is returned

A

Rchild

32
Q

[Operations on Binary Tree] a pointer to father of a node is returned

A

Father/parent

33
Q

[Operations on Binary Tree] A pointer to brother of the node is returned or else NULL pointer is returned

A

Sibling

34
Q

[Operations on Binary Tree] to insert a node

A

Insert

35
Q

[Operations on Binary Tree] to delete a node

A

Deletion

36
Q

[Operations on Binary Tree] to search a given node

A

Search

37
Q

[Operations on Binary Tree] copy one tree to another

A

Copy

38
Q

Used to display/access the data in a tree in a certain order

A

Traversal of a Binary Tree

39
Q

In traversing, _____ sub-tree is always traversed after _____ sub-tree

A

right, left

40
Q

Three methods of traversing (clue: PIP)

A

Preorder Traversing
Inorder Traversing
Postorder Traversing

41
Q

[Methods of Traversing]
—Root-Left-Right
—Prefix expression

A

Preorder Traversing

42
Q

[Methods of Traversing]
—Left-Root-Right
—Infix expression

A

Inorder Traversing

43
Q

[Methods of Traversing]
—Left-Right-Root
—Postfix expression

A

Postorder Traversing

44
Q

Stores keys in the nodes in a way so that searching, insertion and deletion can be done efficiently

A

Binary Search Tree

45
Q

Left child should be _______ than the value of the root. (choices: greater than, less than, equal to)

A

Less than

46
Q

Right child should be _______ than the value of the root. (choices: greater than, less than, equal to)

A

Greater than or equal to

47
Q

balanced binary search tree in which balance factor of every node is either -1, 0 or +1

A

AVL Tree

48
Q

difference between the heights of the left and right subtrees of that node

A

Balance factor

49
Q

When was the AVL tree introduced and who introduced it?

A

1962
G.M. Adelson-Velsky, E.M. Landis.

50
Q

process of moving nodes either to left or to right to make the tree balanced

A

Rotation

51
Q

Two types of rotations (clue: SD)

A

Single Rotation
Double Rotation

52
Q

Rotations under Single Rotation

A

Single Left Rotation (LL Rotation)
Single Right Rotation (RR Rotation)

53
Q

Rotations under Double Rotation

A

Left Right Rotation (LR Rotation)
Right Left Rotation (RL Rotation)

54
Q

[Rotations] Every node moves one position to left from the current position

A

Single Left Rotation (LL Rotation)

55
Q

[Rotation] Every node moves one position to right from the current position

A

Single Right Rotation (RR Rotation)

56
Q

[Rotation] A sequence of single left rotation followed by a single right rotation

A

Left Right Rotation (LR Rotation)

57
Q

[Rotation] A sequence of single right rotation followed by a single left rotation

A

Right Left Rotation (RL Rotation)

58
Q

AVL Tree Operations (clue: SID)

A

Search
Insertion
Deletion

59
Q

A special tree-based data structure and is considered as a complete binary tree

A

Heap Tree

60
Q

Two types of heap (clue: MM)

A

Min-heap
Max-heap

61
Q

[Types of heap] the smallest element is the root of the tree and each node is greater than or equal to its parent

A

Min-heap

62
Q

[Types of heap] the largest element is the root of the tree and each node is less than or equal to its parent

A

Max-heap

63
Q

The common implementation of a heap data structure

A

Binary Heap

64
Q

Properties of binary heap

A

—A complete binary tree when all the levels are completely filled except possibly the last level and the last level has its keys as much left as possible
—Can be a min-heap or max-heap

65
Q

A binary heap is a complete _____ tree and can best be represented as an _____

A

binary, array

66
Q

Operations on Binary Heap (minimum heap) (clue: IDDEG)

A

Insert()
Delete()
decreasekey()
extractMin()
getMin()

Note: For maximum heap, the operations reverse accordingly.

67
Q

[Operations on Binary Heap (minimum heap)] Inserts a new key at the end of the tree. Depending on the value of the key inserted, the heap can be adjusted, without violating the heap property.

A

Insert()

Note: For maximum heap, the operations reverse accordingly.

68
Q

[Operations on Binary Heap (minimum heap)] Deletes a key.

A

Delete()

Note: For maximum heap, the operations reverse accordingly.

69
Q

[Operations on Binary Heap (minimum heap)] Decreases the value of the key. There might have the need to maintain the heap property when this operation takes place.

A

decreasekey()

Note: For maximum heap, the operations reverse accordingly.

70
Q

[Operations on Binary Heap (minimum heap)] Removes the minimum element from the min-heap. It needs to maintain the heap property after removing the minimum element.

A

extractMin()

Note: For maximum heap, the operations reverse accordingly.

71
Q

[Operations on Binary Heap (minimum heap)] Returns the root element of the min-heap.

A

getMin()

Note: For maximum heap, the operations reverse accordingly.

72
Q

Applications of Heaps (clue: HPGW)

A

Heapsort
Priority Queues
Graph algorithms
Worst-case complexity of quicksort algorithm can be overcome by using heap sort

73
Q

[Applications of Heaps] binary heap supports all the operations required for successfully implementing the priority queues in O(log n) time

A

Priority Queues

74
Q

An application of binary trees and priority queues

A

Huffman Coding

Data Structures and Algorithms - Midterms (6 decks)

Brainscape helps you reach your goals faster, through stronger study habits.
© 2024 Bold Learning Solutions. Terms and Conditions