数据结构习题集(2011-2012)doc

第一章概论 一、填空题

1、数据的存储结构可用四种基本的存储方法表示，分别是顺序、 链式 、 索引 和 散列。 2、一个算法具有有穷性、确定性、可行性，有零个或多个输入、有一个或多个输出5个特性。 3、数据结构包括数据的 逻辑结构 、存储结构 和 运算（或基本操作）三个方面的内容。 4、数据结构中评价算法的两个重要指标是 时间 效率和 空间 效率。 5、一个数据结构在计算机中的表示称为 存储结构 。 6、从逻辑上可以把数据结构分为线性结构、非线性结构两大类

7、数据项是数据中不可再分割的最小单位；数据元素是数据集合中的一个“个体”，是计算

机程序中加工处理的基本单位。

8、健壮性指算法对非法输入能适当地做出反应或进行处理，而不会产生莫名其妙的输出结果。 9、下列语句的时间复杂度是O（n2） for(i=1;i<=n;i++) for(j=1;j<=n;j++) {++x;}

二、单项选择题

1、数据结构中，与所使用的计算机无关的是数据的（ C ）结构。 A、存储 B、 物理 C、逻辑 D、物理和存储 2、算法分析的目的是（ C ）。

A、找出数据结构的合理性 B、 研究算法中的输入和输出的关系 C、 分析算法的效率以求改进 D、 分析算法的易懂性和文档性 3、计算机算法指的是（ C ）。

A、计算方法 B、排序方法 C、 解决问题的有限运算序列 D、调度方法 4、计算机算法必须具备输入、输出和（ B ）等5个特性。

A、可行性、可移植性和可扩充性 B、可行性、确定性和有穷性 C、确定性、有穷性和稳定性 D、易读性、稳定性和安全性 5、从逻辑上可以把数据结构分为（ C ）两大类。 A、动态结构、静态结构 B、顺序结构、链式结构 C、线性结构、非线性结构 D、初等结构、构造型结构 6、下列数据中，（ C ）是非线性数据结构。 A、栈 B、队列 C、完全二叉树 D、堆 7、算法分析的两个主要方面是（ A ）。

A、空间复杂性和时间复杂性 B、正确性和简明性

1

C、可读性和文档性 D、数据复杂性和程序复杂性 8、在下面程序段的时间复杂度（ D ）。 i=1; while(i<=n) i=i*3;

A、O(3n) B、O(n) C、O(n3) D、O(log3n) 9、在下面的程序段中，对x的赋值语句的频度为（ C ）。

for(i=1;i<=n;i++)

for(j=1;j<=n;j++)

x=x+1;

A、O(2n) B、O(n) C、O(n2) D、O(log2n) 10、下面关于算法说法错误的是（ D ）。

A、算法最终必须由计算机程序实现

B、为解决某问题的算法同为该问题编写的程序含义是相同的 C、算法的可行性是指指令不能有二义性 D、以上几个都是错误的

三、判断题

1、数据的逻辑结构说明数据元素之间的顺序关系,它依赖于计算机的储存结构.(×) 2、数据的逻辑结构是指数据的各数据项之间的逻辑关系；(×) 3、数据的物理结构是指数据在计算机内的实际存储形式。(√) 4、算法的优劣与算法描述语言无关，但与所用计算机有关。(×) 5、健壮的算法不会因非法的输入数据而出现莫名其妙的状态。(√)

6、算法可以用不同的语言描述，如果用C 语言或PASCAL语言等高级语言来描述，则算法实际上就是程序了。(×)

7、数据元素是数据中不可再分割的最小单位。(×)

8、算法中的每一步，必须有确切的含义，不能产生理解上的二义性。(√)

9、采用事后统计法进行算法分析时，不会因为软硬件环境的改变而影响分析结果。(×)

10、算法的时间与空间效率是指将算法变换为程序后，该程序在计算机上运行时所花费的时间及所占据空间的度量。(√)

四、简答题

1、当为解决某一问题而选择数据结构时，应从哪些方面考虑？

答：通常考虑算法所需要的存储空间量和算法所需要的时间量。后者又涉及到四方面：程序运行时所需输入的数据总量，对源程序进行编译所需时间，计算机执行每条指令所需时间和程序中指令重复执行的次数。

2

第2章 线性表 一、填空

1、当线性表的元素总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素时，应采用 顺序 存储结构。

2、顺序存储的线性表存储结构的特点是：用 物理位置的相邻 表示元素之间的关系的，在顺序表中插入或删除一个元素，移动的元素个数与 表长 和 该元素在表中的位置 有关。 3、设单链表的结点结构为(data，next)，next为指针域，指针p指向单链表中data为x的结点，指针q指向data为y的新结点，若将结点y插入结点x之后，则需要依次执行以下语句：__ q->next=p->next; _ p->next=q

4、在顺序表中访问任意一结点的时间复杂度均为 O(1) ，因此，顺序表也称为 随机存取的数据结构。

5、链式存储结构的特点是利用__指针 来表示数据元素之间的逻辑关系。在单链表中，除了首元结点外，任一结点的存储位置由 其直接前驱结点的链域的值 指示，查找结点都必须从头结点开始，因此，链表也称为 顺序存取 的数据结构。

6、已知指针p指向单链表L中的某结点，u是P的直接后继，删除u的语句是：p->next=u->next; free(u);

7、带头结点的双循环链表L中只有一个元素结点的条件是：L->next->next==L；

8、在顺序表L=（a1,a2,?,an）中，假定删除表中任一元素的概率相同，则删除一个元素平均需要移动元素的个数是（n-1）/2_；第i个元素（1<=i<=n）之前插入一个元素时，需向后移动n-i+1_个元素。如果要在第1个元素前插入一个元素，要后移 n 个元素；删除第i个元素(1≤i≤n)时，需向前移动 n-i 个元素。

9、在n个结点的单链表中要删除已知结点*p，需找到它的前驱结点的地址，其时间复杂度为O（n），在给定值为x的结点后插入一个新结点的时间复杂度为 O(n)_。

10、在非空的线性表中，有且仅有一个没有直接前趋的开始结点 a1 ；有且仅有一个没有直接后继的终端结点 an ；其余的内部结点ai(2≤i≤n-1)都有且仅有一个直接前趋ai-1和一个直接后继ai+1。

11、双向链表结构的对称性可用下式描述：p->prior)->next=p=(p->next)->prior

二、判断正误

1、线性表的特点是每个元素都有一个前驱和一个后继。（×） 2、链表的物理存储结构具有同链表一样的顺序。（×）

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

4、取线性表的第i个元素的时间同i的大小有关。 （×）

3

5、顺序表结构适宜于进行顺序存取，而链表适宜于进行随机存取。（×） 6、顺序存储方式的优点是存储密度大，且插入、删除运算效率高。（×）

7、链表是采用链式存储结构的线性表,进行插入、删除操作时，在链表中比在顺序存储结构中效率高。(√)

8、线性表在顺序存储时，逻辑上相邻的元素未必在存储的物理位置次序上相邻。（×） 9、顺序存储方式只能用于存储线性结构。（×） 10、线性表的逻辑顺序与存储顺序总是一致的。（×） 11、链表中的头结点仅起到标识的作用。（×）

12、顺序存储结构的主要缺点是不利于插入或删除操作。(√)

13、线性表采用链表存储时，结点和结点内部的存储空间可以是不连续的。(√) 14、顺序存储方式插入和删除时效率太低，因此它不如链式存储方式好。（×） 15、对任何数据结构链式存储结构一定优于顺序存储结构。（×） 16、顺序存储的线性表，优点是空间利用率很高。(×)

17、在单链表上插入、删除一个结点，必须知道其前驱结点。(√)

18、遍历操作时，循环链表和非循环链表的终止条件判断是一样的。(×)19、顺序表能按元素序号随机访问，而链表只能顺序查找。(√)

20、在顺序表中做插入删除操作时，平均移动大约表中一半的元素，因此对n较大的顺序表效率低。(√)

三、单项选择题

1、数据在计算机存储器内表示时，物理地址与逻辑地址相同并且是连续的，称之为（ C ）。 A、存储结构 B、逻辑结构 C、顺序存储结构 D、链式存储结构

2、一个向量第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是（ B ）

A、110 B、108 C、100 D、120

3、在n个结点的顺序表中，算法的时间复杂度是O（1）的操作是（ A ）。 A、访问第i个结点（1≤i≤n）和求第i个结点的直接前驱（2≤i≤n） B、在第i个结点后插入一个新结点（1≤i≤n） C、删除第i个结点（1≤i≤n） D、将n个结点从小到大排序

4、向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动（ B ）个元素。

A、8 B、63.5 C、63 D、7

5、线性表（ a1,a2,?,an）以链接方式存储时，访问第i位置元素的时间复杂性为（ C ）。

A、O（i） B、O（1） C、O（n） D、O（i-1）

6、链表是一种采用（ B ）存储结构存储的线性表。

4

A、顺序 B、链式 C、星式 D、网状

7、线性表若采用链式存储结构时，要求内存中可用存储单元的地址（ D ）。 A、必须是连续的 B、部分地址必须是连续的 C、一定是不连续的 D、连续或不连续都可以

8、线性表Ｌ在（ B ）情况下适用于使用链式结构实现。 A、需经常修改Ｌ中的结点值 B、需不断对Ｌ进行删除插入 C、Ｌ中含有大量的结点 D、Ｌ中结点结构复杂 9、单链表的存储密度（ C ）。

A、大于1 B、等于1 C、小于1 D、不能确定

10、对于一个头指针为head的带头结点的单链表，判定该表为空表的条件是（ B ） A、head==NULL B、head→next==NULL C、head→ext==head D、head!=NULL 11、下面关于线性表的叙述中，错误的是哪一个？（ B ） A、线性表采用顺序存储，必须占用一片连续的存储单元。 B、线性表采用顺序存储，便于进行插入和删除操作。 C、线性表采用链接存储，不必占用一片连续的存储单元。 D、线性表采用链接存储，便于插入和删除操作。

