数据结构 第1章 绪论

第一章绪论1.数据：人们利用文字符号、数字符号及其他规定的符号对现实世界的事物及其活动的描述。

凡是能被计算机输入、存储、处理和输出的一切信息都叫数据。

2.数据元素：数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。

数据元素的组成：一个数据元素通常由一个或若干数据项组成。

数据项：指具有独立含义的最小标识单位。

3.数据对象：性质相同的数据元素的集合，是数据的一个子集。

4.数据结构：研究的是数据的逻辑结构和物理结构，以及它们之间的相互关系和所定义的算法在计算机上运行的学科。

5.算法：是对待定问题求解步骤的一种描述，是指令的有限序列。

算法应满足以下性质：1)输入性：具有零个或若干个输入量；2)输出性：至少产生一个输出；3)有穷性：每条指令的执行次数是有限的；4)确定性：每条指令的含义明确，无二义性；5)可行性：每条指令都应在有限的时间内完成。

6.评价算法优劣的主要指标：1)执行算法后，计算机运行所消耗的时间，即所需的机器时间；2)执行算法时，计算机所占存储量的大小，即所需的存储空间；3)所设计的算法是否易读、易懂，是否容易转换成其他可运行的程序语言。

7.会估算某一算法的总执行时间和时间复杂度。

8.熟悉习题P32:3(5)-(9)、4(2)(3)第二章线性表1.线性表(P7)：是性质相同的一组数据元素序列。

线性表的特性：1)数据元素在线性表中是连续的，表中数据元素的个数可以增加或减少，但调整后数据元素仍必须是连续的，即线性表是一种线性结构。

2)数据元素在线性表中的位置仅取决于自己在表中的序号，并由该元素数据项中的关键字(key)加以标识。

3)线性表中所有数据元素的同一数据项，其属性是相同的，数据类型也是一致的。

线性表的主要运算有：插入、删除、查找、存取、长度、排序、复制、合并。

线性表的顺序存储结构及特点(就是把表中相邻的数据元素存放在内存邻接的存储单元，这种存储方法叫做顺序分配，又称顺序映像。

第1章绪论1.1 什么是数据结构数据与数据之间的关系1.2 基本概念和术语1.基本定义(1).数据(Data) ：是客观事物的符号表示。

在计算机科学中指的是所有能输入到计算机中并被计算机程序处理的符号的总称。

数据元素(Data Element) ：是数据的基本单位，在程序中通常作为一个整体来进行考虑和处理。

(2)数据项(Data Item)：一个数据元素可由若干个数据项组成。

数据项是数据的不可分割的最小单位。

数据项是对客观事物某一方面特性的数据描述。

数据对象(Data Object)：是性质相同的数据元素的集合，是数据的一个子集。

2.举例如字符集合C={‘A’,‘B’,‘C’,…}--C表示字符对象；A ，B等表示数据元素；再如学生集合Students={“Zhangsan”, “Lisi”，…}Zhangsan(ID,name,age,grade,…)……--Students表示学生对象；“Zhangsan”、“Lisi”表示数据元素；Zhangsan的ID、name、age等表示数据项。

3.数据结构的形式定义数据结构的形式定义是一个二元组：Data-Structure=(D，S)其中：D是数据元素的有限集，S是D上关系的有限集4.逻辑结构与物理结构(1)数据元素之间的关系可以是元素之间代表某种含义的自然关系，也可以是为处理问题方便而人为定义的关系，这种自然或人为定义的“关系”称为数据元素之间的逻辑关系，相应的结构称为逻辑结构。

(2)数据结构在计算机中的表示（映像）称为数据的物理结构。

数据结构的存储方式1)顺序存储结构：用数据元素在存储器中的相对位置来表示数据元素之间的逻辑结构(关系)。

2)链式存储结构：在每一个数据元素中增加一个存放另一个元素地址的指针(pointer )，用该指针来表示数据元素之间的逻辑结构(关系)。

3)例：设有数据集合A={3.0,2.3,5.0,-8.5,11.0} ，两种不同的存储结构。

《数据结构》吕云翔编著第1章绪论习题解答数据结构是计算机科学中的一个重要概念，它涉及到存储、组织和管理数据的方法和技术。

《数据结构》是吕云翔编著的一本经典教材，本文将就第1章绪论中的习题进行解答。

1. 为什么要学习数据结构？数据结构是计算机科学的基础，它为我们提供了存储和操作数据的方式。

学习数据结构能够帮助我们更好地理解和分析问题，设计高效的算法，并且能够为我们解决实际问题提供支持。

2. 什么是数据结构？数据结构指的是数据元素之间的关系，以及存储和访问这些数据的方法。

常见的数据结构包括数组、链表、栈、队列、树、图等。

每种数据结构都有各自的特点和适用场景。

3. 数据结构有哪些基本操作？数据结构的基本操作包括插入、删除和查找。

插入操作将一个新的元素插入到数据结构中，删除操作将一个元素从数据结构中移除，查找操作用于寻找特定元素的位置或者判断某个元素是否存在。

4. 什么是线性结构？线性结构是数据元素之间呈线性关系的数据结构。

常见的线性结构有数组和链表。

数组是一种连续存储数据元素的结构，链表是一种通过指针将数据元素链接起来的结构。

