To sort records by quick sort, the worst-case time complexity is . (2分)
Shell sort is stable. (2分)
Linear probing is equivalent to double hashing with a secondary hash function of . (2分)
If the inorder and the postorder traversal sequences of a binary tree have exactly the same order, then none of the nodes in the tree has a right subtree. (2分)
is . (2分)
For a graph, if each vertex has an even degree, we can find an Euler circuit that visits every vertex exactly once. (2分)
Let P be the shortest path from S to T. If the weight of every edge in the graph is incremented by 1, P will still be the shortest path from S to T. (2分)
If keys are pushed onto a stack in the order abcde
, then it's impossible to obtain the output sequence cdabe
. (2分)
If numbers are stored in a singly linked list in increasing order, then the average time complexity for binary search is . (2分)
Given a binary search tree with 20 integer keys which include 4, 5, and 6, if 4 and 6 are on the same level, then 5 must be their parent. (2分)
The inorder and the postorder traversal sequences of a binary tree are a b c d e f g
and a c b f g e d
, respectively. Then the preorder traversal sequences is: (3分)
Given input {15, 9, 7, 8, 20, -1, 4}. If the result of the 1st run of Shell sort is {15, -1, 4, 8, 20, 9, 7}, then the initial increment must be: (3分)
Following is the C-like pseudo code of a function that takes a Queue as an argument.
void foo(Queue Q)
{
Queue Q1 = CreateQueue(); // create an empty queue
while (!IsEmpty(Q))
{
// dequeue an item from Q and enqueue it into Q1
Enqueue(Q1, Dequeue(Q));
}
while (!IsEmpty(Q1))
{
// dequeue an item from Q1 and enqueue it into Q
Enqueue(Q, Dequeue(Q1));
}
DisposeQueue(Q1);
}
What does the above function do? (3分)
Let be a tree of nodes created by union-by-size without path compression, then the minimum depth of may be (3分)
It is known that a 3-heap is a heap whose nodes have 3 children. Suppose that the level-order traversal sequence of a max-3-heap is {88, 76, 65, 82, 68, 46, 52, 44, 62, 33, 75, 28, 55, 60}. Use the linear algorithm to adjust this max-3-heap into a min-3-heap, and then run DeleteMin. As a result, there are __ nodes whose positions are not moved in the process. (3分)
Which one of the following is the expression tree corresponding to the postfix expression abc*+ef*+
? (3分)
The maximum flow from v1 to v6 is __ (3分)
Given the structure of a binary search tree (as shown in the figure), which one of the following insertion sequences is impossible? (3分)
Given input {46, 79, 56, 38, 40, 84}. After the first partition (with the left most record as the pivot) of quick sort, the resulting sequence is: (3分)
Insert {18, 23, 4, 26, 31, 33, 17, 39} one by one into an initially empty hash table of size 13 with the hash function , and linear probing is used to resolve collisions. What is the loading density when the first collision occurs? (3分)
A graph with 100 vertices and 12 edges must have at most __ connected component(s). (3分)
Use Dijkstra algorithm to find the shortest paths from 1 to every other vertices. In which order that the destinations must be obtained? (3分)
Suppose that the size of a hash table is 11, and the hash function is H(key)=key%11. The following 4 elements have been inserted into the table as Addr(14)=3, Addr(38)=5, Addr(61)=6, Addr(86)=9. When open addressing with quadratic probing is used to solve collisions, the address of the element with key=49 will be . (3分)
To find the minimum spanning tree with Prim's algorithm for the following graph, a sequence of vertexes 6, 1, 2, 3 was found during the algorithm's early steps. Which one vertex will be added in the next step? (3分)
The following is the part of depth-first search tree to find the articulation points, and the Num(v) value has been marked beside each vertex v. The back edges are not shown. Which of the following situation is impossible? (3分)
In order to convert the infix expression 4 + 3 * (6 * 3 - 12)
to postfix expression using a stack , then the minimum size of must be: (3分)
Which one of the following is a possible postorder traversal sequence of a binary search tree? (3分)
For an in-order threaded binary tree, if the pre-order and in-order traversal sequences are D A B C F E
and B A C D E F
respectively, which pair of nodes' right links are both threads? (3分)
Given a tree of degree 6. Suppose that the numbers of nodes of degrees 1, 2, 3, 4, 5, 6 are 3, 5, 3, 4, 2, 1, respectively. Then the number of leaf nodes must be: (3分)
When inserting a new key K
into a binary search tree T
with 512 nodes, the worst-case number of comparisons between K
and the keys already in T
is in the range of: (3分)
The function is to find the K
-th largest element in a list A
of N
elements. The function BuildMinHeap(H, K)
is to arrange elements H[1]
... H[K]
into a min-heap. Please complete the following program.
ElementType FindKthLargest ( int A[], int N, int K )
{ /* it is assumed that K<=N */
ElementType *H;
int i, next, child;
H = (ElementType *)malloc((K+1)*sizeof(ElementType));
for ( i=1; i<=K; i++ ) H[i] = A[i-1];
BuildMinHeap(H, K);
for ( next=K; next<N; next++ ) {
H[0] = A[next];
if ( H[0] > H[1] ) {
for ( i=1; i*2<=K; i=child ) {
child = i*2;
if ( child!=K && (3分) ) child++;
if ( (3分) )
H[i] = H[child];
else break;
}
H[i] = H[0];
}
}
return H[1];
}
序号 | 结果 | 得分 |
---|---|---|
0 | 答案正确 | 3 |
1 | 答案正确 | 3 |
The function is to find the K
-th largest element in a list A
of N
elements. The initial function call is Qselect(A, K, 0, N-1)
. Please complete the following program.
ElementType Qselect( ElementType A[], int K, int Left, int Right )
{
ElementType Pivot = A[Left];
int L = Left, R = Right+1;
while (1) {
while ( A[++L] > Pivot ) ;
(3分);
if ( L < R ) Swap( &A[L], &A[R] );
else break;
}
Swap( &A[Left], &A[R] );
if ( K < (L-Left) )
return Qselect(A, K, Left, R-1);
else if ( K > (L-Left) )
(3分);
else
return Pivot;
}
序号 | 结果 | 得分 |
---|---|---|
0 | 答案正确 | 3 |
1 | 答案错误 | 0 |
Write a program to test if a give sequence Seq
is a topological order of a given graph Graph
.
bool IsTopSeq( LGraph Graph, Vertex Seq[] );
where LGraph
is defined as the following:
typedef struct AdjVNode *PtrToAdjVNode;
struct AdjVNode{
Vertex AdjV;
PtrToAdjVNode Next;
};
typedef struct Vnode{
PtrToAdjVNode FirstEdge;
} AdjList[MaxVertexNum];
typedef struct GNode *PtrToGNode;
struct GNode{
int Nv;
int Ne;
AdjList G;
};
typedef PtrToGNode LGraph;
The function IsTopSeq
must return true
if Seq
does correspond to a topological order; otherwise return false
.
Note: Although the vertices are numbered from 1 to MaxVertexNum, they are indexed from 0 in the LGraph structure.
#include <stdio.h>
#include <stdlib.h>
typedef enum {false, true} bool;
#define MaxVertexNum 10 /* maximum number of vertices */
typedef int Vertex; /* vertices are numbered from 1 to MaxVertexNum */
typedef struct AdjVNode *PtrToAdjVNode;
struct AdjVNode{
Vertex AdjV;
PtrToAdjVNode Next;
};
typedef struct Vnode{
PtrToAdjVNode FirstEdge;
} AdjList[MaxVertexNum];
typedef struct GNode *PtrToGNode;
struct GNode{
int Nv;
int Ne;
AdjList G;
};
typedef PtrToGNode LGraph;
LGraph ReadG(); /* details omitted */
bool IsTopSeq( LGraph Graph, Vertex Seq[] );
int main()
{
int i, j, N;
Vertex Seq[MaxVertexNum];
LGraph G = ReadG();
scanf("%d", &N);
for (i=0; i<N; i++) {
for (j=0; j<G->Nv; j++)
scanf("%d", &Seq[j]);
if ( IsTopSeq(G, Seq)==true ) printf("yes\n");
else printf("no\n");
}
return 0;
}
/* Your function will be put here */
6 8
1 2
1 3
5 2
5 4
2 3
2 6
3 4
6 4
5
1 5 2 3 6 4
5 1 2 6 3 4
5 1 2 3 6 4
5 2 1 6 3 4
1 2 3 4 5 6
yes
yes
yes
no
no
bool IsTopSeq( LGraph Graph, Vertex Seq[] ){ int Indegree[Graph->Nv]; int i; for(i=0;i<Graph->Nv;i++){ Indegree[i]=0; Seq[i]--; } PtrToAdjVNode T; for(i=0;i<Graph->Nv;i++){ T=Graph->G[i].FirstEdge; while(T!=NULL){ Indegree[T->AdjV]++; T=T->Next; } } for(i=0;i<Graph->Nv;i++){ Vertex V=Seq[i]; if(Indegree[V]!=0)return false; T=Graph->G[V].FirstEdge; while(T!=NULL){ Indegree[T->AdjV]--; T=T->Next; } } return true; }
测试点 | 结果 | 得分 | 耗时 | 内存 |
---|---|---|---|---|
0 | 答案正确 | 4 | 2 ms | 384 KB |
1 | 答案正确 | 1 | 2 ms | 384 KB |
2 | 答案正确 | 1 | 2 ms | 256 KB |
3 | 答案正确 | 1 | 2 ms | 372 KB |
4 | 答案正确 | 1 | 16 ms | 512 KB |
a.c: In function ‘ReadG’: a.c:68:2: warning: ignoring return value of ‘scanf’, declared with attribute warn_unused_result [-Wunused-result] scanf("%d", &Nv); /* 读入顶点个数 */ ^~~~~~~~~~~~~~~~ a.c:71:2: warning: ignoring return value of ‘scanf’, declared with attribute warn_unused_result [-Wunused-result] scanf("%d", &(Graph->Ne)); /* 读入边数 */ ^~~~~~~~~~~~~~~~~~~~~~~~~ a.c:76:7: warning: ignoring return value of ‘scanf’, declared with attribute warn_unused_result [-Wunused-result] scanf("%d %d", &E->V1, &E->V2); ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ a.c: In function ‘main’: a.c:90:5: warning: ignoring return value of ‘scanf’, declared with attribute warn_unused_result [-Wunused-result] scanf("%d", &N); ^~~~~~~~~~~~~~~ a.c:93:13: warning: ignoring return value of ‘scanf’, declared with attribute warn_unused_result [-Wunused-result] scanf("%d", &Seq[j]); ^~~~~~~~~~~~~~~~~~~~