数据结构练习题及答案

数据结构练习题及答案 第1章 绪论 一、 判断题 1. 数据的逻辑结构与数据元素本身的内容和形式无关。

（√）
2. 一个数据结构是由一个逻辑结构和这个逻辑结构上的一个基本运算集构成的整体。

（√）
3. 数据元素是数据的最小单位。

（×）
4. 数据的逻辑结构和数据的存储结构是相同的。

（×）
5. 程序和算法原则上没有区别，所以在讨论数据结构时可以通用。

（×）
6. 从逻辑关系上讲，数据结构主要分为线性结构和非线性结构两类。

（√）
7. 数据的存储结构是数据的逻辑结构的存储映象。

（√）
8. 数据的物理结构是指数据在计算机内实际的存储形式。

（√）
9. 数据的逻辑结构是依赖于计算机的。

（×）
10. 算法是对解题方法和步骤的描述。

（√）
二、填空题 1. 数据有逻辑结构和 存储结构 两种结构。

2. 数据逻辑结构除了集合以外，还包括线性结构、树形结构和图形结构 。

3. 数据结构按逻辑结构可分为两大类，它们是线性结构和非线性结构 。

4. 树形结构 和图形结构 合称为非线性结构。

5. 在树形结构中，除了树根结点以外，其余每个结点只有1个前驱结点。

6. 在图形结构中，每个结点的前驱结点数和后继结点数可以任意多个 。

7. 数据的存储结构又叫物理结构 。

8. 数据的存储结构形式包括顺序存储、链式存储、索引存储和散列存储 。

9. 线性结构中的元素之间存在一对一 的关系。

10. 树形结构中的元素之间存在一对多 的关系。

11. 图形结构的元素之间存在多对多 的关系。

12. 数据结构主要研究数据的逻辑结构、存储结构和算法（或运算）
3个方面的内容。

13. 数据结构被定义为（D，R），其中D是数据的有限集合，R是D上的关系 有限集合。

14. 算法是一个有穷指令 的集合。

15. 算法效率的度量可以分为事先估算法和事后统计法 。

16. 一个算法的时间复杂度是算法 输入规模 的函数。

17. 算法的空间复杂度是指该算法所耗费的存储空间 ，它是该算法求解问题规模的n的函数。

18. 若一个算法中的语句频度之和为T(n)=6n+3nlog2n,则算法的时间复杂度为O（ nlog2n）
。

19. 若一个算法的语句频度之和为T(n)=3n+nlog2+n2,则算法的时间复杂度为O（n2）
。

20. 数据结构是一门研究非数值计算的程序问题中计算机的操作对象，以及它们之间的关系和运算的学科。

三、选择题 1. 数据结构通常是研究数据的（A）及它们之间的相互关系。

A．存储结构和逻辑结构 B．存储和抽象 C．联系和抽象 D．联系与逻辑 2. 在逻辑上可以把数据结构分成（C）。

A．动态结构和静态结构 B．紧凑结构和非紧凑结构 C．线性结构和非线性结构 D．内部结构和外部结构。

3. 数据在计算机存储内表示时，物理地址和逻辑地址相同并且是连续的，称之为（C）。

A．存储结构 B．逻辑结构 C．顺序存储结构 D．链式存储结构 4. 非线性结构中的每个结点（D）。

A．无直接前驱结点． B．无直接后继结点． C．只有一个直接前驱结点和一个直接后继结点D．可能有多个直接前驱结点和多个直接后继结点 5. 链式存储结构所占存储空间（A）。

A．分两部分，一部分存放结点的值，另一个部分存放表示结点间关系的指针。

B．只有一部分，存放结点的值。

C．只有一部分，存储表示结点间关系的指针。

D．分两部分，一部分存放结点的值，另一部分存放结点所占单元素 6. 算法的计算量大小称为算法的（C）。

A．现实性 B．难度 C．时间复杂性 D．效率 7. 数据的基本单位（B）。

A．数据结构 B．数据元素 C．数据项 D．文件 8. 每个结点只含有一个数据元素，所有存储结点相继存放在一个连续的存储空间里，这种存储结构称为（A）结构。

A．顺序结构 B．链式结构 C．索引结构 D．散列结构 9. 每一个存储结点不仅含有一个数据元素，还包含一组指针，该存储方式是（B）。

A．顺序 B．链式 C．索引 D．散列 10. 以下任何两个结点之间都没有逻辑关系的是（D）。

A．图形结构 B．线性结构 C．树形结构 D．集合 11. 在数据结构中，与所使用的计算机无关的是（C）。

A．物理结构 B．存储结构 C．逻辑结构 D．逻辑和存储结构 12. 下列4种基本逻辑结构中，数据元素之间关系最弱的是（A）。

A．集合 B．线性结构 C．树形结构 D．图形结构 13. 与数据元素本身的形式、内容、相对位置、个数无关的是数据的（A）。

A．逻辑结构 B．存储结构 C．逻辑实现 D．存储实现 14. 每一个存储结点只含有一个数据元素，存储结点存放在连续的存储空间，另外有一组指明结点存储位置的表，该存储方式是（C）存储方式。

A．顺序 B．链式 C．索引 D．散列 15. 算法能正确的实现预定功能的特性称为算法的（A）。

A．正确性 B．易读性 C．健壮性 D．高效性 16. 算法在发生非法操作时可以作出相应处理的特性称为算法的（C）。

A．正确性 B．易读性 C．健壮性 D．高效性 17. 下列时间复杂度中最坏的是（D）。

A．O（1）
B.O（n）
C.O( log2n) D.O(n2) 18. 下列算法的时间复杂度是（D）。

for(i=0;i<n;i++) for(j=o;i<n;j++) c[i][j]=i+j; A．O（1）
B.O（n）
C.( log2n) D.O(n2) 19. 算法分析的两个主要方面是（A）。

A.空间复杂性和时间复杂性 B.正确性和简明性 C.可读性和文档性 D.数据复杂性和程序复杂性 20. 计算机算法必须具备输入、输出和（C）。

A.计算方法 B.排序方法 C.解决问题的有限运算步骤D.程序设计方法 第2章 线性表 一、判断题 1. 线性表的链式存储结构优于顺序存储。

（×）
2. 链表的每个结点都恰好包含一个指针域。

（×）
3. 在线性表的链式存储结构中，逻辑上相邻的两个元素在物理位置上并不一定紧邻。

（√）
4. 顺序存储方式的优点是存储密度大，插入、删除效率高。

（×）
5. 线性链表的删除算法简单，因为当删除链中某个结点后，计算机会自动地将后续的各个单元向前移动。

（×）
6. 顺序表的每个结点只能是一个简单类型，而链表的每个结点可以是一个复杂类型。

（×）
7. 线性表链式存储的特点是可以用一组任意的存储单元存储表中的数据元素。

（√）
8. 线性表采用顺序存储，必须占用一片连续的存储单元。

（√）
9. 顺序表结构适宜进行顺序存取，而链表适宜进行随机存取。

（×）
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；
p->next->prior=p->prior 20. 在如图所示的链表中，若在指针P所在的结点之后插入数据域值为a和b的两个结点，则可用语句S->next->next=p->next和P-> next=S；
来实现该操作。

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

p a 10 b 20 c ∧ A．循环链表 B．单向链表 C．双向循环链表 D．双向链表 3. 单向链表的存储密度（ C ）。

A.大于1 B.等于1 C.小于1 D.不能确定 4. 已知一个顺序存储的线性表，设每个结点占m个存储单元，若第一个结点的地址为B，则第i个结点的地址为（ A ）。

A.B+(i-1)×m B.B+i×m C.B-i×m D.B+(i+1)×m 5. 在有n个结点的顺序表上做插入、删除结点运算的时间复杂度为（ B ）。

A．O（1）
B.O（n）
C. O(n2) D.O( log2n) 6. 设front、rear分别为循环双向链表结点的左指针和右指针，则指针P所指的元素是双循环链表L的尾元素的条件是（ D ）。

A.P= =L B.P->front= =L C.P= =NULL D.P->rear= =L 7. 两个指针P和Q，分别指向单向链表的两个元素，P所指元素是Q所指元素前驱的条件是（ B ）
A．P->next= =Q->next B.P->next= =Q C.Q->next= =P D.P==Q 8. 用链表存储的线性表，其优点是（ C ）。

A．便于随机存取 B．花费的存储空间比顺序表少 C．便于插入和删除 D．数据元素的物理顺序与逻辑顺序相同 9. 在单链表中，增加头结点的目的是（ C ）。

A．使单链表至少有一个结点 B．标志表中首结点的位置 C．方便运算的实现 D．说明该单链表是线性表的链式存储结构 10. 下面关于线性表的叙述中，错误的是（ D ）关系。

A．顺序表必须占一片地址连续的存储单元B．顺序表可以随机存取任一元素 C．链表不必占用一片地址连续的存储单元D．链表可以随机存取任一元素 11. L是线性表，已知LengthList(L)的值是5，经DelList(L，2)运算后，LengthList(L)的值是（ C ）。

A．2 B．3 C．4 D．5 12. 单向链表的示意图如下：
L A B C D ∧ P Q R 指向链表Q结点的前驱的指针是（ B ）。

