2020电大数据结构2线性表主题活动

1．根据线性表的定义，想想生活中还有哪些现象可以表现为线性表？请举两例并进行简要分析。（2分）答：在实际问题中线性表的例子是很多的，如学生情况信息表是一个线性表：表中数据元素的类型为学生类型;一个字符串也是一个线性表：表中数据元素的类型为字符型，等等2．在单向链表、双向链表、单向循环链表中，若仅知道指针P指向某结点，不知道头指针，能否将结点*P从相应的链表中删去？请说明原因，写出算法中的关键语句。（3分）单链表将无法删除，因为无法找到*p之前的那个节点，而双链表和单循环链表则可以，时间复杂度为n3．结合自己的学习，分析线性表的顺序存储结构和链式存储结构的优缺点。（2分）（1）顺序存储时，相邻数据元素的存放地址也相邻（逻辑与物理统一）；要求内存中可用存储单元的地址必须是连续的。优点：存储密度大（＝1），存储空间利用率高。缺点：插入或删除元素时不方便。（2）链式存储时，相邻数据元素可随意存放，但所占存储空间分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针优点：插入或删除元素时很方便，使用灵活。缺点：存储密度小（1），存储空间利用率低4．有一个单链表L（至少有两个结点），其头结点指针为head，试写一算法，将最后一个结点变成第一个结点，原来倒数第二个结点变成第二个结点。（3分）voidBinInsert(SeqTablet,RecordTypex){low=2；high=t.length;while(low=high){mid=(low+high)/2;