数据结构复习资料1

《数据结构复习资料1》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构复习第一章 绪论复习内容：(1) 基本概念和术语(2) 抽象数据类型的表示与实现(3) 估算算法时间复杂度复习题：1.仿照三元组的抽象数据类型写出抽象数据类型有理数的定义（有理数是其分子、分母均为自然数且分母不为零的分数）。ADTRational_Num{数据对象：D={

2、e1,e2∈n(n为整数集合)}数据关系：R1={,e1是有理数分子，e2是有理数分母，且e2≠0}基本操作：InitRational_Num(&T,v1,v2)操作结果：构造了有理数T，元素e1，e2分别被赋以参数v1,v2的值。DestroyRational_Num（&

3、T）操作结果：有理数T被销毁。Get（T,i,&e）初始条件：有理数T已存在，i∈{1，2}.操作结果：用e返回T有理数的分子和分母的值，i=1返回分子，i=2返回分母。Put(&T,i,e)初始条件：有理数T已存在，i∈{1，2}.操作结果：改变有理数T的分子或分母的值为e，i=1改变分子，i=2改变分母。AddRational_Num(T1,T2,&T3)初始条件：有理数T已存在。操作结果：有理数T1、T2相加，结果存入有理数T3。SubRational_Num(T1,T2,&T3)初始条件：有理数T已存在。操作结果：有理数T1、T2相减，结果存入有理数T3。MulRati

4、onal_Num(T1,T2,&T3)初始条件：有理数T已存在。操作结果：有理数T1、T2相乘，结果存入有理数T3。DivRational_Num(T1,T2,&T3)初始条件：有理数T已存在。操作结果：有理数T1、T2相除，结果存入有理数T3。}ADTRational_Num2.设n为正整数，请确定下列各程序段中前置以记号@的语句的频度：(1)i=1;k=0;while(i<=n-1){@k+=10*i;i++;}答案：n-1(2)for(i=2;i<=n;++i)for(j=2;j<=i-1;++j){++x;a[i,j]=x;}答案：1+2+3+…+n-2=(n-1)(n

5、-2)/2=(n2-3n+2)/23.试写一算法，自大至小依次输出顺序读入的三个整数X，Y和Z的值。voidDescending(){7scanf(x,y,z);if(x=yif(yzif(x>=temp)y=temp;else{y=x;x=temp;}}printf(x,y,z);}//Descending第二章 线性表复习内容：(1)  线性表的类型和定义(2)  线性表的顺序表示和实现(3)  线性表的链式存储和实现(4)  一元多项式的表示及相加线性表----顺序存储结

6、构----顺序表线性表----链式存储结构----链表线性表在顺序存储结构上实现查找、插入和删除的算法区分线性表的逻辑结构和存储结构复习题：1.(1)在顺序表中插入或删除一个元素，需要平均移动【表中一半】元素，具体移动的元素个数与【表长和该元素在表中的位置】有关。(2)顺序表中逻辑上相邻的元素的物理位置【必定】紧邻。单链表中逻辑上相邻的元素的物理位置【不一定】紧邻。2.例2-1假设:有两个集合A和B分别用两个线性表LA和LB表示，即：线性表中的数据元素即为集合中的成员。现要求一个新的集合A＝A∪B。3.简述顺序表和单链表的优缺点。顺序表--优点：①逻辑相邻，物理相邻②可随机存取

7、任一元素③存储空间使用紧凑。缺点：①插入、删除操作需要移动大量的元素②预先分配空间需按最大空间分配，利用不充分③表容量难以扩充。单链表--优点①它是一种动态结构，整个存储空间为多个链表共用②不需预先分配空间③插入、删除操作方便。①单链表的缺点②指针占用额外存储空间③不能随机存取，查找速度慢。4.写出按正位序建立一个单链表的算法。voidCreateList_L(LinkList&L,intn){//正序输入n个数据元素，建立带头结点的单链表L=(LinkList)malloc(sizeof(LNode));L->next=NULL;//先建立一个带头结点的单链表for(i=1;

8、idata);//输入元素值p->next=L->next;L->next=p;//插入}}//CreateList_L5.已知L是带表头结点的非空单链表，且P结点既不是首元结点，也不是尾元结点，试从下列提供的答案中选择合适的语句序列。（1）删除P结点的语句序列是【JLGCN】。（2）删除尾元结点的语句序列是【IKCN】。7(A)P=P->next;(B)P->next=P;(C)P->n