5. 什么是非线性结构？非线性结构是数据元素之间呈非线性关系的数据结构。

常见的非线性结构有树和图。

树是一种层次结构，图是由节点和边组成的结构，节点之间的关系可以是任意的。

6. 什么是抽象数据类型？抽象数据类型（ADT）是一种数学模型，它定义了一种数据类型的抽象行为和操作。

ADT将数据的逻辑结构和数据的物理存储分离，使得数据结构和数据操作可以独立地进行设计和实现。

7. 数据结构的选择原则是什么？选择适当的数据结构是解决问题的关键。

选择数据结构应该考虑到数据的特点、操作的效率和实际应用需求。

在选择数据结构时，需要综合考虑空间复杂度和时间复杂度的因素，并且合理权衡它们之间的关系。

8. 数据结构与算法之间有什么关系？数据结构和算法是紧密相关的。

数据结构提供了算法操作的底层基础，而算法则是对数据结构进行操作的具体步骤和方法。

大学课程《数据结构》课后习题答案第 1 章绪论课后习题讲解1. 填空⑴（）是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。

【解答】数据元素⑵（）是数据的最小单位，（）是讨论数据结构时涉及的最小数据单位。

【解答】数据项，数据元素【分析】数据结构指的是数据元素以及数据元素之间的关系。

⑶从逻辑关系上讲，数据结构主要分为（）、（）、（）和（）。

【解答】集合，线性结构，树结构，图结构⑷数据的存储结构主要有（）和（）两种基本方法，不论哪种存储结构，都要存储两方面的内容：（）和（）。

【解答】顺序存储结构，链接存储结构，数据元素，数据元素之间的关系⑸算法具有五个特性，分别是（）、（）、（）、（）、（）。

【解答】有零个或多个输入，有一个或多个输出，有穷性，确定性，可行性⑹算法的描述方法通常有（）、（）、（）和（）四种，其中，（）被称为算法语言。

【解答】自然语言，程序设计语言，流程图，伪代码，伪代码⑺在一般情况下，一个算法的时间复杂度是（）的函数。

【解答】问题规模⑻设待处理问题的规模为n，若一个算法的时间复杂度为一个常数，则表示成数量级的形式为（），若为n*log25n，则表示成数量级的形式为（）。

【解答】Ο(1)，Ο(nlog2n)【分析】用大O记号表示算法的时间复杂度，需要将低次幂去掉，将最高次幂的系数去掉。

2. 选择题⑴顺序存储结构中数据元素之间的逻辑关系是由（）表示的，链接存储结构中的数据元素之间的逻辑关系是由（）表示的。

A 线性结构B 非线性结构C 存储位置D 指针【解答】C，D【分析】顺序存储结构就是用一维数组存储数据结构中的数据元素，其逻辑关系由存储位置（即元素在数组中的下标）表示；链接存储结构中一个数据元素对应链表中的一个结点，元素之间的逻辑关系由结点中的指针表示。

⑵假设有如下遗产继承规则：丈夫和妻子可以相互继承遗产；子女可以继承父亲或母亲的遗产；子女间不能相互继承。

则表示该遗产继承关系的最合适的数据结构应该是（）。

