It is always possible to represent a tree by a one-dimensional integer array.
During the sorting, processing every element which is not yet at its final position is called a "run". To sort a list of integers using quick sort, it may reduce the total number of recursions by processing the small partion first in each run.
There must be a collision if we insert a new element into a hash table with the loading density being 1.
In a binary tree, if node A is an ancestor of node B, then A must precede B in the inorder traversal sequence.
For binary heaps with elements, the BuildHeap function (which adjust an array of elements into a heap in linear time) does at most comparisons between elements.
Let P be the shortest path from S to T. If the weight of every edge in the graph is multiplied by 2, P will still be the shortest path from S to T.
To judge an odd integer is prime or not, we need to check if it is divisible by any odd number from 3 to . The time complexity of this algorithm is .
Given that the pushing sequence of a stack is { 1, 2, , } and popping sequence is { }. If , we can obtain 2 different possible popping sequences.
During finding all articulation points in a connected graph, if v1 is the parent of v2 in the depth-first tree, Num(v1) must be less than Num(v2).
The best "worst-case time complexity" for any algorithm that sorts by comparisons only must be .
Given the AOE network of a project with 8 activities shown below, the earliest/latest completion time for node 4
is __.
The array representation of the disjoint sets is given by { 3, 1, -5, 2, 1, -3, -1, 6, 6 }. Keep in mind that the elements are numbered from 1 to 9. After invoking Union(Find(4), Find(8)) with union-by-size, which elements will be changed in the resulting array?
Suppose that the level-order traversal sequence of a max-heap is {64, 53, 45, 36, 48, 27}. Use the linear algorithm to adjust this max-heap into a min-heap, and then insert 32. The postorder traversal sequence of the resulting tree is:
Given an integer sequence 25、84、21、47、15、27、68、35、20, after the first run of the shell sorting by an increment 3, the integer sequence is __.
For a complete binary tree with even number of nodes, among the following statements, how many statement(s) is/are true?
a) the height of the left subtree must be greater than that of the right subtree
b) the number of nodes in the left subtree must be greater than that in the right subtree
c) the number of leaf-nodes in the left subtree must be twice over that in the right subtree
d) the number of leaf-nodes and that of non-leaf-nodes are exactly the same
When solving the maximum flow problem for graph , if partial states of the ( will be the maximum flow when the algorithm terminates) and (residual graph) are shown as the following, what must be the capacity of (v1, v2) or of (v2,v1) in the original graph ?
The space complexity of iteratively traversing a binary tree with nodes and height in inorder (with the help of an auxiliary stack) is __.
Graph G is an undirected completed graph of 20 nodes. Is there an Euler circuit in G? If not, in order to have an Euler circuit, what is the minimum number of edges which should be removed from G?
For an in-order threaded binary tree, if the post-order and in-order traversal sequences are CBFGEDA and BCADFEG respectively, the number of left threaded links and that of right threaded links are _.
A graph with 90 vertices and 20 edges must have at least __ connected component(s).
To find the minimum spanning tree with Prim's algorithm from v1 for the following graph. Which edge will be added in the final step?
If keys are pushed onto a stack in the order { 1, 2, 3, 4, 5} , then in the following sequence, the legal output sequence of the stack is ()
Given a tree of degree 5. Suppose that the numbers of nodes of degrees 1, 2, 3, 4, 5 are 3, 1, 2, 4, 3, respectively. Then the number of leaf nodes must be _.
Suppose that the range of a hash table is [0, 18], and the hash function is H(Key)=Key%17. If linear probing is used to resolve collisions, then after inserting { 16, 32, 14, 34, 48 } one by one into the hash table, the index of 48 is:
Given a binary search tree with its preorder traversal sequence { 10, 8, 21, 12, 15, 32 }. If 10 is deleted from the tree, which one of the following statements is FALSE?
To list the directory in a hierarchical file system with the format of files that are of depth di
will have their names indented by di
tabs,
which of the following traversals is the most suitable one.
Insert {20, 25, 13, 22, 4, 9, 29, 35, 14, 17} one by one into an initially empty hash table of size 13 with the hash function H(Key)=Key%13, and quadratic probing is used to resolve collisions. How many numbers can be inserted without collisions?
The recurrent equations for the time complexities of programs P1 and P2 are:
Then the correct conclusion about their time complexities is:
Given input { 110, 119, 7, 911, 114, 120, 122 }. Which one of the following is the result after the 2nd run of the Least Signification Digit (LSD) radix sort?
The time complexity of traversing a binary tree with nodes and height in levelorder (with the help of with an auxiliary queue) is __.
None-recursive Quick Selection algorithm
The function is to find the K
-th smallest element in a list A
of N
elements. The initial function call is QSelect(A, N, K)
. Please complete the following program.
ElementType QSelect( ElementType A[], int N, int K )
{
ElementType Pivot;
int L, R, Left, Right, K1;
Left = 0; Right = N-1; K1 = K;
for(;;) {
L = Left, R = Right+1;
Pivot = A[Left];
while (1) {
while ( A[++L] < Pivot ) ;
(3分);
if ( L < R ) Swap( &A[L], &A[R] );
else break;
}
Swap( &A[Left], &A[R] );
if ( K1 < (L-Left) )
Right = R-1;
else if ( K1 > (L-Left) ){
(3分);
Left = L;
}else
return Pivot;
}
}
序号 | 结果 | 得分 |
---|---|---|
0 | 运行超时 | 0 |
1 | 段错误 | 0 |
The function Unweighted
is to find the unweighted 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 Graph
is defined as the following:
typedef struct GNode *PtrToGNode;
struct GNode{
int Nv; /* Number of vertices */
int Ne; /* Number of edges */
AdjList List; /* adjacency matrix */
};
typedef PtrToGNode Graph;
void Unweighted( Graph G, Queue Q, int dist[], int path[], Vertex S )
{
Vertex V, U;
NodePtr ptr;
dist[S] = 0;
Enqueue(S, Q);
while ( !IsEmpty(Q) ) {
V = Dequeue( Q );
for ( ptr=G->List[V].FirstEdge; ptr; ptr=ptr->Next) {
U = ptr->AdjV;
if ( dist[U] == INFINITY ) {
(3分);
path[U] = V;
(3分);
}
}
}
}
序号 | 结果 | 得分 |
---|---|---|
0 | 答案正确 | 3 |
1 | 编译错误 | 0 |
Insert a sequence of integer keys into an initially empty binary search tree with larger keys in its left subtree and smaller keys in its right subtree, you are supposed to tell if the resulting tree is a complete binary search tree (CBST), and then return its preorder traversal sequence.
int IsCBST( int A[], int N );
where the sequence of N
insertions is stored in A[]
.
The function IsCBST
is supposed to return 1 if the resulting tree is a CBST, or 0 if not. At the mean time, A[]
must store the preorder traversal sequence of the resulting tree.
#include <stdio.h>
#define MAXN 10
int IsCBST( int A[], int N );
int main()
{
int A[MAXN], N, i;
scanf("%d", &N);
for (i=0; i<N; i++) scanf("%d", &A[i]);
if ( IsCBST(A, N) ) printf("Yes\n");
else printf("No\n");
for (i=0; i<N; i++) printf("%d ", A[i]);
return 0;
}
/* Your function will be put here */
9
38 45 42 24 58 30 67 12 51
Yes
38 45 58 67 51 42 24 30 12
8
38 24 12 45 58 67 42 51
No
38 45 58 67 51 42 24 12
int IsCBST( int A[], int N ) { int i,j,k,T[N]; for (i=0;i<N;i++) T[i]=0; for (i=0;;) { if (T[i]==0) { T[i]=A[i]; break; } else if (T[i]>A[i]) i=2*i+1; else i=2*i+2; } for (i=0;i<N;i++) if (T[i]) A[i]=T[i]; else return 0; return 1; }
a.c: In function ‘IsCBST’: a.c:23:13: warning: unused variable ‘k’ [-Wunused-variable] int i,j,k,T[N]; ^ a.c:23:11: warning: unused variable ‘j’ [-Wunused-variable] int i,j,k,T[N]; ^ a.c: In function ‘main’: a.c:11:5: warning: ignoring return value of ‘scanf’, declared with attribute warn_unused_result [-Wunused-result] scanf("%d", &N); ^~~~~~~~~~~~~~~ a.c:12:25: warning: ignoring return value of ‘scanf’, declared with attribute warn_unused_result [-Wunused-result] for (i=0; i<N; i++) scanf("%d", &A[i]); ^~~~~~~~~~~~~~~~~~
测试点 | 结果 | 得分 | 耗时 | 内存 |
---|---|---|---|---|
0 | 答案错误 | 0 | 4.00 ms | 328 KB |
1 | 答案错误 | 0 | 4.00 ms | 328 KB |
2 | 答案错误 | 0 | 4.00 ms | 324 KB |
3 | 答案错误 | 0 | 4.00 ms | 324 KB |
4 | 答案错误 | 0 | 5.00 ms | 192 KB |
5 | 答案错误 | 0 | 7.00 ms | 312 KB |
6 | 答案正确 | 1 | 4.00 ms | 196 KB |
7 | 答案正确 | 1 | 4.00 ms | 320 KB |