《数据结构》习题及答案：第2章线性表(第1次更新20123)

1、数据结构课后练习题第章线性表 /9北京理工大学珠海学院计算机学院“数据结构”课程组编制2011-3-1 /9北京理工大学珠海学院计算机学院“数据结构”课程组编制2011-3-1第2章线性表、选择题表长为N的顺序表，当在任何位置上插入或删除一个元素的概率相等时，插入一个元素所需移动元素的平均次数为（），删除一个元素需要移动的元素个数为（）。【*,】（N-1）/2B.NC.N+1D.N-1E.N/2F.（N+1）/2G.（N-2）/2线性表是具有N个（）的有限序列。【*】A、表元素B、字符C、数据元素D、数据项E、信息“线性表的逻辑顺序和物理顺序总是一致的。”这个结论是（）。【*】A、正确的B、错

2、误的C、不一定，与具体结构有关。线性表采用链式存储结构时，要求内存中可用存储单元的地址（）。【*,】A、必须是连续的B、部分地址必须是连续的C、一定是不连续的D、连续或不连续都可以。带头结点的单链表为空的判定条件是（）。【*】A、head=NULLB、head-next=NULLC、head-next=headD、head!=NULL不带头结点的单链表head为空的判定条件是（）。【*】A、head=NULLB、head-next=NULLC、head-next=headD、head!=NULL非空的循环单链表head的尾结点P满足（）。（注:带头结点）【*】A、P-NEXT=NULLB、p=

3、NULLC、p-next=headD、p=head在一个具有n个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度是（）。【*,】A、O（1）B、O（n）C、O（n2）D、O（nlog2n）在一个单链表中，若删除P所指结点的后继结点，则执行（）。【*,】A、p-next=p-next-nextB、p=p-next;p-next=p-next-nextC、p-next=p-next;D、p=p-next-next;在一个单链表中，若在P所指结点之后插入S所指结点，则执行（）。【*,】A、s-next=p;p-next=s;B、s-next=p-next;p-next=s;C、s-next=p

4、-next;p=s;D、p-next=s;s-next=p;在一个单链表中，已知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;假设双链表结点的类型如下：【*,】typedefstructlinknodeintdata;/数据域structlinknode*llink;/指向前趋结点的指针域structlinknode*rlink;/指向后继结点的指针域bnode;现将一个q所指新结点作为非空双向链表中的

5、p所指结点的前趋结点插入到该双链表中，能正确完成此要求的语句段是（）A、q-rlink=p;q-llink=p-llink;p-llink=q;p-llink-rlink=q;B、p-llink=q;q-rlink=p;p-llink-rlink=q;q-llink=p-llinkC、q-llink=p-rlink;q-rlink=p;p-llink-rlink=q;p-llink=q;D、以上都不对如上题结点结构，如在此非空循环双向链表的结点p之后插入结点s的操作序列是（）。【】A、p-rlink=s;s-llink=p;p-rlink-llink=s;s-rlink=p-rlink;B、p

6、-rlink=s;p-rlink-llink=s;s-llink=p;s-rlink=p-rlink;C、s-llink=p;s-rlink=p-rlink;p-rlink=s;p-rlink-llink=s;D、s-llink=p;s-rlink=p-rlink;p-rlink-llink=s;p-rlink=s;在一个长度为n的单链表上，设有头和尾两个指针，执行（）操作与链表的长度有关。【*,】A、删除单链表中的第一个元素B、删除单链表中最后一个元素C、在单链表第一个元素前插入一个新元素D、在单链表最后一个元素后插入一个新元素线性结构中的一个结点代表一个（）【】A、数据元素B、数据项C、数

7、据D、数据结构非空线性表L=（a1,a2,ai,an）,下列说法正确的是（）【*】A、每个元素都有一个直接前驱和直接后继B、线性表中至少要有一个元素C、表中诸元素的排列顺序必须是由小到大或由大到小的D、除第一个元素和最后一个元素外其余每个元素都有一个且仅有一个直接前驱和直接后继顺序表是线性表的（）【*,】A、链式存储结构B、顺序存储结构C、索引存储结构D、散列存储结构对于顺序表，以下说法错误的是（）【*,】A、顺序表是用一维数组实现的线性表，数组的下标可以看成是元素的绝对地址B、顺序表的所有存储结点按相应数据元素间的逻辑关系决定的次序依次排列C、顺序表的特点是:逻辑结构中相邻的结点在存储结构中

