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