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分)
If numbers are stored in a singly linked list in increasing order, then the average time complexity for binary search is . (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分)
Quadratic probing is equivalent to double hashing with a secondary hash function of . (2分)
For a graph, if each vertex has an even degree, we can find an Euler circuit that visits every vertex exactly once. (2分)
If keys are pushed onto a stack in the order abcde
, then it's impossible to obtain the output sequence cedab
. (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分)
Mergesort is stable. (2分)
To sort records by quick sort, the worst-case time complexity is . (2分)
is . (2分)
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分)
Given input { 46, 79, 56, 38, 40, 84 }. Which one of the following is the initial heap built by heap sort? (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=60 will be . (3分)
Which one of the following is a possible postorder traversal sequence of a binary search 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分)
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分)
For the quicksort implementation with both the left and the right pointers stop when an element with the same key as the pivot is found during the partitioning, what is the running time when all keys are equal? (3分)
Which one of the following is the expression tree corresponding to the postfix expression aef*+bc*+
? (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分)
The inorder and the postorder traversal sequences of a binary tree are a b c d e f g
and a c b g f e d
, respectively. Then the preorder traversal sequences is: (3分)
The maximum flow from v1 to v6 is __: (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分)
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分)
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分)
Following is the C-like pseudo code of a function that takes a Queue as an argument.
void foo(Queue Q)
{
Stack S = CreateStack(); // create an empty stack
while (!IsEmpty(Q))
{
// dequeue an item from Q and push it into S
Push(S, Dequeue(Q));
}
while (!IsEmpty(S))
{
// pop an item from S and enqueue it into Q
Enqueue(Q, Pop(S));
}
DisposeStack(S);
}
What does the above function do? (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分)
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分)
Let be a tree of nodes created by union-by-size without path compression, then the minimum depth of may be (3分)
When inserting a new key K
into a binary search tree T
with 511 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 smallest element in a list A
of N
elements. The function BuildMaxHeap(H, K)
is to arrange elements H[1]
... H[K]
into a max-heap. Please complete the following program.
ElementType FindKthSmallest ( 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];
BuildMaxHeap(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 |
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;
}
序号 | 结果 | 得分 |
---|---|---|
0 | 答案正确 | 3 |
1 | 答案正确 | 3 |
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 | 256 KB |
1 | 答案正确 | 1 | 2 ms | 376 KB |
2 | 答案正确 | 1 | 2 ms | 256 KB |
3 | 答案正确 | 1 | 2 ms | 384 KB |
4 | 答案正确 | 1 | 29 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]); ^~~~~~~~~~~~~~~~~~~~