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.
Let P be the shortest path from S to T. If the weight of every edge in the graph is incremented by 2, P will still be the shortest path from S to T.
In a binary tree, if node A is a descendant of node B, A may precede B in the inorder traversal sequence.
Given that the pushing sequence of a stack is { 1, 2, , } and popping sequence is { }. If , we can obtain 2 different possible popping sequences.
There must be a collision if we insert a new element into a hash table with the loading density being 1.
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.
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 number of leaf nodes in a binary tree is only related to the number of 2-degree nodes , i.e it has nothing to do with the number of 1-degree nodes.
The best case time complexity of sorting algorithms based only on comparisons is at least .
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 .
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?
For an in-order threaded binary tree, if the post-order and in-order traversal sequences are DFGEBCA and DBFEGAC respectively, the number of left threaded links and that of right threaded links are _.
The recurrent equations for the time complexities of programs P1 and P2 are:
Then the correct conclusion about their time complexities is:
The space complexity of traversing a binary tree with nodes and height in levelorder (with the help of an auxiliary queue) is __.
Given a binary search tree with its preorder traversal sequence { 8, 2, 15, 10, 12, 21 }. If 8 is deleted from the tree, which one of the following statements is FALSE?
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?
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 __.
To find the minimum spanning tree with Kruskal's algorithm for the following graph. Which edge will be added in the final step?
Given a tree of degree 5. Suppose that the numbers of nodes of degrees 1, 2, 3, 4, 5 are 3, 4, 2, 1, 3, respectively. Then the number of leaf nodes must be_.
The time complexity of recursively traversing a binary tree with nodes and height in preorder is __.
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 ?
Suppose that the range of a hash table is [0, 16], and the hash function is H(Key)=Key%13. If linear probing is used to resolve collisions, then after inserting { 24, 12, 13, 49, 23 } one by one into the hash table, the index of 23 is:
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 the AOE network of a project with 8 activities shown below, the earliest/latest completion time for node 4
is __.
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:
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.
The array representation of the disjoint sets is given by { 4, 1, 2, -5, 1, -3, 9, -1, 6 }. Keep in mind that the elements are numbered from 1 to 9. After invoking Union(Find(3), Find(7)) with union-by-size, which elements will be changed in the resulting array?
Given input { 321, 156, 57, 46, 28, 7, 331, 33, 34, 63 }. Which one of the following is the result after the 2nd run of the Least Signification Digit (LSD) radix sort?
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
A graph with 90 vertices and 20 edges must have at most __ connected component(s).
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 | 答案正确 | 3 |
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 | 答案正确 | 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
void Insert(int *ret, int num,int index){//数值插入函数但是由于题目数组为0-n-1的,所以要思考左右下标 int left = (index+1)*2-1,right = (index+1)*2; if(!ret[index])ret[index] = num; else { if(num>ret[index]) Insert(ret,num,left); else Insert(ret,num,right); } return; } int cnt=0; void PostOrder(int *ret, int *a, int index){//后序遍历途中按顺序赋值题目要求的输出的A[],这个写过,但是要注意的是cnt是全局变量,这点我搞了半天。 if(ret[index]){ a[cnt++] = ret[index]; PostOrder(ret,a,(index+1)*2-1); PostOrder(ret,a,(index+1)*2); } } int IsCBST( int A[], int N ){ int ret[111]={0}; int index=0; for(int i=0; i<N; i++) Insert(ret,A[i],0); // for(int i=0; i<N; i++) printf("%d\n",ret[i]); PostOrder(ret,A,0); int flag =1; for(int i =0; i<N; i++)if(!ret[i])flag = 0;//如果是完全二叉树,则所有的点都在要求的N中,而不是则不然:在ret[x](x>N)的条件下会有节点存在 return flag; }
a.c: In function ‘IsCBST’: a.c:41:9: warning: unused variable ‘index’ [-Wunused-variable] int index=0; ^~~~~ 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 | 答案正确 | 1 | 9.00 ms | 192 KB |
1 | 答案正确 | 1 | 18.00 ms | 300 KB |
2 | 答案正确 | 1 | 6.00 ms | 184 KB |
3 | 答案正确 | 1 | 14.00 ms | 192 KB |
4 | 答案正确 | 1 | 6.00 ms | 188 KB |
5 | 答案正确 | 1 | 15.00 ms | 312 KB |
6 | 答案正确 | 1 | 20.00 ms | 188 KB |
7 | 答案正确 | 1 | 7.00 ms | 188 KB |