19-20年期中考试试卷
is .
In Union/Find algorithm, if Unions are done by size, the depth of any node must be no more than , but not .
If a linear list is represented by a 1-dimensional array, the addresses of the elements in the memory must be consecutive.
ADT is the abbreviation for Abstract Data Type in the textbook of data structures.
In a directed graph, the sum of the in-degrees must be equal to the sum of the out-degrees of all the vertices.
If a binary search tree of nodes is also a complete binary tree, then among the following, which one is FALSE?
The following figure shows the AOE network of a project with 8 activities. The earliest and the latest start times of the activity d are __, respectively.
Which one of the following is the data structure that is best represented by the above picture?
For a sequentially stored linear list of length , the time complexities for query and insertion are:
If graph G is NOT connected and has 27 edges, then it must have at least ____ vertices.
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?
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:
Let be a non-negative integer representing the size of input. The time complexity of the following piece of code is:
x = 0;
while ( n >= (x+1)*(x+1) )
x = x+1;
From the given graph shown by the figure, how many different topological orders can we obtain?
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:
Given the shape of a binary tree shown by the figure below. If its postorder traversal sequence is { e, a, c, b, d, f }, then the node on the same level of b must be:
The array representation of the disjoint sets is given by {2, –4, 2, 3, -3, 5, 6, 9, -2}. Keep in mind that the elements are numbered from 1 to 9. After invoking Union(Find(4), Find(6)) with union-by-size, which elements will be changed in the resulting array?
Given the popping sequence of a stack as {1, 2, 3, 4, 5}. Among the following, the impossible pushing sequence is:
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 */
}
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;
}
Please fill in the blanks in the program which deletes a given element at position p from a max-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;
}