Brainscape's Knowledge GenomeTM

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


See full index

Software engineering 2nd yr > DSALG > Flashcards

DSALG Flashcards

1
Q

Name the 3 linear data structures

A

Array, Linked list, Hash table

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

Name all the hierarchical data strucutres

A

Binary Tree
Binary Search Tree
AVL Tree
Splay Tree
Heap
2-3 Tree
B Tree

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

Name the 3 graphical data structure algorithms

A

Tree traversal(Breadth first and Depth first search)
Shortest Path Trees( Dijkstra’s algorithm)
Spanning Trees(Prim and Kruskals algorithm)

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

What are the 2 types of arrays

A

Sorted and unsorted arrays

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

What are the special cases of arrays

A

Stacks ADT, Queue ADT, Priority queue

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

What are the special cases of linked lists

A

Double linked list
Circularly linked lists
Skip list

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

What is a doubly linked list

A

A linked list in which every node has a forward and a backward link

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

What is a circularly linked list

A

A SLL in which the last node contains the
reference to the first node in the SLL

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

What is a skip list

A

A probabilistic data structure, based on parallel linked lists, with an improved efficiency

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

What is a Hash table

A

A searching tool that uses hashing for the time-space trade off

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

What are the special cases for a B tree

A

B * Tree
B+ Tree

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

How is the heap structure applied

A

Priority Queue
Huffman coding

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

What is an algorithm

A

A set of instructions on how to complete a specific task

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

What are the different classifications of algorithms?

A

Brute force
Divide and Conquer
Backtracking
Greedy

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

What is a backtracking algorithm

A

Keep trying but when you a reach a point where things don’t work out you go back and try a different possibility

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

What is a greedy algorithm

A

An algorithm where a decision is made that is deemed good but no consideration is given to future consequences

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

What is a data structure

A

A way to store and organise data in order to facilitate access and modifications

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

What is a hierarchical data structure

A

A data structure where each node has a unique predecessor and many successors

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

What is a linear data structure

A

A data structure where each node has a unique predecessor and a unique successor

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

What is a graphical data structure

A

A data structure where each node has many predecessors and many successors

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

What is a set structure

A

No predecessor and no successor

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

What does ADT stand for

A

Abstract data type

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

What is an ADT

A

A collection of data and associated methods stored as a single module

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

Can data be accessed directly in an ADT

A

No data is accessed indirectly through its methods to access and modify

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

Compare an ADT and a data structure

A

ADT:
What it can do
Implementation independent

Data structure:
How it does it
Implementation dependent

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

What is a stack

A

A collection of objects where only the most recently inserted object (Top) can be removed at anytime works on LIFO(Last in first out) basis.

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

Name some stack methods

A
  • Push-Add an item to the top of the stack
  • Pop-Remove an item from the top of the stack
  • Peek-Examine item at the top of the stack
  • Empty-Determine if the stack is empty
  • Full-Determine if the stack is full
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
28
Q

What is a queue

A

A collection of objects organised such that the object that has been stored in the queue the longest is the next one removed.
Works on a FIFO (First in First Out)

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

Name some ADT

A

Stack
Queue
Linked lists
Hash Table

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

Where are elements inserted and removed in a queue

A

Elements are inserted to the tail(back) of the queue and elements are removed from the head(front)

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

Name some queue methods

A
  • Enqueue - Add to tail of queue
    • Dequeue - Remove from the queue
    • Full - See if its full
    • Empty - See if its empty
    • First - See what element is first
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
32
Q

What is the big O notation for Constant complexity?

A

O(1) - The time taken does not grow no matter how the input n varies or when you find the element immediately

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

What is the big O notation for Linear complexity?

A

O(n) - As the input end gets bigger the time also increases e.g linear search

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

What is the big O notation for Polynomial complexity?

A

O(n^2) - the time it takes increases at a faster rate than the rate of increase in the size of input n e.g bubble sort

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

What is the big O notation for Logarithmic complexity?

A

O(log n) - As the input size grows the number of operation grows very slowly

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

What does complexity of O(logn) mean

A

An algorithm that repeatedly excludes half the variables during its execution

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

Name all the searching algorithms

A

Linear search
Binary Search

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

What happens in linear search

A

You search in order until you find what you want

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

What happens in binary search

A

Check the middle element. Discard the left or right in the list that doesn’t contain the item. List must be sorted tho

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

What is the worst, best and average case of binary search

A

