数据结构习题

数据结构习题

第一章 绪论

一、单项选择题

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．分析算法的易懂性和文档性 ②A．空间复杂性和时间复杂性 B．正确性和简明性 C．可读性和文档性 D．数据复杂性和程序复杂性

6．数据结构是一门研究非数值计算的程序设计问题中计算机的 ① 以及它们之间的 ② 和运算等的学科。

①A．操作对象 B．计算方法 C．逻辑存储 D．数据映象 ②A．结构 B．关系 C．运算 D．算法

7．数据结构被形式地定义为（K，R），其中K是 ① 的有限集合，R是K上的 ② 的有限集合。 ①A．算法 B．数据元素 C．数据操作 D．逻辑结构 ②A．操作 B．映象 C．存储 D．关系 8．在数据结构中，从逻辑上可以把数据结构分成 。 A．动态结构和静态结构 B．紧凑结构和非紧凑结构

1

C．线性结构和非线性结构 D．内部结构和外部结构

二、填空题

1.数据的基本单位是 ，最小单位 。

2.算法的的特性有 、 、 、输入、输出 。 3. 数据结构按结点的关系，可分为4种逻辑结构： 、 、树结构、图结构。 4. 数据结构的存储结构包括顺序、________、索引和散列等四种。 5．算法质量的度量标准有两个： 复杂度和 复杂度。

6．数据的逻辑结构是从逻辑关系上描述数据，它与数据的_____无关，是独立于计算机的。

7．线性结构中元素之间存在 关系，树形结构中元素之间存在 关系，图形结构中元素之间存在 关系。

