【考研类试卷】计算机专业基础综合数据结构（线性表）历年真题试卷汇编4及答案解析.doc

1、计算机专业基础综合数据结构（线性表）历年真题试卷汇编 4 及答案解析(总分：66.00，做题时间：90 分钟)一、单项选择题(总题数：15，分数：30.00)1.静态链表中指针表示的是( )。 【中南大学 2003 二、2(1 分)】（分数：2.00）A.下一元素的地址B.内存储器的地址C.下一元素在数组中的位置D.左链或右链指向的元素的地址2.链表不具有的特点是( )。【电子科技大学 2012 一、3(2 分)】【福州大学 1998 一、8(2 分)】【南京理工大学 2005 一、13(1 分)】（分数：2.00）A.插入、删除不需要移动元素B.可随机访问任一元素C.不必事先估计存储空间D.

2、所需空间与线性长度成正比3.在 n 个结点的线性表的数组实现中，算法的时间复杂性是 O(1)的操作是( )。【哈尔滨工业大学 2003二、1(1 分)】（分数：2.00）A.访问第 i 个结点(1in)和求第 i 个结点的直接前驱(2in)B.在第 i 个结点后插入一个新结点(1in)C.删除第 i 个结点(1fn)D.以上都不对4.(1)静态链表既有顺序存储的优点，又有动态链表的优点。所以，它存取表中第 f 个元素的时间与 i 无关。(2)静态链表中能容纳的元素个数的最大数在表定义时就确定了，以后不能增加。 (3)静态链表与动态链表在元素的插入、删除上类似，不需做元素的移动。以上错误的是(

3、)。【南京理工大学 2000 一、3(15 分)】（分数：2.00）A.(1)，(2)B.(1)C.(1)，(2)，(3)D.(2)5.静态链表与动态链表相比，其缺点是( )。 【北京理工大学 2006 九、5(1 分)】（分数：2.00）A.插入、删除时需移动较多数据B.有可能浪费较多存储空间C.不能随机存取D.以上都不是6.若长度为 n 的线性表采用顺序存储结构，在其第 i 个位置插入一个新元素的算法的时间复杂度为( )(1in+1)。【北京航空航天大学：1999 一、1(2 分)】（分数：2.00）A.O(0)B.O(1)C.O(n)D.O(n 2 )7.若长度为 n 的线性表采用顺序存

4、储结构，在其第 i(1in+1)个位置之前插入一个新元素的算法的移动结点的平均次数为( )。 【北京理工大学 2006 五、4(1 分)】（分数：2.00）A.nB.n2C.(n 一 1)2D.(n+1)28.从一个长度为 n 的顺序表中删除第 i 个元素(1in)时，需向前移动( )个元素。【暨南大学 2010 一、8(2 分)】【烟台大学 2007 一、2(2 分)】【青岛大学 2000 五、1(2 分)】（分数：2.00）A.n-iB.n-i+1C.n-i-1D.i9.对顺序存储的线性表，设其长度为 n，在任何位置上插入或删除操作都是等概率的。删除一个元素时平均要移动表中的( )个元素。

5、【华中科技大学 2007 一、1(2 分)】（分数：2.00）A.n2B.(n+1)2C.(n 一 1)2D.n10.线性表(a 1 ，a 2 ，a n )以链接方式存储时，访问第 i 个位置元素的时间复杂性为( )。【中山大学 1 999 一、2(1 分)】（分数：2.00）A.O(i)B.O(1)C.O(n)D.O(i 一 1)11.在一个单链表中，已知指针 p 指向其中的某个结点，若在该结点前插入一个由指针 s 指向的结点，则需执行( )。 【北京理工大学 2006 九、4(1 分)】（分数：2.00）A.s-next=p-next；p-next=s；B.p-next=s；s-next=

6、p；C.r=p-next；p-next=s；s-next=r；D.仅靠已知条件无法实现12.在一个单链表中，若 p 所指的结点不是最后一个结点，在 p 之后插入 s 所指的结点，则执行( )。【暨南大学 201 1 一、9(2 分)】（分数：2.00）A.s-next=p；p-next=s；B.p-next=s；s-next=p；C.p=s；s-next=p-next；D.s-next=p-next；p-next=-s；13.某线性表用带头结点的循环单链表存储，头指针为 head，当 head-next-next-nex=head 成立时，线性表长度可能是( )。【华中科技大学 2007 二、

