After the first run of Bubble Sort, it is possible that no element is placed in its final position. (2分)
If the inorder and the postorder traversal sequences of a binary tree have exactly the same order, then none of the nodes in the tree has a right subtree. (2分)
If 7 elements have been stored in a hash table of size 13 at positions { 0, 1, 3, 4, 9, 10, 12 }, and the hash function is . Then an empty spot can't be found when inserting the element 26 with quadratic probing. (2分)
If the most commonly used operations are to visit a random position and to insert and delete the last element in a linear list, then sequential storage works the fastest. (2分)
Given a binary search tree with 20 integer keys which include 10, 11, and 12, if 10 and 12 are on the same level, then 11 must be their common ancestor. (2分)
If there are less than 20 inversions in an integer array, the Quick Sort will be the best method among Quick Sort, Heap Sort and Insertion Sort. (2分)
The minimum spanning tree of a connected weighted graph with vertex set V={ A, B, C, D, E } and weight set W={ 1, 3, 2, 5, 2, 7, 9, 8, 4 } must be unique. (2分)
For a sequentially stored linear list of length , the time complexities for deleting the first element and inserting the last element are and , respectively. (2分)
The sum of the degrees of all the vertices in a connected graph must be an even number. (2分)
is . (2分)
The figure shows an AOV network. Which one of the following is a possible topological order of the network? (3分)
For a directed graph, comparing to the representation of the adjacency lists, the adjacency matrix representation is easier to: (3分)
Given a weighted graph as shown by the figure. Which one of the following statements is TRUE about its minimum spanning tree? (3分)
Given an undirected graph, and the edge set of a DFS from V0 as: { (V0,V1) , (V0,V4) , (V1,V2) , (V1,V3) , (V4,V5) , (V5,V6) }. Which one the following cannot be the sequence of another DFS? (3分)
Given a tree of degree 6. Suppose that the numbers of nodes of degrees 1, 2, 3, 4, 5, 6 are 5, 3, 2, 3, 2, 1, respectively. Then the number of leaf nodes must be: (3分)
Suppose that the level-order traversal sequence of a max-heap is {98, 72, 86, 60, 65, 12, 23, 50}. Use the linear algorithm to adjust this max-heap into a min-heap, and then run DeleteMin twice. The inorder traversal sequence of the resulting tree is: (3分)
For an in-order threaded binary tree, if the pre-order and in-order traversal sequences are B E A C F D
and A E C B D F
respectively, which pair of nodes' left links are both threads? (3分)
When inserting a new key a
into a binary search tree T
with 1022 nodes, the worst-case number of comparisons between a
and the keys already in T
is in the range of: (3分)
Given that the pushing sequence of a stack is { 1, 2, , } and popping sequence is { , , , }. If , how many different possible popping sequences can we obtain? (3分)
Suppose that an array of size m
is used to store a circular queue. If the head pointer front
and the current size variable size
are used to represent the range of the queue instead of front
and rear
, then the maximum capacity of this queue can be: (3分)
The inorder and the postorder traversal sequences of a binary tree are a b c d e f g
and b c a e g f d
, respectively. Then the preorder traversal sequences is: (3分)
Which one of the following is a possible postorder traversal sequence of a binary search tree? (3分)
If the hash values of keys are all the same, and linear probing is used to resolve collisions, then the minimum total number of probings must be __ to insert these keys . (3分)
Rehashing is required when an insertion to a hash table fails. Which of the following is NOT necessary to rehashing? (3分)
To sort { 8, 3, 9, 11, 2, 1, 4, 7, 5, 10, 6 } by Shell Sort, if we obtain ( 4, 2, 1, 8, 3, 5, 10, 6, 9, 11, 7 ) after the first run, and ( 1, 2, 3, 5, 4, 6, 7, 8, 9, 11, 10 ) after the second run, then the increments of these two runs must be __ , respectively. (3分)
Which one of the following is the expression tree corresponding to the postfix expression aef+*bc+*
? (3分)
Given the structure of a binary search tree (as shown in the figure), which one of the following insertion sequences is impossible? (3分)
Quick Sort can be implemented by a recursive function void Qsort( ElementType A[ ], int Left, int Right )
. If we are to implement the function Qsort()
in a non-recursive way with a stack, which of the following should be packed as the elements of the stack? (3分)
The maximum flow in the following network is: (3分)
A relation is defined on a set . If for any elements , and in , we have that if " " is true and " " is true, then " " must be true, then is said to be __ over . (3分)
Given an array a[]
of n
integers, the function MissingMax
is to find and return the maximum negative integer which is NOT in the array. For example, given { -3, -1, 8, 1, 0 }, -2 is the largest negative integer which is missing.
int MissingMax( int a[], int n )
{
int i, j, max, missing = -1;
for( i=0; i<n; i++ ){
max = i;
for( j = i+1; j < n; j++ )
if ((3分)) max = j;
if ( max != i ) swap(a[i], a[max]);
if ( a[i] == missing ) missing--;
else if ( a[i] < missing ) (3分);
}
return missing;
}
序号 | 结果 | 得分 |
---|---|---|
0 | 答案正确 | 3 |
1 | 答案正确 | 3 |
The function is to turn an array A[]
of N
elements into a min-heap.
#define leftchild(i) ( 2*(i)+1 )
void BuildMinHeap( ElementType A[], int N )
{ int i, j, child;
ElementType Tmp;
for ( i = (N-1)/2; i >= 0; i-- ) {
j = i;
for ( Tmp = A[j]; leftchild(j) < N; j = child ) {
child = leftchild(j);
if ((2分))
child ++;
if ((2分)) A[j] = A[child];
else break;
}
(2分);
}
}
Thanks to DOU Yan from Yanshan University for the correction!
序号 | 结果 | 得分 |
---|---|---|
0 | 答案正确 | 2 |
1 | 答案正确 | 2 |
2 | 答案正确 | 2 |
Write a program to find the weighted shortest distances from any vertex to a given source vertex in a digraph. It is guaranteed that all the weights are positive.
void ShortestDist( MGraph Graph, int dist[], Vertex S );
where MGraph
is defined as the following:
typedef struct GNode *PtrToGNode;
struct GNode{
int Nv;
int Ne;
WeightType G[MaxVertexNum][MaxVertexNum];
};
typedef PtrToGNode MGraph;
The shortest distance from V to the source S is supposed to be stored in dist[V]. If V cannot be reached from S, store -1 instead.
#include <stdio.h>
#include <stdlib.h>
typedef enum {false, true} bool;
#define INFINITY 1000000
#define MaxVertexNum 10 /* maximum number of vertices */
typedef int Vertex; /* vertices are numbered from 0 to MaxVertexNum-1 */
typedef int WeightType;
typedef struct GNode *PtrToGNode;
struct GNode{
int Nv;
int Ne;
WeightType G[MaxVertexNum][MaxVertexNum];
};
typedef PtrToGNode MGraph;
MGraph ReadG(); /* details omitted */
void ShortestDist( MGraph Graph, int dist[], Vertex S );
int main()
{
int dist[MaxVertexNum];
Vertex S, V;
MGraph G = ReadG();
scanf("%d", &S);
ShortestDist( G, dist, S );
for ( V=0; V<G->Nv; V++ )
printf("%d ", dist[V]);
return 0;
}
/* Your function will be put here */
7 9
0 1 1
0 5 1
0 6 1
5 3 1
2 1 2
2 6 3
6 4 4
4 5 5
6 5 12
2
-1 2 0 13 7 12 3
#ifdef PINTIA #include <stdio.h> #include <stdlib.h> typedef enum {false, true} bool; #define INFINITY 1000000 #define MaxVertexNum 10 /* maximum number of vertices */ typedef int Vertex; /* vertices are numbered from 0 to MaxVertexNum-1 */ typedef int WeightType; typedef struct GNode *PtrToGNode; struct GNode{ int Nv; int Ne; WeightType G[MaxVertexNum][MaxVertexNum]; }; typedef PtrToGNode MGraph; MGraph ReadG(); /* details omitted */ void ShortestDist( MGraph Graph, int dist[], Vertex S ); int main() { int dist[MaxVertexNum]; Vertex S, V; MGraph G = ReadG(); scanf("%d", &S); ShortestDist( G, dist, S ); for ( V=0; V<G->Nv; V++ ) printf("%d ", dist[V]); return 0; } /* Your function will be put here */ #endif int visited[MaxVertexNum] = {0}; void ShortestDist( MGraph Graph, int dist[], Vertex S ) { for (int i = 0; i < Graph->Nv; i++) { dist[i] = Graph->G[S][i]; } visited[S] = 1; // Iter Start for (int i = 0; i < Graph->Nv; i++) { // Find the smallest unknown vertex int min = INFINITY, minDist = INFINITY; for (int j = 0; j < Graph->Nv; j++) { if (visited[j]) continue; if (dist[j] < minDist) { min = j; minDist = dist[j]; } } if (minDist == INFINITY) continue; // break exit visited[min] = 1; for (int j = 0; j < Graph -> Nv; j++) { if (visited[j]) continue; if (dist[j] > dist[min] + Graph->G[min][j]) dist[j] = dist[min] + Graph->G[min][j]; } } dist[S] = 0; for (int i = 0; i < Graph->Nv; i++) { if (dist[i] == INFINITY) { dist[i] = -1; } } }
测试点 | 结果 | 得分 | 耗时 | 内存 |
---|---|---|---|---|
0 | 答案正确 | 4 | 3 ms | 384 KB |
1 | 答案正确 | 3 | 2 ms | 256 KB |
2 | 答案正确 | 1 | 2 ms | 384 KB |
a.c: In function ‘ReadG’: a.c:55:2: warning: ignoring return value of ‘scanf’, declared with attribute warn_unused_result [-Wunused-result] scanf("%d", &Nv); /* 读入顶点个数 */ ^~~~~~~~~~~~~~~~ a.c:58:2: warning: ignoring return value of ‘scanf’, declared with attribute warn_unused_result [-Wunused-result] scanf("%d", &(Graph->Ne)); /* 读入边数 */ ^~~~~~~~~~~~~~~~~~~~~~~~~ a.c:63:7: warning: ignoring return value of ‘scanf’, declared with attribute warn_unused_result [-Wunused-result] scanf("%d %d %d", &E->V1, &E->V2, &E->Weight); ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ a.c: In function ‘main’: a.c:80:5: warning: ignoring return value of ‘scanf’, declared with attribute warn_unused_result [-Wunused-result] scanf("%d", &S); ^~~~~~~~~~~~~~~