第一章绪论一、选择题1.组成数据的基本单位是A数据项B数据类型C数据元素D数据变量2.数据结构是研究数据的以及它们之间的相互关系;A理想结构,物理结构B理想结构,抽象结构C物理结构,逻辑结构D抽象结构,逻辑结构3.在数据结构中,从逻辑上可以把数据结构分成A动态结构和静态结构B紧凑结构和非紧凑结构C线性结构和非线性结构D内部结构和外部结构4.数据结构是一门研究非数值计算的程序设计问题中计算机的①以及它们之间的②和运算等的学科;① A数据元素B计算方法C逻辑存储D数据映像② A结构B关系C运算D算法5.算法分析的目的是;A 找出数据结构的合理性B研究算法中的输入和输出的关系C分析算法的效率以求改进D分析算法的易懂性和文档性6.计算机算法指的是①,它必须具备输入、输出和②等5个特性;① A计算方法B排序方法C解决问题的有限运算序列D调度方法② A可执行性、可移植性和可扩充性B可行性、确定性和有穷性C确定性、有穷性和稳定性D易读性、稳定性和安全性二、判断题1.数据的机内表示称为数据的存储结构;2.算法就是程序;3.数据元素是数据的最小单位;4.算法的五个特性为：有穷性、输入、输出、完成性和确定性;5.算法的时间复杂度取决于问题的规模和待处理数据的初态;三、填空题1.数据逻辑结构包括________、________、_________ 和_________四种类型,其中树形结构和图形结构合称为_____;2.在线性结构中,第一个结点____前驱结点,其余每个结点有且只有______个前驱结点；最后一个结点______后续结点,其余每个结点有且只有_______个后续结点;3.在树形结构中,树根结点没有_______结点,其余每个结点有且只有_______个前驱结点；叶子结点没有________结点,其余每个结点的后续结点可以_________;4.在图形结构中,每个结点的前驱结点数和后续结点数可以_________;5.线性结构中元素之间存在________关系,树形结构中元素之间存在______关系,图形结构中元素之间存在_______关系;6.算法的五个重要特性是_______、_______、______、_______、_______;7.数据结构的三要素是指______、_______和________;8.链式存储结构与顺序存储结构相比较,主要优点是________________________________;9.设有一批数据元素,为了最快的存储某元素,数据结构宜用_________结构,为了方便插入一个元素,数据结构宜用____________结构;四、算法分析题1.求下列算法段的语句频度及时间复杂度参考答案：一、选择题1. C 3. C 4. A、B 5. C 、B二、判断题:1、√2、×3、×4、×5、√三、填空题1、线性、树形、图形、集合；非线性网状2、没有；1；没有；13、前驱；1；后继；任意多个4、任意多个5、一对一；一对多；多对多6、有穷性；确定性；可行性；输入；输出7、数据元素；逻辑结构；存储结构8、插入、删除、合并等操作较方便9、顺序存储；链式存储四、算法分析题fori=1; i<=n; i++forj =1; j <=i ; j++x=x+1;分析：该算法为一个二重循环,执行次数为内、外循环次数相乘,但内循环次数不固定,与外循环有关,因些,时间频度Tn=1+2+3+…+n=nn+1/2有1/4≤Tn/n2≤1,故它的时间复杂度为Ｏn2, 即Ｔn与n2 数量级相同; 2、分析下列算法段的时间频度及时间复杂度for i=1;i<=n;i++for j=1;j<=i;j++for k=1;k<=j;k++x=i+j-k;分析算法规律可知时间频度Tn=1+1+2+1+2+3+...+1+2+3+…+n由于有1/6 ≤ Tn/ n3 ≤1,故时间复杂度为Ｏn3第二章线性表一、选择题1.一个线性表第一个元素的存储地址是100,每个元素的长度为2,则第5个元素的地址是A110 B108C100 D1202. 向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变,平均要移动个元素;A64B63 C D73.线性表采用链式存储结构时,其地址;A 必须是连续的B 部分地址必须是连续的C 一定是不连续的D 连续与否均可以4. 在一个单链表中,若p所指结点不是最后结点,在p之后插入s所指结点,则执行As->next=p;p->next=s; B s->next=p->next;p->next=s;Cs->next=p->next;p=s; Dp->next=s;s->next=p;5.在一个单链表中,若删除p所指结点的后续结点,则执行Ap->next=p->next->next; Bp=p->next; p->next=p->next->next;Cp->next=p->next; Dp =p->next->next;6.下列有关线性表的叙述中,正确的是A线性表中的元素之间隔是线性关系B线性表中至少有一个元素C线性表中任何一个元素有且仅有一个直接前趋D线性表中任何一个元素有且仅有一个直接后继7.线性表是具有n个的有限序列n≠0A表元素B字符C数据元素D数据项二、判断题1.线性表的链接存储,表中元素的逻辑顺序与物理顺序一定相同;2.如果没有提供指针类型的语言,就无法构造链式结构;3.线性结构的特点是只有一个结点没有前驱,只有一个结点没有后继,其余的结点只有一个前驱和后继;4.语句p=p->next完成了指针赋值并使p指针得到了p指针所指后继结点的数据域值;5.要想删除p指针的后继结点,我们应该执行q=p->next ；p->next=q->next；freeq;三、填空题1.已知P为单链表中的非首尾结点,在P结点后插入S结点的语句为：_______________________ ;2.顺序表中逻辑上相邻的元素物理位置相邻, 单链表中逻辑上相邻的元素物理位置_________相邻;3.线性表L＝a1,a2,...,an采用顺序存储,假定在不同的n＋1个位置上插入的概率相同,则插入一个新元素平均需要移动的元素个数是________________________4.在非空双向循环链表中,在结点q的前面插入结点p的过程如下：p->prior=q->prior;q->prior->next=p;p->next=q;______________________;5.已知L是无表头结点的单链表,是从下列提供的答案中选择合适的语句序列,分别实现：1表尾插入s结点的语句序列是_______________________________2 表尾插入s结点的语句序列是_______________________________1.p->next=s;2.p=L;3.L=s;4.p->next=s->next;5.s->next=p->next;6.s->next=L;7.s->next=null;8.whilep->next= Q p=p-next;9.whilep->next=null p=p->next;四、算法设计题1.试编写一个求已知单链表的数据域的平均值的函数数据域数据类型为整型;2.已知带有头结点的循环链表中头指针为head,试写出删除并释放数据域值为x的所有结点的c函数;3.某百货公司仓库中有一批电视机,按其价格从低到高的次序构成一个循环链表,每个结点有价格、数量和链指针三个域;现出库销售m台价格为h的电视机,试编写算法修改原链表;4.某百货公司仓库中有一批电视机,按其价格从低到高的次序构成一个循环链表,每个结点有价格、数量和链指针三个域;现新到m台价格为h的电视机,试编写算法修改原链表;5.线性表中的元素值按递增有序排列,针对顺序表和循环链表两种不同的存储方式,分别编写C函数删除线性表中值介于a与ba≤b之间的元素;6.设A=a0,a1,a2,...,an-1,B=b0,b1,b2,...,bm-1是两个给定的线性表,它们的结点个数分别是n和m,且结点值均是整数;若n=m,且ai= bi 0≤i<n ,则A=B；若n<m ,且ai=bi 0≤i<n ,则A<B；若存在一个j, j<m ,j<n ,且ai=bi 0≤i<j , 若aj<bj,则A<B,否则A>B;试编写一个比较A和B的C函数,该函数返回-1或0或1,分别表示A<B或A=B或A>B;7.试编写算法,删除双向循环链表中第k个结点;8.线性表由前后两部分性质不同的元素组成a0,a1,...,an-1,b0,b1,...,bm-1,m和n为两部分元素的个数,若线性表分别采用数组和链表两种方式存储,编写算法将两部分元素换位成b0,b1,...,bm-1,a0,a1,...,an-1,分析两种存储方式下算法的时间和空间复杂度;9.用循环链表作线性表a0,a1,...,an-1和b0,b1,...,bm-1的存储结构,头指针分别为ah和bh,设计C函数,把两个线性表合并成形如a0,b0,a1,b1,…的线性表,要求不开辟新的动态空间,利用原来循环链表的结点完成合并操作,结构仍为循环链表,头指针为head,并分析算法的时间复杂度;10.试写出将一个线性表分解为两个带有头结点的循环链表,并将两个循环链表的长度放在各自的头结点的数据域中的C函数;其中,线性表中序号为偶数的元素分解到第一个循环链表中,序号为奇数的元素分解到第二个循环链表中;11.试写出把线性链表改为循环链表的C函数;12.己知非空线性链表中x结点的直接前驱结点为y,试写出删除x结点的C函数;参考答案：一、选择题1. B 3. D 4. B 5. A 7、C二、判断题:参考答案：1、×2、√3、×4、×5、√三、填空题1、s->next=p->next; p->next=s;2、一定；不一定3、n/24、q->prior=p;5、16 32 2 91 7四、算法设计题1、include ""include ""typedef struct node{int data;struct node link;}NODE;int averNODE head{int i=0,sum=0,ave; NODE p;p=head;whilep=NULL{p=p->link;++i;sum=sum+p->data;}ave=sum/i;return ave;}2、include ""include ""typedef struct node{int data; / 假设数据域为整型/struct node link;}NODE;void del_linkNODE head,int x / 删除数据域为x的结点/ {NODE p,q,s;p=head;q=head->link;whileq=head{ifq->data==x{p->link=q->link;s=q;q=q->link;frees;}else{p=q;q=q->link;}}}3、void delNODE head,float price,int num {NODE p,q,s;p=head;q=head->next;whileq->price<price&&q=head{p=q;q=q->next;}ifq->price==priceq->num=q->num-num; elseprintf"无此产品"; ifq->num==0{p->next=q->next; freeq;}}4、include ""include ""typedef struct node {float price;int num;struct node next;}NODE;void insNODE head,float price,int num {NODE p,q,s;p=head;q=head->next;whileq->price<price&&q=head{p=q;q=q->next;}ifq->price==priceq->num=q->num+num;else{s=NODE mallocsizeofNODE;s->price=price;s->num=num;s->next=p->next;p->next=s;}}5、顺序表：算法思想：从0开始扫描线性表,用k记录下元素值在a与b之间的元素个数,对于不满足该条件的元素,前移k个位置,最后修改线性表的长度;void delelemtype list,int n,elemtype a,elemtype b{int i=0,k=0；whilei<n{iflisti>=a&&listi<=b k++;elselisti-k=listi;i++;}n=n-k; / 修改线性表的长度/}循环链表:void delNODE head,elemtype a,elemtype b{NODE p,q;p= head;q=p->link; / 假设循环链表带有头结点/ whileq=head && q->data<a{p=q;q=q->link;}whileq=head && q->data<b{r=q;q=q->link;freer;}ifp=qp->link=q;}6、define MAXSIZE 100int listAMAXSIZE,listBMAXSIZE; int n,m;int compareint a,int b{int i=0;whileai==bi&&i<n&&i<mi++;ifn==m&&i==n return0;ifn<m&&i==n return-1;ifn>m&&i==m return1;ifi<n&&i<mifai<bi return-1;else ifai>bi return1;}7、void delDUNODE head,int i{DUNODE p;{head=head->next;head->prior=NULL;return0;}Else{forj=0;j<i&&p=NULL;j++p=p->next;ifp==NULL||j>i return1;p->prior->next=p->next;p->next->prior=p->proir;freep;return0;}8.顺序存储:void convertelemtype list,int l,int h / 将数组中第l个到第h个元素逆置/ {elemtype temp;fori=h;i<=l+h/2;i++{temp=listi;listi=listl+h-i;listl+h-i=temp;}}void exchangeelemtype list,int n,int m; {convertlist,0,n+m-1;convertlist,0,m-1;convertlist,m,n+m-1;}该算法的时间复杂度为On+m,空间复杂度为O1 链接存储:不带头结点的单链表typedef struct node{elemtype data;struct node link;}NODE;void convertNODE head,int n,int m{NODE p,q,r;int i;p=head;q=head;fori=0;i<n-1;i++q=q->link; /q指向an-1结点/r=q->link;q->link=NULL;whiler->link=NULLr=r->link; /r指向最后一个bm-1结点/head=q;r->link=p;}该算法的时间复杂度为On+m,但比顺序存储节省时间不需要移动元素,只需改变指针,空间复杂度为O1typedef struct node{elemtype data;struct node link;}NODE;NODE unionNODE ah,NODE bh {NODE a,b,head,r,q;head=ah;a=ah;b=bh;whilea->link=ah&&b->link=bh {r=a->link;q=b->link;a->link=b;b->link=r;a=r;}ifa->link==ah /a的结点个数小于等于b的结点个数/{a->link=b;whileb->link=bhb=b->link;b->link=head;}ifb->link==bh /b的结点个数小于a的结点个数/{r=a->link;a->link=b;b->link=r;}returnhead;}该算法的时间复杂度为On+m,其中n和m为两个循环链表的结点个数.10.typedef struct node{elemtype data;struct node link;}NODE;void analyzeNODE a{NODE rh,qh,r,q,p；int i=0,j=0；/i为序号是奇数的结点个数j为序号是偶数的结点个数/ p=a；rh=NODE mallocsizeofNODE；/rh为序号是奇数的链表头指针/qh=NODE mallocsizeofNODE; /qh为序号是偶数的链表头指针/r=rh;q=qh;whilep=NULL{r->link=p;r=p;i++;p=p->link;ifp=NULL{q->link=p;q=p;j++;p=p->link;}}rh->data=i;r->link=rh;qh->data=j;q->link=qh;}11.typedef struct node {elemtype data;struct node link;}NODE;void changeNODE head {NODE p;p=head;ifhead=NULL{whilep->link=NULLp=p->link;p->link=head;}}12.typedef struct node {elemtype data;struct node link;}NODE;void delNODE x,NODE y{NODE p,q;elemtype d1;p=y;q=x;whileq->next=NULL / 把后一个结点数据域前移到前一个结点/ {p->data=q->data;q=q->link;p=q;p->link=NULL; / 删除最后一个结点/freeq;}第三章栈和队列一、选择题1. 一个栈的入栈序列是a,b,c,d,e,则栈的不可能的输出序列是;A edcbaBdecbaCdceab Dabcde2.栈结构通常采用的两种存储结构是;A 线性存储结构和链表存储结构B散列方式和索引方式C链表存储结构和数组D线性存储结构和非线性存储结构3.判定一个栈ST最多元素为m0为空的条件是;A ST-〉top=0 BST-〉top==0CST-〉top=m0 DST-〉top=m04.判定一个栈ST最多元素为m0为栈满的条件是;AST->top=0 BST->top==0CST->top=m0-1DST->top==m0-15.一个队列的入列序列是1,2,3,4,则队列的输出序列是;A4,3,2,1B1,2,3,4C1,4,3,2D3,2,4,16.循环队列用数组A0,m-1存放其元素值,已知其头尾指针分别是front和rear则当前队列中的元素个数是Arear-front+m%m B rear-front+1 Crear-front-1Drear-front7.栈和队列的共同点是A 都是先进后出B都是先进先出C只允许在端点处插入和删除元素D没有共同点8.表达式ab+c-d的后缀表达式是;Aabcd+-Babc+d- Cabc+d-D-+abcd个元素a1,a2,a3和a4依次通过一个栈,在a4进栈前,栈的状态,则不可能的出栈序是Aa4,a3,a2,a1 Ba3,a2,a4,a1Ca3,a1,a4,a2 Da3,a4,a2,a110.以数组Q0..m－1存放循环队列中的元素,变量rear和qulen分别指示循环队列中队尾元素的实际位置和当前队列中元素的个数,队列第一个元素的实际位置是Arear－qulen Brear－qulen＋mCm－qulen D1＋rear＋m－qulen% m二、填空题1.栈的特点是_______________________,队列的特点是__________________________;2.线性表、栈和队列都是_____________________结构,可以在线性表的______________位置插入和删除元素,对于栈只能在________插入和删除元素,对于队列只能在_______插入元素和_________删除元素;3.一个栈的输入序列是12345,则栈有输出序列12345是____________;正确/错误4.设栈S和队列Q的初始状态皆为空,元素a1,a2,a3,a4,a5和a6依次通过一个栈,一个元素出栈后即进入队列Q,若6个元素出队列的顺序是a3,a5,a4,a6,a2,a1则栈S至少应该容纳_____个元素;三、算法设计题1.假设有两个栈s1和s2共享一个数组stackM,其中一个栈底设在stack0处,另一个栈底设在stackM-1处;试编写对任一栈作进栈和出栈运算的C函数pushx,i和popi,i=l,2;其中i=1表示左边的栈,,i=2表示右边的栈;要求在整个数组元素都被占用时才产生溢出;2.利用两个栈s1,s2模拟一个队列时,如何用栈的运算来实现该队列的运算写出模拟队列的插入和删除的C函数;一个栈s1用于插入元素,另一个栈s2用于删除元素.参考答案：一、选择题1. C 3. B 4. B 5. B 7、C 8、C 9、C 10、D二、填空题1、先进先出；先进后出2、线性；任何；栈顶；队尾；对头3、正确的4、3三、算法设计题1.define M 100elemtype stackM;int top1=0,top2=m-1;int pushelemtype x,int i{iftop1-top2==1 return1; /上溢处理/elseifi==1 stacktop1++=x;ifi==2stacktop2--=x;return0;}int popelemtype px,int iifi==1iftop1==0 return1; else{top1--;px=stacktop1;return0;}elseifi==2iftop2==M-1 return1; else{top2++;px=stacktop2;return0;}}elemtype s1MAXSIZE,s2MAZSIZE; int top1,top2;void enqueueelemtype x{iftop1==MAXSIZE return1;else{pushs1,x;return0;}}void dequeueelemtype px{elemtype x;top2=0;whileemptys1{pops1,&x;pushs2,x;pops2,&x;whileemptys2{pops2,&x;pushs1,x;}}第四章串一、选择题1.下列关于串的叙述中,正确的是A一个串的字符个数即该串的长度B一个串的长度至少是1C空串是由一个空格字符组成的串D两个串S1和S2若长度相同,则这两个串相等2.字符串"abaaabab"的nextval值为A0,1,01,1,0,4,1,0,1 B0,1,0,0,0,0,2,1,0,1C0,1,0,1,0,0,0,1,1 D0,1,0,1,0,1,0,1,13.字符串满足下式,其中head和tail的定义同广义表类似,如head‘xyz’=‘x’,tail‘xyz’= ‘yz’,则s= ; concatheadtails,headtailtails= ‘dc’; Aabcd Bacbd Cacdb Dadcb4.串是一种特殊的线性表,其特殊性表现在A可以顺序存储B数据元素是一个字符C可以链式存储D数据元素可以是多个字符5．设串S1=‘ABCDEFG’,s2=‘PQRST’,函数CONCATX,Y返回X和Y串的连接串,SUBSTRS,I,J 返回串S从序号I开始的J个字符组成的字串,LENGTHS返回串S的长度,则CONCATSUBSTRS1,2,LENGTHS2,SUBSTRS1,LENGTHS2,2的结果串是ABCDEF B BCDEFG CBCPQRST DBCDEFEF二、算法设计1.分别在顺序存储和一般链接存储两种方式下,用C语言写出实现把串s1复制到串s2的串复制函数strcpys1,s2;2.在一般链接存储一个结点存放一个字符方式下,写出采用简单算法实现串的模式匹配的C 语言函数int L_indext,p;参考答案：一、选择题1. A 3. D 4. D 5. D二、算法设计1.顺序存储：include ""define MAXN 100char sMAXN;int S_strlenchar s{int i;fori=0;si='\0';i++;returni;}void S_strcpychar s1,char s2 include "" typedef struct node{char data;struct node link;}NODE;int L_indexNODE t,NODE p{NODE t1,p1,t2;int i;t1=t;i=1;whilet1=NULL{p1=p;t2=t1->link;whilep1->data==t1->data&&p1=NULL{p1=p1->link;t1=t1->link;}ifp1==NULL returni;i++;t1=t2;}return0;}第五章数组和广义表一、选择题1. 常对数组进行的两种基本操作是A建立与删除B索引和修改C查找和修改D查找与索引2.二维数组M的元素是4个字符每个字符占一个存储单元组成的串,行下标i的范围从0到4,列下标j的范围从0到5,M按行存储时元素M35的起始地址与M按列存储时元素的起始地址相同;AM24BM34CM35DM443.数组A810中,每个元素A的长度为3个字节,从首地址SA开始连续存放在存储器内,存放该数组至少需要的单元数是;A80B100C240D2704.数组A810中,每个元素A的长度为3个字节,从首地址SA开始连续存放在存储器内,该数组按行存放时,元素A74的起始地址为;ASA+141BSA+144CSA+222DSA+2255.数组A810中,每个元素A的长度为3个字节,从首地址SA开始连续存放在存储器内,该数组按列存放时,元素A47的起始地址为;ASA+141BSA+180CSA+222DSA+2256.稀疏矩阵一般的压缩存储方法有两种,即;A 二维数组和三维数组B三元组和散列C三元组和十字链表D散列和十字链表7.若采用三元组压缩技术存储稀疏矩阵,只要把每个元素的行下标和列下标互换,就完成了对该矩阵的转置运算,这种观点;A正确B错误8.设矩阵A是一个对称矩阵,为了节省存储,将其下三角部分按行序存放在一维数组B1,nn-1/2中,对下三角部分中任一元素ai,ji<=j,在一组数组B的下标位置k的值是;Aii-1/2+j-1Bii-1/2+jCii+1/2+j-1 Dii+1/2+j二、填空题1.己知二维数组Amn采用行序为主方式存储,每个元素占k个存储单元,并且第一个元素的存储地址是LOCA00,则A00的地址是_____________________;2.二维数组A1020采用列序为主方式存储,每个元素占一个存储单元,并且A00的存储地址是200,则A612的地址是________________;3.有一个10阶对称矩阵A,采用压缩存储方式以行序为主,且A00=1,则A85的地址是__________________;4.设n行n列的下三角矩阵A已压缩到一维数组S1..nn+1/2中,若按行序为主存储,则Aij对应的S中的存储位置是________________;5.若A是按列序为主序进行存储的4×6的二维数组,其每个元素占用3个存储单元,并且A00的存储地址为1000,元素A13的存储地址为___________,该数组共占用_______________个存储单元;三、算法设计1.如果矩阵A中存在这样的一个元素Aij满足条件:Aij是第i行中值最小的元素,且又是第j 列中值最大的元素,则称之为该矩阵的一个马鞍点;编写一个函数计算出1×n的矩阵A的所有马鞍点;只猴子要选大王,选举办法如下:所有猴子按1,2,...,n编号围坐一圈,从1号开始按1、2、...、m报数,凡报m号的退出到圈外,如此循环报数,直到圈内剩下只猴子时,这只猴子就是大王;n 和m由键盘输入,打印出最后剩下的猴子号;编写一程序实现上述函数;3.数组和广义表的算法验证程序编写下列程序:1求广义表表头和表尾的函数head和tail;2计算广义表原子结点个数的函数count_GL;3计算广义表所有原子结点数据域设数据域为整型〉之和的函数sum_GL;参考答案：一、选择题1. C 3. C 4. C 5. B 7、B 8、B二、填空题1、locA00+ni+jk2、3323、424、ii+1/2+j+15、1039；72三、算法设计题1.算法思想：依题意,先求出每行的最小值元素,放入minm之中,再求出每列的最大值元素,放入maxn之中,若某元素既在mini中,又在maxj中,则该元素Aij便是马鞍点,找出所有这样的元素,即找到了所有马鞍点;因此,实现本题功能的程序如下:include <>define m 3define n 4void minmaxint amn{int i1,j,have=0;int minm,maxn;fori1=0;i1<m;i1++/计算出每行的最小值元素,放入minm之中/{mini1=ai10;forj=1;j<n;j++ifai1j<mini1 mini1=ai1j;}forj=0;j<n;j++/计算出每列的最大值元素,放入maxn之中/{maxj=a0j;fori1=1;i1<m;i1++ifai1j>max j maxj=ai1j;}fori1=0;i1<m;i1++forj=0;j<n;j++ifmini1==maxj{printf"%d,%d:%d\n",i1,j,ai1j;have=1;}ifhave printf"没有鞍点＼n";}2.算法思想:本题用一个含有n个元素的数组a,初始时ai中存放猴子的编号i,计数器似的值为0;从ai开始循环报数,每报一次,计数器的值加1,凡报到m时便打印出ai值退出圈外的猴子的编号,同时将ai的值改为O以后它不再参加报数,计数器值重新置为0;该函数一直进行到n 只猴子全部退出圈外为止,最后退出的猴子就是大王;因此,现本题功能的程序如下:include ""main{int a100;int count,d,j,m,n; scanf"%d %d",&m,&n;/ n>=m/ forj=0;j<n;j++aj=j+1;count=0;d=0;whiled<nforj=0;j<n;j++ifaj=0{count++;ifcount==m{printf"% d ",aj;aj=0;count=0;}}}3.include ""include ""typedef struct node { int tag;union{struct node sublist; char data;}dd;struct node link;}NODE;NODE creat_GLchar s {NODE h;char ch;s++;ifch='\0'{h=NODEmallocsizeofNODE; ifch==''{h->tag=1;h->=creat_GLs;}Else{h->tag=0;h->=ch;}}elseh=NULL;ch=s;s++;ifh=NULLifch==','h->link =creat_GLs; elseh->link=NULL; returnh;}void prn_GLNODE p {ifp=NULL{ifp->tag==1{printf"";ifp-> ==NULL printf" ";elseprn_GLp-> ;}elseprintf"%c",p->;ifp->tag==1printf"";ifp->link=NULL{printf",";prn_GLp->link;}}}NODE copy_GLNODE p{NODE q;ifp==NULL returnNULL;q=NODE mallocsizeofNODE; q->tag=p->tag;ifp->tagq-> =copy_GLp-> ;elseq-> =p->;q->link=copy_GLp->link;returnq;}NODE headNODE p /求表头函数/{returnp->;}NODE tailNODE p /求表尾函数/{returnp->link;}int sumNODE p /求原子结点的数据域之和函数/ { int m,n;ifp==NULL return0;else{ ifp->tag==0 n=p->;elsen=sump->;ifp->link=NULLm=sump->link;else m=0;returnn+m;}}int depthNODE p /求表的深度函数/ {int h,maxdh;NODE q;ifp->tag==0 return0;elseifp->tag==1&&p->==NULL return 1; else{maxdh=0;whilep=NULL{ifp->tag==0 h=0; else{q=p->;h=depthq;}ifh>maxdhmaxdh=h; p=p->link;}returnmaxdh+1;}}main{NODE hd,hc;char s100,p;p=getss;hd=creat_GL&p; prn_GLheadhd;prn_GLtailhd;hc=copy_GLhd;printf"copy after:";prn_GLhc;printf"sum:%d\n",sumhd;printf"depth:%d\n",depthhd;}第六章树和二叉树一、选择题1.在线索化二叉树中,t所指结点没有左子树的充要条件是At-〉left==NULL Bt-〉ltag==1Ct-〉ltag=1且t-〉left=NULLD以上都不对2.二叉树按某种顺序线索化后,任一结点均有指向其前趋和后继的线索,这种说法A正确B错误C不同情况下答案不确定3.二叉树的前序遍历序列中,任意一个结点均处在其子女结点的前面,这种说法A正确B错误C不同情况下答案不确定4.由于二叉树中每个结点的度最大为2,所以二叉树是一种特殊的树,这种说法A正确B错误C不同情况下答案不确定5.设高度为h的二叉树上只有度为0和度为2的结点,则此类二叉树中所包含的结点数至少为;A2h B2h-1C2h+1Dh+16.已知某二叉树的后序遍历序列是dabec;中序遍历序列是debac,它的前序遍历序列是;Aacbed BdecabCdeabc Dcedba7.如果T2是由有序树T转换而来的二叉树,那么T中结点的前序就是T2中结点的A前序B中序C后序D层次序8.某二叉树的前序遍历结点访问顺序是abdgcefh,中序遍历的结点访问顺序是dgbaechf,则其后序遍历的结点访问顺序是;Abdgcefha Bgdbecfha Cbdgaechf Dgdbehfca9.二叉树为二叉排序树的充分必要条件是其任一结点的值均大于其左孩子的值、小于其右孩子的值;这种说法A正确B错误C不同情况下答案不确定10.按照二叉树的定义,具有3个结点的二叉树有种;A3B4C5D611.在一非空二叉树的中序遍历序列中,根结点的右边A只有右子树上的所有结点B只有右子树上的部分结点C只有左子树上的部分结点D只有左子树上的所有结点12.树最适合用来表示;A有序数据元素B无序数据元素C元素之间具有分支层次关系的数据D元素之间无联系的数据13.任何一棵二叉树的叶结点在先序、中序和后序遍历序列中的相对次序A不发生改变B发生改变C不能确定D.以上都不对14.实现任意二叉树的后序遍历的非递归算法而不使用栈结构,最佳方案是二叉树采用存储结构;A二叉链表B广义表存储结构C三叉链表D顺序存储结构15.对一个满二叉树,m个树叶,n个结点,深度为h,则An=h+m Bh+m=2nCm=h-1Dn=2h-116.如果某二叉树的前序为stuwv,中序为uwtvs,那么该二叉树的后序为Auwvts BvwutsCwuvts Dwutsv17.具有五层结点的二叉平衡树至少有个结点;A10B12C15D17二、判断题1.二叉树中任何一个结点的度都是2;2.由二叉树结点的先根序列和后根序列可以唯一地确定一棵二叉树;3.一棵哈夫曼树中不存在度为1的结点;4.平衡二叉排序树上任何一个结点的左、右子树的高度之差的绝对值不大于2三、填空题1.指出树和二叉树的三个主要差别___________,___________,_______________;2.从概念上讲,树与二叉树是两种不同的数据结构,将树转化为二叉树的基本目的是____________3.若结点A有三个兄弟包括A本身,并且B是A的双亲结点,B的度是_______________4.若一棵具有n个结点的二叉树采用标准链接存储结构,那么该二叉树所有结点共有_______个空指针域;5.已知二叉树的前序序列为ABDEGCFHIJ,中序序列为DBGEAHFIJC,写出后序序列_______________;6.已知二叉树的后序序列为FGDBHECA,中序序列为BFDGAEHC ,并写出前序序列_________________;7.找出满足下列条件的二叉树1先序和中序遍历,得到的结点访问顺序一样;_________________________2后序和中序遍历,得到的结点访问顺序一样;_________________________3先序和后序遍历,得到的结点访问顺序一样;__________________________8.一棵含有n个结点的k叉树,可能达到的最大深度和最小深度各是多少____________________9.一棵二叉树有67个结点,这些结点的度要么是0,要么是2;这棵二叉树中度为2的结点有______________________个;10.含有100个结点的树有_______________________________________条边;四、问答题1.一棵深度为h的满m叉树具有如下性质:第h层上的结点都是叶结点,其余各层上每个结点都有m棵非空子树;若按层次从上到下,每层从左到右的顺序从1开始对全部结点编号,试计算:1第k层结点数1≤k≤h;2整棵树结点数;3编号为i的结点的双亲结点的编号;4编号为i的结点的第j个孩子结点若有的编号;2.证明：一个满k叉树上的叶子结点数n0和非叶子结点数n1之间满足以下关系：n0=k-1n1+13.已知一组元素为50,28,78,65,23,36,13,42,71,请完成以下操作:1画出按元素排列顺序逐点插入所生成的二叉排序树BT;2分别计算在BT中查找各元素所要进行的元素间的比较次数及平均比较次数;3画出在BT中删除23〉后的二叉树;4.有七个带权结点,其权值分别为3,7,8,2,6,10,14,试以它们为叶结点构造一棵哈夫曼树请按照每个结点的左子树根结点的权小于等于右子树根结点的权的次序构造〉,并计算出带权路径长度WPL及该树的结点总数;5.有一电文共使用五种字符a,b,c,d,e,其出现频率依次为4,7,5,2,9;1试画出对应的编码哈夫曼树要求左子树根结点的权小于等于右子树根结点的权;2求出每个字符的晗夫曼编码;3求出传送电文的总长度;4并译出编码系列101的相应电文;五、算法设计已知一棵具有n个结点的完全二叉树被顺序存储在一维数组An中,试编写一个算法输出Ai结点的双亲和所有孩子;参考答案：一、选择题1. B 3. A 4. B 5. B 7、A 8、D 9、B 10、C 11、A 12、C 13、A 14、C 15、D 16、C 17 C。