The sum of the degrees of all the vertices in a connected graph must be an even number. (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 parent. (2分)
If a linear list is represented by a linked list, the addresses of the elements in the memory must be consecutive. (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分)
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分)
is the same as . (2分)
After the first run of Bubble Sort, it is possible that no element is placed in its final position. (2分)
"Circular Queue" is defined to be a queue implemented by a circularly linked list or a circular array. (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分)
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分)
Suppose that the level-order traversal sequence of a min-heap is {8, 38, 25, 58, 52, 82, 70, 60}. Use the linear algorithm to adjust this min-heap into a max-heap, and then run DeleteMax twice. The inorder traversal sequence of the resulting tree is: (3分)
Suppose that an array of size m
is used to store a circular queue. If the front position is front
and the current size is size
, then the rear element must be at: (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 the structure of a binary search tree (as shown in the figure), which one of the following insertion sequences is impossible? (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分)
For a directed graph, comparing to the representation of the adjacency lists, the adjacency matrix representation is easier to: (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 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分)
The inorder and the postorder traversal sequences of a binary tree are 1 2 3 4 5 6 7
and 2 3 1 5 7 6 4
, respectively. Then the preorder traversal sequences is: (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 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分)
Which one of the following is the expression tree corresponding to the postfix expression aef+*bc+*
? (3分)
From the given graph shown by the figure, how many different topological orders can we obtain? (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分)
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分)
Which one of the following is a possible postorder traversal sequence of a binary search tree? (3分)
To sort { 8, 3, 9, 11, 2, 1, 4, 7, 5, 10, 6 } by Shell Sort, if we obtain ( 1, 3, 7, 5, 2, 6, 4, 9, 11, 10, 8 ) after the first run, and ( 1, 3, 2, 5, 4, 6, 7, 9, 8, 10, 11 ) after the second run, then the increments of these two runs must be __ , respectively. (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分)
Rehashing is required when an insertion to a hash table fails. Which of the following is NOT necessary to rehashing? (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;
}
The function is to turn an array A[]
of N
elements into a max-heap.
#define leftchild(i) ( 2*(i)+1 )
void BuildMaxHeap( 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!
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