1.6 习题
1.6.1 知识点：数据结构的定义
一、选择题
1① 数据结构通常是研究数据的（ A ）及它们之间的相互联系。
A．存储和逻辑结构 B．存储结构 C．顺序结构 D．链式存储结构
2① 数据在计算机存储器内表示时，物理地址与逻辑地址相同并且是连续的，称之为（ C ）
A．存储结构 B．逻辑结构 C． 顺序存储结构 D．链式存储结构 3① 线性结构是数据元素之间存在一种（ D ）。
A．一对多关系 B. 多对多关系 C 多对一关系 D 一对一关系 4① 计算机内部数据处理的基本单位是（ B ）。
A. 数据 B．数据元素 C.数据项 D．数据库
5② 从逻辑上可以把数据结构分为（C ）两大类。【武汉交通科技 1996】
A．动态结构、静态结构 B．顺序结构、链式结构 C．线性结构、非线性结构 D．初等结构、构造型结构 二、填空题
1① 数据结构按逻辑结构可分为四大类，它们分别是 集合 、 线性 、 树 、 图 。
2① 数据的存储结构可用四种基本的存储方法表示，它们分别是 顺序 、 链式 、 散列 、 索引 。 三、 判断题
（ F）1① 数据元素是数据的最小单位。 （ T ）2① 记录是数据处理的最小单位。
（ F ）3① 数据的逻辑结构是指数据的各数据项之间的逻辑关系。 （ T ）4① 数据的物理结构是指数据在计算机内的实际存储形式。 四、 简答题
1① 简述什么是数据结构?
2② 数据结构与数据类型有什么区别? 【哈尔滨工业 2001】
1.6.2 知识点：算法的概念
一、选择题
1① 计算机算法指的是（C ）
A．计算方法
B．排序方法
C．解决问题的有限运算序列
D．调度方法
2① 算法分析的目的是（ （1）C ），算法分析的两个主要方面（ （2）A ）．
（1） A．找出数据结构的合理性
C．分析算法的效率以求改进
（2） A．空间复杂度和时间复杂度
C．可读性和文档性
B．研究算法中的输入与输出的关系 D．分析算法的易查性和文档性 B．正确性和简明性
D．数据复杂性和程序复杂性
3② 设语句 X++的时间是单位时间，则语句： for
（i=1;i<=n;i++） x++;
时间复杂度为（ C ）。
A．O（1） B．O （n） C．O （n2） D．O （n3）
4② 算法的计算量的大小称为计算的（ B ）。【北京邮电 2000】 A．效率 B．复杂性 C．现实性 D．难度
5② 算法的时间复杂度取决于（ C ）【中科院计算所 1998】 A．问题的规模 B．待处理数据的初态 C．A 和 B 6② 下面关于算法说法错误的是（ A ）【南京理工 2000】 A．算法最终必须由计算机程序实现
B．为解决某问题的算法同为该问题编写的程序含义是相同的 C．算法的可行性是指指令不能有二义性 D．以上几个都是错误的
7② 下面说法错误的是（ D ）【南京理工 2000】
（1） 算法原地工作的含义是指不需要任何额外的辅助空间
（2） 在相同的规模 n 下，复杂度 O（n）的算法在时间上总是优于复杂度 O（2n）的算法 （3） 所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界 （4） 同一个算法，实现语言的级别越高，执行效率就越低 A．（1） B．（1）,（2） C．（1）,（4） D．（3） 8② 程序段 for（i=n-1;i>=1;i++） for（ j=1;j<= i;j++）
if（ A[j]>A[j+1]） A[j]与 A[j+1]对换；
其中 n 为正整数，则最后一行的语句频度在最坏情况下是（ D ）【南京理工 1998】 A．O（n） B．O（nlog2 n） C． O（n3） D． O（n2） 二、填空题
1① 以夹杂自然语言和程序语句的形式来描述解决问题的方法称为____伪码________。 2① 一个算法的效率可分为___时间______效率和__空间_______效率． 3② 有一个程序片断如下：
for（i=0;i 则其时间复杂度为：_O（n）________ 4② 有一个程序片断如下： for（i=0;i 则其时间复杂度为： O（nlog2 n） 三、 判断题 （ T ）1① 算法的优劣与算法描述语言无关，但与所用计算机有关。 （ T ）2① 健壮的算法不会因非法的输入数据而出现莫名其妙的状态。 （ F ）3① 程序一定是算法。 四、 简答题 1① 如何判断一个算法的好坏? 2③ 调用下列 C 函数 f（n） 回答下列问题 ： （1） 试指出 f（n）值的大小，并写出 f（n）值的推导过程； （2） 假定 n= 5，试指出 f（5）值的大小和执行 f（5）时的输出结果。 C 函数： int f（int n） { int i,j，k,sum= 0; for（i=l; i for（k=1;k （\）; } return （sum）; } 【华中理工 2000】 2.7 习题 2.7.1 知识点：线性表的逻辑结构 一、选择题 1① 线性表 L=（a1, a 2 ,…,a n ）,下列说法正确的是 （D ）。 A．每个元素都有一个直接前驱和一个直接后继。 B．线性表中至少要有一个元素。 C．表中诸元素的排列顺序必须是由小到大或由大到小。 D．除第一个和最后一个元素外,其余每个元素都有一个且仅有一个直接前驱和直接后继。 2① 在线性表的下列运算中，不改变数据元素之间结构关系的运算是（ D ）。 A．插入 B．删除 C．排序 D．定位 3① 线性表是具有n 个（C ）的有限序列（n>0）。【清华 1998】 A．表元素 B．字符 C．数据元素 D．数据项 E．信息项 二、判断题 （ T ）1① 线性表中的每个结点最多只有一个前驱和一个后继。 （ F ）2① 线性表中的每个结点都至少有一个前驱结点和后继结点。 （ F ）3① 线性表是 N 个数的有限序列。 （ F）4① 同一线性表的数据元素可以具有不同的特性。 （ T ）5① 线性表的长度 n 就是表中数据元素的个数，当 n=0 时，称为空表。 （ T ）6① 线性表是一个相当灵活的数据结构，它的长度可根据需要增长或缩短。 （ F ）7① 对线性表中的数据元素只能进行访问，不能进行插入和删除操作。 2.7.2 知识点：线性表的顺序存储结构 一、选择题 1① 在一个长度为 n 的顺序表中，在第 i 个元素（1 <= i <=n+1）之前插入一个新元素时 需向后移动（ B ）个元素． A．n-1 B．n-i+1 C．n-i-1 D．i 2① 若某线性表中最常用的操作是取第i个元素和找第i个元素的前趋元素，则采用（ D ）存储方式最节省时间。 A．单链表 B．双链表 C．单向循环 D．顺序表 3② 一个数组第一个元素的存储地址是 100，每个元素的长度为 2，则第 5 个元素的地址是（ B ） A．110 B．108 C．100 D．120 4① 下述哪一条是顺序存储结构的优点（ A ）。【北方交通 2001】 A．存储密度大 B．插入运算方便 C．删除运算方便 D．可方便地用于各种逻辑结构的存储表示 5③ 若长度为 n 的线性表采用顺序存储结构，在其第 i 个位置插入一个新元素的算法的时间复杂度为（ C ） （1<=i<=n+1）。【北京航空航天 1999】 A．O（0） B．O（1） C．O（n） D．O（n 2 ） 6③ 对于顺序存储的线性表，访问结点和增加、删除结点的时间复杂度为（ C ）。【青岛 2000】 A．O（n） O（n） B．O（n） O（1） C．O（1） O（n） D．O（1） O（1） 二、 填空题 1① 线性表的顺序存储的缺点是在任意位置上___插入_____数据与____删除_____数据费时间。 2① 设一线性表的顺序存储，总存储容量为 M，其元素存储位置的范围为__0~M-1__________。 3① 向一个长度为 n 的向量中删除第 i 个元素（1≤i≤n）时，需向前移动____n-i______个元素。 三、 简答题 1③ 已知线性表的存储结构为顺序表，阅读下列算法，并回答问题： void f30 （SeqList *L） { int i，j; for （i=j=0;i if（i!=j）L->data[j]=L->data[i]; j++； } L->length=j; } （1） （2） 设线性表 L=（21，-7，-8，19，0，-11，34，30，-10），写出执行 f30（&L）后L状态；(21,19,0,34,30) 简述算法 f30 的功能。删除顺序表中小于 0 的元素 四、编程题 1④ 已知顺序表 La 中数据元素按非递减有序排列。试写一个算法，将 x 插入到 La 的合适位置上，保持该表的 有序性。 2.7.3 知识点：线性表的链式存储结构 一、选择题 1① 链表是一种采用（ B ）存储结构存储的线性表。 A．顺序 B．链式 C．星式 D．网状 2① 链接存储的存储结构所占存储空间（ A ）。 A．分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针。 B．只有一部分，存放结点值。 C．只有一部分，存储表示结点间关系的指针。 D．分两部分，一部分存放结点值，另一部分存放结点所占单元数。 3① 线性表若采用链式存储结构时，要求内存中可用存储单元的地址（ D ）。 A．必须是连续的 B．部分地址必须是连续的 C．一定是不连续的 D．连续或不连续都可以 4① 线性表Ｌ在（ B ）情况下适用于使用链式结构实现。 A．需经常修改Ｌ中的结点值 B．需不断对Ｌ进行删除插入 C．Ｌ中含有大量的结点 D．Ｌ中结点结构复杂 5① 对单链表表示法,以下说法错误的是（C ）。 A．数据域用于存储线性表的一个数据元素。 B．指针域（或链域）用于存放一个指向本结点所含数据元素的直接后继所在结点的指针。 C．所有数据通过指针的链接而组织成单链表。 D．NULL 称为空指针，它不指向任何结点只起标志作用。 6① 以下说法正确的是（D ）。 A．顺序存储方式的优点是存储密度大且插入、删除运算效率高 B．链表的每个结点中都恰好包含一个指针 C．线性表的顺序存储结构优于链式存储结构 D．顺序存储结构属于静态结构而链式结构属于动态结构 7① 以下说法错误的是（D ）。 A．求表长、定位这两种运算在采用顺序存储结构时实现的效率不比采用链式存储结构时实现的效率低 B．顺序存储的线性表可以随机存取 C．由于顺序存储要求连续的存储区域,所以在存储管理上不够灵活 D．线性表的链式存储结构优于顺序存储结构 8① 不带头结点的单链表 head 为空的判定条件是（ A ）。 A．head= =NULL B．head->next= =NULL C．head->next= =head D．head!=NULL 9① 带头结点的单链表 head 为空的判定条件是（ B ）。 A．head= =NULL B．head->next= =NULL C．head->next= =head D．head!=NULL 10② 在头指针为 head 的非空单循环链表中，指针 p 指向尾结点，下列关系成立的是（ A ）。 A．p->next= =head B．p->next->next= =head C．p->next= =NULL D．p= =head 11② 在一个单链表中，已知 q 所指结点是 p 所指结点的前驱结点，若在 q 和 p 之间插入 s 结点，则执行语句 （ C ）。 A．s->next=p->next;p->next=s; B．p->next=s->next;s->next=p; C．q->next=s;s->next=p; D．p->next=s;s->next=q; 12② 在一个单链表中，若 p 所指结点不是最后结点，在 p 之后插入 s 结点，则应执行语句（ B ）。 A．s->next=p:p->next=s; B．s->next=p->next;p->next=s; C．s->next=p->next;p=s; D．p->next=s;s->next=p; 13② 在一个单链表中，若删除 p 所指结点的后续结点，则应执行语句（ A ）。 A．p->next=p->next->next; B．p=p->next;p->next=p->next->next; C．p->next=p->next; D．p=p->next->next; 14② 指针 p、q 和 r 依次指向某循环链表中三个相邻的结点，交换结点*q 和结点*r 在表中次序的程序段是（ A ）。 A．p->next=r； q->next=r->next； r->next=q； B．p->next=r； r->next=q； q->next=r->next； C．r->next=q； q->next=r->next； p->next=r； D．r->next=q； p->next=r； q->next=r->next； 15① 链表不具有的特点是（ B ） 【福州 1998】 A．插入、删除不需要移动元素 B．可随机访问任一元素 C．不必事先估计存储空间 D．所需空间与线性长度成正比 16① 下面的叙述不正确的是（BC ）【南京理工 1996】 A．线性表在链式存储时，查找第 i 个元素的时间同 i 的值成正比 B．线性表在链式存储时，查找第 i 个元素的时间同 i 的值无关 C．线性表在顺序存储时，查找第 i 个元素的时间同 i 的值成正比 D．线性表在顺序存储时，查找第 i 个元素的时间同 i 的值无关 17① 下面关于线性表的叙述中，错误的是哪一个？（ B ）【北方交通 2001】 A．线性表采用顺序存储，必须占用一片连续的存储单元。 B．线性表采用顺序存储，便于进行插入和删除操作。 C．线性表采用链接存储，不必占用一片连续的存储单元。 D．线性表采用链接存储，便于插入和删除操作。 18① 在一个以 h 为头的单循环链中，p 指针指向链尾的条件是（A）【南京理工 1998】 A．p->next=h B．p->next=NULL C．p->next->next=h D． p->data=-1 19② 若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（ A）存储方式最节省时间。【哈尔滨工业 2001】 A．顺序表 B．双链表 C．带头结点的双循环链表 D．单循环链表 20② 某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（ D）存储方式最节省运算时间。【南开 2000】 A．单链表 B．仅有头指针的单循环链表 C．双链表 D．仅有尾指针的单循环链表 21② 设一个链表最常用的操作是在末尾插入结点和删除尾结点，则选用（ D ）最节省时间。【合肥工业 2000】 A．单链表 B．单循环链表 C．带尾指针的单循环链表 D．带头结点的双循环链表 22② 线性表（a1, a 2 ,…,a n ）以链接方式存储时，访问第i 位置元素的时间复杂性为（C ） 【中山 1999】 A． O（i） B．O（1） C．O（n） D．O（i-1） 23③ 完成在双循环链表结点 p 之后插入 s 的操作是（D ）。【北方交通 1999】 A．p->next:=s ; s->priou:=p; p->next->priou:=s ; s->next:=p->next; B．p->next->priou:=s; p->next:=s; s->priou:=p; s->next:=p->next; C．s->priou:=p; s->next:=p->next; p->next:=s; p->next->priou:=s ; D．s->priou:=p; s->next:=p->next; p->next->priou:=s ; p->next:=s; 24③ 在双向循环链表中,在 p 指针所指向的结点前插入一个指针 q 所指向的新结点,其修改指针的操作是（ C ）。【北京邮电 1998】【青岛 2000】注:双向链表的结点结构为（llink,data,rlink）。 供选择的答案： A． p->llink=q； q->rlink=p； p->llink->rlink=q； q->llink=q； B． p->llink=q； p->llink->rlink=q ； q->rlink= p； q->llink=p->llink； C． q->rlink=p； q->llink=p->llink； p->llink->rlink=q; p->llink=q; D． q->llink=p->llink；q->rlink:=p； p->llink=q；p->llink=q； 25③ 在双向链表存储结构中，删除 p 所指的结点时需修改指针（ A）。【西安电子科技 1998】 A．p->prior->next=p->next p->next->prior=p->prior; B．p->prior =p-> prior-> prior p-> prior-> next=p; C．p-> prior-> prior:=p p-> next=p-> next -> next D．p-> next =（p-> prior） -> prior p-> prior=p-> next-> next 二、填空题 1① 线性表的链式存储是用___malloc______语句实现空间单元动态分配。 2① 单链表是___线性表_____的链接存储表示。 3① 头结点地址指针为 L 的循环单链表，空表的判别标志是___L->next==NULL___。 4① 在一个单链表中删除 p 所指结点时，应执行以下操作： q=p->next; p->data=p->next->data; p->next=q->next_________; free（q）; 5③ 下段程序的功能：有一头指针为 head 的链表,将 new 指针指向的节点插入到 data 域为 7 的节点的后边。 将程序补充完整。 P = head; while（P != NULL） { if （P ->data == 7） /*找到位置插入结点后跳出循环*/ { （1）_new->next=p->next_______________; （2） _p->next=new_______________; （3） ______break__________ ;} else （4）___p=p->next______________; /*指针后移*/ } if（P == NULL） printf（―\\n the position isn‘t exist! ‖）; 6③ 假设某个不设头指针的无头结点单向循环链表的长度大于 1，s 为指向链表中某个结点的指针。算法 f 30 的功能是，删除并返回链表中指针 s 所指结点的前驱。请在空缺处填入合适的内容，使其成为完整的算法。 typedef struct node { DataType data； struct node *next； }*LinkList； DataType f 30（LinkList s） { LinkList pre，p； DataType e； pre=s； p=s->next； while（（1）__p->next!=s____ ）{ pre=p; （2）p=p->next____________ ; } pre ->next=（3）__p->next____________ ; e=p->data; free（p）; return e; } 三、 判断题 （F ）1① 单链表从任何一个结点出发，都能访问到所有结点。 （ F ）2① 线性表的每个结点只能是一个简单类型，而链表的每个结点可以是一个复杂类型。 四、 简答题 1① 描述以下几个概念：顺序存储结构、链式存储结构、顺序表、有序表。 2② 描述以下三个概念的区别：头指针、头结点、首元结点。在单链表中设置头结点的作用是什么？ 3② 线性表有两种存储结构：一是顺序表，二是链表，试问： (1)如果有 n 个线性表同时共存，并且在处理过程中各表的长度会动态地发生变化，线性表的总数也会自动地 改变。在此情况下，应选用哪种存储结构？为什么？链表 (2)若线性表的总数基本稳定，且很少进行插入和删除，但要求以最快的速度存取线性表中的元素，那么应采 用哪种存取结构？为什么？顺序表 4③ 假设本测试中使用的链表如图 2.45 所示，结点定义如下： struct List { int data; struct List *next; }; typedef struct List Node; typedef Node *Link; Link P,Q,R,S,head; Link pointer,back,new; 对以下单链表分别执行下列程序段，要求分别画出结果图。 （1） Q=head->next->next; Q 指向 7 （2）R->data=P->data; 3 变 5 （3）R->data=P->next->data; 3 变 7 （4） S=P; while（S->next!=NULL） { S->data=S->data*2; S=S->next;} 4 10 14 6 8 （5） S=P; while（S!=NULL） { S->data=S->data*2; S=S->next;} 4 10 14 6 16 5③ 假设本测试中使用的链表如图 2.45 所示，结点定义如第 4 题所示。画出执行如下程序段后各指针及链表的示意图。 head=（Link）malloc（sizeof（Node））; head->data=0; head->next=NULL; P=head; for（i=1;i<4;i++） { new=（Link）malloc（sizeof（Node））; new->data=2*i; new->next=NULL; P->next=new; P=new; } 创建了一个链表，数据元素为 0,2,4,6，并且 p 和 new 都指向尾结点 6③ 有一链表如下图所示，阅读程序给出程序的输出结果。 图 2.46 6 题图 P = head; while（P != NULL） { printf（―\\n data=%d‖, P -> data）; P = P->next; if（ P != NULL） P = P ->next; } Data=1 Data=3 Data=5 五、编程题 1④ 一个单链表，其头指针为 head，编写一个函数计算数据域为 x 的节点个数。 2④ 已知单链表 La 中数据元素按非递减有序排列。按两种不同情况，分别写出算法，将元素 x 插入到 La 的合 适位置上，保持该表的有序性：（1）La 带头结点；（2）La 不带头结点。 3④ 试写一个算法，实现顺序表的就地逆置，即在原表的存储空间将线性表（a1,a 2 ,…,an?1,a n ）逆置为（a n ,a 。 n?1,…, a 2 ,a1） 4④ 设计一个算法，求 A 和 B 两个单链表表示的集合的交集、并集合差集。 3.7 习题 3.7.1 知识点：栈的基本概念 一、选择题 1① 下列哪种数据结构常用于函数调用（ A ）。 Ａ．栈 Ｂ．队列 Ｃ．链表 Ｄ．数组 2① 编译器中通常以哪种数据结构处理递归程序调用（ C ） Ａ．队列 Ｂ．数组 C．栈 D．记录 3① 下列哪些数据结构可用来实现栈（ D ）。 （1）链表 （2）数组 （3）树 （4）图 Ａ．（2），（3） Ｂ．（2），（4） C．（1），（4） D．（1），（2） 4② 元素的入栈序列是 a,b,c,d，则栈的不可能的输出序列是（ C ）。 A．dcba B．abcd C．dcab D．cbad 5② 已知栈的最大容量为 4。若进栈序列为 1，2，3，4，5，6，且进栈和出栈可以穿插进行, 则可能出现的出栈序列为（ C ）。 A．5，4，3，2，1，6 B．2，3，5，6，1，4 C．3，2，5，4，1，6 D．1，4，6，5，2，3 6② 若以 S 和 X 分别表示进栈和退栈操作，则对初始状态为空的栈可以进行的栈操作系列是（ D ）。 A．SXSSXXXX B．SXXSXSSX C．SXSXXSSX D．SSSXXSXX 7① 对于栈操作数据的原则是（ B ）。【青岛 2001】 A． 先进先出 B．后进先出 C．后进后出 D．不分顺序 8① 栈在（ D ）中应用。【中山 1998】 A．递归调用 B．子程序调用 C．表达式求值 D．A，Ｂ，Ｃ 9② 一个栈的输入序列为 123…n，若输出序列的第一个元素是 n，输出第 i（1<=i<=n）个元素是（B ）。【中山 1999】 A．不确定 B．n-i+1 C．i D．n-i 10② 若一个栈的输入序列为 1,2,3,…,n，输出序列的第一个元素是 i，则第 j 个输出元素是（D ）。【武汉 2000】 A．i-j-1 B．i-j C．j-i+1 D．不确定的 11② 有六个元素 6，5，4，3，2，1 的顺序进栈，问下列哪一个不是合法的出栈序列？（ C ）【北方交通 2001】 A．5 4 3 6 1 2 B．4 5 3 1 62 C．3 4 6 5 2 1 D．2 3 4 1 5 6 12② 输入序列为 ABC，可以变为 CBA 时，经过的栈操作为（B ）【中山 1999】 A．push,pop,push,pop,push,pop B．push,push,push,pop,pop,pop C．push,push,pop,pop,push,pop D．push,pop,push,push,pop,pop 13② 设计一个判别表达式中左，右括号是否配对出现的算法，采用（ D ）数据结构最佳。【西安电子科技 1996】 A．线性表的顺序存储结构 B．队列 C．线性表的链式存储结构 D．栈 二、填空题 1① 栈是一种特殊的线性表，允许插入和删除运算的一端称为 栈顶 ，不允许插入和删除运算的一端称为 栈底 。 2① 对于顺序存储的栈，因为栈的空间是有限的，在进行 入栈 运算时，可能发生栈的上溢，在进行 出栈 运算时，可能发生栈的下溢。 3① 表达式求值是 栈 应用的一个典型例子。 4① 栈是__一种特殊_____的线性表，其运算遵循____先进后出_____________的原则。【北京科技 1997】 5② 设有一个空栈， 栈顶指针为 1000H（ 十六进制） ， 现有输入序列为 1 ， 2 ，3 ， 4 ， 5 ， 经过 PUSH,PUSH,POP,PUSH,POP,PUSH,PUSH 之后，输出序列是 2,3，_______，而栈顶指针值是 _1000C_____H。设栈为顺序栈，每个元素占 4 个字节。【西安电子科技 1998】 6② 用 S 表示入栈操作，X 表示出栈操作，若元素入栈的顺序为 1234，为了得到 1342 出栈顺序，相应的 S 和 X 的操作串为_________sxssxsxx__________。【西南交通 2000】 三、判断题 （ F ）1① 栈具有先进先出的特性。 （ T ）2① 栈用于实现子程序调用。 （ F ）3① 栈和链表是两种不同的数据结构。 （ T ）4① 栈顶的位置是随着操作而变化的。 （ T ）5① 栈和队列逻辑上都是线性表。 （ T ）6① 栈是实现过程和函数等子程序所必需的结构。【合肥工业 2000】 （ F ）7② 即使对不含相同元素的同一输入序列进行两组不同的合法的入栈和出栈组合操作，所得的输出序列也 一定相同。【北京邮电 1999】 （ T ）8② 若输入序列为1,2,3,4,5,6,则通过一个栈可以输出序列3,2,5,6,4,1。【上海海运1995】 （ F ）9② 若输入序列为1，2，3，4，5，6，则通过一个栈可以输出序列1，5，4，6，2，3。【上海海运 1999】 四、简答题 1① 什么是栈？试举两个应用实例。 2① 简述栈和线性表的差别。 3③ 计算表达式 6*3/2-5*1，要求绘出堆栈的处理过程。 5② 有 5 个元素，其入栈次序为：A，B，C，D，E，在各种可能的出栈次序中，以元素 C，D 最先出栈 （即 C 第一个且 D 第二个出栈）的次序有哪几个？【西南交通 2000】 3.7.2 知识点：栈的存储 一、选择题 1① 如果以链表作为栈的存储结构，则入栈操作时（ B ）。 A．必须判别栈是否满 B．对栈不作任何判别 C．必须判别栈是否空 D．判别栈元素的类型 2① 上溢现象通常出现在（ A ）。 A．顺序栈的入栈操作过程中 B．顺序栈的出栈操作过程中 C．链栈的入栈操作过程中 D．链栈的出栈操作过程中 3① 判定一个栈 ST（最多元素为 m0）为空的条件是（ B ） Ａ．ST->top！=0 Ｂ．ST->top= =0 Ｃ．ST->top！=m0 Ｄ．ST->top= =m0 4① 链表仿真堆栈时，栈空的条件是（B ）。 A．top A．top 6② 在用链表仿真堆栈时（假设 stack 为栈顶指针），将 new 指针指向的节点执行入栈操作应执行（ B ） Ａ．new->next=stack->next； stack=new； Ｂ．new->next=stack； stack=new； Ｃ．new->next=stack；stack=new->next； Ｄ．stack=new；stack->next=new->next； 7② 若一个栈以向量 V[1．．n]存储，初始栈顶指针 top 为 n+1，则下面 x 进栈的正确操作是（ C ）。【南京理工 1998】 A．top=top+1; V [top]=x B．V [top] =x; top=top+1 C．top=top-1; V [top]=x D．V [top]=x; top=top-1 8② 执行完下列语句段后，i 值为：（ B）。【浙江 2000】 int f（int x） { return （（x>0） ? x* f（x-1）:2）;} int i ; i =f（f（1））; A． 2 B． 4 C． 8 D． 无限递归 二、 填空题 1② 以下语句是堆栈的入栈操作，用全局数组 stack 仿真堆栈，数组类型是 int，大小是 MaxSize，栈顶指针是 top，初始化等于－1。 01 void push（int value） 02 { 03 if（top>MaxSize-1） 04 return –1; 05 else 06 { 07 top++; 08 stack[top]=value; 09 } 10 } 指出有错误的语句：___3_____ 写出改正后的语句：_____ top==MaxSize-1_______ 2② 以下语句是数据从堆栈中取出操作,top 为栈顶指针,stack 为堆栈数组。 01 int pop（） 02 { 03 int temp; 04 if（top＝＝0） 05 return –1; 06 else 07 { 08 temp = stack[top]; 09 top ――; 10 } 11 return temp; 12 } 指出有错误的语句：_______________________ 写出改正后的语句：_______8,9 互换________________ 三、 编程题 1④ 假设一个算术表达式中可以包含圆括号“（”和“）”，编写判别给定表达式中所含括号是否正确配对出现的算法。 2④ 编写斐波那契（Fibonacci） 数列的递归算法和迭代算法。 F0 = 0, F1 =1, F Fn=? n 1 +?F nn 2( >= 2) 3.7.3 知识点：队列的基本概念及其应用 一、选择题 1① 下列哪种数据结构常用于系统程序的作业调度（ B ） A．栈 B．队列 C．链表 D．数组 2① 在解决计算机主机与打印机之间速度不匹配问题时通常设置一个打印数据缓冲区, 主机将要输出的数据依次写入该缓冲区,而打印机则从该缓冲区中取出数据打印．该缓冲区应该是一个（ B ）结构． A．堆栈 B．队列 C．数组 D．线性表 3② 设栈 S 和队列 Q 的初始状态为空，元素 e1、e2、e3、e4、e5、e6 依次通过栈 S，一个元素出栈后即进入队列 Q，若 6 个元素出队的序列是 e2、e4、e3、e6、e5、e1，则栈 S 的容量至少应该是（ C ） A．6 B．4 C．3 D．2 4① 栈和队列的共同点是（ C ）。【燕山 2001 一、1（2 分）】 A． 都是先进先出 B．都是先进后出 D． 没有共同点 C． 只允许在端点处插入和删除元素 二、填空题 1① 栈和队列都是线性结构，对于栈只能在____栈顶______ 位置插入和删除元素，对于队列只能在______队尾________位置插入元素和_____队头_________位置删除元素。 2② 队列的队尾位置通常是随着_____入队_________操作而变化的。 3① 队列的特点是_______先进先出_________________。【北京理工 2000】 4② 循环队列的引入，目的是为了克服________假溢出________________。【厦门 2001】 三、判断题 （ T ）1① 队列中所有的插入操作都发生在表的一端，删除则发生在表的另一端。 （ F ）2① 队列为先进后出的结构。 （ F ）3① 队列必须用数组来表示。 （ T ）4① 队列用于操作系统中的作业调度。 （ T ）5① 栈和队列逻辑上都是线性表。 （ T ）6① 栈和队列是在程序中常用的两种数据结构。 （ T ）7① 栈与队列是一种特殊操作的线性表。【青岛 2001】 （ T ）8① 栈和队列都是限制存取点的线性结构。【中科院软件所 1999】 （ F）9① 队列是一种插入与删除操作分别在表的两端进行的线性表，是一种先进后出型结构。【上海海运 1998】 （ F ）10① 通常使用队列来处理函数或过程的调用。【南京航空航天 1997】 （ F ）11① 队列逻辑上是一个下端和上端既能增加又能减少的线性表。【上海交通 1998】 （ T ）12① 栈和队列都是线性表，只是在插入和删除时受到了一些限制。【北京邮电 2002】 四、简答题 1① 什么是队列？试举两个应用实例。 2① 说明线性表、栈和队列的异同点。 3① 顺序队的“假溢出”是怎样产生的？什么是循环队列？如何知道循环队列是空还是满？ 五、编程题 1④ 假设称正读和反读都相同的字符序列为“回文”，例如?abba‘和?abcba‘是回文，?abcde‘ 和?ababab‘则不是回文。试写一个算法判别读入的一个以?@‘为结束符的字符序列是否是“回文”。 3.7.4 知识点：队列的存储 一、选择题 1① 循环队列用数组 A[maxsize] 表示，下面哪个选项表示该循环队列队满（ B ） Ａ．rear= =maxsize-1 B． front= =（rear+1）%maxsize C． rear-front= =maxsize D． rear-front= =maxsize-1 2① 在用数组 queue[maxsize]仿真队列时（temp 为 int 型变量），假设队列中至少有一个元素，出队列操作应执行以下（ D ） A．temp=queue[rear]; rear--; B． rear++; temp=queue[rear]; C．temp=queue[front]; front--; D． front++; temp=queue[front]; 3① 数组Ｑ［ｎ］用来表示一个循环队列，ｆ为当前队列头元素的前一位置，ｒ为队尾元素的位置，假定队列中元素的个数小于ｎ，计算队列中元素的公式为（ D ） Ａ．r－f; Ｂ．（n＋f－r）% n; Ｃ．n＋r－f Ｄ．（n＋r－f）% n 4② 判断一个队列 QU（最多元素为 m0）为空的条件是（ C ）。 A．rear- front= =m0 C．front= = rear B．rear- front-1= =m0 D．front= = rear+1 5② 一个队列（数组仿真，最多元素为 MaxSize）下列哪个选项表示了队列空间全部被利用？（ A ） A．rear – front = = MaxSize B．rear – front = = MaxSize –1 C．rear = = front D．rear + 1 = = front 6② 判定一个循环队列（数组仿真，最多元素为 MaxSize）为空的条件是？（ A ） A．front = = rear B．front != rear C．front = = （rear + 1）%MaxSize D．front != （rear + 1）%MaxSize 7① 用单链表表示的链式队列的队头在链表的（ A ）位置。【清华 1998】 A．链头 B．链尾 C．链中 D．任何 8② 用不带头结点的单链表存储队列时,其队头指针指向队头结点,其队尾指针指向队尾结点，则在进行删除操作时（ D ）。【北京理工 2001】 A．仅修改队头指针 B．仅修改队尾指针 C． 队头、队尾指针都要修改 D．队头,队尾指针都可能要修改 9② 假设以数组 A[m]存放循环队列的元素,其头尾指针分别为 front 和 rear，则当前队列中的元素个数为（ A ）。【北京工商 2001】 A．（rear-front+m）%m B．rear-front+1 C．（front-rear+m）%m D．（rear-front）%m 10② 循环队列存储在数组 A[0．．m]中，则入队时的操作为（ D ）。【中山 1999】 A． rear=rear+1 B．rear=（rear+1） mod （m-1） C． rear=（rear+1） mod m D．rear=（rear+1）mod（m+1） 11② 若用一个大小为 6 的数组来实现循环队列，且当前 rear 和 front 的值分别为 0 和3， 当从队列中删除一个元素，再加入两个元素后，rear 和 front 的值分别为多少？（ B ）【浙江 1999】 A． 1 和 5 B． 2 和 4 C． 4 和 2 D． 5 和 1 12② 用链接方式存储的队列，在进行插入运算时（ B ）。【北方交通 2001】 A．仅修改头指针 B．仅修改尾指针 C．头、尾指针都要修改 D．头、尾指针可能都要修改 二、填空题 1① 栈、队列的建立可使用两种结构：______顺序________结构和____链式______结构。 2② 假设为循环队列分配的向量空间为 Q[20]，若队列的长度和队头指针值分别为 13 和 17，则当前尾指针的值为__10____________。 3③ 以下语句是环状队列的出队操作，用数组 queue 仿真环状队列，数组类型是 int，大小是 MaxSize，队尾指针是 rear，队头指针是 front。 01 int delqueue（） 02 { 03 int temp; 04 if（front==rear） 05 return –1; 06 else 07 { 08 front++; 09 temp=queue[front]; 10 queue[front]=0; 11 return temp; 12 } 13 } 指出有错误的语句：__________8_______________ 写出改正后的语句：________front=(front+1)%MaxSize_______________ 4② 区分循环队列的满与空，只有两种方法，它们是____设标志____和______少用一片空间_______。【北京邮电 2001】 5② 设循环队列存放在向量 sq．data[0..M]中，则队头指针 sq.front 在循环意义下的出队操作可表示为__sq.front=(sq.front+1)%(M+1)_____，若用牺牲一个单元的办法来区分队满和队空（设队尾指针 sq.rear），则队满的条件为_sq.front==(sq.rear+1)%(M+1)___。【长沙铁道 1997】 三、判断题 （ T ）1① 栈和队列的存储方式既可是顺序方式，也可是链接方式。 （ T ）2① 单链表形式的队列，头指针 F 指向队列的第一个结点，尾指针 R 指向队列的最后一个结点。 （ F ）3① 循环队列通常用指针来实现队列的头尾相接。【南京航空航天 1996】 （ T ）4① 循环队列也存在空间溢出问题。【青岛 2002】 四、简答题 1② 设循环队列的容量为 40（序号从 0 到 39），现经过一系列的入队和出队运算后，有（1） front=11，rear=19; （2） front=19，rear=11；问在这两种情况下，循环队列中各有元素多少个？8,32 2② 假设 CQ[0,…,10]是一个环状队列，初始状态 front=rear=1, 画出做完下列操作后队列的头尾指针的状态变化情况，若不能入队，请指出其元素，并说明理由。 （1）d, e, b, g, h 入队； （2）d, e 出队； （3）I, j, k, l, m 入队；（4）b 出队； （5）n, o, p, q, r 入队。 3③ 阅读下列算法，并回答问题（注：lnitQueue、EnQueue、DeQueue 和 QueueEmpty 分别是队列初始化、入列、出队和判队空的操作）。 void f31 （Queue*Q, Queue*Q1, Queue*Q2） { int e; lnitQueue （Q1）; lnitQueue （Q2）; while （!QueueEmpty （Q）） { e=DeQueue （Q）; if （e>=0） EnQueue （Q1,e）; else EnQueue （Q2,e） } } （1）Q、Q1 和 Q2 都是队列结构，设队列 Q=（1，0，-5，2，-4，-6，9），其中 1 为队头元素，写出执行 f31 （&Q,&Q1,&Q2）之后队列 Q、Q1 和 Q2 的状态； Q 为空 Q1=(1,0,2,9)Q2=(-5,-4,-6) （2）简述算法 f31 的功能。 4③ 阅读如下程序，并回答下列问题（注：lnitQueue、EnQueue、DeQueue 和 QueueEmpty 分别是队列初始化、入列、出队和判队空的操作）。 void f 31（Queue *Q）{ DataType e; if （!QueueEmpty（Q））{ e=DeQueue（Q）; f 31（Q）; EnQueue（Q,e）; } } （1） 设队列 Q=（1，3，5，2，4，6）。写出执行算法 f 31 后的队列 Q; Q=(6,4,3,5,3,1) （2） 简述算法 f 31 的功能。将队列反转 5③阅读如下程序，它的功能是清空带头结点的链队列Q。请在空缺处填入合适的内容，使成为一个完整的算法。 typedef struct node{ DataType data； struct node *next； }QueueNode； typedef struct { QueueNode *front；／／队头指针 QueueNode *rear；／／队尾指针 }LinkQueue； void f 31（LinkQueue *Q） { QueueNode *p，*s； p= （1） ； while（p！=NULL） { s=p； p=p->next; free （s）; （2） =NULL; Q->rear= （3） ； } （1） ______p=Q->front->next____________________ （2） ______Q->front->next=NULL________________ （3） ______Q->rear=Q->front______________ _____ 五、编程题 1④ 假设将循环队列定义为：以变量 rear 和 length 分别指示循环队列中队尾元素的位置和内含元素的个数。试给 出此循环队列的队满条件，并写出相应的入队列和出队列的算法。 2④ 假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾元素结点（注意不设头指针），试编写相应 的队列初始化、入队列和出队列的算法。 4.9 习题 4.9.1 知识点：树和二叉树的基本概念 一、选择题 1② 在一棵具有 n 个结点的完全二叉树中，分支结点的最大编号为（ D ）。假定树根结点的编号为0。 A．（n－1）/2 B．n/2 C．n/2+1 D．n/2－1 2② 在一棵完全二叉树中，若编号为 i 的结点存在左孩子，则左子女结点的编号为（C）。假定根结点的编号为 0。 A．2i B．2i－1 C．2i+1 D．2i+2 3② 在一棵具有 35 个结点的完全二叉树中，该树的高度为（ A ）。假定空树的高度为－1。 A．5 B．6 C．7 D．8 4② 树中所有结点的度等于所有结点数加（ C ）。 A．0 B．1 C．－1 D．2 5② 在一棵具有 n 个结点的二叉树的第 i 层上（假定根结点为第 0 层，i 大于等于 0 而小于等于树的高度），最多具有（A ）个结点。 A．2i C．2i?1 B．2i+1 D．2n 6② 在一棵完全二叉树中，假定根结点的编号为 0，则对于编号为I（I＞0）的结点，其双亲结点的编号为（ B ）。 A．（I+1）/2 C．I/2 B．（I－1）/2 D．I/2－1 7③ 在一棵具有 n 个结点的二叉树中，所有结点的空子树个数等于（ C ）。 A．n B．n－1 C．n+1 D．2*n 8③ 在一棵高度为 h（假定根结点的层号为 0）的完全二叉树中，所含结点个数不小于（ D ）。 A．2h?1 C．2 1h ? B．2h+1 D．2h 9② 如下的 4 棵二叉树中，（ D ）不是完全二叉树。 A B C D 图 4.47 10 题图 10② 深度为 5 的二叉树至多有（ C ）个节点。 A．16 C．31 B．32 D．10 11③ 对一棵满二叉树而言，m 个树叶，n 个节点，深度为 h，则下列哪个等式正确（ D ）。 A．n=h+m B．h+m=2n D．n= 2h －1 C．m=n－1 12② 有一棵非空的二叉树，共有n 个节点，其中分支度为 2 的结点有 w 个，则分支度为 1 的结点个数为（ B）。 A．n－2w B．n－2w－1 D．n－2w+1 C．n－w+1 13② 具有 n（n>0）个结点的完全二叉树的深度为（C ）。 A．log2 n +1 B． log2 n C． log2 n D．（log2 n）+1 14② 设树T 的度为4，其中度为1，2，3 和4 的结点个数分别为4，2，1，1 则T 中的叶子数为（ D ）【南京理工 2000】 A．5 B．6 C．7 D．8 15② 在下述结论中，正确的是（ D ）。【南京理工 1999】 （1）只有一个结点的二叉树的度为0; （2）二叉树的度为2； （3）二叉树的左右子树可任意交换; （4）深度为K 的完全二叉树的结点个数小于或等于深度相同的满二叉树。 A．（1）（2）（3） B．（2）（3）（4） C．（2）（4） D．（1）（4） 16② 若一棵二叉树具有10 个度为2 的结点，5 个度为1 的结点，则度为0 的结点个数是（B ）【北京工商 2001】 A．9 B．11 C．15 D．不确定 17② 一棵完全二叉树上有1001 个结点，其中叶子结点的个数是（E ）。【西安交通 1996】 A． 250 B． 500 C．254 D．505 E．以上答案都不对 二、填空题 1② 由 3 个结点所构成的二叉树有___5___种形态；16 个结点可构造出________种不同形态的二叉树。 2② 将含有 82 个结点的完全二叉树从根结点开始顺序编号，根结点为第 0 号，其他结点自上向下，同一层自 左向右连续编号。则第 40 号结点的双亲结点的编号为___14_____。 3① 在一棵树中，_根_____结点没有前驱结点。 4② 假定一棵二叉树的结点个数为 18，则它的最小高度为__4____。假定根结点的高度为 0。 5② 假定一棵三叉树（即度为 3 的树）的结点个数为 50，则它的最小高度为__4_。假定根结点的高度为 0。 6② 一棵高度为 5 的完全二叉树中，最多包含有__63____个结点。假定根结点的高度为0。 7② 在一棵三叉树中，度为 3 的结点数有 2 个，度为 2 的结点数有 1 个，度为 1 的结点数为 2 个, 那么度为 0 的结点数有___6___个。 8② 在一棵高度为 3 的四叉树中，最多含有__21____结点。 9② 一棵深度为 6 的满二叉树有____31__个分支结点和__32____个叶子。 10② 一棵具有 257 个结点的完全二叉树，它的深度为___9___。 11② 设一棵完全二叉树具有 1000 个结点，则此完全二叉树有__500____个叶子结点，有___4999___个度为 2 的结点，有__1____个结点只有非空左子树，有___0___个结点只有非空右子树。 12② 对于一棵具有 n 个结点的树，该树中所有结点的度数之和为__n-1_______。 13② 一棵具有 n 个结点的二叉树，若它有 n0 个叶子结点，则该二叉树上度为 1 的结点 n1=_n-2n0+1_____。 14② 如果结点 A 有 3 兄弟，而且 B 是 A 的双亲，则 B 的度是___4___。 15② 对于一棵完全二叉树，设一个结点的编号为 i，若它的左孩子结点存在，则其编号为__2*i______；若右 孩子结点存在，则其编号为_2*i+1_______；而双亲结点的编号为____i/2_____。 16② 深度为k 的完全二叉树至少有 2k-1 个结点，至多有 2k-1 个结点。 【厦门 2001】 【南京理工 1999】 17② 已知一棵度为3 的树有2个度为1的结点,3个度为2的结点，4个度为3的结点，则该树有____12_____个叶子结点。【厦门 2000】 18② 一棵有n 个结点的满二叉树有___0______个度为1 的结点、有__(n+1)/2_______ 个分支 （非终端）结点和__(n-1)/2_______个叶子，该满二叉树的深度为___ log2 n ______。【华中理工 2000】 +1 三、判断题 （ T ）1① 二叉树中每个结点的两棵子树是有序的。 （ F ）2① 二叉树中每个结点有两棵非空子树或有两棵空子树。 （ F ）3② 对于一棵非空二叉树，它的根结点作为第一层，则它的第 i 层上最多能有2i－1 个结点。 （ T ）4② 具有 12 个结点的完全二叉树有 5 个度为 2 的结点。 （ T ）5① 完全二叉树的某结点若无左孩子，则它必是叶结点。 （ F ）6② 二叉树中不存在度大于 2 的结点，当某个结点只有一棵子树时无所谓左、右子树之分。 （ T ）7② 当 k≥1时，高度为 k 的二叉树至多有2 1k ? 个结点。 （ F ）8② 一棵含有 n 个结点的完全二叉树，它的高度是log2 n +1。 （ F ）9① 二叉树就是结点度为2的树。【长沙铁道1997】【中科院软件所1997】 （ F ）10② 完全二叉树一定存在度为1 的结点。【青岛 2002】 （ T ）11① 树形结构中元素之间存在一个对多个的关系。【燕山 1998】 （ F ）12① 树与二叉树是两种不同的树型结构。【东南 2001】 四、简答题 1③ 已知一棵度为 m 的树中有N1个度为 1 的结点， N2 个度为 2 的结点，…， Nm 个度为 m 的结点。 试问该树中有多少个叶子结点? 2③ 树和二叉树之间有什么样的区别与联系？【西北工业 1998】【厦门 2000】【燕山 2001】 4.9.2 知识点：二叉树和树的存储结构 一、选择题 1① 在一棵树的左子女－右兄弟表示法中，一个结点的右孩子是该结点的（ A ）结点。 A．兄弟 B．子女 C．祖先 D．子孙 2② 在一棵树的静态双亲表示中，每个存储结点包含（ B ）个域。 A．1 B．2 C．3 D．4 3② 在一棵二叉树的二叉链表中，空指针域数等于非空指针域数加（ A ）。 A．2 B．1 C．0 D．-1 4② 二叉树是非线性数据结构，所以（ C ）。 A．它不能用顺序存储结构存储 B．它不能用链式存储结构存储 C．顺序存储结构和链式存储结构都能存储 D．顺序存储结构和链式存储结构都不能使用 5② 利用二叉链表存储树，则根结点的右指针是（ B ）。【青岛 2001】 A．指向最左孩子 B．指向最右孩子 C．空 D．非空 6② 在下列存储形式中，哪一个不是树的存储形式？（ D ）【北方交通 2001】 A．双亲表示法 B．孩子链表表示法 C．孩子兄弟表示法 D．顺序存储表示法 7② 一棵有n 个结点的二叉树，按层次从上到下，同一层从左到右顺序存储在一维数组 A[1..n]中，则二叉树中第i 个结点（i 从1 开始用上述方法编号）的右孩子在数组A 中的位置是（B ）【南京理工 2000】 A． A[2i]（2i<=n） B． A[2i+1]（2i+1<=n） C． A[i－2] D． 条件不充分，无法确定 二、 填空题 1① 二叉树通常有___顺序______存储结构和_____链式_______存储结构。 三、 判断题 （ T ）1② 若二叉树用二叉链表作存贮结构，则在 n 个结点的二叉树链表中只有 n－1 个非空指针域。 （ T ）2① 树适合于表示层次关系。 （ T ） 3② 完全二叉树的存储结构通常采用顺序存储结构。【南京航空航天1996】 四、简答题 1② 描述二叉树的顺序存储。 2② 描述二叉树的链式存储。 4.9.3 知识点：树、森林向二叉树的转换 一、 选择题 1② 把一棵树转换为二叉树后，这棵二叉树的形态是（ A ）。 A．唯一的 B．有多种 D．有多种，但根结点都没有右孩子 C．有多种，但根结点都没有左孩子 2② 如下图所示的二叉树 T2 是由森林 T1 转换而来的二叉树，那么森林 T1 有（ C ）个叶子结点。 A EB F HC D G J I 图 4.48 2 题图 A．4 B．5 C．6 D．7 二、 填空题 1② 设森林 F 中有 4 棵树，第 1、2、3、4 棵树的结点个数分别为 n1、n2、n3、n4，当把森林 F 转换成一棵二 叉树后，其根结点的左子树中有____n1-1____________个结点。 2② 将森林或树转换成二叉树时，所有的水平线段以左边结点为轴心_顺时针__旋转45o。 3② 利用树的孩子兄弟表示法存储，可以将一棵树转换为_二叉树________。【重庆 2000】三、判断题 （ T ）1② 将森林或树转换成二叉树时，在所有相邻兄弟结点（森林中每棵树的根结点可以看成是兄弟结点）之间加一水平连线。 （ T ）2② 将森林或树转换成二叉树时，对每个非叶子结点 k，除了其最左边的孩子结点外，删去 k 与其他孩子结点的连线。 （ F ）3② 将一棵树转换成二叉树后，根结点没有左子树。 （ F ） 4② 必须把一般树转换成二叉树后才能进行存储。【南京航空航天 1997】 四、简答题 1③ 把如图所示的树转化成二叉树。 A D B C 2③ 如何把森林转换成二叉树。 K E L F G M H I J 4.49 1 题图 4.9.4 知识点：树与二叉树的遍历图 一、选择题 1② 已知某二叉树的后序遍历序列是 dabec，中序遍历序列是 debac，则它的前序遍历序列是（D ）。 A．acbed B．decab C．deabc D．cedba 2② 在一棵非空的二叉树的中序遍历序列中，根节点的右边（ B ）。 A．只有左子树上的所有节点 B．只有右子树上的所有节点 C．只有左子树上的部分节点 D．只有右子树上的部分节点 3② 下列二叉树的后序遍历序列是（ C ）。 a b d g e h x c f y D．dgbaehcxfy 图 4.50 3 题图 A．abdecfghxy B．abdgcehfxy C．gdbhexyfca 4② 任何一棵二叉树的叶节点在前序、中序和后序遍历序列中的相对次序（ A ）。 A．不发生改变 B．发生改变 C．不能确定 D．以上都不对 5② 线索二叉树是一种（ C ）结构。 A．逻辑 B．逻辑和存储 C．物理 D．线性 6② 将下图的二叉树按中序线索化，结点 X 的右指针和 Y 的左指针分别指向（C ） A．A，D B．B，C C．D，A A B C Y X D E D．C，A 图 4.51 6 题图 7② 引入线索二叉树的目的是（ A ）。【南京理工 1998】 A．加快查找结点的前驱或后继结点的速度 B．为了能在二叉树中方便插入和删除 C．为了能方便找到双亲 D．使二叉树的遍历结果唯一 8② 树的后根遍历序列等同于该树对应的二叉树的（ B ）。 【北京理工 2001】 A. 先序序列 B. 中序序列 C. 后序序列 9② 一棵二叉树的前序遍历序列为ABCDEFG，它的中序遍历序列可能是（ B ）【北京工业 2001】 A．CABDEFG B．ABCDEFG C．DACEFBG D．ADCFEG 10② 已知一棵二叉树的前序遍历结果为ABCDEF，中序遍历结果为CBAEDF，则后序遍历的结果为（A ）。 【浙江 1999】 A．CBEFDA B． FEDCBA C． CBEDFA D．不定 11② 某二叉树中序序列为A，B，C，D，E，F，G，后序序列为B，D，C，A，F，G，E 则前序序列是：（ B ）【南京理工 2000】 A．E，G，F，A，C，D，B B．E，A，C，B，D，G，F C．E，A，G，C，F，B，D D．上面的都不对 12② 对于前序遍历与中序遍历结果相同的二叉树为（ BF ）;对于前序遍历和后序遍历结果相同的二叉树为（ B ）。【中科院计算所 1999】 A．一般二叉树 B．只有根结点的二叉树 C．根结点无左孩子的二叉树 D．根结点无右孩子的二叉树 E．所有结点只有左子数的二叉树 F．所有结点只有右子树的二叉树二、填空题 1② 在二叉树的一维数组存储方式中，父节点和右孩子的索引值之间满足的关系是_2倍加 1_______。 2② 在中序线索化二叉树时，采用__中序______遍历方法最合适。 3② 线索二叉树中的左线索指向其__前驱______，右线索指向其__后继______。【哈尔滨工业 2000】 三、判断题 （ T ）1② 在一棵二叉树中，假定每个结点只有左子女，没有右子女，对它分别进行中序遍历和后序遍历，则具有相同的遍历结果。 （ F ） 2② 对于一棵具有 n 个结点，其高度为 h 的二叉树，进行任一种次序遍历的时间复杂度为 O（h）。 （ T ）3② 线索化二叉树中的每个结点通常包含有 5 个数据成员。 （ F ）4② 在一棵具有 n 个结点的线索化二叉树中，每个结点的指针域可能指向子女结点，也可能作为线索，使之指向某一种遍历次序的前驱或后继结点，所有结点中作为线索使用的指针域共有 n 个。 （ T ）5② 存在这样的二叉树，对它采用任何次序的遍历，结果相同。 （ F ）6② 若有一个叶子结点是二叉树中某个子树的前序遍历结果序列的最后一个结点，则它一定是该子树中序遍历结果序列的最后一个结点。 （ F ）7② 二叉树的前序遍历并不能唯一确定这棵树，但是，如果我们还知道该树的根结点是那一个，则可以确定这棵二叉树。【上海海运 1995】 （ T ）8② 用树的前序遍历和中序遍历可以导出树的后序遍历。【北京邮电 1999】 （ T ）9② 一个树的叶结点，在前序遍历和后序遍历下，皆以相同的相对位置出现。【上海海运】 （ F ）10② 由一棵二叉树的前序序列和后序序列可以唯一确定它。【中科院软件所 1997】 四、简答题 1② 已知二叉树中的结点类型用 BinTreeNode 表示，被定义为: struct BinTreeNode { ElemType data; BinTreeNode *leftChild， *rightChild; }; 其中 data 为结点值域，leftChild 和 rightChild 分别为指向左、右子女结点的指针域。根据下面函数的定义指出函数的功能。算法中参数 BT 指向一棵二叉树的根结点。 void preserve （ BinTreeNode* BT， ElemType a[ ]， int n ） { static int I = 0; if （ BT != NULL ） { preserve （ BT－>leftChild， a， n ）; a[I++] = BT－>data; preserve （ BT－>rightChild， a， n ）; } } 请描述算法功能。中序遍历树 BT，将遍历的结点放在数组 a 中 2③ 已知一棵二叉树的静态数组表示（即顺序存储表示）如下，其中 0 表示空指针，请分别写出该二叉树的前序、中序、后序遍历的序列。 0 20 1 8 2 3 4 5 6 7 0 8 0 9 10 11 12 35 46 5 15 30 0 10 18 0 3③（1）试找出满足下列条件的二叉树 a. 先序序列与后序序列相同 b. 中序序列与后序序列相同 c. 先序序列与中序序列相同 d. 中序序列与层次遍历序列相同 （2）已知一棵二叉树的中序序列和后序序列分别为DBEAFIHCG 和DEBHIFGCA，画出这棵二叉树。【东北 1999】 4③ 设一棵二叉树的先序遍历序列为： A B D F C E G H ，中序遍历序列为： B F D A G E H C。 （1） 画出这棵二叉树。 （2） 画出这棵二叉树的后序线索树。 （3） 将这棵二叉树转换成对应的树（或森林）。【南京航空航天 1997】 五、算法题 1④ 假设二叉树采用二叉链表存储结构存储，设计一个算法，求先序遍历序列中第 k（1≥k≥二叉树中结点个数）个结点的值。 2④ 编写程序：求二叉树中以值为 x 的节点为根的子树深度。 3④ 假设二叉树采用二叉链存储结构存储，设计一个算法，按层次顺序（同一层次自左至右）遍历二叉树。 4④ 假设二叉树采用链式存储结构进行存储，设计一个算法，求二叉树 b 中值为 x 的结点的层号。 5④ 设计算法：统计一棵二叉树中所有叶结点的数目。【南开 2000】 4.9.5 知识点：哈夫曼树 一、选择题 1② 利用 n 个值作为叶结点上的权值生成的哈夫曼树中共包含有（ D ）个结点。 A．n C．2*n B．n+1 D．2*n－1 2② 利用 3，6，8，12 这四个值作为叶结点的权值生成一棵哈夫曼树，该树的带权路径长度为（ A ）。 A．55 C．58 B．29 D．38 3③ 根据使用频率为 5 个字符设计的哈夫曼编码不可能是（ C ）。 A．111，110，10，01，00 C．100，11，10，1，0 B．000，001，010，011，1 D．001，000，01，11，10 4② 设有 13 个值，用它们组成一颗哈夫曼树，该哈夫曼树共有（D ）个结点。 A．13 B．12 C．26 D．25 5③ 若度为 m 的哈夫曼树中，其叶子结点的个数为 n，则非叶子结点的个数为（ A ）。 A．n－1 B． n/m－1 D．n/（m－1） －1 C．（n－1）/（m－1） 6② 下述编码中哪一个不是前缀码（ B ）。【中科院计算所 2000】 A．（00，01，10，11） B．（0，1，00，11） C．（0，10，110，111） D．（1，01，000，001） 7② 下面几个符号串编码集合中，不是前缀编码的是（ B ）。【西安电子科技2001】 A．{0，10，110，1111} B．{11，10，001，101，0001} 例：1011 C．{00，010，0110，1000} D．{b，c，aa，ac，aba，abb，abc} 二、 填空题 1③ 用 5 个权值{4， 5， 6， 7， 8}构造的哈夫曼（Huffman）树的带权路径长度是_4_____，各结点对应的哈夫曼 编码为__110____、_111_____、___00___、__01___、___10___。 2③ 有数据 WG={7，19，2，6，32，3，21，10}，则所建 Huffman 树的树高是__6____，带权路径长度 WPL 为 __261_____。【南京理工 1999】 三、 判断题 （ T ）1① 哈夫曼树中不存在度为 1 的结点。 （ F ）2② 在哈夫曼树中，权值相同的叶子结点都在同一层。 （ F ）3② 在哈夫曼树中，权值较大的叶子结点一般离根结点较远。 （ F ）4② 在哈夫曼编码中，当两个字符出现的频率相同时，其编码也相同，对于 这种情况应作特殊处理。 （ T ）5② 哈夫曼树的结点个数不能是偶数。【北京邮电 2000】 （ T ）6② 一棵哈夫曼树的带权路径长度等于其中所有分支结点的权值之和。【合肥工业 2000】 （ F ）7② 哈夫曼树无左右子树之分。【青岛 2000】 （ F ）8② 当一棵具有n 个叶子结点的二叉树的WPL 值为最小时，称其树为Huffman 树，且其二叉树的形状必是唯一的。【南京航空航天 1995】 （ T ）9② 哈夫曼树是带权路径长度最短的树，路径上权值较大的结点离根较近。【北京邮电 1999】 四、简答题 ③ 如表所列的数据表给出了在一篇有19710各词的英文文章中出现最普通的15个单词的出现频度。 假定一篇正文仅由上述字符数据表中的词组成，那么它们的最佳编码是什么？平均长度是多少？ 单 词 The of a to and in that he is at on for His are be 出现频度 1192 677 541 518 462 450 242 195 190 181 174 157 138 124 123 5.8 习题 5.8.1 知识点：图的基本概念 一、选择题 1① n 个顶点的连通图至少有（ A ）条边。 A．n-1 C．n+1 B．n D．0 2① 在无向图中定义顶点 vi 与 vj 之间的路径为从 vi 到达 vj 的一个（ B ）。 A．顶点序列 C．权值总和 B．边序列 D．边的条数 3① 具有 n 个顶点的有向图最多可包含（ D ）条有向边。 A．n-1 B． n D． n（n-1） C．n（n-1）/2 4① 在无向图中定义顶点的度为与它相关联的（ B ）的数目。 A．顶点 C．权 B．边 D．权值 5① 一个有 N 个顶点的无向图中，要连通全部顶点至少需要（ C ）条边。 A．N B．N＋1 C．N－1 D．N/2 6② 含 N 个顶点的连通图中的任意一条简单路径，其长度不可能超过（ C ）。 A．1 B．N/2 D．N C．N－1 7② 设无向图的顶点个数为 n，则该图最多有（ B ）条边。【清华 1998】【西安电子科技大 1998】【北京航空航天 1999】 A．n-1 B． n（n-1）/2 D．n（n-1） C．n（n+1）/2 8② 在一个无向图中，所有顶点的度数之和等于所有边数（B ）倍，在一个有向图中，所有顶点的入度之和等于所有顶点出度之和的（C ）倍。【哈尔滨工业 2001】 A．1/2 B．2 C．1 D．4 二、填空题 1② n（n﹥0）个顶点的无向图中顶点的度的最大值为___n-1_____。 2② n（n﹥0）个顶点的无向图最少有___0_____条边。 3② n（n﹥0）个顶点的连通无向图各顶点的度之和最少为__2(n-1)______。 4② 具有 n 个顶点的无向完全图，边的总数为__n(n-1)/2_______条； 而具有 n 个顶点的有向完全图边的总数为__n(n-1)_______条。 5② 在有 n 个顶点的有向图中，每个顶点的度最大可达__2(n-1)_______。 6② 在有 n 个顶点的有向图中，若要使任意两点间可以互相到达，则至少需要__n____ 条弧。【合肥工业大2000】 7② n 个顶点的连通无向图，其边的条数至少为__n-1____。【哈尔滨工业 2000】 8② N 个顶点的连通图的生成树含有_n-1_____条边。【中山 1998】 9② 一个连通图的__生成树____是一个极小连通子图。【重庆 2000】 三、判断题 （ T）1① 如果无向图中各个顶点的度都大于 2，则该图中必有回路。 （ F ）2① 一个图的子图可以是空图，顶点个数为 0。 （ T ）3① 有 n （n≥1） 个顶点的有向强连通图最少有 n 条边。 （ T ）4② 树中的结点和图中的顶点就是指数据结构中的数据元素。【青岛 2001】 （ F ）5② 在 n 个结点的无向图中，若边数大于 n-1，则该图必是连通图。【中科院软件所 1997】 （ T）6② 强连通图的各顶点间均可达。【北京邮电 2000】 （ F）7② 强连通分量是无向图的极大强连通子图。【北京邮电 2002】 （ F）8② 连通分量指的是有向图中的极大连通子图。【燕山 1998】 四、简答题 1③ 设连通图 G 如图所示。 （1）如果有关结点，请找出所有关结点。 （2）如果想把该连通图变成重连通图，至少在图中加几条边？如何加？ 图 5.59 1 题图 5.8.2 知识点：图的存储 一、选择题 1② 在 n 个顶点的有向无环图的邻接矩阵中至少有（C ）个零元素。 A．n B．n（n-1）/2 D．n（n-1） C．n（n+1）/2 2② 若采用邻接矩阵法存储一个 n 个顶点的无向图，则该邻接矩阵是一个（ D ）。 A．上三角矩阵 B．稀疏矩阵 C．对角矩阵 D．对称矩阵 3② 对于一个有 N 个顶点的无向图，若采用邻接矩阵表示，则该矩阵的大小是（ D ）。 A．N B．（N－1）*（N－1） D．N*N D．O（n2） C．N－1 4③ 设一个有 n 个顶点和 e 条边的有向图采用邻接矩阵表示，要计算某个顶点的出度所耗费的时间是（ A ）。 A．O（n） B．O（e） C．O（n+e） 5② 对于具有 e 条边的无向图，它的邻接表中有（ D ）个边结点。 A．e-1 B．e C．2（e-1） D．2e 6③ 下面结构中最适于表示稀疏无向图的是（ E ），适于表示稀疏有向图的是（ D ）。 【北京工业 2001】 A．邻接矩阵 B．逆邻接表 C．邻接多重表 D．十字链表 E．邻接表二、填空题 1① 用邻接矩阵存储图，占用存储空间数与图中顶点个数___n 有_____关，与边数__无______关。 2① 邻接表和十字链表适合于存储___有向______图，邻接多重表适合于存储____无向_____图。 3② 在有向图的邻接矩阵表示中，计算第 I 个顶点入度的方法是__第 i 列非零元素个数____。【青岛 2002】 4② 在图 G 的邻接表表示中，每个顶点邻接表中所含的结点数， 对于无向图来说等于该顶点的___度______；对于有向图来说等于该顶点的___出度______。【燕山 2001】 5② 对于一个具有 n 个顶点 e 条边的无向图的邻接表的表示， 则表头向量大小为__n____，邻接表的边结点个数为__2e____。【青岛 2002】 三、判断题 （T）1① 用邻接矩阵存储一个图时，在不考虑压缩存储的情况下，所占用的存储空间大小只与图中的顶点个数有关，而与图的边数无关。 （ T ）2① 存储无向图的邻接矩阵是对称的，因此只要存储邻接矩阵的下（上）三角部分就可以了。 （ T ）3② 邻接矩阵只适用于稠密图（边数接近于顶点数的平方）， 邻接表适用于稀疏图（边数远小于顶点数的平方）。 （ F ）4② 邻接多重表是无向图和有向图的链式存储结构。【南京航空航天 1995】 （ F ）5② 十字链表是无向图的一种存储结构。【青岛 2001】 （ T ）6② 无向图的邻接矩阵可用一维数组存储。【青岛 2000】 （ T ）7② 有 n 个顶点的无向图， 采用邻接矩阵表示， 图中的边数等于邻接矩阵中非零元素之和的一半。 【北京邮电 1998】 （ F ）8② 有向图的邻接矩阵是对称的。【青岛 2001】 （ F ）9② 无向图的邻接矩阵一定是对称矩阵，有向图的邻接矩阵一定是非对称矩阵。 【东南 2001】【哈尔滨工业 1999】 （ F ）10② 邻接矩阵适用于有向图和无向图的存储，但不能存储带权的有向图和无向图，而只能使用邻接表存储形式来存储它。【上海海运 1998】 （ F ）11② 一个有向图的邻接表和逆邻接表中结点的个数可能不等。【上海交通1998】 四、简答题 1③ 在下图所示的有向图中，试给出： （1） 每一个顶点的入度和出度； （2） 邻接矩阵； （3） 邻接表、逆邻接表； （4） 强连通分量。 v1 v6 v2 v3 v4 v5 2③ 在下图所示的无向图中，试给出： 该图的邻接矩阵 该图的邻接表 该图的多重邻接表 给出每个顶点的度 V1 V3 V4 V6 V0 V2 V5 3③ 已知无向图 G，V（G）={1，2，3，4}，E（G）={（1，2），（1，3），（2，3），（2, 4），（3，4）} 试画出 G 的邻接多重链表，并说明，若已知点 i，如何根据邻接多重链表找到与 i 相邻的点 j？ 【东南 1998】 五、算法题 1④ 设有向图用邻接表表示，图有 n 个顶点，表示为 1 至 n，试写一个算法求顶点 k 的入度（1 5.8.3 知识点：图的遍历 一、选择题 1② 为了实现图的广度优先遍历，BFS 算法使用的一个辅助数据结构是（B ）。 A．栈 B．队列 C．二叉树 D．树 2② 一个连通图的生成树是包含图中所有顶点的一个（ C ）子图。 A．极小 B．连通 C．极小连通 D．无环 3① 采用邻接表存储的图的深度优先遍历算法类似于二叉树的（C ）。 A．前序遍历 B．中序遍历 C．后序遍历 D．层次遍历 4② 对于有向图，其邻接矩阵表示比邻接表表示更易于（A ）。 A．求一个顶点的度 B．求一个顶点的邻接点 D．进行图的广度优先遍历 C．进行图的深度优先遍历 5① 下列说法不正确的是（ C ）。【青岛 2002】 A．图的遍历是从给定的源点出发每一个顶点仅被访问一次 B．遍历的基本算法有两种：深度遍历和广度遍历 C．图的深度遍历不适用于有向图 D．图的深度遍历是一个递归过程 6② 无向图 G=（V，E），其中：V={a，b，c，d，e，f}，E={（a，b），（a，e），（a，c）， （b，e），（c，f），（f，d），（e，d）}，对该图进行深度优先遍历，得到的顶点序列正确的是 （ D ）。【南京理工 2001】 A．a，b，e，c，d，f B．a，c，f，e，b，d C．a，e，b，c，f，d D．a， e，d，f，c，b 7② 下图中给出由 7 个顶点组成的无向图。从顶点 1 出发，对它进行深度优先遍历得到的序列是（ （1）C ），而进行广度优先遍历得到的顶点序列是（ （2）C ）。【中科院软件所 1999】 （1）：A．1354267 B．1347652 C．1534276 D．1247653 E．以上答案均不正确 （2）：A．1534267 B．1726453 C．l354276 D．1247653 E．以上答案均不正确 图 5.62 7 题图 二、填空题 1① 深度优先生成树的高度比广度优先生成树的高度___高_____。 2① 遍历图的基本方法有____深度_____优先搜索和___广度______优先搜索两种。 3① 已知一无向图 G=（V，E），其中 V={a，b，c，d，e }， E={（a，b），（a，d），（a， c），（d，c），（b，e）}。现用某一种图遍历方法从顶点 a 开始遍历图，得到的序列为 abecd，则采用的是___深度_________遍历方法。【南京理工 1996】 4① 为了实现图的广度优先搜索，除了一个标志数组标志已访问的图的结点外，还需__ 队列____存放被访问的结点以实现遍历。【南京理工 1999】 三、判断题 （T ）1② 图的深度优先搜索（depth first search）是一种典型的回溯搜索的例子，可以通过递归算法求解。 （ T ）2① 图的广度优先搜索（breadth first search）算法不是递归算法。 （ T ）3② 对一个连通图进行一次深度优先搜索（depth first search）可以遍访图中的所有顶点。 四、简答题 1③ 设连通图 G 如图所示。试画出该图及其对应的邻接表表示，并给出对它执行从 v0 开始的深度优先搜索的结果。 2③ 首先将如下图所示的无向图给出其存储结构的邻接链表表示，然后写出从顶点 v1 出发，对图分别进行深度和广度优先遍历的结果。 图 5.64 2 题图 3③ 对下图所示的有向图，从顶点 v1 出发，分别画出其深度和广度生成树。 V1 V5V2 V3 V4 V8V6 V7 图 5.65 3 题图 五、算法题 1④ 使用邻接矩阵，实现图的深度优先遍历算法。 2④ 使用邻接表，实现图的广度优先遍历算法。 3④ 假设图采用邻接表存储，分别写出基于 DFS 和 BPS 遍历的算法来判别定点 i 和定点 j（i≠j）之间是否有路 径。 5.8.4 知识点：最小生成树 一、选择题 1② 在用 Kruskal 算法求解带权连通图的最小（代价）生成树时，通常采用一个（ D ）辅助结构，判断一条边的两个端点是否在同一个连通分量上。 A．位向量 B．堆 C．并查集 D．生成树顶点集合 2② 任何一个带权的无向连通图的最小生成树（ B ）。 A．只有一棵 B．有一棵或多棵 C．一定有多棵 D．可能不存在 3② 一个无向连通图的生成树是含有该连通图的全部顶点的（ A ）。 A．极小连通子图 B．极小子图 C．极大连通子图 D．极大子图 4② 对于含有 n 个顶点的带权连通图，它的最小生成树是指图中任意一个（ C ）。 A．由 n-1 条权值最小的边构成的子图 B．由 n-1 条权值之和最小的边构成的子图 C．由 n-1 条权值之和最小的边构成的连通子图 D．由 n 顶点构成的边的权值之和最小的连通子图 5② 在图采用邻接表存储时，求最小生成树的 Prim 算法的时间复杂度为（B ）。【合肥工业 2001】 A. O（n） B. O（n e+ ） C. O（n2） D. O（n3） 二、填空题 1② 101 个顶点的连通网络 N 有 100 条边，其中权值为 1，2，3，4，5，6，7，8，9，10 的边各 10 条，则网络 N 的最小生成树各边的权值之和为_550________。 2② 在使用 Kruskal 算法构造连通网络的最小生成树时，只有当一条候选边的两个端点不在同一个__边__上，才有 可能加入到生成树中。 3② 构造连通网络最小生成树的两个典型算法是____prim_____和__kruskal_______。 4② Prim（普里姆）算法适用于求_稠密_的网的最小生成树； kruskal（克鲁斯卡尔）算法适用于求__稀疏____的网的最小生成树。【厦门 1999】 5③ 对于含 N 个顶点 E 条边的无向连通图，利用 Prim 算法生成最小代价生成树其时间复杂度为__O(n2)___， 利用 Kruskal 算法生成最小代价生成树其时间复杂度为_O(eloge)_____。【长沙铁道 1998】 三、判断题 （ F ）1② 最小生成树是指边数最少的生成树。 （ F ）2① 从 n 个顶点的连通图中选取 n-1 条权值最小的边，即可构成最小生成树。 （ F ）3② 只要无向网中没有权值相同的边，其最小生成树就是唯一的。 （ F ）4② 只要无向网中有权值相同的边，其最小生成树就不可能是唯一的。 （ F ）5② 需要借助于一个队列来实现 DFS 算法。【南京航空航天 1996】 （ F ） 6② 广度遍历生成树描述了从起点到各顶点的最短路径。【合肥工业2001】 （ F ）7② 任何无向图都存在生成树。【北京邮电 2000】 （ F ）8② 不同的求最小生成树的方法最后得到的生成树是相同的。【南京理工1998】 （ F ）9② 带权无向图的最小生成树必是唯一的。【南京航空航天 1996】 （ T ）10② 最小生成树的 KRUSKAL 算法是一种贪心法（GREEDY）。【华南理工 2002】 （ T ）11② 求最小生成树的普里姆（Prim）算法中边上的权可正可负。【南京理工 1998】 （ T ）12② 最小生成树问题是构造连通网的最小代价生成树。【青岛 2001】 （ T ）13② 在图 G 的最小生成树 G1 中，可能会有某条边的权值超过未选边的权值。【合肥工业 2000】 四、简答题 1③ 对下图所示的连通图，请分别用 Prim 和 Kruskal 算法构造其最小生成树。 v2 2 v1 3 v3 1 2 v4 4 v6 1 v8 2 v5 1 2 v7 1 2 图 5.66 1 题图 2④ 已知世界六大城市为:北京（Pe）、纽约（N）、巴黎（Pa）、伦敦（L）、东京（T）、 墨西哥（M），下表给出了这六大城市之间的交通里程（单位:百公里），试作下面的题目： （1）画出这六大城市的交通网络图; （2）画出该图的邻接表表示法; （3）画出该图按权值递增的顺序来构造的最小（代价）生成树。 表 5.1 2 题表 pe n pa L T M Pe N 109 82 81 21 124 58 55 108 32 3 97 92 95 89 113 109 PA 82 58 L T M 3③ 已知无向图如下所示： （1）给出从V1 开始的广度优先搜索序列； （2）画出它的邻接表； （3）画出从V1 开始深度优先搜索生成树。【燕山 2000】 81 55 3 21 108 97 95 124 32 92 89 113 图 5.67 3 题图 五、算法题 1④ 如下图是一个城市连接图，图中的权值表示两个城市之间的里程（单位：100km） 现要设计一条铁路贯穿所有城市（即从一个任一城市可以到达其他城市），设计一个算法，求出最小代价。假设每 1km 的铁路的造价为 100 万元。 图 5.68 1 题图 5.8.5 知识点：图的应用 一、选择题 1② 设有向图有 n 个顶点和 e 条边，采用邻接表作为其存储表示，在进行拓扑排序时，总的计算时间为（ B ）。 A．O（nlog2 e） C．O（ne） B． O（n e+ ） D．O（n2） 2② 图中有关路径的定义是（ A ）。 A．由顶点和相邻顶点序偶构成的边所形成的序列 B．由不同顶点所形成的序列 C．由不同边所形成的序列 D．上述定义都不是 3② 以下说法正确的是（ A ）。 A．连通图的生成树是该连通图的一个极小连通子图 B．无向图的邻接矩阵是对称的，有向图的邻接矩阵一定是不对称的 C．任何一个有向图，其全部顶点可以排成一个拓扑序列 D．有回路的图不能进行拓扑排序 4② 关键路径是事件顶点网络中（ A ）。 A．从源点到汇点的最长路径 C．最长的回路 B．从源点到汇点的最短路径 D．最短的回路 5② 下面哪一方法可以判断出一个有向图是否有环（回路）（ B ）。 A．深度优先遍历 B．拓扑排序 C．求最短路径 D．求关键路径 6② 一个有向无环图的拓扑排序序列（ B ）是唯一的。【北京邮电 2001】 A．一定 B．不一定 7② 在有向图 G 的拓扑序列中，若顶点 Vi 在顶点 Vj 之前，则下列情形不可能出现的是（D）。【南京理工 2000】 A．G 中有弧 8② 在用邻接表表示图时，拓扑排序算法时间复杂度为（ B ）。【合肥工业 2000】【南京理工 2001】【青岛2002】 A. O（n） B. O（n e+ ） C. O（n2） D. O（n3） 9② 下面关于求关键路径的说法不正确的是（ A）。【南京理工 1998】 A．求关键路径是以拓扑排序为基础的 B．一个事件的最早开始时间同以该事件为尾的弧的活动最早开始时间相同 C．一个事件的最迟开始时间为以该事件为尾的弧的活动最迟开始时间与该活动的持续时间的差 D．关键活动一定位于关键路径上 10② 下列关于 AOE 网的叙述中，不正确的是（D）。【北方交通 1999】【北京工业 1999】 A．关键活动不按期完成就会影响整个工程的完成时间 B．任何一个关键活动提前完成，那么整个工程将会提前完成 C．所有的关键活动提前完成，那么整个工程将会提前完成 D．某些关键活动提前完成，那么整个工程将会提前完成 11③ 下列哪一种图的邻接矩阵是对称矩阵？（ B）【北方交通 2001】 A．有向图 B．无向图 C．AOV 网 D．AOE 网 二、 填空题 1① 在 AOE 网中，从源点到汇点路径上各活动时间总和最长的路径称为___关键路径______。 2① 若对一个有向无环图进行拓扑排序，再对排在拓扑有序序列中的所有顶点按其先后次序重新编号，则在相应的 邻接矩阵中所有__非零______元素将集中到对角线以上。 3① 有向图 G 可拓扑排序的判别条件是___AOV 网 有向无环图___。【长沙铁道1998】 4② AOV 网中，结点表示___活动___，边表示__优先级关系___。 AOE 网中，结点表示___事件______，边表示____活动_____。【北京理工 2001】 5② 在 AOE 网中，从源点到汇点路径上各活动时间总和最长的路径称为____关键路径_____。【重庆 2000】 三、 判断题 （ F ）1① 对任何用顶点表示活动的网络（AOV 网）进行拓扑排序的结果都是唯一的。 （ T ）2① 有回路的有向图不能完成拓扑排序。 （ F ）3① 在 AOE 网络中一定只有一条关键路径。 （ F ）4② 对一个有向图进行拓扑排序（topological sorting），一定可以将图的所有顶点按其关键码大小排列到一个拓扑有序的序列中。 （ T ）5② 对于一个边上权值任意的带权有向图，使用 Dijkstra 算法可以求一个顶点到其它各个顶点的最短路径。 （ F ）6② 拓扑排序算法把一个无向图中的顶点排成一个有序序列。【南京航空航天 1995】 （ T ）7② 拓扑排序算法仅能适用于有向无环图。【南京航空航天 1997】 （ F ）8② 拓扑排序的有向图中，最多存在一条环路。【大连海事 2001】 （ F ）9② 任何有向图的结点都可以排成拓扑排序，而且拓扑序列不唯一。【上海交通 1998】 （ F ）10② 即使有向无环图的拓扑序列唯一，也不能唯一确定该图。【合肥工业 2001】 （ T ）11② 若一个有向图的邻接矩阵对角线以下元素均为零，则该图的拓扑有序序列必定存在。【中科院 1997】 （F ）12② AOV 网的含义是以边表示活动的网。【南京航空航天 1995】 （ F ）13② 对一个 AOV 网，从源点到终点的路径最长的路径称作关键路径。【南京航空航天 1995】 （ T ）14② AOE 网一定是有向无环图。【青岛 2001】 （ F ）15② 在 AOE 图中，关键路径上某个活动的时间缩短，整个工程的时间也就必定缩短。【大连海事 2001】 （ T ）16② 当改变网上某一关键路径上任一关键活动后，必将产生不同的关键路径。【上海交通 1998】 四、简答题 1③ 已知有向图，其边集为{<1，2>，<2，3>，<5，2>，<5，6>，<6，4>，<3，4>}，求此图的所有可能的拓扑序列。若以此顺序输入建立图的邻接表，再在此存储储结构上执行拓扑排序过程，则得到的拓扑序列是哪一种？ 2③ 下表给出了某工程各工序之间的优先关系和各工序所需时间 （1）画出相应的 AOE 网。 （2）列出各事件的最早发生时间，最迟发生时间。 （3）找出关键路径并指明完成该工程所需最短时间。 表 5.2 2 题表 工序代号 所需时间 先驱工作 A B C 50 A B D 8 E 15 F 40 G 300 E H 15 G，I I J K 15 L 30 M 20 L N 40 G 15 10 -- -- 120 60 E I B C D B F，I H，J，K 3③ 已知一图如下图所示： （1） 写出该图的邻接矩阵； （1） （2） （3） 写出全部拓扑排序； 以 v1 为源点，以 v8 为终点，给出所有事件允许发生的最早时间和最晚时间，并给出关键路径； 求 V1 结点到各点的最短距离。 4③（1）对于有向无环图，叙述求拓扑有序序列的步骤； 图 5.69 3 题图 （2）对于以下的图，写出它的四个不同的拓扑有序序列。【南开 1998】 图 5.70 4 题图 五、算法题 1④ 已有邻接表表示的有向图，请编程判断从第u顶点至第v顶点是否有简单路径，若有则印出该路径上的顶点。要求：先描述图的存储结构，并简述算法思路；查找邻接点等图的运算要自己实现。（采用非递归算法）【北京工业 2000】 2④ 假设以邻接矩阵作为图的存储结构，编写算法判别在给定的有向图中是否存在一个简单有向回路，若存在，则以顶点序列的方式输出该回路（找到一条即可）。（注：图中不存在顶点到自己的弧）【清华 1994】 3④ 已知个 n 顶点的有向图，用邻接矩阵表示，编写函数计算每对顶点的最短路径。【南京航航天2001】 6.10 习题 6.10.1 知识点：直接插入排序 一、选择题 1② 用直接插入排序方法对下面四个序列进行排序（由小到大），元素比较次数最少的是（ C ）。 A． 94，32，40，90，80，46，21，69 B． 32，40，21，46，69，94，90，80 C． 21，32，46，40，80，69，90，94 D． 90，69，80，46，21，32，94，40 2② 直接插入排序在最坏情况下的时间复杂度为（ D ） A． O（log2 n） B． O（n） C． O（nlog2 n） D． O（n2） 3② 若对 n 个元素进行直接插入排序，则进行第 I 趟排序过程前，有序表中的元素个数为（ A ） A．I B．I+1 C．I-1 D．1 二、填空题 1② 直接插入排序用监视哨的作用是__做比较_________。【南京理工 2001】 三、判断题 （ T ） 1② 直接选择排序算法在最好情况下的时间复杂度为 O（n）。【合肥工业 2001】 四、简答题 1③ 算法模拟：设待排序的记录共7个，排序码分别为8，3，2，5，9，1，6。用直接插入排序以排序码序列的变化描述形式说明排序全过程（动态过程）要求按递减顺序排序。【山东工业 1997】 五、算法题 1③ 请编写直接插入排序算法。（用 C 语言写） Struct rcdtype{ Int key; Element otheritem; } ARRAY[0..n]; 【北京轻工业 1998】 6.10.2 知识点：希尔排序 一、选择题 1③ 对序列{15，9，7，8，20，-1，4}，用希尔排序方法排序，经一趟后序列变为{15，-l，4，8，20，9，7}， 则该次采用的增量是（ B ） A. l B. 4 C. 3 D. 2 二、 填空题 1③ 设用希尔排序对数组{98，36，-9，0，47，23，1，8，10，7}进行排序，给出的步长（也称增量序列）依次是 4，2，1 则排序需____3_____趟，写出第一趟结束后，数组中数据的排列次序_10,7,-9,0,47,23,1,8,98,36________。 2③ 关键码序列{Q，H，C，Y，Q，A，M，S，R，D，F，X}，要按照关键码值递增的次序进行排序，若采用初始步长为 4 的 Shell 排序法，则一趟扫描的结果是_Q，A，C，S，Q，D，F，S，R，H，M，X _； 【北京 1997】 三、 简答题 1③ 对下面数据表，写出采用 SHELL 排序算法排序的每一趟的结果，并标出数据移动情况。（125，11，22， 34，15，44，76，66，100，8，14，20，2，5，1）。【合肥工业 1999】 6.10.3 知识点：冒泡排序 一、 选择题 1③ 若用冒泡排序方法对序列{10，14，26，29，41，52}从大到小排序，需进行 （ C ）次比较。 A. 3 B. 10 C. 15 D. 25 2 对ｎ个不同的排序码进行冒泡排序，在下列哪种情况下比较的次数最多。（ B ） Ａ. 从小到大排列好的 Ｂ. 元素逆序 Ｃ. 元素无序 Ｄ. 元素基本有序 3② 对ｎ个不同的排序码进行冒泡排序，在元素无序的情况下比较的次数为（ D ） Ａ. n+1 Ｂ. n Ｃ. n-1 Ｄ. n（n-1）/2 二、 简答题 1② 设要求从大到小排序。问在什么情况下冒泡排序算法关键字交换的次数为最多。 三、算法题 1④ 冒泡排序算法是把大的元素向上移（气泡的上浮），也可以把小的元素向下移（气泡的下沉）请给出上浮和下 沉过程交替的冒泡排序算法。【吉林 2001】 6.10.4 知识点：快速排序 一、选择题 1③ 有一组数据{15，9，7，8，20，-1，7，4}， 用快速排序的划分方法进行一趟划分后数据的排序为 （ A ）（按递增序）。 A．下面的 B，C，D 都不对。 B．{9，7，8，4，-1，7，15，20} C．{20，15，8，9，7，-1，4，7} D. {9，4，7，8，7，-1，15，20} 2③ 一组记录的关键码为{46，79，56，38，40，84}，则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为（ C ）。 A．{38，40，46，56，79，84} B. {40，38，46，79，56，84} C．{40，38，46，56，79，84} D. {40，38，46，84，56，79} 3③ 对下列关键字序列用快速排序法进行排序时，速度最快的情形是（ A ）。 A． {21，25，5，17，9，23，30} B．{25，23，30，17，21，5，9} C． {21，9，17，30，25，23，5} Ｄ．{5，9，17，21，23，25，30} 4③ 对关键码序列{28，16，32，12，60，2，5，72}快速排序，从小到大一次划分结果为（ B ）。 A. {2，5，12，16} 26 {60，32，72} B. {5，16，2，12} 28 {60，32，72} C. {2，16，12，5} 28 {60，32，72} D. {5，16，2，12} 28 {32，60，72} 5③ 当 n 个整型数据是有序时，对这 n 个数据用快速排序算法排序，则时间复杂度是 （ B ）， 当用递归算法求 n！时，算法的时间复杂度是 （ A ）。 A. O（n） B. O（nlog2 n） C. O（n2） D. O（log2 n） 6② 快速排序在最坏情况下的时间复杂度是（ B ），比（ DE ）的性能差。 A．O（nlog2 n） B．O（n2） C．O（n3） D．堆排序 E．冒泡排序 F．选择排序 7① 快速排序方法在（ D ）情况下最不利于发挥其长处。 A. 要排序的数据量太大 B. 要排序的数据中含有多个相同值 C. 要排序的数据个数为奇数 D. 要排序的数据已基本有序二、填空题 1② 对于 7 个元素的集合{1，2，3，4，5，6，7}进行快速排序，具有最小比较和交换次数的初始排列次序为______4,7,5,6,1,3,2_______________________。 2② 在数据表有序时，快速排序算法的时间复杂度是____ O（n2）________。【合肥工业 2001】 三、判断题 （ F ）1② 快速排序的速度在所有排序方法中为最快，而且所需附加空间也最少。 （ F ）2② 在初始数据表已经有序时，快速排序算法的时间复杂度为 O（nlog2 n）。 （ F ）3② 在待排数据基本有序的情况下，快速排序效果最好。【南京理工 1997】 四、算法题 1④ 写出一趟快速排序算法。【山东师范 2000】 2③ 借助于快速排序的算法思想，在一组无序的记录中查找给定关键字值等于 key 的记录。设此组记录存放于数组 r[l..h]中。若查找成功，则输出该记录在 r 数组中的位置及其值，否则显示―not find‖信息。请编写出算法并简要说明算法思想。【北京邮电 1998】 6.10.5 知识点：直接选择排序 一、 选择题 1③ 采用简单选择排序，比较次数与移动次数分别为（ C ）。 A. O（n）， O（log2 n） B. O（log2 n）， O（n2） C. O（n2）， O（n） D. O（nlog2 n）， O（n） 二、 填空题 1③ 对 n 个记录的表 r[1..n]进行简单选择排序，所需进行的关键字间的比较次数为_n(n-1)/2______。 2③ 用链表表示的数据的简单选择排序，结点的域为数据域 data，指针域 next ；链表首指针为 head ，链表无头结点。 selectsort（head） p=head; while （p（1）->next!=NULL______________） { q=p; r=（2）q->next______________; while（（3）__r!=NULL___________ ） {if （（4）r->data tmp=q->data; q->data=p->data; p->data=tmp; p= （6）p->next_______ _______; } 【南京理工 2000】 3③ 下面的 c 函数实现对链表 head 进行选择排序的算法，排序完毕，链表中的结点按结点值从小到大链接。请在空框处填上适当内容，每个空框只填一个语句或一个表达式： #include { node *p，*q，*r，*s; p=（node *）malloc（sizeof（node））; p->link=head; head=p; while（p->link!=null） {q=p->link; r=p; while （（1）q!=NULL___________） { if （q->link->data {s=r->link; r->link=s->link; s->link= （3）__p->link____; （4）__p->link=s___;} （5）p=p->llink___________ ; } p=head; head=head->link; free（p）; return（head）; } 【复旦 1999】 4④ 下面的排序算法的思想是：第一趟比较将最小的元素放在 r[1]中，最大的元素放在 r[n]中，第二趟比较将次小的放在 r[2]中，将次大的放在 r[n-1]中，…，依次下去，直到待排序列为递增序。（注：<-->）代表两个变量的数据交换）。 void sort（SqList &r，int n） { i=1; while（（1）i_<=n/2____________） { min=max=i; for （j=i+1;（2）j<=n-i+1 ;++j）{ if（（3）r[j].key r[max] <--> r[n-i+1]; } i++; } }【南京理工 2001】 三、简答题 1② 算法模拟：设待排序的记录共7 个，排序码分别为8，3，2，5，9，1，6。用直接选择排序以排序码序列的变化描述形式说明排序全过程（动态过程）要求按递减顺序排序。 【山东工业 1997】 四、算法题 1④ 输入 50 个学生的记录（每个学生的记录包括学号和成绩），组成记录数组，然后按成绩由高到低的次序输出（每行 10 个记录）。排序方法采用选择排序。 【北京师范 1999】 6.10.6 知识点：堆排序 一、选择题 1③ 在含有 n 个关键字的小根堆（堆顶元素最小）中，关键字最大的记录有可能存储在（ D ）位置上。 A．n/2 B．n/2 -1 C．1 D．n/2 +2 2② 以下序列不是堆的是（ D ）。 A. {100，85，98，77，80，60，82，40，20，10，66} B. {100，98，85，82，80，77，66，60，40，20，10} C. {10，20，40，60，66，77，80，82，85，98，100} D. D. {100，85，40，77，80，60，66，98，82，10，20} 3② 下列四个序列中，哪一个是堆（ C ）。 A. 75，65，30，15，25，45，20，10 B. 75，65，45，10，30，25，20，15 C. 75，45，65，30，15，25，20，10 D. 75，45，65，10，25，30，20，15 4② 堆排序是（ E ）类排序，堆排序平均执行的时间复杂度是（ G ）和需要附加的存储空间复杂度是（ ） A. 插入 B. 交换 C. 归并 D. 基数 E. 选择 F. O（n2）和 O（1） G. O（nlog2 n）和 O（1） H. O（nlog2 n）和 O（n） I. O（n2）和 O（n） 5② 对 n 个记录的文件进行堆排序，最坏情况下的执行时间是多少？（ C ） A．O（log2 n）B．O（n） C．O（nlog2 n） D．O（n2） 6③ 有一组数据{15，9，7，8，20，-1，7，4}，用堆排序的筛选方法建立的初始堆为 （ C ） A．-1，4，8，9，20，7，15，7 B．-1，7，15，7，4，8，20，9 C．-1，4，7，8，20，15，7，9 D．A，B，C 均不对。 二、填空题 1③ 堆是一种有用的数据结构. 堆排序是一种___选择_____排序，堆实质上是一棵__完全二叉树___结点的层次序列。对含有 N 个元素的序列进行排序时，堆排序的时间复杂度是 __ O（nlog2 n）______，所需的附加存储结点是___1_____。关键码序列{05，23，16，68， 94，72，71，73}是否满足堆的性质____满足____。 【山东工业 1996】 2② 已知一关键码序列为：3，87，12，61，70，97，26，45。试根据堆排序原理，填写完整下示各步骤结果。 建立堆结构：__97，87，26，61，70，12，3，45___________________ 交换与调整： （1）87 70 26 61 45 12 3 97;（2）_70，61，26，3，45，12，87，97_; （3）61 45 26 3 12 70 87 97;（4）45，12，26，3，61，70，87，97 （5）26 12 3 45 61 70 87 97;（6）_12， 3，26，45 ，61， 70， 87 ，97; （7）3 12 26 45 61 70 87 97; 【首都经贸 1998】 三、判断题 （ T ）1② 堆肯定是一棵平衡二叉树。 （ F ）2② 堆是满二叉树。 （ T ）3③ {101，88，46，70，34，39，45，58，66，10}是堆。【北京邮电 1999】 （ T ）4② 在用堆排序算法排序时，如果要进行增序排序，则需要采用―大根堆‖。【合肥工业 2000】 （ F ）5② 堆排序是稳定的排序方法。【上海交通 1998】 四、简答题 1③ 关于堆排序方法，完成如下工作： （1） 简述该方法的基本思想。 （2） 分析该算法的时间复杂度。【西南财经 1999】 2② 判别序列{12 ，70，33，65，24，56，48，92，86，33}是否是堆（大顶堆），如果不是，则把它调整为堆。【燕山 2001】 3③ 根据给定的关键字集合{20，15，40，35，45，25，50，30，10}。 （1）构造一棵完全二叉树； （2）画出整理好的一棵堆树； （3）画出一棵输出一个排序记录后的二叉树； （4）画出重新调整好的堆树。【大连海事 2001】 4③ 一最小最大堆（min max heap）是一种特定的堆，其最小层和最大层交替出现，根总是处于最小层。最小最大堆中的任一结点的关键字值总是在以它为根的子树中的所有元素中最小（或最大）。如图 6.1 所示为一最小最大堆。 6.10.7 知识点：归并排序 一、 选择题 1② 归并排序中，归并的趟数是（ B ）。 A．O（n） B．O（log2 n） C．O（nlog2 n） D．O（n2） 2② 归并排序的时间复杂性是（ C ）。 A.O（n2） B. O（n） C. O（nlog2 n） D. O（log2 n） 二、 填空题 1③ 设有字母序列{Q，D，F，X，A，P，N，B，Y，M，C，W}， 请写出按 2 路归并排序方法对该序列进行一趟扫描后的结果 D,Q,F,X,A,P,B,N,M,Y,C,W 。 2① 外部排序的基本方法是归并排序，但在之前必须先生成 有序表 。【北京邮电 2001】 三、 判断题 （ F ）1② 归并排序辅助存储为 O（1）。 6.10.8 知识点：基数排序 一、简答题 1③ 对整数序列{179，208，93，306，55，859，984，9，271，33}图示其基数排序的全过程。 6.10.9 综合习题 一、选择题 1② 某内排序方法的稳定性是指（ D ）。 A．该排序算法不允许有相同的关键字记录 B．该排序算法允许有相同的关键字记录 C．平均时间为 O（nlog2 n）的排序方法 D．以上都不对 2① 下面给出的四种排序法中（ D ）排序法是不稳定性排序法。 A. 插入 B. 冒泡 C. 二路归并 D. 堆 3① 下列排序算法中，其中（ D ）是稳定的。 A. 堆排序，冒泡排序 B. 快速排序，堆排序 C. 直接选择排序，归并排序 D. 归并排序，冒泡排序 4② 若要求尽可能快地对序列进行稳定的排序，则应选（ B ）。 40 70 77 9 30 10 15 45 20 50 30 12 7 min level max level min level max level 图 6.1 1 题图 （1） 画出在上图中插入关键字为 5 的结点后的最小最大堆。 （2） 画出在上图中插入关键字为 80 的结点后的最小最大堆；【浙江 1996】 A．快速排序 B．归并排序 C．冒泡排序 5② 若需在 O（nlog2 n）的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方法是（ C ）。 A. 快速排序 B. 堆排序 C. 归并排序 D. 直接插入排序 6② 下列内部排序算法中： （1） 其比较次数与序列初态无关的算法是（ D ） （2） 不稳定的排序算法是（ ADF ） （3） 在初始序列已基本有序（除去 n 个元素中的某 k 个元素后即呈有序，k< A．快速排序 B.直接插入排序 C.归并排序 D. 直接选择排序 E. 冒泡排序 F. 堆排序 7② 排序趟数与序列的原始状态有关的排序方法是（ CD ）排序法。 A．插入 B. 选择 C. 冒泡 D. 快速 8③ 数据序列{8，9，10，4，5，6，20，1，2}只能是下列排序算法中的（ C ）的两趟排序后的结果。 A．选择排序 B.冒泡排序 C.插入排序 D.堆排序 9③ 数据序列{2，1，4，9，8，10，6，20}只能是下列排序算法中的（ A ）的两趟排序后的结果。 A. 快速排序 B. 冒泡排序 C. 选择排序 D. 插入排序 10③ 对一组数据{84，47，25，15，21}排序，数据的排列次序在排序的过程中的变化为： （1） 84 47 25 15 21 （2） 15 47 25 84 21 （3） 15 21 25 84 47 （4） 15 21 25 47 84 则采用的排序是 （ A ）。 A. 选择 B. 冒泡 C. 快速 D. 插入 11③ 对序列{15，9，7，8，20，-1，4}进行排序，进行一趟后数据的排列变为{4，9， -1，8，20，7，15}；则采用的是（ C ）排序。 A. 选择 B. 快速 C. 希尔 D. 冒泡 12③ 若对序列{15，9，7，8，20，-1，4}进行排序经一趟排序后的排列为{9，15，7， 8，20，-1，4}，则采用的是（ C ）排序。 A．选择 B. 堆 C. 直接插入 D. 冒泡 13③ 下列排序算法中（ B ）不能保证每趟排序至少能将一个元素放到其最终的位置上。 A.快速排序 B. 希尔排序 C. 堆排序 D.冒泡排序 14③ 下列排序算法中（ C ）排序在一趟结束后不一定能选出一个元素放在其最终位置上。 A. 选择 B. 冒泡 C. 归并 D. 堆 15② 在下面的排序方法中，辅助空间为 O（n）的是（ D ） 。 A．希尔排序 B. 堆排序 C. 选择排序 D. 归并排序 16② 下列排序算法中，在待排序数据已有序时，花费时间反而最多的是（ C ）排序。 A． 冒泡 B. 希尔 C. 快速 D. 堆 17② 下列排序算法中，在每一趟都能选出一个元素放到其最终位置上，并且其时间性能受数据初始特性影响的是：（ B ）。 A. 直接插入排序 B. 快速排序 C. 直接选择排序 D. 堆排序 18② 对初始状态为递增序列的表按递增顺序排序，最省时间的是（ C ）算法，最费时间的是（ B ）算法。 A. 堆排序 B. 快速排序 C. 插入排序 D. 归并排序 19② 就平均性能而言，目前最好的内排序方法是（ D ）排序法。 A. 冒泡 B. 希尔排序 C. 直接插入 D. 快速 20③ 如果只想得到 1000 个元素组成的序列中第 5 个最小元素之前的部分排序的序列，用（ D ）方法最快。 A．冒泡排序 B．快速排序 C．希尔排序 D．堆排序 E．直接选择排序 21② 在文件―局部有序‖或文件长度较小的情况下，最佳内部排序的方法是（ B ） A．直接插入排序 B．冒泡排序 C．直接选择排序 22③ 下列排序算法中，（D ）算法可能会出现下面情况：在最后一趟开始之前，所有元素都不在其最终的位置上。 A. 堆排序 B. 冒泡排序 C. 快速排序 D. 插入排序 23③ 下列排序算法中，占用辅助空间最多的是：（ A ） A. 归并排序 B. 快速排序 C. 希尔排序 D. 堆排序 24② 从未排序序列中依次取出一个元素与已排序序列中的元素依次进行比较，然后将其放在已排序序列的合适位置，该排序方法称为（ A ）排序法。 A. 插入 B. 选择 C. 希尔 D.归并 25② 在排序算法中，每次从未排序的记录中挑出最小（或最大）关键码字的记录，加入到已排序记录的末尾，该排序方法是（ A ）。 A. 选择 B. 冒泡 C. 插入 D. 堆 26② 在排序算法中每一项都与其它各项进行比较，计算出小于该项的项的个数，以确定该项的位置叫（ A ） A．插入排序 B．枚举排序 C．选择排序 D．交换排序 27② 就排序算法所用的辅助空间而言，堆排序，快速排序，归并排序的关系是 （A ） A．堆排序 < 快速排序 < 归并排序 B．堆排序 < 归并排序 < 快速排序 C．堆排序 > 归并排序>快速排序 D．堆排序 > 快速排序 > 归并排序 E．以上答案都不对 28③ 设要将序列{q，h，c，y，p，a，m，s，r，d，f，x}中的关键码按字母升序重新排序，（ （1）B ）是初始步长为 4 的 shell 排序一趟扫描的结果； （ （2）C ）是对排序初始建堆的结果；（ （3）A ）是以第一个元素为分界元素的快速一趟扫描的结果。从下面供选择的答案中选出正确答案填入括号内。 A. f ，h ，c ，d ，p ，a ，m ，q ，r ，s ，y ，x B. p ，a ，c ，s ，q ，d ，f ，x ，r ，h ，m ，y C. a ，d ，c ，r ，f ，q ，m ，s ，y ，p ，h ，x D. h ，c ，q ，p ，a ，m ，s ，r ，d ，f ，x ，y E. h ，q ，c ，y ，a ，p ，m ，s ，d ，r ，f ，x 29③ 将两个各有 N 个元素的有序表归并成一个有序表，其最少的比较次数是（ A ） A．N B．2N-1 C．2N D．N-1 二、填空题 1② 若不考虑基数排序，则在排序过程中，主要进行的两种基本操作是关键字的____ 比较________和记录的___移动________。【北京邮电 2001】 2② 分别采用堆排序，快速排序，冒泡排序和归并排序，对初态为有序的表，则最省时间的是____冒泡_______算法，最费时间的是______快速______算法。【福州 1998】 3① 不受待排序初始序列的影响，时间复杂度为 O（n2）的排序算法是___直接选择 _________，在排序算法的最后一趟开始之前，所有元素都可能不在其最终位置上的排序算法是___直接插入________。【中国人民 2001】 三、判断题 （ F ）1② 当待排序的元素很大时，为了交换元素的位置，移动元素要占用较多的时间，这是影响时间复杂度的主要因素。【长沙铁道 1998】 （ F ）2② 内排序要求数据一定要以顺序方式存储。【南京理工 1997】 （ F ）3② 排序的稳定性是指排序算法中的比较次数保持不变，且算法能够终止。【南京航空航天 1996】 （ F ）4② 在执行某个排序算法过程中，出现了排序码朝着最终排序序列位置相反方向移动，则该算法是不稳定的。【上海交通 1998】 （ F ）5② 快速排序的速度在所有排序方法中为最快，而且所需附加空间也最少。 （ F ）6② 冒泡排序和快速排序都是基于交换两个逆序元素的排序方法， 冒泡排序算法的最坏时间复杂性是 O（n2），而快速排序算法的最坏时间复杂性是 O（nlog2 n）， 所以快速排序比冒泡排序算法效率更高。【上海海运 1997】 （ F ）7② 在任何情况下，归并排序都比简单插入排序快。【北京邮电 2000】 （ F ）8② 快速排序总比简单排序快。【东南 2001】 四、简答题 1① 内部排序（名词解释）。【燕山 1999】 2② 简述直接插入排序，简单选择排序，2-路归并排序的基本思想以及在时间复杂度和排序稳定性上的差别。【西北工业 1999】 3③ 给出一组关键字 T={12，2，16，30，8，28，4，10，20，6，18}，写出用下列算法从小到大排序时第一趟结束时的序列； （1） 希尔排序（第一趟排序的增量为 5） （2） 快速排序（选第一个记录为枢轴（分隔）） （3） 链式基数排序（基数为 10）【上海交通 1999】 4③ 给出一组关键字：29，18，25，47，58，12，51，10，分别写出按下列各种排序方法进行排序时的变化过程： （1） 归并排序：每归并一次书写一个次序。 （2） 快速排序：每划分一次书写一个次序。 （3） 堆排序：先建成一个堆，然后每从堆顶取下一个元素后，将堆调整一次。【南开 1998】 7.8 习题 7.8.1 知识点：顺序查找 一、选择题 1① 若查找每个记录的概率均等，则在具有 n 个记录的连续顺序文件中采用顺序查找法查找一个记录，其平 均查找长度 ASL 为（ C ）。 A． （n-1）/2 B. n/2 C. （n+1）/2 D. n 2① 对 N 个元素的表做顺序查找时，若查找每个元素的概率相同，则平均查找长度为 （ A ） 。 A．（N+1）/2 B. N/2 C. N D. [（1+N）*N ]/2 3② 顺序查找法适用于查找顺序存储或链式存储的线性表，平均比较次数为（ D ），二分法查找只适用于查找顺序存储的有序表，平均比较次数为（ C ）。 在此假定 N 为线性表中结点数，且每次查找都是成功的。 A.N+1 D.N/2 B. 2log2 N E. N Nlog2 C. log2 N F. N2 4③ 对大小均为 n 的有序表和无序表分别进行顺序查找，在等概率查找的情况下，对于 查找失败，它们的平均查找长度是（ B ），对于查找成功，他们的平均查找长度是（ A ） A. 相同的 B.不同的二、填空题 1② 顺序查找n个元素的顺序表，若查找成功，则比较关键字的次数最多为 n 次； 当使用监视哨时，若查找失败，则比较关键字的次数为 n+1 。【华中理工 2000】 三、判断题 （ F ）1① 有 n 个数存放在一维数组 A[1..n]中，在进行顺序查找时，这 n 个数的排列有序或无序其平均查找长度不同。 （ T ）2② 顺序查找法适用于存储结构为顺序或链接存储的线性表。【山东 2001】 四、简答题 1① 在查找和排序算法中，监视哨的作用是什么？ 2② 设有 n 个值不同的元素存于顺序结构中，试问：你能否用比（2n-3）少的比较次数选出这 n 个元素中的最大值和最小值？若能，请说明是如何实现的；在最坏情况下，至少要进行多少次比较。 7.8.2 知识点：折半查找 选择题 1① 采用折半查找方法查找长度为 n 的线性表时，每个元素的平均查找时间复杂度为（ D ） A.O（n2） A. 3.1 A. O（n2） B.O（n nlog2 ） B. 4 C.O（n） D.O（log2n） D. 5 2③ 具有12个关键字的有序表，折半查找的平均查找长度（ A ） C. 2.5 3② 折半查找的时间复杂性为（ D ） B. O（n） C. O（n nlog2 ） D. ） O（log2n） 4② 当采用分块查找时，数据的组织方式为 （ B A．数据分成若干块，每块内数据有序 B．数据分成若干块，每块内数据不必有序，但块间必须有序，每块内最大（或最小）的数据组成索引块 C. 数据分成若干块，每块内数据有序，每块内最大（或最小）的数据组成索引块 D. 数据分成若干块，每块（除最后一块外）中数据个数需相同 5① 适用于折半查找的表的存储方式及元素排列要求为（ D ） 【南京理工1997】 A．链接方式存储，元素无序 B．链接方式存储，元素有序 C．顺序方式存储，元素无序 D．顺序方式存储，元素有序 6① 用二分（对半）查找表的元素的速度比用顺序法（ D ） 【南京理工 1998】 A． 必然快 B. 必然慢 C. 相等 D. 不能确定 二、填空题 1① 假设在有序线性表 A[1..20]上进行折半查找，则比较一次查找成功的结点数为 1 ，则比较两次查找成功的结点数为 2 ，则比较三次查找成功的结点数为 4 ，则比较四次查找成功的结点数为 8 ，则比较五次查找成功的结点数为__5___，平均查找长度为 3.7 。 2② 在 n 个记录的有序顺序表中进行折半查找，最大比较次数是___log2n +1______。 3② 假定查找有序表 A[1..12]中每个元素的概率相等，则进行折半查找时的平均查找长度为___3.1_______。 4③ 分块检索中，若索引表和各块内均用顺序查找，则有 900 个元素的线性表分成____30______块最好：若分成 25 块，其平均查找长度为___（m+n/m）/2 + 1______。 8② 对于长度为 255 的表，采用分块查找，每块的最佳长度为____255 的平方根______。 9④ 在有序表 A[1..20]中，按折半查找方法进行查找，查找长度为 5 的元素个数是 ____5___。【合肥工业1999】 10③ 在有序表 A[1..12]中，采用折半查找算法查等于 A[12]的元素，所比较的元素下标依次为___6,9,11,12_______。【中国人民 2001】 11③ 在顺序表{8，11，15，19，25，26，30，33，42，48，50}中，用折半查找关键码值 20，需做的关键码比较次数为__4__。【北方交通 2001】 12③ 已知 N 元整型数组 a 存放 N 个学生的成绩，已按由大到小排序，以下算法是用折半查找方法统计成绩大于或等于 X 分的学生人数，请填空使之完善。 #define N /*学生人数*/ int uprx（int a[N]，int x ） /*函数返回大于等于 X 分的学生人数*/ { int head=1，mid，rear=N; do { mid=（head+rear）/2; if（x<=a[mid]）（1） head=mid+1 else （2）rear=mid-1 ; }while（（3）head<=rear ）; if （a[head] （ F ）1② 查找相同结点的效率折半查找总比顺序查找高。 （ F ）2② 用向量和单链表表示的有序表均可使用折半查找方法来提高查找速度。【中科院软件所 1997】 （ T ）3② 在索引顺序表中，实现分块查找，在等概率查找情况下，其平均查找长度不仅与表中元素个数有关，而且与每块中元素个数有关。【上海交通 1998】 四、简答题 1② 折半查找适不适合链表结构的序列，为什么？用折半查找的查找速度必然比线性查找的速度快，这种说法对吗？ 3③ 假定对有序表：{3，4，5，7，24，30，42，54，63，72，87，95}进行折半查找，试回答下列问题： （1）画出描述折半查找过程的判定树； （2）若查找元素 54，需依次与哪些元素比较？ （3）若查找元素 90，需依次与哪些元素比较？ （4）假定每个元素的查找概率相等，求查找成功时的平均查找长度。 五、算法题 1④ 试将折半查找的算法改写成递归算法。 7.8.3 知识点：二叉排序树 一、选择题 1③ 二叉查找树的查找效率与二叉树的（ （1）BC ）有关， 在 （ （2）C ）时其查找效率最低。 （1） A. 高度 B. 结点的多少 C. 树型 D. 结点的位置 C. 呈单枝树 D. 结点太复杂。 （2） A. 结点太多 B. 完全二叉树 2③ 分别以下列序列构造二叉排序树，与用其它三个序列所构造的结果不同的是（ C ） 。【合肥工业2000】 A．{100，80， 90， 60， 120，110，130} B.{100，120，110，130，80， 60， 90} C.{100，60， 80， 90， 120，110，130} D. {100，80， 60， 90， 120，130，110} 二、填空题 1① 已知二叉排序树的左右子树均不为空， 则__左子树__上所有结点的值均小于它的根结点值，__右子树_____上所有结点的值均大于它的根结点的值。 2② 如果按关键码值递增的顺序依次将关键码值插入到二叉排序树中，则对这样的二叉排序树检索时，平均比较次数是_（n+1）/2______。 【山东 1999】 三、判断题 （ F ）1② 在查找树（二叉树排序树）中插入一个新结点，总是插入到叶结点下面。 （ F ）2② 对一棵二叉排序树按前序方法遍历得出的结点序列是从小到大的序列。 （ F ）3② 二叉树中除叶结点外，任一结点 X，其左子树根结点的值小于该结点（X）的值；其右子树根结点的 值≥该结点（X）的值，则此二叉树一定是二叉排序树。 （ T ）4② N 个结点的二叉排序树有多种，其中树高最小的二叉排序树是最佳的。【上海交通 1998】 （ F ）5③ 在任意一棵非空二叉排序树中，删除某结点后又将其插入，则所得二排序叉树与原二排序叉树相同。【中科院软件所 1997】 （ F ）6② 虽然信息项序列的顺序不一样，但依次生成的二叉排序树却是一样的。【长沙铁道 1998】 （ T ）7② 二叉排序树删除一个结点后，仍是二叉排序树。【青岛 2000】 四、简答题 1③ 假定一个线性表为（38，52，25，74，68，16，30，54，90，72），画出按线性表中元素的次序生成的一棵二 叉排序树，求出其平均查找长度。 2③ 有一组数据：27、56、19、40、9、31、20，构建一棵二叉排序树， 在此二叉查找树中，（1）使用二叉树查 找法查找节点 31，按顺序写出查找过程中访问的结点；（2）使用前序遍历查找算法查找节点 45，按顺序写 出查找过程中访问的结点。 3③ 有一棵二叉排序树如下图，在二叉树中分别删除节点 11、9、5、19，使得删除后的二叉树仍保持二叉查找树 的特性，分别画出删除相应结点后的二叉树。 9 5 13 7 12 6 11 19 21 15 20 16 22 14 7.100 3 图 题图 五、算法题 1④ 假设 root 是一棵给定的非空查找树，对于下面给出的子程序，当执行注释中给出的调用语句时，就可以实现如下的操作：在非空查找树 root 中查找值为 k 的结点；若值为 k 的结点在树中，且是一个叶子结点，则删除此叶子结点，同时置 success 为―真‖。若值为 k 的结点不在树中，或者虽然在树中，但不是叶子结点，则不进行删除，仅置 success 为―假‖。应注意到非空查找树只包含一个结点情况，此时树中的唯一结点，既是根结点，也是叶子结点。 #include struct node { int key; struct node *left， *right; } node; node *root; int k，success; void del_leaf（node **t， int k， int *sn） { node *p， *pf=NULL; p=*t; *sn=0; while（（1）p!=NULL &&!*sn） if （k==p->key） *sn =1; else { （2）pf=p ; if （k { if （（3）pf!=NULL ） if （pf->left ==p ） pf ->left=null; else pf->right=null; else （4） free（p）; } else *sn=0; } ; /*call form :del_leaf（ &root， k， &success）;*/ （1） 为_____________________________; （2） 为_____________________________; （3） 为_____________________________; （4） 为_____________________________; 2④ 在二叉查找树中查找符合条件的数据。如查找成功返回数据的下标，否则将其插入，并将插入后的下标位置返回。要求：用数组表示法建立二叉查找树。 int search_binary_tree（int btree[]， int length，int key） /*已知二叉查找树已存储在 btree 数组中，数组长度为 length，在此二叉查找树中查找是否有数据 key 存在*/ 3④ 试写一个判别给定二叉树是否为二叉排序树的算法，设此二叉树以二叉链表作为存储结构，且树中结点的关键字均不同。 7.8.4 知识点：平衡二叉树 一、 选择题 1③ 在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡结点为 A，并已知 A 的左孩子的平衡因子为 0 右孩子的平衡因子为1，则应作（）型调整以使其平衡。【合肥工业2001】 A. LL B. LR 填空题 C. RL D. RR 二、 1① 在一棵有 N 个结点的非平衡二叉树中进行查找，平均时间复杂度的上限（即最坏情况平均时间复杂度）为____O（n）____ 。 2① 高度为 8 的平衡二叉树的结点数至少有____54______个。 N(0)＝0，N(1)＝1 N(n)=N(n-1)+N(n-2)+1 得 N（8）＝54 3 ③平 衡 二 叉 树 又 称 ___AVL 树 ____ ， 其 定 义 是 _ 见 书__________。【北京轻工业 2000】 4② 平衡因子的定义是_结点左子树深度减去右子树深度的值_________。【北京轻工业 2000】 三、判断题 （F）1③ 设 T 为一棵平衡树，在其中插入一个结点 n，然后立即删除该结点后得到T1，则 T 与 T1 必定相同。 （T）2③ 将线性表中的结点信息组织成平衡的二叉树，其优点之一是总能保证任意检索长度均为log2n量级 （n 为线形表中的结点数目）。 （ F ）3② 在平衡二叉树中，向某个平衡因子不为零的结点的树中插入一新结点，必引起平衡旋转。 （ T ）4① 最佳二叉树是AVL树（平衡二叉树）。【北京 1994 】 （ T ）5② 完全二叉树肯定是平衡二叉树。【南京航空航天 1996】 四、简答题 1③ 已知长度为 11 的表（xal，wan，wil，zol，yo，xul，yum，wen，wim，zi，yon），按表中元素顺序依次插入一棵初始为空的平衡二叉排序树，画出插入完成后的平衡二叉排序树，并求其在等概率的情况下查找成功的平均查找长度。 2③ 如图所示是一棵正在进行插入运算的 AVL 树，关键码 70 的插入使它失去平衡，按照 AVL 树的插入方法，需要对它的结构进行调整以恢复平衡。请画出调整后的 AVL 树。 t -- 100 60 + 40 · - 120 ·- -- 80 - 70 · 7.101 2 图 题图 3④ 试画出从空树开始，由字符序列{t，d，e，s，u，g，b，j，a，k，r，i}构成的二叉平衡树，并为每一次 的平衡处理指明旋转类型。【清华 1994】 7.8.5 知识点：B-树和 B+树 一、选择题 1① 下列关于m阶B-树的说法错误的是（ D A．根结点至多有 m 棵子树 B．所有叶子都在同一层次上 C. 非叶结点至少有 m/2 （m 为偶数）或 m/2+1（m 为奇数）棵子树 D. 根结点中的数据是有序的 2① 下面关于m阶B树说法正确的是（ B ）。 ） 。 （1）每个结点至少有两棵非空子树；（2）树中每个结点至多有 m—1 个关键字; （3）所有叶子在同一层上; （4）当插入一个数据项引起 B 树结点分裂后，树长高一层。 A．（1）（2）（3） B. （2）（3） C. （2）（3）（4） D. （3） 3② 下面关于B和B+树的叙述中，不正确的是（ C ） 。 A. B 树和 B+树都是平衡的多叉树 B. B 树和 B+树都可用于文件的索引结构 B 树和 B+树都能有效地支持随机检索 C. B 树和 B+树都能有效地支持顺序检索 D. 4① m阶B-树是一棵（ B ） 。【北京邮电 2000】 A. m 叉排序树 B. m 叉平衡排序树 D. m+1 叉平衡排序树 C. m-1 叉平衡排序树 5③ 在一棵m阶的B+树中， 每个非叶结点的儿子数S 应满足 （ A ）。【武汉交通科技 1996】 A. ?（m+1）/2? ≤S≤m C. 1≤S≤ ?（m+1）/2? B. ?m/2? ≤S≤m D. 1≤S≤ ?m/2? 二、填空题 1② 高度为 4 的 3 阶 b-树中，最多有____80______个关键字。 2② 在一棵 m 阶 B-树中，若在某结点中插入一个新关键字而引起该结点分裂，则此结点中原有的关键字的个数 是___m-1_______;若在某结点中删除一个关键字而导致结点合并，则该结点中原有的关键字的个数是____m/2 向上取整 再减 1______。 3② 具有 N 个关键字的 B 树的查找路径长度不会大于___见书_______。 4② 高度为 5（除叶子层之外）的三阶 B-树至少有_____31_____个结点。【武汉2000】 5④ 127 阶 B-树中每个结点最多有__126___个关键字；除根结点外所有非终端结点至少有__64___棵子树；65 阶 B+树中除根结点外所有结点至少有___33__个关键字；最多有__65___棵子树。【北方交通 1999】 三、判断题 （ T ）1② B-树中所有结点的平衡因子都为零。 （ T ）2③ 在 9 阶 B-树中，除叶子以外的任意结点的分支数介于 5 和 9 之间。 （ T ）3② B-树的插入算法中，通过结点的向上―分裂‖，代替了专门的平衡调整。【华南理工 2001】 （ F ）4② B+树既能索引查找也能顺序查找。【青岛 2002】 四、简答题 1② 在 B-树和 B+树中查找关键字时，有什么不同？ 2③ 设依以下次序给出关键字：34，16，19，21，5，49，24，62，3，17，45，8，构造 3 阶 B-树。要求从空树开始，每插入一个关键字，画出一个树形。 3③ 对下面的 3 阶 B-树，依次执行下列操作，画出各步操作的结果。【合肥工业1999】 （1）插入 90 （2） 插入 25 （3） 插入 45 （4）删除 60 （5）删除 80 50 30 8 20 35 40 60 80 100 7.102 3 图 题图 4④ 设有关键码序列 10，20，35，40，44，51，65，70，85，91，93，95。试按照最大关键码复写原则绘出相应的 2 阶 B+ 树。【山东工业 1996】