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分)
In a directed graph, the sum of the in-degrees and out-degrees of all the vertices is twice the total number of edges. (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, 1, 7, 9, 8, 4} must be unique. (2分)
If the preorder and the postorder traversal sequences of a binary tree have exactly the opposite orders, then none of the nodes in the tree has two subtrees. (2分)
If there are less than 20 inversions in an integer array, then Insertion Sort will be the best method among Quick Sort, Heap Sort and Insertion Sort. (2分)
After the first run of Bubble Sort, it is possible that no element is placed in its final position. (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分)
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分)
If 7 elements have been stored in a hash table of size 13 at positions { 0, 1, 2, 4, 5, 10, 11 }, and the hash function is . Then an empty spot can't be found when inserting the element 40 with quadratic probing. (2分)
is the same as . (2分)
Rehashing is required when an insertion to a hash table fails. Which of the following is NOT necessary to rehashing? (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分)
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分)
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分)
When inserting a new key a
into a binary search tree T
with 1025 nodes, the worst-case number of comparisons between a
and the keys already in T
is in the range of: (3分)
Given a tree of degree 6. Suppose that the numbers of nodes of degrees 1, 2, 3, 4, 5, 6 are 3, 5, 2, 3, 1, 2, respectively. Then the number of leaf nodes must be: (3分)
Given the structure of a binary search tree (as shown in the figure), which one of the following insertion sequences is impossible? (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分)
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分)
The maximum flow in the following network is: (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分)
A relation is defined on a set . If for every element in , " " is always true, then is said to be __ over . (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' right links are both threads? (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分)
Which one of the following is the expression tree corresponding to the postfix expression aef+*bc+*
? (3分)
Which one of the following is a possible postorder traversal sequence of a binary search tree? (3分)
For a directed graph, comparing to the representation of the adjacency lists, the adjacency matrix representation is easier to: (3分)
From the given graph shown by the figure, how many different topological orders can we obtain? (3分)
Given a weighted graph as shown by the figure. Which one of the following statements is TRUE about its minimum spanning 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分)
Given an array a[]
of n
integers, the function MissingMin
is to find and return the minimum positive integer which is NOT in the array. For example, given { 3, -1, 8, 1, 0 }, 2 is the smallest positive integer which is missing.
int MissingMin( int a[], int n )
{
int i, j, min, missing=1;
for( i=0; i<n; i++ ){
min = i;
for( j = i+1; j < n; j++ )
if ((3分)) min = j;
if ( min != i ) swap(a[i], a[min]);
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
void ShortestDist( MGraph Graph, int dist[], Vertex S ){ int known[MaxVertexNum]; int i,j,min,mini; for(i=0;i<MaxVertexNum;i++){ known[i]=0; dist[i]=INFINITY; } dist[S]=0; while(1){ min=INFINITY; for(i=0;i<Graph->Nv;i++){ if(known[i]==1)continue; if(dist[i]<min){ min=dist[i]; mini=i; } } if(min==INFINITY)break; known[mini]=1; for(i=0;i<Graph->Nv;i++){ if(known[i]==1)continue; if(Graph->G[mini][i]<=0||Graph->G[mini][i]==INFINITY)continue; if(dist[i]>dist[mini]+Graph->G[mini][i]){ dist[i]=dist[mini]+Graph->G[mini][i]; } } } for(i=0;i<Graph->Nv;i++){ if(dist[i]==INFINITY)dist[i]=-1; } return; }
测试点 | 结果 | 得分 | 耗时 | 内存 |
---|---|---|---|---|
0 | 答案正确 | 4 | 2 ms | 256 KB |
1 | 答案正确 | 3 | 2 ms | 280 KB |
2 | 答案正确 | 1 | 2 ms | 256 KB |
a.c: In function ‘ShortestDist’: a.c:91:11: warning: unused variable ‘j’ [-Wunused-variable] int i,j,min,mini; ^ 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); ^~~~~~~~~~~~~~~