线性表课堂作业0001

《线性表课堂作业0001》由会员分享，可在线阅读，更多相关《线性表课堂作业0001（5页珍藏版）》请在装配图网上搜索。

1、线性表表示与实现作业一、关于线性表我们已经知道了哪些？（一）填空题1. 当线性表的元素总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素时，应采用存储结构。2. 线性表L= （a1,a2,.,an）用数组表示，假定删除表中任一元素的概率相同，则删 除一个元素平均需要移动元素的个数。3. 设单链表的结点结构为（data,next）, next为指针域，已知指针px指向单链表中data 为x的结点，指针py指向data为y的新结点，若将结点y插入结点x之后，则需要执行 以下语句:； 。4. 在单链表中设置头结点的作用 。5. 对于一个具有n个结点的单链表，在已知的结点和后

2、插入一个新结点的时间复杂度 为,在给定值为x的结点后插入一个新结点的时间复杂度为。6. 根据线性表的链式存储结构中每一个结点包含的指针个数，将线性链表分成和；而又根据指针的连接方式，链表又可分和。7. 在双向循环链表中，向p所指的结点之后插入指针f所指的结点，其操作是、 、 。8. 顺序存储结构是通 表示元素之间的关系的;链式存储结构是通过表示元素之间的关系的。9. 循环单链表的最大优点是：。10. 带头结点的双循环链表L为空表的条件是：。（二）判断题1. 链表中的头结点仅起到标识的作用。（）2. 顺序存储结构的主要缺点是不利于插入或删除操作。（）3. 线性表采用链表存储时，结点和结点内部的存

3、储空间可以是不连续的。（）4. 顺序存储方式插入和删除时效率太低，因此它不如链式存储方式好。（）5. 顺序存储方式只能用于存储线性结构。（）6. 集合与线性表的区别在于是否按关键字排序。（）7. 所谓静态链表就是一直不发生变化的链表。（）8. 线性表的特点是每个元素都有一个前驱和一个后继。（）10. 取线性表的第1个元素的时间同i的大小有关.（）11. 循环链表不是线性表.（）12. 线性表就是顺序存储的表。（）13. 为了很方便的插入和删除数据，可以使用双向链表存放数据。（）14. 顺序存储方式的优点是存储密度大，且插入、删除运算效率高。（）16.链表是采用链式存储结构的线性表，进行插入、删

4、除操作时，在链表中比在顺序存 储结构中效率高。（）（三）选择题1.线性表是具有n个（）的有限序列（n0）。A.表元素 B.字符C.数据元素D.数据项E.信息项2. 若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用()存储方式最节省时间。A.顺序表B-双链表C.带头结点的双循环链表D.单循环链表3. 某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用()存储方式最节省运算时间。A.单链表 B.仅有头指针的单循环链表C-双链表D.仅有尾指针的单循环链表4. 设一个链表最常用的操作是在末尾插入结点和删除尾结点，则选用()最节省时 间。A.单

5、链表B.单循环链表C.带尾指针的单循环链表D.带头结点的双循环链表5. 静态链表中指针表示的是()。A.内存地址B.数组下标C.下一元素地址D.左、右孩子地址6. 链表不具有的特点是()A-插入、删除不需要移动元素B.可随机访问任一元素C.不必事先估计存储空间D.所需空间与线性长度成正比7. 对于顺序存储的线性表，访问结点和增加、删除结点的时间复杂度为()。A. O(n) O(n) B. O(n) O(1) C. O(1) O(n)D. O(1) O8. 线性表(a1,a2,an)以链接方式存储时，访问第i位置元素的时间复杂性为()A. O (i) B. O (1)C. O (n)D. O (

6、i-1)9. 在单链表指针为p的结点之后插入指针为s的结点，正确的操作是：()。A. p-next=s;s-next=p-next; B. s-next=p-next;p-next=s;C. p-next=s;p-next=s-next; D. p-next=s-next;p-next=s;10. 对于一个头指针为head的带头结点的单链表，判定该表为空表的条件是()A. head=NULL B. headnext=NULLC. headnext=headD. head!=NULL二、你掌握这些运用了吗？1. 线性表的顺序存储结构具有三个弱点：其一，在作插入或删除操作时，需移动大量 元素；其二

