1、计算机专业基础综合数据结构（线性表）历年真题试卷汇编 4 及答案与解析一、单项选择题1 对于双向循环链表，在 P 指针所指的结点之后插入 s 指针所指结点的操作应为( )。【北京工业大学 2004 一、1(3 分)】（A）P 一right=s；s 一left=p ；p-right 一left=s；s 一right=p 一right；（B） P 一right=s；p-right 一left=s ； s 一left=p； s 一right=p 一fight ；（C） s 一left=p ； s 一right=p 一right；P 一right=-s；P 一right 一left=s；（D）s 一l
2、eft=p； s 一right=p 一fight ；P 一right 一left=s；P 一right=s ；2 设双向循环链表中结点的结构有数据域 data，指针域 pre 和 next，链表不带头结点。若在指针 P 所指结点之后插入结点 S，则应执行下列 ( )操作。【南京理工大学 2005 一、3 (1 分) 】【北京交通大学 2006 一、1(2 分)】（A）P 一next=s；s 一pre=p；P 一next 一pre=s；s 一next=p 一next ；（B） P 一next=s；P 一next-pre=s；s 一pre=p；s 一next=p 一next；（C） s 一pre=
3、p；s 一nex=p 一next ；P 一next=s；P 一next-pre=s；（D）s 一pre=p ；s-next=p 一next；P 一next 一pre=s ；P 一next=s；3 在下列双向链表中，已知指针 pa 指向结点 A，若在 A、C 之间插入指针 pb 所指的结点 B，则依次执行的语句序列可以是( )。【华中科技大学 2006 二、4(2 分)】(1)pb 一next=pa-next；(2)pb 一prior=pa；(3)pa-next=pb ；(4)pa-next 一prior=pb ；（A）(1)(2)(4)(3)（B） (4)(3)(2)(1)（C） (3)(4)
4、(1)(2)（D）(1)(4)(3)(2)4 对于顺序存储的线性表，访问结点和增加、删除结点的时间复杂度为( )。 【电子科技大学 2013 二、4(2 分)】【青岛大学 2000 五、1(2 分)】【烟台大学2007 一、2(2 分) 】（A）O(n)O(n)（B） O(n)O(1)（C） O(1)O(n)（D）O(1)O(1)5 线性表的动态链表存储结构与顺序存储结构相比，优点是( )。【暨南大学 2011一、3(2 分) 】（A）所有的操作算法实现简单（B）便于随机存取（C）便于插入与删除 （D）便于节省存储器空间6 数据在计算机存储器内表示时，物理地址与逻辑地址不相同的，称之为( )。
5、【暨南大学 2010 一、14(2 分)】（A）存储结构（B）逻辑结构（C）链式存储结构（D）顺序存储结构7 若某线性表最常用的操作是存取第 i 个元素及其前驱的值，则采用 ( )存储方式节省时间。【暨南大学 2010 一、5(2 分)】（A）单链表（B）双链表（C）单循环链表（D）顺序表8 根据教科书中线性表的实现方法，线性表中的元素必须是( )。 【北京理工大学 2007 一、1(1 分) 】（A）整数类型（B）字符类型（C）相同类型（D）结构类型9 若经常需要按序号查找线性表中的数据元素，采用( )比较合适。【北京理工大学 2007 一、2(1 分) 】（A）顺序存储结构（B）链式存储结
6、构（C）静态链表（D）链式存储结构或静态链表二、填空题10 在单链表中设置头结点的作用是_。【哈尔滨工业大学 2000 二、1(1分)】11 对于一个具有 n 个结点的单链表，在已知的结点*p 后插入一个新结点的时间复杂度为_，在给定值为 x 的结点后插入一个新结点的时间复杂度为_。【哈尔滨工业大学 2001 一、1(2 分)】12 根据线性表的链式存储结构中每一个结点包含的指针个数，将线性链表分成_和_；而又根据指针的连接方式，链表又可分成_和_。【西安电子科技大学 1998 二、4(3 分)】13 在双向循环链表中，向 p 所指的结点之后插入指针入所指的结点，其操作是_、_、_、_。【中国
7、矿业大学 2000 一、1(3 分)】14 链接存储的特点是利用_来表示数据元素之间的逻辑关系。【中山大学 1998 一、1(1 分) 】15 顺序存储结构是通过_表示元素之间的关系的；链式存储结构是通过_表示元素之间的关系的。【北京理工大学 2001 七、2(2 分)】16 对于双向链表，在两个结点之间插入一个新结点需修改的指针共_个，单链表为_个。【南京理工大学 2000 二、2(3 分)】17 循环单链表的最大优点是：_。【福州大学 1998 二、3(2 分)】18 带头结点的双循环链表 L 中只有一个元素结点的条件是： _。【合肥工业大学 1999 三、3 2000 三、2(2 分)】
8、19 在单链表 L 中，指针 p 所指结点有后继结点的条件是： _。【合肥工业大学 2001 三、3(2 分) 】20 带头结点的双循环链表 L 为空表的条件是：_ 。【北京理工大学 2000二、1(2 分) 】【 青岛大学 2002 三、1(2 分) 】21 下面算法的功能是_。typedef stuct nodedadetype data； struct node *1ink； *Linklist；void FUN(Linklist lista， Linklist listb)Link2ist p；for(p=lista；p 一1ink;p=p 一link);p 一1ink=1istb;【
9、北京航空航天大学 2006 一、2(1 分)】22 已知 L 是有表头结点的非空循环单链表，试从下列提供的答案中选择合适的填入空格中。(1)删除 P 结点之后的结点语句序列是_；(2)在 P 结点前插入 S 结点的语句序列是_。AP 一next=S；BQ=P 一next；CP 一next=S 一next；DS 一next=P 一next；EP 一 next=Q 一next；FQ=P；G P=Q；Hwhile(p 一next!=Q)p=p 一next ；Ifree(Q) ；【 西南交通大学 2004】23 有一个无头结点的单链表，结点有数据域 data，指针域 next，表头指针为 h，通过遍历
10、链表，将链表中所有的链接方向逆转。要求逆转后的链表的表头指针 h 指向原链表的最后一个结点。算法如下所示，请在空格处填入正确的语句。void Inverse( h)if(1) ) return；p=h 一 next；pr=NULL ；while(2) )(h 一next=pr ；pr=h；h=p； (3)；h 一next=pr；inverse【南京理工大学 2005 二、1(3 分)】24 在头指针为 head 且表长大于 1 的循环链表中，指针 P 指向表中某个结点，若_，则*p 的直接后继是尾结点。【重庆大学 2005】24 设有算法：void abc(LinklistH)链表无头结点；r
11、=H；p=r-next；while(p)if(p 一datadata)P 一datar 一data；交换数据；r=p；p=P 一next；abc链表结点结构为(data，next)。25 该算法的功能是什么?26 执行该算法后下面的链表有什么变化?【南京理工大学 2006(三)(7 分) 】27 以下程序的功能是实现带附加头结点的单链表数据结点的逆序连接，请填空完善之。void reverse(pointer h)/*h 为附加头加结点指针*/ pointer P， q；p=h-next ； h 一next=NULL；while(1) )q=p；p=p-next；q 一next=h-next；
12、h 一next=(2) ；【西南交通大学 2000 一、 9】28 下面是用 C 语言编写的对不带头结点的单链表进行就地逆置的算法，该算法用三返回逆置后的链表的头指针，试在空缺处填入适当的语句。void reverse(1inklistfree(pa); pa=(4) )； )elsepa 一coef(5) )；pa-exp(6) )；q=(7)；pa=(8) )；【南京理工大学 2000 三、3(10 分)】30 对单链表中元素按插入方法排序的 C 语言描述算法如下，其中 L 为链表头结点指针。请填充算法中标出的空白处，完成其功能。typedef struct nodeint data； s
13、truct node*next；linknode，*link；voidInsertsort(1ink L)link P，q ，r，u；p=L 一next;(1) ；while(2) )r=L; q=n-next;while(3) 【北京理工大学 1999 第二部分数据结构7(8 分)】32 下面是一个求两个集合 A 和 B 之差 C=A-B 的程序，即当且仅当 e 是 A 的一个元素，但不是 B 中的一个元素时，e 才是 C 中的一个元素。集合用有序链表实现，初始时，A、B 集合中的元素按递增排列，C 为空；操作完成后 A、B 保持不变，C 中元素按递增排列。下面的函数 append(1ast
14、，e)是把值为 e 的新结点链接在由指针 last 指向的结点的后面，并返回新结点的地址；函数 difference(A，B)实现集合运算 A 一 B，并返回表示结果集合 C 的链表的首结点的地址。在执行 A 一 B 运算之前，用于表示结果集合的链表首先增加一个附加的表头结点，以便新结点的添加，当 A-B 运算执行完毕，再删除并释放表示结果集合的链表的表头结点。typedef struct nodeint element； struct node *link；NODE;NODE *A，*B，*C；NODE *append(NODE*la8t， int e)last 一1ink=(NODE*)
15、malloc (sizeof(NODE)；1a8t 一1ink 一element=e；return(last 一link) ；NODE*difference(NODE*A，NODE*B)(NODE*c，*1ast；C=la8t=(NODE*)malloc (sizeof(NODE)；while (1)if (A 一elementelement) 1a8t=append(last，A 一element)； A=A 一link ； )else if (2)A=A 一1ink； B=B 一link;ELSE (3)；while (4)1ast=append(1ast，A 一element)；A=A
16、一link; )(5) ； last=c； c=c 一link； free (last) ；return(C)； *call form：c=difference(A，B)；*【上海大学 2000 一、4(10 分)】三、判断题33 在一个设有头指针和尾指针的单链表中，执行删除该单链表中最后一个元素的操作与链表的长度无关。( )【中南大学 2003 一、2(1 分)】（A）正确（B）错误34 循环链表不是线性表。( )【南京理工大学 1998 二、1(2 分)】（A）正确（B）错误35 带头结点的单循环链表中，任一结点的后继结点的指针域均不空。( )【中国海洋大学 2005 二、7(1 分)】（
17、A）正确（B）错误计算机专业基础综合数据结构（线性表）历年真题试卷汇编 4 答案与解析一、单项选择题1 【正确答案】 D【试题解析】 双链表在 p 指向的结点前或结点后插入结点都可以，但是必须避免“断链”。本例 A 和 B 第一个语句就将 p 的原后继断链，没必要再浪费时间看这两个选择答案后边的其他语句。2 【正确答案】 D3 【正确答案】 A,D4 【正确答案】 A5 【正确答案】 C6 【正确答案】 C7 【正确答案】 D8 【正确答案】 C9 【正确答案】 A二、填空题10 【正确答案】 有头结点后，插入元素和删除元素的算法统一了，不再需要判断是否在第一个元素之前插入和删除第一个元素。另
18、外，不论链表是否为空，链表指针不变。参见四、1 的解释。11 【正确答案】 O(1) O(n)12 【正确答案】 单链表，双链表，(动态)链表，静态链表13 【正确答案】 f-next=p 一next；f-prior=p；p 一next-一prior=f；p 一next=-f;14 【正确答案】 指针15 【正确答案】 结点物理上相邻 结点指针16 【正确答案】 4 217 【正确答案】 从任一结点出发都可访问到链表中每一个元素18 【正确答案】 L 一next 一nex-t=-L&L 一prior 一priorL&L 一next!=L19 【正确答案】 p 一next!-null20 【正确
19、答案】 L 一nex=L&L 一priOr=L21 【正确答案】 将链表 1istb 接到链表 lista 之后，for 语句的作用是查链表 lista 的尾。22 【正确答案】 (1)B E I (2)F：H D A23 【正确答案】 (1)!h 或 h=null 如果表空 (2)p 或 p!=null 未到表尾(3)p=p 一 next 指向下一待处理结点24 【正确答案】 p-next-next=-head25 【正确答案】 (1)本算法的功能是相邻元素比较，逆序交换，算法结束时最大元素换到表尾。26 【正确答案】 执行该算法后链表的结点数据从头到尾为：12，7，10，5，9，15。27
20、 【正确答案】 (1)p!=null 或 p，链表未到尾就一直作(2)q 将当前结点作为头结点后的第一元素结点插入28 【正确答案】 (1)L=L 一next ； 暂存后继 (2)q=L； 待逆置结点(3)L=p； 头指针仍为 L29 【正确答案】 (1)pa!=ha 或 pa-exp!=-1，链表未到尾(2)pa-exp=0 若指数为 0，即本项为常数项(3)q-next=pa-next 删常数项(4)q 取下一元素(5)=pa-coef*pa-exp(6)一 指数项减 1(7)pa 前驱后移(8)pa-next 取下一元素30 【正确答案】 (1)L 一 next=null 置空链表，然后
21、将原链表结点逐个插入有序表中(2)p!-null 或 p，当链表尚未到尾(3)q!=p 查 p 结点在链表中的插入位置，这时 q 是工作指针(4)p-next=r-next 或 p 一next=q 苷 p 结点链入链表中(5)r-next=p r 是 q 的前驱，u 是下个待插入结点的指针31 【正确答案】 (1)本算法功能是将双向循环链表结点的数据域按值自小到大排序，成为非递减(可能包括数据域值相等的结点)有序双向循环链表。(2)(1)r-prior=q-prior； 将 q 结点摘下，以便插入适当位置(2)p-next-prior=q； (2)(3) 将 q 结点插入(3)p-next=q
22、；(4)r=r-next；或 r=q-next； 后移指针，再将后面结点插入适当位置32 【正确答案】 (1)(A!=null&B!-null) 两表均未空时循环(2)A-element-B-element 两表中相等元素不作结果元素(3)B=B 一link 向后移动 B 表指针(4)(A!=null) 或(A)将 A 表剩余部分放入结果表中(5)last-link=null 置链表尾三、判断题33 【正确答案】 B【试题解析】 必须从头指针开始，查找到尾指针所指结点的前驱结点，故操作与链表长度有关。34 【正确答案】 B35 【正确答案】 A【试题解析】 当带头结点的单循环链表为空时，谈不上“后继结点”。如果说“带头结点的单循环链表中不存在空指针”，这种叙述是正确的。