7、19(2 分)】（分数：2.00）A.0B.1C.2D.314.将长度为 n 的单向链表链接在长度为 m 的单向链表之后的算法的时间复杂性为( )。【哈尔滨工业大学2005 二、1(1 分)】（分数：2.00）A.O(1)B.O(n)C.O(m)D.O(m+n)15.设单循环链表中结点的结构为(data，next)，且 rear 是指向非空的带头结点的单循环链表的尾结点的指针。若要删除链表的第一个结点，正确的操作是( )。【南京理工大学 2004 一、1(1 分)】（分数：2.00）A.s=rear；rear=rear-next；free(s)；B.rear=rear-next；free(s)

8、；C.rear=rear-next 一next；free(s)；D.s=rear-next 一next；rear 一next 一next=-s 一next；free(s)；二、填空题(总题数：5，分数：10.00)16.指针 p 指向单链表的某个结点，在指针 p 所指结点之前插入 s 所指结点。操作序列：_。结点结构(data，next)。【南京理工大学 2006 一(一)、3(15 分)】（分数：2.00）_17.带头结点的双向循环链表 L 为空表的条件是_。【北京理工大学 2005 二、2(2 分)】（分数：2.00）_18.在一个单链表中，删除 p 所指结点的后继结点，需执行的语句序列如

9、下：_；p 一next=q 一next_；【北京理工大学 2006 十、1(1 分)】（分数：2.00）_19.设单链表的结点结构为(data，next)，next 为指针域，已知指针 px 指向单链表中 data 为 x 的结点，指针 py 指向 data 为 y，的新结点，若将结点 y 插入结点 x 之后，则需要执行以下语句：_；_；【华中理工大学 2000 一、4(2 分)】（分数：2.00）_20.判断带头结点的单循环链表 L 仅有一个元素结点的条件是_。【中国科学技术大学 2004】（分数：2.00）_三、判断题(总题数：11，分数：22.00)21.线性表采用链式存储表示时，所有结

10、点之间的存储单元地址可连续可不连续。 ( )【吉林大学 2007 一、1(1 分)】（分数：2.00）A.正确B.错误22.链表的每个结点都恰好有一个指针。( )【北京邮电大学 2005 二、2(1 分)】（分数：2.00）A.正确B.错误23.顺序存储方式插入和删除时效率太低，因此它不如链式存储方式好。( )【北京邮电大学 2002 一、2(1分)】（分数：2.00）A.正确B.错误24.集合与线性表的区别在于是否按关键字排序。( )【大连海事大学 2001 一、5(1 分)】（分数：2.00）A.正确B.错误25.所谓静态链表就是一直不发生变化的链表。( )【合肥工业大学 20001烟台大

11、学 2007 二、2(1 分)】（分数：2.00）A.正确B.错误26.对任何数据结构，链式存储结构一定优于顺序存储结构。( )【南京航空航天大学 1997 一、3(1 分)】（分数：2.00）A.正确B.错误27.线性表的顺序存储表示优于链式存储表示。( )【中国海洋大学 2005 二、3(1 分)】（分数：2.00）A.正确B.错误28.线性表采用链表存储时，结点和结点内部的存储空间可以是不连续的。( )【北京邮电大学 1998 一、2(2 分)】【中国海洋大学 2006 二、1(1 分)】（分数：2.00）A.正确B.错误29.在单链表中，要访问某个结点，只要知道该结点的指针即可，因此，

