1、线性表模拟试卷 1 及答案与解析一、单项选择题下列各题的备选答案中，只有一个是符合题意的。1 某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用( ) 存储方式最节省运算时间。（A）非循环的单链表（B）仅有头指针的单循环链表（C）非循环的双链表（D）仅有尾指针的单循环链表2 以下与数据的存储结构无关的术语是( )。（A）循环队列（B）链表（C）哈希表（D）栈3 一个栈的输入序列为 1，2，3，n若输出序列的第一个元素是 n，输出第i(1inext=NULL（C） head-next=head（D）head!=NULL22 将长度为 n 的单链表链接在长度为 m 的单
2、链表后面，其算法的时间复杂度采用大 O 形式表示应该是（ ）。（A）O(1)（B） O(n)（C） 0(m)（D）O(n+m)23 在一个单链表中，已知 q 所指结点是 P 所指结点的前驱结点，若在 q 和 P 之间插入结点 S，则执行（ ）。（A）s-next=p-next ；p-next=s；（B） P-next=s-next；s-next=p；（C） q-next=s；s-next=D；（D）P-next=s ；s-next=q；24 关于线性表的顺序存储结构和链式存储结构的描述正确的是（ ）。I,线性表的顺序存储结构优于其链式存储结构 II,链式存储结构比顺序存储结构能更方便地表示各种
3、逻辑结构 III,如频繁使用插入和删除结点操作，顺序存储结构更优于链式存储结构,顺序存储结构和链式存储结构都可以进行顺序存取（A）I、II、III（B） II、（C） II、III（D）III、25 下列关于线性表说法正确的是（ ）。I,需要分配较大的连续空间，插入和删除不需要移动元素的线性表，其存储结构为静态链表 II,在一个具有 n 个结点的有序单链表中插入一个新结点并仍然保持有序的时间复杂度是 O(n)III，若用单链表来表示队列，则应该选用带尾指针的循环链表（A）I（B） II（C） I、II（D）I、II、III26 带头结点的双循环链表 L 为空的条件是（ ）。（A）L-prior
4、=L&L-next=NULL（B） L-prior=NULL&L-next=NULL（C） L-prior=NULL&L-next=L（D）L-prior=L&L-nex=L27 在双链表中向 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-next；（C） q-next=p；p-next=q；q-prior-next=-q；q-next-=p ；（D）p-prior-ne
5、xt=q； q-next=p；q-prior-=p-prior；p-prior=q；28 在双向链表存储结构中，删除 P 所指的结点时必须修改指针（ ）。（A）p-llink-rlink=p-rlink；p-rlink-llink=p-llink ；（B） p-llink=p-llink-llink；p-llink-rlink=p ；（C） p-rlink-llink=p；p-rlink=p-rlink-rlink ；（D）p-rlink=p-llink-llink；p-llink=p-rlink-rlink；29 某线性表中最常见的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用
6、（ ）存储方式最省时间。（A）单链表（B）仅有头指针的单循环链表（C）双链表（D）仅有尾指针的单循环链表30 一个链表最常用的操作是在末尾插入结点和删除结点，则选用（ ）最节省时间。（A）带头结点的双循环链表（B）单循环链表（C）带尾指针的单循环链表（D）单链表31 静态链表中指针表示的是（ ）。（A）下一元素的地址（B）内存储器地：吐（C）下一个元素在数组中的位置（D）左链或右链指向的元素的地址32 长度为 n 的线性表采用顺序存储结构，则访问第 i 个位置处元素的时间复杂度为（ ）；如果将存储结构改为链式结构，则时间复杂度为（ ）。（A）O(1)（B） O(n)（C） O(n2)（D）O(
7、nlog 2n)33 若长度为 n 的线性表采用顺序存储结构，在其第 i 个位置插入一个新元素的算法时间复杂度为（ ），如果将存储结构改为链式存储结构，则时间复杂度为（ ）(1in+1)。（A）O(1)（B） O(n)（C） O(n2)（D）O(nlog 2n)34 在一个长度为 n 的带头结点的单链表 h 上，设有尾指针 r，则执行（ ）操作与链表的表长有关。（A）删除单链表中的第一个元素（B）删除单链表中最后一个元素（C）在单链表第一个元素前插入一个新元素（D）在单链表最后一个元素后插入一个新元素35 下面关于线性表的一些说法中正确的是（ ）。（A）对一个设有头指针和尾指针的单链表执行删除
8、最后一个元素的操作与链表长度无关（B）线性表中每个元素都有一个直接前趋和一个直接后继（C）为了方便插入和删除数据，可以使用双链表存放数据（D）取线性表第 i 个元素的时间同 i 的大小有关36 对于一个线性表既要求能够进行较快速地插入和删除，又要求存储结构能反映数据之间的逻辑关系，则应该用（ ）。（A）顺序存储方式（B）链式存储方式（C）散列存储方式（D）以上均可以37 给定有 n 个元素的一维数组，建立一个有序单链表的最少时间复杂度是（ ）。（A）O(1)（B） O(n)（C） O(n2)（D）O(nlog 2n)38 设线性表中有 2n 个元素，（ ）在单链表上实现要比在顺序表上实现效率更
9、高。（A）删除所有值为 x 的元素（B）在最后一个元素的后面插入一个新元素（C）顺序输出前 k 个元素（D）交换第 i 个元素和第 2n-i-1 个元素的值(i=0 ，n-1)二、综合题39 编写一个算法，输出二叉树中距给定结点最近的叶子子孙(可以是给定结点的孩子)。注：二叉树用二叉链表示。40 编写克鲁斯卡尔算法求无向连通网的最小生成树，并分析你所编写的算法的时间和空间复杂度。 41 分析下述算法功能Status A(BiThrTree T，Status(*Visit)(TglemType e)p-T-lchild；while(p!-T)while(p-LTag=Link)p=p-lChil
10、d；if(!Visit(pdata)return ERRoR；while(p-RTag-=Thread&p-rchild!=T)p=p-rchild；Visit(pdata)；p=p-rchild；return OK；42 编写在链式存储结构的队列中删除元素的算法。43 设增量序列为 5、3、1，初始关键字序列为51、12、55、23、49、7、60、36、72、12，写出希尔排序过程及每趟排序结果。线性表模拟试卷 1 答案与解析一、单项选择题下列各题的备选答案中，只有一个是符合题意的。1 【正确答案】 D【知识模块】 线性表2 【正确答案】 D【知识模块】 线性表3 【正确答案】 B【知识模
11、块】 线性表4 【正确答案】 C【知识模块】 线性表5 【正确答案】 B【知识模块】 线性表6 【正确答案】 B【知识模块】 线性表7 【正确答案】 C【试题解析】 线性表是由数据元素组成的，数据元素是由数据项组成的。【知识模块】 线性表8 【正确答案】 B【试题解析】 线性表的定义中要求为有限序列，而 C 中序列中的元素个数是无穷多个，因此 C 错误；而 A 中指定的是集合(集合中各元素没有前后驱关系)，因此A 也错误；D 是属于存储结构，线性表是一种逻辑结构。不要把二者混淆起来。只有 B 满足线性表定义的条件。【知识模块】 线性表9 【正确答案】 A【知识模块】 线性表10 【正确答案】
12、B【试题解析】 对于同一类型的顺序表，表越长，则所占存储空间就越大。元素的类型显然会影响到存储空间的大小。【知识模块】 线性表11 【正确答案】 C【试题解析】 数组指针实际上已经隐含有数组基址了，所以 IV 是多余的。【知识模块】 线性表12 【正确答案】 C【知识模块】 线性表13 【正确答案】 C【试题解析】 由于是顺序表，逻辑地址与物理地址是一一对应的，满足线性关系，所以，访问第 i 个位置的物理地址可以直接计算出来，即在 O(1)内可以访问。在第i 个位置插入一个元素，需要移动 n-i+1 个元素，故时间复杂度为 O(n)。【知识模块】 线性表14 【正确答案】 C【试题解析】 需要
13、将 ai+1a n 元素前移一位，共移动 n-(i+1)+1=n-i 个元素。【知识模块】 线性表15 【正确答案】 A【试题解析】 本题容易误选 B。顺序表是一种支持随机存取的顺序存储结构。注意区分随机存取和顺序存储是两个完全不同的概念，数组采用顺序存储方式存储，因此，根据基地址加上元素的序号，可以很方便地访问到任一元素，即随机存取的概念。【知识模块】 线性表16 【正确答案】 A【试题解析】 由于顺序表具有随机存取特性，所以，和链表相比输出第 i 个元素时效率很高。【知识模块】 线性表17 【正确答案】 D【试题解析】 题干实际要求能够最快存取第 i-1 个、第 i 个和第 i+1 个结点
14、的数据元素值。A、B、C 都只能从头结点顺序依次查找，时间复杂度为 O(n)，只有顺序表可以直接存取，时间复杂度为 O(1)。【知识模块】 线性表18 【正确答案】 C【试题解析】 顺序输出这 n 个元素的值，都要依次访问每个结点，故时间复杂度相同。【知识模块】 线性表19 【正确答案】 A【试题解析】 只有顺序表具有随机存取的功能，且在最后进行插入和删除操作不需要移动元素。【知识模块】 线性表20 【正确答案】 C【试题解析】 单链表设置头结点的目的是为了方便运算的实现，主要好处体现在：第一，有头结点后，插入和删除数据元素的算法统一了，不再需要判断是否在第一个元素之前插入或删除第一个元素；第
15、二，不论链表是否为空，链表指针不变。【知识模块】 线性表21 【正确答案】 B【试题解析】 在带头结点的单链表中，head 指向头结点，由头结点的 next 域指向第 1 个元素结点，head-next=NULL 表示该单链表为空。在不带头结点的单链表中，head 直接指向第 1 个元素结点，head=NuLL 表示该单链表为空。【知识模块】 线性表22 【正确答案】 C【试题解析】 先在长度为 m 的单链表中找到尾结点，然后将其 next 域置为另一个单链表的首结点，其时间复杂度为 O(m)。【知识模块】 线性表23 【正确答案】 C【试题解析】 s 插入后，q 成为 s 的前驱，而 p 成
16、为 s 的后继，选项 C 满足此条件。【知识模块】 线性表24 【正确答案】 B【试题解析】 两种存储结构有不同的适用场合，不能简单地说谁好谁坏，故 I 错误。链式存储用指针表示逻辑结构，而指针的设置是任意的，故可以很方便地表示各种逻辑结构，而顺序存储则只能用物理上的邻接关系来表示逻辑结构。在顺序存储中，插入和删除结点需要大量的移动元素，故效率较低，I 错误。顺序存储结构既可以随机存取也能顺序存取，而链式结构只能进行顺序存取。【知识模块】 线性表25 【正确答案】 D【试题解析】 I 不解释。II 中，单链表只能顺序查找插入位置，时间复杂度为O(n)，若为顺序表，可采用折半查找，时间复杂度可降
17、至 O(log2n)。III 中，因为队列需要在表头删除元素，表尾插入元素，故采用带尾指针的循环单链表比较方便，插入和删除的时间复杂度都是 O(1)。【知识模块】 线性表26 【正确答案】 D【试题解析】 循环单链表 L 为空的条件是头指针的 prior 和 next 指针都指向它自身。【知识模块】 线性表27 【正确答案】 D【试题解析】 为了向 p 之前插入结点 q，可以将 p 的前一个结点的 next 指针域指向 q，而将 q 的 prior 指针域指向 p 的前一个结点；q 的 next 指针域指向 p，p的 priol 指针域指向 q。只有 D 满足条件。【知识模块】 线性表28 【
18、正确答案】 A【试题解析】 与上一题的分析基本类似，只不过这里是删除一个结点，注意将 p的前、后两结点链接起来。【知识模块】 线性表29 【正确答案】 D【试题解析】 在最后一个元素后面插入元素，需要知道最后一个元素的指针，故A 和 C 的时间复杂度为 O(n)。B 因为没有特殊的指针指示头结点或尾结点，故需从某一结点向固定的方向顺序依次搜索插入和删除的位置，时间复杂度也为 O(n)。【知识模块】 线性表30 【正确答案】 A【试题解析】 在链表的末尾插入和删除一个结点时，需要修改其相邻结点的指针域。当我们从链表的第一个结点(由头指针指向)开始寻找尾结点以及尾结点的前驱结点时，只有带头结点的双
19、循环链表所要经过的结点最少。【知识模块】 线性表31 【正确答案】 C【试题解析】 静态链表中的指针又称游标，指示下一个元素在数组中的下标。【知识模块】 线性表32 【正确答案】 A【试题解析】 ，B 顺序存储支持随机存取，因此访问第 i 个位置元素的时间复杂度为 O(1)。链式存储只能顺序存取，时间复杂度为 O(n)。【知识模块】 线性表33 【正确答案】 B【试题解析】 ，B 顺序存储时虽然可以随机存取，但是在第 i 个位置插入元素需要移动 n-i+1 个元素，故时间性能为 O(n)。链式存储时虽然不需要移动元素，但是查找第 i 个位置需要的时间性能为 O(n)。【知识模块】 线性表34
20、【正确答案】 B【试题解析】 删除单链表的最后一个结点需要置其前驱结点的指针域为 NuLL，故需要的时间为 O(n)，与表长有关。其他操作均与表长无关，读者可以自行模拟。【知识模块】 线性表35 【正确答案】 C【试题解析】 双链表能很方便地访问前驱和后继，故删除和插入数据较为方便。A 显然错误。B 表中第一个元素和最后一个元素不满足题设要求。 D 未考虑顺序存储的情况。【知识模块】 线性表36 【正确答案】 B【试题解析】 要求较快速地插入和删除，排除 A、D ，要求存储结构反映数据之间的逻辑关系，排除 C。链式存储中的静态链表满足这一要求。【知识模块】 线性表37 【正确答案】 D【试题解
21、析】 若先建立链表，然后依次直接插入建立有序表，则每插入一个元素就需遍历链表寻找插入位置，此即链表插入排序，时间复杂度为 O(n2)。若先将数组排序，然后建立链表，建立链表的时间复杂度为 O(n)，而数组排序的最少时间复杂度为 0(nlog2n)，故时间复杂度为 O(nlog2n)。本题问最少时间复杂度，故选D。【知识模块】 线性表38 【正确答案】 A【试题解析】 A 中对于单链表和顺序表上实现的时间复杂度都为 O(n)，但后者要移动很多元素，所以在单链表上实现效率更高。B 和 D 效率刚好相反，C 无区别。【知识模块】 线性表二、综合题39 【正确答案】 /二叉树层次遍历算法#includ
22、e#include#define MaxSize 1 000typedef char ElemType；typedef struct nodeElemType data；struct node*lchild：struct node*rchild；BTNode；/使用队列来存储数据，进行层次遍历算法Node*LevelOrder(BTNode*b)BTNode*P：BTNode*quMaxSize；int front。rear；front=rear=-1：rear+4-；qurear=b：while(front!=rear)front=(front+1)MaxSize；p=qufront；pri
23、ntf(“c“，pdata)；if(p-lchild!=NULL)rear 一(rear+1) MaxSize；qu rear=p-1child；jf(prchild!=NULL)rear=(rear+1)MaxSize；qu rear=p-rchild；jf(p-lchild!=NULL&P-rchild!=NULL)return P；return NULL；【知识模块】 线性表40 【正确答案】 #include#define MAX VERTEX NUM 10#define 1NFINITY 1000typedef st ruet Edgeint weight；Edge，EdgeMatr
24、ixMAX VERTEX NUMMAX VERTEX NUM；typedef struct MGraphEdgeMatrix edges；int vexnum；int edgenum；MGraph；typedef struct VexGroupint vertex；int group； VexGroup；typedef struct EdgeMusterint tail；int head；int weight；bool used；EdgeMuster；*对图进行初始化*void InitializeMG(MGraph&G)Gedgenum=Gvexnum=0；for(int i=0； it t
25、dn” ，Ektail，Ekhead，E Ekweight) ；void main()MGraph G：InitializeMG(G)；CreateGraph(G)：MiniSpanTreeKruskal(G)；时间、空间复杂度分析：排序的代价、检查边所关联的两个顶点是否在同一集合中以及集合合并的代价。【知识模块】 线性表41 【正确答案】 采用二叉链表存储结构，Visit 是对数据元素操作的应用函数，先序遍历线索二叉树的递归算法，对每个数据元素调用函数 Visit。【知识模块】 线性表42 【正确答案】 在链式队列中删除元素，即为用链式队列的存储结构进行出队操作。LinkQueue DeQu
26、eue(LinkQueue Q，QueueElementType*e)QueueNode*P；if(QueueEmpty(Q)printf(“队列为空，出队操作失败!n”)；elsep=Qfront-next；*e=p-dataQfront-next=p-next；if(Qrear=p)Qrear=Qfront ；free(P)；return Q；【知识模块】 线性表43 【正确答案】 当增量为 5、3、1 时，对51、12、55、23、49、7、60、36、72、12 的希尔排序的结果为：第一趟 d=5 排序后 7、12、36、23、12、51、60、55、72、49；第二趟 d=3 排序后 7、12、36、23、12、51、49、55、72、60；第三趟 d=1 排序后 7、12、12、23、36、49、51、55、60、72。【知识模块】 线性表