8．下面程序段的时间复杂度是 。 for (i=1; i

for (j=1; j

for(i=0; i

count=0; x=2; while (x

x *= 2; count++; }

return (count) }

11．下面程序段的时间复杂度是 。 s＝0；

2

for（i=0；i

12．下面程序段的时间复杂度是 。 for (i=1; i

for (j=1; j

三、判断题

1.算法的运行时间涉及加、减、乘、除、转移、存、取、等基本运算。要想准确地计算总运算时间是不可行的。

2.为度量一个搜索算法的性能，需要在时间和空间方面进行权衡。 3.数据的基本单位是数据项。 5.数据的最小单位是数据项。

4. 数据的逻辑结构是指各数据元素之间的逻辑关系，是用户根据应用需要建立的。

四、简答题

1.怎样理解数据结构在计算机课中的核心地位。 2.为什么要用抽象数据类型来描述数据结构。

3.描述数据结构、逻辑结构、存储结构和运算的有关概念及其相互之间的关系。它们如何影响算法的设计与实现。

4.描述算法所具备的基本特征，并指出算法与程序之间的差异。

3

第二章 线性表

一、单项选择题

1.线性表是一个具有n个（ ）的有限序列。

A．表元素 B．字符 C．数据元素 D．数据项 2.线性链表不具有的特点是（ ）。

A．随机访问 B．不必事先估计所需存储空间大小 C．插入与删除时不必移动元素 D．所需空间与线性表长度成正比 3.向有127个元素原顺序表中插入一个元素，平均要移动（ ）个元素。 A. 8 B. 63.5 C. 63 D. 7

4.一个有序顺表有255个对象，采用顺序搜索法查表，搜索成功的平均搜索长度为（ ）。 A.128 B.127 C.126 D.255

5．对于顺序存储的线性表，访问结点和增加、删除结点的时间复杂度为（ ）。 A．O(n) O(n) B．O(n) O(1) C．O(1) O(n) D．O(1) O(1)

6．表长为n的顺序存储的线性表，当在任何位置上插入和删除一个元素的概率相等时，插入一个元素所需移动元素的平均个数为（ ），删除一个元素需要移动元素的平均个数为（ ）。 A.(n-1)/2 B.(n+1)/2 C.n/2 D.n E.(n-2)/2

7. 在一个长度为n的顺序表的任一位置插入一个新元素的渐进时间复杂度为（ ）。 A. O(n) B. O(n/2)

C. O(1)

D. O(n)

2

8.线性链表不具有的特点是（ ）。

A．随机访问 B．不必事先估计所需存储空间大小 C．插入与删除时不必移动元素 D．所需空间与线性表长度成正比 9.带头结点的单链表first为空的判定条件是（ ） A. first == NULL; B. first->next == NULL; C. first->next == first; D. first != NULL; 10.用链表表示线性表的优点是( )

A.便于随机存取 B.花费的存储空间比顺序表少 C.便于插入与删除 D.数据元素的物理顺序与逻辑顺序相同

11.在一个单链表中，已知q所指结点是p所指结点的前驱结点，若在q和p之间插入s结点，则执行（ ）。 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. 已知单链表A长度为m，单链表B长度为n，若将B联接在A的末尾，其时间复杂度应为（ ）。 A. O(1) B. O(m) C. O(n) D. O(m+n) 13．设单链表中结点的结构为

4

typedef struct node { file://链表结点定义 ElemType data； file://数据

struct node * Link； file://结点后继指针 } ListNode；

（1）已知指针p所指结点不是尾结点，若在*p之后插入结点*s，则应执行下列哪一个操作？ A. s->link = p； p->link = s； B. s->link = p->link； p->link = s； C. s->link = p->link； p = s；

D. p->link = s； s->link = p；

（2）非空的循环单链表first的尾结点（由p所指向）满足： A. p->link == NULL； B. p == NULL； C. p->link == first； D. p == first；

14．线性表采用链式存储时，结点的存储地址（ ） A．必须是不连续的 B．连续与否均可

C．必须是连续的 D．和头结点的存储地址相连续

15．将长度为n的单链表链接在长度为m的单链表之后的算法的时间复杂度为（ ） A．O（1） B．O（n） C．O（m） D．O（m+n）

16．线性表的顺序存储结构是一种 的存储结构，线性表的链式存储结构是一种 的存储结构。 A．随机存取 B．顺序存取 C．索引存取 D．散列存取 17.下面关于线性表的叙述中，错误的是哪一个？（ ） A．线性表采用顺序存储，必须占用一片连续的存储单元。 B．线性表采用顺序存储，便于进行插入和删除操作。 C．线性表采用链接存储，不必占用一片连续的存储单元。 D．线性表采用链接存储，便于插入和删除操作。 18．线性表是具有n个（ ）的有限序列（n>0）。 A．表元素 B．字符 C．数据元素 D．数据项 19．下面的叙述不正确的是（ ）

A．线性表在链式存储时，查找第i个元素的时间同i的值成正比 B. 线性表在链式存储时，查找第i个元素的时间同i的值无关 C. 线性表在顺序存储时，查找第i个元素的时间同i 的值成正比 D. 线性表在顺序存储时，查找第i个元素的时间同i的值无关

20．设一个链表最常用的操作是在末尾插入结点和删除尾结点，则选用( )最节省时间。 A. 单链表 B.单循环链表 C. 带尾指针的单循环链表 D.带头结点的双循环链表

5

21．线性表的顺序存储结构是一种 的存储结构，线性表的链式存储结构是一种 的存储结构。 A．随机存取 B．顺序存取 C．索引存取 D．散列存取 22．下述哪一条是顺序存储结构的优点？（ ）

A．存储密度大 B．插入运算方便 C．删除运算方便 D．可方便地用于各种逻辑结构的存储表示 23．若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（ ）存储方式最节省时间。

A．顺序表 B．双链表 C．带头结点的双循环链表 D．单循环链表

24．设一个链表最常用的操作是在末尾插入结点和删除尾结点，则选用( )最节省时间。 A. 单链表 B.单循环链表 C. 带尾指针的单循环链表 D.带头结点的双循环链表 25．线性表（a1,a2,?,an）以链接方式存储时，访问第i位置元素的时间复杂性为（ ） A．O（i） B．O（1） C．O（n） D．O（i-1） 26．循环链表h的尾结点p的特点是（ ）

A．p→next=h B．p→next=h->next C．p=h D．p=h->next 27．完成在双循环链表结点p之后插入s的操作是（ ）

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;

28．双向链表中有两个指针域，llink和rlink分别指向前趋及后继，设p指向链表中的一个结点，现要求删去p所指结点，则正确的删除是（ ）（链中结点数大于2，p不是第一个结点） A．p->llink->rlink=p->llink; p->llink->rlink=p->rlink; dispose(p); B．dispose(p); p->llink->rlink=p->llink; p->llink->rlink=p->rlink; C．p->llink->rlink=p->llink; dispose(p); p->llink->rlink=p->rlink; D．以上A，B，C都不对。

二、填空题

1．向一个长度为n的向量的第i个元素(1≤i≤n)之前插入一个元素时，需向后移动 ________个元素。 2．线性表（a1,a2，??，an）以链接方式存储时，在第i个位置删除一个元素的时间复杂度是____ __。 3. 当线性表的元素总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素时，应采用_______存储结构。 4.链表适用于 查找。

6

5.链表对于数据元素的插入和删除不需移动结点，只需改变相关结点的________域的值。 6.在一个链式栈中，若栈顶指针等于NULL则为________。

7.在链表中进行插入和 操作的效率比在顺序存储结构中进行相同操作的效率高。 8.链表对于数据元素的插入和删除不需移动结点，只需改变相关结点的________域的值。

9．在一个带头结点的单循环链表中，p指向尾结点的直接前驱，则指向头结点的指针head可用p表示为head=_____。

10. 对于双向链表,在两个结点之间插入一个新结点需修改的指针共 ______个，单链表为_______个。 11．线性表L=（a1,a2,?,an）用数组表示，假定删除表中任一元素的概率相同，则删除一个元素平均需要移动元素的个数是________。

12．在单链表中设置头结点的作用是________。

13．对于一个具有n个结点的单链表，在已知的结点*p后插入一个新结点的时间复杂度为________, 在给定值为x的结点后插入一个新结点的时间复杂度为________。

14．根据线性表的链式存储结构中每一个结点包含的指针个数，将线性链表分成________和_______；而又根据指针的连接方式，链表又可分成________和________。

15. 在双向链表结构中，若要求在p 指针所指的结点之前插入指针为s 所指的结点，则需执行下列语句： s->next=p； s->prior= ________；p->prior=s；________=s；

16.顺序存储结构是通过________表示元素之间的关系的;链式存储结构是通过________表示元素之间的关系的。

17. 对于双向链表,在两个结点之间插入一个新结点需修改的指针共 ______个，单链表为_______个。 18. 循环单链表的最大优点是：________。

19. 带头结点的双循环链表L中只有一个元素结点的条件是：________ 20. 在单链表L中，指针p所指结点有后继结点的条件是： 21. 带头结点的双循环链表L为空表的条件是：________。

三、判断题

1.顺序存储方式只能用于存储线性结构。

2.顺序表和一维数组一样，都可以按下标随机（或直接）访问。 3.顺序表用一维数组作为存储结构，因此顺序表是一维数组。 4.通常使用两个类来协同表示单链表，即链表的结点类和链表类。

5.在单链表中，任何两个元素的存储位置之间都有固定的联系，因为可以从头结点进行查找任何一个元素。 6.线性表采用顺序存储表示时，必须占用一片连续的存储单元。

7

7.链式存储在插入和删除时需要保持物理存储空间的顺序分配，不需要保持数据元素之间的逻辑顺序。 8．线性表的逻辑顺序与物理顺序总是一致的。 9．线性表的顺序存储表示优于链式存储表示。

10．线性表若采用链式存储表示时所有结点之间的存储单元地址可连续可不连续。

四、应用题

1．线性表的顺序存储表示和链式存储表示的特点比较。

2.这是一个统计单链表中结点的值等于给定值x的结点数的算法，其中while循环有错，请重新编写出正确的while循环。

int count ( ListNode * Ha, ElemType x ) { // Ha为不带头结点的单链表的头指针 int n = 0;

while ( Ha->link != NULL )

{ Ha = Ha->link; if ( Ha->data == x ) n++; return n; }

}

五、算法设计题

1．设带表头结点的双向链表的定义为 typedef int ElemType；

typedef struct dnode { file://双向链表结点定义 ElemType data； file://数据

struct dnode * lLink， * rLink； file://结点前驱与后继指针 DblNode；

typedef DblNode * DblList； file://双向链表

试设计一个算法，改造一个带表头结点的双向链表，所有结点的原有次序保持在各个结点的右链域rLink中，并利用左链域lLink把所有结点按照其值从小到大的顺序连接起来。

2．假设有两个按元素值递增次序排列的线性表，均以单链表形式存储。请编写算法将这两个单链表归并为一个按元素值递减次序排列的单链表，并要求利用原来两个单链表的结点存放归并后的单链表。 3. 已知L1、L2分别为两循环单链表的头结点指针，m,n分别为L1、L2表中数据结点个数。要求设计一算法，用最快速度将两表合并成一个带头结点的循环单链表。

8

4. 顺序结构线性表LA与LB的结点关键字为整数。LA与LB的元素按非递减有序，线性表空间足够大。试用类C语言给出一种高效算法，将LB中元素合到LA中，使新的LA的元素仍保持非递减有序。高效指最大限度的避免移动元素。

5. 设 Listhead为一单链表的头指针，单链表的每个结点由一个整数域DATA和指针域NEXT组成，整数在单链表中是无序的。编一类C过程，将 Listhead链中结点分成一个奇数链和一个偶数链，分别由P,Q指向，每个链中的数据按由小到大排列。程序中不得使用 NEW过程申请空间。 6. 试编写在带头结点的单链表中删除（一个）最小值结点的（高效）算法。

7. 已知非空线性链表由list指出，链结点的构造为（data,link）.请写一算法，将链表中数据域值最小的那个链结点移到链表的最前面。要求：不得额外申请新的链结点。

8. 已知p指向双向循环链表中的一个结点，其结点结构为data、llink、rlink三个域，写出算法change(p),交换p所指向的结点和它的前缀结点的顺序。

9. 线性表(a1,a2,a3,?,an)中元素递增有序且按顺序存储于计算机内。要求设计一算法完成： （1） 用最少时间在表中查找数值为x的元素。 （2） 若找到将其与后继元素位置相交换。

（3） 若找不到将其插入表中并使表中元素仍递增有序。

10 已知两个单链表A和B,其头指针分别为heada和headb，编写一个过程从单链表A中删除自第i个元素起的共len个元素，然后将单链表A插入到单链表B的第j个元素之前。

11．在一个递增有序的线性表中，有数值相同的元素存在。若存储方式为单链表，设计算法去掉数值相同的元素，使表中不再有重复的元素。例如：（7，10，10，21，30，42，42，42，51，70）将变作（7，10，21，30，42，51，70），分析算法的时间复杂度。

12. 函数reverse()实现将已知不带头结点的单链表的链接顺序颠倒的功能，即第一表元变为最后表元，第二表元变为倒数第二表元，??，最后表元变为第一表元。函数中h为链表的头指针，q2为第一个尚未颠倒的链表表元，q1为已颠倒链表的第一个链表表元。

Typedef struct node { int data; struct node *next; }node; //链表的形式说明 void reverse(node h) { node *q1, *q2;

9

; q1=NULL;

while (q2!=NULL) { ; ; h=q2;

;

}

=q1;

}

13. 设有一个表头为first的单链表。试设计一个算法，通过遍历一趟链表，将链表中所有结点按逆序链接。

14．阅读下面的算法

LinkList mynote(LinkList L) {//L是不带头结点的单链表的头指针 if(L&&L->next){

q=L；L=L－>next；p=L； S1： while(p－>next) p=p－>next； S2： p－>next=q；q－>next=NULL； }

return L； }

请回答下列问题： （1）说明语句S1的功能； （2）说明语句组S2的功能；

（3）设链表表示的线性表为（a1,a2, ?,an）,写出算法执行后的返回值所表示的线性表。 15.一个顺序存储的线性表内存储整数，编写算法，将负整数移到线性表的前边，非负整数移到线性表的

10

后边。

Move5（list r，int n）

11

第三章 栈和队列

一、单项选择题

1. 对于栈操作数据的原则是（ ）。

A. 先进先出 B. 后进先出 C. 后进后出 D. 不分顺序 1.链式栈与顺序栈相比，一个比较明显的优点是( ) A.插入操作更加方便 B.通常不会出现栈满的情况 C.不会出现栈空的情况 D.删除操作更加方便

2.在一个顺序存储的循环队列中，队头指针指向队头元素的( )

A.前一个位置 B.后一个位置 C.队头元素位置 D.队尾元素的前一位置 3.栈和队列都是（ ）。

A.顺序存储的线性结构 B.链式存储的线性结构 C.限制存储点的线性结构 D.限制存储点的非线性结构

4.设输入序列为1,2,3,4,5，借助一个栈不可能得到的输出序列是( ) 。 A.1,2,3,4,5 B.1,4,3,2,5 C.4，1,3,2,5 D.1,3,2,5,4

5. 假定一个带头结点的链式队列的队头和队尾指针分别为front和rear，则判断队空的条件为( )。 A. front == rear B. front != NULL C. rear != NULL D. front == NULL

6. 设有一个递归算法如下 int fact(int n) { //n大于等于0 if(n<=0) return 1; else return n*fact(n-1); }则计算fact(n)需要调用该函数的次数为（ ）次。 A．n B．n+1 C．n+2 D．n-1 7.向顺序栈中压入新元素时，应当（ ）。

A．先移动栈顶指针，再存入元素 B．先存入元素，再移动栈顶指针 C．先后次序无关紧要 D．同时进行 8.用单链表表示的链式队列的队头在链表的（ ）位置。

A．链头 B．链尾 C．链中 D.任意位置 9.当利用大小为n的数组顺序存储一个队列时，该队列的最大长度为（ ）。 A. n-2 B. n-1

C. n

D. n+1

10．设数组data[m]作为循环队列SQ的存储空间，front为队头指针，rear为队尾指针，则执行出队操作后其头指针front值为（ ）

A．front=front+1 B．front=(front+1)%(m-1) C．front=(front-1)%m D．front=(front+1)%m 11．由两个栈共享一个向量空间的好处是：（ ）

A．减少存取时间，降低下溢发生的机率 B．节省存储空间，降低上溢发生的机率

12

C．减少存取时间，降低上溢发生的机率 D．节省存储空间，降低下溢发生的机率 12. 对于栈操作数据的原则是（ ）。

A. 先进先出 B. 后进先出 C. 后进后出 D. 不分顺序

13. 在作进栈运算时,应先判别栈是否( ① ),在作退栈运算时应先判别栈是否( ② )。当栈中元素为n个,作进栈运算时发生上溢,则说明该栈的最大容量为( ③ )。为了增加内存空间的利用率和减少溢出的可能性,由两个栈共享一片连续的内存空间时,应将两栈的 ( ④ )分别设在这片内存空间的两端,这样,当( ⑤ )时，才产生上溢。

①, ②: A. 空 B. 满 C. 上溢 D. 下溢 ③: A. n-1 B. n C. n+1 D. n/2 ④: A. 长度 B. 深度 C. 栈顶 D. 栈底 ⑤: A. 两个栈的栈顶同时到达栈空间的中心点.

B. 其中一个栈的栈顶到达栈空间的中心点.

C. 两个栈的栈顶在栈空间的某一位置相遇.

D. 两个栈均不空,且一个栈的栈顶到达另一个栈的栈底. 14. 输入序列为ABC，可以变为CBA时，经过的栈操作为（ ）

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

15. 若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3，当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为多少？( ) A. 1和 5 B. 2和4 C. 4和2 D. 5和1 16. 栈和队列的共同点是（ ）。

A. 都是先进先出 B. 都是先进后出 C. 只允许在端点处插入和删除元素 D. 没有共同点

18. 若一个栈的输入序列为1,2,3,?,n，输出序列的第一个元素是i，则第j个输出元素是（ ）。 A. i-j-1 B. i-j C. j-i+1 D. 不确定的

19. 某堆栈的输入序列为a, b，c ，d,下面的四个序列中，不可能是它的输出序列的是（ ）。 A. a，c，b，d B. b, c，d，a C. c, d，b, a D. d, c，a，b 20. 若一个栈以向量V[1..n]存储，初始栈顶指针top为n+1，则下面x进栈的正确操作是( )。 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

21. 若栈采用顺序存储方式存储，现两栈共享空间V[1..m]，top[i]代表第i个栈( i =1,2)栈顶，栈1的底

13

在v[1]，栈2的底在V[m]，则栈满的条件是（ ）。

A. |top[2]-top[1]|=0 B. top[1]+1=top[2] C. top[1]+top[2]=m D. top[1]=top[2] 22. 栈在（ ）中应用。

A. 递归调用 B. 子程序调用 C. 表达式求值 D. A，Ｂ，Ｃ 23. 一个递归算法必须包括（ ）。

A. 递归部分 B. 终止条件和递归部分 C. 迭代部分 D.终止条件和迭代部分 24. 执行完下列语句段后，i值为：（ ） 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. 无限递归 25. 表达式a*(b+c)-d的后缀表达式是( )。

A．abcd*+- B. abc+*d- C. abc*+d- D. -+*abcd

26. 设计一个判别表达式中左，右括号是否配对出现的算法，采用（ ）数据结构最佳。 A．线性表的顺序存储结构 B. 队列 C. 线性表的链式存储结构 D. 栈

27. 用链接方式存储的队列，在进行删除运算时（ ）。 A. 仅修改头指针 B. 仅修改尾指针 C. 头、尾指针都要修改 D. 头、尾指针可能都要修改

28. 用不带头结点的单链表存储队列时,其队头指针指向队头结点,其队尾指针指向队尾结点，则在进行删除操作时( )。

A．仅修改队头指针 B. 仅修改队尾指针

C. 队头、队尾指针都要修改 D. 队头,队尾指针都可能要修改

29. 递归过程或函数调用时，处理参数及返回地址，要用一种称为（ ）的数据结构。 A．队列 B．多维数组 C．栈 D. 线性表

30. 假设以数组A[m]存放循环队列的元素,其头尾指针分别为front和rear，则当前队列中的元素个数为（ ）。

A．(rear-front+m)%m B．rear-front+1 C．(front-rear+m)%m D．(rear-front)%m

31. 若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3，当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为多少？( )

14

A. 1和 5 B. 2和4 C. 4和2 D. 5和1

32. 已知输入序列为abcd 经过输出受限的双向队列后能得到的输出序列有（ ）。 A. dacb B. cadb C. dbca D. bdac E. 以上答案都不对 33. 最大容量为n的循环队列，队尾指针是rear，队头是front，则队空的条件是 （ ）。

A. (rear+1) MOD n=front B. rear=front

C．rear+1=front D. (rear-l) MOD n=front

34. 设栈S和队列Q的初始状态为空，元素e1，e2，e3，e4,e5和e6依次通过栈S，一个元素出栈后即进队列Q，若6个元素出队的序列是e2，e4，e3,e6,e5,e1则栈S的容量至少应该是( )。 A． 6 B. 4 C. 3 D. 2

二、填空题

1．若一个栈以数组V[1..n]存储，初始栈顶指针为top，元素X的入栈操作为______________。 2. 栈是一种限定在表的一端进行插入和删除的线性表，又被称为___________的线性表。 3. 如果一个对象部分地包含自己，或自己定义自己，则称这个对象是_________的对象。

4.设有一个顺序栈S，元素S1，S2，S3，S4，S5，S6依次进栈，如果6个元素的出栈顺序为S2，S3，S4，S6，S5，S1，则顺序栈的容量至少应为 。

5.通常程序在调用另一个程序时，都需要使用一个 来保存被调用程序内分配的局部变量、形式参数的存储空间以及返回地址。

6.在一个链式栈中，若栈顶指针等于NULL则为________。 7．栈顶的位置是随着_____操作而变化的。

8．在队列的顺序存储结构中，当插入一个新的队列元素时，尾指针 ，当删除一个队列元素时，头指针 。

9.循环队列用数组A[0..m-1]存放其元素值。已知其头尾指针分别是front和rear，则当前队列中的元素个数是 ，判断队空的条件是 。

10．循环队列Q中，front和rear分别指示队列头元素及队尾元素的位置，最大队列长度为maxsize，则判断队空的条件是 ，队满的条件是 。

11.队列的插入操作在 进行，删除操作在 进行。

12.在队列的顺序存储结构中，当插入一个新的队列元素时，尾指针 ，当删除一个队列元素时，头指针 。

13．栈是___ ____的线性表，其运算遵循_______的原则。 14．____ ___是限定仅在表尾进行插入或删除操作的线性表。

15. 设有一个空栈，栈顶指针为1000H(十六进制)，现有输入序列为1，2，3，4，5，经过

15

PUSH,PUSH,POP,PUSH,POP,PUSH,PUSH之后，输出序列是_______，而栈顶指针值是_______H。设栈为顺序栈，每个元素占4个字节。

16. 当两个栈共享一存储区时，栈利用一维数组stack(1,n)表示，两栈顶指针为top[1]与top[2]，则当栈1空时，top[1]为_______，栈2空时 ，top[2]为_______，栈满时为_______。 17．两个栈共享空间时栈满的条件_______。

18．在作进栈运算时应先判别栈是否 ;在作退栈运算时应先判别栈是否 ；当栈中元素为n个，作进栈运算时发生上溢，则说明该栈的最大容量为 。为了增加内存空间的利用率和减少溢出的可能性，由两个栈共享一片连续的空间时，应将两栈的 分别设在内存空间的两端，这样只有当 时才产生溢出。

19. 多个栈共存时，最好用_______作为存储结构。

20．表达式23+((12*3-2)/4+34*5/7)+108/9的后缀表达式是_______。

21. 循环队列的引入，目的是为了克服_______。 22. 已知链队列的头尾指针分别是f和r，则将值x入队的操作序列是_______。 23．区分循环队列的满与空，只有两种方法，它们是______和______。

24. 设循环队列存放在向量sq.data[0:M]中，则队头指针sq.front在循环意义下的出队操作可表示为_______，若用牺牲一个单元的办法来区分队满和队空（设队尾指针sq.rear）,则队满的条件为_______。 25．表达式求值是_______应用的一个典型例子。

三、判断题

1.栈和队列都是顺序存取的的线性表，但它们对存取位置的限制不同。 2.通常递归的算法简单、易懂、容易编写，但执行的效率不高。 3.在一个顺序存储的循环队列中, 队头指针指向队头元素的后一个位置。 4.在用循环单链表表示的链式队列中，可以不设队头指针，仅在链尾设置队尾指针。 5.用非递归方法实现递归算法时一定要使用递归工作栈。 6．队列只允许在表的一端进行插入，而在另一端删除元素。

四、应用题

1．设有一个顺序栈S，元素s1， s2， s3， s4， s5， s6依次进栈，如果6个元素的出栈顺序为s2， s3， s4， s6， s5， s1，则顺序栈的容量至少应为多少？ 2. 试推导出当总盘数为n的Hanoi塔的移动次数。

3. 用栈实现将中缀表达式8-(3+5)*(5-6/2)转换成后缀表达式，画出栈的变化过程图。

16

4. 举例说明顺序队的“假溢出”现象，并给出解决方案。

五、算法设计题

1. 设有两个栈S1,S2都采用顺序栈方式，并且共享一个存储区[O..maxsize-1],为了尽量利用空间，减少溢出的可能，可采用栈顶相向，迎面增长的存储方式。试设计S1,S2有关入栈和出栈的操作算法。 2. 设从键盘输入一整数的序列：a1, a2, a3，?，an,试编写算法实现：用栈结构存储输入的整数，当ai≠-1时，将ai进栈；当ai=-1时，输出栈顶整数并出栈。算法应对异常情况（入栈满等）给出相应的信息。 3. 设表达式以字符形式已存入数组E[n]中，‘#’为表达式的结束符，试写出判断表达式中括号（‘（’和‘）’）是否配对的C语言描述算法：EXYX(E); (注：算法中可调用栈操作的基本算法。) 4. 如果允许在循环队列的两端都可以进行插入和删除操作。要求： （1）写出循环队列的类型定义；

（2）写出“从队尾删除”和“从队头插入”的算法。

5．线性表中元素存放在向量A（1,?,n）中，元素是整型数。试写出递归算法求出A中的最大和最小元素。 6. 已知求两个正整数m与n的最大公因子的过程用自然语言可以表述为反复执行如下动作：第一步：若n等于零，则返回m；第二步：若m小于n，则m与n相互交换；否则，保存m，然后将n送m，将保存的m除以n的余数送n。

（1）将上述过程用递归函数表达出来（设求x除以y的余数可以用x MOD y 形式表示）。 （2）写出求解该递归函数的非递归算法。

7．设计算法以求解从集合{1..n}中选取k（k<=n）个元素的所有组合。例如，从集合{1..4}中选取2个元素的所有组合的输出结果为：1 2，1 3，1 4，2 3， 2 4，3 4。 8．假设两个队列共享一个循环向量空间， 其类型Queue2定义如下： typedef struct{

DateType data[MaxSize]； int front,rear； }Queue2；

对于i=0或1，front[i]和rear[i]分别为第i个队列的头指针和尾指针。请对以下算法填空，实现第i个队列的入队操作。

int EnQueue (Queue2*Q,int i,DateType x)

{//若第 i个队列不满，则元素x入队列，并返回1；否则返回0 if(i<0||i>1)return 0；

17

if(Q－>rear[i]==Q－>front[ ① ]return0； Q－>data[ ② ]=x； Q－>rear[i]=[ ③ ]; return 1； )

六、简答题

1.（1）什么是递归程序？

（2）递归程序的优、缺点是什么？

（3）递归程序在执行时，应借助于什么来完成？

（4）递归程序的入口语句、出口语句一般用什么语句实现？

2. 当过程P递归调用自身时，过程P内部定义的局部变量在P的2次调用期间是否占用同一数据区？为什么？ 3. 在一个算法中需要建立多个堆栈时可以选用下列三种方案之一，试问：这三种方案之间相比较各有什么优缺点？

（1）分别用多个顺序存储空间建立多个独立的堆栈； （2）多个堆栈共享一个顺序存储空间； （3）分别建立多个独立的链接堆栈。

18

第四章 串

一、单项选择题

1．串是一种特殊的线性表，其特殊性体现在（ ）

A．可以顺序存储 B．数据元素是一个字符C．可以链接存储 D．数据元素可以是多个字符 2．如下陈述中正确的是（ ）

A．串是一种特殊的线性表 B．串的长度必须大于零 C．串中元素只能是字母 D．空串就是空白串

3．若目标串的长度为n，模式串的长度为[n/3]，则执行模式匹配算法时，在最坏情况下的时间复杂度是（ ）

A．O（ ） B．O（n） C．O（n） D．O（n） 4.设有两个串 p和q,求q在p中首次出现的位置的运算称作 。 A.连接 B.模式匹配 C.求串长 D.求子串 5.设字符串 S1=―ABCDEFG‖，S2=―PQRST‖，则运算：

S=CONCAT（SUBSTR（S1，2，LEN（S2））, SUBSTR（S1，LEN（S2），2））；后的串值为 。 A.BCDEF B.BCDEFG C.BCDPQRST D.BCDEFEF

2

3

二、填空题

1. 空格串是指 ，其长度等于 。 2．在串S=“structure”中，以t为首字符的子串有_____个。

三、判断题

1.空格串和空串的长度均为 1。

2.串是一种特殊的线性表，其特殊性体现在数据元素可以使多个字符。 3.判断两个串是否相等，只需要判断这两个串是否包含相同的字符即可。

四、应用题

1．设S1 =―Data Structure Course‖，S2 =―Structure‖，S3 =―Base‖，求： （1）Length(S1)； （2）Compare(S2, S3)； （3）Insert(S1, 5, S3)； （4）Delete(S1, 5, 9)；

（5）SubString(S1, 5, 9, T)； （6）Search(S1, 0, S2)； （7）Replace(S1, 0, S2, S3) 2.令t1=―aaab‖, t2=―abcabaa‖, t3=―abcaabbabcabaacba‖，试分别求出他们的next[j]值。

19

五、算法设计题

1.设串采用静态数组存储结构，编写函数实现两个串的比较Compare(S, T)。要求比较结果有等于和不等于两种情况。

2.设串采用静态数组存储结构，编写函数实现两个串的比较Compare(S, T)。要求比较结果有大于、等于和小于三种情况。

3.设串采用静态数组存储结构，编写函数实现串的替换Replace(S, start, T, V)，即要求在主串S中，从位置start开始查找是否存在子串T，若主串S中存在子串T，则用子串V替换子串T，且函数返回1；若主串S中不存在子串T，则函数返回0。

4.设字符串采用单字符的链式存储结构，编写删除串s从位置i开始长度为k的子串的算法。 5．下列算法的功能是比较两个链串的大小，其返回值为：

comstr(s1,s2)=-1（s1s2) 请在空白处填入适当的内容。

int comstr(LinkString s1,LinkString s2) {//s1和s2为两个链串的头指针 while(s1&&s2){

if(s1－>datedate)return －1； if(s1－>date>s2－>date)return 1； ① ； ② ； }

if( ③ )return －1； if( ④ )return 1； ⑤ ； }

六、简答题

1.什么叫串？串和字符在存储方法上有什么不同？空串和空格串是否相同，为什么？ 3.串是由字符组成的，长度为1的串和字符是否相同。为什么？

4.串是不定长的，表示串的长度有几种方法？C语言中的串采用哪种方法？

5.可以说串是数据类型固定为字符类型的线性表，但是串操作和线性表操作的主要不同之处在哪里？ 6.可以用几种存储方法存储串？

7.分别写出串的静态数组存储结构和串的动态数组存储结构的结构体定义。

20

8.为什么动态数组结构下串的实现要增加撤消函数？

21

第五章 数组和广义表

一、单项选择题

1.设有一个二维数A[m][n],假设A[0][0]存放位置在644(10),A[2][2]存放位置在676(10),每个元素占一个空间，则A[4][5]在（ ）位置，(10)表明用10进数表示。 A.692(10) B.626(10) C.709(10) D.724(10)

2．二维数组A[10][20]采用行优先顺序存储，每个元素占1个存储单元，并且初始地址是200，则A[6][12]的地址是（ ）

3.设有50行60列的二维数组A[50][60]，其元素长度为4字节，按行优先顺序存储，基地址为200，则元素A[18][25]的存储地址为（ ）。

A．3700 B．4376 C．3900 D．4620 5.若采用邻接矩阵法存储一个N个顶点的无向图，则该邻接矩阵是一个( ) A.上三角矩阵 B.稀疏矩阵 C.对角矩阵 D.对称矩阵 6.稀疏矩阵一般的压缩存储方法有两种，即（ ）。

A．二维数组和三维数组 B三元组和散列 C．三元组和十字链表 D散列和十字链表 7．一个非空广义表的表头（ ）

A．不可能是子表 B．只能是子表 C．只能是原子 D．可以是子表或原子

8.设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储，a11为第一元素，其存储地址为1，每个元素占一个地址空间，则a85的地址为（ ）。

A. 13 B. 33 C. 18 D. 40

9. 设有数组A[i,j]，数组的每个元素长度为3字节，i的值为1到8 ，j的值为1到10，数组从内存首地址BA开始顺序存放，当用以列为主存放时，元素A[5，8]的存储首地址为( )。 A. BA+141 B. BA+180 C. BA+222 D. BA+225

10. 假设以行序为主序存储二维数组A=array[1..100，1..100]，设每个数据元素占2个存储单元，基地址为10，则LOC[5，5]=（ ）。

A. 808 B. 818 C. 1010 D. 1020

11. 数组A[0..5,0..6]的每个元素占五个字节，将其按列优先次序存储在起始地址为1000的内存单元中，则元素A[5，5]的地址是( )。

A. 1175 B. 1180 C. 1205 D. 1210

12. 将一个A[1..100，1..100]的三对角矩阵，按行优先存入一维数组B[1‥298]中，A中元素A6665（即该元素下标i=66，j=65），在B数组中的位置K为（ ）。 A. 198 B. 195 C. 197

22

13. 二维数组A的每个元素是由6个字符组成的串，其行下标i=0,1,?,8,列下标j=1,2,?,10。若A按行先存储，元素A[8,5]的起始地址与当A按列先存储时的元素（ ）的起始地址相同。设每个字符占一个字节。

A. A[8,5] B. A[3,10] C. A[5,8] D. A[0,9]

14. 若对n阶对称矩阵A以行序为主序方式将其下三角形的元素(包括主对角线上所有元素)依次存放于一维数组B［1..(n(n+1))/2］中，则在B中确定aij（i

15. 设A是n*n的对称矩阵，将A的对角线及对角线上方的元素以列为主的次序存放在一维数组B[1..n(n+1)/2]中，对上述任一元素aij(1≤i，j≤n，且i≤j)在B中的位置为( )。 A. i(i-l)/2+j B. j(j-l)/2+i C. j(j-l)/2+i-1 D. i(i-l)/2+j-1

16. A[N，N]是对称矩阵，将下面三角（包括对角线）以行序存储到一维数组T[N（N+1）/2]中，则对任一上三角元素a[i][j]对应T[k]的下标k是（ ）。

A. i（i-1）/2+j B. j（j-1）/2+i C. i（j-i）/2+1 D. j（i-1）/2+1 17. 对稀疏矩阵进行压缩存储目的是（ ）。

A．便于进行矩阵运算 B．便于输入和输出 C．节省存储空间 D．降低运算的时间复杂度 18. 已知广义表L=（（x,y,z），a，（u，t，w）），从L表中取出原子项t的运算是（ ）。 A. head（tail（tail（L））） B. tail（head（head（tail（L）））） C. head（tail（head（tail（L）））） D. head（tail(head（tail（tail（L）））)） 19.已知广义表LS＝((a,b,c),(d,e,f)),运用head和tail函数取出LS中原子e的运算是( )。 A. head(tail(LS)) B. tail(head(LS))

C. head(tail(head(tail(LS))) D. head(tail(tail(head(LS)))) 20.广义表A=(a,b,(c,d),(e,(f,g))),则下面式子的值为（ ）。 Head(Tail(Head(Tail(Tail(A)))))

A. (g) B. (d) C. c D. d 21.已知广义表: A=(a,b), B=(A,A), C=(a,(b,A),B), 求下列运算的结果: tail(head(tail(C))) =( )。

A.（a） B. A C. a D. (b) E. b F. (A) 22. 广义表L=（a，（b，c）），进行Tail（L）操作后的结果为（ ）。 A. c B. b，c C.（b，c） D.（（b，c）） 23. 广义表（（a,b,c,d））的表头是（ ），表尾是（ ）。 A. a B.（） C.（a,b,c,d） D.（b,c,d）

23

24. 设广义表L=（（a,b,c）），则L的长度和深度分别为（ ）。 A. 1和1 B. 1和3 C. 1和2 D. 2和3 25. 下面说法不正确的是( )。

A. 广义表的表头总是一个广义表 B. 广义表的表尾总是一个广义表 C. 广义表难以用顺序存储结构 D. 广义表可以是一个多层次的结构

二、填空题

1.二维数组是一种非线性结构，其中的每一个数组元素最多有_________个直接前驱(或直接后继)。 2．假设有二维数组A6*8，每个元素用相邻的6个字节存储，存储器按字节编址。已知A00的存储位置为1000，那么按行优先存储时，元素a14的存储地址为 ，按列优先存储时，a47的地址为 。 3.将一个n阶三对角矩阵A的三条对角线上的元素按行压缩存放于一个一维数组B中，A[0][0]存放于B[0]中。对于任意给定数组元素B[K]，它应是A中第_________行的元素。

4.设有一个二维数组A[0..6,0..8]，A[0][0]存放位置为500，每个元素占2个字节，以行序为主序列，则A[4][5]在位置 。

5.在程序运行过程中不能扩充的数组是 分配的数组。这种数组在声明它时必须指定它的大小。

6.数组的存储结构采用_______存储方式。

8.设二维数组A[-20..30,-30..20], 每个元素占有4 个存储单元, 存储起始地址为200.如按行优先顺序存储,则元素 A[25,18]的存储地址为 ；如按列优先顺序存储,则元素A[-18,-25]的存储地址为 。 9. 用一维数组B与列优先存放带状矩阵A中的非零元素A[i,j] (1≤i≤n,i-2≤j≤i+2),B中的第8个元素是A 中的第 行，第 列的元素。

10．己知三对角矩阵A【1..9,1..9】的每个元素占2个单元，现将其三条对角线上的元素逐行存储在起始地址为1000的连续的内存单元中，则元素A[7,8]的地址为 。

11.设有一个10阶对称矩阵A采用压缩存储方式（以行为主序存储：a11=1），则a85 的地址为_______。 12.所谓稀疏矩阵指的是_______。 13.对矩阵压缩是为了_______。

14.当广义表中的每个元素都是原子时，广义表便成了_______。 15.广义表的表尾是指除第一个元素之外，_______。

16.广义表简称表，是由零个或多个原子或子表组成的有限序列，原子与表的差别仅在于 。为了区分原子和表，一般用 表示表，用 表示原子。一个表的长度是指 ，而表的深度是指 。

17. 广义表的 定义为广义表中括弧的重数。

24

18．设广义表L=((),()), 则head(L)是 ；tail(L)是 ；L的长度是 ；深度是 。

19. 已知广义表A=(9,7,( 8,10,(99)),12)，试用求表头和表尾的操作Head( )和Tail( )将原子元素99从A中取出来 。 20. 广义表的深度是_______。

21. 广义表A=（（（a，b），（c，d，e））），取出A中的原子e的操作是: 。 22.广义表(a,(a,b),d,e,((i,j),k))的长度是 ，表头是 ，表尾是 。 23.广义表A（（a，b，c），（d，e，f））的表尾为 。

三、判断题

2.二维数组是数组元素为一维数组的线性表，因此它是线性结构。 3．广义表的表尾可以是原子也可以是列表。

4.一个广义表的表尾总是一个广义表。 5．二维数组是其数组元素为线性表的线性表。

6．每种数据结构都应具备三种基本运算：插入、删除和搜索。

7.数组可看成线性结构的一种推广，因此与线性表一样，可以对它进行插入、删除等操作。 8.数组元素之间的关系，既不是线性的，也不是树形的。

1.数组是一种复杂的数据结构，数组元素之间的关系既不是线性的也不是树形的。

四、应用题

1. 二维数组A[10][20]，按行存放于一个连续的存储空间中，A[0][0]的存储地址是200，每个数组元素占1个存储字，则A[6][2]的存储字地址是多少。

2.画出广义表A=(()，(e),(a,(b,c,d)))的链式存储结构的示意图。

3．画出下列广义表的共享结构图形表示P=（（（z）,(x,y)）,((x,y),x),(z)）。

4. 若按照压缩存储的思想将n×n阶的对称矩阵A的下三角部分（包括主对角线元素）以行序为主序方式存放于一维数组B[1..n(n+1)/2]中，那么，A中任一个下三角元素aij(i≥j),在数组B中的下标位置k是什么？ 5. 求下列广义表的运算结果。 （1）CAR(CDR(((a,b),(c,d),(e,f)))) （2）CDR(CAR(((a,b),(c,d),(e,f)))) （3）CAR(CDR(CAR(((a,b),(e,f))))) （4）CDR(CAR(CDR(((a,b),(e,f))))) （5）CDR(CDR(CAR(((a,b),(e,f)))))

25

12.对于一个具有 n 个结点的二叉树，当它储存在二叉树表中时，其指针字段的总数为______ 个，其中________个用于链接孩子点，_____________个空闲，

13．一棵深度为 K 的满二叉树结点总数为___________ ，一棵深度为 K 的完全二叉树的结点总数的最小值为________，最大值为____________。

14.如果 T2 是由有序树 T 转换而来的二叉树，那么 T 中结点的前序是 T2 中结点的 _______序。 15.具有 n 个结点的完全二叉树，若按层次从上到下 、从左到右对其编号（根结点为 1号），则编号最大的分支结点序号为_______ ，编号最小的分支结点序号为_______ ，编号最大的叶子结点序号为________ ，编号最小的叶子结点序号为___________ 。

16.有 m个叶子结点的哈夫曼树，其结点总数为________________ 。 17. 由三个结点构成的二叉树，共有_____________种不同的结构。

三、判断题

1.具有n个结点的完全二叉树的高度为?log2n??1。 2.有n个结点的不同的二叉树有n！棵。

3.在只有度为0和度为k的结点的k叉树中，设度为0的结点有n0个，度为k的结点有nk个，则有n0=nk+1。 4.完全二叉树的某结点若无左孩子，则它必是叶子结点。

5. 在一棵二叉树中，假定每个结点只有左子女，没有右子女，对它分别进行中序遍历和后序遍历，则具有相同的结果。

6.由树转化成二叉树，其根的右子女指针总是空的。

7.对于一棵具有n个结点，其高度为h的二叉树，进行任一种次序遍历的时间复杂度为O(h)。 8.在霍夫曼编码中，当两个字符出现的频率相同时，其编码也相同，对于这种情况应当特殊处理。 9．二叉树的中序和后序遍历序列可以唯一确定一棵二叉树。

四、应用题

1.假设一棵树的广义表表示为A（B（E），C（F（H，I，J），G），D），回答下列问题：

（1）该树的度（2）树的深度（3）终端结点的个数（4）单分支结点的个数（5）双分支结点的个数（6）三分支结点的个数（7）C结点的双亲（8）C结点的孩子结点

2. 已知一棵树边的集合为｛< I ， M >，< I ， N >,< E ， I >，< B ， E >，< B ， D>，< A ， B>，< G ， J >，< G ， K>，< C ， G>，< C ， F>，< H ， L>，< C ， H>，< A ， C >｝，画出这棵树，并回答下列问题： ? 哪个结点是根结点？ ? 哪些结点是叶子结点？

31

? 哪个结点是结点 G 的双亲结点？ ? 哪些结点是结点 G 的祖先结点？ ? 哪些结点是结点 G 的孩子结点？ ? 哪些结点是结点 E 的子孙结点？

? 哪些结点是结点 E 的兄弟结点？哪些是结点 F 的兄弟结点？ ? 结点 B 和 N 的层次分别是多少？ ? 树的深度是多少？

? 以结点 C 为根的子树的深度是多少？ 3. 某二叉树的结点数据采用顺序存储表示如下：

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 E A F D H C G I B (1)试画出此二叉树的图形表示。(2)写出结点D的双亲结点及左、右子女。 (3)将此二叉树看作森林的二叉树表示，试将它还原为森林。

4.假设一棵二叉树的中序序列DCBGEAHFIJK和后序序列为DCEGBFHKJIA请画出该二叉树，并给出先序序列。 5.按照下列给定二叉树的先序遍历序列、中序遍历和后序遍历序列，分别构造出二叉树。 ①先序遍历序列： EBADCFHGIKJ 中序遍历系列： ABCDEFGHIJK ②中序遍历序列： ACBGEDF 后序遍历序列： ABCDEFG

6.对上题①所得的二叉树，分别画出它的顺序存储结构和二叉链表。

7．已知一棵树的度为4，其中度为4的结点的数目为3，度为3的结点的数目为4，度为2的结点的数目为5，度为1的结点的数目为2，请求出该树中的叶子结点的数目。

8．如果已知一棵二叉树有20个叶子结点，有10个结点仅有左孩子，15个结点仅有右孩子，求出该二叉树的结点数目。

9．已知某完全二叉树有100个结点，试用三种不同的方法求出该二叉树的叶子结点数。

10．如果已知完全二叉树的第6层有5个叶子，试画出所有满足这一条件的完全二叉树，并指出结点数目最多的那棵完全二叉树的叶子结点数目。

11．在编号的完全二叉树中，判断编号为i和j的两个结点在同一层的条件是什么？ 12．设计算法以求解编号为i和j的两个结点的最近的公共祖先结点的编号。 13．分别求出下图中二叉树的三种遍历序列。

32

14．分别描述满足下面条件的二叉树的特征： （1）先序序列和中序序列相同。 （2）先序序列和后序序列相反。

15．证明：由二叉树的先序序列和中序序列能唯一确定一棵二叉树，并分别由下面的两个序列构造出相应的二叉树：

①先序：ABCDEFGHI ②先序：ABCDEFGHIJ 中序：ADECFBGIH 中序：BDECAGIJHF

16．证明：由二叉树的后序序列和中序序列能唯一确定一棵二叉树，并分别由下面的两个序列构造出相应的二叉树：

①后序：DCFEBIHGA ②后序：DECBGIHFA 中序：DCBFEAGHI 中序：DCEBAFHGI

17．已知一棵二叉树的先序、中序和后序序列如下，其中各有一部分未给出其值，请构造出该二叉树。

先序：A CDEF_H_J 中序：C_EDA_GFI_ 后序：C_ _BHGJI_ _

18．证明：任意一棵非空的二叉树的先序序列的最后一个结点一定是叶子结点。 19．用反例证明：由二叉树的先序序列和后序序列不能唯一确定一棵二叉树。 20．设计算法以输出二叉树中先序序列的前k（k>0）个结点的值。

21．设计算法按中序次序依次输出各结点的值及其对应的序号。例如，下图中的二叉树的输出结果是(C,1) (B,2) (E,3) (D,4) (F,5) (A,6) (H,7) (J,8) (I,9) (G,10)。

33

22．设计算法以输出每个结点到根结点之间的路径上的所有结点的值。

23．设计算法将一棵以二叉链表形式存储的二叉树转换为顺序存储形式存储到数组A[n]中，并将其中没有存放结点值的数组元素设置为NULL。

24．设计算法将一棵以顺序存储方式存储在数组A中的二叉树转换为二叉链表形式。

25．写出如下图树的先根遍历序列和后根遍历序列并将此树转化为二叉树：

26.已知某系统在通讯联络中只可能出现6种字符{a,b,c,d,e,f}，其概率分别为0.10，0.22，0.13，0.14，0.15，0.26，试画出赫夫曼树并设计赫夫曼编码。

27.假定用于通信的电文仅由8个字母a，b，c，d，e，d，f，g，h组成，各个字母在电文中出现的频率分别为5，23，3，6，10，11，36，4。试为这8个字母设计不等长Huffman编码，并输出该电文的总码数。 （1）Huffman树为：（2）Huffman编码为（3）电文总长度：

28．对给定的权值｛ 2 ， 3 ， 4 ， 7 ， 8 ， 9 ｝，构造出相应的赫夫曼树和赫夫曼编码，并求出带权路径的长度 WPL 。

29．将下图中的二叉树转换为对应的森林。

34

30．已知二叉树的存储结构为二叉链表，阅读下面算法。 typedef struct node { DateType data； Struct node * next； }ListNode；

typedef ListNode * LinkList ； LinkList Leafhead=NULL； void Inorder (BinTree T) {

LinkList s； if(T)

{

Inorder(T－>lchild)；

if ((!T－>lchild)&&(!T－>rchild))

{

s=(ListNode*)malloc(sizeof(ListNode))； s－>data=T－>data； s－>next=Leafhead； Leafhead=s； }

Inorder(T－>rchild)；

} }

对于如下所示的二叉树

（1）画出执行上述算法后所建立的结构；

35

本文来源：https://www.bwwdw.com/article/jtlg.html