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分)
In Union/Find algorithm, if Unions are done by size, the depth of any node must be no more than , but not . (3分)
is . (3分)
For a sequentially stored linear list of length , the time complexities for query and insertion are: (5分)
If a binary search tree of nodes is complete, which one of the following statements is FALSE? (5分)
Let be a non-negative integer representing the size of input. The time complexity of the following piece of code is: (5分)
x = 0;
while ( n >= (x+1)*(x+1) )
x = x+1;
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分)
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分)
Given the popping sequence of a stack as {a, b, c, d, e}. Among the following, the impossible pushing sequence is: (5分)
How many distinct topological sequences are there in the following DAG?(5分)
If graph G is NOT connected and has 20 edges, then it must have at least __ vertices. (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 217 nodes? (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分)
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分)
Which one of the following is the data structure that is best represented by the above picture? (1分)
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分)
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 | 编译错误 | 0 |
1 | 未作答 | 0 |
2 | 编译错误 | 0 |
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 | 编译错误 | 0 |
1 | 编译错误 | 0 |
2 | 答案错误 | 0 |
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 |