1、计算机专业基础综合数据结构（线性表）历年真题试卷汇编 3 及答案与解析一、单项选择题1 静态链表中指针表示的是( )。 【中南大学 2003 二、2(1 分)】（A）下一元素的地址（B）内存储器的地址（C）下一元素在数组中的位置（D）左链或右链指向的元素的地址2 链表不具有的特点是( )。【电子科技大学 2012 一、3(2 分)】【福州大学 1998一、8(2 分) 】【 南京理工大学 2005 一、13(1 分) 】（A）插入、删除不需要移动元素（B）可随机访问任一元素（C）不必事先估计存储空间（D）所需空间与线性长度成正比3 在 n 个结点的线性表的数组实现中，算法的时间复杂性是 O(1
2、)的操作是( )。【哈尔滨工业大学 2003 二、1(1 分)】（A）访问第 i 个结点(1in)和求第 i 个结点的直接前驱(2in)（B）在第 i 个结点后插入一个新结点(1in)（C）删除第 i 个结点(1fn)（D）以上都不对4 (1)静态链表既有顺序存储的优点，又有动态链表的优点。所以，它存取表中第 f个元素的时间与 i 无关。(2)静态链表中能容纳的元素个数的最大数在表定义时就确定了，以后不能增加。 (3)静态链表与动态链表在元素的插入、删除上类似，不需做元素的移动。以上错误的是( ) 。【南京理工大学 2000 一、3(15 分)】（A）(1)，(2)（B） (1)（C） (1)
3、，(2)，(3)（D）(2)5 静态链表与动态链表相比，其缺点是( )。 【北京理工大学 2006 九、5(1 分)】（A）插入、删除时需移动较多数据（B）有可能浪费较多存储空间（C）不能随机存取（D）以上都不是6 若长度为 n 的线性表采用顺序存储结构，在其第 i 个位置插入一个新元素的算法的时间复杂度为( )(1in+1)。【北京航空航天大学：1999 一、1(2 分)】（A）O(0)（B） O(1)（C） O(n)（D）O(n 2)7 若长度为 n 的线性表采用顺序存储结构，在其第 i(1in+1)个位置之前插入一个新元素的算法的移动结点的平均次数为( )。 【北京理工大学 2006 五
4、、4(1 分)】（A）n（B） n2（C） (n 一 1)2 （D）(n+1) 28 从一个长度为 n 的顺序表中删除第 i 个元素(1in)时，需向前移动( )个元素。【暨南大学 2010 一、8(2 分)】【烟台大学 2007 一、2(2 分)】【青岛大学 2000 五、1(2 分)】（A）n-i（B） n-i+1（C） n-i-1（D）i9 对顺序存储的线性表，设其长度为 n，在任何位置上插入或删除操作都是等概率的。删除一个元素时平均要移动表中的( )个元素。【华中科技大学 2007 一、1(2分)】（A）n2（B） (n+1)2（C） (n 一 1)2 （D）n10 线性表(a 1，a
5、 2，a n)以链接方式存储时，访问第 i 个位置元素的时间复杂性为( )。【中山大学 1 999 一、2(1 分) 】（A）O(i)（B） O(1)（C） O(n)（D）O(i 一 1)11 在一个单链表中，已知指针 p 指向其中的某个结点，若在该结点前插入一个由指针 s 指向的结点，则需执行( )。 【北京理工大学 2006 九、4(1 分)】（A）s-next=p-next ；p-next=s；（B） p-next=s；s-next=p；（C） r=p-next；p-next=s ；s-next=r ；（D）仅靠已知条件无法实现12 在一个单链表中，若 p 所指的结点不是最后一个结点，在
6、 p 之后插入 s 所指的结点，则执行( ) 。【暨南大学 201 1 一、9(2 分) 】（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 二、19(2 分) 】（A）0（B） 1（C） 2 （D）314 将长度为 n 的单向链表链接在长度为 m 的单向链表之后的算法的时间复杂性为( )。
7、【哈尔滨工业大学 2005 二、1(1 分) 】（A）O(1)（B） O(n)（C） O(m)（D）O(m+n)15 设单循环链表中结点的结构为(data，next)，且 rear 是指向非空的带头结点的单循环链表的尾结点的指针。若要删除链表的第一个结点，正确的操作是( )。【南京理工大学 2004 一、1(1 分)】（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
8、；free(s)；二、填空题16 指针 p 指向单链表的某个结点，在指针 p 所指结点之前插入 s 所指结点。操作序列：_。结点结构(data，next)。【南京理工大学 2006 一(一)、3(15分)】17 带头结点的双向循环链表 L 为空表的条件是_ 。【北京理工大学 2005二、2(2 分) 】18 在一个单链表中，删除 p 所指结点的后继结点，需执行的语句序列如下：_；p 一next=q 一next_ ；【北京理工大学 2006 十、1(1 分)】19 设单链表的结点结构为(data，next)，next 为指针域，已知指针 px 指向单链表中 data 为 x 的结点，指针 py
9、指向 data 为 y，的新结点，若将结点 y 插入结点 x 之后，则需要执行以下语句：_；_；【华中理工大学 2000 一、4(2 分)】20 判断带头结点的单循环链表 L 仅有一个元素结点的条件是 _。【中国科学技术大学 2004】三、判断题21 线性表采用链式存储表示时，所有结点之间的存储单元地址可连续可不连续。 ( )【吉林大学 2007 一、1(1 分) 】（A）正确（B）错误22 链表的每个结点都恰好有一个指针。( )【北京邮电大学 2005 二、2(1 分)】（A）正确（B）错误23 顺序存储方式插入和删除时效率太低，因此它不如链式存储方式好。( )【北京邮电大学 2002 一、
10、2(1 分)】（A）正确（B）错误24 集合与线性表的区别在于是否按关键字排序。( )【大连海事大学 2001 一、5(1分)】（A）正确（B）错误25 所谓静态链表就是一直不发生变化的链表。( )【合肥工业大学 20001烟台大学 2007 二、2(1 分) 】（A）正确（B）错误26 对任何数据结构，链式存储结构一定优于顺序存储结构。( )【南京航空航天大学 1997 一、3(1 分) 】（A）正确（B）错误27 线性表的顺序存储表示优于链式存储表示。( )【中国海洋大学 2005 二、3(1分)】（A）正确（B）错误28 线性表采用链表存储时，结点和结点内部的存储空间可以是不连续的。(
11、)【北京邮电大学 1998 一、2(2 分)】【中国海洋大学 2006 二、1(1 分)】（A）正确（B）错误29 在单链表中，要访问某个结点，只要知道该结点的指针即可，因此，单链表是一种随机存取结构。( ) 【中国海洋大学 2007 二、2(1 分)】（A）正确（B）错误30 顺序存储结构属于静态结构，链式结构属于动态结构。( )【中国海洋大学2007 二、3(1 分) 】（A）正确（B）错误31 在具有头结点的链式存储结构中，头指针指向链表中的第一个数据结点。( )【中国海洋大学 2007 二、1(1 分)】（A）正确（B）错误四、综合题31 线性表有两种存储结构：一是顺序表，二是链表。试
12、问：32 如果有 n 个线性表同时并存，并且在处理过程中各表的长度会动态变化，线性表的总数也会自动地改变。在此情况下，应选用哪种存储结构?为什么?33 若线性表的总数基本稳定，且很少进行插入和删除，但要求以最快的速度存取线性表中的元素，那么应采用哪种存储结构?为什么? 【西安电子科技大学 1999 软件二、1(5 分) 】计算机专业基础综合数据结构（线性表）历年真题试卷汇编 3 答案与解析一、单项选择题1 【正确答案】 C2 【正确答案】 B3 【正确答案】 A4 【正确答案】 B5 【正确答案】 B【试题解析】 静态链表首先要定义一个一维数组空间，每个数组元素有两个分量，一是数据元素的值，二
13、是指针。指针指向下一个元素在数组中的位置(下标)，插入和删除时只需修改指针，不移动数据。不能随机存取。若定义数组太大，有可能浪费较多存储空间。6 【正确答案】 C7 【正确答案】 B8 【正确答案】 A9 【正确答案】 C10 【正确答案】 C【试题解析】 时间复杂度没有 O(i)和 O(i 一 1)这样的描述。11 【正确答案】 D【试题解析】 单链表的结点只有指向后继的指针，插入到某结点后可以在 O(1)时间完成，而在结点前插入，必须知道该结点的前驱结点的指针。答案 A 和 C 都是后插，B 使链表“断链”，所以选择 D。12 【正确答案】 D13 【正确答案】 A,C14 【正确答案】
14、C【试题解析】 先找到长度为 m 的单向链表的表尾结点的指针 p，再链接长度 n 的单向链表。15 【正确答案】 D二、填空题16 【正确答案】 参见本章选择题 26。这里用交换两结点数据的办法达到在结点前插入结点的目的。语句序列为：s 一next=p 一next；p 一next=s；p 一datas 一data17 【正确答案】 L 一prior=L 一next=L ；18 【正确答案】 q=p 一next free(q)19 【正确答案】 py 一next=px 一next；px 一next=py20 【正确答案】 L 一next 一next=L&Lnext!=L三、判断题21 【正确答案
15、】 A【试题解析】 线性表是逻辑结构，属于线性结构。顺序存储时叫顺序表，链式存储时叫链表。22 【正确答案】 B23 【正确答案】 B【试题解析】 顺序存储和链式存储各有优缺点，不能笼统说哪一个好，应根据实际情况选用。顺序存储结构实现方法简单，可以随机存取，存储密度大。但是插入、删除操作要移动大量元素，效率低，另外存储空间要预先分配，不易分配恰当，容易造成存储浪费或空间溢出。链表需要用指针体现元素间的逻辑关系，增加了空间开销。插入和删除操作只修改指针，效率高。两种存储结构各有长短，选择哪一种存储结构，由实际问题中的主要因素决定。通常“较稳定”的线性表选择顺序存储结构，而频繁做插入、删除操作的线
16、性表，即动态性较强的线性表宜选择链式存储结构。24 【正确答案】 B【试题解析】 集合内的元素无逻辑关系。25 【正确答案】 B26 【正确答案】 B27 【正确答案】 B28 【正确答案】 B【试题解析】 线性表采用链表存储时，不要求结点所占空间连续，但是一个结点内部空间必须连续。29 【正确答案】 B30 【正确答案】 B31 【正确答案】 B【试题解析】 头指针指向头结点。请参见四、8 的解释。四、综合题32 【正确答案】 选链式存储结构。它可动态申请内存空间，不受表长度(即表中元素个数)的影响，插入、删除时间复杂度为 O(1)。33 【正确答案】 选顺序存储结构。顺序表可以随机存取，时间复杂度为 O(1)。
