第5章线性表

第5章线性表一、问答题线性表可用顺序表或链表存储。试问：1.两种存储表示各有哪些主要优缺点?2.如果一个表有n个数据元素，并且在处理过程中表的长度会动态发生变化，在此情况下，应选用哪种存储表示？为什么？3.若元素的总数基本稳定，且很少进行插入和删除，但要求以最快的速度存取表中的元素，这时，应采用哪种存储表示？为什么？4.综合1～3，何时选用顺序表,何时选用链表做为线性表的存储结构为宜?5.描述以下三个概念的区别:头指针,头结点,首元结点(第一个元素结点)。6.为什么单循环链表中设置尾指针比设置头指针更好？7.为什么在单循环链表中,若仅知道指针p指向某个结点,不知道头指针,能否将所指结点从相应的链表中删除?若可以,其时间复杂度为多少?二、选择题1.线性结构中的一个结点代表一个（）。A．数据元素B．数据项C．数据据D．数据结构2.线性表若采用链表存储结构，要求内存中可用存储单元的地址（）。Ａ．必须是连续的Ｂ．部分必须是连续的Ｃ．一定是不连续的Ｄ．连续不连续都可以3.线性表L=（a1,a2,…,ai…,an）,下列说法正确的是（）。A．每个元素都有一个直接前驱和直接后继B．线性表中至少要有一个元素C．表中各元素的排列顺序必须是由小到大或由大到小的D．除第一个元素和最后一个元素外其余每个元素都有且仅有一个直接前驱和一个直接后继4.顺序表是（）。A．链式存储结构B．顺序存储结构C．索引存储结构D．散列存储结构5.对顺序表上的插入、删除算法的时间复杂度分析来说,通常以()为基本操作。Ａ．条件判断Ｂ．结点移动Ｃ．算术表达式Ｄ．赋值语句6.对于顺序表的优缺点，以下说法错误的是（）。Ａ．无需为表结点间的逻辑关系而增加额外的存储空间Ｂ．可以方便地随机存取表中的任意结点Ｃ．插入和删除操作较方便Ｄ．由于顺序表要求占用连续的空间，存储分配使用前需预先分配7.在含有n个结点的顺序存储的线性表中，在任一结点前插入一个结点的平均次数为（）。Ａ．nB．n/2C．(n-1)/2D．(n+1)/28.在含有n个结点的顺序存储的线性表中，删除一个结点所需移动结点的平均次数（）。Ａ．nB．n/2C．(n-1)/2D．(n+1)/29.头指针为head的带头结点单链表为空的条件是（）。Ａ．head=NULLB．head-next=NULLC．head-next=headD．head!=NULL10.若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（）存储方式最节省时间。A．顺序表B．双链表C．带头结点的双循环链表D．单循环链表11.某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（）存储方式最节省运算时间。A．单链表B．仅有头指针的单循环链表C．顺序表D．仅有尾指针的单循环链表12.设一个链表最常用的操作是在末尾插入结点和删除尾结点，则选用()最节省时间。A.单链表B.单循环链表C.带尾指针的单循环链表D.带头结点的双循环链表13.若某线性表中最常用的操作是取第i个元素和找第i个元素的前驱元素，则采用（）。A．顺序表B．单链表C．双链表D．单循环链表14.非空单循环链表head的尾结点*p满足（）A．p-next==NULLB．p==NULLC．p-next==headD．p==head15.在一个单链表中，已知*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;16.在一个单链表中，若*p结点不是最后结点，在*p之后插入结点*s，则执行（）。A．s-next=p;p-next=s;B．s-next=p-next;p-next=s;C．s-next=p-next;p=s;D．p-next=s;s-next=p;17.在一个单链表中，若删除*p结点的后继结点，则执行（）。A．q=p-next;p-next=q-next;deleteq;B．p=p-next;p-next=p-next-next;deleteq;C．p-next=p=-next;deleteq;D．p=p-next-next;deketep-next;18.循环链表的主要优点是（）。A．不再需要头指针了B．已知某个结点的位置后，容易找到它的直接前驱C．在进行插入、删除操作时，能更好地保证链表不断开D．从表中任一结点出发都能扫描到整个链表19.在双循环链表的*p结点之后插入*s结点的操作是（）。A．p-next=s;s-prior=p;p-next-prior=s;s-next=p-next;B．p-next=s;p-next-prior=s;s-prior=p;s-next=p-next;C．s-prior=p;s-next=p-next;p-next=s;p-next-prior=s;D．s-prior=p;s-next=p-next;p-next-prior=s;p-next=s;20.在循环链表中,将头指针改设为尾指针rear后,其头结点和尾结点的存储位置分别是()。A．rear和rear-next-nextB．rear-next和rearC．rear-next-next和rearD．rear和rear-next21.在线性表的下列存储结构中,读取元素花费时间最少的是()。A．单链表B．双链表C．循环链表D．顺序表22.若线性表采用顺序存储结构，每个元素占4个存储单元，第一个元素的存储地址是100，则第12个元素的存储地址是()。A．112B．144C．148D．41223.在n个结点的线性表的数组表示法中，算法的时间复杂度为O(1)的操作是()。A．访问第i个结点(1≤i≤n)和求第i个结点的直接前驱(2≤i≤n)B.在第i个结点后插入一个新结点(1≤i≤n)C.删除第i个结点(1≤i≤n)D．以上都不对24.在长度为n的顺序表的第i(1≤i≤n+1)个位置上插入一个元素，元素的移动次数为()。A．n-i+1B.n-iC.iD.i-125.线性表的顺序存储结构是一种（）的存储结构，线性表的链式存储结构是一种（）的存储结构。A.随机存取B.顺序存取C.索引存取D.散列存取26.从表中任一结点出发都能扫描整个表的是（）。A.静态链表B.单链表C.顺序表D.双链表E.循环链表三、填空题1.线性表所含结点个数称为线性表的()。2.为了便于讨论,有时将含n(n≥0)个结点的线性结构表示成(a1,a2...an),其中每个ai代表一个()，a1称为第一个结点,an称为()结点,i称为ai在线性表中的()，对任意一对相邻结点ai、ai+1(1≤in),ai称为ai+1的()，ai+1称为ai的()。3.在顺序表中插入或删除一个元素,平均需要移动()元素,具体移动的元素个数与()有关。4.单链表表示法的基本思想是用()表示结点之间的逻辑关系。5.对于一个具有n个结点的单链表,在所指结点后插入一个结点的时间复杂度为()，在给定值为x的结点后插入新的结点的时间复杂度为()。6.在单链表中,若p和s是两个指针,且满足p-next与s相同,则语句p-next=s-next的作用是()s指向的结点。7.在单链表中,指针p所指结点为最后一个结点的条件是()。8.在单链表中,删除p所指结点的直接后继的操作是()9.在双链表中，每个结点有两个指针域,一个指向(),另一个指向()。10.对于双向链表,在两个结点之间插入一个新结点时需修改的指针共有()个,单链表为()个。四、算法设计1.利用顺序表的操作，实现以下的函数。1)从顺序表中删除具有最小值的元素并由函数返回被删元素的值。空出的位置由最后一个元素填补，若顺序表为空则显示出错信息并退出运行。2)从顺序表中删除第i个元素并由函数返回被删元素的值。如果i不合理或顺序表为空则显示出错信息并退出运行。3)向顺序表中第i个位置插入一个新的元素x。如果i不合理则显示出错信息并退出运行。4)从顺序表中删除具有给定值x的所有元素。5)从顺序表中删除其值在给定值s与t之间（要求s小于t）的所有元素，如果s或t不合理或顺序表为空则显示出错信息并退出运行。6)从有序顺序表中删除其值在给定值s与t之间（要求s小于t）的所有元素，如果s或t不合理或顺序表为空则显示出错信息并退出运行。7)将两个有序顺序表合并成一个新的有序顺序表并由函数返回结果顺序表。8)从顺序表中删除所有其值重复的元素，使表中所有元素的值均不相同。2．设单链表L是一个非递减有序表,试写一个算法将x插入其中后仍保持L的有序性.3.试写出在不带头结点的单链表的第i个元素之前插入一个元素的算法。4.单链表L是一个递减有序表,试写一个高效算法,删除表中值大于min且小于max的结点(设表中有这样的结点),同时释放被删除结点空间,这里min和max是两个给定的参数.请分析算法的时间复杂度.5.编写一个算法将一个头结点指针为pa的单链表A分解成两个单链表A和B,其头结点指针分别为pa和pb,使得A链表中含有原链表A中序号为奇数的元素,而B链表中含有原链表A中序号为偶数的元素,并保持原来的相对顺序.6.假设以线性表A,B依值递增有序排列分别表示两个集合,要求另辟空间构造一个线性表C,其元素为两集合的交集,且表C中元素也依值递增有序排列.对顺序表编写求C的算法.7.以知由单链表表示的线性表中含三类字符的数据元素(如:字母字符,数字字符,和其他字符),试编写算法构造三个以循环链表表示的线性表,使得没个表中只含有同一类的字符,且利用原表中的结点空间作为这三个表的结点空间,头结点可另辟空间.8.给出用单链表存储多项式的结构,并写一个按指数递增次序输入所产生的多项式链表的过程.9．假设有两个按元素值递增有序的线性表A和B，均以带头结点的单链表为存储结构，编写算法将A表和B表归并成一个按元素值递减有序的线性表C，并要求利用原表的结点空间存放表C.10.已知一个循环线性链表如下图所示，设计算法，将所有箭头方向取反（即逆置）a1a2a3an…head11.设一系列整数存放在一个数组中，试设计算法，将所有负数存放在数组的前半部分，将所有正数和零存放在数组的后半部分。要求尽可能少用临时存储单元并使时间最少。12.设有一个由正整数组成的无序（向后）单链表，编写能够完成下列功能的算法：①找出最小值结点，且打印该数值；②若该数值是奇数，则将其与直接后继结点的数值交换；③若该数值是偶数，则将其直接后继结点删除。