Brainscape's Knowledge GenomeTM

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


See full index

CS 261 > Final > Flashcards

Final Flashcards

1
Q

How many root nodes does a tree have?

A

One

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

A _____ consists of a collection of nodes connected by directed arcs.

A

Tree

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

A node that points to one or more other nodes…

A

Parent

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

What are the nodes that are pointed to?

A

Children

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

How many parents does every node have? (except root node)

A

One

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

What are nodes with no children

A

Leaf nodes

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

What are the nodes with children called?

A

Interior nodes

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

What are nodes that have the same parent?

A

Siblings

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

Consists of its children, and their children, and so on…

A

Descendants

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

A _____ rooted at a node consists of that node and all of its descendants.

A

Subtree

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

A path’s _____ is equal to the number of arcs traversed.

A

Length

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

A node’s _____ is equal to the maximum path length from that node to a leaf node.

A

Height

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

A leaf node has a height of…

A

0

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

The height of a tree is equal to…

A

The height of the root.

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

A node’s _____ is equal to the path length from the root to that node.

A

Depth

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

How many children can a node have?

A

Two

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

For a Full Binary Tree, every internal node has _ children.

A

2

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

For a Full Binary Tree, every leaf is at the same _____.

A

Depth

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

What is the height of nodes for a Full Binary Tree?

A

2^h+1 - 1

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

What is the height of leaves for a Full Binary Tree?

A

2^h

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

Write the structs for a Tree?

A

struct Node
{
TYPE val;

struct Node *left;

struct Node *rght;

};

structBSTree

{

struct Node *root;

int cnt;

};

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

If the tree is reasonably full, what is the search time for an element?

A

O(n)

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

Returns elements in sorted order.

A

In-order traversal

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

Write the implementation:

void add(struct BSTree *tree, TYPE val);

A 
void add(struct BSTree *tree, TYPE val)
{

tree->root = _addNode(tree->root, val);

tree->cnt++;

}

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

Write the implementation:

struct Node *_addNode(struct Node *cur, TYPE val);

A

struct Node *_addNode(struct Node *cur, TYPE val)
{

struct Node *newNode;

if(cur == NULL)

{

newnode = malloc(sizeof(struct Node));

assert (newnode != 0);

newnode->val = val;

newnode->left = newnode->right = 0;

return newnode;

}

if (val val)

cur->left = _addNode(cur->left,val);    else cur->right = _addNode(cur->right, val);      return cur;

}

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

Write the implementation:

void initBST(struct BinarySearchTree *tree);

A 
void initBST(struct BinarySearchTree *tree) 
 {

tree->size = 0;

tree->root = 0;

}

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

Write the implementation:

void addBST(struct BinarySearchTree *tree, TYPE newValue)

A

void addBST(struct BinarySearchTree *tree, TYPE newValue)

{

tree->root = _nodeAddBst(tree->root, newValue);

tree->size++;

}

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

Write the implementation:

int sizeBST (struct binarySearchTree *tree)

A

int sizeBST (struct binarySearchTree *tree)

{

return tree->size;

}

29
Q

Write the implementation:

struct node * _nodeAddBST (struct node *current, TYPE newValue)

A

struct node * _nodeAddBST (struct node *current, TYPE newValue)

{

struct Node *node;

if (current == 0) {

node = (struct Node *)malloc(sizeof(struct Node));

assert (node != 0);

node->value = newValue;

node->left = node->right = 0;

return node;

}

if (LT(newValue, current->value))
current->left = _addNode(current->left, newValue);

else current->right = _addNode(current->right, newValue);

return current;

}

30
Q

Write the implementation:

int containsBST (struct binarySearchTree *tree, TYPE d)

A

int containsBST (struct binarySearchTree *tree, TYPE d)

{

struct Node *cur = tree->root;

while (cur != 0 ) {
if (EQ(d, cur->value))

  return   1  ;   /* Return true if value found. */  

if   (LT(d, cur->value))  

  cur = cur->left;   /* Otherwise, go to the left */  

else   cur = cur->right;   /* or right, depending on val. */

}
return 0 ; /* Return false if not found. */

}

31
Q

Write the implementation:

void removeBST (struct binarySearchTree *tree, TYPE d)

A

void removeBST (struct binarySearchTree *tree, TYPE d)

{

if (containsBST(tree, d) {
tree->root = _nodeRemoveBST(tree->root, d); tree->size–;

}

}

32
Q

Write the implementation:

TYPE _leftMostChild (struct node * current)

A

TYPE _leftMostChild (struct node * current)

{

while (current->left != 0 )

current = current->left;

return current->val;

}

33
Q

Write the implementation:

struct node * _removeLeftmostChild (struct node *current)

A

struct node * _removeLeftmostChild (struct node *current)

struct Node *node;

if(current->left == 0) {  

  node = current->right; free(current);
 return   node;

}

current->left = _removeLeftMost(current->left);

return   current;

}

34
Q

Write the implementation:

void _nodeRemoveBST (struct node * current, TYPE d)

A

void _nodeRemoveBST (struct node * current, TYPE d)

