Arbori Cu Radacina
Test sumativ la capitolul arbori
Questions and Answers
- 1.
Un arbore cu rădăcină, cu 9 noduri, numerotate de la 1 la 9, este memorat cu ajutorul vectorului „de taţi” t=(9,3,4,7,3,9,0,7,2). Care este numărul minim de noduri ce trebuie eliminate pentru ca lungimea celui mai lung lanţ elementar, cu o extremitate în rădăcină, să fie 3 şi subgraful obţinut să fie tot arbore?
- A.
4
- B.
3
- C.
2
- D.
5
Correct Answer
B. 3Explanation
The given question is asking for the minimum number of nodes that need to be removed from the tree in order to have a longest path with one end at the root and a length of 3, while still maintaining the tree structure. To solve this problem, we can start by identifying the longest path from the root, which is 9-3-7-7-2. Since the length of this path is already 4, we need to remove at least one node from this path to make it 3. By removing any of the nodes 7, 3, or 2, we can achieve a longest path of length 3 with one end at the root. Therefore, the correct answer is 3.Rate this question:
-
- 2.
Un arbore cu rădăcină, cu 9 noduri, numerotate de la 1 la 9, este memorat cu ajutorul vectorului „de taţi” t=(9,3,4,7,3,9,0,7,2). Mulţimea tuturor nodurilor de tip frunză este:
- A.
{8, 6, 1, 5}
- B.
{1, 6}
- C.
{8}
- D.
{1, 6, 8}
Correct Answer
A. {8, 6, 1, 5}Explanation
The given vector "de taţi" represents the parent-child relationship in the tree. The index of each element represents the node number, and the value at that index represents the parent node of that node. In this case, the parent of node 1 is node 9, the parent of node 2 is node 3, and so on. The leaf nodes in a tree are the nodes that do not have any children. By looking at the given vector, we can see that nodes 1, 5, 6, and 8 do not have any children, making them the leaf nodes of the tree. Therefore, the correct answer is {8, 6, 1, 5}.Rate this question:
-
- 3.
Se consideră arborele cu 12 noduri, numerotate de la 1 la 12, definit prin următorul vector „de taţi”: (4, 8, 0, 3, 10, 1, 8, 3, 2, 4, 7, 10). Care dintre nodurile arborelui au exact un descendent direct (fiu) ?
- A.
6, 9, 11
- B.
5, 12, 6, 9, 11
- C.
1, 2, 7
- D.
10, 1, 2, 7
Correct Answer
C. 1, 2, 7Explanation
The nodes 1, 2, and 7 have exactly one direct descendant (child) in the given tree. This can be determined by examining the "parent" vector. Node 1 is the parent of node 6, node 2 is the parent of node 9, and node 7 is the parent of node 11.Rate this question:
-
- 4.
Fie un arborele cu rădăcină, cu 9 noduri, numerotate de la 1 la 9. Care este vectorul „de taţi” al acestui arbore ştiind că nodurile 1, 2, 3, 4 ,5, 6, 7, 8 au exact câte un descendent direct (fiu)?
- A.
(1,2,3,4,5,6,7,8)
- B.
(1,2,3,4,5,6,7,8,9)
- C.
(0,1,2,3,4,5,6,7,8)
- D.
(0,1,2,3,4,5,6,7,8,9)
Correct Answer
C. (0,1,2,3,4,5,6,7,8)Explanation
The vector "de taţi" represents the parent of each node in the tree. Since the nodes 1 to 8 have exactly one direct descendant, their parent will be the previous node in the sequence. For example, node 2 will have node 1 as its parent, node 3 will have node 2 as its parent, and so on. Therefore, the vector "de taţi" for this tree will be (0,1,2,3,4,5,6,7,8).Rate this question:
-
- 5.
Se consideră un arbore G, cu rădăcină, memorat cu ajutorul vectorului de „taţi” următor: T=(2,0,4,2,4,7,2). Care dintre următoarele afirmaţii este adevărată ?
- A.
Nodurile 1,4 şi 6 sunt fraţi.
- B.
G este conex şi prin eliminarea unei muchii oarecare din G, graful obţinut nu este conex.
- C.
Prin eliminarea muchiei [6,7] se obţine un graf parţial, conex.
- D.
Arborele G are 5 frunze.
Correct Answer
B. G este conex şi prin eliminarea unei muchii oarecare din G, graful obţinut nu este conex.Explanation
The given answer states that G is connected and by removing any edge from G, the resulting graph is not connected. This means that there is a path between any two nodes in G and removing an edge would disconnect the graph. This can be inferred from the fact that the given vector of "fathers" represents a rooted tree, where each node has a unique parent except for the root. In a rooted tree, removing any edge would create two separate trees, thus disconnecting the graph.Rate this question:
-
- 6.
Care este vectorul de ”taţi” asociat arborelui cu rădăcină din figura alăturată în care nodul 5 este nodul rădăcină?
- A.
[1,0,2,5,2]
- B.
[2,5,2,5,0]
- C.
[2,0,1,5,0]
- D.
[2,5,2,1,0]
Correct Answer
B. [2,5,2,5,0]Explanation
The vector represents the parent nodes of each node in the tree. Starting from the root node, the parent of node 1 is node 2, the parent of node 2 is node 5, the parent of node 5 is node 2, and the parent of node 0 is node 5. Therefore, the correct answer is [2,5,2,5,0].Rate this question:
-
- 7.
Care este vectorul de ”taţi” asociat arborelui cu rădăcină din figura alăturată în care nodul 1 este nodul rădăcină?
- A.
[3,1,0,3,3,4,4]
- B.
[0,1,1,3,3,4,4]
- C.
[3,1,0,3,3,2,2]
- D.
[0,2,2,3,3,4,4]
Correct Answer
B. [0,1,1,3,3,4,4]Explanation
The correct answer is [0,1,1,3,3,4,4] because the vector represents the parent nodes of each node in the tree. Starting from the root node 1, the parent nodes of the other nodes are as follows: node 2 has parent 0, node 3 has parent 1, node 4 has parent 1, node 5 has parent 3, and node 6 and 7 both have parent 4. Therefore, the correct vector is [0,1,1,3,3,4,4].Rate this question:
-
- 8.
Un arbore cu rădăcină având 8 noduri, numerotate de la 1 la 8, este memorat cu ajutorul vectorului de ”taţi” t=(8,8,0,3,4,3,4,6). Care sunt descendenţii nodului 4?
- A.
{5,7}
- B.
{3,5,7}
- C.
{3}
- D.
{1,2,3}
Correct Answer
A. {5,7}Explanation
The given array represents the parent-child relationship in the tree. The first element of the array represents the parent of node 1, the second element represents the parent of node 2, and so on. In this case, node 4 has two children, which are nodes 5 and 7. Therefore, the descendants of node 4 are {5,7}.Rate this question:
-
- 9.
Care este numărul de noduri ale unui arbore cu 100 de muchii?
- A.
98
- B.
100
- C.
99
- D.
101
Correct Answer
D. 101Explanation
An arbore (tree) is a connected acyclic graph. In a tree, the number of nodes is always one more than the number of edges. Therefore, if the tree has 100 edges, it will have 101 nodes.Rate this question:
-
- 10.
Se consideră un arbore G, cu rădăcină, memorat cu ajutorul vectorului de „taţi” următor: T=(2,0,4,2,4,7,2). Care dintre următoarele afirmaţii este adevărată?
- A.
Nodurile 1,4 şi 6 sunt fraţi.
- B.
Arborele G are 5 frunze.
- C.
Prin eliminarea muchiei [6,7] se obţine un graf parţial, conex.
- D.
G este conex şi prin eliminarea unei muchii oarecare din G, graful obţinut nu este conex.
Correct Answer
D. G este conex şi prin eliminarea unei muchii oarecare din G, graful obţinut nu este conex.Explanation
The given answer states that G is connected and by removing any edge from G, the resulting graph is not connected. This can be deduced from the fact that the tree is represented by the parent vector T, which indicates the parent of each node. In a connected tree, there is a path between any pair of nodes. Therefore, removing any edge will disconnect the graph.Rate this question:
-
- 11.
Se consideră un arbore cu rădăcină, cu 100 noduri, numerotate de la 1 la 100. Dacă nodul 13 are exact 14 fraţi şi nodul 100 este tatăl nodului 13, care este numărul total de descendenţi direcţi (fii) ai nodului 100?
- A.
13
- B.
14
- C.
12
- D.
15
Correct Answer
B. 14 -
- 12.
Dacă T este un arbore cu rădăcină, cu 100 de noduri, care este numărul minim de frunze pe care le poate avea T?
- A.
99
- B.
100
- C.
1
- D.
2
Correct Answer
C. 1Explanation
In a rooted tree, every node except the root has exactly one parent. Since there are 100 nodes in the given tree, there must be 99 nodes that have a parent. Therefore, the minimum number of leaves that the tree can have is 1.Rate this question:
-
- 13.
Fie T un arbore cu rădăcină. Arborele are 8 noduri numerotate de la 1 la 8 şi este descris prin următorul vector „de taţi”:(3,5,0,3,3,5,5,5).Care este nodul cu cei mai mulţi descendenţi direcţi (fii)?
- A.
3
- B.
1
- C.
5
- D.
2
Correct Answer
C. 5Explanation
The given vector "de taţi" represents the parent-child relationship in the tree. Each element in the vector represents the parent of the corresponding node. In this case, node 1 has parent 3, node 2 has parent 5, node 3 has parent 0 (which means it is the root), node 4 has parent 3, node 5 has parent 3, node 6 has parent 5, node 7 has parent 5, and node 8 has parent 5. The node with the most direct descendants (children) is node 5, as it has a total of 4 direct descendants (nodes 2, 6, 7, and 8).Rate this question:
-
- 14.
Se consideră un graf orientat cu 5 vârfuri şi 8 arce. Care dintre următoarele şiruri de numere poate fi şirul gradelor exterioare ale vârfurilor acestui graf?
- A.
2, 3, 1, 1, 1
- B.
1, 0, 1, 1, 1, 1
- C.
2, 2, 6, 5, 1
- D.
1, 1, 0, 2, 1
Correct Answer
A. 2, 3, 1, 1, 1Explanation
The given answer, 2, 3, 1, 1, 1, represents the sequence of the outdegrees of the vertices in the directed graph. Since the graph has 5 vertices and 8 arcs, each vertex must have an outdegree equal to the sum of the outdegrees of all the arcs connected to it. Therefore, the sum of the outdegrees of all the vertices must be equal to the total number of arcs, which is 8. The given answer satisfies this condition, as the sum of the numbers in the sequence is indeed 8.Rate this question:
-
- 15.
Care dintre nodurile arborelui din figura alăturată pot fi considerate ca fiind rădăcină astfel încât în arborele cu rădăcină rezultat fiecare nod să aibă cel mult doi descendenţi direcţi?
- A.
{4,6,7, 8, 9, 10}
- B.
{4,6,7, 8}
- C.
{1,2,3,4}
- D.
{7, 8, 9, 10}
Correct Answer
A. {4,6,7, 8, 9, 10}Explanation
The set {4,6,7, 8, 9, 10} can be considered as the root of the tree because it contains all the nodes in the other sets. In order for each node to have at most two direct descendants, the root must have all the nodes in the tree. Therefore, the set {4,6,7, 8, 9, 10} satisfies this condition and can be considered as the root.Rate this question:
-
- 16.
Pentru reprezentarea unui arbore cu rădăcină, cu 9 noduri, etichetate cu numerele naturalede la 1 la 9, se utilizează vectorul de “taţi”: T=(5,0,2,7,3,3,2,4,7). Din câte muchiieste format un lanţ elementar de lungime maximă, în arborele dat?
- A.
2
- B.
5
- C.
6
- D.
3
Correct Answer
C. 6 -
- 17.
Fie arborele din imaginea alaturate. Care este succesiunea de noduri obtinuta prin parcurgerea arborelui in INORDINE ?
- A.
1, 3, 4, 6, 7, 8, 10, 13, 14
- B.
8, 3, 1, 6, 4, 7, 10, 14, 13
- C.
1, 4, 7, 6, 3, 13, 14, 10, 8
- D.
13, 3, 4, 1, 6,8, 10, 1, 14
Correct Answer
A. 1, 3, 4, 6, 7, 8, 10, 13, 14Explanation
The correct answer is the sequence of nodes obtained by traversing the tree in INORDER is 1, 3, 4, 6, 7, 8, 10, 13, 14.Rate this question:
-
Back to top