计算机专业基础综合数据结构（线性表）历年真题试卷汇编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一>right=-s；P一>right一>left=s；D.s一>left=p；s一>right=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；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分)】(1)pb一>next=pa->next；(2)pb一>prior=pa；语句序列可以是( )。
(3)pa->next=pb；(4)pa->next一>prior=pb；（分数：2.00）A.(1)(2)(4)(3) √B.(4)(3)(2)(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.数据在计算机存储器内表示时，物理地址与逻辑地址不相同的，称之为( )。
【暨南大学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.若经常需要按序号查找线性表中的数据元素，采用( )比较合适。
【北京理工大学2007一、2(1分)】（分数：2.00）A.顺序存储结构√B.链式存储结构C.静态链表D.链式存储结构或静态链表解析：二、填空题(总题数：22，分数：46.00)10.在单链表中设置头结点的作用是__________。
【哈尔滨工业大学2000二、1(1分)】（分数：2.00）________________________________________________________________ __________________________ 正确答案：(正确答案：有头结点后，插入元素和删除元素的算法统一了，不再需要判断是否在第一个元素之前插入和删除第一个元素。
另外，不论链表是否为空，链表指针不变。
参见四、1的解释。
)解析：11.对于一个具有n个结点的单链表，在已知的结点*p后插入一个新结点的时间复杂度为__________，在给定值为x的结点后插入一个新结点的时间复杂度为__________。
【哈尔滨工业大学2001一、1(2分)】（分数：2.00）________________________________________________________________ __________________________ 正确答案：(正确答案：O(1) O(n)) 解析：12.根据线性表的链式存储结构中每一个结点包含的指针个数，将线性链表分成__________和__________；而又根据指针的连接方式，链表又可分成__________和__________。
【西安电子科技大学1998二、4(3分)】（分数：2.00）________________________________________________________________ __________________________ 正确答案：(正确答案：单链表，双链表，(动态)链表，静态链表)解析：13.在双向循环链表中，向p所指的结点之后插入指针入所指的结点，其操作是__________、__________、__________、__________。
【中国矿业大学2000一、1(3分)】________________________________________________________________ __________________________正确答案：(正确答案：f->next=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分)】（分数：2.00）________________________________________________________________ __________________________正确答案：(正确答案：4 2)解析：17.循环单链表的最大优点是：__________。
【福州大学1998二、3(2分)】________________________________________________________________ __________________________正确答案：(正确答案：从任一结点出发都可访问到链表中每一个元素)解析：18.带头结点的双循环链表L中只有一个元素结点的条件是：__________。
【合肥工业大学1999三、3 2000三、2(2分)】（分数：2.00）________________________________________________________________ __________________________正确答案：(正确答案：L一>next一>nex-t==-L&&L一>prior 一>priorL&&L一>next!=L)解析：19.在单链表L中，指针p所指结点有后继结点的条件是：__________。
【合肥工业大学2001三、3(2分)】（分数：2.00）________________________________________________________________ __________________________正确答案：(正确答案：p一>next!--null)解析：20.带头结点的双循环链表L为空表的条件是：__________。
【北京理工大学2000二、1(2分)】【青岛大学2002三、1(2分)】（分数：2.00）________________________________________________________________ __________________________正确答案：(正确答案：L一>nex=L&&L一>priOr=L)解析：21.下面算法的功能是__________。
typedef stuct node{dadetype data；struct node *1ink；}*Linkl．ist；void FUN(Linklist lista，Linklist listb){Link2．ist p；for(p=lista；p一>1ink;p=p一>link);p 一>1ink=1istb;}【北京航空航天大学2006一、2(1分)】（分数：2.00）________________________________________________________________ __________________________正确答案：(正确答案：将链表1istb接到链表lista之后，for语句的作用是查链表lista的尾。