- 第一章 绪论
- 第二章 线性表
- 第三章 栈和队列
- 第四章 串
- 第五章 数组和广义表
- 第六章 树和二叉树
- 第七章 图
- 第八章 查找
- 第九章 排序
考点：时间、空间复杂度
各种不同算法时间复杂度的比较关系如下:
O
(
1
)
<
O
(
l
o
g
2
n
)
<
O
(
n
)
<
O
(
n
l
o
g
2
n
)
<
O
(
n
2
)
<
O
(
n
3
)
<
O
(
2
n
)
<
O
(
n
!
)
O(1) 考点：链表 1.求链表长度算法 2.逆置算法 考点：递归算法 1.求n的阶乘：-----数值计算 2.用递归写出求数组中n个元素之和 考点：模式匹配（next数组） 考点：压缩矩阵、广义表 1.压缩矩阵 2.广义表(GetHead()、GetTail()) 考点：树的遍历、哈夫曼树及哈夫曼编码 1.树的遍历 2.哈夫曼树及哈夫曼编码
W
P
L
=
(
23
+
29
)
∗
2
+
(
11
+
14
)
∗
3
+
(
3
+
5
+
7
+
8
)
∗
4
=
271
WPL=(23+29)*2+(11+14)*3+(3+5+7+8)*4=271
WPL=(23+29)∗2+(11+14)∗3+(3+5+7+8)∗4=271 3.判定编码方案是否为前缀编码 考点：图的遍历：{深度优先搜索、广度优先搜索} 最小生成树：{Prim算法、Kruskal算法} 最短路径：{Dijkstra算法、Floyd算法} 拓扑排序、关键路径 **考点：**插入排序：{直接插入排序、折半插入排序、希尔排序} 交换排序：{冒泡排序、快速排序} 选择排序：{简单选择排序、堆排序} 归并排序：{二路归并排序}某算法的时间复杂度为O(n2)，表明该算法的（ ）。
A.问题规模是n2 B.执行时间等于n2
C.执行时间与n2成正比 D.问题规模与n2成正比 [C]
下面几种算法时间复杂度中，时间复杂度最高的是（ ）。
A.O(nlog2n) B.O(n2) C.O(n) D.O(2n) [D]
算法的空间复杂度是指（ ）。
A.算法中输入数据所占用的存储空间的大小
B.算法本身所占用的存储空间的大小
C.算法中所占用的所有存储空间的大小
D.算法中需要的辅助变量所占用存储空间的大小 [D]
第二章 线性表
int Length_LinkList (LinkList H)
{
LinkList p=H; 在这里插入代码片
int count= -1;
while ( p)
{
p=p->next;
count++;
}
return (count);
}
void reverse_LinkList (LinkList H)
{
LinkList p,q;
p=H->next;
H->next=NULL;
while (p) {
q=p;
p=p->next;
q->next=H->next;
H->next=q;
}
}
已知一个带有表头结点的单链表，结点结构为
|data|link|
假设该链表只给出了头指针list。在不改变链表的前提下，请设计一个尽可能高效的算法，查找链表中倒数第k个位置上的结点(k为正整数)。若查找成功，算法输出该结点的data域的值，并返回1;否则，只返回0。要求：
1)描述算法的基本设计思想。
2)描述算法的详细实现步骤。
3)根据设计思想和实现步骤，采用程序设计语言描述算法（使用C、C++或Java语言实现)，关键之处请给出简要注释。
算法的详细实现步骤如下：
①count=0,p和q指向链表表头结点的下一个结点。
②若p为空，转⑤。
③若count等于k,则q指向下一个结点；否则，count=count+1。
④p指向下一个结点，转②。
⑤若count等于k,则查找成功，输出该结点的data域的值，返回1;否则，说明k值超过了线性表的长度，查找失败，返回0。
⑥算法结束。
typedef struct LNode{
ElemType data;
struct LNode *link;
}LNode,*LinkList;
int Search_k(LinkList list,int k){
LNode *p=list->link,*q=list->link; //指针p、q指示第一个结点
int count=0;
while (p!=NULL){ //遍历链表直到最后一个结点
if (count
有一个带头结点的单链表L（至少有一个数据结点），设计一个算法使其元素递增有序排列。
void sort(LinkNode *&L)
{
LinkNode *p，*pre，*q;
p=L->next->next; //p指向L的第2个数据结点
L->next->next=NULL; //构造只含一个数据结点的有序表
while (p!=NULL)
{ q=p->next; //q保存p结点后继结点的指针
pre=L; //从有序表开头进行比较，pre指向插入p的前驱结点
while (pre->next!=NULL && pre->next->data
第三章 栈和队列
int fact(int n) {
if (n==1)
return 1;
else
return (n*fact(n-1));
}
int sum(int a[],int n){
if(n<=0)
return 0;
else
return(sum(a,n-1)+a[n-1]);
}
已知循环队列存储在一维数组A[0..n-1]中，且队列非空时front和rear分别指向队头元素和队尾元素。若初始时队列为空，且要求第一个进入队列的元素存储在A[0]处，则初始时front和rear的值分别是( )。
A.0,0 B.0,n-1 C.n-1,0 D.n-1,n-1 [B]
循环队列放在一维数组A[0..M-1]中，end1指向队头元素，end2指向队尾元素的后一个位置。假设队列两端均可进行入队和出队操作，队列中最多能容纳M-1个元素。初始时为空。下列判断队空和队满的条件中，正确的是()。
A.队空:end1==end2; 队满:end1==(end2+1)mod M
B.队空:end1==end2; 队满:end2==(end1+1)mod(M-1)
C.队空:end2==(end1+1)modM; 队满:end1==(end2+1)modM
D.队空:end1==(end2+1)modM; 队满:end2==(end1+1)mod(M-1) [A]
某队列允许在其两端进行入队操作，但仅允许在一端进行出队操作。若元素a,b,c,d,e依次入此队列后再进行出队操作，则不可能得到的出队序列是()。
A.b,a,c,d,e B.d,b,a,c,e C.d,b,c,a,e D.e,c,b,a,d [C]
[分析]: 初始时队列为空，第1个元素a左入（或右入）后，第2个元素b无论是左入还是右入都必与a相邻，而选项C中a与b不相邻
第四章 串
1.已知串S= 'aaab' ，其next数组值为( ) 。
A. 0123 B. 0112 C. 0231 D. 1211 [A]
2.串'ababaaababaa'的next数组值为( )。
A. 01234567899 B. 012121111212
C. 011234223456 D. 0123012322345
3.串'ababaaababaa'的next数组为( ) 。
A. -1,0,1,2,3,4,5,6,7,8,8,8 B. -1,0,1,0,1,0,0,0,0,1,0,1
C. -1,0,0,1,2,3,1,1,2,3,4,5 D. -1,0,1,2,-1,0,1,2,1,1,2,3
第五章 数组和广义表
第六章 树和二叉树
1. 广义表(a,(a,b),d,e,((i,j),k))的长度是___________，深度是___________。 2.已知广义表LS=(a，(b，c，d)，e),运用head和tail函数取出LS中原子b的运算是___。 3.广义表A((( ),(a,(b),c)))，head(tail(head(tail(head(A))))等于___________ 。 4. 广义表运算式HEAD(TAIL(((a,b,c),(x,y,z))))的结果是___。 5.已知广义表LS=((a,b,c),(d,e,f)),运用head和tail函数取出LS中原子e的运算是( ) //树的先序遍历
void PreOrder ( BTree t )
{
if ( t )
{ visite (t->data);
PreOrder ( t->lchild );
PreOrder ( t->rchild );
}
}
//树的中序遍历
void InOrder ( BTree t )
{
if ( t )
{
InOrder ( t->lchild );
Visite (t->data);
InOrder ( t->rchild );
}
}
//树的后序遍历
void PostOrder ( BTree t )
{
if ( t )
{
PostOrder ( t->lchild );
PostOrder ( t->rchild );
Visite(t->data);
}
}
1.假设有一组权值{5,29,7,8,14,23,3,11}，下面我们将利用这组权值演示构造哈夫曼树的过程。
第一步:以这8个权值作为根结点的权值构造具有8棵树的森林
5 29 7 8 14 23 3 11
第二步:从中选择两个根的权值最小的树3，5作为左右子树构造一棵新树，并将这两棵树从森林中删除，并将新树添加进去
第三步:重复第二步过程，直到森林中只有一棵树为止,选择7，8,选择8，11 选择14，15 选择19，23,选择29，29,选择42，58
这就是以上述8个权值为叶子结点权值构成的哈夫曼树，它的带权的路径长度为:
5个字符有如下4种编码方案，不是前缀编码的是( )。
A.01,0000,0001,001,1 B.011,000,001,010,1
C.000,001,010,011,100 D.0,100,110,1110,1100 [D]
[分析]:前缀编码:（字符集中）任一编码都不是其它字符的编码的前缀
下列选项给出的是从根分别到达两个叶结点路径上的权值序列，属于同一棵哈夫曼树的是( )。
A.24,10,5和24,10,7 B.24,10,5和24,12,7
C.24,10,10和24,14,11 D.24,10,5和24,14,6 [D]
已知字符集{a,b,c,d,e,f,g,h},若各字符的哈夫曼编码依次是0100,10，0000,0101,001,011,11,0001,则编码序列0100011001001011110101的译码结果是()。
A.acgabfh B.adbagbb C.afbeagd D.afeefgd [D]
[分析]:哈夫曼编码是前缀编码，各个编码的前缀不同，因此直接拿编码序列与哈夫曼编码一一比对即可。序列可分割为0100 011 001 001 011 11 0101，译码结果是afeefgd。
对个互不相同的n个符号进行哈夫曼编码。若生成的哈夫曼树共有115个结点，则n的值是()
A.56 B.57 C.58 D.60 [C]
[分析]:n个符号构造成哈夫曼树的过程中，共新建了n-1个结点（双分支结点），因此哈夫曼树的结点总数为2n-1=115,n的值为58.
第七章 图
