ImageVerifierCode 换一换
格式:DOC , 页数:13 ,大小:75KB ,
资源ID:844646      下载积分:2000 积分
快捷下载
登录下载
邮箱/手机:
温馨提示:
如需开发票,请勿充值!快捷下载时,用户名和密码都是您填写的邮箱或者手机号,方便查询和重复下载(系统自动生成)。
如填写123,账号就是123,密码也是123。
特别说明:
请自助下载,系统不会自动发送文件的哦; 如果您已付费,想二次下载,请登录后访问:我的下载记录
支付方式: 支付宝扫码支付 微信扫码支付   
注意:如需开发票,请勿充值!
验证码:   换一换

加入VIP,免费下载
 

温馨提示:由于个人手机设置不同,如果发现不能下载,请复制以下地址【http://www.mydoc123.com/d-844646.html】到电脑端继续下载(重复下载不扣费)。

已注册用户请登录:
账号:
密码:
验证码:   换一换
  忘记密码?
三方登录: 微信登录  

下载须知

1: 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。
2: 试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓。
3: 文件的所有权益归上传用户所有。
4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
5. 本站仅提供交流平台,并不能对任何下载内容负责。
6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

版权提示 | 免责声明

本文([考研类试卷]计算机专业基础综合数据结构(线性表)历年真题试卷汇编4及答案与解析.doc)为本站会员(Iclinic170)主动上传,麦多课文库仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对上载内容本身不做任何修改或编辑。 若此文所含内容侵犯了您的版权或隐私,请立即通知麦多课文库(发送邮件至master@mydoc123.com或直接QQ联系客服),我们立即给予删除!

[考研类试卷]计算机专业基础综合数据结构(线性表)历年真题试卷汇编4及答案与解析.doc

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【试题解析】 当带头结点的单循环链表为空时,谈不上“后继结点”。如果说“带头结点的单循环链表中不存在空指针”,这种叙述是正确的。

copyright@ 2008-2019 麦多课文库(www.mydoc123.com)网站版权所有
备案/许可证编号:苏ICP备17064731号-1