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

加入VIP,免费下载
 

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

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

下载须知

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

版权提示 | 免责声明

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

[考研类试卷]计算机专业基础综合(数据结构)模拟试卷1及答案与解析.doc

1、计算机专业基础综合(数据结构)模拟试卷 1 及答案与解析一、单项选择题1-40 小题,每小题 2 分,共 80 分。下列每题给出的四个选项中,只有一个选项是最符合题目要求的。1 若某线性表中最常用的操作是在最后一个结点之后插入一个结点和删除第一个结点,则下面最节省运算时间的存储方式是( )。(A)单链表(B)带有头指针的单循环链表(C)双链表(D)带有尾指针的单循环链表2 已知两个长度分别为 l 和 s 的降序链表,若将它们合并为一个长度为 l+s 的升序链表,则最坏情况下的时间复杂度是( )。(A)O(l)(B) O(ls)(C) O(min(l,s)(D)O(max(l,s)3 线性表中存

2、放的主要是( )。(A)整型常量(B)字符(C)数据元素(D)信息元素4 下面的叙述中正确的是( )。I线性表在链式存储时,查找第 i 个元素的时间同 i 的值成正比线性表在链式存储时,查找第 i 个元素的时间同 i 的值无关线性表在顺序存储时,查找第 i 个元素的时间同 i 的值成正比(A)仅 I(B)仅 (C)仅 (D)I、5 对于某线性表来说,主要的操作是存取任一指定序号的元素和在最后进行插入运算,那么应该选择( ) 存储方式最节省时间。(A)顺序表(B)双链表(C)带头结点的双循环链表(D)单循环链表6 若线性表最常用的运算是查找第 i 个元素及其前驱的值,则下列存储方式中最节省时间的

3、是( ) 。(A)单链表(B)双链表(C)单循环链表(D)顺序表7 如果线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素,则采用( ) 存储方式最节省运算时间。(A)单链表(B)仅有头指针的单循环链表(C)双链表(D)仅有尾指针的单循环链表8 算法的时间复杂度取决于( )。(A)问题的规模(B)待处理数据的初态(C) A 和 B(D)以上都不正确9 关于链表的特点,下面的叙述中不正确的是( )。(A)插入、删除运算方便(B)可实现随机访问任一元素(C)不必事先估计存储空间(D)所需空间与线性长度成正比10 设线性表中有 2n 个元素,以下操作中,在单链表上实现要比在顺序表上

4、实现效率更高的是( ) 。(A)删除指定元素(B)在最后一个元素的后面插入一个新元素(C)顺序输出前 k 个元素(D)交换第 i 个元素和第 2ni1 个元素的值(i=0,1,n 一 1)11 下面的算法实现的是带附加头结点的单链表数据结点逆序连接,空缺处应当填入( )。void reverse(pointer h) h 为附加头结点指针pointer p,q;P=h 一next;h 一next=NULL;while(P!=null)q=P:P=P 一next:q 一next=h 一next;h 一next=( );(A)h(B) P(C) q(D)q 一next12 若长度为 n 的线性表采

5、用顺序存储结构,在其第 i 个位置插入一个新元素的算法的时间复杂度为( )(1in+1)。(A)O(0)(B) O(1)(C) O(n)(D)O(n 2)13 线性表(a 1,a 2,a n)以链式存储方式存储时,访问第 i 位置元素的时间复杂度为( )。(A)O(i)(B) O(1)(C) O(n)(D)O(i 1)14 非空的循环单链表 head 的尾结点 P 满足( ) 。(A)p 一next=head(B) p-next=NULL(C) P=NULL(D)P=head15 双向链表中有两个指针域,即 prior 和 next,分别指向前驱及后继,设 P 指向链表中的一个结点,q 指向一

6、个待插入结点,现要求在 P 前插入 q,则正确的插入为( )。(A)p 一prior=q;q 一 next=P;p 一prior 一next=q;q 一prior=p 一prior ;(B) q 一prior=p 一prior;p 一prior 一next=q;q 一next=P ;p 一prior=q;(C) q 一next=P;p 一next=q;p 一prior 一next=q;q 一next=P ;(D)p 一prior 一next=q;q 一next=P;q 一prior=p 一prior;p 一prior=q ;16 静态链表中指针表示的是( )。(A)内存地址(B)数组下标(C)

7、下一元素数组下标(D)左、右孩子地址17 在单链表指针为 P 的结点之后插入指针为 s 的结点,正确的操作是( )。(A)p 一next=s ;s 一next=p 一next ;(B) s 一next=p 一next;p 一next=s;(C) p 一next=s;p 一next=s 一next ;(D)p 一next=s 一next;p 一next=s;18 对于一个头指针为 head 的带头结点的单链表,判定该表为空表的条件是 ( )。(A)head=NULL(B) head-next=NULL(C) head 一next=head(D)head!=NULL19 以下与数据的存储结构无关的

8、术语是( )。(A)循环队列(B)链表(C)哈希表(D)栈20 以下数据结构中,( )是线性数据结构。(A)广义表(B)二叉树(C)稀疏矩阵(D)串二、综合应用题41-47 小题,共 70 分。21 有两个集合 A 和 B,利用带头结点链表表示,设头指针分别为 la 和 lb。两集合的链表元素皆为递增有序。设计一个算法,将 A 与 B 合并,合并后仍然保持整个链表中的数据依次递增。不得利用额外的结点空间,只能在 A 和 B 的原有结点空间上完成。要求:(1)给出算法的基本设计思想。(2)根据设计思想,采用 C 或 C+或 Java 语言描述算法,关键之处给出注释。(3)分别给出算法各部分的时间

9、复杂度。22 线性表(a 1,a 2,a 3,a n)中元素递增有序且按顺序存储于计算机内。要求设计一算法用最少时间在表中查找数值为 x 的元素,并将其与后继元素位置相交换。如果线性表中找不到该元素,则将该元素插入表中并使表中元素仍递增有序。 (1)给出算法的基本设计思想。 (2)根据设计思想,采用 C 或 C+或 Java 语言描述算法,关键之处给出注释。 (3)分别给出算法备部分的时间复杂度。23 已知顺序表 A,在不改变顺序表中奇数号元素与偶数号元素相对位置的前提下,设计算法,将所有奇数号元素移到所有偶数号元素前。(1)给出算法的基本设计思想。(2)根据设计思想,采用 C 或 C+或 J

10、ava 语言描述算法,关键之处给出注释。(3)说明你所设计算法的时间复杂度和空间复杂度。24 已知单链表 L 是一个递增有序表,试写一高效算法,删除表中值大于 min 且小于 max 的结点( 若表中有这样的结点) ,同时释放被删结点的空间,这里 min 和 max是两个给定的参数。25 线性表(a 1,a 2,a 3,a n)中元素递增有序且按顺序存储于计算机内。要求设计算法完成以下内容: (1)用最少的时间在表中查找数值为 x 的元素。 (2)若找到将其与后继元素位置相交换。 (3)若找不到将其插入表中并使表中元素仍递增有序。26 设有一个双链表 L,每个结点中除有 prior、data

11、和 next 这 3 个域外,还有一个访问频度域 freq,在链表被启用之前,其值均初始化为零。每当在链表进行一次LocateNode(L,x)运算时,令元素值为 x 的结点中 freq 域的值加 1,并调整表中结点的次序,使其按访问频度的递减排列,以便使频繁访问的结点总是靠近表头。试写一符合上述要求的 LocateNode 运算的算法。27 有一个不带头结点的单链表 list,链表中结点都有两个域:数据域 data 和指针域 link。已知初始时该单链表无序,请设计一个算法将该链表按结点数据域的值的大小,将其从小到大依次重新链接,在链接过程中不得使用除该链表以外的任何链结点空间。要求:(1)

12、给出算法的基本设计思想。(2)根据设计思想,采用 C 或 C+或 Java 语言描述算法,关键之处给出注释。28 如果以单链表表示集合,设集合 A 用单链表 LA 表示,集合 B 用单链表 LB 表示,设计算法求两个集合的差,即 AB。29 已知 3 个带头结点的线性链表 A、B、C 中的结点均依元素值自小至大非递减排列(可能存在两个以上值相同的结点),编写算法对链表 A 进行如下操作:使操作后的链表 A 中仅留下 3 个表中均包含的数据元素的结点,且没有值相同的结点,并释放所有无用结点。限定算法的时间复杂度为 O(m+n+p),其中 m、n 和 p 分别为 3 个表的长度。30 已知非空链表

13、 A,其指针是 list,链表中的结点由两部分组成:数据域 data 和指针域 link。设计一个算法,将链表中数据域值最小的那个链结点移到链表的最前面,在不额外申请新的链结点的情况下,使得算法时间复杂度和空间复杂度尽可能低。要求:(1)给出算法的基本设计思想。(2)根据设计思想,采用 C 或 C+或 Java 语言描述算法,关键之处给出注释。31 已知一个双向链表,其结点结构为数据域 data、左指针域 Uink、右指针域rlink;设指针 P 指向双向链表中的某个结点。写出一个算法,实现 P 所指向的结点和它的前缀结点之间顺序的互换。要求:(1)给出算法的基本设计思想。(2)根据设计思想,

14、采用 C 或 C+或 Java 语言描述算法,关键之处给出注释。32 两个整数序列 A=a1,a 2,a 3,a m 和 B=b1,b 2,b 3,b n 已经存入两个单链表中,设计一个算法,判断序列 B 是否是序列 A 的子序列。33 已知一个带有头结点的单链表 L,其结点结构由两部分组成:数据域 data,指针域 link。设计一个算法,以最高效的方法实现在单链表中删除数据域最小值结点。要求:(1)给出算法的基本设计思想。(2)根据设计思想,采用 C 或 C+或 Java 语言描述算法,关键之处给出注释。34 设有集合 A 和集合 B,要求设计生成集合 C=AB 的算法,其中集合 A、集合

15、B 和集合 C 用链式存储结构表示。计算机专业基础综合(数据结构)模拟试卷 1 答案与解析一、单项选择题1-40 小题,每小题 2 分,共 80 分。下列每题给出的四个选项中,只有一个选项是最符合题目要求的。1 【正确答案】 D【试题解析】 在链表中的最后一个结点之后插入一个结点要知道终端结点的地址,所以,单链表、带有头指针的单循环链表、双链表都不合适。考虑在带有尾指针的单循环链表中删除第一个结点,其时间性能是 O(1),所以答案是 D。【知识模块】 数据结构2 【正确答案】 D【试题解析】 在合并过程中,最坏的情况是两个链表中的元素依次进行比较,比较的次数最少是 m 和 n 中的最大值。【知

16、识模块】 数据结构3 【正确答案】 C【试题解析】 线性表中主要存放的是数据元素,而数据元素可以是整型也可以是字符型,但对于一个线性表来说,所有的数据元素的类型必须相同。【知识模块】 数据结构4 【正确答案】 A【试题解析】 在线性表链式存储结构中,查找第 i 个元素的时间与 i 的位置成正比。而在顺序存储结构中查找第 i 个元素的时间与 i 的位置无关。【知识模块】 数据结构5 【正确答案】 A【试题解析】 线性表中要想最省时间地存取某一指定序号的元素,那么就要利用顺序表这种存储方式。但顺序表不利于插入和删除运算,可是题目中强调是在最后进行插入运算,因此,本题最合适的选项是顺序表。【知识模块

17、】 数据结构6 【正确答案】 D【试题解析】 本题的考点是线性表的存储结构及其特点。在线性表中主要的存储结构有顺序表和链表两种,其特点如下:(1)顺序表可以实现随机存取,其时间复杂度为 O(1)。但在顺序表中,进行插入和删除操作需要移动大量的元素,其时间复杂度为 O(n);(2)链表中只能实现顺序查找,其时间复杂度为 O(n)。但链表中进行插入和删除操作不需要移动元素,只需要修改指针,其时间复杂度为 O(1)。本题中,线性表中常用的操作是取第 i 个元素,所以应选择随机存取结构,即顺序表;同时在顺序表中查找第 i 个元素的前驱也很方便。单链表和单循环链表既不能实现随机存取,查找第 i 个元素的

18、前驱也不方便;双链表虽然能快速查找第 i 个元素的前驱,但不能实现随机存取。【知识模块】 数据结构7 【正确答案】 D【试题解析】 最常用的操作是最后一个元素之后插入一个元素和删除第一个元素,则采用尾指针的单循环链表。【知识模块】 数据结构8 【正确答案】 C【试题解析】 此题考查的知识点是算法时间复杂度的定义。算法的时间复杂度取决于输入问题的规模和待处理数据的初态,所以选 C。A 和 B 都不全面。【知识模块】 数据结构9 【正确答案】 B【试题解析】 链表的特点包括:事先不需要申请存储空间,插入和删除运算方便,但不能实现随机存取。【知识模块】 数据结构10 【正确答案】 A【试题解析】 对

19、于 A,删除指定元素,在顺序表中需要移动较多元素,而在单链表上执行同样的操作不需要移动元素,因此单链表的效率要高一些。 对于 B,在最后一个元素的后面插入一个新元素不需要移动元素,顺序表的效率和单链表相同。对于 C,顺序输出前 k 个元素,单链表和顺序表的效率几乎相同。对于 D,交换第 i 个元素和第 2ni 一 1 个元素的值(i=0,1,n1),由于顺序表可以实现随机查找,因此顺序表的效率会更高一些。【知识模块】 数据结构11 【正确答案】 C【试题解析】 h 一next=q;表示将当前结点作为头结点后的第一元素结点插入。【知识模块】 数据结构12 【正确答案】 C【试题解析】 此题考查的

20、知识点是线性表基本操作的时间复杂度。顺序存储的线性表插入元素时需要从插入位置开始向后移动元素,腾出位置以便插入,平均移动次数为(n+1) 2,所以复杂度为 O(n),选 C。【知识模块】 数据结构13 【正确答案】 C【试题解析】 此题考查的知识点是线性表基本操作的时间复杂度。链式存储的线性表访问第 i 个位置的元素时需要从头开始向后查找,平均查找次数为 (n+1)2,所以时间复杂度为 O(n),选 C。【知识模块】 数据结构14 【正确答案】 A【试题解析】 此题考查的知识点是循环单链表的存储定义。非空的循环单链表的尾结点的指针指向头结点,所以选 A。B、C、D 均不能构成非空的循环单链表。

21、【知识模块】 数据结构15 【正确答案】 A【试题解析】 此题考查的知识点是双向链表的插入操作。在 p 前插入,要修改 p的 prior 指针、p 的 prior 所指结点的 next 指针,所以选 A。B、C、D 都将使地址丢失,连接失败。【知识模块】 数据结构16 【正确答案】 C【试题解析】 静态链表中指针表示的是下一元素的数组下标。【知识模块】 数据结构17 【正确答案】 B【试题解析】 此题考查的知识点是单链表的插入操作。要先保存 p 的后继结点,再连入 s 结点,所以选 B。A、C、D 都将使地址丢失,连接失败。【知识模块】 数据结构18 【正确答案】 B【试题解析】 此题考查的知

22、识点是带头结点的单链表操作。带头结点的单链表空的时候表示只有一个结点存在,但没有存信息。所以选 B。A 表示没有结点,C 表示循环单链表,D 表示有一个指针不为空,所以都不对。【知识模块】 数据结构19 【正确答案】 D【试题解析】 此题考查的知识点是对数据结构和存储结构的理解。A 、B 、C 描述的均为物理结构即数据的存储结构,D 是逻辑结构,所以选 D。【知识模块】 数据结构20 【正确答案】 D【试题解析】 此题考查的知识点是线性结构的定义。线性结构的定义可简单地理解为元素只有一个前导、一个后继,而 A、B、C 有多个后继,均错,所以选 D。【知识模块】 数据结构二、综合应用题41-47

23、 小题,共 70 分。21 【正确答案】 (1)算法的基本设计思想:分别从 A、B 的头结点开始,依次比较A、B 中元素的内容,如果 A 中的元素值大于 B 中的元素值,则将 B 中的结点插入结果链表,反之将 A 中的结点插入结果链表。由于题目中要求将结果链表中的结点按元素值的大小依次递增地排列。因此,如果 A、B 中两个元素值相同,只将其中的一个加入结果链表。(2)算法的设计如下:typedef struct LNodeint data;struct INode*next;* Linkedlist;LinkedList union(IAnkedList la,lb)pa=la 一next;p

24、b=lb 一next; 设工作指针 pa 和 pbpc=la; pc 为结果链表当前结点的前驱指针while(pastruct node*next;lklist;void intersection(lklist*ha,lklist* hb,lklist*&hc)lklist*P,*q,*t:for(P=ha,hc=NULL ; P!=NULL;P=p-next)for(q=hb;q!=NULL ;q=q 一next)if(q 一data=p 一data)break;if(q!=NULL)t=(lklist*)malloc(sizeof(lklist);t 一data=p 一data;t 一next=hc ;hc=t :【知识模块】 数据结构

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