In a directed graph, the sum of the in-degrees must be equal to the sum of the out-degrees of all the vertices. (3分)
If a linear list is represented by a linked list, the addresses of the elements in the memory must be consecutive. (3分)
ADT is the abbreviation for Abstract Data Type in the textbook of data structures. (3分)
is . (3分)
In Union/Find algorithm, if Unions are done by size, the depth of any node must be no more than , but not . (3分)
Given the shape of a binary tree shown by the figure below. If its inorder traversal sequence is { e
, a
, c
, b
, d
, g
, f
}, then the node on the same level of c
must be: (5分)
Which one of the following is the data structure that is best represented by the above picture? (1分)
If besides finding the shortest path from S
to every other vertices, we also need to count the number of different shortest paths, we can modify the Dijkstra algorithm in the following way: add an array count[]
so that count[V]
records the number of different shortest paths from S
to V
. Then count[V]
shall be initialized as: (5分)
For the following function
int func ( int n )
{ int i = 0, sum = 0;
while ( sum < n ) sum += ++i;
return i;
}
the time complexity is: (5分)
If a binary search tree of nodes is also a complete binary tree, then among the following, which one is FALSE? (5分)
If graph G is NOT connected and has 14 edges, then it must have at least __ vertices. (5分)
How many distinct topological sequences are there in the following DAG?(5分)
Given the popping sequence of a stack as {1, 2, 3, 4, 5}. Among the following, the impossible pushing sequence is: (5分)
A full tree of degree 3 is a tree in which every node other than the leaves has 3 children. How many leaves does a full tree of degree 3 have if it has 127 nodes? (5分)
For a sequentially stored linear list of length , the time complexities for query and insertion are: (5分)
The following figure shows the AOE network of a project with 8 activities. The earliest and the latest completion times of the activity d
are __, respectively. (5分)
Since the speed of a printer cannot match the speed of a computer, a buffer is designed to temperarily store the data from a computer so that later the printer can retrieve data in order. Then the proper structure of the buffer shall be a: (5分)
The array representation of the disjoint sets is given by { 2, –4, 2, 2, -3, 5, 6, 9, -2 }. Keep in mind that the elements are numbered from 1 to 9. After invoking Union(Find(7), Find(9)) with union-by-size, which elements will be changed in the resulting array? (4分)
Please fill in the blanks in the program which deletes a given element at position p
from a min-heap H
.
Deletion ( PriorityQueue H, int p ) /* delete the element H->Elements[p] */
{
ElementType temp;
int child;
temp = H-> Elements[ H->Size-- ];
if ( temp < H->Elements[p] ) {
while ( (p != 1) && (temp < H->Elements[p/2]) ) {
(3分);
p /= 2;
}
}
else {
while( (child = 2*p) <= H->Size) {
if ( child != H->Size && (3分) )
child ++;
if ( (3分) ) {
H->Elements[p] = H->Elements[child];
p = child;
}
else
break;
}
}
H->Elements[p] = temp;
}
序号 | 结果 | 得分 |
---|---|---|
0 | 答案正确 | 3 |
1 | 答案正确 | 3 |
2 | 答案正确 | 3 |
The function is to return the reverse linked list of L
, with a dummy header.
List Reverse( List L )
{
Position Old_head, New_head, Temp;
New_head = NULL;
Old_head = L->Next;
while ( Old_head ) {
Temp = Old_head->Next;
(3分);
New_head = Old_head;
Old_head = Temp;
}
(3分);
return L;
}
序号 | 结果 | 得分 |
---|---|---|
0 | 答案正确 | 3 |
1 | 答案正确 | 3 |
The function Dijkstra
is to find the shortest path from Vertex S
to every other vertices in a given Graph
. The distances are stored in dist[]
, and path[]
records the paths. The MGraph
is defined as the following:
typedef struct GNode *PtrToGNode;
struct GNode{
int Nv; /* Number of vertices */
int Ne; /* Number of edges */
WeightType G[MaxVertexNum][MaxVertexNum]; /* adjacency matrix */
};
typedef PtrToGNode MGraph;
void Dijkstra( MGraph Graph, int dist[], int path[], Vertex S )
{
int collected[MaxVertexNum];
Vertex V, W;
for ( V=0; V<Graph->Nv; V++ ) {
dist[V] = Graph->G[S][V];
path[V] = -1;
collected[V] = false;
}
dist[S] = 0;
collected[S] = true;
while (1) {
V = FindMinDist( Graph, dist, collected );
if ( V==ERROR ) break;
collected[V] = true;
for( W=0; W<Graph->Nv; W++ )
if ( collected[W]==false && Graph->G[V][W]<INFINITY ) {
if ( (4分) ) {
dist[W] = (3分);
path[W] = (3分);
}
}
} /* end while */
}
序号 | 结果 | 得分 |
---|---|---|
0 | 答案正确 | 4 |
1 | 答案正确 | 3 |
2 | 答案正确 | 3 |