A．L B．P C．Q D．R 13. 设p为指向单循环链表上某结点的指针，则*p的直接前驱（ C ）。

A．找不到 B．查找时间复杂度为O（1）
C．查找时间复杂度为O（n）D．查找结点的次数约为n 14. 等概率情况下，在有n个结点的顺序表上做插入结点运算，需平均移动结点的数目为（ 8 ）。

A．n B.(n-1)/2 C.n/2 D.(n+1)/2 15. 在下列链表中不能从当前结点出发访问到其余各结点的是（ C ）。

A.双向链表 B.单循环链表 C.单向链表 D.双向循环链表 16. 在顺序表中，只要知道（ D ），就可以求出任一结点的存储地址。

A.基地址 B.结点大小 C.向量大小 D.基地址和结点大小 17. 在双向链表中做插入运算的时间复杂度为（ A ）。

A．O（1）
B.O（n）
C. O(n2) D.O( log2n) 18. 链表不具备的特点是（ A ）。

A．随机访问 B.不必事先估计存储空间C. 插入删除时不需要移动元素 D.所需空间与线性表成正比 19. 以下关于线性表的论述，不正确的为（ C ）。

A.线性表中的元素可以是数字、字符、记录等不同类型B.线性顺序表中包含的元素个数不是任意的 C.线性表中的每个结点都有且仅有一个直接前驱和一个直接后继 D.存在这样的线性表，即表中没有任何结点 20. 在（ B ）的运算中，使用顺序表比链表好。

A.插入 B.根据序号查找 C.删除 D.根据元素查找 第3章 栈 一、 判断题 1. 栈是运算受限制的线性表。

（√）
2. 在栈空的情况下，不能作出栈操作，否则产生下溢。

（√）
3. 栈一定是顺序存储的线性结构。

（×）
4. 栈的特点是“后进先出”。

（√）
5. 空栈就是所有元素都为0的栈。

（×）
6. 在C（或C++）语言中设顺序栈的长度为MAXLEN，则top=MAXLEN时表示栈满。

（×）
7. 链栈与顺序栈相比，其特点之一是通常不会出现栈满的情况。

（√）
8. 一个栈的输入序列为：A，B，C，D，可以得到输出序列：C，A，B，D。

（×）
9. 递归定义就是循环定义。

（×）
10. 将十进制数转换为二进制数是栈的典型应用之一。

（√）
二、填空题 1. 在栈结构中，允许插入、删除的一端称为 栈顶 。

2. 在顺序栈中，当栈顶指针top=-1时，表示 栈空 。

3. 在有n个元素的栈中，进栈操作时间复杂度为 O（1）
。

4. 在栈中，出栈操作时间复杂度为 O（1）
。

5. 已知表达式，求它的后缀表达式是 栈 的典型应用。

6. 在一个链栈中，若栈顶指针等于NULL，则表示 栈空 。

7. 向一个栈顶指针为top的链栈插入一个新结点*p时，应执行p->next=top;top=p；
操作。

8. 顺序栈S存储在数组S->data[0…MAXLEN-1]中，进栈操作时要执行的语句有：S->top++。(或S->top+1) S->data[S->top]=x 9. 链栈LS，指向栈顶元素的指针是LS->next。

10. 从一个栈删除元素时，首先取出 栈顶元素 ，然后再移动栈顶指针。

11. 由于链栈的操作只在链表的头部进行，所以没有必要设置 头 结点。

12. 已知顺序栈S，在对S进栈操作之前首先要判断 栈是否满 。

13. 已知顺序栈S，在对S出栈操作之前首先要判断 栈是否空 。

14. 若内在空间充足， 链 栈可以不定义栈满运算。

15. 链栈LS为空的条件是 LS->next=NULL 。

16. 链栈LS的栈顶元素是链表的 首 元素。

17. 同一栈的各元素的类型 相同 。

18. 若进栈的次序是A、B、C、D、E，执行3次出栈操作以后，栈顶元素为 B 。

19. A+B/C-D*E的后缀表达式是 ABC/+DE*- 。

20. 4个元素A、B、C、D顺序进S栈，执行两次Pop(S,x)运算后，x的值是 C 。

三、选择题 1. 插入和删除操作只能在一端进行的线性表，称为（ C ）。

A．队列 B．循环队列 C．栈 D．循环栈 2. 设有编号为1，2。3，4的4辆列车，顺序进入一个栈结构的站台，下列不可能的出站顺序为（ D）。

A．1234 B．1243 C．1324 D．1423 3. 如果以链表作为栈的存储结构，则出栈操作时（ B ）。

A．必须判别栈是否满 B．必须判别栈是否为空 C．必须判别栈元素类型 D．栈可不做任何判别 4. 元素A、B、C、D依次进栈以后，栈顶元素是（ D ）
A．A B．B C．C D．D 5. 顺序栈存储空间的实现使用（ B ）存储元素。

A．链表 B．数组 C．循环链表 D．变量 6. 在C（或C++）语言中，一个顺序栈一旦被声明，其占用空间的大小（ A ）。

A．已固定 B．不固定 C．可以改变 D．动态变化 7. 带头结点的链栈LS的示意图如下，栈顶元素是（ A ）。

LS H A B C D ∧ A．A B．B C．C D．D 8. 链栈与顺序栈相比，有一个比较明显的优点是（ B ）。

A. 插入操作更加方便 B.通常不会出现栈满的情况 C.不会出现栈空的情况 D.删除操作更加方便 9. 从一个栈顶指针为top的链栈中删除一个结点时，用x保存被删除的结点，应执行下列（d ）命令。

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

A.HS->next=S B.S->next=HS->next;HS->next=S; C.S->next=HS->next;HS=S; D.S->next=HS=HS->next 11. 4元素按A、B、C、D顺序进S栈，执行两次Pop(S，x)运算后，栈顶元素的值是（ B ）。

A．A B．B C．C D．D 12. 元素A、B、C、D依次进栈以后，栈底元素是（ A ）。

A．A B．B C．C D．D 13. 经过下列栈的运算后，再执行ReadTop(s)的值是（ A ）。

InitStack(s);Push(s，a); Push(s，b);Pob(s); A. a B.b C.1 D.0 14. 经过下列栈的运算后，x的值是（ B ）。

InitStack(s)（初始化栈）; Push(s，a); Push(s，b); ReadTop(s) ；
Pob(s，x); A. a B.b C.1 D.0 15. 经过下列栈的运算后，x的值是（ B ）。

InitStack(s)（初始化栈）; Push(s,a); Pob(s，x); Push(s,b); Pob(s，x); A.a B.b C.1 D.0 16. 经过下列栈的运算后,SEmpty(s)的值是（ C ）。

InitStack(s)（初始化栈）; Push(s,a); Push(s,b); Pob(s，x); Pob(s，x); A.a B.b C.1 D.0 17. 向顺序栈中输入元素时（ B ）。

A．先存入元素，后移动栈顶指针 B．先移动栈顶指针，后存入元素 C．谁先谁后无关紧要 D．同时进行 18. 初始化一个空间大小为5的顺序栈S后，S->top的值是（ B ）。

A．0 B．-1 C．不再改变 D．动态变化 19. 设有一个入栈的次序A、B、C、D、E，则栈不可能的输出序列是（ C ）。

A．EDCBA B．DECBA C．DCEAB D．ABCDE 20. 设有一个顺序栈S，元素A、B、C、D、E、F依次进栈，如果6个元素出栈的顺序是B、D、C、F、E、A，则栈的容量至少应是（ A ）。

A．3 B．4 C．5 D．6 第4章 队列 一、判断题 1. 队列是限制在两端进行操作的线性表。

（√）
2. 判断顺序队列为空的标准是头指针和尾指针都指向同一个结点。

（√）
3. 在链队列上做出队操作时，会改变front指针的值。

（×）
4. 在循环队列中，若尾指针rear大于头指针front，其元素个数为rear-front。

（√）
5. 在单向循环链表中，若头指针为h，那么p所指结点为尾结点的条件是p=h。

（×）
6. 链队列在一定范围内不会出现队满的情况。

（√）
7. 在循环链队列中无溢出现象。

（×）
8. 栈和队列都是顺序存储的线性结构。

（×）
9. 在队列中允许删除的一端称为队尾。

（×）
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) 。

13. 在一个链队列中，若队首指针与队尾指针的值相同，则表示该队列为 空 。

14. 设循环队列的头指针front指向队首元素，尾指针rear指向队尾元素后的一个空闲元素，队列的最大空间为MAXLEN，则队满标志为 front= =(rear+1)%MAXLEN 。

15. 在一个链队列中，若队首指针为front，队尾指针为rear，则判断队列只有一个结点的条件为front= =rear或front!。

16. 向一个循环队列中插入元素时，首先要判断 队尾指针 ，然后再向指针所指的位置写入新的数据。

17. 读队首元素的操作 不改变或不影响队列元素的个数。

18. 设循环队列的容量为40（序号0～39），现经过一系列的入队和出队的运算后，front=11，rear=19，则循环队列中还有 8 个元素。

19. 队列Q，经过下列运算：InitQueue(Q)(初始化队列)；
InQueue(Q,a)；
InQueue(Q,b)；
OutQueue(Q,x)；
ReadFront(Q,x)；
QEmpty(Q)；
后的值是 8 。