8、仍相邻D、顺序表的特点是:逻辑上相邻的元素，存储在物理位置也相邻的单元中对顺序表上的插入、删除算法的时间复杂性分析来说，通常以（）为标准操作。【*】A、插入操作B、结点移动C、算术表达式D、删除操作对于顺序表的优缺点，以下说法错误的是（）【*】A、无需为表示结点间的逻辑关系而增加额外的存储空间B、可以方便地随机存取表中的任一结点C、插入和删除运算较方便D、由于顺序表要求占用连续的空间，存储分配只能预先进行（静态分配）若某线性表中最常用的操作是取第i个元素和找第i个元素的前趋元素，则采用（）存储方式最节省时间。【*】A、顺序表B、单链表C、双链表D、单循环链表循环链表主要优点是（）【*】A、不再

9、需要头指针了B、已知某个结点的位置后，能够容易找到它的直接前趋C、在进行插入、删除运算时，能更好地保证链表不断开D、从表中任一结点出发都能扫描到整个链表在线性表的下列存储结构中，读取元素花费时间最少的是（）【*,】A、单链表B、双链表C、循环链表D、顺序表二、填空题在线性结构中，第一个结点()前趋结点，其余每个结点有且只有()个前趋结点。【】在顺序表中插入或删除一个元素，需要平均移动()元素，具体移动的元素个数与()有关。【】已知L是无表头结点的单链表，试从下列提供的答案中选择合适的语句序列，分别实现：【*,】表首插入S结点的语句序列是()。表尾插入S结点的语句序列是()。A、P-next=S

10、;E、P=L;C、L=S;D、P-next=S-next;E、S-next=P-next;F、S-next=L;G、S-next=NULL;H、while(P-next!=Q)p=p-next;I、while(P-next!=NULL)P=P-next;已知L是带表头结点的非空单链表，试从下列提供的答案中选择合适的语句序列。【*,】删除首元结点的语句序列是(),删除尾元结点的语句序列是()A、P=P-next;B、P-next=P-next-next;C、while(P!=NULL)P=P-next;D、while(Q-next!=NULL)P=Q;Q=Q-next;E、while(P-nex

11、t!=Q)P=P-next;F、Q=P;G、Q=P-next;H、P=L;I、L=L-next;J、free(Q);已知L是带表头结点的非空单链表，且P结点既不是首元结点，也不是尾元结点，试从下列提供的答案中选择合适的语句序列。【】删除P结点的直接后继结点的语句序列是()，删除P结点的直接前趋结点的语句序列是()A、P-next=P-next-next;B、P=P-Pnext-next;C、while(P-next!=Q)P=P-next;D、while(P-next-next!=Q)P=P-next;E、Q=P;F、Q=P-next;G、P=L;H、L=L-next;I、free(Q);已知

12、结点编号，在各结点查找概率相等的情况下，从n个结点的单链表中查找一个结点，平均要访问()个结点，从n个结点的双链表中查找一个结点，平均要访问()个结点。【,?】对于一个具有n个结点的单链表，在已知p所指结点后插入一个新结点的时间复杂度是（）；在值域为给定值的结点后插入一个新结点的时间复杂度是（）。【*,】单链表是（）的链接存储表示。【】单链表中设置头结点的作用是（）。【*】在单链表中，除首元结点外，任一结点的存储位置由（）指示。【*】在非空双向循环链表中，在结点q的前面插入结点p的过程如下：【*】p-prior=q-prior;q-prior-next=p;p-next=q;（）;在双向链表中

13、，每个结点有两个指针域，一个指向（），另一个指向（）。【*】顺序表中逻辑上相邻的元素的物理位置（）相邻。单链表中逻辑上相邻的元素的物理位置（）相邻。【*】为了便于讨论，有时将含n（nO）个结点的线性结构表示成（al,a2,an）,其中每个ai代表一个。al称为结点，an称为结点，i称为ai在线性表中的。对任意一对相邻结点ai、ai+1（1Win）,ai称为ai+1的直接，ai+1称为TOC o 1-5 h zai的直接。【*】线性结构的基本特征是：若至少含有一个结点，则除起始结点没有直接外，其他结点有且仅有一个直接；除终端结点没有直接外，其它结点有且仅有一个直接.【*】所有结点按1对1的邻接关

