2024年4月29日发(作者：)
第一章概论
一、名词解释
数据表示2.数据处理3.数据4.数据元素5.逻辑关系6.逻辑结构7.结构
8.运算9.基本运算10.存储结构11.顺序存储结构12.链式存储结构
13.索引存储结构 14.散列存储结构 15.算法 16.运行终止的程序可执行部分
17.伪语言算法 18.非形式算法 19.时空性能 20.时间复杂性 21.数据结构
二、填空题
1.计算机专业人员必须完成的两项基本任务是：_________和__________。
2.数据在计算机存储器中的存在形式称为_________。
3.概括地说，数据结构课程的主要内容包括: 数据的__________、定义在_________、数据
的__________的实现。此外，该课程还要考虑各种结构和实现方法的__________。
4.由一种__________结构和一组__________构成的整体是实际问题的一种数学模型，这种数
学模型的建立、选择和实现是数据结构的核心问题。
5.存储结构是逻辑结构的__________实现。
6.数据表示任务是逐步完成的，即数据表示形式的变化过程是
__________->__________->__________。
7.数据处理任务也是逐步完成的，即转化过程是__________->__________->__________。
8.从数据结构的观点看，通常所说的"数据"应分成三个不同的层次，即__________、
__________和__________。
9.根据需要，数据元素又被称为__________、__________、__________或__________。
10.在有些场合下，数据项又称为__________或__________，它是数据的不可分割的最小标
识单位。
11.从某种意义上说，数据、数据元素和数据项实际反映了数据组织的三个层次，数据
可由若干个__________构成，数据元素可由若干个__________构成。
12.根据数据元素之间关系的不同特性，通常有__________、_________、__________、
__________四类基本逻辑结构，它们反映了四类基本的数据组织形式。
13.根据操作的效果，可将运算分成以下两种基本类型：
①__________型运算，其操作改变了原逻辑结构的“值”，如结点个数、某些结点的内容等；
②__________型运算，其操作不改变原逻辑结构，只从中提取某些信息作为运算的结果。
14.将以某种逻辑结构S为操作对象的运算称为“__________”，简称“__________”。
15.一般地，可能存在同一逻辑结构S上的两个运算A和B，A的实现需要或可以利用B，而
B的实现不需要利用A。在这种情况下，称A可以“__________”为B。
16.存储实现的基本目标是建立数据的__________。
17.一般地，一个存储结构包括__________、__________、__________三个主要部分。
18.通常，存储结点之间可以有__________、__________、__________、_________四种关联
方式，称为四种基本存储方式。
19.可用任何一种存储方式所规定的存储结点之间的关联方式来间接表达给定逻辑
结构S中数据元素之间的逻辑关系。由此得到的存储结构，称为____________________或
__________。
20.一个运算的实现是指一个完成该运算功能的__________。运算实现的核心是处
理步骤的规定，即___________。
21.任何算法都必须用某种语言加以描述。根据描述算法的语言的不同，可将算法分
1
为：___________、___________、___________三类。
22.数据结构课程着重评论算法的___________，又称为“___________”。
23.通常从___________、___________、___________、___________等几方面评价算法的(包
括程序)的质量。
24.一个算法的时空性能是指该算法的___________和______________________，前者是算法
包含的___________，后者是算法需要的___________。
25.通常采用下述办法来估算求解某类问题的各个算法在给定输入下的计算量：
① 根据该类问题的特点合理地选择一种或几种操作作为“___________”；
② 确定每个算法在给定输入下共执行了多少次___________，并将此次数规定为该算法在
给定输入下的___________。
26.通常，一个算法在不同输入下的计算量是不同的。则可用以下两种方式来确定一个算法
的计算量：
① 以算法在所有输入下的计算量的最大值作为算法的计算量，这种计算量称为算法的
________或___________。
② 以算法在所有输入下的计算量的加权平均值作为算法的计算量，这种计算量称为算法的
___________或___________。
27.最坏情况时间复杂性和平均时间复杂性统称为___________或___________。
28.在一般情况下，一个算法的时间复杂性是___________的函数。
29.一个算法的输入规模或问题的规模是指___________。
30.常见时间复杂性的量级有：常数阶O(___________)、对数阶O(___________)、线性阶O
(___________)、平方阶O(___________)、和指数阶O(___________)。通常认为，具有指数
阶量级的算法是___________，而量级低于平方阶的算法是___________的。
31.数据结构的基本任务是数据结构的___________和___________。
32.数据结构的课程的主要内容可以概括为：___________、___________、___________和
___________。
33.___________与数据元素本身的内容和形式无关。
34.从逻辑关系上讲，数据结构主要分为两大类，它们是___________和___________。
35.程序段“for(i=l;i<=n;i++){k++;for(j=1;j<=n;j++)l+=k;}”的时间复杂度T(n)=
___________。
36.程序段“i=1;while(i<=n)i=i*2;”的时间复杂度T(n)= ___________。
三、单项选择题
1.以下说法错误的是
①用数字式计算机解决问题的实质是对数据的加工处理
②程序设计的实质是数据处理
③数据的逻辑结构是数据的组织形式，基本运算规定了数据的基本操作方式
④运算实现是完成运算功能的算法，或这些算法的设计
⑤数据处理方式总是与数据某种相应的表示形式相联系，反之亦然
2.根据数据元素之间关系的不同特性，以下四类基本的逻辑结构反映了四类基本的
数据组织形式。以下解释错误的是 ( )
①集合中任何两个结点之间都有逻辑关系但组织形式松散
②线性结构中结点按逻辑关系依次排列形成一条"锁链"
③树形结构具有分支、层次特性，其形态有点像自然界中的树
2
④图状结构中的各个结点按逻辑关系互相缠绕，任何两个结点都可以邻接
3.关于逻辑结构，以下说法错误的是 ( )
①逻辑结构与数据元素本身的形成、内容无关
②逻辑结构与数据元素的相对位置有关
③逻辑结构与所含结点个数无关
④一些表面上很不相同的数据可以有相同的逻辑结构
⑤逻辑结构是数据组织的某种"本质性"的东西
4.根据操作的效果，可将运算分成加工型运算、引用型运算两种基本类型。对于表格
处理中的五种功能以下解释错误的是 ( )
①查找引用型运算，功能是找出满足某种条件的结点在s(线形结构)中的位置
②读取引用型运算 功能是读出s(线形结构)中某指定位置结点的内容
③插入引用型运算，功能是在s(线形结构)的某指定位置上增加一个新结点
④删除加工型运算，功能是撤消s(线形结构)某指定位置上的结点
⑤更新加工型运算，功能是修改s(线形结构)中某指定结点的内容
5.一般地，一个存储结构包括以下三个主要部分。以下说法错误的是 ( )
①存储结点每个存储结点可以存放一个或一个以上的数据元素
②数据元素之间关联方式的表示 也就是逻辑结构的机内表示
③附加设施，如为便于运算实现而设置的“哑结点”等等
6.一般地，一个存储结构包括以下三个主要部分。以下说法错误的是
①每个存储结点只能存放一个数据元素 ( )
②数据元素之间的关联方式可由存储结点之间的关联方式直接表达
③一种存储结构可以在两个级别上讨论。其一是机器级，其二是语言级
④语言级描述可经编译自动转换成机器级 因此也可以看成是一种机内表示
7.通常从正确性、易读性、健壮性、高效性等四个方面评价算法(包括程序)的质
量。以下解释错误的是 ( )
①正确性 算法应能正确地实现预定的功能(即处理要求)
②易读性 算法应易于阅读和理解 以便于调试 修改和扩充
③健壮性 当环境发生变化时，算法能适当地做出反应或进行处理，不会产生不需要的
运行结果
④高效性 即达到所需要的时间性能
8.对于数据结构课程的主要内容，以下解释正确的是 ( )
①数据结构的定义，包括逻辑结构、存储结构和基本运算集
②数据结构的实现，包括存储实现、运算实现和基本运算集
③数据结构的评价和选择，包括逻辑结构的选择、基本运算集的选择和存储
选择
9，与数据元素本身的形式、内容、相对位置、个数无关的是数据的 ( )
①存储结构②存储实现③逻辑结构④运算实现10顺序存储结构
( )
①仅适合于静态查找表的存储
②仅适合于动态查找表的存储
③既适合静态又适合动态查找表的存储
④既不适合静态又不适合动态查找表的存储
3
11.算法的时间复杂度，都要以通过算法中执行频度最高的语句的执行次数来确定这种
观点 ( )
①正确②错误
12以下说法正确的是 ( )
①所谓数据的逻辑结构指的是数据元素之间的逻辑关系。
②逻辑结构与数据元素本身的内容和形式无关
③顺序文件只适合于存放在磁带上，索引文件只能存放在磁盘上
④基于某种逻辑结构之上的运算，其实现是惟一的
13以下说法正确的是 ( )
①数据元素是数据的最小单位
②数据项是数据的基本单位
③数据结构是带有结构的各数据项的集合
④数据结构是带有结构的数据元素的集合
14以下说法错误的是 ( )
①所谓数据的逻辑结构指的是数据元素之间的逻辑关系的整体
②数据的逻辑结构是指各数据元素之间的逻辑关系，是用户按使用需要而建立的
③数据结构、数据元素、数据项在计算机中的映象分别称为存储结构、结点、数据域
④数据项是数据的基本单位
15通常要求同一逻辑结构中的所有数据元素具有相同的特性，这意味着 ( )
①数据元素具有同一特点
②不仅数据元素所包含的数据项的个数要相同，而且对应数据项的类型要一致
③每个数据元素都一样
④数据元素所包含的数据项的个数要相等
四、简答及应用
1数据与数据元素有何区别？
2·为什么说数据元素之间的逻辑关系是数据内部组织的主要方面?
3·逻辑结构与存储结构是什么关系?
4·运算与运算的实现是什么关系?有哪些相同点和不同点？
5，类C语言与标准C语言的主要区别是什么?
五、算法设计
1、 设计求解下列问题的类C语言算法，并分析其最坏情况时间复杂性及其量级。
（1） 在数组]中查找值为K的元素,若找到则输出其位置i(1<=i<=n),否则输
出0作为标志。
（2） 找出数组]中元素的最大值和次最大值（本小题以数组元素的比较为标
准操作）。
第二章 线性表
一．名词解释
1. 线性结构 2.数据结构的顺序实现 3.顺序表 4.链表 5.数据结构的链接实现
6.建表7.字符串 8.串 9.顺序串 10.链串
二、填空题
1.为了便于讨论，有时将含n(n>=0)个结点的线性结构表示成(a
1
，a
2
,……a
n
)，其中每
个a
i
代表一个______。a
1
称为______结点，a
n
称为______结点，i称为a
i
在线性表中的
4
________或______。对任意一对相邻结点a
i
、a
i┼1
(1<=i i 称为a i┼1 的直接______a i┼1 称 为a i 的直接______。 2.为了满足运算的封闭性，通常允许一种逻辑结构出现不含任何结点的情况。不含任何 结点的线性结构记为______或______。 3.线性结构的基本特征是:若至少含有一个结点，则除起始结点没有直接______外，其 他结点有且仅有一个直接______;除终端结点没有直接______外，其它结点有且仅有一个直 接______. 4.所有结点按1对1的邻接关系构成的整体就是______结构。 5.线性表的逻辑结构是______结构。其所含结点的个数称为线性表的______，简称 ______. 6.表长为O的线性表称为______ 7.线性表典型的基本运算包括:______、______、______、______、______、______等 六种。 8.顺序表的特点是______。 9.顺序表的类型定义可经编译转换为机器级。假定每个datatype类型的变量占用 k(k>=1)个内存单元，其中，b是顺序表的第一个存储结点的第一个单元的内存地址，那么， 第i个结点a i 的存储地址为______。 10.以下为顺序表的插入运算，分析算法，请在______处填上正确的语句。 Void insert_sqlist(sqlistL，datatypex，inti) /*将X插入到顺序表L的第i-1个位置*/ { if( == maxsize) error(“表满”)； if((i<1)||(i>+1))error(“非法位置”); for(j=;j>=i;j--)______; [i-1]=x; =+1; } 11.对于顺序表的插入算法insert_sqlist来说，若以结点移动为标准操作，则插入算 法的最坏时间复杂性为________，量级是________。插入算法的平均时间复杂性为________， 平均时间复杂性量级是________。 12.以下为顺序表的删除运算，分析算法，请在________处填上正确的语句。 void delete_sqlist(sqlist L,int i) /*删除顺序表L中的第i-1个位置上的结点*/ {if((i<1)||(i>))error(“非法位置”)； for(j=i+1;j=;j++)________; =-1; } 13.对于顺序表的删除算法delete_sqlist来说，若以结点移动为标准操作，最坏情况 时间复杂性及其量级分别是________和________,其平均时间复杂性及其量级分别为 ________和________。 14.以下为顺序表的定位运算，分析算法，请在________处填上正确的语句。 int locate_sqlist(sqlist L,datatype X) /*在顺序表L中查找第一值等于X的结点。若找到回传该结点序号；否则回传0*/ {________; 5 while((i≤)&&([i-1]!=X))i++; if(________)return(i); else return(0); } 15.对于顺序表的定位算法，若以取结点值与参数X的比较为标准操作，平均时间复杂 性量级为________。求表长和读表元算法的时间复杂性为________。 16.在顺序表上，求表长运算LENGTH（L）可通过输出________实现，读表元运算 GET（L，i）可通过输出________实现。 17.线性表的常见链式存储结构有________、________和________。 18.单链表表示法的基本思想是用________表示结点间的逻辑关系。 19.所有结点通过指针的链接而组织成________。 20.为了便于实现各种运算，通常在单链表的第一个结点之前增设一个类型相同的结点， 称为________，其它结点称为________。 21.在单链表中，表结点中的第一个和最后一个分别称为________和________。头结点 的数据域可以不存储________，也可以存放一个________或________。 22.单链表INITIATE（L）的功能是建立一个空表。空表由一个________和一个________ 组成。 TE()的功能是建立一个空表。请在________处填上正确的语句。 lklist initiate_lklist() /*建立一个空表*/ {________________; ________________; return(t); } 24.以下为求单链表表长的运算，分析算法，请在 ________处填上正确的语句。 int length_lklist(lklist head) /*求表head的长度*/ {________; j=0; while(p->next!=NULL) {________________; j++; } return(j); /*回传表长*/ } 25.以下为单链表按序号查找的运算，分析算法，请在____处填上正确的语句。 pointer find_lklist(lklist head,int i) { p=head;j=0; while(________________) { p=p->next; j++; } if(i==j) return(p); else return(NULL); } 26.以下为单链表的定位运算，分析算法，请在____处填上正确的语句。 6 int locate_lklist(lklist head,datatype x) /*求表head中第一个值等于x的结点的序号。不存在这种结点时结果为0*/ { p=head;j=0; while(________________________________){p=p->next;j++;} if (p->data==x) return(j); else return(0); } 27.以下为单链表的删除运算，分析算法，请在____处填上正确的语句。 void delete_lklist(lklist head,int i) { p=find_lklist(head,i-1); if(____________________________) { q=________________; p->next=p->next; free(q); } else error(“不存在第i个结点”) } 28.以下为单链表的插入运算，分析算法，请在____处填上正确的语句。 void insert_lklist(lklist head,datatype x,int i) /*在表head的第i个位置上插入一个以x为值的新结点*/ { p=find_lklist(head,i-1); if(p==NULL)error(“不存在第i个位置”)； else {s=________________;s->data=x; s->next=________________; p->next=s; } } 29.以下为单链表的建表算法，分析算法，请在____处填上正确的语句。 lklist create_lklist1() /*通过调用initiate_lklist和insert_lklist算法实现的建表算法。假定$是结束标志 */ { ininiate_lklist(head); i=1; scanf(“%f”,&x); while(x!=’$’) {________________; ________________; scanf(“%f”,&x); } return(head); } 该建表算法的时间复杂性约等于____________，其量级为____________。 7 30.以下为单链表的建表算法，分析算法，请在____处填上正确的语句。 lklist create_lklist2() /*直接实现的建表算法。*/ { head=malloc(size); p=head; scanf(“%f”,&x); while(x!=’$’) { q=malloc(size); q->data=x; p->next=q; ________________; scanf(“%f”,&x); } ________________; return(head); } 此算法的量级为________________。 31．除单链表之外，线性表的链式存储结构还有_________和_________等。 32．循环链表与单链表的区别仅仅在于其尾结点的链域值不是_________，而是一个指 向_________的指针。 33．在单链表中若在每个结点中增加一个指针域,所含指针指向前驱结点，这样构成的 链表中有两个方向不同的链，称为______。 34．C语言规定，字符串常量按______处理，它的值在程序的执行过程中是不能改变的。 而串变量与其他变量不一样，不能由______语句对其赋值。 35．含零个字符的串称为______串，用______表示。其他串称为______串。任何串中所 含______的个数称为该串的长度。 36．当且仅当两个串的______相等并且各个对应位置上的字符都______时，这两个串相 等。一个串中任意个连续字符组成的序列称为该串的______串，该串称为它所有子串的 ______串。 37．串的顺序存储有两种方法：一种是每个单元只存一个字符，称为______格式，另一 种是每个单元存放多个字符，称为______格式。 38．通常将链串中每个存储结点所存储的字符个数称为______。当结点大小大于1时， 链串的最后一个结点的各个数据域不一定总能全被字符占满，此时，应在这些未用的数据域 里补上______。 三、单向选择题 1．对于线性表基本运算，以下结果是正确的是 ( ) ①初始化INITIATE(L)，引用型运算，其作用是建立一个空表L=Ф . ② 求表长LENGTH(L)，引用型运算，其结果是线性表L的长度 ③读表元GET(L,i), 引用型运算。若1<=i<=LENGTH(L),其结果是线性表L的第i个结点； 否则，结果为0 ④定位LOCATE(L,X), 引用型运算.若L中存在一个或多个值与X相等的结点，运算结果为 这些结点的序号的最大值；否则运算结果为0 ⑤插入INSERT(L,X,i),加工型运算。其作用是在线性表L的第i+1个位置上增加一个以X 8 为值的新结点 ⑥删除DELETE(L,i), 引用型运算.其作用是撤销线性表L的第i个结点Ai 2.线性结构中的一个结点代表一个 （ ） ① 数据元素 ② 数据项 ③ 数据 ④ 数据结构 3．顺序表的一个存储结点仅仅存储线性表的一个 （ ） ① 数据元素 ② 数据项 ③ 数据 ④ 数据结构 4．顺序表是线性表的 （ ） ①链式存储结构 ②顺序存储结构 ③ 索引存储结构 ④ 散列存储结构 5.对于顺序表，以下说法错误的是 （ ） ①顺序表是用一维数组实现的线性表，数组的下标可以看成是元素的绝对地址 ②顺序表的所有存储结点按相应数据元素间的逻辑关系决定的次序依次排列 ③顺序表的特点是:逻辑结构中相邻的结点在存储结构中仍相邻 ④顺序表的特点是:逻辑上相邻的元素，存储在物理位置也相邻的单元中 6.对顺序表上的插入、删除算法的时间复杂性分析来说，通常以（ ）为标准操作 ①条件判断 ②结点移动 ③算术表达式 ④赋值语句 7.对于顺序表的优缺点，以下说法错误的是 （ ） ①无需为表示结点间的逻辑关系而增加额外的存储空间 ②可以方便地随机存取表中的任一结点 ③插人和删除运算较方便 ④由于顺序表要求占用连续的空间，存储分配只能预先进行(静态分配) ⑤容易造成一部分空间长期闲置而得不到充分利用 8.指针的全部作用就是 （ ） ①指向某常量 ② 指向某变量 ③指向某结点 ④存储某数据 9.除了( ) ，其它任何指针都不能在算法中作为常量出现，也无法显示。 ①头指针 ②尾指针 ③指针型变量 ④空指针 10.单链表表示法的基本思想是指针P表示结点间的逻辑关系，则以下说法错误的是 （ ） ①任何指针都不能用打印语句输出一个指针型变量的值 ②如果要引用(如访问)p所指结点，只需写出p(以后跟域名)即可 ③若想修改变量p的值(比如让P指向另一个结点)，则应直接对p赋值 ④对于一个指针型变量P的值。只需知道它指的是哪个结点 ⑤结点*ｐ是由两个域组成的记录，p->data是一个数据元素，p->next的值是一个指针 11.单链表的一个存储结点包含 （ ） ①数据域或指针域 ②指针域或链域 ③指针域和链域 ④数据域和链域 12.对于单链表表示法，以下说法错误的是 （ ） ①数据域用于存储线性表的一个数据元素 9 ②指针域或链域用于存放一个指向本结点所含数据元素的直接后继所在结点的指针 ③所有数据通过指针的链接而组织成单链表 ④NULL称为空指针，它不指向任何结点，只起标志作用 13.对于单链表表示法，以下说法错误的是 （ ） ①指向链表的第一个结点的指针，称为头指针 ②单链表的每一个结点都被一个指针所指 ③任何结点只能通过指向它的指针才能引用 ④终端结点的指针域就为NULL ⑤尾指针变量具标识单链表的作用，故常用尾指针变量来命名单链表 14．有时为了叙述方便，可以对一些概念进行简称，以下说法错误的是 （ ） ①将“指针型变量”简称为“指针” ②将“头指针变量”称为“头指针” ③将“修改某指针型变量的值”称为“修改某指针” ④将“p中指针所指结点”称为“P值” 15．设指针P指向双链表的某一结点，则双链表结构的对称性可用（ ）式来刻画 ① p->prior->next->==p->next->next ② p->prior->prior->==p->next->prior ③ p->prior->next->==p->next->prior ④ p->next->next==p->prior->prior 16.以下说法错误的是 （ ） ①对循环链表来说，从表中任一结点出发都能通过前后操作而扫描整个循环链表 ②对单链表来说，只有从头结点开始才能扫描表中全部结点 ③双链表的特点是找结点的前趋和后继都很容易 ④对双链表来说，结点*P的存储位置既存放在其前趋结点的后继指针域中，也存放在它 的后继结点的前趋指针域中。 17．在循环链表中，将头指针改设为尾指针（rear）后，其头结点和尾结点的存储位置分别 是 （ ） ①real和rear->next->next ②rear->next 和real ③rear->next->next和rear ④rear和rear->next 18.以下说错误的是 ( ) ①对于线性表来说，定位运算在顺序表和单链表上的量级均为O（n） ②读表元运算在顺序表上只需常数时间O（1）便可实现，因此顺序表是一种随机存取结 构 ③在链表上实现读表元运算的平均时间复杂性为O（1） ④链入、摘除操作在链表上的实现可在O（1）时间内完成 ⑤链入、摘除操作在顺序表上的实现，平均时间复杂性为O（n） 19．在串的基本运算中，属于加工型运算的有 （ ） ①EQAL(S,T) ②LENGTH(S) ③CONCAT(S,T) ④REPLACE(S,T,R) ⑤INDEX(S,T) 20. 在串的基本运算中，属于引用型运算的有 （ ） 10 ①ASSIGN(S,T) ②INSERT(S1,i,S2) ③DELETE(S,i,j) ④SUBSTR(S,i,j) ⑤REPLACE(S,T,R) 21．循环链表主要优点是 （ ） ①不再需要头指针了 ②已知某个结点的位置后，能够容易找到它的直接前趋 ③在进行插入、删除运算时，能更好地保证链表不断开 ④从表中任一结点出发都能扫描到整个链表 22，每种数据结构都具备三个基本操作:插入、删除和查找，这种说法 （ ） ①正确 ②错误 23．以下说法错误的是 （ ） ①数据的物理结构是指数据在计算机内实际的存储形式 ②算法和程序没有区别，所以在数据结构中二者是通用的 ③对链表进行插人和删除操作时，不必移动结点 ④双链表中至多只有一个结点的后继指针为空 24．以下说法正确的是 ①线性结构的基本特征是：每个结点有且仅有一个直接前趋和一个直接后继 ②线性表的各种基本运算在顺序存储结构上的实现均比在链式存储结构上的实现效率 要低 ③在线性表的顺序存储结构中，插人和删除元素时，移动元素的个数与该元素位置有关 ④顺序存储的线性表的插人和删除操作不需要付出很大的代价，因为平均每次操只有近 一半的元素需要移动 25．以下说法错误的是 （ ） ①求表长、定位这二种运算在采用顺序存储结构时实现的效率不比采用链式存储结构时 实现的效率低 ②顺序存储的线性表可以随机存取 ③由于顺序存储要求连续的存储区域，所以在存储管理上不够灵活 ④线性表的链式存储结构优于顺序存储结构 26．以下说法错误的是 （ ） ①线性表的元素可以是各种各样的，逻辑上相邻的元素在物理位置上不一定相邻 ②在线性表的顺序存储结构中，逻辑上相邻的两个元素在物理位置上不一定相邻 ③在线性表的链式存储结构中，逻辑上相邻的元素在物理位置上不一定相邻 ④线性表的链式存储结构的特点是用一组任意的存储单元存储线性表的数据元素 27．以下说法正确的是（ ） ①在单链表中，任何两个元素的存储位置之间都有固定的联系，因为可以从头结点进行 查找任何一个元素 ②在单链表中，要取得某个元素，只要知道该元素的指针即可，因此，单链表是随机存 取的存储结构 ③顺序存储结构属于静态结构，链式结构属于动态结构 ④顺序存储方式只能用于存储线性结构 28.以下说法正确的是（ ） ①顺序存储方式的优点是存储密度大、且插入、删除运算效率高 ②链表的每个结点中都恰好包含一个指针 11 ③线性表的顺序存储结构优于链式存储结构 ④顺序存储结构属于静态结构，链式结构属于动态结构 29.下面关于线性表的叙述正确的是( ) ①线性表采用顺序存储，必须占用一片连续的存储单元 ②线性表采用顺序存储，便于进行插人和删除操作 ③线性表采用链接存储，不必占用一片连续的存储单元 ④线性表采用链接存储，不便于插人和删除操作 30.线性表L=(a 1 ,a 2 ,...,a i ,...,a n ),下列说法正确的是( ) ①每个元素都有一个直接前驱和直接后继 ②线性表中至少要有一个元素 ③表中诸元素的排列顺序必须是由小到大或由大到小的 ④除第一个元素和最后一个元素外其余每个元素都有一个且仅有一个直接前驱和直接 后继 31.线性表的逻辑顺序与存储顺序总是一致的，这种说法( ) ①正确 ②不正确 32.设p,q是指针,若p=q,则*p=*q ,这种说法( ) ①正确 ②不正确 33.线性表若采用链表存储结构时，要求内存中可用存储单元的地址( ) ①必需是联系的 ②部分地址必须是连续的 ③一定是不连续的 ④连续不连续都可以 34.设REAR是指向非空带头结点的循环单链表的尾指针,则删除表首结点的操作可表示为 ( ) ①p=rear; ②rear=rear->next; rear=rear->next; free(rear); free(p) ③rear=rear->next->next; ④ p=rear->next->next; free(rear); rear->next->next=p->next; free(p); 35. 单链表中，增加头结点的目的是为了 ( ) ①使单链表至少有一个结点 ②标示表结点中首结点的位置 ③方便运算的实现 ④说明单链表是线性表的链式存储实现 36线性结构中的一个结点代表一个数据元素，通常要求同一线性结构的所有结点所代表的 数据元素具有相同的特性，这意味着 ① 每个结点所代表的数据元素都一样。 ② 每个结点所代表的数据元素包含的数据项的个数要相等 ③ 不仅数据元素包含的数据项的个数要相同，而且对应数据项的类型要一致 ④ 结点所代表的数据元素有同一特点 37．带头结点的单链表Head为空的判定条件是 ①Head=Null ②Head->next=NULL ③Head->next=Head 38.非空的单循环链表L的尾结点*P,满足 P->next=NULL P=NULL P->next=L P=L. 39.双向链表结点结构如下： 12 LLink data RLink 其中：LLink是指向前驱结点的指针域： data是存放数据元素的数据域； Rlink是指向后继结点的指针域。 下面给出的算法段是要把一个新结点*Q作为非空双向链表中的结点*p的前驱，插入到此双 向链表中。不能正确完成要求的算法段是 ①Q->LLink=P->LLink; ②P->LLink=Q; Q->Rlink=P; Q->Rlink=P; P->LLink=Q; P->LLink->Rlink=Q; P->LLink->Rlink=Q; Q->LLink=P->LLink; ③Q->LLink=P->LLink; Q->Rlink=P; P->LLink->Rlink=Q; P->LLink=Q; 40.若某线性表中最常用的操作是取第i个元素和找第i个元素的前趋元素，则采用（ ） 存储方式最节省时间。 ①顺序表 ②单链表 ③双链表 ④单循环链表 41．串是任意有限个 ①符号构成的集合 ②符号构成的序列 ③字符构成的集合 ④字符构成的序列 四、简答及应用 1． 请用类C语言描述顺序表，并予以解释说明。 2． 请用类C语言描述单链表的类型定义，并予以解释说明。 3． 请用类C语言描述双链表的类型定义，并予以解释说明。 4． 请用类C语言描述顺序串的类型定义。 5． 请用类C语言描述链串的类型定义。 6.叙述以下概念的区别：头指针变量、头指针、头结点、首结点，并说明头指针变量和头结 点的作用。 7．有哪些链表可仅由一个尾指针来惟一确定，即从尾指针出发能访问到链表上任何一个结 点。 8．简述下列每对术语的区别： 空串和空格串;串变量和串常量;主串和子串;串变量的名字与串变量的值。 9．设有 A=””,B="mule"，C="old"，D="my",试计算下列运算的结果(注:A+B是CONCAT（A,B） 的简写,A=" "的 " "含有两个空格)。 (a) A+B (b) B+A (c) D+C+B (d) SUBSTR(B,3,2) (e) SUBSTR(C,1,0) (f) LENGTH(A) (g) LENGTH(D) (h) INDEX(B,D) 13 (i) INDEX(C,"d") (j) INSERT(D,2,C) (k) INSERT(B,1,A) (l) DELETE(B,2,2) (m) DELETE(B,2,0) 10.已知:S="(xyz)*",T="(x+z)*y"。试利用连接、求子串和置换等基本运算，将S转换为T。 五、算法设计 1． 设A=（a 1 ,a 2 ,a 3 ,......a n ）和B=(b 1 ,b 2 ,.. .,b m )是两个线性表（假定所含数据元素均为 整数）。若n=m且a i =b i (i=1,.. .,n),则称A=B;若a i =b i (i=1,.. .,j)且a j+1 j+1 （j 则称A 输出-1，0或者1。 2，试编写在无头结点的单链表上实现线性表基本运算LOCATE(L,X)、INSERT(L,X，i)和 DELETE(L,i)的算法，并和在带头结点的单链表上实现相的算法进行比较。 3．试编写在不带头结点的单链表上实现线性表基本运算LENGTH(L)的算法。 4．假设有两个按数据元素值递增有序排列的线性表A和B，均以单链表作存储结构。编写 算法将A表和B表归并成一个按元素值递减有序（即非递增有序，允许值相同）排列的线性 表C，并要求利用原表(即A表和B表的)结点空间存放表C。 5．设有线性表A=(a 1 ,a 2 ,.. .,a m )和B=(b 1 ,b 2 ,.. .,b n ).试写合并A、B为线性表C的算法， 使得： (a1,b1,...,am,bm,bm1,bn)当mn; C= (a1,b1,...,an,bn,an1,...,am)当mn; 假设A、B均以单链表为存储结构(并且m、n显示保存)。要求C也以单链表为存储结构并利 用单链表A、B的结点空间。 6，设线性表存放在向量A[arrsize]的前elenum分量中，且递增有序。试写一算法，将X 插入到线性表的适当位置上，以保持线性表的有序性，并且分析算法的时间复杂性。 7．已知单链表L中的结点是按值非递减有序排列的，试写一算法将值为x的结点插入表L 中，使得L仍然有序。 8，试分别以顺序表和单链表作存储结构，各写一个实现线性表的就地(即使用尽可能少的附 加空间)逆置的算法，在原表的存储空间内将线性表(a 1 ，a 2 ,.. .,a n )逆置为(a n ,.. .,a 2 ,a 1 )。 9．假设分别以两个元素值递增有序的线性表A、B表示两个集合(即同一线性表中的元素各 不相同)，现要求构成一个新的线性表C，C表示集合A与B的交，且C中元素也递增有序。 试分别以顺序表和单链表为存储结构，填写实现上述运算的算法。 10，已知A、B和C为三个元素值递增有序的线性表，现要求对表A作如下运算： 删去那些 既在表B中出现又在表C中出现的元素。试分别以两种存储结构(一处种顺序结构，一种链 式的)编写实现上述运算的算法。 11．假设在长度大于1的循环链表中，既无头结点也无头指针。s为指向链表中某个结点的 指针，试编写算法删除结点*s的前趋结点。 12．已知一单链表中的数据元素含有三个字符(即:字母字符、数字字符和其它字符)。试编 写算法，构造三个循环链表，使每个循环链表中只含同一类的字符，且利用原表中的结点空 间作为这三个表的结点空间(头结点可另辟空间)。 13.(Josephus环)任给正整数n、k，按下述方法可得排列1，2，……,n的一个置换:将数字 14 1，2，.. .,n环形排列(如图算法设计题13.所示)，按顺时针方向从1开始 计数；计满K 时输出该为之上的数字(并从环中删去该数字)，然后从下一个数字开始继续计数，直到环中 所有数字均被输出为止。例如，n=10,k=3时，输出的置换是3，6，9，2，7，1，8，5，10， 4。试编写一算法，对输人的任意正整数n、k，输出相应的置换 14·在双链表上实现线性表的下列基本运算(a)初始化； (b)定位(c)插入(d)删除。 15·设有一双链表，每个结点中除有prior、data和next三个域外，还有一个访问频度域 freq，在链表被起用之前，其值均初始化为零。每当在双链表上进行一次LOCATEL，X)运算 时，令元素值为X的结点中freq域的值增1，并使此链表中结点保持按访问频度递减的顺 序排列，以便使频繁访问的结点总是靠近表头。试编写实现符合上述要求的LOCATE运算的 算法。 16·若X和Y是用结点大小为1单链表表示的串，设计一个算法找出X中第一个不在y中出 现的字符。 17．在顺序串上实现串的判等运算EQUAL(S,T)。 18．在链串上实现判等运算EQUAL(S,T)。 19．若S和T是用结点大小为1的单链表存储的两个串（S、T为头指针），设计一个算法将 串S中首次与串T匹配的子串逆值。 20．用串的其他运算构造串的子串定位运算index。 第三章 栈、队列和数组 一、名词解释： 1.栈、栈顶、栈底、栈顶元素、空栈2.顺序栈3.链栈4.递归5.队列、队尾、队头6.顺序 队7.循环队8.队满9.链队10.随机存储结构11.特殊矩阵12.稀疏矩阵13.对称方阵14.上 （下）三角矩阵 二、填空题： 1. 栈修改的原则是_________或称________，因此，栈又称为________线性表。在栈 顶进行插入运算，被称为________或________，在栈顶进行删除运算，被称为 ________或________。 2. 栈的基本运算至少应包括________、________、________、________、________五 种。 3. 对于顺序栈，若栈顶下标值top=0,此时，如果作退栈运算，则产生“________”。 4. 对于顺序栈而言，在栈满状态下，如果此时在作进栈运算，则会发生“________”。 5. 一般地，栈和线性表类似有两种实现方法，即________实现和________实现。 6. top=0表示________，此时作退栈运算，则产生“________”；top=sqstack_maxsize-1 表示________，此时作进栈运算，则产生“________”。 7. 以下运算实现在顺序栈上的初始化，请在________处用适当的句子予以填充。 int InitStack(SqStackTp *sq) 15 { ________; return(1);} 8. 以下运算实现在顺序栈上的进栈，请在________处用适当的语句予以填充。 Int Push(SqStackTp *sq,DataType x) { if(sp->top==sqstack_maxsize-1}{error(“栈满”);return(0);} else{________________: ________________=x; return(1);} } 9. 以下运算实现在顺序栈上的退栈，请在________________用适当句子予以填充。 Int Pop(SqStackTp *sq,DataType *x) {if(sp->top==0){error(“下溢”);return(0);} else{*x=________________; ________________; return(1);} } 10. 以下运算实现在顺序栈上判栈空，请在________________处用适当句子予以填充。 Int EmptyStack(SqStackTp *sq) {if(________________) return(1); else return(0); } 11.以下运算实现在顺序栈上取栈顶元素，请在________________处用适当句子予以填 充。 Int GetTop(SqStackTp *sq,DataType *x) {if(________________) return(0); else{*x=________________; return(1);} } 12. 以下运算实现在链栈上的初始化，请在________________处用请适当句子予以填 充。 Void InitStacl(LstackTp *ls){ ________________;} 13.` 以下运算实现在链栈上的进栈，请在处用请适当句子予以填充。 Void Push（LStackTp *ls,DataType x） { LstackTp *p;p=malloc(sizeof(LstackTp)); ________________; p->next=ls; ________________; } 14．以下运算实现在链栈上的退栈，请在________________处用请适当句子予以填充。 Int Pop(LstackTp *ls,DataType *x) {LstackTp *p; 16 if(ls!=NULL) { p=ls; *x=________________; ls=ls->next; ________________; return(1)； }else return(0); } 15. 以下运算实现在链栈上读栈顶元素，请在________________处用请适当句子予以填 充。 Int Get Top(LstackTp *ls,DataType *x) { if(ls!=NULL){ ________________;return(1);} else return(0); } 16.必须注意，递归定义不能是“循环定义”。为此要求任何递归定义必须同时满足如下 条件： ①被定义项在定义中的应用（即作为定义项的出现）具有________________； ②被定义项在最小“尺度”上的定义不是________________的。 17．队列简称________________。在队列中，新插入的结点只能添加到 ________________，被删除的只能是排在________________的结点。 18．队列以线性表为逻辑结构，至少包括________________、________________、 ________________、________________ ________________、五种基本运算。 19．顺序队的出、入队操作会产生“________________”。 20．以下运算实现在循环队上的初始化，请在________________处用适当句子予以填充。 Void InitCycQueue(CycqueueTp *sq) { ________________;sq->rear=0;} 21. 以下运算实现在循环队上的入队列，请在________________处用请适当句子予以填 充。 Int EnCycQueue(CycquereTp *sq,DataType x) { if((sq->rear+1)%maxsize== ________________) {error(“队满”);return(0); else{ ________________; ________________ ________________; return(1); } 22. 以下运算实现在循环队上的出队列，请在________________处用适当句子予以填 充。 Int OutCycQueue(CycquereTp *sq,DataType *x) {if(sq->front== ________________){error(“队空”);return(0)；} else{ ________________; ________________; return(1); 17 } } 23. 以下运算实现在循环队上判队空，请在________________处用适当句子予以填充。 Int EmptyCycQueue(CycqueueTp sq) {if(________________) return(1); else return(0); } 24. 以下运算实现在循环队上取队头，请在________________处用适当句子予以填充。 Int GetHead(CycqueueTp sq,DataType *x) { if(== ________________return(0); else{ *x=[________________ ]; return(1); } 25.链队在一定范围内不会出现________________的情况。当==试， 队中无元素，此时________________。 26．以下运算实现在链队上的初始化，请在________________处用适当句子予以填充。 void InitQueue(QueptrTp *lp) { LqueueTp *p; p=(LqueueTp *)malloc(sizeof(LqueueTp))； ________________； lq->rear=p; (lq->front)->next=________________; } 27. 以下运算实现在链队上的入队列，请在________________处用适当句子予以填充。 Void EnQueue(QueptrTp *lq,DataType x) { LqueueTp *p; p=(LqueueTp *)malloc(sizeof(LqueueTp)); ________________=x; p->next=NULL; (lq->rear)->next=________________; ________________; } 28. 以下运算实现在链队上的出队列，请在________________处用适当句子予以填充。 int OutQueue(QuetrTp *lq,DataType *x) { LqueueTp *s; if(lq->front==lq->rear){erroe(“队空”)；return(0);} else { s=(lq->front)->next; ________________=s->data; (lq->front)->next=________________； if(s->next==NULL) lq->rear=lq->front; free(s); return(1); 18 } } 29. 以下运算实现在链队上判队空，请在________________处用适当句子予以填充 int EmptyQueue(QueptrTp *lq) { if(________________) return(1)； else return(0); } 30. 以下运算实现在链队上读队头元素，请在________________处用适当句子予以填 充。 Int GetHead(QueptrTp lq,DataType *x) { LqueueTp *p; if(==) return(0); else{________________; ________________ =p->data; return(1); } } 31．一般地，一个n维数组可视为其数据元素为___________维数组的线性表。数组通常只 有___________和___________两种基本运算。 32，通常采用___________存储结构来存放数组 。对二维数组可有两种存储方法：一种是以 ___________为主序的存储方式，另一种是以___________为主序的存储方式。C语言数组用 的是以___________序为主序的存储方法；FORTRAN语言用的是以___________序为主序的存 储方法 33．需要压缩存储的矩阵可分为___________矩阵和___________矩阵两种。 34．对称方阵中有近半的元素重复， 若为每一对元素只分配一个存储空间 ，则可将n2个 元素压缩存储到___________个元素的存储空间中。 35．假设以一维数组M（1：n(n+1)/2）作为n阶对称矩阵A的存储结构，以行序为主序存 储其下三角（包括对角线）中的元素，数组M和矩阵A间对应的关系为___________。 36．上三角矩阵中，主对角线上的第t行(1<=t<=n)有___________个元素，按行优先顺序存 放上三角矩阵中的元素a ij 时，a ij 之前的前i-1行共有___________个元素，在第i行上， a ij 是该行的第___________个元素，M[k]和a ij 的对应关系是。 当i>j时，a ij =c,c存放在M[___________]中。 37．下三角矩阵的存储和对称矩阵类似。M[K]和a ij 的对应关系是___________。 38．基于三元组的稀疏矩阵转置的处理方法有两种，以下运算按照矩阵A的列序来进行转置， 请在___________处用适当的句子用以填充。 Trans_Sparmat(SpMatrixTp a,SpMatrixTp *b) { (*b).mu=;(*b).nu=;(*b).tu=; if() { q=1; for(col=1; ___________;col++) for(p=1;p<=;p++) 19 if(___________==col) {(*b).data[q].i=[p].j; (*b).data[q].j=[p].i; (*b).data[q].v=[p].v; ___________; } } 39．基于三元组的稀疏矩阵转置的处理方法有两种，以下计算按照矩阵A的三元组 的次序进行转置，请在___________处用适当的句子用以填充。 Fast_Trans_Sparmat(SpMatrixTp a,SpMatrixTp *b) { (*b).mu=;(*b).nu=;(*b).tu==; if() {for(col=1;___________;col++) num[col]=0; for(t=1;t<=a,tu;t++) num[[t].j]++; cpot[1]=1; for(col=2;col<=;col++) cpot[col]=___________; for(p=1;p<=;p++) { col=[p].j; q=cpot[col]; (*b).data[q].i=[p].j; (*b).data[q].j=[p].i; (*b).data[q].v=[p].v; __________________________; } } } 40．栈称为___________线性表。 ; 41．队称为___________线性表。 42设一个链栈的栈顶指针为ls，栈中结点的格式为 info next,栈空的条件是 ___________；如果栈不为空，则退栈操作为p=ls;___________;ls=ls->next;free(p)。 43．设有二为数组int M[10][20](注：m为0...10,n为0...20),每个元素（整数） 栈两个存储单元，数组的起始地址为2000，元素M[5][10]的存储位置为___________， M[8][19]的存储值为___________。 44．在具有n个单元的循环队列中，队满时共有___________个元素。 45．___________可以作为实现递归函数调用的一种数据结构。 46．数组M中每个元素的长度是3个字节，行下标i从1到8，列下标j从1到0， 从首的址EA开始连续存放在存储其中。若按行方式存放，元素M[8][5]的起始地址为 ___________；若按列优先方式存放，元素M[8][5]的地址为___________。 47．对带有头结点的列队列lq,判定队列中只有一个数据元素的条件是___________。 48．二维数组M的成员是6个字符（每个字符栈一个存储单元）组成的串，行下标i 的范围从0到8，列下标j的范围从1到10，则存放M至少需要___________个字节；M的 第8列和第5行共占___________个字节；若M按行方式存储，元素M[8][5]的起始地址与 20 当M按列优先方式存储时的___________元素的起始地址一致。 三、单项选择题 1．在以下栈的基本运算中，不是加工型运算的是 （ ） ①lnitStack(S) ②Push(S,X)③Pop(S) ④empty(S) 2.以下说法正确的是 ( ) ①因链栈本身没有容量限制,故在用户内存空间的范围内不会出现栈满情况 ②因顺序栈本身没有容量限制,故在用户内存空间的范围内不会出现栈满情况 ③对于链栈而言,在栈满状态下,如果此时再作进栈运算，则会发生“上溢” ④对于顺序栈而言在栈满状态下如果此时再作迸栈运算，则会发生“下溢”。 3．在以下队列的基本运算中，不是加工型运算的是 （ ） ①InitQueue(Q) ②EnQueue(Q,X) ③OutQueu(Q,X) ④GetHead(Q,x) 4.顺序队列的人队操作应为 ( ) ①=+1 []=x ②[]=x =+1 ③=(+1)% maxsize; []=x ④[sqrear]=x =(+1)% maxsize 5.循环队列的人队操作应为 ( ) ①=+1 []=x ②[]=x =+1 ③=(+1)% maxsize []=x ④[]=x =(+1)% maxsize 6.顺序队列的出队操作为 ( ) ①=(+1)% maxsize ②=+1 ③=(+1)% maxsize ④=+1 7.循环队列的出队操作为 ( ) ①=(+1)% maxsize ②=+1 ③=(+)% maxsize ④=+1 8.循环队列的队满条件为 ( ) ①(+1) % mazsize ==(+1) % maxsize; ②(+1 % maxsize ==+1 ③sq.(rear+1) % maxsize == ④ == 9.循环队列的队空条件为 ( ) ①(+1) % maxsize ==(+1) % maxsize ②(+) % maxsize ==+1 ③(+1) % maxsize == ④ == 21 10.数组的数据元素类型DataType可根据实际需要而定义。以下说法完全正确的是 ( ) ①数组的读运算可以读取一个数据元素整体,写运算只能修改一个数据元素的一部分 ②数组的读、写运算可以读取或修改一个数据元素的一部分或一个整体 ③数组的读、写运算只能读取或修改一个数据元素的一部分 ④数组的读、写运算只能读取或修改一个数据元素整体 11．对于以行序为主序的存储结构来说，在数组A[c 1 ···d 1 ，c 2 ···d 2 ]中，c1和d1分别为 数组A的第一个下标的上、下界，c 2 …d 2 分别为第二各下标的上、下界，每个数据元素占K 个存储单元，二维数组中任一元素a[i,j]的存储位置可由( )式确定. ①Loc[i,j]=[( d 2 -c 2 +1)(i-c 1 )+(j- c 2 )]*k ②Loc[i,j]=loc[c 1 , c 2 ]+[( d 2 - c 2 +1)(i-c 1 )+(j- c 2 )]*k ③Loc{i,j}=A[c 1 , c 2 ]+[( d 2 - c 2 +1)(i- c 1 )+(j- c 2 )]*k ④Loc[i,j]=loc[0,0]+[( d 2 - c 2 +1)(i-c 1 )=(j- c 2 )]*k 12对于C语言的二维数组DataType A[m][n],每个数据元素占K个存储单元，二维数组中任 意元素a[i,j] 的存储位置可由( )式确定. ①Loc[i,j]=A[m,n]+[(n+1)*i+j]*k ②Loc[i,j]=loc[0,0]+[(m+n)*i+j]*k ③Loc[i,j]=loc[0,0]+[(n+1)*i+j]*k ④Loc[i,j]=[(n+1)*i+j]*k 13.线性表的顺序存储结构是一种( )的存储结构,线性表的链式存储结构是一种（ ）的 存储结构。 ① 随机存取 ② 顺序存储 14．如果以链表作为栈的存储结构，则退栈操作是 ( ) ①必须判别栈是否满 ②必须判别栈是否空 ③判别栈元素的类型 ④对栈不做任何操作 15对于基于三元组的稀疏矩阵转置的处埋方法以下说法正确的是 ( ) ①按照矩阵A的列序来进行转置，算法的时间复杂度为0(nu+tu) ②按照A的三元组的次序进行转置，算法的时间复杂度为O(nu*tu) ③按照矩阵A的列序来进行转置的方法称快速转置 ④按照矩阵A的列序进行转置,对于tu< 16．稀疏矩阵的压缩存储方法是只存储 ( ) ①非零元素 ② 三元祖（i,j, a ij ）③ a ij ④i,j 17．基于三元组的稀疏矩阵，对每个非零元素a ij ,可以用一个（ ）唯一确定。 ①非零元素 ②三元组(i,j,a ij ) ③ a ij ④i,j 18如果以链表作为栈的存储结构,则退栈操作时 ( ) ①必须判别栈是否满 ②判别栈元素的类型 ③必须判别栈是否空 ④ 队栈不做任何判别 19．设C语言数组Data[m+1]作为循环队列SQ的存储空间， front为队头指针，rear为队 为指针，则执行出队操作的语句为 （ ） ①front=front+1 ② front=（front+1）%m ③rear=(rear+1)%m ④ front=(front+1)%(m+1) 20.三角矩阵可压缩存储到数组（ ）中。 ①M[1:n(n+1)/2+1] ② M[1:n(n+1)/2] 22 ③M[n(n+1)/2+1] ④M[n(n+1)/2] 21.设有一顺序栈S，元素s 1 ,s 2 ,s 3 ,s 4 ,s 5 ,s 6 依次进栈，如果6个元素出线的顺序是s 2 ,s 3 ,s 4 , s 6 , s 5 ,s 1 ,则栈的容量至少应该是 （ ） ①2 ② 3 ③ 5 ④6 22．设有一顺序栈已含3个元素，如下图所示，元素a4正等待进栈。那么下列4个序列 中不可能出现的出栈序列是 （ ） 0 1 2 3 maxsize-1 sq a1 a2 a3 ↑top ①a3,a1,a4,a2 ②a3,a2,a4,a1 ③ a3,a4,a2,a1 ④a4,a3,a2,a1 23.向一个栈顶指针为Top的链中插入一个s所指结点时，其操作步骤为 （ ） ①Top->next=s ② s->next=Top->next;Top->next=s ③s->next=Top;Top=s ④ s->next=Top;Top=Top->next 24.从栈顶指针为Top的链栈中删除一个结点，并将被删节点的值保存到x中，其操作步骤 为（ ） ①x=Top->data;Top=Top->next ②Top=Top->next;x=Top->data ③x=Top;Top=Top->next ④ x=Top->data 25.在一个链队中，若f,r分别为队首、队尾指针，则插入s所指结点的操作为（ ） ①f->next=c;f=s ②r->next=s;r=s ③s->next=r;r=s ④ s->next=f;f=s 26常对数组进行的两种基本操作是 （ ） ①建立与删除 ② 索引与修改 ③ 查找与修改 ④ 查找与索引 27．链栈与顺序栈相比，有一个比较明显的优点即 （ ） ①插入操作更方便 ② 通常不会出现栈满的情况 ③不会出现栈空的情况 ④ 删除操作更方便 28．若采用三元组压缩技术存储稀疏矩阵，只要把每个元素的行下标和列下标互换，就完成 了对该矩阵的转置运算，这种观点 （ ） ①正确 ②错误 29。二为数组M[i,j]的元素是4个字符（每个字符占一个存储单元）组成的串，行下标i 的范围从O到4，列下标j的范围从O到5。M按行存储时元素M[3,5] 的起始地址与M按列 存储时元素( )的起始地址相同。 ①M [2,4] ② M[3,4] ③M[3,5] ④M[4,4] 30.一个栈的入栈序列是a,b,c,d,e,则栈的不可能的输出序列是 （ ） ① e d c b a ②d e c b a ③d c e a b ④a b c d e 31.一个队列的人列序是1，2，3，4，则队列的输出系列是 （ ） ① 4，3，2，1 ② 1，2，3，4， ③1，4，3，2④ 3，2，4，1 32．设计一个判别表达式中左、右括号是否配对出线的算法，采用（ ）数据结构最佳。 ①线性标的顺序存储结构 ②栈 ③ 队列 ④ 线性表的链式存储结构 33．若已知一个栈的输入序列为1，2，3，...,n,其输出序列为P 1 、P 2 、...P n 。若p 1 =n,则 P 1 为 23 ①i②n=i③ n-i+1 ④ 不确定 34．以下说法正确的是 ①顺序队和循环队的队满和队空判断条件是一样的 ②栈可以作为实现过程调用的一种数据结构 ③插人和删除操作是数据结构中最基本的两种操作，所以这两种操作在数组中也经常使用 ④在循环队列中，front指向队列中第一个元素的前一位置，rear指向实际的队尾元素，队 列为满的条件front=rear 35. 以下说法正确的是 ①数组是同类型值的集合 ②数组是一组相继的内存单元 ③数组是一种复杂的数据结构，数组元素之间的关系，既不是线性的，也不是树形的 ④使用三元组表表示稀疏矩阵的元素，有时并不能节省存储空间 四、简答及应用 1．简述顺序栈的类型定义。 2．简述链栈的类型定义。 3．简述顺序队列、循环队列的类型定义。 4．简述链队的类型定义。 5，写出基于三元组的稀疏矩阵的类型说明。 6．对于循环队列，试写出求队列长度的算法。 7．设有编号为t，2，3，4的四辆列车。顺序进入一个占世界共的展台，试写出这四两列车 开出车站的所有可能的顺序。 8设有上三角矩阵(a ij )n*n,将其上三角元素逐行存于数组B(1:m)中（m充分大），使得B[k]=a ij , 且k=f 1 (i)+f 2 (j)+c。是推导出函数f 1 ,f 2 和常数c(要求f 1 和f 2 中不含常数项)。 9．设有三对角矩阵（a ij ）n*n,将其三条对角线上的元素逐行存于数组B(1:3n-2)中，使得 B[k]=a ij ,求： （1） 用i、j表示k的下标变换公式； （2） 用k表示i、j的下标变换公式. 10.阅读下列程序，写出程序的运行结果。 # define sqstack_maxsize 40 typedef struct sqstack { char data[sqstack_maxsize]; int top; } SqStackTp; main() { SqStackTp sq; int i; char ch; InitStack(&sq); For(ch=’A’;ch<=’A’+12;ch++) { Push(&sq,ch); printf(“%c”,ch); } 24 printf(“n”); while(!EmptyStack(sq)) { Pop(&sq,&ch); printf(“&c”,ch); } printf(“n”); } 11.阅读下列算法，写出其完整的功能。 Void reverse_list( LinkedListTP *head) { LstackTP ls,p; DataType x; InitStack(&ls); p=head->next; While(p!=NULL) { Push(&ls p=p->next;} p=head->next; While(! EmptyStack(&ls)) { Pop(&l,&x); p->data=x; p=p-next;} } 12，对下列函数，按照《数据结构导论》课本的图3-5失利，画出调用f(5)是引起的工作 栈状态变化情况。 Int f(int I) { if(n==1) return(10); else return(f(I-1)+2); } 五、算法设计 1.某汽车轮渡口，过江渡船每次能载10辆车过江。过江车辆分为客车类和货车类， 上渡船的有如下规定：同类车先到先上船；且每上4辆客车，才允许上一辆货车；若等待客 车不足4辆，则以火车代替，若无货车等待允许客车都上船。试写一算法模拟渡口管理。 可以在一个数组中保存两个栈：一个栈以数组的第一个单元作为栈底，另一个栈以 数组的最后一个单元作为栈底（如下图所示）。设S是其中一个占，是分别编写过程 push(S,X)(元素X入栈)， 出栈pop(S)和取栈顶元素Top(S).题示：设其中一个栈为0，另 一栈为1。 0 1 2 M-1 M M+1 ······ 栈0底 栈0顶 栈1顶 栈1底 3．假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾元素结点（注意不设 25 头指针），试编写相应的初始化队列、入队列和出队列算法。 4．假设以数组cycque[m](假设数组范围在0..m)存放循环队列的元素，同时设变量rear 和quelen分别指示循环队列中队尾元素位置和内含元素的个数。试给出此循环队列的队满 条件，并写出相应的入队列和出队列的算法。 5．编写算法:按行优先存储顺序，将稀疏矩阵转换为三元组的表示形式。 6．稀疏矩阵用三元组的表示形式，试写一算法实现两个稀疏矩阵相加，结果仍用三元组表 示。 7．假设一个算术表达式中可以包含三中括号：圆括号“（”和“）”，方括号“[”和“]”以 及花括号与“{”和“}”，且这三种括号可按任意的次序嵌套试用，如 （.. .[.. .{.. .}.. .[.. .].. .].. .( .. .[.. .].. .)。试利用栈的运算编写判断给 定表达式中所含括号是否正确 配对出现的算法（可设表达式已存入字符型数组中）。 8．已知Ackerman函数定义如下： n1当m0时 akm(m,n)= akm(m1,1)当m0,n0时 akm(m1,akm(m,n1))当m0,n0时 试写出递归算法。 9．设函数f(m,n)按下式定义（ m,n为）0的整数） mn1当m*n0时 f(m,n)= f(m1,f(m,n1))当m*n0时 试写出计算函数的递归过程。 10．设有一个背包可以放入的物品重量为S，现有n件物品，重量分别为w 1 ,w 2 ,.. .，w n .问 能否从这n件物品中选择若干件放入此背包，使得放入的重量之和正好为S.如果存在一种 符合上述要求的选择，则称此背包问题有解（或承接为真），否则此问题无解（或结为假）， 试用递归和非递归两种方法设计此背包问题的算法。 11．借助栈(可用栈的基本运算)来实现单链表的逆置运算。 第六章 树 一．名词解释： 1 树 2。结点的度 3。叶子 4。分支点 5。树的度 6．父结点、子结点 7兄弟 8结点的层数 9树的高度 10 二叉树 11 空二叉树 12 左孩子、右孩子 13孩子数 14 满二叉树 15完全二叉树 16 先根遍历 17 中根遍历 18后根遍历 19二叉树的遍历 20 判定树 21 哈夫曼树 二、填空题 1、 树（及一切树形结构）是一种“________”结构。在树上，________结点没有直接前趋。 对树上任一结点X来说，X是它的任一子树的根结点惟一的________。 2、 一棵树上的任何结点（不包括根本身）称为根的________。若B是A的子孙，则称A是 B的________ 3、 一般的，二叉树有______二叉树、______的二叉树、只有______的二叉树、只有______ 的二叉树、同时有______的二叉树五种基本形态。 4、 二叉树第i(i>=1)层上至多有______个结点。 26 5、 深度为k(k>=1)的二叉树至多有______个结点。 6、 对任何二叉树，若度为2的节点数为n2，则叶子数n 0 =______。 7、 满二叉树上各层的节点数已达到了二叉树可以容纳的______。满二叉树也是______二叉 树，但反之不然。 8、 具有n个结点的完全二叉树的深度为______。 9、 如果将一棵有n个结点的完全二叉树按层编号，则对任一编号为i(1<=i<=n)的结点X 有： （1） 若i=1,则结点X是______；若i〉1,则X的双亲PARENT(X)的编号为______。 （2） 若2i>n，则结点X无______且无______；否则，X的左孩子LCHILD(X)的编号 为______。 （3） 若2i+1>n，则结点X无______；否则，X的右孩子RCHILD(X)的编号为______。 10.二叉树通常有______存储结构和______存储结构两类存储结构。 11.每个二叉链表的访问只能从______结点的指针，该指针具有标识二叉链表的作用。 12.对二叉链表的访问只能从______指针开始，若二叉树为空，则______=NULL. 13.二叉链表中每个存储结点的每个指针域必须有一个值，这个值或者是____________的指 针，或者是______。 14.具有n个结点的二叉树中,一共有________个指针域,其中只有________个用来指向结点 的左右孩子，其余的________个指针域为NULL。 15．二叉树有不同的链式存储结构，其中最常用的是________与________。 16．可通过在非完全二叉树的“残缺”位置上增设“________”将其转化为完全二叉树。 17．以下程序段采用先根遍历方法求二叉树的叶子数，请在横线处填充适当的语句。 Void countleaf(bitreptr t,int *count)/*根指针为t，假定叶子数count的初值为 0*/ {if(t!=NULL) {if((t->lchild==NULL)&&(t->rchild==NULL))________; countleaf(t->lchild,&count); ________ } } 18．一棵二叉树由根、左子树和右子树三部分组成，因此对二叉树的遍历也可相应地分解成 ________、________、________三项“子任务”。 19．若以D、L、R分别表示二叉树的三项子任务，限定“先左后右”，这样可能的次序有： ________、________、________三种，按这三种次序进行的遍历分别称为________、________、 ________。 20．树的主要遍历方法有________、________、________等三种。 21．判定树的每个________包含一个条件，对应于一次比较或判断，每个________对应一种 分类结果。 22．设定T是一判定树，其终端结点为n 1 ,……，n k 。每个终端结点ni对应的百分为pi（通 常将p i 称为n 1 的权）。再假定n i 的祖先数为l i ，这样，按T进行分类的平均比较次数为 ________。 23．根据文字说明，请在以下横线处填充适当的语句。 采用静态链表作存储结构，设置一个大小为2n-1的数组,令数组每个元素由四个域组 27 成：wt是结点的权值；lchild、rchild分别为结点的左、右孩子指针；parent是结点的双 亲在数组中的下标。其数组元素类型定义如下： typedef struct {float wt /*权值*/ int parent,lchild rchild; /*指针域*/ }node; typedef node hftree[2*n-1]; 在这种存储结构上的哈夫曼算法可描述如下： void Huffman(int k,float W[k],hftree T) /*求给定权值W的哈夫曼树 T*/ {int i,j,x,y; float m,n; for(i=0;i<2*k-1;i++) { T[i].parent=-1;T[i].lchild=-1;T[i].rchild=-1; if(________)T[i].wt=W[i]; else T[i].wt=0 } for(i=0;i { x=0;y=0;m=maxint;n=maxint; for(j=0;j if((T[j].wt else if((T[j].wt T[x].parent=________;T[y].parent=________; T[k+i].wt=________; T[k+i].lchild=________;T[k+i].rchild=________; } 24．若二叉树的一个叶子是某子树的中根遍历序列中的第一个结点，则它必是该子树的后根 遍历序列中的________个结点。 25．在________遍历二叉树的序列中，任何结点的子树上的所有结点，都是直接跟在该结点 之后。 26．具有n个结点的完全二叉树，若按层次从上到下、从左到右对其编，号（根结点为1 号），则编号最大的分支结点序号是________，编号最小的分支结点序号是________，编号 最大的叶子结点序号是________，编号最小的叶子结点序号是________。 27．二叉树的先根遍历序列中，除根结点外，任一结点均处在其双亲结点的________。 28．先根遍历树和先根遍历与该树对应的二叉树，其结果________。 29．树与二叉树之间最主要的差别是：二叉树中各结点的子树要区分为________和________， 即使在结点只有一棵子树的情况下，也要明确指出该子树是________还是________。 30．由________转换成二叉树时，其根结点的右子树总是空的。 31．哈夫曼树是带权路径度________的树，通常权值较大的结点离根________。 32．有m个叶子结点的哈夫曼树，其结点总数为________。 28 33．一棵树的形状如图填空题33所示，它的根结点是________，叶子结点是________，结 点H的度是________，这棵树的度是________，这棵树的深度是________，结点F的儿子结 点是________，结点G的父结点是________。 34．树的结点数目至少为________，二叉树的结点数目至少为________。 35．________中结点的最大度数允许大于2，而________中结点的最大度数不允许大于2。 36．结点最少的树为________，结点最少的二叉树为________。 37．若一棵二叉树的叶子数为n，则该二叉树中，左、右子树皆非空的结点个数为________。 38．任意一棵具有n个结点的二叉树，若它有m个叶子，则该二叉树上度数为1的结点为 ________个。 39．现有按中序遍历二叉树的结果为ABC，问有________种不同形态的二叉树可以得到这一 遍历结果，这些二叉树分别是________。 40．以数据集{4，5，6，7，10，12，18}为叶结点权值所构造的哈无曼树为________，其带 权路径长度为________。 41．有m个叶子结点的哈夫曼树上的结点数是________。 42．已知一棵度为3的树有2个度为1的结点，3个度过为2的结点，4个度为3的结点， 则该树中有________个叶子结点。 43．设树T的度为4，其中度为1、2、3和4的结点个数分别是4、2、1和1，则T中叶子 结点的个数是________。 三、单向选择题 1． 以下说法错误的是 ( ) ①树形结构的特点是一个结点可以有多个直接前趋 ②线性结构中的一个结点至多只有一个直接后继 ③树形结构可以表达(组织)更复杂的数据 ④树(及一切树形结构)是一种"分支层次"结构 ⑤任何只含一个结点的集合是一棵树 2，以下说法错误的是 ( ) ①二叉树可以是空集 ②二叉树的任一结点都有两棵子树 ③二叉树与树具有相同的树形结构 ④二叉树中任一结点的两棵子树有次序之分 29 3、以下说法错误的是 ( ) ①完全二叉树上结点之间的父子关系可由它们编号之间的关系来表达 ②在三叉链表上，二叉树的求双亲运算很容易实现 ③在二叉链表上，求根，求左、右孩子等很容易实现 ④在二叉链表上，求双亲运算的时间性能很好 4、以下说法错误的是 ( ) ①一般在哈夫曼树中，权值越大的叶子离根结点越近 ②哈夫曼树中没有度数为1的分支结点 ③若初始森林中共有n裸二叉树，最终求得的哈夫曼树共有2n-1个结点 ④若初始森林中共有n裸二叉树，进行2n-1次合并后才能剩下一棵最终的哈夫曼树 5．深度为6的二叉树最多有( )个结点 ( ) ①64 ②63 ③32 ④31 6．将含有83个结点的完全二叉树从根结点开始编号，根为1号，后面按从上到下、从左到 右的顺序对结点编号，那么编号为41的双结点编号为 ( ) ①42 ②40 ③21④20 7．任何一棵二叉树的叶结点在其先根、中根、后跟遍历序列中的相对位置 ( ) ①肯定发生变化 ②有时发生变化 ③肯定不发生变化 ④无法确定 8．设二叉树有n个结点，则其深度为 ( ) ①n-1 ②n ③5floor(log 2 n) ④无法确定 9．设深度为k的二叉树上只有度为0和度为2的节点，则这类二叉树上所含结点总数最少 （ ）个 ①k+1 ②2k ③2k-1 ④2k+1 10.下列说法正确的是 ( ) ①树的先根遍历序列与其对应的二叉树的先根遍历序列相同 ②树的先根遍历序列与其对应的二叉树的后根遍历序列相同 ③树的后根遍历序列与其对应的二叉树的先根遍历序列相同 ④树的后根遍历序列与其对应的二叉树的后根遍历序列相同 11．下列说法中正确的是 ( ) ①任何一棵二叉树中至少有一个结点的度为2 ②任何一棵二叉树中每个结点的度都为2 ③任何一棵二叉树中的度肯定等于2 ④任何一棵二叉树中的度可以小于2 12．一棵二叉树满足下列条件：对任意结点，若存在左、右子树，则其值都小于它的左子树 上所有结点的值，而大于右子树上所有结点的值。现采用（ ）遍历方式就可以得到这棵 二叉树所有结点的递增序列。 ①先根 ②中根 ③后根 ④层次 13．设森林T中有4棵树，第一、二、三、四棵树的结点个数分别是n1,n2,n3,n4,那么当 把森林T转换成一棵二叉树后，且根结点的右子树上有（ ）个结点。 ①n 1 -1 ②n 1 ③n 1 +n 2 +n 3 ④n 2 +n 3 +n 4 14．森林T中有4棵树，第一、二、三、四棵树的结点个数分别是n1,n2,n3,n4,那么当把 森林T转换成一棵二叉树后，且根结点的左孩子上有（ ）个结点。 30 ①n 1 -1 ②n 1 ③n 1 +n 2 +n 3 ④n 2 +n 3 +n 4 15.对含有（ ）个结点的非空二叉树，采用任何一种遍历方式，其结点访问序列均相 同。 ①0 ②1③2 ④不存在这样的二叉树 16．讨论树、森林和二叉树的关系，目的是为了（ ） ①借助二叉树上的运算方法去实现对树的一些运算 ②将树、森林按二叉树的存储方式进行存储 ③将树、森林转换成二叉树 ④体现一种技巧，没有什么实际意义 17．如图选择题17所示二叉树的中序遍历序列是（ ） ①abcdgef ② dfebagc ③dbaefcg ④defbagc 18.已知某二叉树的后续遍历序列是dabec,中序遍历序列是deabc,它的前序遍历序列是 （ ） ①acbed ②deabc ③decab ④cedba 19.如果T 2 是由有序树T转化而来的二叉树，那么T中结点的前序就是T 2 中结点的（ ） ①前序 ②中序 ③后序 ④层次序 20．如果T 2 是由有序树T转化而来的二叉树，那么T中结点的后序就是T 2 中结点的（ ） ①前序 ②中序 ③后序 ④层次序 21．某二叉树的前序遍历结点访问顺序是abdgcefh,中序遍历的结点访问顺序是dgbaechf, 则其后序遍历的结点访问顺序是 （ ） ①bdgcefha ②gdbecfha ③④ bdgechfa ④ gdbehfca 22.在图选择题22中的二叉树中，（ ）不是完全二叉树。 31 23、二叉树的前序遍历序列中，任意一个结点均处在其子女结点的前面，这种说法 ( ) ①正确②错误 24、由于二叉树中每个结点的度最大为2，所以二叉树是一种特殊的树，这种说法 ( ) ①五确②错误 25，二叉树是每个结点的度不超过2的有序树的特殊情况，这种说法 ( ) ①正确②错误 26·树最适合用来表示 ( ) ①有序数据元素②无序数据元素 ③元素之间具有分支层次关系的数据④元素之间无联系的数据 27，深度为5的二叉树至多有( )个结点。 ①16 ②32 ③31 ④10 28、在计算递归函数时，如不使用递归过程，则一般情况下必须借助于（ ）数据结构 ①栈②树③双向队列④顺序表 29.堆(Heap)是 ( ) ①完全二叉树②线性表③满二叉树 30、下列说法中正确的是 ( ) ①二叉树中任何一个结点的度都为2 ②二叉树的度为2 ③任何一棵二叉树中至少有一个结点的度为2 ④一棵二叉树的度可以小于2 31、设二叉树根结点的层次为0，一棵高度为h的满二叉树中的结点个数是（ ） hh-1hh+1 ①2②2③2-1 ④2-1 32、设二叉树结点的先根序列、中根序列和后根序列中，所有叶子结点的先后顺序( ) ①都不相同 ②完全相同 ③先序和中序相同，而与后序不同 ④中序和后序相同，而与先序不同 33·以下说法错误的是 ( ) ①存在这样的二叉树，对它采用任何次序的遍历，其结点访问序列均相同 ②二叉树是树的特殊情形 ③由树转换成二叉树，其根结点的右子树总是空的 ④在二叉树只有一棵子树的情况下也要明确指出该子树是左子树还是右子树 34、以下说法正确的是 ( ) ①先根遍历树和前序遍历与该树对应的二叉树，其结果不同 32 ②后根遍历树和前序遍历与该树对应的二叉树，其结果不同 ③前序遍历森林和前序遍历与该森林对应的二叉树，其结果相同 ④后序遍历森林和中序遍历与该森林对应的二叉树，其结果不同 35·以下说法正确的是 ( ) ①一般来说，若深度为k的n个结点的二叉树具有最小路径长度，那么从根结点到第k-1 k-1k-1 层具有最多的结点数为2-1余下的n-2+1个结点在第k层的任一位置上 ②若有一个结点是某二叉树子树的前序遍历序列中的最后一个结点，则它必是该子树的前序 遍历序列中的最后一个结点。 ③若一个结点是某二叉树子树的前序遍历序列中的最后一个结点，则它必是该子树的中序遍 历序列中的最后一个结点。 ④在二叉树中插人结点，该二叉树便不再是二叉树 36、以下说法正确的是 ( ) ①若一个树叶是某二叉树子树的前序遍历序列中的最后一个结点，则它必是该子树的前序遍 历序列中的最后一个结点。 ②若一个树叶是某二叉树子树的前序遍历序列中的最后一个结点，则它必是该子树的中序离 历序列中的最后一个结点 ③二叉树中，具有两个子女的父结点，在中序遍历序列中，它的后继结点最多只能有一个子 女结点。 ④在二叉树中，具有一个子女结点，在中序遍历序列中，它没有后继子女结点。 37、以下说法错误的是 ( ) ①哈夫曼树是带权路径长度最短的树，路径上权值较大的结点离根较近。 ②若一个二叉树的树叶是某子树的中序遍历序列中的第一个结点，则它必是该子树的后序遍 历序列中的第一个结点。 ③已知二叉树的前序遍历和后序遍历序列并不能惟一地确定这棵树，因为不知道树的根结点 是哪一个。 ④在前序遍历二叉树的序列中，任何结点的子树的所有结点都是直接跟在该结点的之后。 四、简答及应用题 1．简述二叉链表的类型定义。 2．简述三叉链表的类型定义。 3．简述孩子链表表示法的类型定义。 4．分别就图简答题4.1中的二叉树和树回答下列问题 (1)哪个是根结点? (2)哪些是叶结点? (3)哪个是G的双亲? (4)哪些是G的祖先? (5)哪些是G的孩子? (6)哪些是E的子孙? (7)哪些是E的兄弟? 哪些是C的兄弟? (8)结点B和I的层数分别是多少? (9)树的深度是多少? (10)以结点G为根的子树的深度是多少? (11)树的度数是多少？ 33 5．为什么图简答题5所示的结构都不是树形结构？详细说明理由。 6．分别画出含3个结点的树与二叉树的所有不同形态。 7．分别画出图简答题7-1所示二叉树的二叉链表、三叉链表和顺序存储结构。 8．分别写出图简答题4.1（a）所示二叉树的先根、中根和后根序列。 9.试找出分别满足下列条件的所有二叉树： （1） 先根序列和中根序列相同； （2）中根序列和后根序列相同； （ 3 ）先根序列和后根序列相同。 10．已知一棵二叉树的中根序列和后根序列分别为BDCEAFHG和EDCBHGEA，试画出这棵二叉 34 树。 11． 试分别画出图简答题11-1所示树的孩子链表、孩子兄弟链表和静态双亲链表。 12．分别给出简答题11.1图中树的先根、后根和层次遍历的结点访问序列。 13．将图简答题13-1所示的林转换成二叉树。 14．分别画出图简答题14-1所示各二叉树对应的林。 15．给定权值7，18，3，32，5，26，12，8，构造相应的哈夫曼树。 16．试以三种遍历为基础，分别写出在二叉树上查找直接前趋或直接后继的关键操作步骤。 17．已知一棵二叉树的前根序列和中根序列分别为ABDGHECFIJ及GDHBEACIJF，请画出这棵 二叉树。 18．设某密码电文由8个字母组成，每个字母在电文中的出现频率分别是7，19，2，6，32， 3，21，10，试为这8个字母设计相应的哈夫曼编码。 19．有一二叉树如图19-1所示，试画出它的顺序存储结构示意图。 35 20．将图简答20-1所示森林转换为二叉树。 五，算法设计 1、以二叉链表为存储结构，分别实现二叉树的下列运算: （1）PARENT (BT,X)； （2）CREATE ( X, )； (3)DELLEFT(BT,X)。 2.以三叉链表作存储结构重做上题。 3．以二叉链表作存储结构，试编写求二叉树深度的算法。 4．一棵n个结点的完全二叉树存放在二叉树的顺序存储结构中，试编写非递归算法对该树 进行先根遍历。 5．试编写算法判断两棵二叉树是否等价。若二叉树T1和T2等价，则T1和T2都是空的二 叉树；或T1和T2的根结点的值相同，并且T1的左子树与T2的左子树是等价的，T1的右 子树与T2的右子树是等价的。 6．试编写算法交换二叉树中所有结点的左、右子树（自选存储结构）。 7．试编写算法查找二叉链表中数据域值为X的结点（假定各结点的数据域值各不相同），并 打印出X所有祖先的数据域值（提示：利用后根遍历非递归算法）。 8．试以孩子链表为存储结构，实现树数据结构的下列运算： （1）PARENT（T，X）； （2） CHILD (T,X,i)； （3）DELETE(T,X，i)。 9．试分别以孩子兄弟链表和静态双亲链表为存储结构，重做上题。 10．试分别编写二叉树中根遍历在下列存储结构上的非递归算法： （1） 二叉链表； （2） 三叉链表（提示：考虑是否需要引入工作栈）； 11．试分别编写二叉树后根遍历在下列存储结构上的非递归算法： （1） 二叉链表（提示：可在指针进栈的同时将一个标志进栈）； 36 （2） 在存储结点中增设了标志域的mark:0..2的三叉链表（要求不用工作栈）； 12．试编写一个将百分制转换成五分制的算法，要求其时间性能尽可能地高（即平均比较次 数尽可能少）。假定学生成绩的分布情况如下： 分数 比例 0-59 0．05 60-69 0．15 70-79 0．40 80-89 0．30 90-100 0．10 13．有一二叉链表，按后根遍历时输出的结点顺序为a 1 , a 2 ,…a a n 。试编写一算法，要求输 出后根序列的逆序a n ,a n-1 …，a 2 , a 1 。 14．有一二叉链表，试编写按层次顺序遍历二叉树的算法。 15．以二叉链表作为存储结构，试编写求二叉树中叶子数的算法。 第七章 图 一、名词解释 1.图 2.无向完全图 3.有向完全图 4.子图 5.连通分量 6.图的遍历 7.图的最小生成树 8.拓扑排序 一、填空题 1.设x,y是图G中的两顶点，则（x,y）与（y,x）被认为________边，但 的两条弧。 2.若顶点的偶对是有序的，此图为________图，有序偶对用________括号括起来；若顶点偶 对是无序的，此图为________图，无序偶对用________括号括起来。 3.设x,y∈V，若 点，y称为________点。若（x,y）∈E，则在无向图G中x和y间有一条________。 4.在无向图中，若顶点x与y间有边（x,y），则x与y互称________，边（x,y）称为与顶 点x和y________。 5.一个具有n个顶点的完全无向图的边数为________。一个具有n个顶点的完全有向图的弧 度数为________。 6.图的边或弧附带的数值叫________。每条边或弧都带权的图称为________或________。 7.无向图中的顶点V的度是________，记为________。若G是一个有向图，则把以顶点V 为终点的弧的数目称为V的________，记为________；把以顶点V为始点的弧的数目称为V 的________，称为________。有向图中顶点V的度定义为D（V）=________。 8.路径长度定义为________。第一个顶点和最后一个顶点相同的路径称为________或 ________。序列中顶点不重复出现的路径称为________。除了第一个顶点和最后一个顶点外， 其余顶点不重复的回路，称为________或________。 9.在无向图中，如果从顶点v到顶点v’有路径，则称v和v’是_______的。如果对于图中 的任意两个顶点v i ,v j ∈V，且v i 和v j 都是连通的，则称G为________。 10.连通分量是无向图中的________连通子图。 11.一个连通图的生成树是含有该连通图的全部顶点的一个________。 12.若连通图G的顶点个数为n，则G的生成树的边数为________。如果G的一个子图G’的 边数________，则G’中一定有环。相反，如果G’的边数________，则G’一定不连通。 13.无向图的邻接矩阵是一个________矩阵，有向图的邻接矩阵不一定是________矩阵。 14.对于无向图的邻接矩阵，顶点vi的度是________________。对于有向图的邻接矩阵，顶 37 点vi的出度OD（vi）为________________，顶点vi的入度ID(vi)是________________。 15.图的存储结构主要有________和________两种。 16.邻接表表示法是借助________来反映顶点间的邻接关系，所以称这个单链表为邻接表。 17.对无向图，若它有n顶点e条边，则其邻接表中需要________个结点。其中，________ 个结点构成邻接表，________个结点构成顶点表。 18.对有向图，若它有n顶点e条边，则其邻接表中需要________个结点。其中，________ 个结点构成邻接表，________个结点构成顶点表。 19.在邻接表上，无向图中顶点vi的度恰为________________。对有向图，顶点vi的出度 是________________。为了求入度，必须遍历整个邻接表，在所有单链表中，其邻接点域的 值为________的结点的个数是顶点vi的入度。 20.遍历图的基本方法有________优先搜索和________优先搜索两种。 21.以下是图的深度优先算法，请在________处填充适当的语句。 Dfs(GraphTp g,int v) { ArcNodeTp *p; printf(“%d”,v); visited[v]=1; p=________________; while(p!=NULL) {if(!________________) Dfs(g,p->adjvex); p=________________; } } 22.以下是图的广度优先搜索算法，请在________处填充适当的语句。 Bfs(GraphTp g,int v) {QueptrTp Q; ArcNodeTp *p; InitQueue(&Q); printf(“%d”,v); visited[v]=1; ________________ while(!EmptyQueue(Q)) {________________; p=t[v].firstarc; while(p!=NULL) {if(!visited[p->adjvex]) {printf(“%d”,p->>adjvex); visited[[->adjvex]=1; EnQueue(&Q,p->adjvex); } ________________; } } 38 } 23.深度优先搜索遍历类似于树的________遍历，它所用到的数据结构是________；广度优 先搜索遍历类似于树的________遍历，它所用到的数据结构是________。 24.任何连通图的连通分量只有一个，即________。 25.对具有n个顶点的图其生成树有且仅有________条边，即生成树是图的边数________的 连通图。 26.一个图的________的表示法是惟一的，而________表示法是不惟一的。 27.对无向图，其邻接矩阵是一个关于________对称的矩阵。 28.在有向图的邻接矩阵上，由第i行可得到第________个结点的出度，而由第j列可得到 第________个结点的入度。 29.________的有向图，其全部顶点有可能排成一个拓扑序列。 30.一个有向图G中若有弧, i ,V j >、 j ,V k >和 i ,V k >,则在图G的拓扑序列中，顶点V i 、V j 和V k 的相对位置为________。 二、单项选择题 1.设有无向图G=（V，E）和G’=（V’,E’）,如G’为G的生成树，则下面不正确的说法是（ ） ①G’为G的子图 ②G’为G的连通分量 ③G’为G的极小连通子图且V’=V ④G’是G的无环子图 2.任何一个带权的无向连通图的最小生成树（ ） ①只有一棵 ②有一棵或多棵 ③一定有多棵 ④可能不存在 3.设图G采用邻接表存储，则拓扑排序算法的时间复杂度为（ ） ①O(n) ②O(n+e) ③O(n*n) ④O(n*e) 4.含n个顶点的连通图中的任意一条简单路径，其长度不可能超过 （ ） ①1 ② n/2 ③ n-1 ④n 5．一有向图G的邻接表存储结构如图单项选择5所示。现按深度优先遍历算法，从顶点V1 出发，所得到的顶点序列是 （ ） ①V 1 ,V 3 , V 2 ,V 4 , V 5 ②V 1 , V 3 , V 4 , V 2 , V 5 ③V 1 ,V 2 , V 3 , V 4 , V 5 ④V 1 , V 3 , V 4 , V 5 , V 2 6.在无向图中，所有顶点的度数之和是所有边数的（ ）倍。 ①0.5 ②1 ③2 ④4 7.在有向图中，所有顶点的入度之和是所有顶点出度之和的（ ）倍。 （ ） ①0.5 ② 1 ③ 2 ④4 8．在图的邻接表存储结构上执行深度优先搜索遍历类似于二叉树上的 （ ） ①先根遍历 ② 中根遍历 ③ 后根遍历 ④按层次遍历 9．在图的邻接表存储结构上执行广度优先搜索遍历类似于二叉树上的 39 （ ） ①先根遍历 ②中根遍历 ③后根遍历 ④按层次遍历 10．判断一个有向图是否存在回路，除了可以利用拓扑排序方法，还可以利用 （ ） ①求关键路径方法②求最短路径的Dijkstra方法③广度优先遍历方法④深度优先遍历方法 11．在图单项选择中，从顶点V1出发，按广度优先遍历图的顶点序列是 （ ） ①V 1 V 3 V 5 V 4 V 2 V 6 V 7 ②V 1 V 2 V 4 V 7 V 6 V 5 V 3 ③V 1 V 5 V 3 V 4 V 2 V 7 V 6 ④V 1 V 4 V 7 V 2 V 6 V 5 V 3 12.在图单项选择中，从顶点V1出发,广度遍历图的顶点序列是 （ ） ①V 1 V 5 V 3 V 4 V 2 V 6 V 7 ②V 1 V 5 V 3 V 4 V 2 V 7 V 6 ③V 1 V 7 V 2 V 6 V 4 V 5 V 3 ④V 1 V 2 V 4 V 7 V 6 V 5 V 3 13.设有6个结点的无向图，该图至少应有（ ）条边能确保是一个连通图。 （ ） ①5 ② 6 ③7 ④ 8 14.以下说法正确的是 （ ） ①连通图的生成树，是该连通图的一个极小连通子图。 ②无向图的邻接矩阵是对称的，有向图的邻接矩阵一定是不对称的。 ③任何一个有向图，其全部顶点可以排成一个拓扑序列。 ④有回路的图不能进行拓扑排序。 15以下说法错误的是 （ ） ①用相邻矩阵法存储一个图时，在不考虑压缩存储的情况下，所占用的存储空间大小只与图 中结点个数有关，而与图的边数无关。 ②邻接表法只能用于有向图的存储，而相邻矩阵法对于有向图和无向图的存储都适用。 ③存储无向图的相邻矩阵是对称的，因此只要存储相邻矩阵的下（或上）三角部分就可以了 ③用相邻矩阵A表示图，判定任意两个结点Vi和Vj之间是否有长度为m的路径相连，则只 要检查A的第 i行第j列的元素是否为0即可。 16．以下说法正确的是 （ ） ①连通分量是无向图中的极小连通子图。 ②强连通分量是有向图中的极大强连通子图。 ③在一个有向图的拓扑序列中，若顶点a在顶点b之前，则图中必有一条弧 ④对有向图G,如果从任意顶点出发进行一次深度优先或广度优先搜索能访问到每个顶点， 则该图一定是完全图。 四、简答及应用 1． 简述图的邻接矩阵表示的类型定义 2． 简述图的邻接表的类型定义。 3． 给出无向图简答题3中g1的邻接矩阵和邻接表。 40 4．分别给出图简答题3中g2的邻接矩阵、邻接表和逆邻接表。 5．分别给出图简答题3中g3从v5出发按深度优先搜索和广度优先搜索算法遍历得到的顶 点序列。 6．求出图简答题6-1的连通分量。 7．求出带权图简答题7-1的最小生成树 8．写出有向图简答题8-1的拓扑排序序列。 9．给出网图简答题9-1的邻接矩阵表示。 10．已知连通网的邻接矩阵如下，试画出它所表示的连通网及该连通网的最小生成树。 11．对于图简答题11-1从其邻接表中回答下列问题： （1） 图中有多少条弧？ （2） 图中是否存在从i到j的弧？ （3） 如何求顶点i的出度？ 41 12．图简答题11-1所示为一有向图，请给出该图的下述要求： （1） 每个顶点的入/出度。 （2） 邻接矩阵。 （3） 邻接表。 （4） 逆邻接表。 13．拓扑排序的结果不是唯一的，对图简答题13-1进行拓扑排序，试写出其中任意5个不 同的拓扑排序列。 14．对m个顶点的无向图G，采用邻接矩阵，如何判别下列有关问题： （1） 图中有多少条边？ （2） 任意两个顶点i和j是否有边相连？ （3） 任意一个顶点的度是多少？ 15.已知图G的邻接表如图简答题15-1所试，顶点V1为出发点，完成要求： （1） 深度优先搜索的顶点序列； （2） 广度优先搜索的顶点序列； （3） 由深度优先搜索得到的一棵生成树； （4） 由广度优先搜索得到的一棵生成树。 Vertex fi 16.设有一无向图G=(V,E),其中 V={1,2,3,4,5,6},E={(1,2),(1,6),(2,6),(1,4),(6,4),(1,3),(3,4),(6,5),(4,5),(1,5), (3,5)}。 （1） 按上述顺序输入后，画出其相应的邻接表； 42 （2） 在该邻接表上，从顶点4开始，写出DFS序列和BFS序列。 17．图简答题17-1所示为一无向连通网络，先要求根据prim算法构造出它的最小生成树。 五、算法设计 1． 写出将一个无向图的邻接矩阵转换成邻接表的算法。 2． 写出将一个无向图的邻接表转换成邻接矩阵的算法。 3． 试以邻接矩阵为存储结构，分别写出连通图的深度优先和广度优先搜索算法。 4． 写出建立一个有向图的逆邻接表的算法。 5． G为一n个顶点的有向图，其存储结构分别为： （1） 邻接矩阵； （2） 邻接表。 请写出相应存储结构上的计算有向图G出度为0的顶点个数的算法。 6．以邻接表作存储结构，给出拓扑排序算法的实现。 第九章 查找表 一、名词解释 1.查找表2.集合3.查找长度4.有序表5.平衡化6.平衡二叉排序树7.平衡因子8.散列表 9.散列函数10.散列地址11.同义词12.冲突13.开散列表14.拉链法15.堆积 二、填空题 1.对任何集合A而言，A的每一个成员a称为A的一个________，记为________。 2.空集是________的集合，记为________。 3.在集合这种逻辑结构中，任何结点之间都不存在________关系，这是集合这种逻辑结构的 基本特点。 4.集合中没有相同的________。作为一个数学概念，集合的元素没有________。 5.数据元素之间的逻辑关系反映的是________。 6.对于集合这逻辑结构来说，其中的数据元素之间也可以有各种各样的非逻辑关系，但任何 一对数据元素之间没有________关系，即没有________关系。 7.查找表按其所包括的运算的不同分为________查找表和________查找表。 8.查找表中主关键字指的是________，次关键字指的是________。 9.静态查找表包括________、________、________三种基本运算。 10.动态查找表包括________、________、________、________、________五种基本运算。 11.假定key为主关键字，若顺序表中第n个元素的键值为K，则顺序查找算法的查找长度 为1；若第1个元素的键值为K，则查找长度为________；若表中无键值等于K的元素，则 43 查找长度为________。 12.以下算法在有序表R中用二分查找法查找键值等于K的元素，请分析程序，并在________ 上填充合适的语句。 int binsearch(sqtable R,keytype K) {low=1;hig=R.n;/*置查找区间初值。low,hig分别标记查找区间的下、上界*/ while(low<=hig) {mid=（low+hig)/2; switch {case K==[mid].key:return(mid);/*找到，返回位置mid*/ case K<[mid].key:________;break;/*缩小区间*/ case K>[mid].kiy:________;break;/*缩小区间*/ } } return(0);/*若区间长度已为0但仍不成功，则返回0，表示查找不成功*/ } 13.二分查找在查找成功时的查找长度不超过________，其平均查找长度为________，当n 较大时约等于________。 14.一个________表由一个顺序表和一个索引表两部分组成。其中的顺序表在组织形式与普 通的________表完全相同；而索引表本身在组织形式上也是一个________表。 15.索引顺序表的特点表现为以下两个方面：a.顺序表中的数据元素"________"；b.索引表 反映了这些"________"的有关特性。 16.在索引顺序表上，对于顺序表中的每一块，索引表中有相应的一个"索引项"。每个索引 项有两个域：块内最大________值和块________位置。 17.索引顺序表上的查找分两个阶段：一、________；二、________。该查找方法称为________ 查找。 18.静态查找表的三种不同实现各有优缺点。其中，________查找效率最低但限制最少。 ________查找效率最高但限制最强。而________查找则介于上述二者之间。 19.二叉排序树是一种特殊的、增加了限制条件的二叉树，其限制条件是任一结点的键值 ________于其左孩子（及其子孙）的键值且________于其右孩子（及其子孙）的键值。 20.在表示一棵二叉排序树的二叉链表上，要找键值比某结点X的键值________的结点，只 需通过结点X的左指针到它的左子树中去找。 21.中根遍历一棵二叉排序树所得的结点访问序列是键值的________序列。 22.对于一个无序序列，可以通过构造一棵________而使其成为一个有序序列。 23.以下算法在指针T所指的二叉排序树上查找键值等于K的结点。成功时回送指向该结点 的指针；否则回送空指针。请分析程序，并在________填充合适的语句。 bitreptr search_bst(bitreptr T,keytype K) {if(T==NULL)return(NULL); else swith {case T->key==K:________; case________: rerutn(search_bst(T->lchild,K)); case________: rerutn(search_bst(T->rchild,K)); } 44 } 24.二叉排序树上的查找长度不仅与________有关，也与二叉排序树的________有关。 25.在随机情况下，含有n个结点的二叉排序树的平均查找长度为________，其时间效率很 高。 26.二叉排序的查找效率与树的形态有关。当二叉排序树退化为一条单支时，查找算法退化 为________查找，平均查找长度上升为________。 27.有n个结点的AVL树的深度与________是同数量级的，因而在它上面进行查找的平均查 找长度也与________同数量级。 28.平衡二叉排序树上任一结点的平衡因子只可能是________、________或________。 29.采用散列技术时需要考虑的两个主要问题是：一、________？二、________？ 30.按组织形式的不同，通常有________与________两类散列表。 31.以下算法在开散列表HP中查找键值等于K的结点，成功时返回指向该结点的指针，不成 功时返回空指针。请分析程序，并在________上填充合适的语句。 pointer research_openhash(keytype K,openhash HP) {i=H(K); /*计算K的散列地址*/ p=HP[i]; /*i的同义词子表表头指针传给p*/ while(________)p=p->next;/*未达表尾且未找到时，继续扫描*/ ________; } 32以下算法实现若开散列表HP中无键值为K结点，则插入一个这样的结点。请分析程序并 在________上填充合适的语句。 void insert_openhash(keytype K,openhash HP) {if(research_openhash(K,HP)==NULL) {i=H(K); q=malloc(size);q->key=________; /*生成新结点*/ ________=HP[i];HP[i]=________; /*前插法链入新结点*/ } } 33.以下算法实现若开散列表HP中存在键值为K结点，则将其删除。请分析程序并在________ 上填充合适的语句。 void delete_openhash(keytype K,openhash HP) {i=H(K); if(HP[i]==NULL)return;/*空表则退出*/ p=HP[i]; if(p->key==K){_______=p->next;free(p);return;} /*表首结为待点时的删除*/ while(p->next!=NULL) /*其他情况下的删除*/ {q=p;p=p=->next; if(p->key==K){________=p->next;delete(p);return;} } } 34.对闭散列表来说，________的方法就是处理冲突的方法。 35.常见的构造后继散列地址序列的方法有________、________、________、________四种。 45 36.以下算法假定以线性探测法解决冲突，在闭散列表HL中查找键值为K的结点，成功时回 送该位置；不成功时回送标志-1。请分析程序，并在________上填充合适的语句。 int search_cloxehash(keytype K,closehash HL) {d=H(K); /*计算散列地址*/ i=d; while(HL[i].key!=K&&(i!=d-1)i=______;/*未成功且未查遍整个HL时继续扫描*/ if(________)reurn(i); /*查找成功*/ else return(-1); /*查找失败*/ } 37.________查找法的平均查找长度与元个数n个数无关。 38.在分块查找法中，首先查找________，然后再查找找相应的________。 39.在具有24个元素的有序表上进行二分查找，则比较一次查找成功的结点数为________， 比较二次查找成功的结点数为________，比较五次查找成功的结点数为________。总的平均 查找长度为________。 40.在散列存储中，装填因子x的值越大，则________。 41.________是散列表的一个重要参数，它反映出散列表的装满程度。 42.当所有结点的权值都相等时，用这些结点构造的二叉排序树上只有________。 43.在二叉排序树上插入新结点时，不必移动其它结点，仅需使某结点的指针域由________ 变为________即可。 44．二分查找方法仅适用于这样的表：表中的记录必须________，其存储结构必须是 ________。 45.设线性表(a 1 ,a 2 ,…,a 500 )元素的值由小到大排列。对一个给定的k值，用二分法检索查找 表中与k相等的元素，在检索不成功的情况下至多较________次。 46.设线性表L=（a 1 ,a 2 ,…,a n )(n>2),表中元素按值的递增顺序排列。对一个给定的值k，分 别用顺序检索和二分法检索查找与k相等的元素，比较次数分别为s和b ，若检索不成功， 则s和b的数量关系是________。 47.设有两个散列函数H 1 (k)=k mod 13 和H 2 (k)=k mod 11+1，散列表为T[0…12]，用双重 散解决冲突。函数H1用来计算散列地址，当发生冲突时，H 2 作为计算下一个探测地址的地 址增量，假定在某一时刻T的状态为： T: 0 1 2 3 4 5 6 7 8 9 10 11 12 80 85 34 下一个被插入的关键码是42，其插入的位置是:______________。 48.设有一个已按各元素的值排好序的线性表，长度为125，对给定的k值，用二分法查找 与k相等的元素，若查找成功，则至少需要比较________次，至多需比较________次。 三、单项选择题 1． 以下说法错误的是 （ ） ①数字分析法对健值的各位进行分析，选择分布较均匀的若干位组成散列地址。 ②除余法选择一个适当的正整数p,以p除健值以所得的余数作为散列地址。 ③平方取中法以健值平方的中间几位作为散列地址。 ④基数转换法将健值看成另一种进制的数再转换成原来进制的数，然后选择其中几位作为散 列地址。 46 ⑤随机数法选择一个随机函数random,以健值在该函数下的值作为散列地址。 2． 以下所法正确的是 （ ） ①数字分析法需事先知道所有可能出现的健值及所有健值的每一位上各数字的分布情况，并 且健值的位数比散列地址的位数多。 ②除余法要求事先知道全部健值。 ③平方取中法需要事先掌握健值的分布情况。 ④随机数法适用于健值不相等的场合。 3． 除余法选择一正整数p，以健值除以p所得的余数作为散列地址。通常选p为（ ） ①小于或等于散列表长的素数。 ②接近表长的且不与组成关键字的字符基数直接相关的质数。 ③大于或等于散列表长的素数。 ④接近表长的质数。 4．顺序查找法适合于（ ）存储结构的查找表。 ①压缩 ② 散列 ③索引 ④顺序或链式 5．对采用二分查找法进行查找运算的查找表，要求按（ ）方式进行存储。 ①顺序存储 ② 链式存储 ③顺序存储且结点按关键字有序 ④ 链式存储且结点按关键字有序 6．设顺序表的长为n,则其每个元素的平均查找长度是 （ ） ①n ② (n-1)/2 ③ n/2 ④ (n+1)/2 7.设有序表的关键字序列为{1，4，6，10，18，35，42，53，67，71，78，84，92，99}， 当用二分查找法查找健值为84的结点时，经（ ）次比较后查找成功。 ①2 ② 3 ③ 4 ④ 12 8．静态查找表与动态查找表两者的根本差别在于 （ ） ①逻辑结构不同 ② 存储实现不同 ③施加的操作不同 ④ 数据元素的类型不同 9．长度为12的按关键字有序的查找表采用顺序组织方式。若采用二分查找方法，则在等概 率情况下，查找失败时的ASL值是 （ ） ①37/12 ② 62/13 ③ 39/12 ④49/13 10.在表长为n的顺序表中，实施顺序查找，在查找不成功时，与关键字比较的次数为（ ） ①n ②1 ③ n+1 ④n-1 11.二分查找法适用于存储结构为（ ）的，且按关键字排序的线性表。 （ ） ①顺序存储 ② 链接存储 ③ 顺序存储或链接存储 ④索引存储 12．用顺序查找法对具有n个结点的线性表查找的时间复杂性量级为 2 ①O（n） ② O(nlog 2 n) ③ O（n） ④ O(log 2 n) 13．用二分查找法对具有n个结点的线性表查找的时间复杂性量级为 （ ） 2 ①O(n) ② O(nlog 2 n) ③ O(n) ④O(log 2 n) 14．二叉排序树的查找和折半查找的时间性能相同。这种说法 （ ） ①正确 ② 错误 15．与其他查找方法相比，散列查找法的特点是 （ ） ①通过关键字比较进行查找 ②通过关键字计算记录存储地址进行查找 47 ③通过关键字计算记录存储地址，并进行一定的比较进行查找 16．在采用线性探测法处理冲突所构成的闭散列表上进行查找，可能要探测多个位置，在查 找成功的情况下，所探测的这些位置上的健值 （ ） ①一定都是同义词 ② 一定都不是同义词 ③都相同 ④ 健值不一定有序的顺序表 18．设散列函数为H(k)=k mod 7,一组关键码为23，14，9，6，30，12和18，散列表T 的地址空间为0..6,用线性探测法解决冲突，依次将这组关键码插入T中，得到的散列表为 （ ） ①0 1 2 3 4 5 6 14 6 23 9 18 30 12 ② 0 1 2 3 4 5 6 14 18 23 9 30 12 6 ③0 1 2 3 4 5 6 14 12 9 23 30 18 6 ④0 1 2 3 4 5 6 6 23 30 14 18 12 9 19．设有一个用线性探测法解决冲突得到的散列表： T:0 1 2 3 4 5 6 7 8 9 10 13 25 80 16 17 6 14 散列函数为H(k)=kmod 11,若要查找元素14，探测的次数是 （ ① 18 ② 9 ③3 ④6 20．在散列函数H(k)=k MOD m 中，一般来讲，m应取 （ ①奇数 ②偶数 ③ 素数 ④ 充分大的数 21，分块查找的时间性能 （ ①低于二分查找 ② 高于顺序查找而低于二分查找 ③高于顺序查找 ④ 低于顺序查找而高二分查找 22．以下说法正确的是 （ ①顺序查找效率最低但限制最强。 ②二分查找效率最高但限制最少。 ③分块查找效率介于顺序查找和二分查找之间。 23．以下说法正确的是 （ ①查找表中数据元素的任何数据项都可以作为关键字。 ②采用二分查找法对有序表进行查找总比采用顺序查找法对其进行查找要快。 ③二叉排序树的查找和二分查找时间的性能相同。 ④最佳二叉排序树一定是平衡二叉树 ⑤“顺序查找法”是指在顺序表上进行查找的方法。 24．．以下说法错误的是 （ ①散列法存储的基本思想是由关键码的值决定数据的存储地址。 ②散列表的结点中只包含数据元素自身的信息，不包含任何指针。 ③装填因子是散列法的一个重要参数，它反映散列表的装填程度。 ④散列表的查找效率主要取决于散列表造表时选取的散列函数和处理冲突的方法。 48 ） ） ） ） ） ） 25．以下说法错误的是 （ ） ①当所有的结点的权之都相等时，用这些结点构造的二叉排序树的特点是只有右子树 ②中序遍历二叉排序树的结点就可以得到排好序的结点序列。 ③任一二叉排序树的平均检查时间都小于用顺序查找法查找同样结点的线性表的平均查找 时间。 ④对两棵具有相同关键字集合的而形状不同的二叉排序树，按中序遍历它们得到的序列的顺 序是一样的。 ⑤采用分块查找方法，既能实现线性表所希望的较快的查找速度，又能适应动态变化的需要。 26．以下说法正确的是 （ ） ①平衡树一定是丰满树。 ②虽然信息项的序列的顺序不一样，但依次生成的二叉排序树确是一样的。 ③在二叉排序树上插入新的结点时，不必移动其他结点，只需改动某个结点的指针，由空变 为非空即可。 ④在二叉排序树上删除一个结点时，不必移动其他结点，只要将该结点的父结点的相应的指 针域置空即可。 27．长度为12的有序表：Apr,Aug,Dec,Feb,Jan,Jul,Jun,Mar,May,Nov,Oct,Sep,按折半查 找法对该表进行查找。在表内各元素等概率情况下查找成功所需的平均比较次数为（ ）。 ① 35/12 ②37/12 ③39/12 ④43/12 28．已知一采用开放地址法解决Hash表冲突，要从此Hash表中删除一个记录，正确的做法 是 （ ） ①将该元素所在的存储单元清空。 ②将该元素用一个特殊的元素代替 ③将与该元素有相同Hash地址的后继元素顺次前移一个位置。 ④用与该元素有相同Hash地址的最后插入表中的元素替代。 四、简答及应用 1． 写出作为静态查找表存储结构的顺序表的类型定义。 2． 何谓二叉排序树？ 3． 简述开散列表的组织方式及类型定义。 4． 简述闭散列表的类型定义。 5． 简述闭散列表解决冲突的基本思想。 6． 简述二次探测法解决冲突的基本思想。 7． 简述多重散列法解决冲突的基本思想 8． 简述公共溢出区法解决冲突的基本思想。 9． 对长度为20的有序表进行二分查找，试画出它的一棵判定树，并求等概率情况下的平 均查找长度。 10． 给定有序表 D={006,087,155,188,220,465,505,508,511,586,656,670,700,766,897,908}，用二分 查找法在D中查找586，试用图示法表示出查找过程。 11．给定表（19，14，22，01，66，21，83，27，56，13，10）。 （1）试按元素在表中的次序将它们依次插入一棵初始时为空的二叉排序树，画出插入完成 之后的二叉排序树。 （2）按表中元素顺序构造一棵AVL树，并求其在等概率情况下查找成功的平均查找长度。 49 12．给定表（Jan,Feb,Mar,Apr,May,Jun,Jun,Aug,Sep,Oct,Nov,Dec）.设取散列函数 H(x)=|_i/2_|,其中i为健值中第一个字母在英语字母表中的序号，要求： （1）画出相应的开散列表； （2）画出闭散列表（以线性探测法处理）； （3）分别求这两个散列表在等概率情况下查找成功与不成功时的平均查找长度。 13．已知散列函数为H(K)=K mod 12,健值序列为25，37，52，43，84，99，120，15，26， 11，70，82，采用拉链法处理冲突，试构造开散列表，并计算查找成功的平均查找长度。 14．顺序查找时间为O(n),二分查找时间为O(log 2 n),散列查找时间为O(1),为什么有高效 率的查找方法而不放弃低效率的方法？ 五、算法设计 1． 假设线性表中结点是按健值递增的顺序存放的。试写一顺序查找法，将岗哨设在高下标 端。然后分别求出等概率情况下查找成功和不成功时的平均查找长度。 2． 若线性表中各结点的查找概率不等，则可用如下策略提高顺序查找的效率：若找到指定 的结点，则将该结点和其前驱（若存在）结点交换，使得经常被查找的结点尽量位于表 的前端。试对线性表的顺序存储结构和链式存储结构写出实现上述策略的顺序查找算法 （注意，查找时必须从表头开始向后扫描）。 3． 试写出二分查找的递归算法。 4． 试编写算法求出指定结点在给定的二叉排序树中所在的层数。 5． 试编写算法，在给定的二叉排序树上找出任意两个不同结点的最近公共祖先（若在两结 点A、B中，A是B的祖先，则认为A、B的最近公共祖先就是A）。 6． 试写一个判别给定二叉树是否为二叉排序树的算法，设此二叉树以二叉链表作存储结 构。 7． 试写出在二叉排序树上删除指定结点的算法。 8． 在以T为根指针的AVL树上插入健值K的新结点，返回值为新AVL树的根指针。 第十章 排序 一、名词解释 1.排序 2.内部排序 3.外部排序 4.堆 5.堆排序 二、填空 1.若待排序的序列中存在多个记录具有相同的键值，经过排序，这些记录的相对次序仍然保 持不变，则称这种排序方法是________的，否则称为________的。 2.按照排序过程涉及的存储设备的不同，排序可分为________排序和________排序。 3.按排序过程中依据的不同原则对内部排序方法进行分类，主要有：________、________、 ________、________等四类。 4.在排序算法中，分析算法的时间复杂性时，通常以________和________为标准操作。评价 排序的另一个主要标准是执行算法所需要的________。 5.常用的插入排序方法有________插入排序、________插入排序、________插入排序和 ________插入排序。 6.以下为直接插入排序的算法。请分析算法，并在________上填充适当的语句。 void straightsort(list r); {for(i=___________;i<=n;i++) {r[0]=r[i];j=i-1; 50 while(r[0].key r[j+1]=_______; } } 7.直接插入排序是稳定的，它的时间复杂性为________，空间复杂度为________。 8.以下为冒泡排序的算法。请分析算法，并在________上填充适当的语句。 void bulbblesort(int n,list r) /*flag为特征位，定义为布尔型*/ {for(i=1;i<=________;i++) {_______________; for(j=1;j<=_________;j++) if(r[j+1].key if(flag) return; } } 9.对于n个记录的集合进行冒泡排序，其最坏情况下所需的时间复杂度是________。 10.以下对r[h],r[h+1],……r[p]子序列进行一趟忆速排序。请分析算法，并在________上 填充适当的语句。 int quickpass(list r,int h,int p) {i=h;j=p;x=r[i];/*置初值，以第一个记录的键值为标准*/ while(i {while((r[j].key>=)&&(i if(i {________;i++;/* 将r[j].kiy<的记示移至i所指位置*/ while((r[i].key<=)&&(i if(i } } r[i]=________;return(i);/*一趟快速 排序结束，将x移至正确的位置*/ } 11.对快速排序来讲，其最好情况下的时间复杂度是________，其最坏情况下的时间复杂度 是________。 12.以下是直接选择排序的算法。请分析算法，并在横线上填充适当的语句。 void select(list r,int n) {for(i=1;i<=________;i++)/*每次循环，选择出一个最小键值*/ {k=i; for(j=i+1;j<=n;j++)if(r[j].key if(______)swap(r[k],r[i]）;/*函数swap(r[k],r[i]）交换r[k]和r[i]的位置*/ } } 13.直接选择排序是不稳定的，其时间复杂性为________。 14.树形选择排序要增加________个结点以保存前面比较的结果。另外，排序的结果还需要 另外开辟________. 51 15.树形选择排序可用一棵树来表示这一排序过程，树中的n个叶子代表待排序记录的键值， 叶子上面一层是________两两比较的结果，依次类推。________表示最后选择出来的最小关 键字。在选择次最小键值时，只需将叶结点中最小键值改成________，重新进行比较。依次 类推。 16.若树形选择排序的叶子数为n，除第一次需执行________次比较就选择出一个最小的键 值外，以后的每次都只经过________次比较就选择出一个最小的键值。所以树形选择排序总 的时间开销为________。 17.从一个无序序列建立一个堆的方法是：首先将要排序的所有键值分放到一棵________的 各个结点中，然后从i=________的结点k i 开始，逐步把以k n/2 ,k n/2-1 ,k n/2-2 ,……为根的子树排 成堆，直到以k 1 为根的树排成堆，就完成了建堆的过程。 18.堆排序是不稳定，空间复杂度为________。在最坏情况下，其时间复杂性也为________。 19.以下将a h ,…,a m 和a m+1 ,…,a n 两个有序序列（它们相应的关键字值满足K h <=…<=K m ,K m+1 <=… <=K n ）合并成一个有序序列R h ，…,R n （使其关键字值满足K h <=…<=K n ）。请分析算法，并在 ________上填充适当的语句。 void merge(list a,list R,int h,int m,int n) {i=h;k=h;j=m+1; while((i<=m)&&(j<=n)) {if(a[i].key<=a[j].key){R[k]=________;________;} else{R[k]=________;________;} k++; } while(i<=________){R[k]=a[i];i++;k++;} while(j<=________){R[k]=a[j];j++;k++;} } 此算法的执行时间为________. 20．归并排序要求待排序列由若干个___________的子序列组成。 21．二路归并排序的时间复杂度是___________。 22．对于n个记录的集合进行归并排序，所需的附加空间消耗是___________。 23.设表中元素的初始状态是按键值递增的，分别用堆排序、快速排序、冒泡排序和归并排 序方法对其仍按递增顺序进行排序，则___________最省时间，___________最费时间。 24．分别采用堆排序、快速排序、插入排序和归并排序算法对初始状态为递增序列的表按递 增顺序进行排序，最省时间的是___________算法，最费时间的是___________算法。 三、单项选择 1． 以下说法错误的是 （ ） ①直接插入排序的空间复杂度为O(1)。 ②快速排序附加存储开销为O(log 2 n)。 ③堆排序的空间复杂度为O(n)。 ④二路归并排序的空间复杂度为O(n),需要附加两倍的存储开销。 2． 以下不稳定的排序方法是 （ ） ①直接插入排序 ②冒泡排序 ③直接选择排序 ④二路归并排序 3． 以下稳定的排序方法是 （ ） ①快速排序 ②冒泡排序 ③直接选择排序 ④ 堆排序 52 4． 以下时间复杂性不是O(n)的排序方法是 （ ） ①直接插入排序 ②二路归并排序 ③冒泡排序 ④直接选择排序 5． 以下时间复杂性不是O(nlog 2 n)的排序方法是 （ ） ①堆排序 ② 直接插入排序 ③二路归并排序 ④快速排序 6． 在文件局部有序或文件长度较小的情况下，最佳的排序方法是 （ ） ①直接插入排序 ② 冒泡排序 ③ 直接选择排序 ④归并排序 7． 对于大文件的排序要研究在外设上的排序技术，即 （ ） ①快速排序法 ② 内排序法 ③外排序法 ④ 交叉排序法 8．排序的目的是为了以后对已排序的数据元数进行（ ）操作。 ①打印输出 ②分类 ③ 合并 ④查找 9．当初始序列已按健值有序时，用直接插入算法进行排序，需要比较的次数为（ ） 2 ①n-1 ②log 2 n ③ 2log 2 n ④n 10.快速排序在最坏的情况下的时间复杂度是 （ ） 23 ①O(log 2 n) ②O(nlog 2 n) ③ O(n) ④O(n) 11.具有24个记录的序列，采用冒泡排序至少的比较次数是 （ ） ①1 ②23 ③ 24 ④ 529 12．用某种排序方法对序列（25，84，21，47，15，27，68，35，20）进行排序，记录序列 的变化情况如下： 25 84 21 47 15 27 68 35 20 15 20 21 25 47 27 68 35 84 15 20 21 25 35 27 47 68 84 15 20 21 25 27 35 47 68 84 则采取的排序方法是 （ ） ①直接选择排序 ②冒泡排序 ③快速排序 ④二路归并排序 13．在排序过程中，健值比较的次数与初始序列的排列顺序无关的是 （ ） ①直接插入排序和快速排序 ②直接插入排序和归并排序 ③直接选择排序和归并排序 ④快速排序和归并排序 14．（ ）方法是从未排序序列中依次取出元素与已排序序列中的元素作比较，将其放入已 排序序列的正确位置上。 ①归并排序 ② 插入排序 ③快速排序 ④选择排序 15（ ）方法是从未排序序列中挑选元素，并将其依次放入已排序序列的一端。 ①归并排序 ②插入排序 ③ 快速排序 ④选择排序 16．（ ）方法是对序列中的元素通过适当的位置交换将有关元素一次性地放置在其最终 位置上。 ①归并排序 ②插入排序 ③快速排序 ④选择排序 17．将上万个一组无序并且互不相等的正整数序列，存放于顺序存储结构中，采用（ ） 方法能够最快地找出其中最大的正整数。 ①快速排序 ②插入排序 ③ 选择排序 ④ 归并排序 18一般情况下，以下四种排序方法中，平均查找长度最小的是 （ ） ①归并排序 ②快速排序 ③选择排序 ④插入排序 19．以下四种排序方法中，要求附加的内存容量最大的是 （ ） ①插入排序 ②选择排序 ③快速排序 ④归并排序 2 53 20已知一个链表中有3000个结点，每个结点存放一个整数，（ ）可用于解决这3000 个整数的排序问题且不需要对算法作大的变动。 ①直接插入排序法 ②简单选择排序方法 ③快速排序方法 ④堆排序方法 21．若用冒泡排序法对序列（18，14，6，27，8，12，16，52，10，26，47，29，41，24） 从小到大进行排序，共要进行（ ）次比较。 ①33 ②45 ③70 ④91 22．在任何情况下，快速排序方法的时间性能总是最优的。这种说法 ①正确 ②错误 23．对一个由n个整数组成的序列，借助排序过程找出其中的最大值，希望比较次数和移动 次数最少，应选用（ ）方法。 ①归并排序 ②直接插入排序 ③直接选择排序 ④快速排序。 四、简答及应用 1．对于给定的一组键值：83，40，63，13，84，35，96，57，39，79，61，15，分别画出 应用直接插入排序、直接选择排序、快速排序、堆排序、归并排序对上述序列进行排序中各 趟的结果。 2．举例说明本章介绍的各排序方法中那些是不稳定的？ 3．相对于树形选择排序，直接选择排序和堆排序有何优点？ 4．试比较直接插入排序、直接选择排序、快速排序、堆排序、归并排序的时、空性能。 5．判断下列两序列是否为堆？如不是，按照建堆的思想把它调整为堆，并用图表示建堆的 过程。 （1）（3，10，12，22，36，18，28，40）； （2）（5，8，11，15，23，20，32，7）。 6．对于下列一组关键字46，58，15，45，90，18，10，62，试写出快速排序每一趟的排序 结果，并标出每一趟中各元素的移动方向。 7．已知数据序列为（12，5，9，20，6，31，24），对该数据序列进行排序，试写出插入排 序和冒泡排序每趟的结果。 五、算法设计 1． 设计一个用链表表示的直接选择排序算法。 2． 写出非递归调用的快速排序算法。 3． 插入排序中找插入位置的操作可以通过二分法查找的方法来实现。试据此写一个改进后 的插入排序方法。 4． 一个线性表中的元素为正整数或负整数。设计一个算法，将正整数和负整数分开，使线 性表前一半为负整数，后一半为正整数。不要求对这些元素排序，但要求尽量减少交换 次数。 5． 已知（k 1 ,k 2 ……，k n ）是堆，试写一个算法将（k 1 ,k 2 ,……，k n ,k n+1 ）调整为堆。按此思 想写一个从空堆开始一个一个填入元素的建堆算法（题示：增加一个k n+1 后应从叶子向 根的方向调整）。 6． 设计一个用链表表示的直接插入排序算法。 第一章 参考答案 54 一、名词解释 （略） 二、填空题 1、数据表示 数据处理 2、机内表示 3、逻辑结构 逻辑结构上的基本运算 存储结构和运算 评价和选择 4、逻辑性 基本运算 5、存储 6、机外表示 逻辑结构 存储结构 7、处理要求 基本运算和运算 算法 8、数据 数据元素 数据项 9、元素 结点 顶点 记录 10、字段 域 11、数据元素 数据项 12、集合 线性结构 树形结构 图状结构 13、加工 引用 14、定义在S上的运算 S上运算 15、归纳 16、机内表示 17、存储结点 数据元素之间关联方式的表示 附加设施 18、顺序存储方式 链式存储方式 索引存储方式 散列存储方式 19、给定逻辑结构S的存储实现 存储映象 20、程序 算法设计 21、运行终止的程序可执行部分 伪语言算法 非形式算法 22、时空性能 算法分析 23、正确性能 易读性 健壮性 高效性 24、时间性能（或时间效率） 空间性能（或空间效率） 计算量 存储量 25、标准操作 标准操作 计算量 26、最坏情况时间复杂性 最坏情况时间复杂度 平均时间复杂性 平均时间复杂度 27、时间复杂性 时间复杂度 28、算法输入规模 29、作为该算法输入的数据所含数据元素的数目，或与此数目有关的其他参数 2 n 30、1 log 2 n n n 2实际不可计算 高效 31、设计 实现 32、数据结构的定义 数据结构的实现 数据结构的评价 选择 33、数据的逻辑结构 34、线性结构 非线性结构 2 34、O（n） 36、o(log 2 n)。 三、单项选择题 1.②2.①3.②4.③5.①6.②7.④8.③9.③ 10.③ 11.② 12.② 13.④14.④ 15.② 四、简答及应用 1． 凡能被计算机存储、加工的对象通称为数据。 数据元素是数据的基本单位，在程序中作为一个整体而加以考虑和处理。换句话说， 数据元素被当作运算的基本单位，并且通常具有完整确定的实际意义。根据需要，数据 元素又被称为元素、结点、顶点或记录。 在很多情况下，数据元素又是由数据项组成的，但数据项通常不肯有完整确定的实 际意义，或不被当作一个整体对待。在有些场合下，数据项又称为字段或域。它是数据 的不可分割的最小标识单位。 从某种意义上说，数据，数据元素和数据实际反映了数据组织的三个层次，数据 可由若干个数据元素构成，而数据元素又可由若干个数据项构成。 55 ２、所谓逻辑关系是指数据元素之间的关联方式或称“邻接关系”。数据元素之间 逻辑关系的整体称为逻辑结构。数据的逻辑结构就是数据的组织形式。关于逻辑结 构的以下几点需特别注意： （１）、逻辑结构与数据元素本身的形成、内容无关。 （２）、逻辑结构与数据元素的相对位置无关。 （３）、逻辑结构与所含结点个数无关。 由此可见，一些表面上很不相同的数据可以有相同的逻辑结构，因此，逻辑结 构是数据组织的某种“本质性”的东西，是数据内部组织的主要方面。 ３、逻辑结构反映数据元素之间的逻辑关系，而存储结构是数据结构在计算机中的 表示，它包括数据元素的表示及其关系的表示。 ４、一般地，运算是指在任何逻辑结构上施加的操作，即对逻辑结构的加工。一个 运算的实现是指一个完成该运算功能的程序。 相同点：运算与运算的实现都能完成对数据的“处理”或某种特定的操作。 不同点：运算只描述处理功能，不包括处理步骤和方法，而运算实现的核心是 处理步骤。 ５、类Ｃ语言基本上是标准Ｃ语言的简化。类Ｃ语言与标准Ｃ语言的主要区别如下： （１） 局部量的说明可以省略（但形参表中及函数类型的说明需保留），重要的 变量需在注解中用文字说明基类型和作用。 （２） 分情形语句可以采用下述形式： switch { case 条件１：语句序列１；break; case 条件2：语句序列2；break; …… case 条件n：语句序列n；break; default: 语句序列n+1; } 其中“default: 语句序列n+1;”可以省略。 （３） 不含goto语句，增加了一个出错处理语句error（字符串），其功能是 终止它所在算法的执行并回送表示出错信息的字符串。 （４） 输入输出语句有： 输入语句 scanf([格式串]，变量度，……，变量n); 输出语句 printf([格式串]，变量度，……，变量n); (５) 类Ｃ语言的形参书写比标准Ｃ语言简单，如int abc (int a,int b,int c)可以简写为 int abc(int a,b,c)。 五．算法设计 １．（１）int locate(dataytpe ],dateytpe k) { i=n; while ((I<=n)&&(A[i]!=k)) I++; if (I<=n) return(i); else return(o); } 当查找不成功时，总是比较n+1次，所以，最坏时间复杂性为n+1。其量 56 T（n）=O(n). （２）Void CZ_max(datatype A[n],x,y) { x=A[1]; y=A[1]; for(I=2;I<=n;I++) if(x else if(y } 若经条件判断语句为标准操作，则最坏情况时间复杂性为n-1。其量级为 T(n)=O(n). 第二章 参考答案 一、名词解释 （略） 二、填空题 1、结点 起始 终端 序号 位置 前趋 后趋 2、（） ф 3、前趋 前趋 后趋 后趋 4、线性 5、线性 长度 表长 6、空表 7、初始化INITLATE（L） 求表长LENGTH（L） 读表长GET（L，i） （L，X） 插入INSERT（L，X，i） 删除DELETE（L，i） 8、逻辑结构中相邻的结点在存储结构中仍相邻 9、b+（i-1）x k 10、L．data[j]=L．data[j-1] 11、n O(n) n/2 O(n) 12、[j-2]=[j-1] 13、n-1 o(n) (n-1)/2 O(n) 14、i=1 i≦ 15、O(n) O(1) 16、 [i-1] 17、单链表 循环链表 双链表 18、指针 19，单链表 20、头结点 表结点 21、首结点 尾结点 任何信息、特殊标志 表长 22、头结点 头结点 23、t=malloc(size) t->next=NULL 24、p=haed p=p->next 25、(p->next!=NULL)&&(j 26、(p->next!=NULL)&&(p->data!=x) 27、(p!=NULL)&&(p->next!=NULL) p->next 28、mailloc(size) p->next 57 定位LOCATE 29、insert_lklist(head,x,I) I++ n(n-1)/2 O(n) 30、p=q p->next=NULL O(n) 31、单向循环链表（简称循环链表） 双向循环链表（简称双链表） 32、NULL 头结点 33、双链表 34、字符数组 赋值 35、空 ф 非空 字符 36、长度 相同 子 主 37、非紧缩 紧缩 38、结点大小 不属于字符集的特殊符号 三、单项选择题 1、②2、①3、①4、②5、①6、②7、③8、③9、④ 10、②11、④12、③13、⑤14、④15、③16、①17、②18、③ 19、④20、④21、④22、223、②24、③25、④26、②27、③ 28、④29、①30、④31、②32、②33、④34、④35、③36、③ 37、②38、③39、②40、①41、④ 四、简答及应用 1、线性表的数据元素的类型为datatype，则在语言上可用下述类型定义来描述顺序表： const maxsize=顺序表的容量； typedef struct { datatype data[maxsize] int last; }sqlist; sqlist L; 数据域data是一个一维数组，线性表的第1，2……，n个元素分别存放在此数组的 第0，1，……，last-1个分量中，数据域last表示线性表当前的长度，而last-1是线性 表的终端结点在顺序表中的位置。常数maxsize称为顺序表的容量，从last到maxsize-1 为顺序表当前的空闲区（或称备用区）。 Sqlist类型完整地描述了顺序表的组织。L被说明为sqlist类型的变量，即为一顺 序表，其表长应写为，而它的终端结点则必须写为 [-1]。 2、假设数据元素的类型为datatype。单链表的类型定义如下： typedef struct node *pointer struct node {datatype data; pointer next; }; typedef pointer lklist; 其中，①ponter是指向struct node类型变量的指针类型;②struct node是结构体 类型规定一个结点是由两个域data和next组成的记录，其中data的结点的数据域,next 是结点的链域；③lklist与pointer相同类型，用来说明头指针变量的类型，因而lklist 也就被用来作为单链表的类型。 3、typedef struct dnode *dpointer; struct dnode 2 58 {datatype data; dpointer prior,next; } typedaf dpinter dlklist; 链域prior和next分别指向本结点数据域data所含数据元素的直接前趋和直接后继所 在的结点。所有结点通过前趋和后继指针链接在一起，再加上起标识作用的头指针，就得到 双向循环链表。 4、顺序串的类型定义与顺序表类似，可描述如下： const maxlen=串的最大长度 typedef struct {char ch[maxlen] int curlen; }string 5、链串的类型定义为： const nodesize=用户定义的结点大小; typedef struct node *pointer; struct node {char ch[nodesize] poinernext; } typedef pointer strlist; 当结点大小为1时，可将ch域简单地定义为：char ch 6、head称为头指针变量，该变量的值是指向链表的第一个结点的指针，称为头指针。头指 针变量是用于存放头指针的变量。 为了便于实现各种运算，通常在单链表的第一个结点之前增设一个类型相同的结点，称 为头结点。其它结点称为表结点。表结点中和第一个和最后一个分别称为首结点和尾结点。 头指针变量的作用：对单链表中任一结点的访问，必须首先根据头指针变量中存放的头 指针找到第一个结点，再依次按各结点链域存放的指针顺序往下找，直到找到或找不到。头 指针变量具有标识单链表的作用，故常用头指针变量为命名单链表。 头结点的作用：头结点的数据域可以不存储任何信息，也可以存放一个特殊标志或表长。 其作用是为了对链表进行操作时，将对第一个结点煌处理和对其它结点的处理统一起来。 7、循环单链表、循环双链表。 8、空串和空格串：含0个字符的串称为空串，其长度为0。空格串是含有一个或多处空格 字符组成的串，其长度不为0。 串变量和串常量：串常量在程序的执行过程中只能引用不能改变而串变量的值在程序执 行过程中是可以改变和重新赋值的。 主串和子串：一个串中任意个连续字符组成的子序列称为该串的子串，该串称为它的所 以子串的主串。 串变量的名字与串变量的值：串变量的名字表示串的标识符；串变量的值表示串变量的 字符序列。 9、(a)A+B “ mule” (b)B+A “mule ” 59 (c)D+C+B “myoldmule” (d)SUBSTR(B,3,2) “le” (e)SUBSTR(C,1,0) “” (f)LENGTH(A) 2 (g)LENGTH(D) 2 (h)INDEX(B,D) 0 (i)INDEX(C,”d”) 3 (j)INSERT(D,2,C) “myold” (k)INSERT(B,1,A) “m ule” (l)DELETE(B,2,2) “me” (m)DELETE(B,2,0) “mule” 10、REPLACE(S,SUBSTR(T,7,1),SUBSTR(T,3,1));CONCAT(S,”y”); 五、算法设计 1、 分析：(1)当A、B表都不为空时，比较A，B表中各元素对应位置的内容的大小， 进而判断A，B的大小。 (2)当A，B表都不为空时，且A，B表中各各元素对应位置的内容相同时，比 较A，B的长度，进而判断A，B的大小或是否相等。 const maxsize=顺序表的容量; typedef struct {int data[maxsize] int last; }sqlist; int CMP_sqlist(sqlist A ,sqlist B) { for (i=0;(i<)&&(I<));i++} { if([i]<[i])return(-1); if([i]>[i])return(1); } if(= =) return(0); else if(>) return(1); else return(-1); } 2、(1)定位LOCATE(L，X) 在带头结点类单链表上实现的算法为： int locate_lklist(lklist head,datatype x) /*求表head中第一个值等于x的的序号，不存在这种结点时结果为0*/ {p=head->next;j=1; /*置初值*/ while((p!=NULL)&&(p->data!=x)) {p=p->next;j++}/*未达表结点又未找到值等于X的结点时经，继续扫描*/ if (p->data = =x) return(j); else return(0); 60 } 在无头结点的单链表上实现的算法为： int Wlocate(lklist head,datatype X) /*求表head中第一个值等于x的结点的序号。不存在这种结点时结果为0*/ {p=head; j=1; /*置初值*/ while((p!=NULL)&&(p->data!=x)) {p=p->next;j++}/*未达表结点又未找到值等于X的结点时经，继续扫描*/ if( p->data = =X) return(j); else return(0); } (2)按序号查找find(L,i) 在带头结点的单链表上实现的算法为： pointer find_lklist(lklist head , int i); { j=1; p=head->next; while((j<1)&&(p!=NULL)){p=p->next; j++} if(i= = j) return(p); else return(NULL); } 在无头结点的单链表上实现的算法为： pointer find_lklist(lklist head , int i); { j=1; p=head; while((j<1)&&(p!=NULL)){p=p->next; j++} if(i= = j) return(p); else return(NULL); } (3)、插入INSERT(L，X，i) 在带头结点单链表上实现的算法为： void insert_lklist(lklist head,datatype x,int I) /*在表haed的第i个位置上插入一人以x为值的新结点*/ {p=find_lklist(head,i-1); /*先找第i-1个结点*/ if(p= =NULL)reeor(“不存在第i个位置”)/*若第i-1个结点不存在，退出*/ else{s=malloc(size);s->data=x /*否则生成新结点*/ s->next=p->next /*结点*p在链域值传给结点*s的链域*/ p->next=s; /*修改*p的链域*/ } } 在无头结点的单链表上实现的算法为： void Winsert(lklist head,dataytpe X,int i) /*在表haed的第i个位置上插入一人以x为值的新结点*/ {if(i<=0) error(“i<=0”); else{ s=malloc(size);s->data=X; /*否则生成新结点*/ if(i= =1){s->next=head;head=s;} 61 else{ p=wfind_lklist(lklist head,i-1); if(p= =NULL) error(“i>n+1”); else{s->next=p->next;p->next=s;} } } (4)删除DELDTE(L,i) 在带头结点的单链表上实现的算法为： void delete_lklist(lklist head,int i) /*删除表head的第i个结点*/ {p=find_lklist(head,i-1) /*先找待删结点的直接前驱*/ if((p!==NULL)&&(p->next!=NULL))/*若直接前趋存在且待结点存在*/ (q=p->next; /*q指向待删结点*/ p->next=q->next/*摘除待结点*/; free(q);/*释放已摘除结点q*/ } else error(“不存在第i个结点”)/*否则给出相关信息*/ } 在无头结点的单链表上实现的算法为： void Wdelete(lklist head,int i) /* 删除表head的第i个结点，若该链表仅有一个结点时，赋该结点指针NULL*/ {if(i<=0) error(“I＜＝0” else{if(i= =0){q=head;head=head->next;free(q);} else{p=wfind_lklist(head,i-1);/*找链表head中第i-1结点指针*/ if(p!=NULL)&&(p->next!=NULL) ｛q=p->next; p->next=q->next; free(q);｝ else error(“不存在第I个结点”)； ｝ ｝ ｝ 3、 分析：从第一个结点开始访问，只要是非空计数一次。 Int wlength_lklist(lklist head) /*求表head的长度*/ {p=head;j=0; while(p!=NULL){p=p->next;j++;} return(j); /*回传表长*/ ｝ 4、 设A,B,C均为无头结点单链表 分析：（1）当有序表A，B均非空时，找出两表中元素最小的一个元素，然后将此结点插入 到C表中，重复上述步骤。 （2）当A，B两表有一个为空表时，将另一表中元素顺序地插入到C表中。 （3）由于C按递减排序，因此在C表中插入元素时，应始终插入到C表表头。 Lklist Wlink_lklist(lklist A,lklist B) { while((A!=NULL)&&(B!=NULL)) if(A->data 62 else p->next=C;C=p; } if(A= =NULL) A=B; while(A!=NULL) {p=A;A=A->next; p->next=C;C=p;} return(C); } 5、 分析：（1）当有序表A、B均非空时，依次分别从A、B表头部取下结点，插入C表中。 （2）当A、B两表有一个为空表时，将非空表插入到C表尾部。 设A，B，C均为带头结点的单链表 lklist HB_lklist(lklist A,lklist B) { C=A; A=A->next;B=B->next; //去除头结点 While((A!=NULL)&&(B!=NULL)) {p->next=A;p=p->next;A=A->next; p->next=B;p=p->next;B=B->next; } if((B= =NULL)&&(A!=NULL)) p->next=A; else if((A= =NULL)&&(B!=NULL)) p->next=B; Return(c); } 6、 分析：从有序表的尾部开始依次取元素与插入元素比较，若大于插入元素，此元素后移 一位，再取它前面一个元素重复上述步骤；则将待插入元素插入。 Void CR(datatype A[],datatype X,int elenum) { i=elenum-1; while((i>=0)&&X A[i+1]=X; Elenum=elenum+1; } 算法的时间复杂度为O（n）。 7、 分析首先从表头开始查找待插入位置的直接前趋，找到后插入待插结点。 /*设L表带头结点*/ Void CR_lklist(lklist L,datatype x) {q=L;p=q->next; while((p!=NULL)&&(p->data s=malloc(size);s->data=s; } 8、 (1)顺序表 63 分析：将顺序表的第一个元素与最后一个元素互换，第二个元素与倒数第二个元素互换。 Void NZ_sqlist(sqlist A) {for{i=0;i<((-1)/2);i++} {x=[i]; [i]=[-i-1]; [-i-1]=x; } } (2)单链表 分析：将原单链表的元素依次取出，再插入另一个单链表的头部。 设该单链表为无头结点，s为指向表的第一个结点的指针。 Void NZ_lklist(lklist s) {p=NULL; /*p指向当前结点的前趋结点*/ while(s!=NULL) { q=s;s=s->next; /*将原单链表的元素依次取出到q*/ q->next=p;p=q; /*再插入另一个单链表p的头部*/ } s=p; /*s指向新单链表的第一个结点*/ } 9、 分析：A与B的交是指A与B的相同部分元素，即那些在A中出现又在B中出现的元素。 由于A、B是有序表，故从表头开始依次比较当前指针所指元素的值是否相同，若相同， 在C表中插入该元素，然后将两个表的指针后移，否则指向较小元素的指针后移。重复 上述步骤，直到A，B表中有一个表到表尾。 (1)顺序表 sqlist HDZ_sqlist(sqlist A,sqlist B) { t=0;j=0;k=0; while((t<=-1)&&(j<=-1)) switch{ case [i]<[j];i++;break; case [i]>[j];j++;break; case [i]= =[j];[k]=[i];k++;i++;j++;break; } =k; Return(c ); } (2)单链表（设带头结点） lklist HDZ_lklist(lklist A,lklist B) { C=initiate_lklist(); r=C;p=A->next;q=B->next:; While ((p!=null)&&(q!=null)) Switch { case p->data case p->data 64 case p->data==q->data; s=malloc(size);s->data=p->data; s->next=r->next; r->next=s; r=s; p=p->next;q=q->next; } return(c); } 10.分析：①在有序表B、C中找出相同元素X； ②若X在表A中出现则删除，否则转①； ③重复①②直到B、C表有一个表查找完毕。 （1） 顺序表 void ASBC_sqlist(sqlist A, sqlist B, sqlist C) {I=0;j=0;k=0; while ((j<)&&(k<)) switch {case [j]<[k]:j++;break; case [j]<[k]:k++;break; case [j]==[k]:/*B、C中找到相同元素*/ {while((I<)&&( [I]<[j]))I++;/*在A中查找B、C表共有元素*/ if (I>= ) return; if ([I]==[j])/*在A中存在B、C表共有元素，删除*/ {for(t=I+1;t< ;t++) [t-1]= [t] --;} j++;k++; } } } （2） 单链表（设含头结点） void ASBC_lklist(lklist A,lklist B,lklist C) {pa= A ->next;q= A; pb= B ->next;pc= C ->next; while ((pb!=null)&&(pc!=null)) switch { case pb->data case pb->data case pb->data= =pc->data:/* B、C中找到相同元素*/ if(pa= =null)return; if (pa->data= =pb->data)/*在 A中存在 B、C 表共有元素，删除*/ {q->next=pa->next; free(pa);pa=q->next;} pb=pb->next;pc=pc->next; 65 } } } 11．分析设置两个指针，分别指向*S及其后继，然后按循环链表特性，顺序往下查找*s的 直接前趋，找到后删除； void DELETE_Xlklist(lklist S) {p=s; q=p->next; while (q->nest!=s) { p=q; q=q->next;} p->next=s; free(q); } 12．分析：在链表L中依次取元素，若取出的元素是字母，把它插入到字母B中，然后在L 中删除该元素；若取出的元素是数字，把它插入到数字链D中，然后在L中删除该元素。继 续取下一个元素，直到链表的尾部。最后B、D、L中分别存放的是字母字符、数字字符和其 它字符。 设原表有头结点、头指针L，新建数字字符链D，字母字符链B，其它字符链R。 void DISM_lklist(lklist L,lklist D,lklist B,lklist R) { D =malloc(size of(int)); D ->next= D; /*建D循环链表头结点*/ B =malloc(sizeof(char)); B ->next= B; /*建B循环链表头结点*/ p= L;q=p->next; while(q!=null) {if((q->data<=’9’)&&(q->data>=’0’)) {p->next=q->next; /*在表L 中摘除q结点*/ q->next= D ->next; D ->next=q; /*将q结点插入D中*/ q=p->next; /*移动q指针*/ } else if (q->data<=’z’)&&(q->data>=’a’)||(q->data<=’z’)&&(q->data>=’a’)) {p->next=q->next; /*在表L中删除q 结点*/ q->next= B ->next; B ->next=q; /*将q结点插入B中*/ q=p->next; /*移动q指针*/ }else {p=q;q=p->next;} /*移动q指针*/ } p->next=L;R=L; /*使R为循环表*/ } 13．分析：使用一维数组，数组下标表示元素的序号，数组值为1表示元素存在，数组 值为0表示此元素不存在。若累加数组的下标大于N，再从1开始继续累加数组值，直到 所有元素都输出。 Void JSP( int n, k, a[n]) {for(I=0;I j=0; for(I=0;I {s=0; 66 while (s s=s+a[j-1]; printf(“%d”,j);a[j-1]=0; } } 14．（1）始化 dlklist initiate_dlklist() {t=malloc(size); t->next =null; t->prior=null; return(t); } (2)定位（设含头结点） int locate_dlklist (dlklist head, datatype x) /*求表head中第一个值等于x 的结点的序号。不存在这种结点时结果为0 */ {p=head->next;j=1; /*置初值*/ while((p!=null)&&(p->data!=x)) {p=p->next;j++;} /*未达尾结点又未找到值等于x的结点时继续扫描*/ if (p->data = = x) return (j); else return (0); } （3） 插入（设含头结点） void insert_dlklist (dlklist head, datatype x, int I) /*在表head的第I 个位置上插入一个以x为值的新结点*/ {p=head->next; j=1; /*先找第I-1个结点*/ while ((p!=null) &&(j if ((I-1)!=j) error(“不存在第I个位置”)/*若第I-1个结点不存在，退出*/ else {s=malloc(size);s->data=x;/*否则生成新结点*/ s->prior=p; s->next=p->next; p->next->prior=s; p->next=s; } } （4） 删除（设含头结点） void deldtd_dlklist(dlklist head, int I) /*删除表head的第i个结点*/ {p=head->next;j=1; /*先找第i个结点*/ while((p!=null)&&(j if(I!=j) error(“不存在第I个位置”)/*若第i个结点不存在，退出*/ if(p!=null) /*若直接前趋存在且待删结点存在*/ {p->prior->next=p->next; p->next->prior=p->prior; 67 free(p);/*释放已摘除结点p*/ } else error(“不在存在第I 结点”) /*否则给出相关信息*/ } 15．分析：首先在链表中查找元素值为X的结点，若找到则让freq域的值增1；然后 依次和它的前趋的freq域值比较，若比前freq域值大，和前趋结点位置交换，直到比 前趋结点的freq域值小为止。 Typedef struct dfnode *dfpointer; Struct dfnode {datatype data; int freq; dfpointer prior,next; } typedef dfpointer dflklist; 设该双链表含头结点。 Int LOCATE_dflklist(dflklist L,datatype X) {/*定位值等于X的结点*/ p=L->next; I=1; while ((p!=null)&&(p->data!=X)) {o=p->next; I++;} if ((p->data!=X||(p= = null)) error(“不存在值为X的结点 ”); else { p->freq++; /*令元素值为X的结点中freq域的值增1*/ q=p->prior; while((q!= L)&&(q->freq {I=I-1; p->prior->next=p->next; /*摘除p*/ p->next->prior=p->prior; q->prior- p->prior=q->prior; p->next=q; q->prior=p; q=p->prior; /*q重新指向p的前趋*/ } return(i); } 16．分析：将X串的结点依次与Y串中的结点值比较，若找到第一个不在Y中出现的结点， 则查找成功，返回该值。 设单链表无头结点 char CZC_lklist (lklist X,lklist Y) {p=x; while (p!=null) {q=Y; 68 while (q!=null)&&(q->data!=p->data) q=q->next; if (q!=null) return(p->data); else p=p->next; } return(‘＄’); /*若X中的字符都在Y中出现，则返回’＄’*/ } maxlen=串的最大长度; typedef struct {char ch [maxlen]; int curlen; } string; int EQUAL_string(string s,string t ) { if (!=) return(0); for (t=0; t<; t++) if ([t]!=[t] ) return(0); return(1); } 18.设单链表无头结点 const nodesize =用户定义的结点大小； typedef struct node *pointer; struct node {char ch; pointer next; } typedef pointer strlist; int EQULA_strlist(strlist s ,strlist t ) { while ((s!= null )&&(t!=null)&&(s->ch==t->ch)) {s=s->next;t=t->next;} return((t= = null)&&(s= =null)); } 19．分析：首先判断串T是否为串S的子串，若串T是串S的子串对S中该子串逆置。 Int NZ_strlist (strlist s,strlist t) {p=s->next;t=t->next;q=s; while(p!=null) {pp =p ; tt =t; /*判断串T是否为串S的子串*/ while ((tt!=null)&&(pp!=null)&&(pp->ch= =tt->ch)) {pp=pp->next;tt=tt->next;} if (tt==null) /*串T是串S的子串对S中的该子串的位置*/ {qq=q->next; /* q是子串的第一个结点前趋pp是子串最后一个结点后继*/ while(qq!=pp) {g=qq; qq= qq->next; 69 q->next =pp; pp=g; } q->next=pp; /*将该子串的前趋与逆置后的子串的相连*/ return(1);/*找到并逆置返1 */ }else {q=p;p=p->next;} } return(0);/*找不到匹配的串返0*/ } 20．Int index(char *s, char *t) {l=LENGTH(s);k=LENGTH(t); for (j=1;j<=l;j++) {if (( l-j+1)>=k) {ASSIGN(m,SUBSTR(s,j,k)); if (EQUAL(m,t )) return(j); }else return(0); } } 第三章参考答案 一、名词解释（略） 二、填空题 1、 先进后出、后进先出，后进先出，进栈，入栈，退栈，出栈 2、 初始化InitStack(S)、进栈Push(S,X), 退栈Pop(S)，读栈顶Top(S),判栈空Empty(S) 3、 下溢 4、 上溢 5、 顺序、链接 6、 栈空、下溢、栈满、上溢 7、 sq->top=0 8、 sq->top++,sq->data[sq->top] 9、 sq->data[sq->top],sq->top— 10、 sq->top= =0 11、 sq->top= =0,sq->data[sq->top] 12、 ls=NULL 13、 p->data=x,ls=p 14、 p->data,free(p) 15、 *x=ls->data 16、 更小的“尺度”、递归 17、 队、队尾、队头 70 18、 队列初始化InitQueue(Q)、入队列EnQueue(Q,X)、出队OutQueue(Q,X)、判队列 空EmptyQueue(Q)、读队头ead(Q,x) 19、 假溢出 20、 sq->front=0 21、 sq->front,sq->rear=(sq->rear+1)%maxsize,sq->data[sq->rear]=x 22、 sq->rear,sq->fornt=(sq->rear+1)%maxsize,*x= sq->data[sq->rear] 23、 = 24、 ,(+1)%maxsize 25、 队满、队空 26、 lq->front=p,NULL 27、 p->data,p,lq->rear=p 28、 *x,s->next 29、 = = 30、 p=->next,*x 31、 n-1,读、写 32、 顺序、列序、行序、行、列 33、 特殊、稀疏 34、 n(n+1)/2 35、 i(i-1)/2+j 当i≧j k= j(j-1)/2+i 当i 36、n-t+1,(i-1)(2n-i+2)/2,j-i+1 (i-1)(2n-i+2)/2+j-i+1 当i<=j k= n(n+1)/2+1 当i>j n(n+1)/2+1 37、 (i-1)/2+j 当i≧j k= n(n+1)/2+1 当i 38、col<=,[p].j,q++ 39、col<=,cpot[col-1]+num[col-1],cpot[col]++ 40、先进后出（后进先出） 41、先进先出（后进后出） 42、ls= =NULL,*x=p->info 43、2230,2374 44、n-1 45、栈 46、EA+222,EA+117 47、lq->front->next= =lq->rear 48、540,108,M[3][10] 71 三、单项选择题 1、④2、①3、④4、①5、③6、②7、①8、③9、④10②、 11、②12、③13、①②14、②15、④16、①17、②18、③19、④20、① 21、②22、①23、③24、①25、②26、③27、②28、②29、②30、③ 31、②32、②33、③34、②35、④ 四、简答及应用 1、顺序栈类型定义如下： #define sqstack_maxsize 顺序栈的容量 typedef struct sqstack {DataType data[sqstack_maxsize]; int top }SqStackTp 它有两个域：data和top。Data为一个一维数组，用于存储栈中元素，DataType为栈元素 的数据类型。Top为int型，它的实际取值范围为0~sqstack_maxsize－1。 2、链栈的类型定义如下： typedef stuct node { DataType data; struct node *next; }LstackTp; 单链表的第一个结点就是链栈栈顶结点，链栈由栈顶指针惟一确定。栈中的其它结点通过它 们的next域链接起来不。栈底结点的next域为NULL。 3、顺序队列的类型定义如下： #define maxsize 顺序栈的容量 typedef struct sqqueue {DataType data[maxsize]; int fornt,rear }SqQueueTp SqQueueTp sq; 该类型变量有三个域：data,front,rear。其中data存储队中元素的一维数组。队头指针 front和队尾指针rear定义为整型变量，实际取值范围为0~maxsize－1。 循环队列的类型定义如下： #define maxsize 循环队的容量 typedef struct cycqueue{ DataType data[maxsize] Int front,rear }CycqueueTp; CycqueueTp sq; 4、typedef struct linked_queue { DataType data; struct linked_queue *next; }LqueueTp; typedef struct queueptr 72 { LqueueTp *front, *rear; }QueptrTp; QueptrTp lq; 5、#define maxnum 非零元素的容量 typedef struct node { int i,j ; /*非零元素所在的行号、列号*/ DataType v; /*非零元素的值*/ }NODE; typedef struct spmatrix { int mu,nu,tu; /*行数、列数、非零元素的个数*/ NODE data[maxnum+1];/*这里假定三元组的下标的起始值为1*/ }SpMatrixTp 6、int length(CycqueueTp sq) {len=(+maxsize)%maxsize; return(len); } 7、1234、4321、2143、3421、3241、1324、1432、1342、1243、3214、2134、2314、2341、 2431 8、 i(2n-i+1)/2 当i<=j f 1 (i)= 0 当i>j j 当i<=j f 2 (j)= 0 当i>j -n 当i<=j c= n(n+1)/2+1 当i>j 9、(1)k=2i+j-2; (i,j=1,2,…..n) (2)i=ceil((k+1)/3) j=floor(k/3)+k mod 3 10、运行结果：ABCDEFGHIJKLM MLKJIHGFEDCBA 11、借助栈将一个带头结点的单链表倒置。 12- Top- Top- > 1 r’’’ ’ 73 Top- > Top- > Top- > 5 r 4 r ’ 5 r Top- > 3 r’ ’ 4 r’ 5 r > 2 r’’ ’ 3 r’’ 4 r’ 5 r 2 r’’’ 3 r’’ 4 r’ 5 r 调用f(5)前 调用f(5)前 调用f(4)前 调用f(3)前 调用f(2)前 调用 f(1)前 Top-> 2 r’’’ 3 r’’ Top-> 4 r’ 5 r 3 r’’ 4 r’ Top-> 5 r 4 r’ 5 r Top-> 5 r Top-> 返回f(1)后 返回f(2)后 返回f(3)后 返回f(4)后 返回f(5) 后 五、算法设计 1．本程序中，将客车类定义一个队KE，货车类定义一个队HE，过江渡船定义成一个栈DC。 栈采用顺序存储结构，队采用链式存储结构。 #define sqstack_maxsize 10 typedef struct sqstack {DataType data[sqstack_maxsize]; int top; }SqStackTp; typedef struct linked_queue {DataType data; struct linked_queue *next; }LqueueTp; typedef struct queueptr {LqueueTp *front,*rear; }QueptrTp; int InitStack(SqStackTp *sq) {sq->top=0; return(1);} void InitQueue (QueptrTp *lp) {LqueueTp *p; p=(LqueueTp *)malloc(sizeof(LqueueTp)); lq->front=p; lq->rear=p; ( lq->front)->next=NULL; 74
发布者：admin，转转请注明出处：http://www.yc00.com/web/1714363762a2432613.html
评论列表（0条）