12、某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（ D ）存储方式最节省运算时间。 A、单链表 B、仅有头指针的单循环链表 C、双链表 D、仅有尾指针的单循环链表 13、链表不具有的特点是（ B ）。

A、插入、删除不需要移动元素 B、可随机访问任一元素

C、不必事先估计存储空间 D、所需空间与线性长度成正比

14、设一个链表最常用的操作是在末尾插入结点和删除尾结点，则选用( D )最节省时间。 A、单链表 B、单循环链表 C、带尾指针的单循环链表 D、带头结点的双循环链表 15、若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为（ C ）(1<=i<=n+1)。

A、O(0) B、O(1) C、 O(n) D、O(n) 16、下述（A ）是顺序存储结构的优点。

A、存储密度大 B、插入运算方便

C、删除运算方便 D、可方便地用于各种逻辑结构的存储表示

17、在单链表指针为p的结点之后插入指针为s的结点，正确的操作是（ B ）。

A、p->next=s;s->next=p->next; B、s->next=p->next;p->next=s; C、p->next=s;p->next=s->next; D、p->next=s->next;p->next=s; 18、线性表是具有n个（ C ）的有限序列（n>0）。

2

5

A、表元素 B、字符 C、数据元素 D、数据项

19、若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（ A ）存储方式最节省时间。

A、顺序表 B、双链表 C、带头结点的双循环链表 D、单循环链表 20、在双向链表指针p的结点前插入一个指针q的结点操作是（C ）。 A、p->prior=q;q->next=p;p->prior->next=q;q->prior=q； B、p->prior=q;p->prior->next=q;q->next=p;q->prior=p->prior; C、q->next=p;q->prior=p->prior;p->prior->next=q;p->prior=q; D、q->prior=p->prior;q->next=q;p->prior=q;p->prior=q;

21、若某线性表中最常用的操作是取第i 个元素和找第i个元素的前趋元素，则采用（D ）存储方式最节省时间。

A、单链表 B、双链表 C、单向循环 D、顺序表 22、链表不具有的特点是（ B ）

A、插入、删除不需要移动元素 B、可随机访问任一元素 C、不必事先估计存储空间 D、所需空间与线性长度成正比

23、对于顺序存储的线性表，访问结点和增加、删除结点的时间复杂度为（ C ）。

A、O(n) O(n) B. O(n) O(1) C、 O(1) O(n) D.O(1) O(1)

24、对于一个头指针为head的带头结点的单链表，判定该表为空表的条件是（ B） A、head==NULL B、head→next==NULL C、head→next==head D、head!=NULL 25、在双向链表存储结构中，删除p所指的结点时须修改指针（S）。

A、p->prior->next=p->next；p->next->prior=p->prior; B、p->prior:=p->prior->prior；(p->prior)^.rlink:=p; C、p->next->prior=p；p->next=p->next->next

D、p->next =p->prior->prior；p->prior=->next->next;

四、简答题

1、试比较顺序存储结构和链式存储结构的优缺点。在什么情况下用顺序表比链表好？ 答：① 顺序存储时，相邻数据元素的存放地址也相邻（逻辑与物理统一）；要求内存中可用存储单元的地址必须是连续的。

优点：存储密度大（＝1？），存储空间利用率高。缺点：插入或删除元素时不方便。

②链式存储时，相邻数据元素可随意存放，但所占存储空间分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针

优点：插入或删除元素时很方便，使用灵活。缺点：存储密度小（<1），存储空间利用率低。 顺序表适宜于做查找这样的静态操作；链表宜于做插入、删除这样的动态操作。

6

若线性表的长度变化不大，且其主要操作是查找，则采用顺序表；

若线性表的长度变化较大，且其主要操作是插入、删除操作，则采用链表。 2、在单链表和双向链表中，能否从当前结点出发访问到任何一个结点?

答：在单链表中不能从当前结点（若当前结点不是第一结点）出发访问到任何一个结点，链表只能从头指针开始，访问到链表中每个结点。在双链表中求前驱和后继都容易，从当前结点向前到第一结点，向后到最后结点，可以访问到任何一个结点。

五、算法设计题

1、有一个单链表，其头指针为head，编写一个算法计算数据域为x的结点的个数。

Int count（Node *heaD、{ node *p;

int n=0; p＝head； While（P！＝ NULL）｛ if（P->data==X） n＋＋； P=p->next；｝ return（n） }

2、试编写在带头结点的单链表中删除一个最小值结点的高效算法。

Void delete（Linklist &L）

∥L是带头结点的单链表，本算法删除其最小值结点。

{p=L->next；∥p为工作指针。指向待处理的结点。假定链表非空。 pre=L； ∥pre指向最小值结点的前驱。

q=p； ∥q指向最小值结点，初始假定第一元素结点是最小值结点。 while（p->next!=null）

{if（p->next->datadatA、{pre=p；q=p->next；} ∥查最小值结点 p=p->next； ∥指针后移。 }

pre->next=q->next；∥从链表上删除最小值结点 free（q）； ∥释放最小值结点空间 }∥结束算法delete。

3、已知不带头结点的线性链表list，链表中结点构造为（data、next），其中data为数据

域，next为指针域。请写一算法，将该链表按结点数据域的值的大小从小到大重新链接。要求链接过程中不得使用除该链表以外的任何链结点空间。 LinkedList LinkListSort(LinkedList list)

7

∥list是不带头结点的线性链表，链表结点构造为data和link两个域，data是数据域，link是指针域。本算法将该链表按结点数据域的值的大小，从小到大重新链接。

{p=list->next; ∥p是工作指针，指向待排序的当前元素。

list-> next=null;∥假定第一个元素有序，即链表中现只有一个结点。 while(p!=null)

{r=p-> next; ∥r是p的后继。 q=list;

if(q->data>p->data ∥处理待排序结点p比第一个元素结点小的情况。 {p-> next =list;

list=p;∥链表指针指向最小元素。 }

else∥查找元素值最小的结点。

{while(q-> next!=null&&q-> next ->datadata、q=q-> next;

p-> next =q-> next;∥将当前排序结点链入有序链表中。 q-> next =p;}

p=r;∥p指向下个待排序结点。 }}

4、以下程序的功能是实现带头结点的单链表数据结点逆序连接，请填空完善之。 void reverse(pointer h)

/* h为附加头结点指针；类型pointer同算法设计第3题*/

{pointer p,q;

p=h->next; h->next=NULL;

while(p!=null _____)∥链表未到尾就一直作 {q=p; p=p->next; q->next=h->next;

h->next= q; ∥将当前结点作为头结点后的第一元素结点插入

}}

5、设L为单链表的头结点地址，其数据结点的数据都是正整数且无相同的，链表中结点构造为（data、next），其中data为数据域，next为指针域。请设计利用直接插入的原则把该链表整理成数据递增的有序单链表的算法。

解：本题明确指出单链表带头结点，其结点数据是正整数且不相同，要求利用直接插入原则把链表整理成递增有序链表。这就要求从第二结点开释，将各结点依次插入到有序链表中。

8

LinkedList LinkListInsertSort(LinkedList la)

∥la是带头结点的单链表，其数据域是正整数。本算法利用直接插入原则将链表整理成

递增的有序链表。

{if(la->next!=null)∥链表不为空表。

{p=la->next->next;∥p指向第一结点的后继。

la->next->next=null;∥直接插入原则认为第一元素有序，然后从第二元素起依次插入 while(p!=null)

{r=p->next;∥暂存p的后继。

q=la;

while(q->next!=null&&q->next->datadata)

q=q->next;∥查找插入位置。 p->next=q->next;∥将p结点链入链表。 q->next=p; p=r; }

6、设计算法将一个带头结点的单链表A分解为两个具有相同结构的链表B、C，其中B表的结点为A表中值小于零的结点，而C表的结点为A表中值大于零的结点。 解：void DisCreat1(LinkedList A)

∥A是带头结点的单链表，链表中结点的数据类型为整型。本算法将A分解成两个单链表B和C，B中结点的数据小于零，C中结点的数据大于零。 {B=A;

C=(LinkedList )malloc(sizeof(LNode));∥为C申请结点空间。 C->next=null ∥C初始化为空表。 p=A->next; ∥p为工作指针。 B->next=null; ∥B表初始化。 while(p!=null)

{r=p->next; ∥暂存p的后继。 if (p->data<0)∥小于0的放入B表。

{p->next=B->next; B->next=p; }∥将小于0的结点链入B表。 else {p->next=C->next; C->next=p; } p=r;∥p指向新的待处理结点。 }}∥算法结束。

9

第3章 栈和队列 一、填空题

1、队列是限定在 队尾 插入和 队首 删除元素的线性表。

2、栈是_操作受限__的线性表，其运算遵循__后进先出 的原则，最先放入栈中元素在 栈底 ，最后放入的元素在 栈顶 ，而删除元素刚好相反，最后放入的元素 最先 删除，最先放入的元素 最后 删除。

3、对栈的操作限定为：只能在 栈顶 插入和删除元素；

4、栈S的空间大小为stacksize，S.base[0]是栈底元素，S.top是栈顶指针，则：进栈时需将S.top加1，退栈时需将S.top 减1。S.top==0时表示空栈，S.top==stacksize表示栈满。 5、设有一个空栈，现有输入序列为1，2，3，4，5，经过PUSH,PUSH,POP,PUSH,POP,PUSH,PUSH之后，输出序列是_2，3___。

6、在作进栈运算时应先判别栈是否_满_;在作退栈运算时应先判别栈是否_空 ；当栈中元素为n个，再作进栈运算时发生上溢，则说明该栈的最大容量为_n_。

7、顺序栈用data[1..n]存储，栈顶指针是top,值为x的元素入栈的操作是data[++top]=x。 8、已知链队列的头尾指针分别是f和r，则将值x入队的操作序列是：s=(LinkedList)malloc(sizeof(LNode))； s->data=x;s->next=r->next；r->next=s；r=s； 9、循环队列的引入，目的是为了克服__假溢出时大量移动数据元素_，区分循环队列的满与空，有__牺牲一个存储单元__和__设标记_两种方法。

10、在具有n个单元的循环队列中，队满时共有 n-1 个元素。

11、 向栈中压入元素的操作是先 移动栈顶指针 ，后 存入元素 。

12、从循环队列中删除一个元素时，其操作是 先 移动队首指针 ，后 取出元素 。 13、循环队列用数组A[0..m-1]存放其元素值，已知其头尾指针分别是front和rear ，则当前队列的元素个数是_（rear-front+m）% m； _。

14、设循环队列存放在向量sq.data[0:M]中，则队头指针sq.front在循环意义下的出队操作可表示为__ sq.front=(sq.front+1)%(M+1)；return(sq.data(sq.front))；，若用牺牲一个单元的办法来区分队满和队空（设队尾指针sq.rear）,则队满的条件为_(sq.rear+1)%(M+1)==sq.front；

二、判断题

1、线性表的每个结点只能是一个简单类型，而链表的每个结点可以是一个复杂类型。（×） 2、在表结构中最常用的是线性表，栈和队列不太常用。（×）

3、栈是一种对所有插入、删除操作限于在表的一端进行的线性表，是一种后进先出型结构。（√）

4、对于不同的使用者，一个表结构既可以是栈，也可以是队列，也可以是线性表。（√）

10

5、队列是一种插入与删除操作分别在表的两端进行的线性表，是一种先进后出型结构。（×） 6、循环队列也存在空间溢出问题。（√）

7、栈和队列的存储方式，既可以是顺序方式，又可以是链式方式。（√） 8、栈和队列都是限制存取点的线性结构。（√）

9、队列和栈都是运算受限的线性表，只允许在表的两端进行运算（×） 10、通常使用队列来处理函数或过程的调用。（×） 11、栈与队列是一种特殊操作的线性表。（√）

12、若输入序列为1,2,3,4,5,6,则通过一个栈可以输出序列3,2,5,6,4,1. （√） 13、栈和队列都是限制存取点的线性结构。（√） 14、循环队列通常用指针来实现队列的头尾相接（×） 15、循环队列的引入，目的是为了克服假溢出现象。（ √ ）

三、单项选择题

1、栈中元素的进出原则是（ B ）

Ａ．先进先出 Ｂ．后进先出 Ｃ．栈空则进 Ｄ．栈满则出

2、若已知一个栈的入栈序列是1，2，3，?，n，其输出序列为p1，p2，p3，?，pn，若p1=n，则pi为（ C ）

Ａ．i Ｂ．n=i Ｃ．n-i+1 Ｄ．不确定

3、判定一个顺序栈ST（最多元素为m）为空的条件是（ B ）

Ａ、ST->top<>0 Ｂ、ST->top=0 Ｃ、．ST->top<>m Ｄ、ST->top=m 4、判定一个队列QU（最多元素为m）为满队列的条件是（ A ） Ａ、QU->rear-QU->front= =m Ｂ、QU->rear-QU->front-1==m Ｃ、QU->front==QU->rear Ｄ、QU->front==QU->rear+1

5、数组Ｑ［ｎ］用来表示一个循环队列，ｆ为当前队列头元素的前一位置，ｒ为队尾元素的位置，假定队列中元素的个数小于ｎ，计算队列中元素个数的公式为（ D ）。 Ａ、r－f; Ｂ、（n＋f－r）% n; Ｃ、n＋r－f; Ｄ、（n＋r－f）% n 6、若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3，当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为( B )。 A、1和 5 B、2和4 C、4和2 D、5和1 7、栈和队列的共同点是（ C ）。

A、都是先进先出、 B、都是先进后出 C、只允许在端点处插入和删除元素 D、没有共同点 8、栈和队都是（ C ）。

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

11

9、栈与一般线性表的区别在于（ B ）。

A、数据元素的类型不同 B、运算是否受限制 C、数据元素的个数不同 D、逻辑结构不同

10、有六个元素6，5，4，3，2，1 ，按顺序进栈，下列（ C ）不是合法的出栈序列。 A、5 4 3 6 1 2 B、4 5 3 1 2 6 C、 3 4 6 5 2 1 D、2 3 4 1 5 6

11、一个栈的输入序列为123?n，若输出序列的第一个元素是n，输出第i（1<=i<=n）个元素是（ B ）。

A、不确定 B、n-i+1 C、 I D、n-i

12、若一个栈的输入序列为1,2,3,?,n，输出序列的第一个元素是i，则第j个输出元素是（ D ）。

A、i-j-1 B、 i-j C、 j-i+1 D、 不确定的 13、设栈的输入序列是1，2，3，4,则（D ）不可能是其出栈序列。

A、 1，2，4，3 B、2，1，3，4 C、 1，4，3，2 D、4，3，1，2

14、设一个栈的输入序列是 1，2，3，4，5,则下列序列中，是栈的合法输出序列的是（ D ）。 A、5 1 2 3 4 B、 4 5 1 3 2 C、 4 3 1 2 5 D、3 2 1 5 4 15、循环队列存储在数组A[0..m]中，则入队时的操作为（ D ）。 A、rear=rear+1 B、 rear=(rear+1) mod (m-1) C、rear=(rear+1) mod m D rear=(rear+1)mod(m+1)

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

A、(rear-front+m)%m B、rear-front+1 C、(front-rear+m)%m D、(rear-front)%m 17、栈在（ D ）中应用。

A、递归调用 B、子程序调用 C、表达式求值 D、以上三种

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

A、仅修改队头指针 B、仅修改队尾指针

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

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

20、有六个元素6，5，4，3，2，1 的顺序进栈，下列哪一个不是合法的出栈序列？（ ） A、5 4 3 6 1 2 B、4 5 3 1 2 6 C、 3 4 6 5 2 1 D. 2 3 4 1 5 6

四、简答题

1、说明线性表、栈与队的异同点。

12

答：相同点：都是线性结构，都是逻辑结构的概念。都可以用顺序存储或链表存储；栈和队列是两种特殊的线性表，即受限的线性表，只是对插入、删除运算加以限制。

不同点：①运算规则不同，线性表为随机存取，而栈是只允许在一端进行插入、删除运算，因而是后进先出表LIFO；队列是只允许在一端进行插入、另一端进行删除运算，因而是先进先出表FIFO。

② 用途不同，堆栈用于子程调用和保护现场，队列用于多道作业处理、指令寄存及其他运算等等。

2、顺序队的“假溢出”是怎样产生的？如何知道循环队列是空还是满？

答：一般的一维数组队列的尾指针已经到了数组的上界，不能再有入队操作，但其实数组中还有空位置，这就叫“假溢出”。采用循环队列是解决假溢出的途径。另外，解决队满队空的办法有三：设置一个布尔变量以区别队满还是队空；浪费一个元素的空间，用于区别队满还是队空。使用一个计数器记录队列中元素个数（即队列长度）。

我们常采用法②，即队头指针、队尾指针中有一个指向实元素，而另一个指向空闲元素。 判断循环队列队空标志是： f=rear 队满标志是：f=(r+1)%N

第四、五章 一、填空题

1、不包含任何字符（长度为0）的串称为空串；由一个或多个空格（仅由空格符）组成的串

称为空白串。

2、设S=“A;/document/Mary.doc”，则字符串“/”的位置为 3 。

3、子串的定位运算称为串的模式匹配； 被匹配的主串 称为目标串， 子串 称为模式。 4、串的存储方式有顺序存储、堆分配存储和块链存储。

5、有一个二维数组A[0:8,1:5],每个数组元素用相邻的4个字节存储，存储器按字节编址，假设存储数组元素A[0,1]的地址是100，若按行主顺序存储，则A[3,5]的地址是176 和 A[5,3]的地址是208 。若按列存储，则A[7,1] 的地址是128 ，A[2,4]的地址是216 。 6、设数组a[1?60, 1?70]的基地址为2048，每个元素占2个存储单元，若以列序为主序顺序存储，则元素a[32,58]的存储地址为 8950 。

7、 三元素组表中的每个结点对应于稀疏矩阵的一个非零元素，它包含有三个数据项，分别表示该元素的 行下标 、 列下标 和 元素值 。

8、二维数组A[10][20]采用列序为主方式存储，每个元素占10个存储单元，且A[0][0]的存储地址是2000，则A[6][12]的地址是3260

9、已知二维数组A[20][10]采用行序为主方式存储,每个元素占2个存储单元,并且A[10][5]的存储地址是1000,则A[18][9]的存储地址是 1168

10、已知二维数组A[10][20]采用行序为主方式存储，每个元素占2个存储单元,并且A[0][0]

13

的存储地址是1024, 则A[6][18]的地址是1300 11、组成串的数据元素只能是字符。

12、两个字符串相等的充分必要条件是两串的长度相等且两串中对应位置的字符也相等。

二、单选题

1、串是一种特殊的线性表，其特殊性体现在（ B ） Ａ、可以顺序存储 Ｂ、数据元素是一个字符 Ｃ、可以链式存储 Ｄ、数据元素可以是多个字符

2、设有两个串p和q，求q在p中首次出现的位置的运算称作（ B ） Ａ、连接 Ｂ、模式匹配 Ｃ、求子串 Ｄ、求串长

3、设串s1=’ABCDEFG’，s2=’PQRST’，函数con(x,y)返回x和y串的连接串，subs(s, i, j)返回串s的从序号i开始的j个字符组成的子串，len(s)返回串s的长度，则con(subs(s1, 2, len(s2)), subs(s1, len(s2), 2))的结果串是（ D ） Ａ、BCDEF Ｂ、BCDEFG Ｃ、BCPQRST Ｄ、BCDEFEF

4、假设有60行70列的二维数组a[1?60, 1?70]以列序为主序顺序存储，其基地址为10000，每个元素占2个存储单元，那么第32行第58列的元素a[32,58]的存储地址为（ A ）。（无第0行第0列元素）

Ａ、16902 Ｂ、16904 Ｃ、14454 Ｄ、答案A, B, C均不对 5、下面关于串的的叙述中，（ B ）是不正确的。

A、串是字符的有限序列 B、空串是由空格构成的串

C、模式匹配是串的一种重要运算 D、串既可以采用顺序存储，也可以采用链式结构 6、串的长度是指（ B ）

A、串中所含不同字母的个数 B、串中所含字符的个数 C、串中所含不同字符的个数 D、串中所含非空格字符的个数 7、设矩阵A是一个对称矩阵，为了节省存储，将其下三角部分（如下图所示）按行序存放在一维数组B[ 1, n(n-1)/2 ]中，对下三角部分中任一元素ai,j(i≤j), 在一维数组B中下标k的值是( B )

A、i(i-1)/2+j-1 B、i(i-1)/2+j C、i(i+1)/2+j-1 D、i(i+1)/2+j 8、以下关于广义表的叙述中,正确的是（ A）

A、广义表是由0个或多个单元素或子表构成的有限序列 B、广义表至少有一个元素是子表 C、广义表不能递归定义 D、广义表不能为空表

?a1,1?a2,1?A??????an,1a2,2an,2?????an,n??? 14

9、设A是n*n的对称矩阵，将A的对角线及对角线上方的元素以列为主的次序存放在一维数组B[1..n(n+1)/2]中，对上述任一元素aij(1≤i，j≤n，且i≤j)在B中的位置为( 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 10、A[N，N]是对称矩阵，将下面三角（包括对角线）以行序存储到一维数组T[N（N+1）/2]中，则对任一上三角元素a[i][j]对应T[k]的下标k是（ B ）。

A、i（i-1）/2+j B、j（j-1）/2+I C、i（j-i）/2+1 D、j（i-1）/2+1 11、有一个二维数组A，行下标的范围是1到6，列下标的范围是0到7，每个数组元素用相邻的6个字节存储，存储器按字节编址。那么，这个数组的体积是（ A ）个字节。 A、288 B、283 C、276 D、282

12、有一个二维数组A，行下标的范围是1到6，列下标的范围是0到7，每个数组元素用相邻的6个字节存储，存储器按字节编址，假设存储数组元素A[1,0]的第一个字节的地址是0，则存储数组A的最后一个元素的第一个字节的地址是 B 。 A、288 B、282 C、276 D、283

13、有一个100*90的稀疏矩阵，非0元素有10个，设每个整型数占2字节，则用三元组表示该矩阵时，所需的字节数是（B ）。 A、60 B、66 C、18000 D、33 14、对稀疏矩阵进行压缩存储目的是（ C ）。

A、便于进行矩阵运算 B、便于输入和输出 C、节省存储空间 D、降低运算的时间复杂度 15、下面说法不正确的是( A )。

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

三、简答题

1.已知二维数组Am,m采用按行优先顺序存放，每个元素占K个存储单元，并且第一个元素的存储地址为Loc(a11)，请写出求Loc(aij)的计算公式。如果采用列优先顺序存放呢？ 解：公式教材已给出，此处虽是方阵，但行列公式仍不相同；

按行存储的元素地址公式是： Loc(aij)= Loc(a11) +[ (i-1)*m+(j-1) ] * K 按列存储的元素地址公式是： Loc(aij)= Loc(a11) +[ (j-1)*m+(i-1) ] * K 2.递归算法比非递归算法花费更多的时间，对吗？为什么？

答：不一定。时间复杂度与样本个数n有关，是指最深层的执行语句耗费时间，而递归算法与非递归算法在最深层的语句执行上是没有区别的，循环的次数也没有太大差异。仅仅是确定循环是否继续的方式不同，递归用栈隐含循环次数，非递归用循环变量来显示循环次数而已。

15

四、判断题

1、子串是主串中任意个连续字符组成的序列。（√）

2、广义表((( a ), b), c ) 的表头是(( a ), b)，表尾是( c )。（√） 3、数组元素的下标值越大，存取时间越长。（×）

4、数组可看成线性表的一种推广，因此与线性表一样，可以对它进行插入，删除等操作。（×） 5、个串p和q，求q在p中首次出现的位置的运算称作求子串。（×） 6、二维数组是其数据元素为线性表的线性表。（√）

7、若一个广义表的表头为空表，则此广义表亦为空表。（×） 8、用一维数组存储二叉树时，总是以前序遍历存储节点。（×） 9、KMP算法的特点是在模式匹配时指示主串的指针不会变小。（√）

10、若采用三元组压缩技术存储稀疏矩阵，只要把每个元素的行下标和列下标互换，就完成

了对该矩阵的转置。（×）

第六章 树及二叉树 一、判断正误

1、完全二叉树中，若一个结点没有左孩子，则它必是叶子结点。（√） 2、二叉树中每个结点的两棵子树的高度差等于1。（×） 3、二叉树中每个结点的两棵子树是有序的。（√）

4、二叉树中每个结点有两棵非空子树或有两棵空子树。（×） 5、一棵树中的叶子数一定等于与其对应的二叉树的叶子数。（×） 6、二叉树是度为2的有序树。（×）

7、二叉树中所有结点，如果不存在非空左子树，则不存在非空右子树。（×） 8、线索二叉树的优点是便于在中序下查找前驱结点和后继结点。（√） 9、树与二叉树是两种不同的树型结构。（√）

10、哈夫曼树是带权路径最短的树,路径上权值较大的结点离根较近。（√）

11、一棵一般树的结点的前序遍历和后序遍历分别与它相应二叉树的结点前序遍历和后序遍

历是一致的。(× )

12、在哈夫曼树中，权值最小的结点离根结点最近。(× ) 13、对一棵二叉树进行层次遍历时，应借助于一个栈。(× ) 14、深度为K的完全二叉树至少有2K-1个结点。（√ ）

15、具有n个结点的满二叉树，其叶结点的个数为（n+1）/2。(√ )

16、二叉树中每个结点有两个子结点,而树无此限制,因此二叉树是树的特殊情况。(× ) 17、完全二叉树一定存在度为1的结点。(× )

18、二叉树的遍历只是为了在应用中找到一种线性次序。(√ )

16

19、二叉树的叶子结点在前序遍历和后序遍历下，皆以相同的相对位置出现。(√ ) 20、用一维数组存储二叉树时，总是以前序遍历顺序存储结点。(× )

二、填空

1、二叉树由根结点、左子树、右子树_三个基本单元组成。

2、在二叉树中，指针p所指结点为叶子结点的条件是p->lchild==null && p->rchlid==null。 3、一棵具有257个结点的完全二叉树，它的深度为 9 。

4、某二叉树有20个叶子结点，有30个结点仅有一个孩子，则该二叉树的总结点数为_69_。 5、设一棵完全二叉树具有1000个结点，则此完全二叉树有 500 个叶子结点，有 499 个度为2的结点，有 1 个结点只有非空左子树，有 0 个结点只有非空右子树。 6、一棵含有n个结点的k叉树，可能达到的最大深度为 n ，最小深度为 2 。 7、若已知一棵二叉树的前序序列是BEFCGDH，中序序列是FEBGCHD，则它的后序序列必是 F E G H D C B 。

8、具有256个结点的完全二叉树的深度为__9___。 9、高度为8的完全二叉树至少有__64___个叶子结点。

10、N个结点的二叉树采用二叉链表存放，共有空链域个数为n+1 11、深度为6（根层次为1）的二叉树至多有2–1个结点。

12、线索二元树的左线索指向其_前驱____，右线索指向其__后继___。

6

三、选择题

1、二叉树结点的中序序列为A、B、C、D、E、F、G，后序序列为B、D、C、A、F、G、E，则其左子树中结点数目为（C ）

A、3 B、2 C、4 D、5 2、二叉树是非线性数据结构，所以（ B ）

Ａ、它不能用顺序存储结构存储; Ｂ、顺序存储结构和链式存储结构都能存储; Ｃ、它不能用链式存储结构存储; 顺序存储结构和链式存储结构都不能使用 3、有n(n>0)个结点的完全二叉树的深度为（ C ）。

Ａ、log2(n)? B、 ? log2(n)? Ｃ、? log2(n) ?+1 Ｄ、?log2(n)+1? 4、把一棵树转换为二叉树后，这棵二叉树的形态是（ A ）。 A、唯一的 B、有多种

C、有多种，但根结点都没有左孩子 D、有多种，但根结点都没有右孩子

5、下述二叉树中,哪一种满足性质：从任一结点出发到根的路径上所经过的结点序列按其关

键字有序（D ）。

A、二叉排序树 B、哈夫曼树 C、AVL树 D、堆

17

6、线索二叉树是一种（ C ）结构。

A、逻辑 B、 逻辑和存储 C、 物理 D、线性

7、将一棵有100个结点的完全二叉树从根这一层开始，每一层从左到右依次对结点进行编号，根结点编号为1，则编号为49的结点的左孩子的编号为（ A） A、98 B、99 C、50 D、48

8、设森林F中有三棵树，第一、第二和第三棵树的结点个数分别为M1、M2和M3。与森林F对应的二叉树根结点的右子树上的结点个数是（D ） A、M1 B、M1+M2 C、M3 D、M2+M3

9、将一棵有100个结点的完全二叉树从根这一层开始，每一层从左到右依次对结点进行编号，根结点编号为1，则编号最大的非叶结点的编号为（C ） A、48 B、49 C、50 D、51 10、引入二叉线索树的目的是（ A ）

A、加快查找结点的前驱或后继的速度 B、为了能在二叉树中方便的进行插入与删除 C、为了能方便的找到双亲 D、使二叉树的遍历结果唯一

11、若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（ B ） A、9 B、11 C、15 D、不确定

12、一棵树高为K的完全二叉树至少有（ C ）个结点 A、2k –1 B. 2k-1–1 C、 2k-1 D、2k

13．设森林F中有三棵树，第一，第二，第三棵树的结点个数分别为M1，M2和M3。与森林F对应的二叉树根结点的右子树上的结点个数是（ D ）。 A、M1 B、M1+M2 C、M3 D、M2+M3

14、一棵二叉树的前序遍历序列为ABCDEFG，它的中序遍历序列可能是（ B ） A、CABDEFG B、ABCDEFG C、DACEFBG D、ADCFEG 15、有关二叉树下列说法正确的是（ B ）

A、二叉树的度为2 B、一棵二叉树的度可以小于2 C、二叉树中至少有一个结点的度为2 D、二叉树中任何一个结点的度都为2 16、一个具有1025个结点的二叉树的高h为（ C ） A、11 B、10 C、11至1025之间 D、10至1024之间

17、一棵二叉树高度为h,所有结点的度或为0，或为2，则这棵二叉树最少有( B )结点

A、2 B、2-1 C、2+1 D、h+1 18、对于有n 个结点的二叉树, 其高度为（D ）

A、nlog2n B、log2n C、?log2n?|+1 D、不确定 19、一棵具有n个结点的完全二叉树的树高度（深度）是（ A ）

A、?logn?+1 B、logn+1 C、?logn? D、logn-1

h

h

h

18

20、已知某二叉树的后序遍历序列是dabec,中序遍历序列是debac,它的前序遍历是（D ）。

A、acbed B、decab C、deabc D、cedba

21、若二叉树采用二叉链表存储结构，要交换其所有分支结点左、右子树的位置，利用( C )遍历方法最合适。

A、前序 B、中序 C、后序 D、按层次

22、在下列存储形式中，哪一个不是树的存储形式？（ D ）

A、双亲表示法 B、孩子链表表示法 C、孩子兄弟表示法 D、顺序存储表示法 23、在下列关于二叉树的叙述中，正确的是（ D ）

①只有一个结点的二叉树度为0;②二叉树的度为2； ③二叉树的左右子树可任意交换; ④深度为K的完全二叉树的结点个数小于或等于深度相同的满二叉树。 A、①②③ B、②③④ C、②④ D、①④

24、若X是二叉中序线索树中一个有左孩子的结点，且X不为根，则x的前驱为( C ) A、X的双亲 B、X的右子树中最左的结点 C、X的左子树中最右结点 D、X的左子树中最右叶结点

25、在二叉树结点的先序序列，中序序列和后序序列中，所有叶子结点的先后顺序（ B ） A、都不相同 B、完全相同

C、先序和中序相同 而与后序不同 D、中序和后序相同，而与先序不同。 26、在线索化二叉树中，t所指结点没有右子树的充要条件是（ ）。 A、t->Rtag==1 B、t->Rchild==NULL C、t->Rtag==1且t->Rchild==NULL D、以上都不对 27、设给定权值总数有n 个，其哈夫曼树的结点总数为( D )

A、不确定 B、2n C、2n+1 D、2n-1 28、利用二叉链表存储树，则根结点的右指针是（C ） 。 A、指向最左孩子 B、指向最右孩子 C、空 D、非空 29、在下列存储形式中，（ D ）不是树的存储形式。

A、双亲表示法 B、孩子链表表示法 C、孩子兄弟表示法 D、顺序存储表示法 30、一棵非空二叉树的先序遍历序列与后序遍历序列正好相反，则该二叉树一定满足（ C ）。 A、所有的结点均无左孩子 B、所有的结点均无右孩子 C、只有一个叶子结点 D、是任意一棵二叉树

四、简答题

1、给定二叉树的两种遍历序列，分别是：前序遍历序列：D，A，C，E，B，H，F，G，I； 中序遍历序列：D，C，B，E，H，A，G，I，F，试画出二叉树B。

解：方法是：由前序先确定root，由中序可确定root的左、右子树。然后由其左子树

19

的元素集合和右子树的集合对应前序遍历序列中的元素集合，可继续确定root的左右孩子。将他们分别作为新的root，不断递归，则所有元素都将被唯一确定，问题得解。 2、已知一棵二叉树，其中序序列DBCAFGE，后序序列DCBGFEA，构造该二叉树。 解：

3、给定权值{8，12，4，5，26，16，9}，构造一棵带权路径长度最短的二叉树，并计算其带权路径长度。 解：

或：

WPL=8×3+4×4+5×4+16×2+9×3+12×3+26×2 =207 [注]：哈夫曼树的左右子树可以互换。 4、（把如图所示的树转化成二叉树。

答：注意全部兄弟之间都要连线（包括度为2的兄弟）,并注意原有连线结点一律归入左子树，新添连线结点一律归入右子树。 A

20

B E C K F H D

L G I M J

5、画出和下列二叉树相应的森林。

答：注意根右边的子树肯定是森林， 而孩子结点的右子树均为兄弟。

五、算法设计题

1、编写递归算法，计算二叉树中叶子结点的数目。

解：思路：输出叶子结点比较简单，用任何一种遍历递归算法，凡是左右指针均空者，则为叶子，将其打印出来。

void Leaf(BitTree bt,int *count) {

if (bt) {

Leaf(bt->lchild,&count); //计算左子树的叶子结点个数 if (bt->lchild==NULL&&bt->rchild==NULL) (*count)++;

Leaf(bt->rchild,&count); //计算右子树的叶子结点个数 }}2.写出求二叉树深度的算法，先定义二叉树的抽象数据类型。 解： int depth(liuyu*root) /*统计层数*/

{int d,p; /*注意每一层的局部变量d,p都是各自独立的*/ p=0;

if(root==NULL)return(p); /*找到叶子之后才开始统计*/

21

else{

d=depth(root->lchild);

if(d>p) p=d; /*向上回朔时，要挑出左右子树中的相对大的那个深度值*/ d=depth(root->rchild); if(d>p)p=d; } p=p+1; return(p); }

3、求二叉树中以元素值为x的结点为根的子树的深度。

解：int Get_Sub_Depth(Bitree T,int x)//求二叉树中以值为x的结点为根的子树深度 { if(T->data==x)

{ printf(\找到了值为x的结点,求其深度 exit 1; } } else {

if(T->lchild) Get_Sub_Depth(T->lchild,x);

if(T->rchild) Get_Sub_Depth(T->rchild,x); //在左右子树中继续寻找 } }//Get_Sub_Depth

4、编写按层次顺序（同一层自左至右）遍历二叉树的算法。

解：思路：既然要求从上到下，从左到右，则利用队列存放各子树结点的指针是个好办法。 这是一个循环算法，用while语句不断循环，直到队空之后自然退出该函数。

技巧之处：当根结点入队后，会自然使得左、右孩子结点入队，而左孩子出队时又会立即使得它的左右孩子结点入队，??以此产生了按层次输出的效果。 void LayerOrder(Bitree T)//层序遍历二叉树 { InitQueue(Q); //建立工作队列

EnQueue(Q,T);

while(!QueueEmpty(Q)) {

DeQueue(Q,p); visit(p);

if(p->lchild) EnQueue(Q,p->lchild);

22

if(p->rchild) EnQueue(Q,p->rchild); }

}//LayerOrder

5、二叉树按二叉链表形式存储，编写算法判别给定二叉树是否为完全二叉树。

答：int IsFull_Bitree(Bitree T)//判断二叉树是否完全二叉树,是则返回1,否则返回0 { InitQueue(Q); flag=0;

EnQueue(Q,T); //建立工作队列 while(!QueueEmpty(Q)) { {

DeQueue(Q,p); if(!p) flag=1;

else if(flag) return 0; else

{ EnQueue(Q,p->lchild);

EnQueue(Q,p->rchild); //不管孩子是否为空,都入队列 } }//while return 1; }//IsFull_Bitree

6、计算二叉树上单分支结点数目。 int Onchild(BiTree T)//单分支节点的 {

int num1,num2,n=0; if(T==NULL) return(0); else

if((T->lchild==NULL&&T->rchild!=NULL)||(T->lchild!=NULL&&T->rchild==NULL)) n=1;

num1=Onchild(T->lchild); num2=Onchild(T->rchild); return(num1+num2+n); }

7、写出在中序线索二叉树里；找指定结点在后序下的前驱结点的算法。

[题目分析]在后序序列中，若结点p有右子女，则右子女是其前驱，若无右子女而有左子女，

23

则左子女是其前驱。若结点p左右子女均无，设其中序左线索指向某祖先结点f（p是f右子树中按中序遍历的第一个结点），若f有左子女，则其左子女是结点p在后序下的前驱；若f无左子女，则顺其前驱找双亲的双亲，一直继续到双亲有左子女（这时左子女是p的前驱）。还有一种情况，若p是中序遍历的第一个结点，结点p在中序和后序下均无前驱。

BiThrTree InPostPre (BiThrTree t,p)

//在中序线索二叉树t中，求指定结点p在后序下的前驱结点q {BiThrTree q;

if (p->rtag==0) q=p->rchild; //若p有右子女，则右子女是其后序前驱

else if (p->ltag==0) q=p->lchild; //若p无右子女而有左子女，左子女是其后序前驱。 else if(p->lchild==null) q=null;//p是中序序列第一结点，无后序前驱 else //顺左线索向上找p的祖先，若存在，再找祖先的左子女 {while(p->ltag==1 && p->lchild!=null) p=p->lchild;

if(p->ltag==0) q=p->lchild; //p结点的祖先的左子女是其后序前驱

else q=null; //仅右单枝树（p是叶子），已上到根结点，p结点无后序前驱 }

return(q); }//结束InPostPre

8、线索二叉树有数据域data，左右孩子域lchild和rchild，左右标志ltag及rtag，规定标志为1对应的孩子域是线索，0则为指向孩子的指针。规定在储存线索二叉树时，完成下面中序线索化过程。（存储线索二叉树，不增加头结点，只在原有的由tree指向的二叉树中增加线索，线索化前所有的标志tag都是0）。

/* pre是同tree类型相同的指针，初值是null */ thread_inorder (tree) { if(tree!=null)

{ thread_inorder((1)____);

if(tree->lchild==(2)______) { tree->ltag=1; tree->lchild=pre; } if((3)___ == null){ (4)_______; (5)_______;}

pre=p; thread-inorder((6)_______); } }

（1）tree->lchild (2)null (3)pre->rchild (4)pre->rtag=1 (5) pre->right=tree; (6) tree->right (注（4）和（5）顺序可换)

24

第七章 图 一、单选题

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

2、在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的（ B ）倍。 A、1/2 B、1 C、2 D、4 3、有8个结点的无向图最多有（ B ）条边。

A、14 B、28 C、56 D、112 4、一个n个顶点的连通无向图，其边的个数至少为（ A ）。

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

A、14 B、28 C、56 D、112 6、用邻接表表示图进行广度优先遍历时，通常是采用（ B ）来实现算法的。 A、栈 B、队列 C、 树 D、图 7、用邻接表表示图进行深度优先遍历时，通常是采用（ A ）来实现算法的。 A、栈 B、队列 C、树 D、图 8、下面关于求关键路径的说法不正确的是（ C ）。 A、求关键路径是以拓扑排序为基础的

B、一个事件的最早开始时间同以该事件为尾的弧的活动最早开始时间相同

C、一个事件的最迟开始时间为以该事件为尾的活动最迟开始时间与该活动持续时间的差 D、关键活动一定位于关键路径上

9、已知图的邻接矩阵如下，根据算法思想，则从顶点0出发，按深度优先遍历的结点序列是（ D ）。

?0?1??1?1??1??0??1100100110001001100110101101000011011??1?0??0?0??1?0??A、0 2 4 3 1 5 6 B、0 1 3 5 6 4 2 C、0 4 2 3 1 6 5 D、0 1 3 4 2 5 6 10、下列关于AOE网的叙述中，不正确的是（ B ）。

A、关键活动不按期完成就会影响整个工程的完成时间 B、任何一个关键活动提前完成，那么整个工程将会提前完成

25

C、所有的关键活动提前完成，那么整个工程将会提前完成 D、某些关键活动提前完成，那么整个工程将会提前完成

11、已知图的邻接矩阵如下，根据算法，则从顶点0出发，按广度优先遍历的结点序列是（ C ）

?0?1??1?1??1??0??1100100110001001100110101101000011011??1?0??0?0??1?0??A 0 2 4 3 1 6 5 B、0 1 3 5 6 4 2 C、0 1 2 3 4 6 5 D、0 1 2 3 4 5 6

12、已知图的邻接表如下所示，根据算法，则从顶点0出发按深度优先遍历的结点序列是（ D ）

A、0 1 3 2 B、0 2 3 1 C、0 3 2 1 D、0 1 2 3

13、已知图的邻接表如下所示，根据算法，则从顶点0出发按广度优先遍历的结点序列是（ A ）

A、0 3 2 1 B、0 1 2 3 C、0 1 3 2 D、0 3 1 2

14、深度优先遍历类似于二叉树的（ A ）。

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

A、先序遍历 B. 中序遍历 C、 后序遍历 D、层次遍历 16、下面结构中最适于表示稀疏无向图的是（ D ）。

A、邻接矩阵 B、逆邻接表 C、十字链表 D、邻接表

26

17、下列（ B ）的邻接矩阵是对称矩阵。

A、有向图 B、无向图 C、AOV网 D、AOE网 18、下面哪一方法可以判断出一个有向图是否有环（回路）( B)。 A、深度优先遍历 B、拓扑排序 C、求最短路径 D、求关键路径

19、在有向图G的拓扑序列中，若顶点Vi在顶点Vj之前，则下列情形不可能出现的是（ D ）。 A、G中有弧 B、G中有一条从Vi到Vj的路径 C、G中没有弧 D、G中有一条从Vj到Vi的路径

二、填空题

1、图有 邻接矩阵 、邻接表 等存储结构，遍历图 深度优先遍历、 广度优先遍历 等方法。 2、有向图G用邻接表矩阵存储，其第i行的所有元素之和等于顶点i的 出度 。 3、拓扑排序算法是通过重复选择具有 0 个前驱顶点的过程来完成的。

4、n个顶点e条边的图，若采用邻接矩阵存储，则空间复杂度为O(n2)，若采用邻接表存储，则空间复杂度为O(n+e)。

5、n个顶点e条边的图采用邻接矩阵存储，广度优先遍历算法的时间复杂度为 O(n2) ；若采用邻接表存储，该算法的时间复杂度为O(n+e)。

6、设有一稀疏图G，则G采用 邻接表 存储较省空间，设有一稠密图G，则G采用邻接矩阵存储较省空间。

7、用Dijkstra算法求某一顶点到其余各顶点间的最短路径是按路径长度递增的次序来得到最短路径的。

8、n个顶点的连通无向图，其边的条数至少为__ n-1____。若用n表示图中顶点数目，则有___

n(n-1)/2____条边的无向图成为完全图。

9、具有8个顶点的有向完全图有 56条弧。具有10个顶点的无向图，边的总数最多为_ 45_。 10、在无向图G的邻接矩阵A中，若A[i][j]等于1，则A[j][i]等于 1 。 11、G是一个非连通无向图，共有28条边，则该图至少有_9_个顶点。

12、为了实现图的广度优先搜索，除了一个标志数组标志已访问的图的结点外，还需_队列存放被访问的结点以实现遍历。

13、一无向图G（V，E），其中V（G）={1,2,3,4,5,6,7}，E（G）={（1,2）,(1,3），（2,4），（2,5），（3,6），（3,7），（6,7）（5,1）},对该图从顶点3开始进行遍历，去掉遍历中未走过的边，得一生成树G’(V，E’）,V（G’）=V（G），E（G’）={（1,3），（3,6），（7,3），（1,2），（1,5），（2,4）}，则采用的遍历方法是___广度优先遍历___ 14、在图G的邻接表表示中，每个顶点邻接表中所含的结点数，对于无向图来说等于该顶点的_度_；对于有向图来说等于该顶点的_出度_。

15、 已知一无向图G=（V，E），其中V={a,b,c,d,e } E={(a,b),(a,d),(a,C、,(d,C、,(b,e)}

27

现用某一种图遍历方法从顶点a开始遍历图，得到的序列为abecd，则采用的是__深度优先遍历方法。

三、判断题

1、在拓朴序列中，如果结点Vi排在结点Vj的前面，则一定存在从Vi到Vj的路径。(? ) 2、用邻接矩阵法存储一个图时，在不考虑压缩存储的情况下，所占用的存储空间大小只与图中结点个数有关，而与图的边数无关。(√ )

3、拓扑排序是按AOE网中每个结点事件的最早发生时间对结点进行排序。(× ) 4、采用邻接表存储的图的深度优先遍历算法类似二叉树的按层次遍历算法。（× ） 5、若一个有向图的邻接矩阵中对角线以下元素均为零，则该图的拓扑有序序列必定存在。(√ )

6、在n个结点的无向图中，若边数大于n-1,则该图必是连通图。（× ） 7、有e条边的无向图，在邻接表中有e个结点。（× ）

8、有向图中顶点V的度等于其邻接矩阵中第V行中的1的个数。（× ） 9、强连通图的各顶点间均可达。（√ ）

10、连通分量指的是有向图中的极大连通子图。（×）

11、任何有向图的结点都可以排成拓扑排序，而且拓扑序列不唯一。（×） 12、用邻接矩阵法存储一个图所需的存储单元数目与图的边数有关。（×）

13、有n个顶点的无向图, 采用邻接矩阵表示, 图中的边数等于邻接矩阵中非零元素之和的一半。（√）

14、当改变网上某一关键路径上任一关键活动后，必将产生不同的关键路径(× ) 15、不同的求最小生成树的方法最后得到的生成树是相同的.（× ）

四、简答题

1、请对下图的无向带权图：

（1） 写出它的邻接矩阵，并按普里姆算法求其最小生成树；

（2） 写出它的邻接表，并按克鲁斯卡尔算法求其最小生成树。

解：设起点为a。可以直接由原始图画出最小生成树，而且最小生成树只有一种（类）!

邻接矩阵为：

最小生成树→ ?043????40559??3505????55076??9?703?630 ???????5?2???54??????5?206????5?4?????6?0??28

2、已知二维数组表示的图的邻接矩阵如下图所示。试分别画出自顶点1出发进行遍历所得的深度优先生成树和广度优先生成树。

2、给定下列

网G:

A B———————C

试着找出网G的最小生成树，画出其逻辑结构图； 解：

3、图2表示一个地区的通讯网，边表示城市间的通讯线路，边上的权值表示架设线路花费的代价，请找出能连通每个城市、且总代价最省的n-1条线路。

E————F G————D

答： 图2

29

4、B = (K, R), K = {k1, k2, ?, k9}

R={, , ,, , ,, , , , }

分别对关系r中的开始结点，举出一个拓扑序列的例子。

解：开始结点：（入度为0）K1，K2，终端结点（出度为0）K6，K7。 拓扑序列K1，K2，K3，K4，K5，K6，K8，K9，K7 K2，K1，K3，K4，K5，K6，K8，K9，K7

规则：开始结点为K1或K2，之后，若遇多个入度为0的顶点，按顶点编号顺序选择。 5、已知有向图如下所示，对该图进行拓扑排序。

G B A C E H I D F

答：拓扑序列为：A、B、C、D、E、F、G、H、I（不唯一） 6.已知图的邻接矩阵为： V1 V2 V3 V4 V5 V6 V7 V8 V9 V10 V1 0 1 1 1 0 0 0 0 0 0 V2 0 0 0 1 1 0 0 0 0 0 V3 0 0 0 1 0 1 0 0 0 0 V4 0 0 0 0 0 1 1 0 1 0 V5 0 0 0 0 0 0 1 0 0 0 V6 0 0 0 0 0 0 0 1 1 0 V7 0 0 0 0 0 0 0 0 1 0 V8 0 0 0 0 0 0 0 0 0 1 V9 0 0 0 0 0 0 0 0 0 1 30

V10 0 0 0 0 0 0 0 0 0 0

当用邻接表作为图的存储结构，且邻接表都按序号从大到小排序时，试写出： （1）．以顶点V1为出发点的唯一的深度优先遍历； （2）．以顶点V1为出发点的唯一的广度优先遍历； （3）．该图唯一的拓扑有序序列。

7、已知一数据集合的逻辑结构为：B = (K, R), 其中，K = {k1, k2, ?, k8}，R={, , ,, , , , ，，}，请回答下面两个问题： （1）画出这个逻辑结构的图示。 （2）写出关系R的一个拓扑序列。

K2 K3 K7 K1 K4 K5 K6 K8 （2）拓扑序列K1，K2，K3，K4，K8，K5，K6，K7

五、算法设计题

1、编写算法，由依次输入的顶点数目、弧的数目、各顶点的信息和各条弧的信息建立有向图的邻接表。

解：Status Build_AdjList(ALGraph &G) //输入有向图的顶点数,边数,顶点信息和边的信息建立邻接表 { InitALGraph(G); scanf(\

if(v<0) return ERROR; //顶点数不能为负 G.vexnum=v; scanf(\、;

if(a<0) return ERROR; //边数不能为负 G.arcnum=a; for(m=0;m

G.vertices[m].data=getchar(); //输入各顶点的符号 for(m=1;m<=a;m++)

31

{

t=getchar();h=getchar(); //t为弧尾,h为弧头 if((i=LocateVex(G,t))<0) return ERROR;

if((j=LocateVex(G,h))<0) return ERROR; //顶点未找到 p=(ArcNode*)malloc(sizeof(ArcNode));

if(!G.vertices.[i].firstarC、 G.vertices[i].firstarc=p; else {

for(q=G.vertices[i].firstarc;q->nextarc;q=q->nextarC、; q->nextarc=p; }

p->adjvex=j;p->nextarc=NULL; }//while return OK; }//Build_AdjList

2.试在邻接矩阵存储结构上实现图的基本操作：DeleteArc(G,v,w) ，即删除一条边的操作。（如果要删除所有从第i个顶点出发的边呢？ 提示： 将邻接矩阵的第i行全部置0 ） 解：//本题中的图G均为有向无权图。

Status Delete_Arc(MGraph &G,char v,char w)//在邻接矩阵表示的图G上删除边(v,w) {

if((i=LocateVex(G,v))<0) return ERROR; if((j=LocateVex(G,w))<0) return ERROR; if(G.arcs[i][j].adj) {

G.arcs[i][j].adj=0; G.arcnum--; }

return OK; }//Delete_Arc

3.试基于图的深度优先搜索策略写一算法，判别以邻接表方式存储的有向图中是否存在由顶点vi到顶点vj的路径（i≠j）。注意：算法中涉及的图的基本操作必须在此存储结构上实现。

32

int visited[MAXSIZE]; //指示顶点是否在当前路径上

int exist_path_DFS(ALGraph G,int i,int j)//深度优先判断有向图G中顶点i到顶点j 是否有路径,是则返回1,否则返回0 {

if(i==j) return 1; //i就是j else {

visited[i]=1;

for(p=G.vertices[i].firstarc;p;p=p->nextarC、 {

k=p->adjvex;

if(!visited[k]&&exist_path(k,j)) return 1;//i下游的顶点到j有路径 }//for }//else

}//exist_path_DFS

第九章 查找 一、填空题

1、在数据的存放无规律而言的线性表中进行检索的最佳方法是 顺序查找（线性查找） 。 2、线性有序表（a1，a2，a3，?，a256)是从小到大排列的，对一个给定的值k，用二分法检索表中与k相等的元素，在查找不成功的情况下，最多需要检索 8 次。设有100个结点，用二分法查找时，最大比较次数是 7 。

3、假设在有序线性表a[20]上进行折半查找，则比较一次查找成功的结点数为1；比较两次查找成功的结点数为 2 ；比较四次查找成功的结点数为 8 ；平均查找长度为 3.7 。

4、折半查找有序表（4，6，12，20，28，38，50，70，88，100），若查找表中元素20，它

将依次与表中元素 28，6，12，20 比较大小。

5、在各种查找方法中，平均查找长度与结点个数n无关的查找方法是 散列查找 。 6、散列法存储的基本思想是由 关键字的值 决定数据的存储地址。

7、有一个表长为m的散列表，初始状态为空，现将n（n

8、设一哈希表表长M为100 ，用除留余数法构造哈希函数，即H（K）=K MOD P（P<=M）, 为使函数具有较好性能，P应选（ 97 ）

9、在各种查找方法中，平均查找长度与结点个数无关的是哈希查找法

33

10、对线性表进行二分查找时，要求线性表必须以 顺序方式存储，且结点按关键字有序排列。

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

12、顺序查找n个元素的顺序表，若查找成功，则比较关键字的次数最多为_n__次；当使用监视哨时，若查找失败，则比较关键字的次数为_ n+1。

13、在有序表A[1..12]中，采用二分查找算法查等于A[12]的元素，所比较的元素下标依次为_____6,9,11,12 _____。

14、在有序表A[1..20]中，按二分查找方法进行查找，查找长度为5的元素个数是__5 15、已知二叉排序树的左右子树均不为空，则左子树_上所有结点的值均小于它的根结点值，_右子树_上所有结点的值均大于它的根结点的值。

二、单项选择题

1、在表长为ｎ的链表中进行线性查找，它的平均查找长度为（ B ）。

A、ＡＳＬ＝ｎ; B、ＡＳＬ＝（ｎ＋１）／２; C、ＡＳＬ＝n＋１; D、ＡＳＬ≈ｌｏｇ２（ｎ＋１）－１

2、折半查找有序表（4，6，10，12，20，30，50，70，88，100）。若查找表中元素58，则它将依次与表中（ A 比较大小，查找结果是失败。

A、20，70，30，50 B、30，88，70，50 C、20，50 D、30，88，50 3、对22个记录的有序表作折半查找，当查找失败时，至少需要比较（ C ）次关键字。

A、3 B、4 C、5 D、 6 4、链表适用于（ A ）查找。

A、顺序 B、二分法 C、顺序，也能二分法 D、随机 5、折半搜索与二叉搜索树的时间性能（ C ）。

A、相同 B、完全不同 C、有时不相同 D、数量级都是O（log2n） 6、散列表的地址区间为0-17,散列函数为H(K)=K mod 17。采用线性探测法处理冲突，并将关键字序列26，25，72，38，8，18，59依次存储到散列表中。元素59存放在散列表中的地址是（ D ）。

A、 8 B. 9 C、 10 D、11 7、当采用分快查找时，数据的组织方式为 ( B )。 A、数据分成若干块，每块内数据有序

B、数据分成若干块，每块内数据不必有序，但块间必须有序，每块内最大（或最小）的数据组成索引块

C、数据分成若干块，每块内数据有序，每块内最大（或最小）的数据组成索引块 D、数据分成若干块，每块（除最后一块外）中数据个数需相同

34

8、散列函数有一个共同的性质，即函数值应当以( D )取其值域的每个值。 A、最大概率 B、最小概率 C、平均概率 D、同等概率

9、假定有k个关键字互为同义词，若用线性探测法把这k个关键字存入散列表中，至少要进行多少次探测？( D )。

A、k-1次 B. k次 C、 k+1次 D、k（k+1）/2次

10、哈希查找中k个关键字具有同一哈希值，若用线性探测法将这k个关键字对应的记录存入哈希表中，至少要进行( )次探测。

A、k B、k+1 C、k(k+1)/2 D、1+k(k+1)/2

11、在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡结点为A,并已知A的左孩子的平衡因子为0右孩子的平衡因子为1,则应作( C ) 型调整以使其平衡。 A、LL B、LR C、RL D、RR

12、二叉查找树的查找效率与二叉树的( C )、有关, 在 (B )时其查找效率最低。 (1): A、高度 B、结点的多少 C、树型 D、结点的位置 (2): A、结点太多 B、完全二叉树 C、呈单枝树 D、结点太复杂。

13、在顺序表 ( 3, 6, 8, 10, 12, 15, 16, 18, 21, 25, 30 ) 中，用折半法查找关键码值11，所需的关键码比较次数为（ C ）。

A、 2 B) 3 C、 4 D、 5 14、对包含n个元素的哈希表进行查找，平均查找长度为（ D ）。 A、 O(log2n) B、 O(n) C、 O(nlog2n) D、不直接依赖于n

15、若查找每个记录的概率均等，则在具有n个记录的连续顺序文件中采用顺序查找法查找一个记录，其平均查找长度ASL为( C )。

A、(n-1)/2 B、n/2 C、 (n+1)/2 D、n 16、下面关于二分查找的叙述正确的是 ( D )。

A、表必须有序，表可以顺序方式存储，也可以链表方式存储 B、表必须有序，而且只能从小到大排列

C、表必须有序且表中数据必须是整型，实型或字符型 D、表必须有序，且表只能以顺序方式存储

17. 对线性表进行二分查找时，要求线性表必须（ B ）。 A、以顺序方式存储 B、以顺序方式存储,且数据元素有序 C、以链接方式存储 D、以链接方式存储,且数据元素有序 18、适用于折半查找的表的存储方式及元素排列要求为( D )。 A、链接方式存储，元素无序 B、链接方式存储，元素有序 C、顺序方式存储，元素无序 D、顺序方式存储，元素有序 19、用二分（对半）查找表的元素的速度比用顺序法( D )。

35

A、必然快 B、必然慢 C、相等 D、不能确定

20、当在一个有序的顺序存储表上查找一个数据时，即可用折半查找，也可用顺序查找，但前者比后者的查找速度( C )。

A、必定快 B、不一定 C、在大部分情况下要快 D、取决于表递增还是递减 21、具有12个关键字的有序表，折半查找的平均查找长度（ A ）。 A、3.1 B、4 C、2.5 D、5 22、折半查找的时间复杂性为（ D ）

A、O（n2） B、O（n） C、O（nlogn） D、O（logn） 23、当采用分快查找时，数据的组织方式为 ( B )。 A、数据分成若干块，每块内数据有序

B、数据分成若干块，每块内数据不必有序，但块间必须有序，每块内最大（或最小）的数据组成索引块

C、 数据分成若干块，每块内数据有序，每块内最大（或最小）的数据组成索引块 D、数据分成若干块，每块（除最后一块外）中数据个数需相同 24、二叉查找树的查找效率与二叉树的( C ) 有关。

A、高度 B、结点的多少 C、树型 D、结点的位置 25．在等概率情况下,一棵平衡树的ASL为 ( B )

A、O(1) B、O( log2n ) C、 O((log2n)2) D、O(nlog2n)

26、分别以下列序列构造二叉排序树，与用其它三个序列所构造的结果不同的是( C )。 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)

27、在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡结点为A,并已知A的左孩子的平衡因子为0右孩子的平衡因子为1,则应作( C ) 型调整以使其平衡。 A. LL B. LR C、 RL D、RR 28、下列关于m阶B-树的说法错误的是( D )。 A、根结点至多有m棵子树 B、所有叶子都在同一层次上

C、 非叶结点至少有m/2 (m为偶数)或m/2+1（m为奇数）棵子树 D、 根结点中的数据是有序的

29、下面关于m阶B树说法正确的是( B )。

①每个结点至少有两棵非空子树； ②树中每个结点至多有m一1个关键字; ③所有叶子在同一层上; ④当插入一个数据项引起B树结点分裂后，树长高一层。

36

A、 ①②③ B. ②③ C、 ②③④ D. ③ 30、下面关于B和B+树的叙述中，不正确的是( C ) 。

A、B树和B+树都是平衡的多叉树。 B、B树和B+树都可用于文件的索引结构。 C、B树和B+树都能有效地支持顺序检索。 D、B树和B+树都能有效地支持随机检索。

三、判断题

1、查找相同结点的效率折半查找总比顺序查找高。(× ) 2、索引顺序表的特点是块内可无序，块间要有序。（ √ ）

3、在采用线性探测法处理冲突的散列表中，所有同义词在表中一定相邻。( ?) 4、在平衡二叉树中，任意结点左右子树的高度差（绝对值）不超过1。(√ ) 5、若查找表的长度为n，则顺序查找法的平均查找长度为（n+1）/2。（√ ） 6、折半搜索适用于有序表，包括有序的顺序表和有序的链表。(╳ )

7、采用线性探测法处理散列时的冲突，当从哈希表删除一个记录时，不应将这个记录的所在位置置空，因为这会影响以后的查找。（√ ）

8、在散列检索中，“比较”操作一般也是不可避免的。（√ ）

9、在m阶B-树中每个结点上至少有 个关键字，最多有m个关键字。(× )

10、负载因子 (装填因子)是散列表的一个重要参数，它反映散列表的装满程度。（√ ） 11、散列法的平均检索长度不随表中结点数目的增加而增加，而是随负载因子的增大而增大。（√ ）

12、哈希表的结点中只包含数据元素自身的信息，不包含任何指针。 (× ) 13、若散列表的负载因子α<1，则可避免冲突的产生。(× )

14、用向量和单链表表示的有序表均可使用折半查找方法来提高查找速度。(× )

15、在平衡二叉树中，向某个平衡因子不为零的结点的树中插入一新结点，必引起平衡旋转。(× )

16、顺序查找法适用于存储结构为顺序或链接存储的线性表。（√ ）

17、就平均查找长度而言，分块查找最小，折半查找次之，顺序查找最大。(× )

18、对大小均为n的有序表和无序表分别进行顺序查找，在等概率查找的情况下，对于查找

成功，它们的平均查找长度是相同的，而对于查找失败，它们的平均查找长度是不同的。（√ ）

19、任一查找树(二叉分类树)的平均查找时间都小于用顺序查找法查找同样结点的线性表的平均查找时间. (× )

20、在二叉树排序树中插入一个新结点，总是插入到叶结点下面。(× )

37

四、简答题

1、对分（折半）查找适不适合链表结构的序列，为什么？用二分查找的查找速度必然比线性查找的速度快，这种说法对吗？

答：不适合！虽然有序的单链表的结点是按从小到大（或从大到小）顺序排列，但因其存储结构为单链表，查找结点时只能从头指针开始逐步搜索，故不能进行折半查找。

二分查找的速度在一般情况下是快些，但在特殊情况下未必快。例如所查数据位于首位时，则线性查找快；而二分查找则慢得多。

2、假定对有序表：（3，4，5，7，24，30，42，54，63，72，87，95）进行折半查找，试回答下列问题：

（1） 画出描述折半查找过程的判定树； （2） 若查找元素54，需依次与哪些元素比较？ （3） 若查找元素90，需依次与哪些元素比较？

（4） 假定每个元素的查找概率相等，求查找成功时的平均查找长度。 解：

（1） 先画出判定树如下（注：mid=?(1+12)/2?=6）：

30

5 63 3 7 42 87 4 24 54 72 95 (2) 查找元素54，需依次与30, 63, 42, 54 等元素比较； (3) 查找元素90，需依次与30, 63,87, 95, 72等元素比较；

（4） 求ASL之前，需要统计每个元素的查找次数。判定树的前3层共查找1＋2×2＋4×3=17次；

但最后一层未满，不能用8×4，只能用5×4=20次， 所以ASL＝1/12（17＋20）＝37/12≈3.08

3、设哈希（Hash）表的地址范围为0～17，哈希函数为：H（K）＝K MOD 16。

K为关键字，用线性探测法再散列法处理冲突，输入关键字序列： （10，24，32，17，31，30，46，47，40，63，49） 造出Hash表，试回答下列问题： （1） 画出哈希表的示意图；

（2） 若查找关键字63，需要依次与哪些关键字进行比较？ （3） 若查找关键字60，需要依次与哪些关键字比较？

（4） 假定每个关键字的查找概率相等，求查找成功时的平均查找长度。 解： （1）画表如下：

38

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 30 31 46 47 32 17 63 49 24 40 10 （2） 查找63,首先要与H(63)=63=15号单元内容比较，即63 vs 31 ,no; 然后顺移，与46,47,32,17,63相比，一共比较了6次！

（3）查找60,首先要与H(60)=60=12号单元内容比较，但因为12号单元为空（应当有空标记），所以应当只比较这一次即可。

（4） 对于黑色数据元素，各比较1次；共6次；

对红色元素则各不相同，要统计移位的位数。“63”需要6次，“49”需要3次，“40”需要2次，“46”需要3次，“47”需要3次，

所以ASL=1/11（6＋2＋3×3）＝17/11=1.5454545454≈1.55

4、设哈希表长度为11，哈希函数H（K）=（K的第一字母在字母表中的序号）MOD11，若输入顺序为（D，BA，TN，M，CI，I，K，X，TA、，处理冲突方法为线性探测再散列或链地址法，要求构造哈希表，并求出等概率情况下查找成功平均查找长度。

0 K ASL=20/9 0

1 2 3 4 5 6 7 8 9 10 1 TA 2 BA 3 M 4 D 5 CI 6 X 7 8 9 TN 10 I

ASL=15/9

5、输入一个正整数序列{100，50，302，450，66，200，30，260}，建立一棵二叉排序树，要求：⑴ 画出该二叉排序树；

⑵ 画出删除结点302后的二叉排序树。

解： 100 50 302 30 66 200 450 260 100 50 260 39 30 66 200 450

6、设有一组关键字：{19，01，23，14，55，20，84，27，68}，采用哈希函数： H（key）=key mod 7，采用开放地址法的线性探测再散列方法解决冲突。 要求：在0∽11的散列地址空间中对该关键字序列构造哈希表。

0 1 2 3 4 5 6 7 8 9 10 11 解： 0 1 2 3 4 5 6 7 8 9 10 11 14 01 23 84 7、已知如下所示长度为12的表： （Jan, Feb, Mar, Apr, May, June, July, Aug, Sep, Oct, Nov, DeC、

(1)试按表中元素的顺序依次插入一棵初始为空的二叉排序树，画出插入完成之后的二叉排序

树，并求其在等概率的情况下查找成功的平均查找长度。

(2)若对表中元素先进行排序构成有序表，求在等概率的情况下对此有序表进行折半查找时查

找成功的平均查找长度。

(3)按表中元素顺序构造一棵平衡二叉排序树，并求其在等概率的情况下查找成功的平均查找

19 55 20 27 68 长度。

8、用开放地址法的二次探测再散列方法Hi=(H(key)+di) mod 10(di=12,22,32,?,)解决冲突。要求：对该关键字序列构造哈希表，并计算查找成功的平均查找长度。 解：

40

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