数据结构 - 题目详解 - 《school(IOT) 学习笔记》

第一单元绪论
第二单元线性表
第三单元栈
第四单元队列
第六单元树与二叉树
第七单元图
第八单元查找排序

第一单元绪论

一．判断题（下列各题，正确的请在前面的括号内打√；错误的打╳ ）
（ t ）（1）数据的逻辑结构与数据元素本身的内容和形式无关。
逻辑结构：数据元素间的逻辑关系
（~~ f~~ t）（2）一个数据结构是由一个逻辑结构和这个逻辑结构上的一个基本运算集构成的整体。
数据结构=逻辑结构+残存结构+数据的运算
（ f ）（3）数据元素是数据的最小单位。
数据元素可以= 若干个数据项。
数据项是数据的最小单位。
（ f ）（4）数据的逻辑结构和数据的存储结构是相同的。
逻辑结构：数据元素间的逻辑关系
存储结构：数据结构在计算机中的表现
（ f ）（5）程序和算法原则上没有区别，所以在讨论数据结构时可以通用。
程序是：
算法是：
（ t ）（6）从逻辑关系上讲，数据结构主要分为线性结构和非线性结构两类。
（ t ）（7）数据的存储结构是数据的逻辑结构的存储映像。
（ t ）（8）数据的物理结构是指数据在计算机内实际的存储形式。
存储结构也称物理结构
（ f ）（9）数据的逻辑结构是依赖于计算机的。
逻辑结构指数据之间的逻辑关系，与数据的存储无关。
存储结构则依赖于计算机
（ t ）（10）算法是对解题方法和步骤的描述。

二．填空题
（1）数据有逻辑结构和存储结构两种结构。
（2）数据逻辑结构除了集合以外，还包括：线性结构、树形结构和图状结构。
（3）数据结构按逻辑结构可分为两大类，它们是线性结构和非线性结构。
（4）树形结构和图状结构合称为非线性结构。
（5）在树形结构中，除了树根结点以外，其余每个结点只有 1 个前趋结点。
（6）在图形结构中，每个结点的前趋结点数和后续结点数可以任意多个。
（7）数据的存储结构又叫物理结构。
（8）数据的存储结构形式包括：顺序存储、链式存储、索引存储和散列存储。
（9）线性结构中的元素之间存在一对一的关系。
（10）树形结构结构中的元素之间存在一对多的关系，
（11）图形结构的元素之间存在多对多的关系。
（12）数据结构主要研究数据的逻辑结构、存储结构和 ~~数据的运算~~ 算法（或运算）三个方面的内容。
（13）数据结构被定义为(D，R)，其中D是数据的有限集合，R是D上的关系的有限集合。
（14）算法是一个有穷指令的集合。
（15）算法效率的度量可以分为事先估算法和事后统计法。
（16）一个算法的时间复杂性是算法输入规模的函数。
（17）算法的空间复杂度是指该算法所耗费的储存空间，它是该算法求解问题规模n的函数。
（18）若一个算法中的语句频度之和为T（n）=6n+3nlog2n，则算法的时间复杂度为 ~~3nlog2n~~ O（nlog2n）。
（19）若一个算法中的语句频度之和为T（n）=3n+nlog2n+n2，则算法的时间复杂度为 n2 O（n2）。
（20）数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象，以及它们之间的关系和运算的学科。

