1-1算法分析的两个主要方面是时间复杂度和空间复杂度的分析。(2分)
T F
1-2将NNN个数据按照从小到大顺序组织存放在一个单向链表中。如果采用二分查找，那么查找的平均时间复杂度是O(logN)O(logN)O(logN)。(3分)
T F
1-3通过对堆栈S操作：Push(S,1), Push(S,2), Pop(S), Push(S,3), Pop(S), Pop(S)。输出的序列为：123。(3分)
T F
1-4所谓“循环队列”是指用单向循环链表或者循环数组表示的队列。(2分)
T F
1-5某二叉树的前序和中序遍历序列正好一样，则该二叉树中的任何结点一定都无右孩子。(3分)
T F
1-6在一棵二叉搜索树上查找63，序列39、101、25、80、70、59、63是一种可能的查找时的结点值比较序列。(3分)
T F
1-7将1、2、3、4、5、6顺序插入初始为空的AVL树中，当完成这6个元素的插入后，该AVL树的先序遍历结果是：4、2、1、3、5、6。(3分)
T F
1-8一棵有124个结点的完全二叉树，其叶结点个数是确定的。(3分)
T F
1-9用邻接表法存储图，占用的存储空间数只与图中结点个数有关，而与边数无关。(3分) T F
1-10如果无向图G必须进行两次广度优先搜索才能访问其所有顶点，则G中一定有回路。(3分)
T F
二、选择题
2-1下列函数中，哪个函数具有最快的增长速度？(4分)
A、N^2logNN
B、N(logN)^4
C、N^3
D、NlogN^2
2-2给定N×NN\times NN×N的二维数组A，则在不改变数组的前提下，查找最大元素的时间复杂度是：(4分)
A、O(N^2)
B、O(NlogN
C、O(N
D、O(N^2 logN
2-3给定程序时间复杂度的递推公式：T(1)=1T(1)=1T(1)=1，T(N)=2T(N/2)+NT(N)=2T(N/2)+NT(N)=2T(N/2)+N。则程序时间复杂度是：(4分)
A、O(logN)
B、O(N)
C、O(NlogN)
2-4设h为不带头结点的单向链表。在h的头上插入一个新结点t的语句是：(4分)
A、h=t; t->next=h->next;
B、t->next=h->next; h=t;
C、h=t; t->next=h;
D、t->next=h; h=t;
2-5若借助堆栈将中缀表达式a+b*c+(d*e+f)*g转换为后缀表达式，当读入f时，堆栈里的内容是什么（按堆栈自底向上顺序）？(4分)
A、+(*+
B、+(+
C、++(+
D、abcde
2-6若用大小为6的数组来实现循环队列，且当前front和rear的值分别为0和4。当从队列中删除两个元素，再加入两个元素后，front和rear的值分别为多少？(4分)
A、2和0
B、2和2
C、2和4
D、2和6
2-7三叉树中，度为1的结点有5个，度为2的结点3个，度为3的结点2个，问该树含有几个叶结点？(4分)
A、8
B、10
C、12
D、13
2-8已知一棵二叉树的先序遍历结果是ABC，则以下哪个序列是不可能的中序遍历结果：(4分)
A、ABC
B、BAC
C、CBA
D、CAB
2-9在一个用数组表示的完全二叉树中，如果根结点下标为1，那么下标为17和19这两个结点的最近公共祖先结点在哪里（数组下标）？（注：两个结点的“公共祖先结点”是指同时都是这两个结点祖先的结点）(4分)
A、8
B、4
C、2
D、1
2-10将6、4、3、5、8、9顺序插入初始为空的最大堆（大根堆）中，那么插入完成后堆顶的元素为：(4分)
A、3
B、5
C、6
D、9
2-11设一段文本中包含字符{a, b, c, d, e}，其出现频率相应为{3, 2, 5, 1, 1}。则经过哈夫曼编
码后，文本所占字节数为：(4分)
A、40
B、36
C、25
D、12
2-12在并查集问题中，已知集合元素0~8所以对应的父结点编号值分别是{ 1, -4, 1, 1, -3, 4, 4, 8, -2 }（注：?n-n?n表示树根且对应集合大小为nnn），那么将元素6和8所在的集合合并（要求必须将小集合并到大集合）后，该集合对应的树根和父结点编号值分别是多少？(4分)
A、1和-6
B、4和-5
C、8和-5
D、8和-6
3-1下列代码的功能是从一个大顶堆H的某个指定位置p开始执行下滤。voidPercolateDown( int p, PriorityQueue H )
{
int child;
ElementTypeTmp = H->Elements[p];
for ( ; p * 2 <= H->Size; p = child ) {
child = p * 2;
if ( child!=H->Size &&__________ (6分) )
child++;
if ( H->Elements[child] >Tmp )
___________________(6分);
else break;
}
H->Elements[p] = Tmp;
}
3-2
下列代码的功能是返回带头结点的单链表L的逆转链表。
List Reverse( List L )
{
Position Old_head, New_head, Temp;
New_head = NULL;
Old_head = L->Next;
while ( Old_head ) {
Temp = Old_head->Next;
______________(6分);
New_head = Old_head;
Old_head = Temp;
}
__________________(6分);
return L;
}
三、程序题
给定KK K个整数组成的序列{ N1N_1N1, N2N_2N2, ..., NKN_K N K }，“连续子列”被定义为{ NiN_i N i, Ni+1N_{i+1}N i+1, ..., NjN_j N j }，其中1≤i≤j≤K1 \le i \le j \le
K1≤i≤j≤K。“最大子列和”则被定义为所有连续子列元素的和中最大者。例如给定序列{ -2, 11, -4, 13, -5, -2 }，其连续子列{ 11, -4, 13 }有最大的和20。现要求你编写程序，计算给定整数序列的最大子列和。
本题旨在测试各种不同的算法在各种数据情况下的表现。各组测试数据特点如下：
?数据1：与样例等价，测试基本正确性；
?数据2：102个随机整数；
?数据3：103个随机整数；
?数据4：104个随机整数；
?数据5：105个随机整数；
输入格式:
输入第1行给出正整数KK K (≤100000\le 100000≤100000)；第2行给出KK K个整数，其间以空格分隔。
输出格式:
在一行中输出最大子列和。如果序列中所有整数皆为负数，则输出0。
输入样例:
输出样例:
Given a sequence of K integers {N1, N2, ..., N K }. A continuous subsequence is defined to be { N i, N i+1, ..., N j } where 1≤i≤j≤K. The Maximum Subsequence is the continuous subsequence which has the largest sum of its elements. For example, given sequence { -2, 11, -4, 13, -5, -2 }, its maximum subsequence is { 11, -4, 13 } with the largest sum being 20.
Now you are supposed to find the largest sum, together with the first and the last numbers of the maximum subsequence.
Input Specification:
Each input file contains one test case. Each case occupies two lines. The first line contains a positive integer K (≤10000\le 10000≤10000). The second line contains KK K numbers, separated by a space.
Output Specification:
For each test case, output in one line the largest sum, together with the first and the last numbers of the maximum subsequence. The numbers must be separated by one space, but there must be no extra space at the end of a line. In case that the maximum subsequence is not unique, output the one with the smallest
indices i and j(as shown by the sample case). If all the K numbers are negative,
then its maximum sum is defined to be 0, and you are supposed to output the first and the last numbers of the whole sequence.
Sample Input:
Sample Output: