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 的值成正比（A）仅（B）仅 （C）仅 （D）、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 个元素和第 2n-i-1 个元素的值(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 分。20 有两个集合 A 和 B，利用带头结点链表表示，设头指针分别为 la 和 lb。两集合的链表元素皆为递增有序。设计一个算法，将 A 与 B 合并，合并后仍然保持整个链表中的数据依次递增。不得利用额外的结点空间，只能在 A 和 B 的原有结点空间上完成。要求：21 给出算法的基本设计思想。22 根据设计思想，采用 C 或 C+或 Java 语言描述算法，关键之处给出注释。23 分别给出算法各部分的时间复杂度。23
9、 线性表(a 1，a 2，a 3，a n)中元素递增有序且按顺序存储于计算机内。要求设计一算法用最少时间在表中查找数值为 x 的元素，并将其与后继元素位置相交换。如果线性表中找不到该元素，则将该元素插入表中并使表中元素仍递增有序。24 给出算法的基本设计思想。25 根据设计思想，采用 C 或 C+或 Java 语言描述算法，关键之处给出注释。26 分别给出算法各部分的时间复杂度。26 已知顺序表 A，在不改变顺序表中奇数号元素与偶数号元素相对位置的前提下，设计算法，将所有奇数号元素移到所有偶数号元素前。27 给出算法的基本设计思想。28 根据设计思想，采用 C 或 C+或 Java 语言描述算
10、法，关键之处给出注释。29 说明你所设计算法的时间复杂度和空间复杂度。30 已知单链表 L 是一个递增有序表，试写一高效算法，删除表中值大于 min 且小于 max 的结点( 若表中有这样的结点) ，同时释放被删结点的空间，这里 min 和 max是两个给定的参数。30 线性表(a 1，a 2，a 3，a n)中元素递增有序且按顺序存储于计算机内。要求设计算法完成以下内容：31 用最少的时间在表中查找数值为 x 的元素。若找到将其与后继元素位置相交换。32 若找不到将其插入表中并使表中元素仍递增有序。33 设有一个双链表 L，每个结点中除有 prior、data 和 next 这 3 个域外，
11、还有一个访问频度域 freq，在链表被启用之前，其值均初始化为零。每当在链表进行一次LocateNode(L，x)运算时，令元素值为 x 的结点中 freq 域的值加 1，并调整表中结点的次序，使其按访问频度的递减排列，以便使频繁访问的结点总是靠近表头。试写一符合上述要求的 LocateNode 运算的算法。33 有一个不带头结点的单链表 list，链表中结点都有两个域：数据域 data 和指针域 link。已知初始时该单链表无序，请设计一个算法将该链表按结点数据域的值的大小，将其从小到大依次重新链接，在链接过程中不得使用除该链表以外的任何链结点空间。要求：34 给出算法的基本设计思想。35
12、根据设计思想，采用 C 或 C+或 Java 语言描述算法，关键之处给出注释。36 如果以单链表表示集合，设集合 A 用单链表 LA 表示，集合 B 用单链表 LB 表示，设计算法求两个集合的差，即 A-B。37 已知 3 个带头结点的线性链表 A、B、C 中的结点均依元素值自小至大非递减排列(可能存在两个以上值相同的结点)，编写算法对链表 A 进行如下操作：使操作后的链表 A 中仅留下 3 个表中均包含的数据元素的结点，且没有值相同的结点，并释放所有无用结点。限定算法的时间复杂度为 O(m+n+p)，其中 m、n 和 p 分别为 3 个表的长度。37 已知非空链表 A，其指针是 list，链
13、表中的结点由两部分组成：数据域 data 和指针域 link。设计一个算法，将链表中数据域值最小的那个链结点移到链表的最前面，在不额外申请新的链结点的情况下，使得算法时间复杂度和空间复杂度尽可能低。要求：38 给出算法的基本设计思想。39 根据设计思想，采用 C 或 C+或 Java 语言描述算法，关键之处给出注释。39 已知一个双向链表，其结点结构为数据域 data、左指针域 llink、右指针域rlink；设指针 P 指向双向链表中的某个结点。写出一个算法，实现 P 所指向的结点和它的前缀结点之间顺序的互换。要求：40 给出算法的基本设计思想。41 根据设计思想，采用 C 或 C+或 Ja
14、va 语言描述算法，关键之处给出注释。42 两个整数序列 A=a1，a 2，a 3，a n 和 B=b1，b 2，b 3，b n 已经存入两个单链表中，设计一个算法，判断序列 B 是否是序列 A 的子序列。42 已知一个带有头结点的单链表 L，其结点结构由两部分组成：数据域 data，指针域 link。设计一个算法，以最高效的方法实现在单链表中删除数据域最小值结点。要求：43 给出算法的基本设计思想。44 根据设计思想，采用 C 或 C+或 Java 语言描述算法，关键之处给出注释。45 设有集合 A 和集合 B，要求设计生成集合 C=AB 的算法，其中集合 A、集合B 和集合 C 用链式存储
15、结构表示。计算机专业基础综合（线性表）模拟试卷 1 答案与解析一、单项选择题1-40 小题，每小题 2 分，共 80 分。下列每题给出的四个选项中，只有一个选项是最符合题目要求的。1 【正确答案】 D【试题解析】 在链表中的最后一个结点之后插入一个结点要知道终端结点的地址，所以，单链表、带有头指针的单循环链表、双链表都不合适。考虑在带有尾指针的单循环链表中删除第一个结点，其时间性能是 O(1)，所以答案是 D。【知识模块】 线性表2 【正确答案】 D【试题解析】 在合并过程中，最坏的情况是两个链表中的元素依次进行比较，比较的次数最少是 m 和 n 中的最大值。【知识模块】 线性表3 【正确答案
16、】 C【试题解析】 线性表中主要存放的是数据元素，而数据元素可以是整型也可以是字符型，但对于一个线性表来说，所有的数据元素的类型必须相同。【知识模块】 线性表4 【正确答案】 A【试题解析】 在线性表链式存储结构中，查找第 i 个元素的时间与 i 的位置成正比。而在顺序存储结构中查找第 i 个元素的时间与 i 的位置无关。【知识模块】 线性表5 【正确答案】 A【试题解析】 线性表中要想最省时间地存取某一指定序号的元素，那么就要利用顺序表这种存储方式。但顺序表不利于插入和删除运算，可是题目中强调是在最后进行插入运算，因此，本题最合适的选项是顺序表。【知识模块】 线性表6 【正确答案】 D【试题
17、解析】 本题的考点是线性表的存储结构及其特点。在线性表中主要的存储结构有顺序表和链表两种，其特点如下：(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【试题解析】 对于 A，删除指定元素，在顺序表中需要移动较多元
19、素，而在单链表上执行同样的操作不需要移动元素，因此单链表的效率要高一些。对于 B，在最后一个元素的后面插入一个新元素不需要移动元素，顺序表的效率和单链表相同。对于 C，顺序输出前 k 个元素，单链表和顺序表的效率几乎相同。对于 D，交换第 i 个元素和第 2n-i-1 个元素的值(i=0，1，n-1) ，由于顺序表可以实现随机查找，因此顺序表的效率会更高一些。【知识模块】 线性表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 均不能构成非空的循环单链表。【知识模块】 线性表15 【正确答案】 A【试题解析】
21、 此题考查的知识点是双向链表的插入操作。在 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 小题，共 70 分。【知识模块】 线性表21 【正确答案】 算法的
23、基本设计思想：分别从 A、B 的头结点开始，依次比较A、B 中元素的内容，如果 A 中的元素值大于 B 中的元素值，则将 B 中的结点插入结果链表，反之将 A 中的结点插入结果链表。由于题目中要求将结果链表中的结点按元素值的大小依次递增地排列。因此，如果 A、B 中两个元素值相同，只将其中的一个加入结果链表。【知识模块】 线性表22 【正确答案】 算法的设计如下：typedef struct LNodeint data：struct LNode：lc next；*Linkedlist；LinkedList Union(IJnkedList la，lb)pa=la 一next；pb=lb 一ne
24、xt； 设工作指针 pa 和 pbpc=la； pc 为结果链表当前结点的前驱指针while(pa p 是链表的工作指针pre=list; pre 指向链表中数据域最小值结点的前驱q=P; q 指向数据域最小值结点，初始假定是第一结点while(p-link!=null)if(p 一link 一datadata)pre=P ；q=p-link； 找到新的最小值结点P=p-link；if(q!=list 一link) 若最小值是第一元素结点，则不需再操作pre 一link=q 一link；将最小值结点从链表上摘下q 一link=list 一link ； 将 q 结点插到链表最前面list 一li
25、nk=q；算法结束【知识模块】 线性表【知识模块】 线性表40 【正确答案】 算法的基本思想：已知双向循环链表中的一个结点 P，与前驱交换涉及 4 个结点(P 结点，前驱结点，前驱的前驱结点，后继结点 )、6 条链。【知识模块】 线性表41 【正确答案】 算法的设计如下：typedef struct DuLNodeint data；struct DuLNode*llink，*rlink：DuLNode*Linkedlist；void Exchange(LinkedList P) 将 P 所指结点与其前驱结点交换Linkedlist*q；q=p-llink；q 一llink 一rlink=P；
26、p 的前驱的前驱之后继为 Pp 一llink=q 一llink ； p 的前驱指向其前驱的前驱q 一rlink=p 一rlink； p 的前驱的后继为 P 的后继q 一llink=P； p 与其前驱交换P 一rlink 一llink=q ； p 的后继的前驱指向原 P 的前驱p 一rlink=q ； p 的后继指向其原来的前驱【知识模块】 线性表42 【正确答案】 typedef struct LNodeint data；struct LNode*next；*Linkedlist；int Pattern(LinkedList A，B)A 和 B 分别是数据域为整数的单链表，本算法判断链表 B
27、是否是链表 A 的子序列。如是，返回 1；否则，返回 0，表示失败。Linkedlist*P，*pre，*q ：p=A； p 为链表 A 的工作指针，本题假定链表 A 和链表 B 均无头结点pre=p； pre 记住每趟比较中链表 A 的开始结点q=B； q 是链表 B 的工作指针while(p p 为工作指针，指向待处理的结点。假定链表非空pre=L; pre 指向最小值结点的前驱q=P; q 指向最小值结点，初始假定第一元素结点是最小值结点while(p 一next !=null)if(P 一next 一datadata)f pre=P; q=P-next； 查最小值结点P=P 一next
28、; 指针后移pre 一next-q 一next； 从链表上删除最小值结点free(q)； 释放最小值结点空间结束算法 delete【知识模块】 线性表45 【正确答案】 typedef struct nodeint data；struct node*next；lklist；void intersection(1klist*ha，lklist*hb，lklist* 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=(1klist*)malloc(sizeof(lklist)；t-data=p-data；t 一next=hc ；hc=t ；【知识模块】 线性表