三．选择题
（1）数据结构通常是研究数据的（）及它们之间的相互联系。
A. 存储结构和逻辑结构 B. 存储和抽象 C. 联系和抽象 D. 联系与逻辑
（2）在逻辑上可以把数据结构分成：（）。
A. 动态结构和静态结构 B. 紧凑结构和非紧凑结构
C. 线性结构和非线性结构 D. 内部结构和外部结构
（3）数据在计算机存储器内表示时，物理地址和逻辑地址相同并且是连续的，称之为（）。
A. 存储结构 B. 逻辑结构 C. 顺序存储结构 D. 链式存储结构
（4）非线性结构中的每个结点（）。
A. 无直接前趋结点
B. 无直接后继结点
C. 只有一个直接前趋结点和一个直接后继结点
D. 可能有多个直接前趋结点和多个直接后继结点
（5）链式存储的存储结构所占存储空间（）。
A．分两部分，一部分存放结点的值，另一部分存放表示结点间关系的指针
B．只有一部分，存放结点的值
C．只有一部分，存储表示结点间关系的指针
D．分两部分，一部分存放结点的值，另一部分存放结点所占单元素
（6）算法的计算量大小称为算法的（）。
A. 现实性 B. 难度 C. 时间复杂性 D. 效率(效率是指执行的时间)
（7）数据的基本单位是（）。
A. 数据结构 B. 数据元素 C. 数据项 D. 文件
（8）每个结点只含有一个数据元素，所有存储结点相继存放在一个连续的存储区里，这种存储结构称为（）结构。
A. 顺序存储 B. 链式存储 C. 索引存储 D. 散列存储
（9）每一个存储结点不仅含有一个数据元素，还包含一组指针，该存储方式是（）存储方式。
A. 顺序 B. 链式 C. 索引 D. 散列
（10）以下任何两个结点之间都没有逻辑关系的是（）。
A. 图形结构 B. 线性结构 C. 树形结构 D. 集合
（11）在数据结构中，与所使用的计算机无关的是（）。
A. 物理结构 B. 存储结构 C. 逻辑结构 D. 逻辑和存储结构
（12）下列四种基本逻辑结构中，数据元素之间关系最弱的是（）。
A. 集合 B. 线性结构 C. 树形结构 D. 图形结构
（13）与数据元素本身的形式、内容、相对位置、个数无关的是数据的（）。
A. 逻辑结构 B. 存储结构 C. 逻辑实现 D. 存储实现
（14）每一个存储结点只含有一个数据元素，存储结点存放在连续的存储空间，另外有一组指明结点存储位置的表，该存储方式是（）存储方式。
A. 顺序 B. 链式 C. 索引 D. 散列
（15）算法能正确的实现预定功能的特性称为算法的（）。
A. 正确性 B. 易读性 C. 健壮性 D. 高效性
（16）算法在发生非法操作时可以作出处理的特性称为算法的（）。
A. 正确性 B. 易读性 C. 健壮性 D. 高效性
（17）下列时间复杂度中最坏的是（）。
A. O（1） B. O（ n） C. O（log2n） D. O（n2）
（18）下列算法的时间复杂度是（）。
for (i=0;i for (j=0;ic[i][j]=i+j;
A. O（1） B. O（ n） C. O（log2n） D. O（n2）
（19）算法分析的两个主要方面是（）。
A. 空间复杂性和时间复杂性 B. 正确性和简明性
C. 可读性和文档性 D. 数据复杂性和程序复杂性
（20）计算机算法必须具备输入、输出和（）。
A. 计算方法 B. 排序方法
C. 解决问题的有限运算步骤 D. 程序设计方法

四．分析下面各程序段的时间复杂度
（1） for (i=0;i for (j=0;j A[i][j]
解： ~~ nm~~ O(nm)
（2） s=0;
for (i=0;ifor (j=0;j s+=B[i][j];
sum=s;
解： O(n^2)
（3） T=A；
A=B；
B=T；
解： O(1)
（4） s1(int n)
{ int p=1,s=0;
for (i=1;i<=n;i++)
{ p=i;s+=p; }
return(s);
}
解： O(n)
（5） s2(int n)
{x=0;
y=0;
for (k=1;k<=n;k++)
x++;
for (i=1;i<=n;i++)
for (j=1;j<=n;j++)
y++;}
解： O(n^2)

五．根据二元组关系，画出对应逻辑图形的草图，指出它们属于何种数据结构。
1．A=（D，R），其中：
D={a，b，c，d，e}，
R={ }
解：集合

2． B=（D，R），其中：
D={a，b，c，d，e，f}， R={r}
R={，，，，} （尖括号表示结点之间关系是有向的）
解：线性结构

3．根据二元组关系画出逻辑图形，并指出它们属于何种数据结构。
F=（D，R），其中：
D={50，25，64，57，82，36，75，55}，
R={<50,25>,<50,64>,<25,36>,<64,57>,
<64,82>,<57,55>,<57,75>}
解：树

4．根据二元组关系画出逻辑图形，并指出它们属于何种数据结构。
C=（D，R），其中：
D={1，2，3，4，5，6}，
R={（1,2）,（2,3）,（2,4）,（3,4）,（3,5）,（3,6）,（4,5）,（4,6）}
（园括号表示结点之间关系是无向的）
解：图

5．根据二元组关系画出逻辑图形，并指出它们属于何种数据结构。
E=（D，R），其中：
D={a，b，c，d，e，f，g，h}，
R={，，，，，，}
解：树
**模拟考题
1．根据二元组关系画出逻辑图形，并指出它们属于何种数据结构。
A=（D，R），其中：
D={1，2，3，4，5，6}，
R={（1,2）,（1,6）,（2,3）,（2,4）,
（3,4）,（3,5）,（3,6）,（4,5）,（5,6）}
解：图

2．根据二元组关系画出逻辑图形，并指出它们属于何种数据结构。
B=（D，R），其中：
D={40，30，20，60，50，80，70，10}，
R={<30,20>,<30,60>,<20,40>,<60,50>,
<60,70>,<60,80>,<70,10>}
解：树

3．根据二元组关系画出逻辑图形，并指出它们属于何种数据结构。
C=（D，R），其中：
D={1，2，3，4，5，6}，
R={（1,2）,（2,3）,（2,4）,（3,4）,
（3,5）,（3,6）,（4,5）,（4,6）}
解：图

4．根据二元组关系画出逻辑图形，并指出它们属于何种数据结构。
E=（D，R），其中：
D={a，b，c，d，e，f，g，h}，
R={,,,,
,,}
解：树

第二单元线性表

一．判断题（下列各题，正确的请在前面的括号内打√；错误的打╳ ）
（ f ）（1）线性表的链式存储结构优于顺序存储。
（ f ）（2）链表的每个结点都恰好包含一个指针域。
（ t ）（3）在线性表的链式存储结构中，逻辑上相邻的两个元素在物理位置上并不一定紧邻。
（ f ）（4）顺序存储方式的优点是存储密度大，插入、删除效率高。
（ f ）（5）线性链表的删除算法简单，因为当删除链中某个结点后，计算机会自动将后续的各个单元向前移动。
（ f ）（6）顺序表的每个结点只能是一个简单类型，而链表的每个结点可以是一个复杂类型。
（ t ）（7）线性表链式存储的特点是可以用一组任意的存储单元存储表中的数据元素。
（ t ）（8）线性表采用顺序存储，必须占用一片连续的存储单元。
（ f ）（9）顺序表结构适宜于进行顺序存取，而链表适宜于进行随机存取。
（ t f）（10）插入和删除操作是数据结构中最基本的两种操作，所以这两种操作在数组中也经常使用。

二．填空题
（1）顺序表中逻辑上相邻的元素在物理位置上也必须相连。
（2）线性表中结点的集合是有限的，结点间的关系是一对一关系。
（3） 顺序表相对于链表的优点是：节省存储和随机存取。
（4）链表相对于顺序表的优点是：插入、删除方便。
（5）采用顺序存储结构的线性表叫顺序表。
（6）顺序表中访问任意一个结点的时间复杂度均为 O(1) 。
（7）链表相对于顺序表的优点是插入、删除方便；缺点是存储密度 ~~ 低~~ 小。
（8）在双链表中要删除已知结点P，其时间复杂度为 O(1) 。
（9）在单链表中要在已知结点P之前插入一个新结点，需找到*P的直接前趋结点的地址，其查找的时间复杂度为 O(n) 。
（10）单链表中需知道 ~~头结点~~ 头指针才能遍历整个链表。
（11）性表中第一个结点没有直接前趋，称为头开始结点。
（12）在一个长度为n的顺序表中删除第i个元素，要移动 n-i 个元素。
（13）在一个长度为n的顺序表中，如果要在第i个元素前插入一个元素，要后移 n-i+1 个元素。
（14）在无头结点的单链表中，第一个结点的地址存放在头指针中，而其它结点的存储地址存放在( 前驱 ~~上一个~~ )结点的指针域中。
（15）当线性表的元素总数基本稳定，且很少进行插入和删除操作，但要求以最快速度存取线性表中的元素时，应采用顺序存储结构。
（16）在线性表的链式存储中，元素之间的逻辑关系是通过指针决定的。
（17）在双向链表中，每个结点都有两个指针域，它们一个指向其前驱结点，另一个指向其( 后继 )结点。
（18）对一个需要经常进行插入和删除操作的线性表，采用链式存储结构为宜。
（19）双链表中，设p是指向其中待删除的结点，则需要执行的操作为： p->prior->next=p->next 。
（20）在如图所示的链表中，若在指针P所在的结点之后插入数据域值为a和b的两个结点，则可用下列两个语句： S->next->next = P->next 和P->next=S;来实现该操作。

三．选择题
（1）在具有n个结点的单链表中，实现（）的操作，其算法的时间复杂度都是O（n）。
A．遍历链表或求链表的第i个结点 B．在地址为P的结点之后插入一个结点
C．删除开始结点 ~~ D．删除地址为P的结点的后继结点
（2）设a、b、c为三个结点，p、10、20分别代表它们的地址，则如下的存储结构称为（）。

A．循环链表 B．单链表 C．双向循环链表 D．双向链表
（3）单链表的存储密度（）。
A．大于1 ~~B．等于1 ~~ C．小于1 D．不能确定
（4）已知一个顺序存储的线性表，设每个结点占m个存储单元，若第一个结点的地址为B，则第i个结点的地址为（）。
A． B+(i-1)m B．B+im C． B-i*m ~~ ~~D． B+(i+1)m~~
（5）在有n个结点的顺序表上做插入、删除结点运算的时间复杂度为（）。
A．O（1） B．O（n） C．O（n2） D．O（log2n）
（6）设Llink、Rlink分别为循环双链表结点的左指针和右指针，则指针P所指的元素是双循环链表L的尾元素的条件是（）。
A．P== L B．P->Llink== L C．P== NULL D．P->Rlink==L
（7）两个指针P和Q，分别指向单链表的两个元素，P所指元素是Q所指元素前驱的条件是（）。
A．P->next==Q->next B．P->next== Q C．Q->next== P D．P== Q
（8）用链表存储的线性表，其优点是（）。
A．便于随机存取 B．花费的存储空间比顺序表少
C．便于插入和删除 D．数据元素的物理顺序与逻辑顺序相同
（9）在单链表中，增加头结点的目的是（）。
A．使单链表至少有一个结点 B．标志表中首结点的位置
C．方便运算的实现 D．说明该单链表是线性表的链式存储结构
（10）下面关于线性表的叙述中，错误的是（）关系。
A．顺序表必须占一片地址连续的存储单元 B．顺序表可以随机存取任一元素
C．链表不必占用一片地址连续的存储单元 D．链表可以随机存取任一元素
（11）L是线性表，已知LengthList（L）的值是5，经DelList（L，2）运算后，LengthList（L）的值是（）。
A．2 B．3 C．4 D．5
（12）单链表的示意图如下：

指向链表Q结点的前趋的指针是（）。
A．L B．P C．Q D．R
（13）设p为指向单循环链表上某结点的指针，则p的直接前驱（）。
A．找不到 B．查找时间复杂度为O（1）
C．查找时间复杂度为O（n） D．查找结点的次数约为n
（14）等概率情况下，在有n个结点的顺序表上做插入结点运算，需平均移动结点的数目为（）。
A．n B．(n-1)/2 C． n/2 ~~ D．(n+1)/2 ~~
第一移n个，最后一个，移0个->0+1+..+n=
（15）在下列链表中不能从当前结点出发访问到其余各结点的是（）。
A．双向链表 B．单循环链表 C．单链表 D．双向循环链表
（16）在顺序表中，只要知道（），就可以求出任一结点的存储地址。
A．基地址 B．结点大小 C．向量大小 D．基地址和结点大小
（17）在双链表中做插入运算的时间复杂度为（）。
A．O（1） B．O（n） C．O（n2） D．O（log2n）
（18）链表不具备的特点是（）。
A．随机访问 B．不必事先估计存储空间
C．插入删除时不需移动元素 D．所需空间与线性表成正比
（19）以下关于线性表的论述，不正确的为（）。
A．线性表中的元素可以是数字、字符、记录等不同类型
B．线性顺序表中包含的元素个数不是任意的
C．线性表中的每个结点都有且仅有一个直接前趋和一个直接后继
D．存在这样的线性表，即表中没有任何结点
（20）在（）的运算中，使用顺序表比链表好。
A．插入 B．根据序号查找 C．删除 D．根据元素查找

四．下述算法的功能是什么?

解：(1)在L中找p结点
(2)交换两个结点的值

五．程序填空
1．已知线性表中的元素是无序的，并以带表头结点的单链表作存储。试写一算法，删除表中所有大于min，小于max的元素，试完成下列程序填空。
Void delete (lklist head; datatype min, max)
{ q=head->next;
while (p!=NULL)
{ if ((p->data<=min ) | | ( p->data>=max )
{q=p; p= q->next ; }
else
{ q->next= ;
;
p= q ; }
}
}

2．在带头结点head的单链表的结点a之后插入新元素x，试完成下列程序填空。
struct node
{ elemtype data;
node next;
};
void lkinsert (node head, elemtype x)
{ node s, p;
s= ;
s->data= x ;
p=head->next;
while (p!=NULL) && ( p->data!=a )
p = p->next ;
if (p==NULL)
cout<< “ 不存在结点a! “;
else {_ s-next=p->next __;
p->next=s __;
}
}

六．程序设计题
1．写一个对单循环链表进行遍历（打印每个结点的值）的算法，已知链表中任意结点的地址为P 。
void Show(ListNode P)
{ ListNode t=P;
do
{ printf (“%c”,t->data);
t=t->rear;
}
while (t!=P);
}
2．对给定的带头结点的单链表L，编写一个删除L中值为x的结点的直接前趋结点的算法。
void delete(ListNode L)
{ ListNode p=L,q;
if (L->next->data==X)
{ printf (“值为x的结点是第一个结点，没有直接前趋结点可以删除”);
return;
}
for (;p->next->data!=X; q=p; p=p->next); // 删除指针p所指向的结点
q->next=p->next;
delete p;
}
3．将一个顺序表中从第i个结点开始的k个结点删除。
4．已知一个单链表，编写一个函数从单链表中删除自第i个结点起的k个结点。
void Del(node head,int i,int k)
{
node p,q;
int j;
if (i==1)
for (j=1;j<=k;j++) // 删除前k个元素
{
p=head; // p指向要删除的结点
head=head->next;
delete p;
}
else
{
p=head;
for (j=1;j<=i-2;j++)
p=p->next; // p指向要删除的结点的前一个结点
for (j=1;j<=k;j++)
{
q=p->next; // q 指向要删除的结点
p->next=q->next;
delete q;
}
}
}
5．有—个单链表（不同结点的数据域值可能相同），其头指针为head，编写一个函数计算值域为x的结点个数。
6．有两个循环单链表，链头指针分别为head1和head2，编写一个函数将链表head1链接到链表head2，链接后的链表仍是循环链表。
2．解：
void delete(ListNode *L)
{

}

3．解(校对一下,或换一题)
void Del(SeqList *L,int i,int k)
{

}

4．解：
void Del(node *head,int i,int k)
{

}

5．解：本题是遍历单链表的每个结点，每遇到一个结点，结点个数加1，结点个数存储在变量n中。实现本题功能的函数如下：
int counter(head)
node *head；
{

}

6．解：本题的算法思想是：先找到两链表的尾指针，将第一个链表的尾指针与第二个链表的头结点链接起来，使之成为循环的。函数如下：
node link (node head1, *head2)
{

}
**模拟考题
1．在顺序存储的线性表第i个位置插入新结点x，试完成下列程序填空。
typedef struct // 将data和last封装在一个结构体
{ datatype data[MAXLEN]; // MAXLEN为线性表的最大长度
int last;
}SeqList;
int InsList(SeqList *L,int i,datatype x) // 插入结点函数
{ int j;
if (L->last= =MAXLEN-1)
{ cout<< “ 顺序表已满！”; return(-1);}
if( i<1 || ) // 检查插入位置的正确性
{ cout<< “ 位置出错！”; return(0);}
for (j=L->last; ; j—) // 结点移动
;
L->Lata[i-1]= ; // 新结点插入
; （或）
return(1);
}

2．一个带头指针的单链表，写出在值为x的结点之后插入m个结点的算法。
void insertm (lklist head; int m)
{ p=head->next;
while (p!=NULL) && ( p->data != m )
p= p->next ;
if ( p-data==m )
{ q=p->next;
for ( i=0; i< m-1 ; i++ ) // 找到x，在其后插入m个结点
{ s=new (node);
cin<< a ; // 输入待插入的值
s->data= a ;
p->next=s;
p=s; }
p->next=q;
}
}
3．有两个循环单链表，头指针分别为head1和head2，下列函数是将链表head1链接到链表head2，链接后的链表仍然是循环链表，试完成下列程序填空。
（提示：先找到两链表的尾指针，再将第一个链表的尾指针与第二个链表的头结点链接起来）
node link (node head1, node head2)
{ node p, *q;
p=head1;
while (p->next!=head1)
p= p->next ;
q= head2 ;
while (q->next !=head2 )
q=q->next;
p->next= head2 ;
q->next= head1 ;
return (head1);
}

第三单元栈

一．判断题（下列各题，正确的请在前面的括号内打√；错误的打╳ ）
（f ~~t）（1）栈是运算受限制的线性表。
操作受限？
（f~~ t）（2）在栈空的情况下，不能作出栈操作，否则产生下溢出。？
（ f ）（3）栈一定是顺序存储的线性结构。（不一定）
（ t ）（4）栈的特点是“后进先出”。
（ f ）（5）空栈就是所有元素都为0的栈。
空栈是
（ f ）（6）在C或C++语言中设顺序栈的长度为MAXLEN，则top=MAXLEN时表示队满。
不一定，初始化时top=-1? top=0?
栈满时top=max-1 top=max
（ t ）（7）链栈与顺序栈相比，其特点之一是通常不会出现栈满的情况。
（ f ）（8）一个栈的输入序列为：A，B，C，D，可以得到输出序列：C，A，B，D。
（ f ）（9）递归定义就是循环定义。
（ t ）（10）将十进制数转换为二进制数是栈的典型应用之一。
十转二？二转十？看一下具体算法

二．填空题
（1）在栈结构中，允许插入、删除的一端称为栈顶。
（2）在顺序栈中，当栈顶指针top=-1时，表示栈空。
（3）在有n个元素的栈中，进栈操作的时间复杂度为 O(1) 。
（4）在栈中，出栈操作的时间复杂度为： O(1) 。
（5）已知表达式，求它的后缀表达式是栈的典型应用。
（6）在一个链栈中，若栈顶指针等于NULL，则表示栈空。
（7）向一个栈顶指针为top的链栈插入一个新结点*p时，应执行 p->next=p 和top=p 操作。
（8）顺序栈S存储在数组 S->data[0..MAXLEN-1]中，进栈操作时要执行的语句有：
S->top ++ 。（或 S->top+1 ）
（9）链栈LS，指向栈顶元素的指针是 LS-next 。
（10）从一个栈删除元素时，首先取出栈顶元素，然后再移动栈顶指针。
（11）由于链栈的操作只在链表的头部进行，所以没有必要设置 ~~ 尾~~ 头结点。
（12）已知顺序栈S，在对S进行进栈操作之前首先要判断栈是否为满。
（13）已知顺序栈S，在对S进行出栈操作之前首先要判断栈是否为空。
（14）若内存空间充足，链栈可以不定义栈满运算。
（15）链栈LS是空的条件是 ~~top=NULL~~ LS->next=NULL 。
（16）链栈LS的栈顶元素是链表的首元素。
（17）同一栈的各元素的类型相同。
（18）若进栈的次序是A、B、C、D、E，执行三次出栈操作以后，栈顶元素为 B 。
（20）四个元素按A、B、C、D顺序进S栈，执行两次Pop（S，x）运算后，x的值是 C 。

三．选择题
（1）插入和删除只能在一端进行的线性表，称为( )。
A．队列 B．循环队列 C．栈 D．循环栈
（2）设有编号为1，2，3，4的四辆列车，顺序进入一个栈结构的站台，下列不可能的出站顺序为 ( )
A．1234 B．1243 C．1324 D．1423
（3）如果以链表作为栈的存储结构，则出栈操作时（）
A．必须判别栈是否满 B．必须判别栈是否空
C．必须判别栈元素类型 D．队栈可不做任何判别
（4）元素A,B,C,D依次进栈以后，栈顶元素是（）
A．A B．B C．C D．D
（5）顺序栈存储空间的实现使用（）存储栈元素。
A．链表 B．数组 C．循环链表 D．变量
（6）在C或C++语言中，一个顺序栈一旦被声明，其占用空间的大小（）。
A．已固定 B．不固定 C．可以改变 D．动态变化
（8）链栈与顺序栈相比，有一个比较明显的优点是（）。
A．插入操作更加方便 B．通常不会出现栈满的情况。
C．不会出现栈空的情况 D．删除操作根加方便
（9）从一个栈顶指针为top的链栈中删除一个结点时，用x保存被删除的结点，应执行下列 ( )命令。
A．x=top;top=top->next; B．top=top->next;x=top->data;
C．x=top->data; D．x=top->data;top=top->next;

（7）带头结点的链栈LS的示意图如下，栈顶元素是（）

A．A B．B C．C D．D
（10）在一个栈顶指针为HS的链栈中，将一个S指针所指的结点入栈，应执行下列 ( )命令。
A．HS->next=S; B．S->next=HS->next;HS->next=S;
C．S->next=HS->next;HS=S; D．S->next=HS;HS=HS->next;

（11）四个元素按A、B、C、D顺序进S栈，执行两次Pop（S，x）运算后，栈顶元素的值是（）。
A．A B．B C．C D．D
（12）元素A,B,C,D依次进栈以后，栈底元素是（）。
A．A B．B C．C D．D
（13）经过下列栈的运算后，再执行ReadTop(s)的值是（）。
InitStack(s)（初始化栈）;Push(s,a);Push(s,b); Pop(s)
A．a B．b C．1 D．0
（14）经过下列栈的运算后，x的值是（）。
InitStack(s)（初始化栈）;Push(s,a);Push(s,b); ReadTop(s);Pop(s,x);
A．a B．b C．1 D．0
（15）经过下列栈的运算后，x的值是（）。
InitStack(s)（初始化栈）;Push(s,a);Pop(s,x);Push(s,b);Pop(s,x);
A．a B．b C．1 D．0
（16）经过下列栈的运算后，SEmpty(s)的值是（）。
InitStack(s)（初始化栈）; Push(s,a); Push(s,b);Pop(s,x); Pop(s,x);
A．a B．b C．1 D．0
（17）向顺序栈中压入元素时，（）。
~~A．先存入元素，后移动栈顶指针 ~~ B．先移动栈顶指针，后存入元素
C．谁先谁后无关紧要 D．同时进行
（18）初始化一个空间大小为5的顺序栈S后，S->top的值是（）。
A．0 B．-1 C．不再改变 D．动态变化
（19）一个栈的入栈次序ABCDE，则栈的不可能的输出序列是 ( )。
A．EDCBA B．DECBA C．DCEAB D．ABCDE
（20）设有一个顺序栈S，元素A,B,C,D,E,F,依次进栈，如果六个元素出栈的顺序是B，D，C，F，E，A，则栈的容量至少应是 ( )。
A．3 B．4 C．5 D． 6

四．设有一个栈，元素进栈的次序为：A，B，C，D，E，用I表示进栈操作，O表示出栈操作，写出下列出栈的操作序列。
（1）C，B，A，D，E
（2）A，C，B，E，D
解：（1）IIIOOOIOIO（2）IOIIOOIIOO

五．求后缀表达式
（1） A^B^C/D
（2） -A+BC+D/E
（3） A(B+C)D-E
（4） (A+B)C-E/(F+G/H)-D
（5） 8/(5+2)-6
（19）A+B/C-DE的后缀表达式是： ABC/+DE- 。
解:
（1）
（2）
（3）
（4）
（5）

六．算法设计题
1．设用一维数组stack[n]表示一个堆栈，若堆栈中每个元素需占用M个数组单元（M>1），（1）试写出其入栈操作的算法。
（2）试写出其出栈操作的算法。

2．设计一个算法，要求判别一个算术表达式中的圆括号配对是否正确。

1．解：用一整型变量top表示栈顶指针，top为0时表示栈为空。栈中元素从S [1]开始存放元素。
（1）入栈算法：
void push (char x)
{

}
（2）出栈算法：
void pop (char x)
{

}

2．解：设表达式在字符数组a[ ]中，使用一堆栈S来帮助判断。
int correct (char a[ ])
{

}

**模拟考题
求后缀表达式
1．求下列表达式：A/B∧C+DE-AC的后缀表达式。
解：
2．求下列表达式：A/B-C+D*E-F的后缀表达式。
解：

写出运行下列程序段的输出结果
void main()
{ Stack S;
char x,y;
InitStack(S); // 初始化栈
x= “c “;
y= “k “;
Push(S,x); Push(S, “a “);
Push(S,y); Pop(S,x);
Push(S, “t “); Push(S,x);
Pop(S,x); Push(S, “s “);
While (!SEmpty(S))
{ Pop(S,y);cout<cout<}
答：

程序填空
1. 下列程序是判别一个算术表达式（存在字符数组a[ ]中）的圆括号配对是否正确？试填空完成下列程序。
int correct(char a[ ])
{ stack s ;
InitStack(s); // 初始化栈
for (i=0; i if (a[i]= =’(’)
Push ( ~~a[i] ~~ s,’(’ ); 错误思路参考上面
else if (a[i]= = ’)’ )
{
if SEmpty (s)
return 0; // 若栈为空返回0；否则出栈
else
Pop(s);
}
if (SEmpty(s))
cout<< “ 配对正确！”; // printf (“ 配对正确！”);
else
cout<< “ 配对错误！”; // printf (“ 配对错误！”);
}

2．链栈的存储结构和栈顶指针定义如下，试写出把十进数转换为二进制数的程序。
#define MAXLEN 100
typedef struct stacknode // 定义栈的存储结构
{ int data;
struct stacknode next;
}stacknode;
typedef struct
{ stacknode top; // 定义栈顶的指针
}linkstack;
解：
void Conversion(int n) // 栈的应用：二—十进制转换
{ linkstack s;
int x;
s.top=NULL; // 置栈空
do
{ x=n%2; // 取余数
n= ; // 取新的商
stacknode p=new ; // 申请新结点
p->next=s.top ; // 修改栈顶指针
s.top=p;
s.top->data= ; // 余数入栈
}
while (n);
cout<< “ 转换后的二进制数值为：”; // printf(“ 转换后的二进制数值为：”);
while (s.top) // 出栈处理
{ cout<< ;
stacknode p=s.top;
s.top= ;
delete p ; // 出栈一个余数，收回一个结
}
}

第四单元队列

一．判断题（下列各题，正确的请在前面的括号内打√；错误的打╳）
（t ）（1）队列是限制在两端进行操作的线性表。
（t ）（2）判断顺序队列为空的标准是头指针和尾指针都指向同一个结点。
（f）（3）在链队列上做出队操作时，会改变front指针的值。—概念忘了
（f）（5）在单向循环链表中，若头指针为h，那么p所指结点为尾结点的条件是p=h。
（t）（6）链队列在一定范围内不会出现队满的情况。
（f）（7）在循环链队列中无溢出现象。
（f）（8）栈和队列都是顺序存储的线性结构。
（t f）（9）在队列中允许删除的一端称为队尾。 —概念忘了
（f）（10）顺序队和循环队关于队满和队空的判断条件是一样的。

二．填空题
（1）在队列中存取数据应遵循的原则是先进先出。
（2）队列是被限定为只能在表的一端进行插入运算，在表的另一端进行删除运算的线性表。
（3）在队列中，允许插入的一端称为队尾。
（4）在队列中，允许删除的一端称为队头。
（5）队列在进行出队操作时，首先要判断队列是否为空。
（6）顺序队列在进行入队操作时，首先要判断队列是否为满。
（7）顺序队列初始化后，front=rear= -1 。
（8）解决顺序队列“假溢出”的方法是采用循环队列。
（9）循环队列的队首指针为front，队尾指针为rear，则队空的条件为 front == rear 。
（10）链队列LQ为空时，LQ->front->next= NULL 。
（11）设长度为n的链队列用单循环链表表示，若只设头指针，则入队操作的时间复杂度为 O(n) 。
（12）设长度为n的链队列用单循环链表表示，若只设尾指针，则出队操作的时间复杂度为 ~~O(1)~~ O(n) 。
（13）在一个链队列中，若队首指针与队尾指针的值相同，则表示该队列为空。
（15）在一个链队列中，若队首指针为front，队尾指针为rear，则判断该队列只有一个结点的条件为： front==rear && front !NULL 。(或 front==rear && front <>NULL )
（16）向一个循环队列中插入元素时，首先要判断 ~~队满 ~~ 队尾指针，然后再向指针所指的位置写入新的数据。
（17）读队首元素的操作不改变队列元素的个数。
（20）队列Q经过InitQueue(Q)(初始化队列);InQueue(Q,a);InQueue(Q,b); ReadFront(Q,x)后，x的值是 a 。

（~~f ~~t）（4）在循环队列中，若尾指针rear大于头指针front，其元素个数为rear- front。
（14）设循环队列的头指针front指向队首元素，尾指针rear指向队尾元素后的一个空闲元素，队列的最大空间为MAXLEN，则队满标志为： front==(rear+1)%MAXLEN 。
（18）设循环队列的容量为40（序号从0到39），现经过一系列的入队和出队运算后，有 front=11，rear=19，则循环队列中还有 8 个元素。
（L= (N＋rear－front)% N=（40＋19－11）% 40=8）
（14）循环队列SQ队满的条件是( )。
A．SQ->rear==SQ->front B．(SQ->rear+1)% MAXLEN ==SQ->front
C．SQ->rear==0 D．SQ->front==0

三．选择题
（1）队列是限定在（）进行操作的线性表。
A．中间 B．队首 C．队尾 D．端点
（2）队列中的元素个数是( )。
A．不变的 B．可变的 C．任意的 D．0
（3）同一队列内各元素的类型( )。
A．必须一致 B．不能一致 C．可以不一致 D．不限制
（4）队列是一个( )线性表结构。
A．不加限制的 B．推广了的 C．加了限制的 D．非
（5）当利用大小为n的数组顺序存储一个队列时，该队列的最后一个元素的下标为（ B ）。
A．n-2 B．n-1 C．n D．n+1
（6）一个循环队列一旦说明，其占用空间的大小（）。
A．已固定 B．可以变动 C．不能固定 D．动态变化
（7）循环队列占用的空间( )。
A．必须连续 B．不必连续 C．不能连续 ~~ D．可以不连续(链)~~
（8）存放循环队列元素的数组data有10个元素，则data数组的下标范围是( )。
A．0..10 B．0..9 C．1..9 D．1..10
（9）若进队的序列为：A，B，C，D，则出队的序列是（）。
A．B，C，D，A B．A，C，B，D
C．A，B，C，D D．C，B，D，A
（10）四个元素按：A，B，C，D顺序连续进队Q，则队尾元素是（）。
A． A B． B
C． C D． D
（11）四个元素按：A，B，C，D顺序连续进队Q，执行一次OutQueue(Q)操作后，队头元素是（）。
A． A B． B C． C D． D

（19）队列Q，经过下列运算：InitQueue(Q)(初始化队列);InQueue(Q,a); InQueue(Q,b);OutQueue(Q,x); ReadFront(Q,x);QEmpty(Q);后的值是 0 。
（12）四个元素按：A，B，C，D顺序连续进队Q，执行四次OutQueue(Q)操作后，再执行QEmpty(Q);后的值是 A． 0 B． 1 C． 2 D． 3
（13）队列Q，经过下列运算后，x 的值是（）。
InitQueue(Q)(初始化队列);InQueue(Q,a); InQueue(Q,b);OutQueue(Q,x);ReadFront (Q,x);
A．a B．b C．0 D．1
（19）队列Q，经过下列运算后，再执行QEmpty(Q) 的值是（）。
InitQueue(Q) (初始化队列);InQueue(Q,a); InQueue(Q,b);OutQueue(Q,x);ReadQueue(Q,x);
A．a B．b C．0 D．1

（15）设链栈中结点的结构：data为数据域，next为指针域，且top是栈顶指针。若想在链栈的栈顶插入一个由指针s所指的结点，则应执行下列（）操作。
A．s->next=top->next；top->next=s； B．top->next=s；
C．s->next=top；top=top->next； D．s->next=top；top=s；
（16）带头结点的链队列LQ示意图如下，链队列的队头元素是（）

A．A B．B C．C D．D
（17）带头结点的链队列LQ示意图如下，指向链队列的队头指针是（）

A．LQ->front B．LQ->rear
C．LQ->front->next D．LQ->rear->next
（18）带头结点的链队列LQ示意图如下，在进行进队运算时指针LQ->front（）

A．始终不改变 B．有时改变 C．进队时改变 ~~D．出队时改变~~
（20）若用一个大小为6的数组来实现循环队列，且当前front和rear的值分别为3和0，当从队列中删除一个元素，再加入两个元素后，front和rear的值分别为( b )。
A．5和1 B．4和2 C．2和4 D．1和5

四．写出程序运行的结果
写出下列程序段的输出结果（队列中的元素类型为char）。
void main( )
{
Queue Q; InitQueue (Q); // 初始化队列
char x=”E”; y=”C”;
InQueue (Q, “H”);
InQueue (Q, “R”);
InQueue (Q, y);
OutQueue (Q,x); InQueue (Q,x);
OutQueue (Q,x); InQueue (Q, “A”);
while (!QEmpty(Q))
{
OutQueue (Q,y);
printf(y);
};
printf(x);
}
答：输出为“CHAR”。

五．程序填空
1．假定用一个循环单链表表示一个循环队列，该队列只设一个队尾指针rear，试填空完成向循环队列中插入一个元素为x的结点的函数。
typedef struct queuenode // 定义队列的存储结构
{ int data;
struct queuenode next;
}qu;
InQueue(rear,x) // 向队列插入元素为x的函数
{ qu rear；
int x；
{ qu head,s;
s= new qu ;
s->data= x ;
if (rear==NULL) // 循环队列为空，则建立一个结点的循环队列
{ rear=s; rear->next;}
else
{ head= rear-next ; // 循环队列非空，则将s插到后面
rear->next= s ;
rear=s;
~~s->next ~~ rear-next =head;}
}

六. 算法设计题
1．设一个循环队列Queue，只有头指针front，不设尾指针，另设一个含有元素个数的记数器cont，试写出相应的入队算法和出队算法。
2．用一个循环数组Q[0..MAXLEN-1]表示队列时，该队列只有一个头指针front，不设尾指针，而改置一个记数器count用以记录队列中结点的个数。试编写一个能实现：初始化队列、判队空、读队头元素、入队操作和出队操作的算法。
3．一个用单链表组成的循环队列，只设一个尾指针rear，不设头指针，请编写他如下算法：
（1）向循环队列中插入一个元素为x的结点；
（2）从循环队列中删除一个结点。

1．解：用一个循环数组Queue[0，n-1]表示该循环队列，头指针为front，计数器count用来记录队列中结点的个数。

2．解：队列为空：count==0
队列为满：count=MAXLEN
队尾第一个元素位置==(front+count)%MAXLEN
队首第一个元素位置==(front+1)%MAXLEN
const MAXLEN=100;
int queue[MAXLEN];
int front,count; // 定义队头和计数器count

3．

第六单元树与二叉树

掌握树的定义，树的逻辑表示方法，树的基本术语，了解树的性质，树的基本性质，树的存储结构掌握给定树的先根遍历和后根遍历，画出该树。重点掌握二叉树的定义性质P198—-P213 重点掌握二叉树的遍历，二叉树与森林之间的转换，二叉树的构造。重点哈夫曼树的概念及构造过程（*） P241 例7.20

一．判断题（下列各题，正确的请在前面的括号内打√；错误的打╳ ）
（ f ）（1）二叉树是一般树的特殊情形。

      二叉树是另一种树形结构，以递归的形式定义
      二叉树不是一种特殊的树，二叉树可以为空，树不能为空。
树和二叉树的2个主要差别： 1、树中结点的最大度数没有限制，而二叉树结点的最大度数为2； 2、树的结点无左、右之分，而二叉树的结点有左、右之分。……

题目详解 - 图23
（ f ）（2）二叉树是度为2的有序树。

度：一个节点的孩子数二叉树与度为2的树的区别 1：度为2的树至少有3个节点，二叉树可以为空。2：

（ f ）（3）对于有n个结点的二叉树，其高度为。

不确定：如果是完全二叉树则是[]+1，有计算公式。其他的二叉树没有规律，是没有计算公式的，不确定。忘记了也可以用简单的例子试一下，3个结点二叉树，按题目则为1层，实为2层

（ t ）（4）深度为k的二叉树中结点总数<=。

等比数列求和

（ f ）（5）一棵有n个结点的二叉树，从上到下，从左到右用自然数依次给予编号，则编号为i的结点的左儿子的编号为2i（2i<n），右儿子是2i+1（2i+1<n）。

编号为2i（2i<=n），右儿子是2i+1（2i+1<=n）。

（ t ）（6）完全二叉树的存储结构通常采用顺序存储结构。
（ f ）（7）完全二叉树的前序序列中，若结点u在结点v之前，则u一定是v的祖先。

也可能是兄弟

（ f ）（8）对一棵二叉树进行层次遍历时，应借助于一个栈。

广度（层次遍历）优先遍历用队列，深度优先遍历用栈先序、中序不用，后序需要：最后访问根结点，……….

（ ~~t ~~f）（9）当一棵具有n个叶子结点的二叉树的WPL值为最小时，称其树为Huffman树，则其二叉树的形状必是唯一的。

（ t ）（10）哈夫曼树是带权路径长度最短的树，路径上权值较大的结点离根较近。

二．填空题
（1）含有三个结点的不同的二叉树有 5 棵。
（2）一棵二叉树的结点数据采用顺序存储结构，存储在一维数组t中，t[]={e,a,f,0,d,0,g,0,0,c,j,0,0,l,h,i,0,0,0,0,b}（其中0代表空树），c在树中的层次为 4 。
（3）一棵有n个结点的二叉树，叶子结点的数量为，度为2的结点数量为，则与的关系是n0=n2+1 ；如果用二叉链表存储该二叉树，则空指针数量为 n+1。
（4）树在计算机内的表示方式有双亲链表表示法、孩子链表表示法、孩子兄弟表示法。
（5）在二叉树中，指针p所指结点为叶子结点的条件是 p->lchild==nuLL&&p->rchild==nuLL 。
（6）深度为H的完全二叉树至少有 2^(h-1) 个结点；至多有 2^h-1 个结点；H和结点总数N之间的关系是 H=log2(N+1) 或log2N+1 。

至多：等比数列求和

（7）如果结点A有3个兄弟，而且B是A的双亲，则B的度是 4 。
（8）已知一棵度为3的树有2个度为1的结点，3个度为2的结点，4个度为3的结点，则该树有 12 个叶子结点。
（9）设高为h的二叉树只有度为0和2的结点，则此类二叉树的结点至少为 2h-1 ，至多为 2^h-1 。
（10）一棵有n个结点的满二叉树有 0 个度为1的结点、有(n-1)/2或n/2 个分支（非终端）结点和（n+1）/2 个叶子，该满二叉树的深度为 log2(n+1) 。
（11）高度为K的完全二叉树至少有 2^(k-2) 个叶子结点。
（12）已知二叉树有50个叶子结点，则该二叉树的总结点数至少是 99 。

2^5=32<50<2^6=64 故为5层，总节点数至少为2^(5-1)=16

（13）一个有2001个结点的完全二叉树的高度是10 ~~ 11。2^10=1024<2000<2^11=2048(0为1层，11为10层)
（14）在树的兄弟表示法中，二叉链表的左指针指向 ~~左孩子结点的第一个孩子，右指针指向 ~~右孩子~~ 结点的右兄弟。
（15）先序遍历森林时，首先访问森林中第一棵树的根节点。
（16）将一棵结点编号（从上到下，从左至右）为1到7的满二叉树转变为森林，则中序遍历该森林得到的序列为 4,2,5,1,6,3,7 。
（17）设某二叉树的先序遍历序列为abdgcefh，中序遍历序列为dgbaechf，则其后序遍历序列为 gdbehfca。

先：根左右abdgcefh 中：左根右 dgbaechf

（18）某二叉树的后序遍历序列是dabec，中序遍历序列是debac，前序遍历序列是 cedba 。

后：左右根dabec 中：左根右 debac 后：左右根dabe 中：左根右 deba 后：左右根dab 中：左根右 d ba

（19）将一棵树转换成二叉树后，根节点没有右字树。
（20）有数据WG={7,19,2,6,32,3,21,10}，则所建Huffman树的树高是 6 ，带权路径长度WPL为 261 。

三．选择题
（1）已知一棵完全二叉树的第6层（设根是第1层）有8个叶结点，则该完全二叉树的结点个数最多是（ c ）。
A． 39 B． 52 C．111 D． 119
（2）将森林转换为对应的二叉树，若在二叉树中，结点u是结点v的父结点的父结点，则在原来的森林中，u和v可能具有的关系是（b ）。
I.父子关系 II兄弟关系 III. u的父结点与v的父结点是兄弟关系
A．只有II B． I和II C．.I和III D． I、II和III
（3）在一棵度为4的树T中，若有20个度为4的结点，10个度为3的结点，1个度为2的结点，10个度为1的结点，则树T的叶结点个数是（b ）。
A． 41 B． 82 C．113 D． 122
（4）对n（n>=2)个权值均不相同的字符构造哈夫曼树。下列关于该哈夫曼树的叙述中，错误的是（ a ）。
A. 该树一定是一棵完全二叉树
B. 树中一定没有度为1的结点
C. 树中两个权值最小的结点一定是兄弟结点
D. 树中任一非叶结点的权值一定不小于下一层任一结点的权值
（5）若一棵完全二叉树有768个结点，则该二叉树中叶结点的个数是（ c ）。
A． 257 B． 258 C．384 D． 385

2^9=512<768<2^10=1024

（6）若一棵二叉树的前序遍历序列和后序遍历序列分别是1,2,3,4和4,3,2,1，则该二叉树的中序遍历序列不会是（）。
A． 1,2,3,4 B． 2,3,4,1 C．3,2,4，1 D． 4,3,2,1

前:根左右1,2,3,4 后:左右根4,3,2,1 前:根左右 2,3,4 后:左右根4,3,2 前:根左右 3,4 后:左右根4,3 中序左根右 规律：234一定在同一侧，每层只有一个结点，从上到下结点字母变大 C选项，根结点为2时，34应该在2的同侧

（7）已知一棵有2011个结点的树，其叶结点个数为116，该树对应的二叉树中无右孩子的结点个数是（ d ）。
A． 115 B． 116 C．1895 D． 1896

（8）已知一棵二叉树的前序遍历序列为a,e,b,d,c,后序遍历序列为b,c,d,e,a,则根结点的孩子结点（）。
A．只有e B．有e、b C．有e、c D．无法确定

前：根左右：a,e,b,d,c 后：左右根b,c,d,e,a 前：根左右： e,b,d,c 后：左右根b,c,d,e

（9）已知三叉树T中有6个叶结点的权分别是2,3,4,5,6,7，T的带权（外部）路径长度最小是（ b ）。
A． 27 B． 46 C．54 D． 56
（10）先序序列为a,b,c,d的不同二叉树的个数是（ c ）。
A． 13 B． 14 C．15 D． 16

类似6题

（11）下列选项给出的是从根分别到达两个叶结点路径上的权值序列，能属于同一棵哈夫曼树的是（ 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
（12）以下说法中，（）是正确的。
A. 完全二叉树中，叶结点的双亲的左兄弟（如果存在）一定不是叶结点
B. 任何一棵二叉树，叶子结点树为度为2的结点树减1
C. 二叉树不适合用顺序结构存储
D. 结点按层序编号的二叉树，第i个结点的左孩子（如果存在）的编号为2i

A a
      ** b**           d    
                  **c**
B C 不一定，具体情况具体分析 D 2I<=n???

（13）具有300个结点的二叉树，其高度至少应为（ d ）。
A． 6 B． 7 C．8 D． 9

2^8=256<300<2^9=512

（14）从树根（第0层）起，自上到下，逐层从左到右给二叉树的所有结点从1开始编号，则完全二叉树的第h层的从左到右第k个结点的编号为（ a ）。
A． +k-1 B． -k+1 C．+k+1 D． -k-1

0 2^0 1 2 2^1 2 3 h 2^h 2^h 2^h+1

（15）设二叉树中有个度为2的结点，有个度为1的结点，有个度为0的结点，则该二叉树中空指针个数为（ d ）。
A． ++ B． ++2 C．2+ D． +2

（16）设m、n为一棵二叉树上的两个结点，在中序遍历时，n在m前的条件是：（）。
A． n在m右方 B． n是m祖先 C．n在m左方 D．n是m子孙

中：左根右

（17）已知一棵二叉树的前序遍历结果为ABCDEF，中序遍历结果为CBAEDF，则后序遍历的结果为（）。
A． CBEFDA B． FEDCBA C．CBEDFA D．不定

前：根左右ABCDEF 中：左根右CBAEDF a b d c e f

（18）某二叉树结点的中序序列为BDAECF，后序遍历为DBEFCA，则该二叉树对应的森林包括（ c ）棵树。
A． 1 B． 2 C． 3 D． 4

中：左根右 BDAECF 后：左右根 DBEFCA A B C D E F

（19）一棵非空的二叉树的先序序列和后序序列正好相反，则该二叉树一定满足（ c ）。
A. 其中任意一个结点均无左孩子 B. 其中任意一个结点均无右孩子
C. 其中只有一个叶子结点 D.其中度为2的结点最多为一个

先：根左右后：左右根正好相反：全部为左孩子或者全部为右孩子

（20）在下列存储形式中，哪一个不是树的存储形式？（）。
A．双亲表示法 B．孩子链表表示法 C．孩子兄弟表示法 D．顺序存储表示法
四．应用题
1、将下列由三棵树组成的森林转换为二叉树（只要求给出转换结果）

2、已知树的先根遍历序列为：EAFGBHDC，后根遍历序列为：FABDHGCE，画出对应的树。

先：根左右EAFGBHDC 后：左右根FABDHGCE e a g c f b h d

3、将此二叉树变换为森林

4、设A,B,C,D,E,F的权值依次为{4,2,7,11,8,9}。
（1）列出构造相应的哈夫曼树的过程；
（2）计算该哈夫曼树的带权路径长度；

（3）分别列出字符A,B,C,D,E,F的哈夫曼编码
A:1101 B:1100 C:111
D:10 E:00 F:01

五．程序填空
1、将二叉树bt中每一个结点的左右子树互换的c语言算法如下，其中ADDQ（Q,bt），DELQ（Q），EMPTY（Q）分别为进队、出队和判别队列是否为空的函数，请填写算法中空白之处，完成其功能。

2、二叉树中序遍历的非递归算法。

六．程序设计题
1、设计一算法分别求出二元树的叶结点，度数为1的结点，度数为2的结点的个数。
2、设一棵完全二叉树使用顺序存储在数组bt[1..n]中，请写出进行非递归的前序遍历算法。
3、试给出二叉树的自下而上，自右而左的层次遍历算法。
4、编写一算法，利用叶子结点中的空指针域将所有叶子结点链接为一个带有头结点的双链表，算法返回头结点地址。

第七单元图

以下部分，代码不作要求

图的定义，图的基本术语，图的存储结构与基本算法，图的遍历。（给定图，能写出图的邻接矩阵与邻接表）
给定一个图的某一个点，能输出从该点开始的DFS及BFS，以及与之对应的最小生成树。
重点掌握Prim,Kruskal,Dijkstra,Floyd算法的过程
掌握拓扑排序，AOE网与关键路径（能求出每个事件的最早发生时间，最迟发生时间，每个活动的最早发生时间，每个活动的最迟发生时间，及每个活动的时间余量，由此确认关键活动与关键路径）

一．判断题（下列各题，正确的请在前面的括号内打√；错误的打╳ ）
（ f ）（1）n个顶点的无向图至多有n（n-1）条边。

举例：n=3时，最多有3边。但n(n-1)=6
       n=4时，最多有6边。但n(n-1)=12

（ f ）（2）邻接矩阵总是优于邻接表。

不一定，具体情况具体分析

（ t ）（3）在有向图中，所有顶点的入度之和等于所有顶点的出度之和。
（ ~~t ~~f ）（4）如果表示有向图的邻接矩阵是对称矩阵，则该有向图一定是完全有向图。

0 1 1 1 0 1 1 1 0

（ t ）（5）强连通分量是有向图中的极大强连通子图。
（ f ）（6）由一个图的顶点子集和该图的边子集构成该图的子图。

（ f ）（7）对有向图G，如果以任一顶点出发进行一次深度优先或广度优先遍历能访问到每个顶点，则该图一定是完全图。

是连通图不一定是完全图(任意俩顶点都存在边)

（ f ）（8）有n个顶点e条边的图采用邻接表表示，其深度优先搜索遍历算法的时间复杂度为O（e）。

图G由顶点集V和边集E组成。 DFS是递归算法，实现需要借助一个工作栈，空间复杂度为O(|V|) 时间复杂度：每个顶点找其邻接点的过程：用邻接矩阵，总为O(|V|^2) 用邻接表，总为O(|V|+|E|) E:查找所有顶点的邻接点 V:访问顶点所需的时间]

（ f ）（9）任何有向图都能产生拓扑序列。

错，要满足一些条件

（ f ）（10）一个AOV网的拓扑序列是唯一的。不一定

二．填空题
（1）在一个无向图中，所有顶点的度之和等于边数的 2 倍。
（2）有n个顶点的有向图中，每个顶点的度最大可达 2（n-1）。
（3）图的邻接矩阵和邻接表存储结构中，邻接矩阵是唯一的，而邻接表是不唯一的。

（4）用邻接矩阵存储一个不带权有向图G，其第i行的所有元素之和等于顶点i的出度；其第i列的所有元素之和等于顶点i的入度。
（5）对于一个具有n个顶点和e条边的无向图，若采用邻接表表示，则表头节点的个数为 n ；邻接表中边表节点的个数为 2e 。对于一个具有n个顶点和e条边的有向图，若采用邻接表表示，则表头节点的个数为 n ；邻接表中边表节点的个数为 e 。

（6）已知一个有向图的邻接矩阵表示，删除所有从第i个顶点出发的边的表示方法是第i行所有不为0的元素置0 。已知一个无向图的邻接矩阵表示，删除所有从第i个顶点出发的边的表示方法是第i行第i列所有不为0的元素置0 。
（7）对n个顶点的连通图来说，它的生成树一定有 n-1 条边。
（8）一个连通图的生成树是该图的一个子图。
（9） AOV网中，结点表示活动。边表示活动的优先顺序。AOE网中，结点表示事件，边表示活动，边e的权表示完成活动e所需的时间。
（10）可以进行拓扑排序的有向图一定是无环图。
（11）设有向图G如图所示。其所有的拓扑序列为 0213、0123、1023 ；当添加一条边 ~~ 12 ~~ <1,2> 后，则仅可能有唯一的拓扑序列。
（12）为了实现图的广度优先搜索遍历，除了一个标志数组标志已访问的图的结点外，还需队列以存放被访问的结点以实现遍历。

广度优先还不是熟

（13）求图的最小生成树有两种算法， Kruskal 算法适合于求稀疏图的最小生成树。

王道228

（14）在AOE网中，从源点到汇点路径上各个活动的时间总和最长路径称为关键路径。
（15）在拓扑分类中，拓扑序列的最后一个顶点必定是出度为0 的顶点。
（16）在AOV网中，存在环意味着某项活动以自己为先决条件，这是荒谬的；对程序的数据流图来说，它表明存在死循环。
（17）如果具有n个顶点的图是一个环，则它有 ~~ 1~~ 2n 棵生成树。
（18）有n个顶点的有向图，至少需要 n-1 条弧才能保证是连通的。
（19） n个顶点的无向图的邻接矩阵至少有 2（n-1）个非零元素；n个顶点的有向图是强连通图至少有 n 条边。
（20） 在数据结构中，线性结构、树形结构和图形结构数据元素之间分别存在一对一、一对多。和多对多的联系。

三.选择题
（1）一个有n个顶点的有向图最多有（）条边。
A． n B． n（n-1） C．n（n-1）/2 D． 2n

n=2 2 n=3 6 n=4 12

（2）一个无向图中有16条边，度为4的顶点有3个，度为3的顶点有4个，其余顶点的度均小于3，则该图至少有（）个顶点。b
A． 10 B． 11 C．12 D． 13
（3）一个图的邻接矩阵是对称矩阵，则该图一定是（）。
A．无向图 B．有向图 C．无向图或有向图 D．以上都不对
（4）关于邻接表的叙述中，（）是正确的。
A.无向图的邻接表中，第i个顶点的度为第i个单链表中节点的2倍
B.邻接表比邻接矩阵操作更简便
C.邻接矩阵比邻接表操作更简便
D.求有向图节点的度，必须遍历整个邻接表

A.上面有图，相等 BC看情况

（5）带权有向图G用邻接矩阵A存储，则顶点i的入度等于A中（）。
A.第i行非∞的元素之和 B.第i列非∞的元素之和
C.第i行非∞且非0的元素之和 D.第i列非∞且非0的元素之和
（6）采用邻接表存储的图的深度优先搜索遍历算法类似于二叉树的（）算法。
A.先序遍历 B.中序遍历 ~~ C.后序遍历~~ D.层次遍历

概念不熟

（7）对有n个顶点的图进行深度优先搜索遍历，其空间复杂度为（）。
A.O（l） B.O(n) C.O() D.不确定
（8）以下叙述错误的是（）。
A.图的遍历是从给定的初始点出发访问每个顶点且每个顶点仅访问一次
B.图的深度优先搜索遍历适合无向图
C.图的深度优先搜索遍历不适合有向图（不一定）
D.图的深度优先搜索遍历是一个递归过程

（9）任何一个无向连通图（）最小生成树。
A.只有一棵 B.有一棵或多棵 C.一定有多棵 D.可能不存在
（10）关键路径是事件节点网络中（）。
A.从源点到汇点的最长路径 B.从源点到汇点的最短路径
C.最长的回路 D.最短的回路
（11）关键路径由（）构成。
A.关键事件 ~~ B.关键活动 ~~~~ ~~ C.所有事件 D.所有活动
（12）一个表示工程的AOE网中的关键路径（）。
A.必须是唯一的 B.可以有多条 C.可以没有 D.以上都不对
（13）判断有向图是否有回路，除了可以用拓扑排序外，还可以用（）。
A.求关键路径的方法 B.广度优先搜索遍历算法
C.求最短路径的算法 D.深度优先搜索遍历算法
（14）在求边稠密的图的最小生成树时，采用（）算法比较合适。
A.普里姆 B.克鲁斯卡尔 C.迪杰斯特拉 D.其他
（15）在下列网中，（）是边不带权值的图。
A.邮电图 B.AOV网 C.公路网 D.AOE网
（16）下面关于求关键路径的说法不正确的是（）。
A.求关键路径是以拓扑排序为基础的
B.一个事件的最早开始时间同以该事件为尾的弧的活动最早开始时间相同
C.一个事件的最迟开始时间为以该事件为尾的弧的活动最迟开始时间与该活动的持续时间的差
D.关键活动一定是在关键路径上

不太懂

（17）对下图进行拓扑排序，可以得到不同拓扑序列的个数是（）。
A.4 B.3 C.2 D.1
aebcd、abced、abecd、
（18）下面AOE网表示一项包含8个活动的工程。通过同时加快若干活动的进度可以缩短整个工程的工期。下列选项中，加快其进度就可以缩短工程工期的是（）。
A.c和e B.d和c C.f和d D.f和h

全部关键路径：bdcg、bdeh、bfh (只有C包含在所有的关键路径中)

（19）设图的邻接矩阵A如下图所示。各顶点的度依次是（）。
A.1,2,1,2 B.2,2,1,1 C.3,4,2,3 D.4,4,2,2

（20）已知图的邻接表如下，根据算法，则从顶点0出发按广度优先遍历的结点序列是（）。
A.0321 B.0123 C.0132 D.0312

四．应用题
1、给出图G：
（1）画出G的邻接表表示图和邻接矩阵表示图；
（2）根据你画的邻接表，以顶点1为根，画出G的深度优先生成树和广度优先生成树，并分别写出其顶点序列。

顶点序列：1,2,5,3,4,7,6,8,9,10 1,2,3,4,5,6,7,8,9,10
2、一带权无向图的邻接矩阵如下，试画出它的一棵最小生成树。

3、对于下图所示的无向带权图，用普里姆算法从顶点1开始求最小生成树，求：按次序产生的边，共多少条边；用克鲁斯卡尔算法产生的边次序是什么。（注：边用（i，j）的形式表示）

普里姆按次序产生的边：（1,3）：5，（3,4）：6，（4,6）：4，（6,5）：9，（1:2）：12
共五条边
克鲁斯卡尔：（4,6）：4，（1,3）：5，（3,4）：6，（5,6）：9，（1,2）：12

~~五．程序设计题~~
~~1、假设不带权图采用邻接表存储，分别设计实现以下要求的算法：~~
~~（1）求出图中每个顶点的入度；~~
~~（2）求出图中每个顶点的出度；~~
~~（3）求出图中出度最大的一个顶点，输出该顶点编号；~~
~~（4）计算图中出度为0的顶点数；~~
~~（5）判断图中是否存在边.~~
~~2、设计一个算法，求不带权无向连通图G中距离顶点V最远的一个顶点~~
~~3、假设图采用邻接表存储，分别写出基于DFS和BFS遍历的算法来判别顶点i和顶点j （i！=j）之间是否有路径~~

第八单元查找排序

以下部分，代码不作要求第九章查找掌握查找的基本概念，重点掌握折半查找（P320 例9.1) 掌握二叉排序树的概念，重点掌握AVL树的概念及失去平衡后四种调整方法（P336 例9.5) 掌握hash表基本概念，hash函数的构造方法，hash冲突的解决办法(P350 例9.9) 第十章内排序掌握排序的基本概念直接插入排序与希尔排序冒泡排序与快速排序选择排序与堆排序归并排序基数排序每种排序数据的变化过程要掌握。

一．判断题（下列各题，正确的请在前面的括号内打√；错误的打╳ ）
（ t ）（1）顺序查找法适用于存储结构为顺序或链式存储的线性表。
（ f ）（2）折半查找可以在有序的双向链表上进行。

折半查找只能是顺序存储且要求关键字有序

（ t ）（3）在二叉排序树中，每个节点的关键字都比左孩子关键字大，比右孩子关键字小。
（ ~~ t ~~ f ）（4）在二叉排序树中，新插入的关键字总是处于最底层。
（ t ）（5）二叉排序树的查找效率和二叉排序树的高度有关。
（ f ）（6）在一棵二叉排序树中删除关键字为k的节点，然后再插入关键字为k的节点，这样的二叉排序树前后没有变化。
（ f ）（7）m阶B-树中任何节点的子树个数都大于或等于m。
（ f ）（8）若哈希表的装填因子α<1,则可以避免冲突的产生。
（ t ）（9）哈希表的查找效率主要取决于哈希表造表时选取的哈希函数和处理冲突的办法。
（ t ）（10）哈希表只能存储数据元素的值，不能存储数据元素之间的关系。

二．填空题
（1）采用顺序查找方法查找长度为n的线性表时，成功查找时的平均比较次数为（n+1）/2 ；不成功情况下平均比较次数为 n 。
（2）在n个记录的有序顺序表中进行折半查找，成功找到一个记录时最大的关键字比较次数是 log2(n+1）
（3）一个线性表采用折半查找时，该线性表必须具有的特点是顺序存储且有序；
而分块查找法要求将待查找的表均匀地b分成若干块且块中记录的顺序是可以任意的，但块与块之间有序。
（4）在分块查找中，首先查找索引表，然后再查找相应的块表。
（5）高度为8的平衡二叉树的节点数最少有 54 个，最多有 255 个节点。
（6）一棵m阶B-树中，若在某节点中插入一个关键字后会引起该节点分裂，则该节点原来有 m 棵子树。
（7）一棵5阶4层的B-树（根节点为第一层，叶子节点为第四层）中，至少有 17 个关键字，至多有 104 个关键字。
（8）设哈希表长m=14，哈希函数H（key）=key MOD 11。表中已有4个节点H（15）=4，H（38）=5，H(61)=6，H(84)=7，其余地址为空，如用平方探测法处理冲突，则关键字为49的节点的地址是 9 。
（9）若采用拉链法构造一个哈希表，其哈希函数为H(key）=key MOD 17，则需 17 。个链表，这些链表的首指针构成一个指针数组，该数组的下标范围为 0~16 。
（10）在哈希函数H（key）=key MOD p中，p最好取小于等于表长的最大素数。
（11）在哈希表查找存储中，装填因子α的值越大，则存取元素时发生冲突的可能性就越大。α的值越小，则存取元素时发生冲突的可能性就越小。
（12）设线性表{a1，a2，…，a500}元素的值由小到大排列，对一个给定的k值用折半查找线性表，在查找不成功的情况下至多需要比较 9 次。
（13）一棵高度为h的m阶B-树，任意一个叶子结点所处的层数为。
（14）顺序查找法适合于存储结构为顺序存储或链式存储的线性表。
（15）对线性表进行折半查找时，要求线性表必须以顺序方式存储，且节点按关键字有序排列
（16）对有18个元素的有序表R【1..18】进行折半查找，则查找R【3】的比较序列的下标为 9,4,2,3 。
（17）按关键字13,24,37,90,53的次序构成一棵二叉平衡树，它的高度是 3 。根节点为 24 。左子树的数据为 13 。右子树的数据是 37,53,90 。
（１８）高度为６（含叶子结点层）的３阶Ｂ－树至少有 31 个结点。
（１９）有ｎ个元素的数组，查找其中最大值的元素，一般需要 n-1 次元素的比较。
（２０）在含有ｎ个结点的二叉排序树中查找一个关键字，进行关键字比较次数的最大值是 n 。

三.选择题
（1）有一个长度为12的有序表R【0..11】，按折半查找法对该表进行查找，在表内各元素等概率情况下查找成功所需的平均比较次数为（）。
A． 35/12 B． 37/12 C．39/12 D． 43/12

1 2 4 5 成功(11+22+34+45)/12=37/12

（2）有一个有序表为{1，3，9，12，32,41,45,62,75,77,82,95,99}，当采用折半查找法查找关键字为82的元素时，（）次比较后查找成功。
A. 1 B.2 C.4 D.8

第一次 {1，3，9，12，32,41,45,62,75,77,82,95,99} 第二次 { 62,75,77,82,95,99} 向下取整！！！第三次 { ,82,95,99} 第四次 { ,82,}

（3）设有100个元素的有序表，用折半查找时，成功时最大的比较次数为（）。
A.25 B.50 B.10 D.7

log2(n+1)= 2^(5+1)=64<101<2^(6+1)=128

（4）采用分块查找时，若线性表中共有625个元素，查找每个元素的概率相同，假设采用顺序查找来确定节点所在的块时，每块应分（）个节点最佳。
A.10 B.25 C.6 D.625

根号(625)=25

(5)当采用分块查找时，数据的组织方式为（）。
A.数据分成若干块，每块内数据有序
B.数据分成若干块，每块内数据不必有序，但块间必须有序，每块内最大（或最小）的数据组成索引块
C.数据分成若干块，每块内数据有序，每块内最大（或最小）的数据组成索引块
D.数据分成若干块，每块中的数据个数必须相同
（6）在含有27个结点的二叉排序树上，查找关键字为35的结点，则依次比较的关键字有可能是（）。
A.28,36,18,46,35 B.18,36,28,46,35
C.46,28,18,36,35 D.46,36,18,26,35
（7）如图所示的一棵二叉排序树，其成功的平均查找长度是（ c ）；其不成功的平均查找长度是（ a ）。
A.21/7 B.28/7 C.15/6 D.21/6

成功 (11+22+32+41)/6=15/6 不成功(32+43+5*2)/7=21/5

（8）一棵二叉排序树是由关键字集合{18,43,27,44,36,39}构建的，其中序遍历序列是（）。
A. 树形未定，无法确定 B.18,43,27,77,44,36,39
C.18,27,36,39,43,44,77 C.77,44,43,39,36,27,18

先排序18 27 36 39 43 44 77 39 27 44 18 36 43 77

（9）以下关于二叉排序树的叙述中正确的是（）。
A.二叉排序树是动态树表，在查找不成功时，会引起树的重新分裂和组合
B.对二叉排序树进行层次遍历可得到有序序列
C.若用一个有序序列来构造一棵二叉排序树，其高度最大
D.在含有n个结点的二叉排序树中进行查找，关键字的比较次数不超过n/2
（10）有数据集合{53,30,37,12,45,24,96}，从空二叉树开始逐个插入数据来构造一棵二叉排序树。若希望高度最小，则应选择一下哪个序列输入（）。
A.45,24,53,12,37,96,30 B.37,24,12,30,53,45,96
C.12,24,30,37,45,53,96 D.30,24,12,37,45,96,53
（11）在一棵平衡二叉树中，每个节点的平衡因子的取值范围是（）。
A.-1~1 B.-2~2 C.1~2 D.0~1
（12）如图所示的4棵二叉树，（ b ）是平衡二叉树。

（13）平衡二叉树中高度与其节点个数n之间的关系是（）。
A.log2(n) B.n C.n^2 D.2^n

同3(14)含有20个结点的AVL树的最大高度是（）。
A.4 B.5 C.6 D.7

log2(n+1)= 2^(3+1)=16<20<2^(4+1)=32

（15）若在平衡二叉树中插入一个结点就造就了不平衡，设最低的不平衡结点为A，并已知A的左孩子的平衡因子为-1，右孩子的平衡因子为0，则要使其平衡，应做（）。
A.LL型调整 B.RR型调整 C.RL型调整 D.LR型调整

A 左-1 右0 ->

（16）查找效率最高的二叉排序树是（）。
A.所有结点的左子树为空的二叉排序树
B.所有结点的右子树为空的二叉排序树
C.平衡二叉树
D.没有左子树的二叉排序树
（17）一棵m阶B-树中，某非叶子结点有k个孩子结点，则它恰好包含（）个关键字。
A.k+1 B.k C.k-1 D.m/2
(18)下面关于B-和B+树的叙述中，不正确的结论是（）。
A.B-树和B+树都能有效地支持顺序查找
B.B-树和B+树都能有效地支持随机查找
C.B-树和B+树都是平衡的多分树
D.B-树和B+树都可用于文件索引结构

概念不知道！！ B+支持，B树不支持

（19）将10个元素散列到100000个单元的哈希表，则（）产生冲突。
A.一定会 B.一定不会 C.仍可能会 D.以上都不对
（20）在哈希查找过程中，可用（）来处理冲突。
A.除留余数法 B.数字分析法 C.线性探测法 D.关键字比较法

四．应用题
1、有一棵二叉排序树的序列为：（40,28,6,72,100,3,54,1,80,91,38）。回答下列问题：
（1）画出该二叉排序树。（2）画出删除节点72后的二叉树。

（3）给出该二叉排序树的中序遍历序列。（3）1,3,6,28,38,40,54,72,80,91,100
（4）求在等概率情况下成功和不成功的平均查找长度。
成功:（11+22+43+24+25）/11=35/11
不成功：（63+24+25）/10=36/10
2、输入关键字序列{16,3,7,11,9,26,18,14,15}，给出建造的AVL树

3、已知哈希函数H(key)=2key MOD 11,用线性探测法处理冲突。试在0~10的哈希地址空间中对关键字序列{6,8,10,17,20,23,53,41,54,57}构造哈希表。
H（6）=26 MOD 11=1
H（8）=28 MOD 11=5
H（10）=210 MOD 11=9
H（17）=217 MOD 11=1 （冲突）
H（17）=（1+d） MOD 11=（1+1）MOD 11=2
H（20）=220 MOD 11=7
H（23）=223 MOD 11=2 （冲突）
H（23）=（2+d） MOD 11=（2+1）MOD 11=3
H（53）=253 MOD 11=7 （冲突）
H（53）=（7+d） MOD 11=（7+1）MOD 11=8
H（41）=241 MOD 11=5 （冲突）
H（41）=（5+d） MOD 11=（5+1）MOD 11=6
H（54）=254 MOD 11=9 （冲突）
H（54）=（9+d） MOD 11=（9+1）MOD 11=10
H（57）=257 MOD 11=4