广州大学松田学院2数据结构复习题-线性表-参考答案

第1页共7页数据结构复习题线性表一判断题下列各题正确的请在前面的括号内打错误的打线性表的链式存储结构优于顺序存储链表的每个结点都恰好包含一个指针域在线性表的链式存储结构中逻辑上相邻的两个元素在物理位置上并不一定紧邻顺序存储方式的优点是存储密度大插入删除效率高线性链表的删除算法简单因为当删除链中某个结点后计算机会自动地将后续的各个单元向前移动顺序表的每个结点只能是一个简单类型而链表的每个结点可以是一个复杂类型线性表链式存储的特点是可以用一组任意的存储单元存储表中的数据元素线性表采用顺序存储必须占用一片连续的存储单元顺序表结构适宜于进行顺序存取而链表适宜于进行随机存取插入和删除操作是数据结构中最基本的两种操作所以这两种操作在数组中也经常使用二填空题顺序表中逻辑上相邻的元素在物理位置上必须相连线性表中结点的集合是有限的结点间的关系是一对一关系顺序表相对于链表的优点是节省存储和随机存取链表相对于顺序表的优点是插入删除方便采用顺序存储结构的线性表叫顺序表顺序表中访问任意一个结点的时间复杂度均为链表相对于顺序表的优点是插入删除方便缺点是存储密度小在双链表中要删除已知结点其时间复杂度为在单链表中要在已知结点之前插入一个新结点需找到的直接前趋结点的地址其查找的时间复杂度为单链表中需知道头指针才能遍历整个链表性表中第一个结点没有直接前趋称为开始结点在一个长度为的顺序表中删除第个元素要移动个元素在一个长度为的顺序表中如果要在第个元素前插入一个元素要后移个元素在无头结点的单链表中第一个结点的地址存放在头指针中而其它结点的存储地址存放在前趋结点的指针域中当线性表的元素总数基本稳定且很少进行插入和删除操作但要求以最快速度存取线性表中的元素时应采用顺序存储结构在线性表的链式存储中元素之间的逻辑关系是通过指针决定的在双向链表中每个结点都有两个指针域它们一个指向其前趋结点另一个指向其后继结点对一个需要经常进行插入和删除操作的线性表采用链式存储结构为宜双链表中设是指向其中待删除的结点则需要执行的操作为在如图所示的链表中若在指针所在的结点之后插入数据域值为和的两个结点则可用下列两个语句和来实现该操作第2页共7页三选择题在具有个结点的单链表中实现的操作其算法的时间复杂度都是遍历链表或求链表的第个结点在地址为的结点之后插入一个结点删除开始结点删除地址为的结点的后继结点设为三个结点分别代表它们的地址则如下的存储结构称为循环链表单链表双向循环链表双向链表单链表的存储密度大于等于小于不能确定已知一个顺序存储的线性表设每个结点占个存储单元若第一个结点的地址为则第个结点的地址为在有个结点的顺序表上做插入删除结点运算的时间复杂度为设分别为循环双链表结点的左指针和右指针则指针所指的元素是双循环链表的尾元素的条件是两个指针和分别指向单链表的两个元素所指元素是所指元素前驱的条件是用链表存储的线性表其优点是便于随机存取花费的存储空间比顺序表少便于插入和删除数据元素的物理顺序与逻辑顺序相同在单链表中增加头结点的目的是使单链表至少有一个结点标志表中首结点的位置方便运算的实现说明该单链表是线性表的链式存储结构下面关于线性表的叙述中错误的是关系顺序表必须占一片地址连续的存储单元顺序表可以随机存取任一元素链表不必占用一片地址连续的存储单元链表可以随机存取任一元素是线性表已知的值是经运算后的值是单链表的示意图如下第3页共7页指向链表结点的前趋的指针是设为指向单循环链表上某结点的指针则的直接前驱找不到查找时间复杂度为查找时间复杂度为查找结点的次数约为等概率情况下在有个结点的顺序表上做插入结点运算需平均移动结点的数目为在下列链表中不能从当前结点出发访问到其余各结点的是双向链表单循环链表单链表双向循环链表在顺序表中只要知道就可以求出任一结点的存储地址基地址结点大小向量大小基地址和结点大小在双链表中做插入运算的时间复杂度为链表不具备的特点是随机访问不必事先估计存储空间插入删除时不需移动元素所需空间与线性表成正比以下关于线性表的论述不正确的为线性表中的元素可以是数字字符记录等不同类型线性顺序表中包含的元素个数不是任意的线性表中的每个结点都有且仅有一个直接前趋和一个直接后继存在这样的线性表即表中没有任何结点在的运算中使用顺序表比链表好插入根据序号查找删除根据元素查找四下述算法的功能是什么解返回结点的直接前趋结点地址交换结点和结点和的值不变五程序填空已知线性表中的元素是无序的并以带表头结点的单链表作存储试写一算法删除表中所有大于小于的元素试完成下列程序填空是有头结点的单链表是链表中的两个结点第4页共7页在带头结点的单链表的结点之后插入新元素试完成下列程序填空不存在结点六程序设计题写一个对单循环链表进行遍历打印每个结点的值的算法已知链表中任意结点的地址为对给定的带头结点的单链表编写一个删除中值为的结点的直接前趋结点的算法将一个顺序表中从第个结点开始的个结点删除已知一个单链表编写一个函数从单链表中删除自第个结点起的个结点有个单链表不同结点的数据域值可能相同其头指针为编写一个函数计算值域为的结点个数有两个循环单链表链头指针分别为和编写一个函数将链表链接到链表链接后的链表仍是循环链表解第5页共7页解值为的结点是第一个结点没有直接前趋结点可以删除删除指针所指向的结点解校对一下或换一题超出范围解删除前个元素第6页共7页指向要删除的结点指向要删除的结点的前一个结点指向要删除的结点佟解本题是遍历单链表的每个结点每遇到一个结点结点个数加结点个数存储在变量中实现本题功能的函数如下解本题的算法思想是先找到两链表的尾指针将第一个链表的尾指针与第二个链表的头结点链接起来使之成为循环的函数如下第7页共7页模拟考题在顺序存储的线性表第个位置插入新结点试完成下列程序填空将和封装在一个结构体为线性表的最大长度插入结点函数顺序表已满检查插入位置的正确性位置出错结点移动新结点插入或一个带头指针的单链表写出在值为的结点之后插入个结点的算法找到在其后插入个结点输入待插入的值有两个循环单链表头指针分别为和下列函数是将链表链接到链表链接后的链表仍然是循环链表试完成下列程序填空提示先找到两链表的尾指针再将第一个链表的尾指针与第二个链表的头结点链接起来