12、单链表是一种随机存取结构。( )【中国海洋大学 2007 二、2(1 分)】（分数：2.00）A.正确B.错误30.顺序存储结构属于静态结构，链式结构属于动态结构。( )【中国海洋大学 2007 二、3(1 分)】（分数：2.00）A.正确B.错误31.在具有头结点的链式存储结构中，头指针指向链表中的第一个数据结点。( )【中国海洋大学 2007 二、1(1 分)】（分数：2.00）A.正确B.错误四、综合题(总题数：1，分数：4.00)线性表有两种存储结构：一是顺序表，二是链表。试问：（分数：4.00）(1).如果有 n 个线性表同时并存，并且在处理过程中各表的长度会动态变化，线性表的总数也

13、会自动地改变。在此情况下，应选用哪种存储结构?为什么?（分数：2.00）_(2).若线性表的总数基本稳定，且很少进行插入和删除，但要求以最快的速度存取线性表中的元素，那么应采用哪种存储结构?为什么?【西安电子科技大学 1999 软件二、1(5 分)】（分数：2.00）_计算机专业基础综合数据结构（线性表）历年真题试卷汇编 4 答案解析(总分：66.00，做题时间：90 分钟)一、单项选择题(总题数：15，分数：30.00)1.静态链表中指针表示的是( )。 【中南大学 2003 二、2(1 分)】（分数：2.00）A.下一元素的地址B.内存储器的地址C.下一元素在数组中的位置 D.左链或右链指

14、向的元素的地址解析：2.链表不具有的特点是( )。【电子科技大学 2012 一、3(2 分)】【福州大学 1998 一、8(2 分)】【南京理工大学 2005 一、13(1 分)】（分数：2.00）A.插入、删除不需要移动元素B.可随机访问任一元素 C.不必事先估计存储空间D.所需空间与线性长度成正比解析：3.在 n 个结点的线性表的数组实现中，算法的时间复杂性是 O(1)的操作是( )。【哈尔滨工业大学 2003二、1(1 分)】（分数：2.00）A.访问第 i 个结点(1in)和求第 i 个结点的直接前驱(2in) B.在第 i 个结点后插入一个新结点(1in)C.删除第 i 个结点(1f

15、n)D.以上都不对解析：4.(1)静态链表既有顺序存储的优点，又有动态链表的优点。所以，它存取表中第 f 个元素的时间与 i 无关。(2)静态链表中能容纳的元素个数的最大数在表定义时就确定了，以后不能增加。 (3)静态链表与动态链表在元素的插入、删除上类似，不需做元素的移动。以上错误的是( )。【南京理工大学 2000 一、3(15 分)】（分数：2.00）A.(1)，(2)B.(1) C.(1)，(2)，(3)D.(2)解析：5.静态链表与动态链表相比，其缺点是( )。 【北京理工大学 2006 九、5(1 分)】（分数：2.00）A.插入、删除时需移动较多数据B.有可能浪费较多存储空间 C

16、.不能随机存取D.以上都不是解析：解析：静态链表首先要定义一个一维数组空间，每个数组元素有两个分量，一是数据元素的值，二是指针。指针指向下一个元素在数组中的位置(下标)，插入和删除时只需修改指针，不移动数据。不能随机存取。若定义数组太大，有可能浪费较多存储空间。6.若长度为 n 的线性表采用顺序存储结构，在其第 i 个位置插入一个新元素的算法的时间复杂度为( )(1in+1)。【北京航空航天大学：1999 一、1(2 分)】（分数：2.00）A.O(0)B.O(1)C.O(n) D.O(n 2 )解析：7.若长度为 n 的线性表采用顺序存储结构，在其第 i(1in+1)个位置之前插入一个新元素

17、的算法的移动结点的平均次数为( )。 【北京理工大学 2006 五、4(1 分)】（分数：2.00）A.nB.n2 C.(n 一 1)2D.(n+1)2解析：8.从一个长度为 n 的顺序表中删除第 i 个元素(1in)时，需向前移动( )个元素。【暨南大学 2010 一、8(2 分)】【烟台大学 2007 一、2(2 分)】【青岛大学 2000 五、1(2 分)】（分数：2.00）A.n-i B.n-i+1C.n-i-1D.i解析：9.对顺序存储的线性表，设其长度为 n，在任何位置上插入或删除操作都是等概率的。删除一个元素时平均要移动表中的( )个元素。【华中科技大学 2007 一、1(2 分

18、)】（分数：2.00）A.n2B.(n+1)2C.(n 一 1)2 D.n解析：10.线性表(a 1 ，a 2 ，a n )以链接方式存储时，访问第 i 个位置元素的时间复杂性为( )。【中山大学 1 999 一、2(1 分)】（分数：2.00）A.O(i)B.O(1)C.O(n) D.O(i 一 1)解析：解析：时间复杂度没有 O(i)和 O(i 一 1)这样的描述。11.在一个单链表中，已知指针 p 指向其中的某个结点，若在该结点前插入一个由指针 s 指向的结点，则需执行( )。 【北京理工大学 2006 九、4(1 分)】（分数：2.00）A.s-next=p-next；p-next=s