{

struct Node *node;

if ( LT (val, current->val) == 0 ) { if (current->rght == 0 ) {

node = current->  left  ;   free  (current);
 return   node;   /* Found value. */

}
current->val = _leftMost(current->rght);

current->rght = _removeLeftMost(current->rght); }

else if ( LT (val, current->val) 0 )
current-> left = _removeNode(current-> left , val);

else current->rght = _removeNode(current->rght, val); return current;

}

35
Q

Length

A

The number of arcs

traversed.

36
Q

Height

A

The maximum path length from

that node to a left node.

37
Q

Has Height 0

A

Leaf Node

38
Q

Nodes with no

children

A

Leaf Nodes

39
Q

Nodes with Children

A

Interior Nodes

40
Q

Each node has at most two children. Children are

either left or right.

A

Binary Tree

41
Q

We will store our binary trees in instances of

struct Node.

A

Each node will have a value, and a left and

right child, as opposed to the next and prev pointers of the

DLink.

struct Node {

TYPE value;

struct Node * left;

struct Node * right;

}

42
Q

4 Traversals

A

Used to examine every node in a tree in sequence.

43
Q

Preorder Traversal

A

Examine a node first, then left children, then right children

44
Q

Inorder Traversal

A

Examine left children, then a node, then right children

45
Q

Postorder Traversal

A

Examine left children, then right children, then a node

46
Q

Levelorder

A

Examine all nodes of depth n first, then nodes depth n+1, etc

47
Q

Most useful Traversal in practice

A

Inorder

48
Q

Euler

tour

A

Traversal of a tree… Like a walk around the perimeter of a binary tree.

49
Q

Fast addition of new elements, search time, and removal.

A

Skip List

50
Q

Skip Lists

A

Skip lists are a data structure that can be used in place of balanced trees.

Skip lists use probabilistic balancing rather than strictly enforced balancing

and as a result the algorithms for insertion and deletion in skip lists are

much simpler and significantly faster than equivalent algorithms for

balanced trees.

51
Q

Skip Lists

A

Skip lists are linked lists that allow you to skip to the correct node. The performance bottleneck inherent in a sequential scan is avoided, while insertion and deletion remain relatively efficient. Average search time is O (lg n ). Worst-case search time is O ( n ), but is extremely unlikely.

52
Q

Disadvantage of Skip List

A

The one disadvantage of the skip list is that it uses about twice as much memory as needed by the

bottommost linked list.

53
Q

Binary Search Tree

A

A binary search tree is a binary tree that has the following additional property: for each node, the values in all descendants to the left of the node are less than or equal to the value of the node, and the values in all descendants to the right are greater than or equal.

54
Q

Height-balanced binary tree

A

–Depth of all leaf nodes differ by at most 1

–With height h, contains between 2 h -1 and 2 h nodes

55
Q

Full BInary Tree

A

A binary tree in which all of the leaves have the same height and every internal node has two childeren

56
Q

Complete Binary Tree

A

a full tree up to the second last level with the last level of leaves being filled in from left to right (if last level is completely filled, the tree is full)
height h –> between 2^(h-1) and 2^h - 1 nodes

57
Q

Binary Search Tree (BST)

A
  • For each node in tree
  • All data in left subtree is less
  • All data in right subtree is greater Does not allow for duplicates
  • If necessary add “or equal to” to ONE of above lines Shape doesn’t matter - can be anywhere from full to linear
58
Q

balanced tree

A

a tree in which the height of the subtrees are about equal

59
Q

Provenance

A

Describes origin history or how that file came to be

60
Q

Graphs

A

Comprised of vertices and edges, and represent relationships and/or connections

61
Q

Vertices (or Nodes)

A

Represent objects, states, positions or placeholders.

Each vertex is unique -> no two vertices represent object/state.

62
Q

Edges (or Arcs)

A

Edge between two vertices indicates they are connected and neighbors

Can be either directed or undirected

Can be either weighted or unweighted

63
Q

Adjacency Matrix

A

Representation of a graph with O(V^2) Space. Weights can be included or not

By Convention, a vertex is usually connected to itself (but not always)

64
Q

Edge List

A

Representation graph with O(v+e) space. Weights can be included or not.

Stores only the edges > More space efficient for sparse graph

More of a list than a matrix (like the adjacency matrix)

65
Q

depth-first search

A

algorithm for searching a tree, tree structure, or graph

starts at root and explores as far as branches before backtracking

66
Q

Breadth-first search

A

Used with a queue, process start node, put all the neighbors on the queue which are processed before any other nodes. Neighbors of neighbors are then processed.

67
Q

Traits of depth first search

A

Like a single person working a maze

Can take the wrong route and have to backtrack multiple times

May get lucky and find shortest route very quickly OR May get stuck going down an infinite path

68
Q

Traits of breadth first search

A

Like a wave flowing through a maze

May not find goal quickly, but will always find it

Because it checks length 1, then 2, then 3, guaranteed to find shortest path (if it exists)

BFS will never get stuck on an infinite path

69
Q

Dijkstra’s Algorithm

A

Given start vertex, graph and goal. Explores nodes in cost order. Records total cost to point at node, edge travelled to arrive. Overwrites these if arrived at again with smaller cost.
Open list initially start node, closed list initially empty.

Terminates when open list is empty. Start at goal and traverse back along edges.

CS 261 (2 decks)

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