14、系构成的整体就是结构。【*】线性表的逻辑结构是结构。其所含结点的个数称为线性表的。【*】在单链表中，指针p所指结点为最后一个结点的条件是。【*】三、判断题顺序存储的线性表可以随机存取。【*】顺序存储的线性表的插入和删除操作不需要付出很大的代价，因为平均每次操作只有近一半的元素需要移动。【*】线性表中的元素可以是各种各样的，但同一线性表中的数据元素具有相同的特性，因此是属于同一数据对象。【*】在线性表的顺序存储结构中，逻辑上相邻的两个元素在物理位置上不一定相邻。【*】在线性表的链式存储结构中，逻辑上相邻的元素在物理位置上不一定相邻。【*】在单链表中，可以从头结点进行查找任何一个元素。【*】线性表

15、的链式存储结构优于顺序存储结构。【*】在线性表的顺序存储结构中，插入和删除元素时，移动元素的个数与该元素的位置有关。【*】在单链表中，要取得某个元素，只要知道该元素的指针即可，因此，单链表是随机存取的存储结构。【*】顺序存储方式只能用于存储线性结构。【*】四、简答题若较频繁地对一个线性表进行插入和删除操作，该线性表宜采用哪种存储结构？为什么？【*】描述概念：头指针、头结点、首元结点的区别？【*,】设A是一个线性表（a1a2an）,采用顺序存储结构，则在等概率的前提下，平均每插入一个元素需要移动的元素个数为多少？若元素插在ai与ai+1之间（0=lnext)q=L;L=L-next;p=L;wh

16、ile(p-next)p=p-next;p-next=q;q-next=NULL;returnL;如果有n个线性表同时共存，并且在处理过程中各表的长度会发生动态变化，线性表的总长度也会自动地改变。在此情况下，应选择哪一种存储结构。为什么？【】若线性表的总数基本稳定，且很少进行插入删除操作，但要求以最快的方式存取线性表的元素，应该用哪种存储结构。为什么？【】设有多项式a(x)=9+8x+9x4+5x10b(x)=-2x+22x7-5x10用单链表给出a(x)、b(x)的存储表示；设c(x)=a(x)+b(x)，求得c(x)并用单链表给出其存储表示。【*,】五、设计题编写一个函数将一个顺序表A(有

17、多个元素且任何元素不为0)分拆成两个顺序表，使A中大于0的元素存放在B中，小于0的元素存放在C中。【*】设顺序表L中的数据元素递增有序。试写一算法，将e插入到顺序表的适当位置，插入后保持该表的有序性。【*】A、B为元素递增有序排列的单链表(同一表中可能有相同元素)，编写算法另建一单链表C,保存两个表的公共元素，要求C的元素值各不相同且递增有序。【*】4、设有一个由正整数组成的无序单链表，编写算法实现下列功能：【*】找出最小值结点，且显示该数值。若该数值为奇数，则将其与直接后继结点的数值交换。若为偶数，则将其直接后继结点删除。六、编程附加题试分别用顺序表和单链表作为存储结构，实现将线性表(a0,

18、a1,a2,.an-1)就地逆置的操作，所谓“就地”指辅助空间为0(1)。【*,】设单链表L是一个非递减有序表，试写一个算法将x插入其中后仍保持L的有序性。【*】设A、B是两个线性表，其表中元素递增有序，长度分别为m和n。试写一算法分别以顺序存储和链式存储将A和B归并成一个仍按元素值递增有序的线性表C,请分析算法的时间复杂度。【*,】单链表L是一个递减有序表，试写一高效算法，删除表中值大于mink且小于maxk的结点(若表中有这样的结点)，同时释放被删结点空间，这里mink和maxk是两个给定的参数，它们可以和表中元素相同，也可以不同。【*】假设以两个元素依值递增有序排列的线性表A,B分别表示

19、两个集合，先要求另辟空间构造一个线性表C,其元素为两集合的交集，且表C中的元素也依值递增有序排列。是对顺序表编写求C的算法。【*】假设在长度大于1的单循环链表中，既无头结点也无头指针。S为指向链表中某个结点的指针，试编写算法删除结点*s的直接前驱结点。【】计算带头结点的单循环链表的结点个数。【】给定一个不带头结点的单链表，编写计算此链表长度的算法。【】第2章线性表参考答案七、选择题1、E，A2、C3、B4、D5、B6、A7、C8、B9、A10、B11、C12、D龚注:(2012-4-25)。修改4个指针，按顺序(1)-(2)-(3)-(4)。或(1),(2),(3)顺序任意，(4)最后。数据结

