During sorting (25, 21, 47, 15, 27, 68, 35, 20) in ascending order (升序) with the iterative version of Mergesort, (15, 21, 25, 47, 20, 27, 35, 68) is the result of the second run.
The inorder traversal sequence of any max-heap must be in sorted order.
For a connected graph, if there are exactly two vertices having odd degree, we can find an Euler circuit that visits every vertex exactly once by starting from one of its odd-degree vertices.
The average run time and the extra space of Heapsort for sorting elements are and , respectively.
For a binary tree, if its pre-order travel sequence is { 4, 2, 1, 3, 6, 5, 7 }, and its in-order travel sequence is { 1, 2, 3, 4, 5, 6, 7 }, then 4 is the parent of 2.
In most restaurants, we follow one principle called "First come, first served". This principle can be implemented by a queue.
The storage size of a graph using the adjacency matrix is only related to the number of vertices but has nothing to do with the number of edges.
In hashing, when the loading density approaches 1, the operarion INSERTION will be seriously slowed down if the separate chaining method is used to solve collisions.
If a general tree T is converted into a binary tree BT, then the BT's pre-order traversal has the same sequence as that of the post-order traversal of T.
Consider two programs with time complexities being and . then program 2 must run faster than program 1.
Given S = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11 } and 8 equivalence relations: 5~6,7~8,9~10,2~6,3~8,6~8,1~8,1~5. After invoking successively these relations with union-by-size(if the two sizes are equal, the smaller element will be the root)and path compression, which one of the following statements is false?
Given a binary tree, if its Pre-order traversal is {A,B,C,D,E,G,F} and the Post-order traversal is {B,D,G,F,E,C,A}, then which one is its In-order traversal?
In a weighted undirected graph, if the length of the shortest path from v1
to v0
is 14, and there exists an edge of weight 1 between v2
and v1
, then which one of the following is correct?
One of the following algorithms: Selection sort, Shell sort, Insertion sort, is applied to sort the sequence (2, 12, 16, 88, 1, 5, 10)in ascending order. If the resulting sequences of the first two runs are (2, 12 , 16, 10, 1, 5, 88) and (2, 12, 5, 10, 1, 16, 88), then after the third run, the number in front of 5 must be ____ .
The following list is a series of operations for a stack:
Which is the correct pop-up sequence?
Which one of the following is impossible to be the insertion sequence of the given binary search tree?
The following binary tree is called an expression tree. Which one is the arithmetic expression that this tree represents?
Given an array of integers { 15, 22, 30, 18, 3, 8, 28 }. Build a min-heap using the linear algorithm and then call DeleteMin twice. Which of the following is the level-order traversal sequence of the remaining heap?
The maximum flow in the network of the given Figure is:
An inversion in an array A[ ] is any ordered pair (i,j) having the property that i<j but A[i]>A[j]. Given array A: {3,87,12,61,70,26,45},after the first partition of Quicksort with Median3 pivot selection, the number of inversions will be decreased by _____.
Let's traverse a complete binary tree in level-order, and define the level-order index of the root to be 1. Then for the -th node visited, if its left child exists, then the index of this left child is___.
Given the adjacency list of a directed graph,
0: 4,5,6
1: Empty
2: Empty
3: 1,2
4: Empty
5: 3
6: 2
which one below is NOT a valid topological order of the graph?
Given a hash table of size 13 (indexed from 0 to 12) with the hash function %11. Quadratic probing )%13 is used to resolve collisions when the -th(>0) collision occurs. Then after inserting { 9, 21, 20, 33, 31, 5 } one by one into the initially empty hash table, which one of the following statements is false?
Suppose A is an array of length with some random numbers. What is the time complexity of the following program in the worst case?
void function( int A[], int N ) {
int i, j = 0, cnt = 0;
for (i = 0; i < N; ++i) {
for (; j < N && A[j] <= A[i]; ++j);
cnt += j - i;
}
}
The following figure shows a tree. Which one is its corresponding binary tree with the "first-child/next sibling" representation?
In hashig with open addressing method,rehashing is definitely necessary when __.
Given a weighted graph as shown by the figure. Which one of the following statements is TRUE about its minimum spanning tree?
Among the following threaded binary trees (the threads are represented by arrows), which one is the pre-order threaded tree?
The articulation points of the given graph are:
It is known that the sixth layer of a complete binary tree (the root is the first layer) has 8 leaf nodes, then the number of nodes of the complete binary tree is at most ____.
The function NumShortestPaths
is to find the number of shortest paths from Vertex S
to every other vertices in a given graph (positive weights only). The distances and the numbers of shortest paths are stored in dist[]
and num[]
, respectively. The Graph
is defined as follows:
typedef struct GNode *PtrToGNode;
struct GNode{
int Nv; /* Number of vertices */
int Ne; /* Number of edges */
int AdjMat[MaxVertexNum][MaxVertexNum]; /* adjacency matrix */
};
typedef PtrToGNode Graph;
Please fill in the blanks.
void NumShortestPaths(Graph G, Vertex S, bool known[], int dist[], int num[])
{
for (int i = 0; i < G->Nv; ++i)
{
known[i] = false;
dist[i] = INFINITY;
num[i] = 0;
}
dist[S] = 0;
(3分);
while (true) {
Vertex V = FindSmallestUnknown(G, known, dist);
if (V == -1) break;
known[V] = true;
for (Vertex W = 0; W < G->Nv; ++W) {
int weight = G->AdjMat[V][W];
if (weight && !known[W]) {
if (dist[V] + weight < dist[W]) {
dist[W] = dist[V] + weight;
num[W] = num[V];
} else if (dist[V] + weight == dist[W]) {
(3分);
}
}
}
}
}
序号 | 结果 | 得分 |
---|---|---|
0 | 答案正确 | 3 |
1 | 答案错误 | 0 |
Following function Shellsort(int A[], int N) is the implementation of Shellsort Algorithm with increment sequence {1,3,7,11}. Please fill in the blanks.
void Shellsort( int A[ ], int N )
{ int i, j, k, Increment, Inc[]={1,3,7,11};
int Tmp;
for ( k=3; k>=0; k--) {
(3分);
for ( i = Increment; i < N; i++ ) {
Tmp = A[ i ];
for ( j = i; j >= Increment; j -= Increment )
if( Tmp < A[ j - Increment ] )
A[ j ] = A[ j - Increment ];
else break;
(3分);
}
}
}
序号 | 结果 | 得分 |
---|
You are supposed to write a function of finding the height of a binary search tree with the given preorder sequence.
int Height_of_BST( int preorder[], int N );
where the preorder sequence is stored in int preorder[]
, and the integer N
is the number of nodes in the tree, which is guaranteed to be positive. The function Height_of_BST
is supposed to return the height of the binary search tree.
Note:
MAXN
is a small number (less than 100) in the judge's program.#include <stdio.h>
#include <stdlib.h>
#define MAXN 10
int Height_of_BST( int preorder[], int N );
int main()
{
int preorder[MAXN], N, i;
scanf("%d", &N);
for (i=0; i<N; i++) scanf("%d", &preorder[i]);
printf("%d\n", Height_of_BST(preorder, N));
return 0;
}
/* Your function will be put here */
9
10 6 2 9 8 25 20 22 30
3
int Height_of_BST( int preorder[], int N ) { int x,i,j; for(x=1,i=1;i<10;i++) { for(j=0;j<i;j++) { x*=2; } x-=1; if(x>N) { break; } } return 0; }
a.c: In function ‘main’: a.c:12:5: warning: ignoring return value of ‘scanf’, declared with attribute warn_unused_result [-Wunused-result] scanf("%d", &N); ^~~~~~~~~~~~~~~ a.c:13:25: warning: ignoring return value of ‘scanf’, declared with attribute warn_unused_result [-Wunused-result] for (i=0; i<N; i++) scanf("%d", &preorder[i]); ^~~~~~~~~~~~~~~~~~~~~~~~~
测试点 | 结果 | 得分 | 耗时 | 内存 |
---|---|---|---|---|
0 | 答案错误 | 0 | 2.00 ms | 196 KB |
1 | 答案错误 | 0 | 2.00 ms | 188 KB |
2 | 答案错误 | 0 | 2.00 ms | 324 KB |
3 | 答案错误 | 0 | 2.00 ms | 316 KB |
4 | 答案正确 | 1 | 2.00 ms | 184 KB |
5 | 答案错误 | 0 | 2.00 ms | 184 KB |