7、，由于难以估计，必须预先分配较大的空间，往往使存储空间不能得到充分利用； 其三，表的容量难以扩充。线性表的链式存储结构是否一定都能够克服上述三个弱点，试讨 论之。2. 线性表(气，a。，气)用顺序映射表示时，气和ai+1 (1next; q=p-next; r=q-next；while (q!=L) while (p!=L) & (p-dataq-data) p=p-prior； q-prior-next=r； (1)； q-next=p-next； q-prior=p；(2) ； (3)； q=r； p=q-prior；(4)；2. 设单链表定义如下：typedef struct node

8、int data;struct node *next;Lnode,* LinkList;int Length_LinkList(LinkList L) /求带头结点的单链表L的长度Lnode *p;j=0;while(p-next!=NULL);j+;return(j);3. 阅读算法，并完成填空。设线性表顺序存储结构定义如下：# define MAXSIZE 20typedef int datatype ;typedef struct datatype data MAXSIZE + l ; /表中元素从1单元开始存放int last ; / 表长 SeqList ;利用在表头设立监视哨的方法

9、，实现在顺序表L中查找值为x的元素的位置的算法，如 果没找到返回0,若找到返回其在表中的位置。int Locate ( SeqList L , datatype x )/在表头设立监视哨，从表尾向表头依次查找时，不用再进行查找范围的判定L.data0=x;for( int i=L. last;); /从后往前找return i; /找不到时，i为04. 以下程序的功能是实现带附加头结点的单链表数据结点逆序连接，请填空完善之。void reverse(LinkList h)/* h为附加头结点指针；LinkList同算法分析第2题*/ LinkList p,q;p=h-next; h-next=

10、NULL;while(1)q=p; p=p-next; q-next=h-next; h-next;5. 设有一个由正整数组成的带头结点的无序单链表List，编写完成下列功能的算法: 输出最大的结点值。(要求带注释)其中结点结构如下：typedef struct node int data；struct node *next；NODE；6. 编写从顺序表中删除其值等于X的所有元素的算法。7. 设计一个算法，将乂插入到一个有序(从小到大排序)的线性表(顺序存储结构) 的适当位置上，并保持线性表的有序性。8. 设将n(n1)个整数存放到一维数组R中。设计一个在时间和空间两方面尽可能高效 的算法。将

11、R中的序列循环左移P(0Pn)个位置，即将R中的数据由(X0, X1,Xn-1) 变换为(Xp, Xp-1 Xn-1，X0, X1Xp-1)要求：(1) 给出算法的基本设计思想。(2) 根据设计思想，采用C或C+或JAVA语言描述算法，关键之处给出注释。(3) 说明你所设计算法的时间复杂度和空间复杂度。9. 设L为单链表的头结点地址，其数据结点的数据都是正整数且无相同的，试设计利 用直接插入的原则把该链表整理成数据递增的有序单链表的算法。datalink10. 已知一个带有表头结点的单链表，结点结构为假设该链表只给出了头指针list。在不改变链表的前提下，请设计一个尽可能高效的算法，查找链表中

12、倒数第k个位置上的结点(k为正整数)。若查找成 功，算法输出该结点的data值，并返回1；否则，只返回0；要求：(1) 描述算法的基本设计思想；(2) 描述算法的详细实现步骤；(3) 根据设计思想和实现步骤，采用程序设计语言描述算法(使用(3或C+或JAVA语 言实现)，关键之处请给出简要注释。11. 假设有两个按元素值递增次序排列的线性表，均以单链表形式存储。请编写算法将 这两个单链表归并为一个按元素值递减次序排列的单链表，并要求利用原来两个单链表的结 点存放归并后的单链表。12. 设有两个链表，ha为单向链表，hb为单向循环链表。编写算法，将两个链表合并 成一个单向链表，要求算法所需时间与链表长度无关。