20、构课后练习题第章线性表 #/9北京理工大学珠海学院计算机学院“数据结构”课程组编制2011-3-1 #/9北京理工大学珠海学院计算机学院“数据结构”课程组编制2011-3-1数据结构课后练习题第章线性表 #/9北京理工大学珠海学院计算机学院“数据结构”课程组编制2011-3-1 #/9北京理工大学珠海学院计算机学院“数据结构”课程组编制2011-3-113、D14、Br数据结构课后练习题第章线性表 #/9北京理工大学珠海学院计算机学院“数据结构”课程组编制2011-3-1 #/9北京理工大学珠海学院计算机学院“数据结构”课程组编制2011-3-1数据结构课后练习题第章线性表 #/9北京理工大学

21、珠海学院计算机学院“数据结构”课程组编制2011-3-1 #/9北京理工大学珠海学院计算机学院“数据结构”课程组编制2011-3-1删除第一个元素：只需移动头指针与长度无关删除最后一个元素：尾指针需移动上一个结点，需搜索整个链表。与长度有关在头插入一个元素：新结点的头指针；头指针赋新结点指针。与长度无关在尾部插入一个元素：尾指针的新结点;尾指针=新结点指针与长度无关15、A16、D17、B18、A19、B20、C21、A22、D23、D数据结构课后练习题第章线性表 #/9北京理工大学珠海学院计算机学院“数据结构”课程组编制2011-3-1 #/9北京理工大学珠海学院计算机学院“数据结构”课程组

22、编制2011-3-1数据结构课后练习题第章线性表 #/9北京理工大学珠海学院计算机学院“数据结构”课程组编制2011-3-1 #/9北京理工大学珠海学院计算机学院“数据结构”课程组编制2011-3-1八、填空题1、没有；12、表中一半；该元素的位置3、(1)FC(2)BIAG4、(1)HGBJ(2)HFDBJ数据结构课后练习题第2章线性表数据结构课后练习题第2章线性表 /9北京理工大学珠海学院计算机学院“数据结构”课程组编制2011-3-1 /9北京理工大学珠海学院计算机学院“数据结构”课程组编制2011-3-15、(1)FAI(2)EGDFAI6、n/2,n/4(此题有误！另作说明)7、0(

23、1)0(n)8、线性表9、插入和删除首元素时不必进行特殊处理10、其直接前趋结点的链域11、q-prior=p;12、前趋结点，后继结点13、必定，不一定14、结点、第一个、最后一个、位置、前驱、后继15、前驱、前驱、后继、后继16、线性17、线性、长度18、pnext=NULL;九、判断题1.V2.X3V4.X56.V7.X89.X10.十、简答题1、宜采用链式存储结构，因为它使线性表的插入和删除操作的时间复杂度为0(1),而顺序存储结构的为0(n)。2、首元结点是指链表中存储线性表中第一个数据元素的结点。为了操作方便，通常在链表的首元结点之前附设一个结点，称为头结点，该结点的数据域中不存线

24、性表的数据元素，其作用是为了对链表进行操作时，可以对空表非空表的情况以及对首元结点进行统一的处理。头指针是指向链表第一个结点(头结点或首元结点)的指针。若链表中附设头结点，则不管线性表是否为空表，头指针均不为空，否则表示空表的链表的头指针为空。这三个概念对单链表、双向链表和循环链表均适用。4、解答：单循环链表中无论设置尾指针还是头指针都可以任一结点从遍历表中其它结点，但设置尾指针时，若在表尾进行插入或删除操作时可在0(1)时间内完成，同样在表头进行插入或删除操作时也可在0(1)时间内完成。但设置的是头指针，表尾进行插入或删除操作，需要遍历整个链表，时间复杂度为0(n)。5、解答：能删除。双链表

25、上删除p所指向的结点的时间复杂度为0(1)，单循环链表上删除p所指向的结点的时间复杂度为0(n)。6、解答：如果长度大于1，则将首元结点删除并插入到表尾。7、解答：应选用链式存储结构。因为顺序表是静态存储结构，只能预先分配存储单元，不能随着线性表长度的改变而变化。而链表则可根据需要动态的申请空间，因此适用于动态变化表长的线性表。8、解答：应该用顺序存储结构。因为顺序存储结构存取元素操作的时间复杂度为0(1)。9、解答：用单链表表示多项式，除指针域外需设置两个数据域，一个用来存储系数，一个用来存储指数。(3)cTT*227A十一、设计题1、voidsplit(SqListA,SqList&B,SqList&C)/采用顺序存储结构实现intI;length=C.length=0;for(I=0;I0)elemB.length=A.elemi;B.length+;elseelemC.length=A.elemi;length+;2、statusListInsert(SqList&L,ElemTypee)ElemType*p,*q,*newbase;intj;if(L.length=L.listsize)newbase=(ElemType)realloc(L.elem,(L.listsize+LI