19、；B.p-next=s；s-next=p；C.r=p-next；p-next=s；s-next=r；D.仅靠已知条件无法实现 解析：解析：单链表的结点只有指向后继的指针，插入到某结点后可以在 O(1)时间完成，而在结点前插入，必须知道该结点的前驱结点的指针。答案 A 和 C 都是后插，B 使链表“断链”，所以选择 D。12.在一个单链表中，若 p 所指的结点不是最后一个结点，在 p 之后插入 s 所指的结点，则执行( )。【暨南大学 201 1 一、9(2 分)】（分数：2.00）A.s-next=p；p-next=s；B.p-next=s；s-next=p；C.p=s；s-next=p-ne

20、xt；D.s-next=p-next；p-next=-s； 解析：13.某线性表用带头结点的循环单链表存储，头指针为 head，当 head-next-next-nex=head 成立时，线性表长度可能是( )。【华中科技大学 2007 二、19(2 分)】（分数：2.00）A.0 B.1C.2 D.3解析：14.将长度为 n 的单向链表链接在长度为 m 的单向链表之后的算法的时间复杂性为( )。【哈尔滨工业大学2005 二、1(1 分)】（分数：2.00）A.O(1)B.O(n)C.O(m) D.O(m+n)解析：解析：先找到长度为 m 的单向链表的表尾结点的指针 p，再链接长度 n 的单向

21、链表。15.设单循环链表中结点的结构为(data，next)，且 rear 是指向非空的带头结点的单循环链表的尾结点的指针。若要删除链表的第一个结点，正确的操作是( )。【南京理工大学 2004 一、1(1 分)】（分数：2.00）A.s=rear；rear=rear-next；free(s)；B.rear=rear-next；free(s)；C.rear=rear-next 一next；free(s)；D.s=rear-next 一next；rear 一next 一next=-s 一next；free(s)； 解析：二、填空题(总题数：5，分数：10.00)16.指针 p 指向单链表的某个结

22、点，在指针 p 所指结点之前插入 s 所指结点。操作序列：_。结点结构(data，next)。【南京理工大学 2006 一(一)、3(15 分)】（分数：2.00）_正确答案：(正确答案：参见本章选择题 26。这里用交换两结点数据的办法达到在结点前插入结点的目的。语句序列为：s 一next=p 一next；p 一next=s；p 一datas 一data)解析：17.带头结点的双向循环链表 L 为空表的条件是_。【北京理工大学 2005 二、2(2 分)】（分数：2.00）_正确答案：(正确答案：L 一prior=L 一next=L；)解析：18.在一个单链表中，删除 p 所指结点的后继结点，