20. 队列Q经过InitQueue(Q)(初始化队列)；
InQueue(Q,a)；
InQueue(Q,b)；
ReadFront(Q,x)后，x的值是 a 。

三、选择题 1. 队列是限定在（D）进行操作的线性表。

A．中间者 B.队首 C.队尾 D.端点 2. 队列中的元素个数是（B）。

A．不变的 B.可变的 C.任意的 D.0 3. 同一队列内的各元素的类型（A）。

A.必须一致 B.不能一致 C.可以不一致 D.不限制 4. 队列是一个（C）线性表结构。

A.不加限制的 B.推广了的 C.加了限制的 D.非 5. 当利用大小为n的数组顺序存储一个队列时，该队列的最后一个元素的下标为（B）。

A.n-2 B.n-1 C.n D.n+1 6. 一个循环队列一旦说明，其占用空间的大小（A）。

A.已固定 B.可以变动 C.不能固定 D.动态变化 7. 循环队列占用的空间（A）。

A.必须连续 B.不必连续 C.不能连续 D.可以不连续 8. 存放循环队列元素的数组data有10个元素，则data数组的下标范围是（B）。

A.0～10 B.0～9 C.1～9 D.1～10 9. 若进队的序列为A、B、C、D，则出队的序列是（C）。

A.B、C、D、A B.A、C、B、D C.A、B、C、D D.C、B、D、A 10. 4个元素按A、B、C、D顺序连续进队Q，则队尾元素是（D）
A．A B．B C．C D．D 11. 4个元素按A、B、C、D顺序连续进队Q，执行一次QutQueue(Q)操作后，队头元素是（B）。

A.A B.B C.C D.D 12. 4个元素按A、B、C、D顺序连续进队Q，执行4次QutQueue(Q)操作后，再执行QEmpty(Q)；
后的值是（B）。

A.0 B.1 C.2 D.3 13. 队列Q，经过下列运算后，x的值是（B）。InitQueue(Q)(初始化队列)；
InQueue(Q,a)；
InQueue(Q,b)；
OutQueue(Q,x)；
ReadFront(Q,x)；

A.a B.b C.0 D.1 14. 循环队列SQ队满的条件是（B）。

A.SQ->rear= =SQ->front B.(SQ->rear+1)%MAXLEN= =SQ->front C.SQ->rear= =0 D.SQ->front= =0 15. 设链栈中结点的结构：data为数据域，next为指针域，且top是栈顶指针，若想在链栈的栈顶插入一个由指针s所指的结点，则应执行下列（A）操作。

A.s->next=top->next;top->next=s; B.top->next=s; C.s->next=top;top->next; D.s->next=top;top=s; 16. 带头结点的链队LQ示意图如下，链队列的队头元素是（A）。

LQ->front H A B C D ∧ LQ->rear A．A B．B C．C D．D 17. 带头结点的链队列LQ示意图如下，指向链队列的队头指针是（C）。

LQ->front H A B C D ∧ LQ->rear A.LQ->front B.LQ->rear C.LQ->front->next D.LQ->rear->next 18. 带头结点的链队列LQ示意图如下,在进行进队的运算时指针LQ->frnot(A). LQ->front H A B C D ∧ LQ->rear A.始终不改变 B.有时改变 C.进队时改变 D.出队时改变 19.队列Q，经过下列运算后，再执行QEmpty(Q)的值是（C）。

InitQueue(Q)(初始化队列)；
InQueue(Q,a)；
InQueue(Q,b)；
OutQueue(Q,x)；
ReadQueue(Q,x)；

A.a B.b C.0 D.1 20.若用一个大小为6数组来实现循环队列，且当前front和rear的值分别为3和0，当从队列中删除一个元素，再加入两个元素后，front和rear的值分别为（B）。

A.5和1 B.4和2 C.2和4 D.1和5 第5章 串 一、判断题 1. 串是n个字母的有限序列。

（×）
2. 串的数据元素是一个字符。

（√）
3. 串的长度是指串中不同字符的个数。

（×）
4. 如果两个串含有相同的字符，则说明它们相等。

（×）
5. 如果一个串中所有的字母均在另一个串中出现，则说明前者是后者的子串。

（×）
6. 串的堆分配存储是一种动态存储结构。

（√）
7. “DT”是“DATA”的子串。

（×）
8. 串中任意个字符组成的子序列称为该串的子串。

（×）
9. 子串的定位运算称为模式匹配。

（√）
10. 在链串中为了提高存储密度，应该增大结点的大小。

（√）
二、填空题 1. 由零个或多个字符组成的有限序列称为 字符串（或串）
。

2. 字符串按存储方式可以分为顺序存储、链接存储和 堆分配存储 。

3. 串的顺序存储结构简称为 顺序串 。

4. 串顺序存储非紧凑格式的缺点是 空间利用率低 。

5. 串顺序存储紧凑格式的缺点是对串的字符处理 效率低 。

6. 串链接存储的优点是插入、删除方便，缺点是 空间利用率 。

7. 在C或C++语言中，以字符 ＼0 表示串值的终结。

8. 空格串的长度等于 空格的个数 。

9. 在空串和空格串中，长度不为0的是 空格串 。

10. 两个串相等是指两个串长度相等，且对应位置的 字符都相同 。

11. 设“S=My Music”，则LenStr(s)= 8 。

12. 两个字符串分别为；
S1=”Today is”、S2=”30 July，2005”，ConcatStr(S1，S2)的结果是 Today is 30 July,2005 。

13. 求子串函数SubStr(“Today is 30 July，2005”，13，4)的结果是 July 。

14. 在串的运算中，EqualStr(aaa,aab)的返回值 <0 。

15. 在串的运算中，EqualStr(aaa,aaa)的返回值 0 。

16. 在子串的定位运算中，被匹配的主串称为目标串，子串称为 模式 。

17. 模式匹配成功的起始位置称为 有效位移 。

18. 设S=”abccdcdccbaa”，T=”cdcc”，则第 6 次匹配成功。

19. 设S=”c:/mydocument/text1.doc”，T=”mydont”，则字符定位的位置为 0 。

20. 若n为主串长度，m为子串长度，n>>m，则模式匹配算法最坏情况下的时间复杂度为 (n-m+1)*m 。

三、选择题 1. 串是和种特殊的线性表，其特殊体现在（B）。

A．可能顺序存储 B．数据元素是一个字符C．可以链接存储 D．数据元素可以是多个字符 2. 某串的长度小于一常数，则采用（B）存储方式最节省空间。

A．链式 B．顺序 C．堆结构 D．无法确定 3. 以下论述正确的是（C）。

A．空串与空格串是相同的B．”tel”是”Teleptone”的子串 C．空串是零个字符的串 D．空串的长度等于1 4. 以下论述正确的是（B）。

A．空串与空格串是相同的B．”ton”是”Teleptone”的子串 C．空格串是有空格的串 D．空串的长度等于1 5. 以下论断正确的是（A）。

A．全部由空格组成的串是空格串 B．”BEUIJING”是”BEI JING”的子串 C．”something”<”Something” D．”BIT”=”BITE” 6. 设有两个串S1和S2，则EqualStr（S1，S2）运算称作（D）。

A．串连接 B．模式匹配 C．求子串 D．串比较 7. 串的模式匹配是指（D）。

A．判断两个串是否相等 B．对两个串比较大小 C．找某字符在主串中第一次出现的位置D．找某子串在主串中第一次出现的第一个字符位置 8. 若字符串”ABCDEFG”采用链式存储，假设每个字符占用1个字节，每个指针占用2个字节。则该字符串的存储密度为（D）。

A．20% B．40% C．50% D．33.3% 9. 若字符串”ABCDEFG”采用链式存储，假设每个指针占用2个字节，若希望存储密度为50%，则每个结点应存储（A）个字符。

A.2 B.3 C.4 D.5 10. 设串S1=”IAM”，S2=”A SDUDENT”，则ConcatStr(S1，S2)=（B）。

A．”I AM” B.”I AM A SDUDENT” C.”IAMASDUDENT” D.”A SDUDENT” 11. 设S=””，则LenStr(S)=（A）。

A.0 B.1 C.2 D.3 12. 设目标串T=”AABBCCDDE”，模式P=”ABCDE”，则该模式匹配的有效位移为（A）。

A.0 B.1 C.2 D.3 13. 设目标串T=”AABBCCDDEEFF”，模式P=”CCD”，则该模式匹配的有效位移为（D）。

A.2 B.3 C.4 D.5 14. 设目标串T=”aabaababaabaa”，模式P=”abab”，模式匹配算法的外层循环进行了（D）次。

A.1 B.9 C.4 D.5 15. 模式匹配算法在最坏情况下的时间复杂是（D）。

A.O(m) B.O(n) C.O(m+n) D.O(m×n) 16. S=”morning”,执行求子串函数SubSur(S,2,2)后结果为（B）。

A. ”mo” B. ”or” C. ”in” D. ”ng” 17. S1=”good”，S2”morning”，执行串连接函数ConcatStr(S1，S2)后结果为（A）。

A. ”goodmorning” B. ”good morning” C. ”GOODMORNING” D. ”GOODMORNING” 18. S1=”good”, S2=”morning”执行函数SubSur(S2,4,LenStr(S1))后的结果为（B）。

