Graph Theory and Algorithms
(a) T or F: For a directed graph with n vertices to be acyclic, the maximum number of edges is n − 1.
(b) T or F: When DFS processes node u’s adjacency list, the color of neighbor v is black, then (u, v) is a forward edge.
(c)
T or F: If u is a descendant of v in a DFS tree, DFS must have discovered v before discovering u.(d) T or F: Topological ordering can be found for any directed acyclic graph.
(e)
T or F: If all edge weights are distinct, the edge with the lowest weight must be in the minimum spanning tree.(f) T or F: To code n symbols with any prefix code, at least one symbol will have code length ≥ log2 n.
(g) T or F:
0-1 knapsack problem can be solved optimally using greedy algorithm.(h) T or F:
The optimal solution of the activity selection problem is unique.(i) T or F: The single-source shortest path problem in a DAG can be solved within Θ(|V | + |E|).
(j)
T or F: We still don’t know whether NP complete problems can be solved in polynomial time.
2. Which of the following statements about breadth-first search (BFS) are true?
(a)
BFS starting from vertex s will visit all the vertices that are reachable from s;(b) Run BFS on a unweighted undirected graph G, if u and v are in a same BFS Tree, then the path between u and v in the BFS tree is the shortest path between u and v in G;
(c)
Run BFS on a bi-partite undirected graph
G, there should not be any edge between two vertices at the same level of a BFS tree;(d) Run BFS on a directed graph will produce a directed BFS tree;
(e)
The complexity of BFS on a dense graph is Θ(
E);
3. Which of the following statements about depth-first search (DFS) are true?
(a)
DFS will visit all the vertices, even if the graph is not fully connected;
(b) DFS will generate shortest paths in a graph;(c) In a directed graph, if there is an edge (u,v), then f(u) > f(v); (d)
For a undirected graph, DFS tree has no cross edges;
(e)
DFS can determine whether there is a cycle in both directed and undirected graphs;
4. Which of the following graph problems CANNOT be solved in linear time O(|V | + |E|)?(a) Determining a topological sort of the vertices in a directed acyclic graph; (b) Finding strongly connected components in a directed graph;
(c) Finding the shortest paths from a source to all the other nodes in a unweighted graph; (d)
Finding the minimum spanning tree of a connected undirected graph;
(e)
Building the transitive closure of a connected undirected graph;
5. Which of the following statements about Greedy Algorithm are true?(a)
Dijkstra’s algorithm is a greedy algorithm;
(b)
Optimal solution for the Activity Selection problem can be obtained using a greedy algorithm;
(c) Singe-source shortest path problem in a DAG can be solved using a greedy algorithm;
(d) The rod-cutting problem is solved using a greedy algorithm;
(e)
Greedy heuristic algorithm can be developed for a NP-Complete problem without guaranteeing an optimal solution
Which of the following statements are true?
(a)
If A is NP-complete, and A can be reduced to B in polynomial time, then B is NP-hard;
(b) IfAisinP,andAcanbereducedtoBinpolynomialtime,thenBisinP;
(c) 2-SAT problem is NP-Complete;
(d)
The time needed to check whether a path is a Hamiltonian cycle is polynomial
(e) If a polynomial time algorithm is found for a NP-complete problem, all NP-complete problems are solvable in polynomial time;
(a)
T or F: Worst case tree height for AVL tree with n nodes is θ(log(n)).(b) T or F: To save time on determining whether an edge (u, v) exists in a graph, one should use adjacency matrix, instead of adjacency list, to represent the graph.
(c)
T or F: For an undirected graph with n vertices to be acyclic, the maximum number of edges is n−1.(d) T or F
: There is only one valid topological ordering of vertices in a directed acyclic graph.(e) T or F
: A dynamic programming algorithm has to find all optimal solutions of the problem to besolved.
(f)
T or F: 0-1 knapsack problem is NP-Complete, but can be solved by dynamic programming;(g) T or F
: Kruskal’s algorithm for minimum spanning tree does not work on a graph with negative weight edges.(h)
T or F: For any Huffman code, if we exchange the codewords for the two least frequent symbols, the new code is still optimal.(i) T or F: The least weighted edge must be in the minimum spanning tree of a connected graph.
(j) T or F
: If all the edge weights are distinct, there can be only one shortest path between any pair ofnodes;
Which of the following statements about depth-first search (DFS) are true?
(a)
Complexity of DFS on a dense graph is θ(E);
(b) DFS can generate shortest path in a graph;(c)
In a DAG, if there is an edge (u,v
), then f(u)
> f(v);
(d)For an undirected graph, DFS tree has no cross edges;
(e) None of the above.
Which of the following graph problems CANNOT be solved in linear time (O(|V | + |E|))?
(a) Determining a topological order of the vertices for a directed acyclic graph; (b) Determining if an undirected graph is connected;
(c) Determining if an undirected graph has at least one loop;
(d)Finding the minimum spanning tree of a connected undirected graph;
(e) None of the above.
Which of the following algorithms does NOT require a heap for its efficient implementation?
(a) Huffman coding algorithm; (b) Dijkstra’s algorithm;
(c) Prim’s algorithm;
(d)Floyd–Warshall algorithm;
(e) None of the above.
In the activity selection problem, if a new activity is added to the input activity set, which has the earliest finishing time among all activities. Compare with the solution of the original problem, which of the following are true?
(a)
The maximum number of activities can be scheduled together will not reduce;
(b)This new activity is in at least one of the optimal solutions to the new problem;
(c) Any optimal solution cannot include the activity with the latest finish time;
NetID: Page 2
(d) The maximum number of activities that can be selected is always increased by one; (e) None of the above.
6. Which of the following statements about shortest path are true?
(a)
In Bellman-Ford algorithm, the edges can be relaxed in any given order;
(b) Greedy shortest path algorithms can work on a graph with negative weight edges;
(c)
In a directed acyclic graph, shortest path distance between any pair of vertices is always well-defined;
(d) If path P1 is the shortest path between u and v, and P2 is the shortest path between v and w, then
the shortest path between u and w is P1 + P2.
(e) None of the above
7. Which of the following statements are true?
(a) Halting Problem is NP;
(b)
Any NP problem can be solved in polynomial time by a non-deterministic algorithm;
(c) NP-Complete problems are not in NP-Hard problem set;
(d)
If a polynomial time algorithm is found for a NP-complete problem, all NP-complete problems are
Solvable in polynomial time;
(e) None of the above.
1.从最小堆中取出两个频率最小的节点。2.创建一个新节点，它的频率是这两个节点频率之和，新节点作为这两个节点的父节点。3.将新节点插回最小堆中。4.重复上述步骤，直到最小堆中只有一个节点，这个节点就是哈夫曼树的根。
d
Ddd
生成哈夫曼编码： 从根节点开始，向左走赋值 0，向右走赋值 1，直到叶节点。每个叶节点的路径就是该符号的哈夫曼编码。
8
边的类型
根据DFS的结果，标记每条边的类型：
树边（Tree Edges）：DFS中从一个顶点探索到另一个新顶点时形成的边。 后向边（Back Edges）前向边（Forward Edges）：连接一个顶点到其子孙但不在树中的边。 交叉边（Cross Edges）其余的边.
DFS-Visit 调用过程： 访问A： A变为灰色，discovery[A] = 1 时间计数器增加到2 访问A的邻接点B 访问B： B变为灰色，discovery[B] = 2 时间计数器增加到3 访问B的邻接点D 访问D： D变为灰色，discovery[D] = 3 时间计数器增加到4 访问D的邻接点C 访问C： C变为灰色，discovery[C] = 4 时间计数器增加到5 发现D已为灰色（访问中），故不再访问 C变为黑色，finish[C] = 5 时间计数器增加到6 回到D 继续访问D： 发现D已无其他未访问邻接点 D变为黑色，finish[D] = 6 时间计数器增加到7 回到B 继续访问B： 发现B已无其他未访问邻接点 B变为黑色，finish[B] = 7 时间计数器增加到8 回到A 继续访问A： 访问A的下一个邻接点E 访问E： E变为灰色，discovery[E] = 8 时间计数器增加到9 发现E无其他未访问邻接点 E变为黑色，finish[E] = 9 时间计数器增加到10 回到A 完成访问A： A变为黑色，finish[A] = 10 时间计数器增加到11 访问未访问的顶点： F变为灰色，discovery[F] = 11 时间计数器增加到12 访问F的邻接点G 访问G： G变为灰色，discovery[G] = 12 时间计数器增加到13 访问G的邻接点H 访问H： H变为灰色，discovery[H] = 13 时间计数器增加到14 发现H的邻接点F已为灰色（访问中），故不再访问 H变为黑色，finish[H] = 14 时间计数器增加到15 回到G 继续访问G： 发现G已无其他未访问邻接点 G变为黑色，finish[G] = 15 时间计数器增加到16 回到F 继续访问F： 发现F已无其他未访问邻接点 F变为黑色，finish[F] = 16
MST satisfies the greedy choice property: for any graph G = (V,E), let S ⊂ V be any subset of vertices, if (u, v) ∈ E is the least-weight edge connecting S to V − S, then (u, v) must be in the MST. Kruskal’s algorithm first makes disjoint sets for all vertices, then processes all edges in the increasing order of weights, when (u, v) is processed, if u and v are not in the same set yet, then (u, v) is added to the MST, and their sets are merged. Please use MST’s greedy choice property to prove that this is correct.
Answer: Since Kruskal’s algorithm processes all edges in the increasing order of weights, when (u,v) is being processed at time t, all the edges with lower weights must have been processed already. After Kruskal’s algorithm processes an edge, its two vertices will be put in the same disjoint set. At time t, if u and v are in different disjoint sets, let S be the disjoint set u belongs to. For an edge with lower weight than (u,v), its two vertices are either both in S, or both not in S, so it is not an edge connecting S to V − S. In other words, (u, v) must be the lowest weight edge connecting S with V − S, so it should be put in the MST.
Given a direct graph G = (V, E), if C1 and C2 are two strongly connected components (SCCs), let s and u be two vertices in C1, x and v be two vertices in C2, and there is an edge from u to v, and there may be other SCCs and other links. Suppose DFS starts at s, let f(·) represents the DFS finish time of a vertex, prove or disprove the following statements:
(a) (4 points) f(s) > f(x); (b) (4 points) f(u) > f(v); (c) (4 points) f(u) > f(x).
Hint: if you think the statement is always true, prove it is true; if you think the statement is wrong, you just need to come up with a counter-example to disprove it. You can use any theorem/statement we used in lectures.
Answer: (a) Yes.
Since DFS starts at s, s and u are in the same SCC, so there is path going from s to u, similarly, there must be a path from v to x, together with the link from u to v, we have a white path from s to x when DFS starts. According to the white path theorem, x will be a descendant of s in a DFS tree, f(s) > f(x).
(b) Yes.
Since u and v are in different SCCs, and there is an link from u to v, then there should not be any path from v back to u. (Otherwise the two SCCs will be merged into one SCC). If DFS visits u first, v is still white, then (u,v) is a white path, and v will be a descendant of u in a DFS tree, f(u) > f(v); If DFS visits v first, there is no white path from v to u, so u will not be a descendant of v in a DFS tree, and u will be discovered only after v is finished. Therefore, we have f(u) > d(u) > f(v).
(c) Yes.
Let y be the first vertex discovered by DFS in C2. When y is discovered, there is a white path from y to any other node in C2. So all the nodes in C2 are descendants of y in a DFS tree, and f(y) ≥ f(x); Similar tocase(b),thereisapathfromutoythroughv,andtherecannotbeapathfromybacktou. Ifyis discovered after u, when u is discovered, there is a white path from u through v to y, y will be a descendant of u in a DFS tree, and f(x) ≤ f(y) < f(u); If y is discovered before u, there is no white path from y to u, so u will not be a descendant of y in a DFS tree, and u will be discovered only after y is finished. Therefore, we have f(u) > d(u) > f(y) ≥ f(x). In both cases, we have f(u) > f(x).
Let A and B be two sequences of digits, each digit takes value from 0 to k − 1. If a common subsequence between A and B has l digits, it can be treated as an l-digit number. The largest common subsequence is the one with the largest value. For example, with k = 10, A = {1,9,2}, B={9,1,2}, the longest common subsequences are {1, 2} and {9, 2}, but the largest common subsequence is just {9, 2}.
(a) (6 points) Design a dynamic programming algorithm to find the largest common subsequence between two sequences of n and m digits respectively. Your algorithm should output the value of the largest common subsequence. What is the complexity of your algorithm?
(b) (4 points) Apply your algorithm to find the largest common subsequence between {1, 2, 3, 9, 4, 6, 7, 5} and {2,8,3,1,4,6,9,5}, with k = 10.
Answer: a) From the lecture, we know that any common subsequence between A[1···n] and B[1···m] must be one of the following:
(a) a common subsequence between A[1···n−1] and B[1···m]; (b) a common subsequence between A[1···n] and B[1···m−1];
(c) a common subsequence between A[1···n−1] and B[1···m−1] concatenated by x, if A[n] = B[m] = x. Let L[n, m] be the largest common subsequence between A[1 · · · n] and B[1 · · · m]. It satisfies the following
recurrence:
L[n,m]=max{L[n−1,m],L[n,m−1]}, ifA[n]̸=B[m] (1)L[n,m]=max{L[n−1,m],L[n,m−1],k∗L[n−1,m−1]+x}, ifA[n]=B[m]=x (2) Dynamic programming algorithm can be developed using the above recurrence, starting with base case of
L[i,0] = L[0,j] = 0, for 1 ≤ i ≤ n and for 1 ≤ j ≤ m.
The complexity of the algorithm is simply θ(nm).
In Homework 10, Q3, we developed a greedy algorithm for making changes with the smallest number of coins out of quarters (25¢), dimes (10¢), nickels (5¢), and pennies (1¢). Prove the greedy algorithm is optimal by following the three steps below:
(a) (3 points) greedy algorithm is optimal for making changes with only nickels (5¢), and pennies (1¢);
(b) (3 points) greedy algorithm is optimal for making changes with only dimes (10¢), nickels (5¢), and
pennies (1¢);
(c) (4 points) greedy algorithm is optimal for making changes with quarters (25¢), dimes (10¢), nickels
(5¢), and pennies (1¢)
Answer: a) To make changes for x cents, if an optimal solution is not greedy, i.E., the number of nickels is less than ⌊x/5⌋, then number of pennies will be larger than 5, by replacing 5 pennies with one nickel, the number of coins reduces by 4, contradiction! So optimal solution must be the greedy solution.
Answer: b) If x < 10, we will only use nickels and pennies, from a), greedy is optimal.
For x ≥ 10, if an optimal solution is not greedy, i.E., the number of dimes is less than ⌊x/10⌋, then the total value of nickels and pennies should be larger than or equal to 10; based on a), we will have at least 2 nickels, by replacing these two nickels with one dime, the number of coins reduces by 1, contradiction! So optimal solution must be the greedy solution.
Answer: c) If x < 25, we will only use dimes, nickels and pennies, from b), greedy is optimal.
if x ≥ 25, if an optimal solution is not greedy, then the total value y of dimes, nickels and pennies should belarger than or equal to 25:
1) if 25 ≤ y < 30, according to b), we will have at least two dimes, and one nickel, replace them with one quarter, the total number of coins reduces by 2; contradiction!
2) if y ≥ 30, according to b), we will have at least three dimes, replace them with one quarter plus one dime, the total number of coins reduces by 1; contradiction!
So optimal solution must be the greedy solution.
13. Given an unweighted directed graph G = (V, E), we define the Strongly Connected Component (SCC) distance from node u to node v as the least number of SCCs that one has to visit on the way from u to v. If u and v are in the same SCC, their SCC distance is zero, and if v is not reachable from u, the SCC distance from u to v is ∞.
(a) (8 points) design an O(|V | + |E|) algorithm to find the SCC distances from a given source node s to all the other nodes in G;
(b) (4 points) show that the SCC distance from any node u to any node v equals to the shortest path length from u to v if and only if G is a DAG;
(c) (4 points) if we further define the weighted SCC distance from u to v as the total number of nodes in all the visited SCCs on the way from u to v, design another O(|V | + |E|) algorithm to find the longest weighted SCC distances from a given source node s to all the other nodes in G.
(You can use any algorithm we learned in class without writing out the detailed algorithm.)
Answer: a) Let Gc = (Vc,Ec) be the component DAG for G, and Cu and Cv be the SCCs of u and v, respectively. The SCC distance from u to v is just the shortest path distance from Cu to Cv in Gc. The following is the algorithm:
1) Run Kosaraju/Tarjan’s algorithm to find SCCs of G, build the component DAG GC , complexity O(|V |+ |E |);
2) Run BFS, starting from Cs, in Gc to find the shortest paths to all the other SCCs complexity O(|V c| + |Ec|) = O(|V | + |E|),
3) Return shortest path distance from Cs to Cv as the SCC distance from s to v
The total complexity is O(|V | + |E|).
Answer: b) (⇒, ONLY IF) If there a cycle in G, all nodes on the cycle belong to the same SCC, SCC distances between them will be zero. So if G is not DAG, SCC distance is not the same as the shortest path length;
(⇐, IF) On the other hand, if G is a DAG, each node becomes an independent SCC, then Gc is isomorphic to G, the SCC distance equals the shortest path distance.
Answer: c) Let nC be the number of nodes in SCC C. In the component DAG Gc, assign −nC as the link weights for all links going to node C. Let Cs be the SCC of node s. For any other node v, find the shortest path distance d(Cs,Cv) from Cs to Cv in Gc using topological sort+one pass Bellman Ford relaxation, if d(Cs,Cv) = ∞, there is no path from s to v, the weighted SCC distance is 0, d(Cs,Cv) < 0, −d(Cs,Cv) is the weighted SCC distance. (since the link weights are all negative, if Cv is reachable from Cs, d(Cs,Cv) < 0 always.)
Finding shortest path algorithm in weighted DAG is O(|V c| + |Ec|) = O(|V | + |E|).
当然可以，这里是用英文总结的100个经典的与图论、动态规划、贪心算法、复杂性理论相关的判断题，带有一些中文的专业术语翻译。
### Graph Theory (图论)
1. For an undirected graph with \( n \) vertices, the maximum number of edges is \( n(n-1)/2 \).（T）
2. A connected undirected graph has exactly one minimum spanning tree.（F）
3. In a directed graph, a DFS tree contains no back edges.（F）
4. All bipartite graphs are 2-colorable.（T）
5. Topological sorting can be applied to any directed graph.（F）
6. BFS can only be used for undirected graphs.（F）
7. A graph’s minimum spanning tree is always unique.（F）
8. Strongly connected components of a graph can be found using DFS.（T）
9. A graph’s shortest path is always unique.（F）
10. If an undirected graph has \( n \) vertices and \( n \) edges, it must be connected.（F）
11. An Eulerian circuit exists in a graph if every vertex has an even degree.（T）
12. A Hamiltonian path exists in any complete graph.（T）
13. In a tree, the number of edges is always one less than the number of vertices.（T）
14. Dijkstra’s algorithm cannot handle negative weights.（T）
15. Bellman-Ford algorithm can handle graphs with negative weight edges.（T）
16. The Floyd-Warshall algorithm can be used to find the shortest paths between all pairs of vertices.（T）
17. Kruskal’s algorithm always produces the same minimum spanning tree as Prim’s algorithm for a given graph.（F）
18. A bipartite graph can have an odd-length cycle.（F）
19. All trees are bipartite.（T）
20. The adjacency matrix of an undirected graph is always symmetric.（T）
### Dynamic Programming (动态规划)
21. Dynamic programming can be used to solve any optimization problem.（F）
22. The Fibonacci sequence can be solved using dynamic programming.（T）
23. In the knapsack problem, the 0-1 knapsack problem can be solved using a greedy algorithm.（F）
24. Longest common subsequence problem can be solved using dynamic programming.（T）
25. In dynamic programming, overlapping subproblems must exist.（T）
26. Matrix chain multiplication can be optimized using dynamic programming.（T）
27. The coin change problem can be solved using dynamic programming.（T）
28. Dynamic programming is always more efficient than recursion.（F）
29. In dynamic programming, the optimal substructure property must hold.（T）
30. The edit distance between two strings can be found using dynamic programming.（T）
31. The traveling salesman problem can be solved in polynomial time using dynamic programming.（F）
32. The rod cutting problem can be solved using dynamic programming.（T）
33. The shortest path problem in a graph with negative weights can be solved using dynamic programming.（T）
34. Dynamic programming can solve the all-pairs shortest path problem.（T）
35. Subset sum problem can be solved using dynamic programming.（T）
36. The maximum subarray problem can be solved using dynamic programming.（T）
37. Dynamic programming is always space efficient.（F）
38. Dynamic programming can be used to solve the longest increasing subsequence problem.（T）
39. The knapsack problem’s fractional version can be solved using dynamic programming.（F）
40. Palindrome partitioning can be solved using dynamic programming.（T）
### Greedy Algorithms (贪心算法)
41. Dijkstra’s algorithm is a greedy algorithm.（T）
42. The activity selection problem can be solved using a greedy algorithm.（T）
43. Greedy algorithms always provide the optimal solution.（F）
44. The fractional knapsack problem can be solved using a greedy algorithm.（T）
45. The Huffman coding algorithm is a greedy algorithm.（T）
46. Prim’s algorithm for minimum spanning trees is a greedy algorithm.（T）
47. Kruskal’s algorithm for minimum spanning trees is a greedy algorithm.（T）
48. The coin change problem can be solved using a greedy algorithm for any set of coin denominations.（F）
49. Greedy algorithms are typically more efficient than dynamic programming.（T）
50. The traveling salesman problem can be solved using a greedy algorithm.（F）
51. Greedy algorithms can be used to solve the job sequencing problem.（T）
52. The interval scheduling maximization problem can be solved using a greedy algorithm.（T）
53. Greedy algorithms always involve sorting the input.（F）
54. The optimal substructure property is necessary for greedy algorithms.（T）
55. The knapsack problem’s 0-1 version can be solved using a greedy algorithm.（F）
56. The shortest path problem in a weighted graph with non-negative weights can be solved using a greedy algorithm.（T）
57. Greedy algorithms can be used to solve the minimum spanning tree problem.（T）
58. A greedy algorithm for the set cover problem always finds the optimal solution.（F）
59. Greedy algorithms make decisions by considering the future consequences.（F）
60. The single-source shortest path problem in a directed acyclic graph can be solved using a greedy algorithm.（T）
### Complexity Theory (复杂性理论)
61. NP-complete problems can be solved in polynomial time.（F）
62. If a problem is in P, it is also in NP.（T）
63. All NP problems can be reduced to NP-complete problems in polynomial time.（T）
64. The 3-SAT problem is NP-complete.（T）
65. P = NP is a solved problem.（F）
66. If a polynomial-time algorithm is found for an NP-complete problem, all NP problems can be solved in polynomial time.（T）
67. The traveling salesman problem is NP-hard.（T）
68. The Hamiltonian cycle problem is NP-complete.（T）
69. The problem of deciding whether a graph is bipartite is in P.（T）
70. If a problem is NP-hard, it must be in NP.（F）
71. The problem of determining the satisfiability of a Boolean formula is NP-complete.（T）
72. Polynomial-time reductions are used to show that problems are NP-complete.（T）
73. The clique problem is NP-complete.（T）
74. The problem of determining whether a number is prime is in P.（T）
75. The subset sum problem is NP-complete.（T）
76. The halting problem is undecidable.（T）
77. All problems in NP can be verified in polynomial time.（T）
78. The decision version of the knapsack problem is NP-complete.（T）
79. If a problem is NP-complete, it can be solved in polynomial time.（F）
80. NP-complete problems are a subset of NP problems.（T）
81. The vertex cover problem is NP-complete.（T）
82. The problem of determining whether a graph has a Hamiltonian path is NP-complete.（T）
83. The problem of determining whether a context-free grammar is ambiguous is undecidable.（T）
84. The problem of determining whether a graph is planar is in P.（T）
85. The problem of determining the chromatic number of a graph is NP-hard.（T）
86. NP-hard problems are at least as hard as NP-complete problems.（T）
87. The traveling salesman problem can be solved in polynomial time if the graph is unweighted.（F）
88. The longest path problem is NP-hard.（T）
89. The problem of determining whether a set of integers has a subset that sums to zero is NP-complete.（T）
90. The problem of determining the maximum flow in a flow network is in P.（T）
91. The minimum cut problem can be solved in polynomial time.（T）
92. The problem of determining whether a context-free grammar generates a particular string is in P.（T）
93. The problem of determining the minimum vertex cover of a graph is NP-hard.（T）
94. The Hamiltonian path problem is NP-hard.（T）
95. The problem of finding a maximal independent set in a graph is in P.（T）
96. The problem of determining whether two context-free grammars are equivalent is undecidable.（T）
97. The problem of determining whether a graph has an Eulerian path is in P.（T）
98. The problem of determining the minimum spanning tree of a graph is in P.（T）
99. The problem of determining the longest common subsequence of two strings is in P.（T）
100. The problem of determining whether a DFA accepts a given string is in P.（T）
这些判断题涵盖了图论、动态规划、贪心算法和复杂性理论的核心概念和常见考点。希望对你的备考有所帮助！