23、需执行的语句序列如下：_；p 一next=q 一next_；【北京理工大学 2006 十、1(1 分)】（分数：2.00）_正确答案：(正确答案：q=p 一next free(q)解析：19.设单链表的结点结构为(data，next)，next 为指针域，已知指针 px 指向单链表中 data 为 x 的结点，指针 py 指向 data 为 y，的新结点，若将结点 y 插入结点 x 之后，则需要执行以下语句：_；_；【华中理工大学 2000 一、4(2 分)】（分数：2.00）_正确答案：(正确答案：py 一next=px 一next；px 一next=py)解析：20.判断带头结点的单循环链

24、表 L 仅有一个元素结点的条件是_。【中国科学技术大学 2004】（分数：2.00）_正确答案：(正确答案：L 一next 一next=L&Lnext!=L)解析：三、判断题(总题数：11，分数：22.00)21.线性表采用链式存储表示时，所有结点之间的存储单元地址可连续可不连续。 ( )【吉林大学 2007 一、1(1 分)】（分数：2.00）A.正确 B.错误解析：解析：线性表是逻辑结构，属于线性结构。顺序存储时叫顺序表，链式存储时叫链表。22.链表的每个结点都恰好有一个指针。( )【北京邮电大学 2005 二、2(1 分)】（分数：2.00）A.正确B.错误 解析：23.顺序存储方式插入

25、和删除时效率太低，因此它不如链式存储方式好。( )【北京邮电大学 2002 一、2(1分)】（分数：2.00）A.正确B.错误 解析：解析：顺序存储和链式存储各有优缺点，不能笼统说哪一个好，应根据实际情况选用。顺序存储结构实现方法简单，可以随机存取，存储密度大。但是插入、删除操作要移动大量元素，效率低，另外存储空间要预先分配，不易分配恰当，容易造成存储浪费或空间溢出。链表需要用指针体现元素间的逻辑关系，增加了空间开销。插入和删除操作只修改指针，效率高。两种存储结构各有长短，选择哪一种存储结构，由实际问题中的主要因素决定。通常“较稳定”的线性表选择顺序存储结构，而频繁做插入、删除操作的线性表，即

26、动态性较强的线性表宜选择链式存储结构。24.集合与线性表的区别在于是否按关键字排序。( )【大连海事大学 2001 一、5(1 分)】（分数：2.00）A.正确B.错误 解析：解析：集合内的元素无逻辑关系。25.所谓静态链表就是一直不发生变化的链表。( )【合肥工业大学 20001烟台大学 2007 二、2(1 分)】（分数：2.00）A.正确B.错误 解析：26.对任何数据结构，链式存储结构一定优于顺序存储结构。( )【南京航空航天大学 1997 一、3(1 分)】（分数：2.00）A.正确B.错误 解析：27.线性表的顺序存储表示优于链式存储表示。( )【中国海洋大学 2005 二、3(1

27、 分)】（分数：2.00）A.正确B.错误 解析：28.线性表采用链表存储时，结点和结点内部的存储空间可以是不连续的。( )【北京邮电大学 1998 一、2(2 分)】【中国海洋大学 2006 二、1(1 分)】（分数：2.00）A.正确B.错误 解析：解析：线性表采用链表存储时，不要求结点所占空间连续，但是一个结点内部空间必须连续。29.在单链表中，要访问某个结点，只要知道该结点的指针即可，因此，单链表是一种随机存取结构。( )【中国海洋大学 2007 二、2(1 分)】（分数：2.00）A.正确B.错误 解析：30.顺序存储结构属于静态结构，链式结构属于动态结构。( )【中国海洋大学 20

28、07 二、3(1 分)】（分数：2.00）A.正确B.错误 解析：31.在具有头结点的链式存储结构中，头指针指向链表中的第一个数据结点。( )【中国海洋大学 2007 二、1(1 分)】（分数：2.00）A.正确B.错误 解析：解析：头指针指向头结点。请参见四、8 的解释。四、综合题(总题数：1，分数：4.00)线性表有两种存储结构：一是顺序表，二是链表。试问：（分数：4.00）(1).如果有 n 个线性表同时并存，并且在处理过程中各表的长度会动态变化，线性表的总数也会自动地改变。在此情况下，应选用哪种存储结构?为什么?（分数：2.00）_正确答案：(正确答案：选链式存储结构。它可动态申请内存空间，不受表长度(即表中元素个数)的影响，插入、删除时间复杂度为 O(1)。)解析：(2).若线性表的总数基本稳定，且很少进行插入和删除，但要求以最快的速度存取线性表中的元素，那么应采用哪种存储结构?为什么?【西安电子科技大学 1999 软件二、1(5 分)】（分数：2.00）_正确答案：(正确答案：选顺序存储结构。顺序表可以随机存取，时间复杂度为 O(1)。)解析：