A.”good” B.”ning” C.”go” D.”morn” 19. 设串S1=”ABCDEFG”，S2=”PQRST”，则ConcatStr（SubStr(S1，2，LenStr（S2）），SubStr(S1，LenStr（S2），2））的结果串为（D）。

A. BCDEF B.BCDEFG C.BCPQRST D.BCDEFEF 20. 若串S=”SOFTWARE”，其子串的数目最多是（C）。

A．35 B.36 C.37 D.38 第6章 多维数组和广义表 一、判断题 1. n维多维数可以视为n-1维数组元素组成的线性结构。

（√）
2. 稀疏矩阵中非零元素的个数远小于矩阵元素的总数。

（√）
3. 上三角矩阵主对角线以上（不包括主对角线的元素），均为常数C。

（×）
4. 数组元素可以由若干数据项组成。

（√）
5. 数组的三元组表存储是对稀疏矩阵的压缩存储。

（√）
6. 任何矩阵都可以进行压缩存储。

（×）
7. 广义表是线性表的推广，所以广义表也是线性表。

（×）
8. 广义表LS=（a0，a1，……an-1），则an-1是其表尾。

（×）
9. 广义表（（a，b）a，b）的表头和表尾是相等的。

（√）
10. 一个广义表的表尾总是一个广义表。

（√）
二、填空题 1. 多维数组的顺序存储方式有按行优先顺序存储和 按优先顺序存储 两种。

2. 在多维数组中，数据元素的存放地址可以直接通过地址计算公式算出，所以多维数组是一 种 随机 存取结构。

3. 在n维数组中的每一个元素最多可以有 n 个直接前驱。

4. 输出二维数组A[n][m]中所有元素值的时间复杂度为 n(n*m) 。

8 0 0 0 0 0 0 11 0 0 0 0 0 0 0 6 0 0 0 3 0 0 7 0 0 5 0 0 0 0 0 0 0 0 9 0 图6-19 稀疏矩阵A 5. 数组元素a[0…2][0…3]的实际地址是2000，元素长度是4，则LOC[1，2]= 2024 。

6. 稀疏矩阵的三元组有 3 列。

7. 稀疏矩阵的三元组中第1列存储的是数组中非零元素所在的 行数 。

8. n阶对称矩，如果只存储下三角元素，只需要 n(n-1)/2 个存储单元。

9. 稀疏矩阵A如图6-19所示，其非零元素存三元组表中，三元组（4，1，5）按列优先顺序存储在三元组表的第 4 项。

10. 稀疏疏矩阵的压缩存储方法通常有三元组表和 十字链表 两种。

11. 任何一个非空广义表的表尾必定是广义表（或子表）
。

12. tail(head((a，b)(c，d)= b 。

13. 设广义表（（a，b，c））则将c分离出来的运算是 head(tail(tail(head(L)))) 。

14. 广义表现出（（a，b）c，d），表尾是 (c,d) 。

15. n阶下三角矩阵，因为对角线的上方是同一个常数，需要 n(n-1)/2+1 个存储单元。

16. 稀疏矩阵中有n个非零元素，则三元组有 n 行。

17. 广义表LS=（a,（b）,（（c,（d））））的长度是 3 。

18. 广义表LS=（a,（b）,（（c,（d））））的深度是 4 。

19. 广义表LS=（（），L）,则L的深度是 ∞ 。

20. 广义表LS=（a,（b）,（（c,（d））））的表尾是 ((b),((c,(d)))) 。

三、选择题 1. 在一个m维数组中，（D）恰好有m个直接前驱和m个直接界后继。

A.开始结点 B.总终端结点 C.边界结点 D.内部结点 2. 对下述矩阵进行压缩存储后，失去随机存取功能的是（D）。

A.对称矩阵 B.三角矩阵 C.三对角矩阵 D.稀疏矩阵 3. 在按行优先顺序存储的三元组表中，下述陈述错误的是（D）。

A.同一行的非零元素，是按列号递增次序存储的B. 同一列的非零元素，是按行号递增次序存储的 C.三元组表中三元组行号是递增的 D. 三元组表中三元组列号是递增的 4. 对稀疏矩阵进行压缩存储是为了（B）。

A.降低运算时间B.节约存储空间C.便于矩阵运算D.便于输入和输出 5. 若数组A[0‥m] [0‥n]按列优先顺序存储，则aij的地址为（A）。

A.LOC(a00)+[j×m+i] B. LOC(a00)+[j×n+i] C. LOC(a00)+[(j-1)×n+i-1] D. LOC(a00)+[(j-1)×m+i-1] 6. 下列矩阵是一个（B）。

A． 对称矩阵 B．三角矩阵 C．稀疏矩阵 D．带状矩阵 1 0 0 0 2 3 0 0 4 5 6 0 7 8 9 10 7. 在稀疏矩阵的三元组表示法中，每个三元组表示（D）。

A．矩阵非零元素的值 B．矩阵中数据元素的行号和列号 C．矩阵中数据元素的行号、列号和值 D．矩阵中非零数据元素的行号、列号和值 8. 已知二维数组A[6][10]，每个数组元素占4个存储单元，若按行优先顺序存储存放数组元素a[3][5]的存储地址是1000，则a[0][0]的存储地址是（B）。

A．872 B．860 C．868 D．864 9. 广义表是线性表的推广，它们之间的区别于（A）。

A．能否使用子表 B．肥否使用原子项 C．是否能为空 D．表的长度 10. 下列广义表属于线性表的是（B）。

A.E=(a,E) B.E=(a,b,c) C.E=(a,(b,c)) D.E=(a,L);L=() 11. 广义表（（a,b）,c,d）的表尾是（D）。

A．a B．d C．(a,b) D．(c,d) 12. 广义表A=((x,(a,b)),(x,(a,b),y)),则运算head(head(tail(A)))为（A）。

A． x B．(a,b) C．(x,(a,b)) D．A 13. tail(head((a,b),c,(c,d)))的结果是（B）。

A． b B．(b) C．(a,b) D．(d) 14. 若广义表满足head(L)=tail(L),则L的形式是（B）。

A．空表 B．若L=（a1,…,an）,则a1=(a2,…,an) C．若L=（a1,…,an）,则(a1=a2,=…an) D．((a1)( a1)) 15. 数组是一个（B）线性表结构。

A.非 B.推广了的 C.加了限制的 D.不加限制的 16. 数组A[0：1，0：1，0：1]共有（D）元素。

A.4 B.5 C.6 D.8 17. 广义表（（a,b）,c,d）的表头是（C）。

A. a B.d C.(a,b) D.(c,d) 18. 广义表A=(a),则表尾为（C）。

A. a B.(()) C.空表 D.(a) 19. 以下（C）是稀疏矩阵的压缩存储方法。

A.一维数组 B.二维数组 C.三元数组 D.广义表 20. 设广义表D=(a,b,c,d),其深度为（D）。

A.2 B.3 C.4 D.∞ 第7章 树和二叉树 一、判断题 1. 树结构中每个结点最多只有一个直接前驱。

（√）
2. 完全二叉树一定是满二叉树。

（×）
3. 在中序线索二叉树中，右线索若不为空，则一定指向其双亲。

（×）
4. 一棵二叉树中序遍历序列的最后一个结点，必定是该二叉树前序遍历的最后一个结点。（√）
5. 二叉树的前序遍历中，任意一个结点均处于其子女结点的前面。

（√）
6. 由二叉树的前序遍历序列和中序遍历序列，可以推导出后序遍历的序列。

（√）
7. 在完全二叉树中，若一个结点没有左孩子，则它必然是叶子结点。

（√）
8. 在哈夫曼编码中，当两个字符出现的频率相同，其编码也相同，对于这种情况应该做特殊处理。（×）
9. 含多于两棵树的森林转换的二叉树，其根结点一定无右孩子。

（×）
10. 具有n个叶子结点的哈夫曼树共有2n-1个结点。

（√）
二、填空题 1. 在树中，一个结点所拥有的子树数称为该结点的 度 。

2. 度为零的结点称为 叶（或叶子，或终端）
结点。

3. 树中结点的最大层次称为树的 深度（或高度）
。

4. 对于二叉树来说，第i层上至多有 2i-1 个结点。

5. 深度为h的二叉树至多有 2h-1 个结点。

6. 由一棵二叉树的前序序列和 中序 序列可唯一确定这棵二叉树。

7. 有20个结点的完全二叉树，编号为10的结点的父结点的编号是 5 。

8. 哈夫曼树是带权路径长度的 最小 的二叉树。

9. 由二叉树的后序和 中序 遍历序列，可以唯一确定一棵二叉树。

10. 某二叉树的中序遍历序列为：DEBAC，后序遍历序列为：EBCAD。则前序遍历序列为 DABEC 。

11. 设一棵二叉树结点的先序遍历序历为：ABDECFGH，中序遍历序历为：DEBAFCHG，则二叉树中叶结点是：
E、F、H 。

12. 已知完全二叉树的第8层有8个结点，则其叶结点数是 68 。

13. 由树转换二叉树时，其根结点无 右子树 。

14. 采用二叉链表存储的n个结点的二叉树，一共有 2n 个指针域。

15. 采用二叉链表存储的n个结点的二叉树，共有空指针 n+1 个。

16. 前序为A，B，C且后序C，B，A的二叉树共有 4 种。

17. 三个结点可以组成 2 种不同形态的树。

18. 将一棵完全二叉树按层次编号，对于任意一个编号为i的结点，其左孩子结点的编号为：
2*i 。

19. 给定如图7-36所示的二叉树，其前序遍历序列为：
ABEFHCG 。

20. 给定如图7-37所示的二叉树，其层次遍历序列为：
ABCEFGH 。

A A B C B C E F G 图7-36 二叉树1 E F G 图7-37 二叉树2 HD HD 三、选择题 1. 树最适合用来表示（D）。

A.有序数据元素 B.无序数据元素 C.元素之间无联系的数据 D.元素之间有分支的层次关系 2. 前序为A，B，C的二叉树共有（D）种。

A.2 B.3 C.4 D.5 3. 根据二叉树的定义，具有3个结点的二叉树有（C）种树型。

A.3 B.4 C.5 D.6 4. 在一棵具有五层的满二叉树中，结点的点数为（B）。

A.16 B.31 C.32 D.33 5. 具有64个结点的完全二叉树的深度为（C）。

A.5 B.6 C.7 D.8 6. 任何一棵二叉树的叶结点在前序、中序、后序遍历序列中的相对次序（A）。

A.不发生改变 B.发生改变 C.不能确定 D.以上都不对 7. A，B为一棵二叉树上的两个结点，在中序遍历时，A在B前的条件是（C）。

A.A和B右方 B.A是B祖先 C.A和B左方 D.A是B子孙 8. 下列4棵树中，（B）不是完全二叉树。

A． A B. A C. A D. A B C B C B C B C D E HD G D E F D E D 9. 如图7-38所示的二叉树，后序遍历的序列是（D）。

A.ABCDEFGHI A B.ABDHIECFG 图7-38二叉树3 C.HDIBEAFCG B C D.HIDEBFGCA D E F G H I 10. 对于图7-39所示的二叉树，其中序序序列为（A）。

A． DBEHAFCG B.DBHEAFCG C.ABDEHCFG D.ABCDEFGH A B C D E F G 图7-39二叉树4 H 11. 某二叉树的后序遍历序列为：DABEC，中序遍历序列为：DEBAC，则前序遍历序列为（D）。

A.ACBED B.DECAB C.DEABC D.CEDBA 12. 具有n(n>1)个结点的完全二叉树中，结点i(2i>n)的左孩子结点是（D）。

A.2i B.2i+1 C.2i-1 D.不存在 13. 把一棵树转换为二叉树后，这棵二叉树的形态是（A）。

A.唯一的 B.有多种 C.有多种，但根结点都没有左孩子 D.有多种，但根结点都没有右孩子 14. 将一棵有100个结点的完全二叉树从上到下，从左到右依次对结点编号，根结点的编号为1，则编号为45的结点的左孩子编号为（B）。

A.46 B.47 C.90 D.91 15. 将一棵有100个结点的完全二叉树从上到下，从左到右依次对结点编号，根结点的编号为1，则编号为49的结点的右孩子编号为（B）。

A.98 B.99 C.50 D.100 16. 二叉树按某种顺序线索化后，任一结点均有指向其前驱和后继的线索，这种说法（B）。

A.正确 B.错误 C.不确定 D.都有可能 17. 下列陈述正确的是（D）。

A.二叉树是度为为2的有序树 B.二叉树中结点只有一个孩子时无左右之分 C.二叉树必有度为2的结点 D.二叉树中最多只有两棵子树，且有左右子树之分 18. 用5个权值{3，2，4，5，1}构造的哈夫曼树的带权路径长度是（B）。

A.32 B.33 C.34 D.15 19. 在树结构中，若结点B有4个兄弟，A是B的父亲结点，则A的度为（C）。

A.3 B.4 C.5 D.6 20. 二叉树的叶结点个数比度为2的结点的个数（C）。

A.无关 B.相等 C.多一个 D.少一个 第8章 图 一、判断题 1. 图可以没有边，但不能没有顶点。

（√）
2. 在无向图中，(v1，v2)与（v2，v1）是两条不同的边。

（×）
3. 邻接表只能用于有向图的存储。

（×）
4. 一个图的邻接矩阵表示是唯一的。

（√）
5. 用邻接矩阵法存储一个图时，所占用的存储空间大小与图中顶点个数无关，而只与图的边数有关。（×）
6. 有向图不能进行广度优先遍历。

（×）
7. 若一个无向图以顶点v1为起点进行深度优先遍历，所得的遍历序列唯一，则可以唯一确定该图。

（√）
8. 存储无向图的邻接矩阵是对称的，因此只要存储邻接矩阵的上三角（或下三角）部分就可以了。

（√）
9. 用邻接表法存储图时，占用的存储空间大小只与图中的边数有关，而与结点的个数无关。

（×）
10. 若从一个无向图中任一顶占出发，进行了一次深度优先遍历，就可以访问图中所有的顶点，则该图一定是连通的。

（√）
二、填空题 1. 图常用的存储方式有邻接矩阵和 邻接表 等。

2. 图的遍历有：
深度优先搜 和广度优先搜等方法。

3. 有n条边的无向图邻接矩阵中，1的个数是 2n 。

4. 有向图的边也称为 弧 。

5. 图的邻接矩阵表示法是表示 顶点 之间相邻关系的矩阵。

6. 有向图G用邻接矩阵存储，其第i行的所有元素之和等于顶点i的 出度 。

7. n个顶占e条边的图若采用邻接矩阵存储，则空间复杂度为：
On2 。

8. n个顶占e条边的图若采用邻接表存储，则空间复杂度为：
O(n+e) 。

9. 设有一稀疏图G，则G采用 邻接表 存储比较节省空间。

10. 设有一稠密图G，则G采用 邻接矩阵 存储比较节省空间。

11. 图的逆邻接表存储结构只适用于 有向 图。

12. n个顶点的完全无向图有 n(n-1)/2 条边。

13. 有向图的邻接矩阵表表示适于求顶点的 出度 。

14. 有向图的邻接矩阵表示中，第i列上非0元素的个数为顶点vi的 入度 。

15. 对于具有n个顶点的图，其生成树有且仅有 n-1 条边。

16. 对有n个顶点，e条弧的有向图，其邻接表表示中，需要 n+e 个结点。

17. 从图中某一顶点出发，访遍历图中其余顶点，且使每一顶点仅被访问一次，称这一过程为图的 遍历 。

18. 无向图的邻接矩阵一定是 对称 矩阵。

19. 一个连通网的最小生成树是该图所有生成树中 权 最小的生成树。

20. 若要求一个稠密图G的最小生成树，最好用 Prim 算法来求解。

三、选择题 1. 在一个图中，所有顶点的度数之和等于图的边数的（C）倍。

A.1/2 B.1 C.2 D.4 2. 在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的（B）倍。

A.1/2 B.1 C.2 D.4 3. 对于一个具有n个顶点的有向图的边数最多有（B）。

A.n B.n(n-1) C.n(n-1)/2 D.2n 4. 在一个具有n个顶点的无向图中，要连通全部顶点至少需要（C）条边。

A.n B.n+1 C.n-1 D.n/2 5. 有8个结点的有向完全图有（ C）条边。

A.14 B.28 C.56 D.112 6. 深度优先遍历类似于二叉树的（A）。

A.先序遍历 B.中序遍历 C.后序遍历 D.层次遍历 7. 广度优先遍历类似于二叉树的（D）。

A.先序遍历 B.中序遍历 C.后序遍历 D.层次遍历 8. 任何一个无向连通图的最小生成树（A）。

A.只有一棵 B.一棵或多棵 C.一定有多棵 D.可以不存在 9. 无向图顶点v的度是关联于该顶点B）的数目。

A.顶点 B.边 C.序号 D.下标 10. 有n个顶点的无向图的邻接矩阵是用（B）数组存储。

A.一维 B.n行n列 C.任意行n列 D.n行任意列 11. 对于一个具有n个顶点和e条边的无向图，采用邻接表表示，则表头向量大小为（C）。

A.n-1 B.n+1 C.n D.n+e 12. 在图的表示法中，表示形式唯一的是（A）。

A.邻接矩阵表示法 B.邻接表表示法 C.逆邻接表表示法 D.邻接表和逆邻接表表示法 13. 在一个具有n个顶点e条边的图中，所有顶点的度数之和等于（C）。

A. n B.e C.2n D.2e v1 1 a a v2 v3 2 3 b c b c e e v4 v5 4 5 d f d f 图8-23度为3的结点 图8-24（15）题 图8-25从顶点a出发 图8-26优先遍历 14. 图8-23中，度为3的结点是（B）。

A.V1 B.V2 C.V3 D.V4 15. 图8-24是（A）。

A.连通图 B.强连通图 C.生成树 D.无环图 16. 如图8-25所示，从顶点a出发，按深度优先进行遍历，则可能得到的一种顶点序列为（D）。

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 17. 如图8-26所示，从顶点a出发，按广度优先进行遍历，则可能得到的一种顶点序列为（A）。

A.a,b,e,c,d,f B.a,b,e,c,f,d C.a,e,b,c,f,d D.a,e,d,f,c,b 18. 最小生成树的构造可使用（A）算法。

A.Prim算法 B.卡尔算法 C.哈夫曼算法 D.迪杰斯特拉算法 19. 下面关于图的存储结构的叙述中正确的是（A）。

A.用邻接矩阵存储图，占用空间大小只与图中顶点数有关，而与边数无关 B.用邻接矩阵存储图，占用空间大小只与图中边数有关，而与顶点数无关 C.用邻接存储图，占用空间大小只与图中顶点数有关，而与边数无关 D.用邻接存储图，占用空间大小只与图中边数有关，而与顶点数无关 20. 连通分量是（C）的极大连通子图。

A. 树 B.图 C.无向图 D.有向图 第9章 查找 一、判断题 1. 二分查找法要求待查表的关键字值必须有序。

（√）
2. 对有序表而言采用二分查找总比采用顺序查找法速度快。

（×）
3. 在二叉排序树中，根结点的值都小于孩子的结点的值。

（×）
4. 散列存储法的基本思想是由关键字的值的决定数据的存储地址。

（√）
5. 哈希表是一种将关键字转换为存储地址的存储方法。

（√）
6. 选择好的哈希函数就可以避免冲突的发生。

（×）
7. 在有序的顺序表和有序的链表上，均可以采用二分查找来提高查找速度。

（×）
8. 采用分块查找，既有实现线性表所希望的查找速度，又能适应动态变化的需要。

（√）
9. 哈希查找的效率主要取决于哈希表构造时选取的哈希函数和处理冲突的方法。

（√）
10. 在二叉排序树上删除一个结点时，不必移动其他结点，只要将该结点的父结点的相应指针域置空即可。

（×）
二、填空题 1. 顺序查找法，表中元素可以 任意 存放。

2. 在分块查找方法中，首先查找 索引 ，然后再查找相应的块。

3. 顺序查找、二分查找、分块查找都属于 静态 查找。

4. 静态 查找表所含元素个数在查找阶段是固定不变的。

5. 对于长度为n的线性表，若进行顺序查找，则时间复杂度为 O(n) 。

6. 对于长度为n的线性表，若采用二分查找，则时间复杂度为 O(log2n) 。

7. 理想情况下，在散列表中查找一个元素的时间复杂度为：
O(1) 。

8. 在关键字序列（7，10，12，18，28，36，45，92）中，用二分查找法查找关键字92，要比较 4 次才找到。

9. 设有100个元素，用二分查找法查找时，最大的比较次数是 7 次。

10. 对二叉排序树进行查找的方法是用待查的值与根结点的键值进行比较，若比根结点值小，则继续在 左 子树中查找。

11. 二叉排序树是一种 动态 查找表。

12. 哈希表是按 散列 存储方式构造的存储结构。

13. 哈希法既是一种存储方法，又是一种 查找 方法。

14. 散列表的查找效率主要取决于散列表造表时选取的散列函数和处理 冲突 的方法。

15. 设散列函数H和键值k1，k2，若k1≠k2 ，而H（k2 ）H（k2），则称这种现象为 冲突 。

16. 处理冲突的两类主要方法是开放定地址法和 拉链法（或链地址法）
。

17. 散列表（或散列）
查找法的平均查找长度与元素个数n无关。

18. 在哈希函数H（key）= key%P中，P一般应取 质数 。

19. 在查找过程中有插入元素或删除元素操作的，称为 动态 查找。

20. 各结点左、右子树深度之差的绝对值至多为 1 的二叉树称为平衡二叉树。

三、选择题 1. 查找表以（A）为查找结构。

A.集合 B.图 C.树 D.文件 2. 顺序查找法适合于存储结构为（B）的线性表。

A.散列存储 B.顺序存储或链接存储C.压缩存储 D.索引存储 3. 在表长为n的链表中进行线性查找，它的平均查找长度为（B ）。

A.ASL=n B.ASL=(n+1)/2 C.ASL=+1 D.ASL≈log2n 4. 对线性表进行二分查找时，要求线性表必须（D）。

A.以顺序方式存储 B.以链接方式存储，且结点按关键字有序排序 C.以链接方式存储 D.以顺序方式存储，且结点按关键字有序排序 5. 衡量查找算法效率的主要标准是（B）。

A.元素个数 B.平均查找长度 C.所需的存储量 D.算法难易难度 6. 如果要求一个线性表既能较快地查找，又能适应动态变化的要求，可以采用（A）查找方法。

A.分块 B.顺序 C.二分 D.散列 7. 链表适用于（A）查找。

A.顺序 B.二分 C.随机 D.顺序或二分 8. 一个有序表为{1，3，9，12，32，41，45，62，75，77，82，95，100}，当二分查找值为82的结点时，（C）次比较后查找成功。

A.2 B.3 C.4 D.5 9. 二分查找有序表{4，6，10，12，20，30，50，70，88，100}，若查找表中元素58，则它将依次与表中（B）比较大小，查找结果是失败。

A.30，88，70，50 B.20，70，30，50 C.20，50 D.30，88，50 10. 对有14个元素的有序A[1‥14]作二分查找，查找元素A[4]时的被比较元素依次为（C）
A.A[1]，A[2]，A[3]，A[4] B.A[1]，A[14]，A[7]，A[4] C.A[7]，A[3]，A[5]，A[4] D.A[7]，A[5]，A[3]，A[4] 11. 有一个长度为12的有序表，按二分查找法对其进行查找，在表内各元素等概率情况下查找成功所需的平均比较次数为（B）。

A.35/12 B.37/12 C.39/12 D.43/12 12. 采用分块查找时，若线性表共有625个元素，查找生个元素等概率相等，假设采用顺序查找来确定结点所在的块时，每块分（C）个结点最佳。

A．6 B．10 C．25 D．625 13. 下列（C）不是利用查找表中数据元素的关系进行查找的方法。

A．平衡二叉树 B．有序表的查找 C．散列查找 D．二叉排序树的查找 14. 设哈希表长m=14，哈希函数H(key)=key%11。表中已有4个结点：addr(15)=4 addr(38)=5 addr(61)=6 addr(84)=7其余地址为空。如用二次探测再散列处理冲突，关键字为49的结点的地址是（D）。

A．8 B．3 C．5 D．9 15. 对包含n个元素的散列表进行查找。平均查找长度为（D）。

A．O(n2) B．O(log2n) C．O(n) D．不直接依赖于n 16. 冲突指的是（C）。

A．两个元素具有相同序号 B．两个元素的键值不同 C．不同键值对应相同的存储地址 D．两个元素的键值相同 17. 在查找过程中，不做增加、删除或修改的查找称为（A）。

A．静态查找 B．内创造 C．动态查找 D．处查找 18. 已知8个元素为{34，76，45，18，26，54，92，65}，按照依次插入结点的方法生成一棵二叉排序树，最后两层上结点的总数为（B）。

A．1 B．2 C．3 D．4 19. 不可能生成图9-17所示的二叉排序树的关键字的序列是（A）。

A．4 5 3 1 2 B．4 2 5 3 1 C．4 5 2 1 3 D．4 2 3 1 5 4 2 5 1 3 图9-17二叉树 20. 动态查找包括（B）查找。

A.顺序表 B.二叉排序树 C.有序表 D.索引顺序表 第10章 排序 一、判断题 1. 如果某种排序算法不稳定，则该排序方法就没有实用价值。

（×）
2. 希尔排序是不稳定的排序。

（√）
3. 冒泡排序是不稳定的排序。

（×）
4. 对n个记录的进行快速排序，所需要的平均时间是O（nlog2n）。

（√）
5. 堆排序所需的时间与待排序的记录个数无关。

（×）
6. 当待排序的元素个数很多时，为了交换元素的位置占用较多的时间，这是影响时间复杂度的主要因素。

（ √ ）
7. 快速排序在任何情况下都比其他排序方法速度快。

（×）
8. 对快速排序来说，初始序列为正序或反序都是最坏情况。

（√）
9. 采用归并排序可以实现外排序。

（√）
10. 采用希尔排序时，若原始关键字的排列杂乱无序，则效率最高。

（√）
二、填空题 1. 大多数排序算法都有两个基本的操作：
比较 和移动。

2. 评价排序算法优劣的主要标准是 时间复杂度 和算法所需的附加空间。

3. 根据被处理的数据在计算机中使用不同的存储设备，排序可分为 内排序 和外排序。

4. 外排序是指在排序过程中，数据的主要部分存在计算机的 外存 中。

5. 对n个关键字进行冒泡排序，其可能的最小比较次数为 n-1 次。

6. 在最坏情况下，在第i趟直接插入排序中，要进行 i-1 次关键字的比较。

7. 对n个关键字进行冒泡排序，时间复杂度为 O（n2 ）
。

8. 快速排序在最坏情况下的时间复杂度是 O（n2）
。

9. 对于n个记录的集合进行归并排序，所需要的平均时间为 O（nlog2n）
。

10. 对于n个记录的集合进行归并排序，所需要的附加空间为 O(n) 。

11. 若原始数据接近无序，则选用 快速排序 最好。

12. 在排序前，关键字值相等的不同记录，排序后相对位置保持 不变 的排序方法，称为稳定排序方法。

13. 在插入排序和选择排序中，若初始数据基本正序，则选用 插入排序较好。

14. 当增量为1时，该趟希尔排序与 直接插入 排序基本一致。

15. 第一趟排序后，序列中键值最大的记录交换到最后的排序算法是 冒泡 排序。

16. 依次将后面文件每个记录插入到一个前面有序的子文件中的排序方法称为直接插入 排序。

17. 在插入排序、选择排序和归并排序中，不稳定的排序为：
选择 排序。

18. 在对一组记录（54，38，96，23，15，72，60，45，93）进行直接插入排序时，当把第7个记录60插入到有序表时，为寻找插入位置需比较 3 次。

19. 两个序列分别为：L1={25，57，48，37，92，86，12,33} L2 ={25，37，33，12，48，57，86，92} 用冒泡排序法对L1和 L2进行排序，交换次数较少的是序列：
L2 。

20. 对一组记录（54，35，96，21，12，72，60，44，80）进行直接选择排序时，第4次选择和交换后，未排序记录是 54，72，60，96，80 。

三、选择题 1. 排序是根据（A ）的大小重新安排各元素的顺序。

A.关键字 B.数组 C.元素件 D.结点 2. 评价排序算法好坏的标准主要是（D）。

A.执行时间 B.辅助空间 C.算法本身的复杂度 D.执行时间和所需的辅助空间 3. 直接插入排序的方法是（ B ）的排序方法。

A.不稳定 B.稳定 C.外部 D.选择 4. 直接插入排序的方法要求被排序的数据（B）存储。

A.必须链表 B.必须顺序 C.顺序或链表 D.可以任意 5. 排序方法中，从无序序列中选择关键字最小的记录，将其与无序区（初始为空）的第一个记录交换的排序方法，称为（D）。

A.希尔排序 B.归并排序 C.插入排序 D.选择排序 6. 每次把待排序的数据划分为左、右两个区间，其中左区间中元素的值不大于基准元素的值，右区间中元素的值不小于基准元素的值，此种排序方法称为（C ）。

A.冒泡排序 B.堆排序 C.快速排序 D.归并排序 7. 快速排序在（ C）情况下最易发挥其长处。

A.待排序的数据中含有多个相同的关键字B.待排序的数据已基本有序 C.待排序的数据完全无序 D.待排序的数据中最大值与最小值相差悬殊。

8. 下述几种排序方法中，要求内存量最大的是（ D ）。

A.插入排序 B.选择排序 C.快速排序 D.归并排序 9. 直接插入排序的方法是从第（ B ）个元素开始，插入前边适当位置的排序方法。

A.1 B.2 C.3 D.n 10. 堆的形状是一棵（ C ）。

A.二叉排序树 B.满二叉树 C.完全二叉树 D.平衡二叉树 11. 内排序是指在排序的整个过程中，全部数据都在计算机的（ A ）中完成的排序。

A.内存 B.外存 C.内存和外存 D.寄存器 12. 快速排序的方法是（A ）的排序方法。

A.不稳定 B.稳定 C.外部 D.选择 13. 下列排序方法中，关键字比较次数与记录的初始排列次序无关的是（ A）。

A.选择排序 B.希尔排序 C.插入排序 D.冒泡排序 14. 下述几种排序方法中，平均时间复杂度最小的是（A）。

A.希尔排序 B.插入排序 C.冒泡排序 D.选择排序 15. 对有n个记录的表作快速排序，在最坏情况下，算法的时间复杂度是（B）。

A.O(n) B.O(n2) C.O(nlog2n) D.O(n3) 16. 冒泡排序的方法对n个数据进行排序，第一趟排序共需要比较（C ）次。

A.1 B.2 C.n-1 D.n 17. 对n个不同的排序码进行冒泡（递增）排序，在下列（B ）情况比较的次数最多。

A.从小到大排列好的 B.从大到小排列好的C.元素无序 D.元素基本有序 18. 用直接插入排序法对下面的4个序列进行由小到大的排序，元素比较次数最少的是（B）。

A.94，32，40，90，80，46，21，69 B.21，32，46，40，80，69，90，94 C.32，40，21，46，69，94，90，80 D.90，69，80，46，21，32，94，40 19. 一组记录的排序码为（25，48，16，35，79，82，23，40），其中含有4个长度为2的有序表，按归并排序的方法对该序列进行一趟归并后的结果为（ A）。

A.16 25 35 48 23 40 79 82 B.16 25 35 48 79 82 23 40 C.16 25 48 35 79 82 23 40 D.16 25 35 48 79 23 40 82 20. 一个数据序列的关键字为（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，79，56，84）
第十章文件 1．文件：性质相同的记录的集合。放在外存 主关键字项：能唯一标识记录的数据项或数据项的组合（如学号）
文件的操作：检索和维护 文件的存贮结构：顺序、索引、散列、链 文件的组织方式：顺序文件、索引文件、散列文件、多关键字文件 2．顺序文件：记录进入文件的先后顺序存放其逻辑顺序与物理顺序一致的文件。

顺序文件的更新方法：
优点：
3．索引文件：在主文件之外另外建立一张表：逻辑记录与物理记录的对应关系表各主文件一起构成的文件叫索引文件。

4．索引顺序文件：索引表按主关键字有序，主文件按关键字可有序 索引非顺序文件索引表按主关键字有序，主文件按关键字无序 ISAM文件：专为磁盘存取设计的文件组织方式，静态索引结构，由多级主索引、柱面索引、磁道索引和主文件组成。

VSAM文件：虚拟存贮存取方法，用B+树用为动态索引结构，文件由三部分组成：索引集、顺序集、数据集 5．散列文件：用散列存贮方式组织的文件，直接存取文件 桶：
6．多关键字文件：包含有多个次关键字索引的文件 多重表文件：索引方法与链接方法相结合的一种组织方式 倒排文件：与多重表不同的是次关键字索引的结构不同 三、应用题(本大题共5小题，每小题6分，共30分) 26.已知广义表的图形表示如图所示, (1) 写出该广义表L; (2) 分别写出该广义表的深度和长度。

L=((e), (), (a,(b,c,d)), (b,c,d)) 深度3 长度4 27.已知二叉树的先序序列和中序序列分别为ABDEHCFI和DBHEACIF， (1) 画出该二叉树的二叉链表存储表示; (2) 写出该二叉树的后序序列。DHEBIFCA A B C D E F H I 28.已知有向图的邻接表如图所示, (1) 写出从顶点A出发,对该图进行广度优先搜索遍历的顶点序列：ABDCE (2) 画出该有向图的逆邻接表。

29.依次读入给定的整数序列{7，16，4，8，20，9，6，18，5}，完成下列操作：
1)构造一棵二叉排序树,计算在等概率情况下该二叉排序树的平均查找长度ASL; 2)若变更序列中元素的排列,可构造出平均查找长度达到最小的二叉排序树。写出满足上述要求的序列中的第一个元素。

7 4 16 6 8 20 5 9 18 ASL=1/9*（1+2*2+3*3+3*4）=26/9 {9，7，5，4，8，18，6，16，20} 9 7 18 5 8 16 20 4 6 ASL=1/9*（1+2*2+4*3+2*4）=25/9 26.由森林转换得到的对应二叉树如图所示，写出原森林中第三棵树 的前序序列和后序序列。

G H I J 前序序列：GHI J 后序序列：HJIG 27.图的邻接表的类型定义如下所示：
#define MaxVertexNum 50 typedef struct node { int adjvex; struct node *next; }EdgeNode; typedef struct { VertexType vertex; EdgeNode *firstedge; }VertexNode; typedef VertexNode AdjList[MaxVertexNum]; typedef struct { AdjList adjlist; int n, e; }ALGraph; 为便于删除和插入图的顶点的操作，可将邻接表的表头向量定义为链式结构，两种定义的存储表示实例如下图所示，请写出重新定义的类型说明。

题27图 typedef struct link { VertexType vertex; EdgeNode *firstedge; link *down; }; typedef struct node { struct node *next; struct link *next1; }EdgeNode; struct Link * ALGraph; 28.某类物品的编号由一个大写英文字母及2位数字（0..9）组成，形如E32。运用基数排序对下列物品编号序列进行按字典序的排序，写出每一趟（分配和收集）后的结果。

E13，A37，F43，B32，B47，E12，F37，B12 第一趟：B32,E12,B12,E13,F43,A37,B37,F37 第二趟：E12,B12,E13,B32,A37,F37,F43,B47 第三趟：A37,B12,B32,B47,E12,E13,F37,F43 29.（1）画出对表长为13的有序顺序表进行二分查找的判定树；

A[6]=28 A[3]= 16 A[10]= 67 A[1]= 12 A[4]= 21 A[8]=43 A[12]=84 A[2]= 14 A[5]= 24 A[7]= 35 A[9]= 52 A[11]= 71 A[13]= 99 （2）已知关键字序列为（12，14，16，21，24，28，35，43，52，67，71，84，99），写出在该序列中二分查找37时所需进行的比较次数。5 29．在栈的输入端元素的输入顺序为1，2，3，4，5，6，进栈过程中可以退栈，则退栈时能否排成序列3，2，5，6，4，1和1，5，4，6，2，3，若能，写出进栈、退栈过程，若不能，简述理由。（用push（x）表示x进栈，pop(x)表示x退栈）
push（1）push（2）push（3）pop(3) pop(2) push（4）push（5）
POP（5）push（6）pop(6) pop(4) pop(1) 30．已知一棵二叉树的中根遍历序列为CBEDFAGH，后根遍历序列为CEFDBHGA，画出该二叉树。

A B G C D H E F 31．给定表（15，11，8，20，14，13），试按元素在表中的顺序将它们依次插入一棵初始时为空的二叉排序树，画出插入完成后的二叉排序树，并判断该二叉排序树是否为平衡二叉排序树，若为非平衡二叉排序树，将它调整为平衡二叉排序树。

15 11 20 8 14 13 调整方法：
根结点不平衡：根左子树高>右子树高+1：根的中序序列8，11，13，14，15，20中根的前一点14上移为根 14 11 15 8 13 20 根左子树高<右子树高+1：根的中序序列中根的后一点上移为根 33．用冒泡排序法（快速排序）对数据序列（49，38，65，97，76，134，27，49）进行排序，写出排序过程。并说明冒泡排序是否为稳定排序。

冒泡排序法稳定 49，38，65，97，76，134，27，49 49，65，97，76，134，38，49，27 65，97，76，134，49，49，38，27 97，76，134，65，49，49，38， 27 97，134，76， 65，49，49，38， 27 134，97， 76， 65，49，49，38， 27 快速排序不稳定 49，38，65，97，76，134，27，49 49，38，27，49，76，134，97，65， 27，38，49，49，65，76，97，134 27，38，49，49，65，76，97，134 29.已知3阶B-树如图所示， (1)画出将关键字6插入之后的B-树；

(2)画出在(1)所得树中插入关键字2之后的B-树。

2 5 6 2 1 3 2 8 9 2 3 6 2 1 2 1 5 2 8 9 32．如题32图所示无向图，（1）写出其邻接矩阵；
（2）写出三种以顶点A为起点的深度优先搜索顶点序列。

a0 1 1 0 0 0 0 1 b1 0 0 1 1 00 0 c0 0 0 0 0 1 0 0 d0 1 0 1 0 0 0 0 e0 1 0 0 0 1 0 0 f 0 0 1 0 0 0 0 0 g0 0 0 1 1 0 0 0 h10 0 0 0 0 0 0 图6-19 稀疏矩阵A ACFBEGDH ABDGEHCF AHBEGDCF 28.假设通信电文使用的字符集为 {a，b，c， d， e， f， g， h} 各字符在电文中出现的频度分别为：7，26，2，28，13，10，3，11，试为这8个字符设计哈夫曼编码。要求：
(1)画出你所构造的哈夫曼树(要求树中左孩子结点的权值不大于右孩子结点的权值)；

(2)按左分支为0和右分支为1的规则，分别写出与每个字符对应的编码。

100 46 54 21 25 26b 28d 10f 11h 12 13e 5 7a 2c 3g A:0101 b:10 c:01000 d:00 e:011 f:000 g:01001 h:001 四、算法阅读题(本大题共4小题，每小题5分，共20分) 四、算法阅读题（本大题共4小题，每小题5分，共20分）
30.假设以带头结点的单链表表示线性表,阅读下列算法f30,并回答问题: (1) 设线性表为( a1, a2, a3, a4, a5, a6, a7 ), 写出执行算法f30后的线性表；

(2) 简述算法f30的功能。

void f30(LinkList L) { //L为带头结点单链表的头指针 LinkList p,q; P =L; while (p &&p–>next) {q = p–>next; //q指向第一个点 p–>next =q–>next; //p的下一个指向第二个点,删除了第一个点 p =q–>next; //p指向第二个点 free(q);//回收q } } (1) (a2, a3, a4, a5, a6, a7 ), (2) 删除了链表第一个点(不是头结点) 31.算法f31的功能是借助栈结构实现整数从10进制到8进制的转换，阅读算法并回答问题：
(1) 画出n为十进制的1348时算法执行过程中栈的动态变化情况; (2) 说明算法中while循环完成的操作。

void f31(int n) //n为非负的十进制整数 { int e; SeqStack S; InitStack(& S); do{ Push(& S,n%8); n =n/8; }while (n); while ( ! StackEmpty(& S)){e =Pop(& S);printf (〞%ld〞,e);} } (1)4，0，5 2 (2)当栈不空时出栈输出n化为8进制数的序列2504 32.已知以二叉链表作二叉树的存储结构，阅读算法f32，并回答问题：
(1) 设二叉树T如图所示,写出执行f32(T)的返回值; (2) 简述算法f32的功能。

int f32(BinTree T) { int m, n; if(! T) return 0; else { m= f32(T–>lchild); n = f 32(T–>rchild); if(m>n)return m +1; else return n+1; } } (1) (2) 33.设有向图邻接表定义如下；

typedef struct{ VertexNode adjlist[Max VertexNum]; int n,e; //图的当前顶点数和弧数 } ALGraph; //邻接表类型 vertex firstedge 其中顶点表结点VertexNode结构为：
adjvex next 边表结点EdegNode结构为：
阅读下列算法f33，并回答问题：
(1)已知有向图G的邻接表如图所示, 写出算法f33的输出结果; (2)简述算法f33的功能。

void dfs (ALGraph *G,int v) { EdgeNode * p; visited[v]=TRUE; printf(〞%c〞,G–>adjlist[v]·vertex); for(p =G–>adjlist[v])·firstedge; p; p=p–>next) if(! visited[p–>adjvex]) dfs (G, p–>adjvex); } void f33(ALGraph *G) { int v,w; for(v=0; v <G–>n; v ++) { for(w=0;w<G–>n; w++) visited[w]=FALSE; printf(〞%d: 〞,v); dfs(G,v); printf(〞﹨n〞); } } 30.假设以带头结点的单链表表示线性表，单链表的类型定义如下：
typedef int DataType; typedef struct node { DataType data; struct node * next; } LinkNode, * LinkList; 阅读下列算法，并回答问题：
(1)已知初始链表如图所示，画出执行f30(head)之后的链表；

题30图 (2)简述算法f30的功能。

void f30( LinkList head) { LinkList p,r, s; if (head - > next) { r = head - > next; p = r->next; r - > next = NULL; while (p) { s =p; p = p->next; if ( s - > data% 2 = = 0) { s - > next = head - > next; head - > next = s; } else { s - > next = r - > next; r->next = s; r =s; } } } } (1) 2 8 5 7 (2)将原链中偶数置前，奇数置后 31.假设以二叉链表表示二叉树，其类型定义如下：
typedef struct node { DataType data; struct node * lchild, * rchild; //左右孩子指针 } * BinTree ; 阅读下列算法，并回答问题：
(1)已知以T为根指针的二叉树如图所示， 写出执行f31(T)之后的返回值；

(2)简述算法f31的功能。

int f31 ( BinTree T) { int d; if ( ! T) return 0; d = f31 ( T - > lchild) + f31 ( T - > rchild) ; if (T - > lchild && T - > rchild) return d + 1 ; else return d; (1) (2) 32.设有向图邻接表定义如下：
typedef struct { VertexNode adjlist[ MaxVertexNum ] ; int n，e；

／／图的当前顶点数和弧数 }ALGraph；

／／邻接表类型 其中顶点表结点VertexNode 边表结点EdgeNode结构为：
阅读下列算法，并回答问题：
(1)已知某有向图存储在如图所示的邻接 表G中，写出执行f32(＆G)的输出；

(2)简述算法f32的功能。

int visited[ MaxNum ]; void DFS(ALGraph * G, int i) { EdgeNode * p; visited [ i ] = TRUE ; if (G - > adjlist[ i]. firstedge = = NULL) printf( “% c “, G - > adjlist[ i]. vertex)；

else { p = G - > adjlist[ i]. firstedge; while (p ! = NULL) { if ( ! visited[p -> adjvex] ) DFS( G, p - > adjvex) ; p = p->next; } } } void f32 ( ALGraph * G) { int i; for (i = 0; i < G->n; i ++) visited [ i ] = FALSE ; for (i = 0; i < G->n; i++) if ( ! visited[i] ) DFS(G, i) ; } (1) (2) 33.下列算法f33的功能是对记录序列进行双向冒泡排序。算法的基本思想为，先从前往后通过交换将关键字最大的记录移动至后端，然后从后往前通过交换将关键字最小的记录移动至前端，如此反复进行，直至整个序列按关键字递增有序为止。请在空缺处填入合适的内容，使其成为完整的算法。

#define MAXLEN 100 typedef int KeyType; typedef struct { KeyType key; InfoType otherinfo; } NodeType ; typedef NodeType SqList[ MAXLEN ]; void f33 ( SqList R, int n) { int i,j,k; NodeType t; i =0; j =n-l; while (i < j) { for ( k=i;k<j;k++ ) if (R[k].key > R[k +l].key) { t = R[k]; R[k] = R[k +1]; R[k +1] = t; } j--; for (k =j; k > i; k -- ) if (R[k-1].key > R[k ].key ) { t = R[k]; R[k] = R[k-1]; R[k-1] = t; }