第5章线性表.doc

第5章 线性表 一、问答题 线性表可用顺序表或链表存储。试问： 两种存储表示各有哪些主要优缺点? 如果一个表有n个数据元素，并且在处理过程中表的长度会动态发生变化，在此情况下，应选用哪种存储表示？为什么？ 若元素的总数基本稳定，且很少进行插入和删除，但要求以最快的速度存取表中的元素，这时，应采用哪种存储表示？为什么？ 综合1～3，何时选用顺序表,何时选用链表做为线性表的存储结构为宜? 描述以下三个概念的区别:头指针,头结点,首元结点(第一个元素结点)。 为什么单循环链表中设置尾指针比设置头指针更好？ 为什么在单循环链表中,若仅知道指针p指向某个结点,不知道头指针,能否将 所指结点从相应的链表中删除?若可以,其时间复杂度为多少? 二、选择题 线性结构中的一个结点代表一个（　 ）。　　 A． 数据元素　 B． 数据项　 C． 数据据　 D． 数据结构 线性表若采用链表存储结构，要求内存中可用存储单元的地址（ 　）。 Ａ． 必须是连续的　　　　Ｂ． 部分必须是连续的 Ｃ． 一定是不连续的　　　Ｄ． 连续不连续都可以 线性表L=（a1,a2,…,ai…,an）,下列说法正确的是（ ）。 A． 每个元素都有一个直接前驱和直接后继 B． 线性表中至少要有一个元素 C． 表中各元素的排列顺序必须是由小到大或由大到小的 D． 除第一个元素和最后一个元素外其余每个元素都有且仅有一个直接前驱和一个直接后继 顺序表是（ ）。 A． 链式存储结构 B． 顺序存储结构 C． 索引存储结构 D． 散列存储结构 对顺序表上的插入、删除算法的时间复杂度分析来说,通常以(　 )为基本操作。 Ａ． 条件判断　 Ｂ． 结点移动　 Ｃ． 算术表达式　 　Ｄ． 赋值语句 对于顺序表的优缺点，以下说法错误的是（ ）。 Ａ．无需为表结点间的逻辑关系而增加额外的存储空间 Ｂ．可以方便地随机存取表中的任意结点 Ｃ．插入和删除操作较方便 Ｄ．由于顺序表要求占用连续的空间，存储分配使用前需预先分配 在含有n个结点的顺序存储的线性表中，在任一结点前插入一个结点的平均次数为（ ）。　　 Ａ．n B．n/2 C．(n-1)/2 D．(n+1)/2 在含有n个结点的顺序存储的线性表中，删除一个结点所需移动结点的平均次数（ ）。　　 Ａ．n B．n/2 C．(n-1)/2 D．(n+1)/2 头指针为head的带头结点单链表为空的条件是（ ）。　　 Ａ．head =NULL B．head-next=NULL C．head-next=head D．head!=NULL 若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（ ）存储方式最节省时间。　　　 A．顺序表 B．双链表 C．带头结点的双循环链表 D．单循环链表 某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（ ）存储方式最节省运算时间。　　　 A．单链表 B．仅有头指针的单循环链表 C．顺序表 D．仅有尾指针的单循环链表 设一个链表最常用的操作是在末尾插入结点和删除尾结点，则选用( )最节省时间。 A. 单链表 B. 单循环链表 C. 带尾指针的单循环链表 D. 带头结点的双循环链表 若某线性表中最常用的操作是取第i个元素和找第i个元素的前驱元素，则采用（　 ）。 　 A．顺序表　　 B．单链表　　 C．双链表　　 D．单循环链表 非空单循环链表head的尾结点*p满足（　）　 A．p-next= =NULL B．p= =NULL C．p-next= =head D．p= =head 在一个单链表中，已知*q结点是*p结点的前驱结点，若在*q和*p之间插入结点*s，则执行（　）。 A．s-next=p-next; p-next=s; B．p-next=s-next; s-next=p; C．q-next=s; s-next=p;　　　 D．p-next=s; s-next=q; 在一个单链表中，若*p结点不是最后结点，在