○ Best case O(1)
○ Worst Case O((log2n)
Average O(log2n)

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

What is the worst, best and average case of linear search

A

○ Best case O(1)
○ Worst case O(n)
○ Average case N/2

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

Name the 5 sorting algorithms

A

Selection Sort
Insertion sort
Bubble sort
Quick sort
Merge Sort

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

What happens in selection sort

A

Smallest/largest element is selected from the unsorted array and swapped with the leftmost element of the unsorted section. Item now in its correct final position with the ascending/descending order. Repeat on unsorted side until all are in order

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

What happens in insertion sort

A

Item is inserted into the correct position

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

What happens in bubble sort

A

Works by swapping the items via comparison. At the end of each pass the largest item is at the end

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

What is the best and worst case of Insertion

A
  • Best case O(n)
  • Worst Case O(n^2)
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
47
Q

What is the best and worst case of bubble sort

A

○ Best case O(n^2)
○ Worst case O(n^2)

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

What is the best and worst case of selection sort

A

○ Best case O(n^2)
○ Worst case O(n^2)

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

What is recursion

A

Recursion is a alternative method of repeating a code
Its when a function calls itself

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

When is recursion applied

A

○ Solution is easy to specify for certain conditions–stopping case.
Rules for proceeding to a new state which is either a stopping case or eventually leads to a stopping case–recursive steps

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

What happens in merge sort

A

Merge sort is when you break apart the list then in the final bit you merge so in order

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

What is the worst, average and best case for merge sort

A
  • Best case O(n log n)
    • Worst case O(n log n)
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
53
Q

What happens in quick sort

A

You choose a pivot then compare your pointers and swap accordingly. Then you repeat this for either side of the pivot treating either side as its own list

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

What is the best, worst and average case of quicksort

A
  • Best case is O(n log n)
    • Worst case is n^2
    • Average case is O( n logn)
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
55
Q

What is a static array

A

A fixed array

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

Give some advantages and disadvantages of static arrays

A

Advantage:
Faster access to each entry as long as the index is known - O(1)
Disadvantage:
Fixed size - can not be easily extended
Can be expensive to maintain

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

What is a linked list

A

A collection of objects, called nodes
Its a dynamic data structure

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

What are the 2 components of nodes

A

Information to be stored (the data)
Reference to the next node (often called a link

In code its written as
○ head.data
§ Accesses data sorted in the first node.
○ head.link
§ Reference to the second node

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

Name some advantages and disadvantages of dynamic data structures

A

Advantages:
○ Easily extended or reduced to fit the data set.
Efficient - O(1) to insert/delete item, once located
Disadvantages:
Does not allow direct access
Uses more memory

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

What is the difference between a general tree, binary tree and a binary search tree

A

General Trees: No restriction on the number of child nodes a parent can have
Binary Trees: At most two children per node, with ordering.
Binary Search Trees: At most two children per node but left node < parent and right node > parent makes search and retrieval efficient

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

What is the formula for the max number if nodes in a binary search tree of height n

A

(2^n) -1

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

What is the formula for the height of a balanced binary tree

A

h=⌊log2​(n)⌋+1

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

What is another way to find the height of a tree

A

Number of comparison in the worst case

64
Q

Does the middle element have to be the root in a binary tree

A

No

65
Q

What is a balanced tree

A

A tree in which all paths from the root node to the leaf nodes are of the same length(all leaves are on the same level)

66
Q

Define a tree

A

A hierarchical structure that consists of nodes connected by edges

67
Q

Define an edge

A

The connection between nodes

68
Q

Define the root

A

The topmost node in a tree, which has no parent

69
Q

Define a branch

A

A connection between a parent node and its child node

70
Q

Define subtree

A

A tree formed by a node and its descendants

71
Q

Define a leaf(terminal node)

A

node with no preceding node(nothing after it)

72
Q

Define degree of a node

A

The number of branches connected to it. It tells you how many children the node has

73
Q

Define the level of a node

A

The distance of a node from the root. The root is at level 0

74
Q

Define the height/depth of a tree

A

The length of the longest path from the root to a leaf node

75
Q

What are the 5 traversals

A

Pre order
Post order
In order
Breadth first
Depth first

76
Q

What are the tips for post,pre an in order traversal

A
  • For PreOrder you start with the root
  • For post order you end with root also start with left then right
  • In order just write out the numbers from smallest to largest
77
Q

What does AVL mean

A

Self balancing

78
Q

What does splay mean

A

Self organising

79
Q

What are the pros and cons of balancing in trees

A

Pros:
If tree reasonably balanced then operations (insertion, deletion and search) are fast
Best case O(log2n)

Cons
If tree unbalanced then operations are slow
Worst case O(n)

80
Q

Why do we use AVL trees

A

To avoid the worst case

81
Q

What is an AVL tree

A
  • An AVL tree is a binary tree search tree in which:
    ○ The height of the subtrees are at most a difference of 1
    ○ Left and right subtrees are also their own AVL trees( a recursive definition)
82
Q

How do we ensure the height of subtrees are at most a difference of 1 in AVL trees

A

We make use of rotations

83
Q

What is the balance factor of a node

A

The height of its left subtree minus the height of its right subtree

84
Q

How are AVL trees created

A

Insert the items as per usual then balance them out using rotations

85
Q

Name the types and the actual rotations used in AVL trees

A

Single rotations - LL and RR
Double rotations - LR and RL

86
Q

Where do rotations take place in AVL trees

A

Around the unbalanced node

87
Q

Give some pros and cons to AVL Trees

A

Pros:
Searching is fast
Insertion and deletion is both fast (rotation is required)
Cons:
Since rotation is required its complex to understand and maintain

88
Q

What is the complexity of AVL trees

A

O(log2n)

89
Q

What is a splay tree

A

. A self organising BST with the property that recently accessed elements are always quick to access again
. It keeps the most commonly used data near the top of the tree
. Self-adjusts after every search, insertion and deletion operation.

90
Q

What is splaying

A

The movement of a node S to the root through a series of rotations

91
Q

How does insertion work in splay trees

A

Look where to insert the item and insert it
Once inserted splay the item to the root using a series of double rotations

92
Q

How does deletion work in splay trees

A
  • Search for the item to be deleted
  • If its found splay the item to be deleted to the root
  • Then remove and replace the deleted item
  • If the item to be deleted is not found:
    Splay the last item located to the root
93
Q

How does searching work in splay trees

A
  • Search for the item normally.
  • If the item is found splay it to the root
  • If not found splay the last item located to the root
94
Q

Name the type of rotations and actual rotations in Splay trees

A

Single rotations
o Zig (equivalent to LL and RR rotations used in AVL trees)

Double rotations
o ZigZag (equivalent to LR and RL rotations used in AVL trees)
o ZigZig

95
Q

What is the best, worst and average case for splay trees

A

best case : O(1).
worst case : O(n).
average case: O(log2 n).

96
Q

What is a 2-3 tree

A
  • A multi-way search tree in which:
    ○ Each node contains 1 or 2 data items
    ○ Every internal node must have 2 or 3 children
97
Q

Why is a 2-3 tree balanced

A

All leaves are on the same level

98
Q

What is a 2 node

A

A node that has:
1 item of data
Has either 2 children or no children

99
Q

What is a 3 node

A

A node that has:
○ 2 items of data
○ Has either 3 children or no
children

100
Q

What are the 2 extra rules for nodes in a 2-3 tree

A

○ Values of all descendants in the centre subtree are less than the value of the second data item
○ Values of all descendants in the right subtree are greater than the value of the second data item.

101
Q

How does insertion work in 2-3 trees

A
  • The new item is inserted directly into the leaf node
  • The steps are as follows:
    ○ Locate the new leaf node that should contain the new item
    ○ If the leaf node contains one data item: the new item is inserted into this leaf node and the insertion completed.
    ○ If leaf node contains two data items: space has to be created – this is achieved by splitting nodes.
102
Q

How is splitting done in 2-3 trees

A
  • The node is split into two nodes - say, L1&L2.
  • The smallest of the 3 data items is placedintoL1.
  • The largest of the 3 data items is placedinL2.
  • The remaining data item(the middle one) is promoted to the parent node.
    (Look at slides for what to do based on typa node)
103
Q

Give the pros and cons of 2-3 trees

A

Pros:
Tree always balanced
Insertion, deletion and searching is fast - O(log3n)
Cons:
Complex and maintaining

104
Q

What is a B tree

A
  • B Tree of order m is a self-balancing multi-way search tree with the following properties to maintain its balance:
    ○ root node can store between 2 and m-1 items
    ○ Internal nodes(any node below the root) have between [m/2] and m children
    All leaves are on the same level
105
Q

What is my simplified version of what a B tree

A

Like a 2-3 tree but you specify the order/degree of nodes with the letter m

106
Q

What is the formula for the number of data items in a 2 -3 tree

A

(2^h)-1
and (3^h)-1

107
Q

What does each node in a B tree represent

A

A block(or page) of secondary storage which means accessing is more expensive

108
Q

What is a B* Tree

A
  • The B* Tree is a variation of the B Tree with aim to improve efficiency of access.
  • Where each node except the root node is at least 2/3 full
  • The frequency of splitting a node is decreased by delaying a split
  • When a node overflows:
  • A split is delayed by redistributing the keys between the node and its sibling.
  • When a split is made two nodes are split into three
109
Q

What is a B + Tree

A

Internal nodes of a B+ Tree are used as an index to enable fast access to the data.
The index is a B Tree

110
Q

Compare a B Tree and a B + Tree

A

B Tree:
Keys/indices not repeated
Data stored in all nodes
Long search
Deletion is hard
B + Tree:
Stores redundant keys/indices
Data only stored in leaf nodes
Quick search and quicker in general
Deletion is easy

111
Q

What is Hashing

A

Hashing involves using an array for the efficient storage and retrieval of information

112
Q

How does hashing work

A
  • Mapping the input key (data item) to an output index of the array.
  • The mapping will not keep a sorted array of keys
    Hashing makes the retrieval of data faster
113
Q

What must a good hashing function have

A

○ Quick and easy to compute
○ Minimise collisions
○ Achieve an even distribution of keys
. It must aim for the efficiency O(1) for the retrieval and storage of data
.use less memory

114
Q

What is truncation

A

Ignores part of the key and uses remaining parts as the hash value. Its fast but can fail to distribute keys uniformly

115
Q

What is folding

A

Splits the key into several parts and then combines the parts to get the hash values. It gives better spread than truncation

116
Q

What is modulo arithmetic

A

Divide key by table size and uses the remainder as the hash value

117
Q

Name some ways to solve collisions

A

Chaining & open addressing

118
Q

What are the open addressing methods for solving collisions

A

○ Linear Probing - linear search of the table from the hashed position is used to find an empty slot (h + i)
○ Quadratic Probing (h + i^2)
○ Double Hashing - 2 hash functions are used. The hash value of another hash function g is added to the hashed value h repetitively to find an empty slot(h, h + g, h + 2g and etc)
○ Random Rehashing - RNG used to obtain increments.

119
Q

What is a priority queue?

A

An abstract data type(ADT) supporting the following operations:
○ Insert an element into the queue with an associated priority;
○ Remove element from the queue with the highest priority.
○ Locating the element with the highest priority

120
Q

How are priority queues implemented

A

Static arrays
Heap data structure because the highest priority item is stored at the root

121
Q

Why are priority queues efficient

A

Because you are inserting into the first available space O(1)

122
Q

When is a heap data structure useful

A

When it is necessary to repeatedly remove the object with the highest (or lowest) priority, or when insertions need to be scattered with removals of the root node

123
Q

What is a max heap

A

A binary tree with the following characteristics:
○ It’s a complete binary tree
○ The key present at the root node must be greatest among the keys present at all of it’s children.
○ The same property must be recursively true for all sub-trees in that Binary Tree

124
Q

What is a min heap

A

A binary tree with the following characteristics:
○ The key present at the root node must be minimum among the keys present at all of it’s children.
○ The same property must be recursively true for all sub-trees in that Binary Tree

125
Q

What happens in heap insertion

A
  • Item is inserted as the next leaf on that level
  • If full the item is inserted on the next level on the left side
  • Insertion can destroy the heap property
  • To restore the heap property the inserted item is moved up the tree until it ends up as the root or it finds a parent which restores the heap property (Keep swapping until the biggest all the smallest is the parent)
126
Q

what happens in heap removal

A

Items at the root are easy to remove - leaving us with two sub-trees from which we must re-create a single tree which satisfies properties of a heap.

127
Q

Compare AVL, Splay and heap

A

AVL - BST, focuses on the balance(difference of height) of the tree, height is not guaranteed
Splay - BST, focuses on the most recently visited node, height not guaranteed
Heap - Complete BT, focuses on priority, shortest height

128
Q

Name some applications of heap

A
  • Dijkstra’s algorithm
    • Kruskal’s algorithm
      Huffman’s algorithm
129
Q

What is data compression:

A
  • Aim to represent information as accurately as possible using the fewest number of bits
130
Q

What are some good things about data compression

A

○ Reduces storage space used and storage costs

Reduces time to retrieve data & time to transmit data

131
Q

What are the 2 types if compression

A

Lossy and lossless

132
Q

Name some data compression techniques

A

Text compression, Voice compression, Image compression

133
Q

What is fixed length encoding

A
  • When each character/element is encoded using a fixed number of bits
  • Using 2 bits per character instead of 8 bits per character
134
Q

What is variable length encoding

A
  • Code words used to represent characters
  • Shorter code words used more frequently
  • Longer code words are used more frequently
  • Variable length coding can reduce the size of an encoded string
135
Q

What is huffman coding

A
  • Huffman coding is a statistical compression method to convert characters into variable length bit strings.
  • Most frequently occurring characters are converted into short code-words and the least frequently occurring ones into longer code-words
  • Makes use of a priority queue so we use heap data structure
136
Q

When are graphical data structures used

A

Mostly used when linear and tree structures are not applicable

137
Q

Name some graph theories

A
  • Shortest path problem - Graph traversal and path search with tradeoff between space and time
  • Ramsey theory - For any 6 people, either at least 3 of them are mutual strangers or at least 3 of them are mutual acquaintances
138
Q

Name some ways graphs are applied irl

A
  1. Planning a journey by air:
    ○ What is the shortest route
    ○ Shortest distance between 2 cities
  2. A maze
    ○ Is there a path from the entrance to the exit
139
Q

What is path

A

The route taken along the edges in a graph

140
Q

What is a cycle

A

A path that starts and ends at the same vertex in a graph

141
Q

What are vertices

A

The nodes in a graph

142
Q

What is a directed graph

A

Graph with arrows

143
Q

What is a undirected graph

A

Graph without arrows

144
Q

What is a weighted graph

A

A graph where the edged hold numerical weight(edges have numbered)

145
Q

What is an adjacency matrix

A

A square matrix used to describe which vertices (or nodes) of the graph are adjacent to each other.
If they are adjacent we represent this using a 1, if they aren’t we use a 0
In a weighted graph we replace the 1 with the weight of the edges and 0s with infinite.

146
Q

What is an adjacency list

A

An alternative to an adjacency matrix
* A 1D array is used to store vertices and their adjacency
* A set of singly linked lists with one SLL for each vertex.
* Each SLL contains all vertices that are adjacent to the vertex

147
Q

What is a short path tree and name an example

A
  • A tree that contains all vertices and a subset of edges - the path from the root to any other vertex has the shortest distance

Example dijkstras algorithm

148
Q

What is a spanning tree

A
  • A spanning tree of a graph is a tree that contains all the vertices with only path between pairs if vertices
  • A graph can have many different spanning trees (E.g. Breadth first search and depth first search)
149
Q

Name some applications of spanning trees

A

Design of computer networks
Airline routes

150
Q

Name algorithms that involve spanning trees

A

Prim’s Algorithms and Kruskal’s Algorithm

151
Q

Why is Binary Search Preferred over Ternary or N-ary Search?

A

. Simple and easy to understand
. Fewer comparisons
. Efficient memory acces

152
Q

Compare a SLL and a skip list

A

SLL:
. Elements are connected one after the other in a straight line.
Searching takes
. O(n) time on average
. Insertion and deletion quick and easy

Skip-list:
. Consists of multiple parallel SLL
. Searching is faster
. Insertion and deletion is harder

153
Q
A

Depth First Traversal (DFT)
* Proceeds along a path from the root through one child to the most distant descendant of that first child before processing the second child.
* Implementation uses a stack.
* Leaf by leaf.
 Breadth First Traversal (BFT)
* Proceeds horizontally from the root to all of its children then to its children’s children and so on…
*Implementation uses a queue. * Level by level.

154
Q

Name the 3 types of depth first traversal

A

Pre order,inorder postorder

155
Q

. Explain the difference between a Depth First Traversal and a Breadth First Traversal of a graph.

A

BFS of a graph processes the start vertex and then processes all of its adjacent vertices.  Then it picks the first adjacent vertex and processes all of its adjacent vertices(makes use of edge table)

156
Q

What is the formula for the maximum number of nodes in B tree

A

(o^h) -1
o is the order of the tree
j is the height of a tree

157
Q
A

Software engineering 2nd yr (3 decks)

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