COMPSCI 220
COMPSCI 220代写 Adding an arc to a digraph of order n and size m (before the arc was added) stored using adjacency lists will require, on average
1.Adding an arc to a digraph of order n and size m (before the arc was added) stored using adjacency lists will require, on average, how much extrastorage? COMPSCI 220代写
A.Resizing the hashtable
B.Universalhashing
C.Open addressing with linearprobing
D.Separatechaining
E.Open addressing with doublehashing
- Supposethat the function f (n) is Θ(n) and that the function g(n) is O(n log n). Then the product function h(n) = f (n) g(n) is . . .
A.Θ(n2)
B.Ω(n2log n)
C.Θ(n2log n) COMPSCI 220代写
D.O(n2log n)
E.O(n2)
- Algorithms 1–5 have running times for input of size n given respectively by the formulae (ln n)2+ 4 lg n 1, 10−60n3, 3 lg n + 2000n, (log3 n)5, n2 + 5n 1/n6. Which is the third fastest, asymptot- ically?
A.4
B.5
C.1
D.2
E.3
- Consider digraph tt Which of the following orderings on the nodes of tt is the topological ordering obtained by executing DFS starting from node 1 and selecting the node with the smallest label when the algorithm has multiplechoices? COMPSCI 220代写
A.1,4,2,8,3,7,6,5
B.1,8,3,2,7,4,6,5
C.1,4,2,3,8,7,5,6
D.1,2,4,8,3,7,6,5
E.1,4,2,3,8,7,6,5
5.Suppose that an algorithm runs DFS from every node of a digraph with order n and size m. The running time of the algorithmis COMPSCI 220代写
A.Θ(n2+ nm)
B.Θ(n3)
C.Θ(n +m)
D.Θ(n2)
E.Θ(m2)
- The all pairs shortest paths (APSP) problem can be solved for a typical weighted digraph of ordern and size m with arbitrary weights most efficiently by:
A.Bellman-Ford with running timeΘ(n3)
B.Bellman-Ford with running timeΘ(n2m) COMPSCI 220代写
C.Floyd’s with running timeΘ(n3)
D.Floyd’s with running timeΘ(n2m)
E.Dijkstra with running timeΘ(n2m)
7.Supposethat an unsorted list of size 1, 000 has 100, 000 How many inversions will it have after swapping two nearest neighbours, which were out of order?
A.99,999
B.50,000
C.99,001
D.98,999
E.99,000
- What is the girth of the graphshown?
A.8
B.∞
C.4
D.3
E.6
9.We have a hash table of size 7 to store integer keys, with hash function h(x) = x mod 7.
If we use linearprobing (where we probe to the left) and insert elements in the order 1, 15, 14, 3, 9, 5, 20, how many times will an element try to move to an occupied spot?
A.1
B.4
C.0
D.3
E.6
- Therecurrence T (n) = T (n/2) + n, T (1) = 0 has a solution that is of exact order
A.2n
B.n logn
C.n2
D.logn
E.n
- If algorithm A has time complexity Θ(n log n) and runs for 103ms on a problem of size 104, about how long would you expect it to take to solve a problem of size 106? COMPSCI 220代写
A.2.4 × 108ms
B.2 × 106ms
C.1.5 × 105ms
D.105ms
E.106ms
12.A researcher has a database of 100 million records of people.
The researcher wants to study the distributionof given names according to other criteria such as zodiac sign, birth year, etc, so wants to sort by name with the option of further sorting later. The researcher should use ***-sort, where *** is:
A.selection
B.merge
C.heap
D.quick
E.insertion
- Consider the following
(i)If BFS is run on a graph, there can be no cross edges.
(ii)If DFS is run on a graph, there can be no cross edges.
(iii)IfBFS is run on a digraph, there can be no forward Which are true? COMPSCI 220代写
A.(ii) and(iii)
B.(i) and(iii)
C.(i), (ii) and(iii)
D.(i)
E.(i) and(ii)
- Considerthe digraph tt with nodes 0, 1, 2 and arcs (0, 1) with weight 5, (0, 2) with weight 2, (1, 2)with weight −2. If we are solving the SSSP problem for node 0 then which of the following is true? COMPSCI 220代写
A.Dijkstra gives wrong answer; Bellman-Ford gives rightanswer
B.Dijkstra and Bellman-Ford both give rightanswer
C.Dijkstra and Bellman-Ford both give wronganswer
D.There is no solution for this
E.Dijkstra gives right answer; Bellman-Ford gives wronganswer
15.Ifweexecute Prim’s algorithm on the graph shown starting at vertex 0 and breaking ties by choosingthe vertex with the lower index,
what is the order in which vertices are added to the tree (turn black)?
A. 0,3,2,5,4,1
B.0,3,2,5,1,4
C.0,1,2,3,4,5
D.0,3,5,4,1,2
E.0,2,5,3,4,1
- Which attribute of a binary tree is the recursive formula f (T ) = 1 + max(f (Tl),f (Tr)) used to compute? (hereTl, Tr are the left and right subtrees of the root of the binary tree T )
A.number ofleaves
B.average nodedepth
C.number ofnodes
D.height
E.internal pathlength
- List all sorting methods (***-sort) covered in this course that are comparison-based, in-place, and stable when implemented using arrays. COMPSCI 220代写
A.heap,merge
B.insertion,Shell
C.insertion
D.insertion,merge
E.heap,quick
- The running time to find the out-degree of node i in a digraph of order n and size m represented by an adjacency list is
A.Θ(1)
B.Θ(m)
C.Θ(n)
D.Θ(degree(i))
E.Θ(n +m)
19.Considerthe weighted digraph tt with adjacency lists
0 1 3 2 4
1 0 2 3 2
2 1 3
3 2 1
What is the third column (corresponding to node 2) of the adjacency matrix for tt? COMPSCI 220代写
A.0, 3, 0,0
B.4, 0, 0,1
C. 0, 1, 0,1
D.none of the others are correct E. 2, 3, 0,0
20.Whichof the following inputs makes mergesort perform the largest number of comparisons?
A. 1, 2, 3,4
B.all the other choices are correct C. 4, 3, 2,1
C. 1, 3, 2,4
D. 2, 1, 4,3
- Wehave two algorithms for searching a database of n Algorithm A has running time 0.1√n while algorithm B has running time 10 lg n. If we want to run them on a database whose records consist of all Nobel prizewinners, then
A.Ais preferred, since n will not be large enough for B to overtake it
B.all the other answers arewrong
C.B is preferred, since its asymptotic runtime isbetter
D.Bis preferred, since n will not be large enough for A to overtake it
E.A is preferred, since its asymptotic runtime isbetter
- For the graph shown what is the weight of a minimum spanningtree?
A.8
B.6
C.9
D.7
E.10
23.The concept of universal hashing is best described by which of thefollowing?
A.Thesize of the hash table is chosen to be large enough so that keys will hash uniformly into it.
B.Thehash function is universal in the sense that it will hash any randomly chosen key.
C.The keys to hash into the table are chosen randomly. COMPSCI 220代写
D.The size of the hash table, m, is chosen randomly at runtime.
E.Thehash function associated with a table is chosen randomly at run time from a set of possible hash functions.
24.How many strong components does the digraph with adjacency lists belowhave?
0 1 3 5
1 4
2 3
3 2
4 5
5 0 1
A.3
B.2
C.1
D.6
E.4
- Consider the following functions of n: 2n2,n lg3 n, 0.1n3/2, n!, 2n. Put them in order from smallest to largest asymptotic growth COMPSCI 220代写
A.n lg3 n, 0.1n3/2, 2n2, 2n, n!
B. n lg3 n, 0.1n3/2, 2n, 2n2, n!
C. 2n2,n lg3 n, 0.1n3/2, n!, 2n
D. n!, 2n, 2n2, 0.1n3/2,n lg3 n
E. 0.1n3/2, 2n2,n lg3 n, 2n, n!
- Ifyou run Dijkstra’s algorithm starting from node 3 and use lower index labels to break ties, the first node added to the “BLACK” set S is 3. What is the third node added to S?
A.7
B.4
C.1
D.5
E.2
27.If the running time for a particular algorithm is O(n2), which type of asymptotic bound does the function n2give for the running time? COMPSCI 220代写
A.Average
B.Median
C.Upper
D.Lower
E.Tight
- Supposewecarry out DFS on the digraph shown starting at node 0 and breaking ties by choosing the node with the lower index.
Which arc is NOT a tree arc?
A.(2,4)
B.(3,0)
C.(1,3)
D.(0,1)
E.(3,2)
- Choosethe FALSE statement: 7 lg n + 5n + n lg lg n + 3n ln n is COMPSCI 220代写
A.Ω(n2)
B.O(n2)
C.Ω(n)
D.O(n log2n)
E.Θ(n logn)
- Suppose G is a digraph with nodes labeled 0, 1,…,n1 and t records time in a priority first search. If we want the PFS to mimic DFS, what priority can be given to node i when it turns grey? Use the convention that a lower key has a higher priority.
A.−t
B.t +i
C.t
D.t −i
E.i
31.You know that algorithm A runs in exponential time Θ(2n). COMPSCI 220代写
If your computer can process input of size 1000 in one year using an implementation of this algorithm, about what size input would you expect to be able to solve in one year with a computer 1000 timesfaster?
A.1002
B.1010
C.32 000
D.1 000 000
E.1 500
- Considerthe digraph tt with nodes 0, 1, 2 and arcs (0, 1) with weight 1, (1, 2) with weight 4, (2, 1)with weight 2. If we are solving the SSSP problem for node 0 then which of the following is true?
A.Dijkstra and Bellman-Ford both give wronganswer
B.Dijkstra and Bellman-Ford both give rightanswer
C.Dijkstra gives right answer; Bellman-Ford gives wronganswer
D.There is no solution for this digraph.
E.Dijkstra gives wrong answer; Bellman-Ford gives rightanswer
33.Whichcollision resolution policy in hashing often leads to clustering of keys in the table? COMPSCI 220代写
A.Resizing the hashtable
B.Universalhashing
C.Open addressing with linearprobing
D.Separatechaining
E.Open addressing with doublehashing
- It is known that the limit limn→∞log log n = 0. Which of the following statements is true in accord with the Limit Rule?
A.logn is O(log log n) and log n is not Ω(log log n).
B.loglog n is O(log n) and log log n is not Ω(log n).
C.loglog n is not O(log n) and log log n is Ω(log n).
D.logn is O(log log n) and log n is Ω(log log n).
E.loglog n is O(log n) and log log n is Ω(log n).
35.Suppose that we have performed DFS on a digraph tt. If v is an ancestor of w in the resulting search forest,then
A.seen[w] < done[w] < seen[v] <done[v]
B.seen[v] < seen[w] < done[w] <done[v]
C.seen[v] < done[v] < seen[w] <done[w]
D.seen[w] < seen[v] < done[v] <done[w]
E.seen[v] < seen[w] < done[v] <done[w]
- Afterthe items 4, 6, 1, 3, 5, 2 are inserted in that order into an initially empty binary max-heap, what is the right child of the root?
A.1
B.5
C.3
D.4
E.2
- Suppose a graph tt is bipartite with at least one cycle. Which of the following isFALSE? COMPSCI 220代写
A.tt has an odd cycle.
B.The girth of tt is at least 4.
C.BFS can be used to find the bipartition of vertices.
D.BFScan be used to find cycles in tt.
E.tt has a2-colouring.
- In the following graph, the sequence of vertices efcebaeis:
A.a walk and a path but not acycle
B.neither a walk, cycle nor
C.a walk and a cycle but not apath
D.a walk, a cycle and apath
E.a walk but not a cycle orpath
39.Youare given a program which stores a digraph internally, lets you choose a vertex, and tells you what the indegree of that vertex is. COMPSCI 220代写
You try the program on a few graphs and you observe that the running time of the program when it computes the indegree increases both with the number of vertices in the graph and with the number of edges. The storage method the program uses is most likely:
A.A binary
B.A
C.An
D.An adjacency
E.An adjacency
- Supposewe carry out BFS on the digraph shown starting at a randomly chosen white
How many trees could be in the resulting search forest? Choose the most accurate answer.
A.2 or3
B.2
C.1 or2
D.1, 2, or 3
E.1
其他代写：代写CS C++代写 java代写 matlab代写 web代写 作业代写 物理代写 数学代写 考试助攻 paper代写 金融经济统计代写 C/C++代写
