Suppose that you run the orthogonal line segment intersection algorithm from lec
ID: 3690361 • Letter: S
Question
Suppose that you run the orthogonal line segment intersection algorithm from lecture on the following set of segments:
A ( 8, 15) -> ( 8, 18) [ vertical ]
B (17, 17) -> (19, 17) [ horizontal ]
C ( 4, 9) -> (18, 9) [ horizontal ]
D ( 3, 11) -> ( 7, 11) [ horizontal ]
E (11, 8) -> (11, 14) [ vertical ]
F ( 2, 10) -> ( 9, 10) [ horizontal ]
G ( 5, 6) -> ( 5, 14) [ vertical ]
H ( 0, 13) -> (14, 13) [ horizontal ]
Give the horizontal line segments in the BST (sorted in increasing order of y-coordinate) just before the sweep-line algorithm processes the vertical line segment G.
H F C
C F H
C F D H
H F D C
Consider the adjacency-lists representation of a graph with 8 vertices and 9 edges:
A: F E
B: G C
C: G D H B
D: C
E: A
F: G A
G: C F H B
H: C G
Run depth-first search (using the adjacency-lists representation) from vertex A. Give the sequence in which depth-first search discovers (marks) the vertices. This is known as the preorder.
A E B F G C D H
A B C D E F G H
A F G C D H B E
A F B C D G H E
3.
Consider the adjacency-lists representation of a graph with 10 vertices and 11 edges:
A: B G F
B: H A G
C: I
D: J E
E: J D
F: G A
G: F B A H
H: B G
I: C
J: D E
Compute the connected components of the graph using the depth-first search algorithm (and start numbering connected component ids with 0). Give the sequence of the 10 integers in the id[] array for the vertices A through J.
v A B C D E F G H I J
------------------------------------
id[v]
A.0 0 1 2 2 0 2 2 1 2
B.0 0 1 2 2 0 0 0 1 2
C.0 0 1 2 2 1 0 0 1 2
D.0 0 1 2 2 0 1 0 1 2
4.
Suppose that the following keys are inserted into an initially empty linear-probing hash table but not necessarily in the order given:
key hash
--- ----
A 2
B 3
F 0
G 1
H 2
Q 4
W 3
Assuming that the size of the hash table is 7 and that it does not grow or shrink, which one or more of the following could be the contents of the resulting array?
F G H W B Q A
H G F B A Q W
B F G W Q H A
A B Q F W G H
5.
Insert the following sequence of 12 keys into a separate-chaining hash table with 3 chains:
key hash
--- ----
Z 0
R 1
A 2
W 0
M 2
P 2
H 0
N 0
Y 2
C 1
B 0
I 1
Consider a search hit for the key P, whose hash value is 2.
What is the sequence of keys that get compared with P?
A M P
A M
A M Y P
Y P
6.
Consider the left-leaning red-black BST whose level-order traversal is:
40 28 85 17 29 72 98 15 71 84 93 69 81
List (in ascending order) the keys in the red nodes. A node is red if the link from its parent is red.
A.17 69 72 81 93
B.15 69 81 93
C.15 29 72 81 93
D.15 69 72 81 93
7.
Consider the left-leaning red-black BST whose level-order traversal is
35 13 86 10 31 71 91 29 68 72 ( red links = 29 71 )
What is the level-order traversal of the red-black BST that results after inserting the following sequence of keys:
40 80 37
35 13 86 10 31 71 91 29 68 80 40 72 37
71 35 86 13 40 80 91 10 31 37 68 72 29
71 35 86 10 40 80 91 13 31 37 68 72 29
35 13 86 10 31 37 71 91 29 68 80 40 72
8.
Consider the left-leaning red-black BST whose level-order traversal is
86 57 93 38 60 90 95 32 53 10 ( red links = 10 38 )
What is the level-order traversal of the red-black BST that results after inserting the following sequence of keys:
50 68 63
A.86 57 93 38 63 90 95 32 53 60 68 10 50
B.86 57 93 38 63 90 95 10 53 60 68 32 50
C.86 57 93 38 63 68 90 95 32 53 60 10 50
D.86 57 93 38 68 90 95 32 53 60 63 10 50
9.
Give the level-order traversal of the BST that results after inserting
the following sequence of keys into an initially empty BST:
53 83 95 13 86 68 47 87 64 54
83 53 95 13 68 86 47 64 87 54
13 47 53 54 64 68 83 86 87 95
53 13 47 54 64 87 68 86 95 83
53 13 83 47 68 95 64 86 54 87
10.
Given a BST whose level-order traversal is:
14 36 25 84 32 42 88 57 86 91 59 65
What is the level-order traversal of the resulting BST after Hibbard deleting the following three keys?
86 57 36
A.14 25 32 42 84 88 59 65 91
14 25 84 32 42 88 59 65 91
C.14 32 25 84 42 88 91 59 65
D.14 42 25 84 32 59 88 65 91
A.H F C
B.C F H
C.C F D H
D.H F D C
Explanation / Answer
Multiple Questions : ANswering 1 (Question 2).
A F G C D H B E
C.A F G C D H B E
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.