考研计算机－习题精炼和重点回顾 线性表

考研计算机－习题精炼和重点回顾 线性表内容摘要：

考研计算机－习题精炼和重点回顾 线性表 以为空 能为空 以为空 以为空 正确答案是：【A】解析：线性表的定义如下：线性表是具有 n（n0）个元素的一个有限序列，当 n=0时称为空表。 2在 n 个结点的顺序表，算法的时间复杂度是 O(1)的操作是 i 个结点(1in)和求第 i 个结点的直接前驱(2in) i 个结点后插入一个新结点(1in) i 个结点(1in) x 相等的元素 正确答案是：【A】解析：顺序表可以按元素下标直接存和直接取，其时间复杂度为 O(1)。 在第 i 个元素后面插入新元素和删除第 i 个元素的时间复杂度都是 O(n)，顺序查找的时间复杂度也是 O(n)。 3若长度为 n 的线性表采用顺序存储结构，在表的第 i 个位置插入一个数据元素，需要移动表中数据元素的数目为 B.n+i 正确答案是：【C 】解析：在线性表的第 i 个位置插入一个新的数据元素之前，需要先将线性表的第 i 个数据元素至第 n 个数据元素依次后移 1 个位置，一共需要移动 个数据元素。 4将两个各有 元素的有序表（递增）归并成一个有序表，仍保持其递增顺序，则最少的比较次数是 A. B. C. D. 正确答案是：【C 】解析：由于将长度为 n 的单链表链接在长度为 m 的单链表之后的操作，需要把长度为m 的单链表遍历一遍，找到最后的一个结点，所以时间复杂度为 O（m）。 5已知 L 是带头结点的单链表，结点 p 既不是第一个结点，也不是最后一个结点，删除 p 结点的直接后继结点的语句序列是 A.p=pB.pp C.ppD.p=p正确答案是：【C 】解析：选项 A 是删除了当前 p 结点；选项 B 是把 p 结点之后的所有结点都丢失了，同时在 p 结点本身形成了一个环；选项 C 正确；选项 D 是把 p 和 p 的后继结点都删除了。 6设双向循环链表中结点的结构为（，且不带表头结点。 若想在指针 p 所指结点之后插入指针 s 所指结点，则应执行下列哪一个操作 A.ps； sp； ps； sp B.ps； ps； sp ； sp C.sp； sp ps； ps； D.sp ； spps； ps； 正确答案是：【D】解析：本题主要考查如何在双向链表中插入一个结点，指针操作的顺序不是唯一的，但也不是任意的。 根据双向链表的结构特点可以知道，选项 D 所提供的操作顺序是正确的，具体过程如下图所示。 7以下关于采用链式存储结构的线性表叙述中，不正确的是 此存储密度小于顺序存储结构 i 个结点的存储地址 除运算操作方便，不必移动结点 正确答案是：【C 】解析：选项 C 错误的原因是链式存储结构的地址不一定是连续的，所以不能通过计算直接确定第 i 个结点的存储地址。 8某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用下列存储方式最节省运算时间的是 正确答案是：【D】解析：本题显然应在选项 B 和选项 D 中选择正确答案，考虑到需要在最后一个元素之后插入和删除第一个元素，所以最好可以直接得到链表尾指针。 如果只有头指针，必须遍历所有链表才能得到尾指针。 9若要在 O(1)的时间复杂度上实现两个循环单链表头尾相接，则对应两个循环单链表个设置一个指针，分别指向 一个表的尾结点 正确答案是：【B】解析：实现这样的操作需要能方便地找到两个循环单链表的尾结点，因此设置指向两个循环单链表的尾结点指针 现合并的过程如下图所示。 10静态链表的类型定义如下：；S 是表示静态链表的数组，若第 k 个结点的下标是 i，则第 k+1 个结点的数据是 A.Si+1B.Sk+1ik正确答案是：【C 】解析：在静态链表中，第 k 个结点是 Si，其下一个结点（即第 k+1 个结点）的下标是 Sk此第 k+1 个结点是 SSk其包含的数据是 SSk1设一个一元多项式 A 和 B 的项数分别为 m 和 n，均采用单链表表示，则进行A+B 运算时最好情况下的时间复杂度为 A.O(m)（当 m>n） B.O(n)（当 m C.O(m+n) D.O(m×n) 正确答案是：【C 】解析：当两个多项式单链表以指数有序排列时，实现相加运算时所花时间最少，为O(m+n)12线性表（a1，a2， ，采用顺序存储，每个元素都是整数，试设计算法用最少时间把所有值为负数的元素移到全部正数值元素前边的算法。 要求：（1）采用 C 或 C+或 言描述算法，关键之处给出注释。 （2）说明你所设计算法的时间复杂度和空间复杂度。 参考答案是：题目中要求重排以顺序存储结构存储的线性表的 n 个元素，使得所有值为负数的元素移到正数元素的前面。 可采用快速排序的思想来实现，只是提出暂存的第一个元素（枢轴）并不作为以后的比较标准，比较的标准是元素是否为负数。 【解答】（1）用 C 语言算法描述如下：a, n) i=0, j= i,j 为工作指针（下标），初始指向线性表 a 的第 1 个和第 t=a0; 暂存枢轴元素。 i=0) 若当前元素为大于等于零，则指针前移if(& 假定链表非空，p 为工作指针，指向待处理的结点。 ； 向最小值结点的前驱q=p； q 指向最小值结点，初始假定第一元素结点是最小值结点p->if（p-> 查最小值结点p；q=p-> p=p-> 指针后移q->从链表上删除最小值结点q； 释放最小值结点空间 解析：无15设计一个在时间和空间上尽可能高效的算法，将带有头结点的非空单链表中数据域值最小的那个结点移到链表的最前面。 要求：（1）给出算法的基本设计思想。 （2）根据设计思想，采用 C 或 C+或 言描述算法，关键之处给出注释 ； 参考答案是：【解答】（1）算法的基本设计思想：本题要求将链表中数据域值最小的结点移到链表的最前面。 首先要查找最小值结点，将其移到链表最前面，实质上是将该结点从链表上摘下（不是删除并回收空间），在插入到链表的最前面。 （2）用 C 语言算法描述如下：L)p=L->*; /向链表中数据域最小值结点的前驱q=p; /q 指向数据域最小值结点，初始假定是第一结点p->if(p-> /找到新的最小值结点p; q=p->p=p->if(q!=L-> /若最小值是第一元素结点，则不需再操作q->>->>q; 解析：无16编写一个算法，设有两个无头结点的单链表,头指针分别为 ha,个链表的数据都按递增序存放。 现要求将 归到 中,且归并后 递增序, 在归并中对于 中已有的数据若 也有, 则 的这部分数据不归并到 ,链表在算法中不允许破坏。 参考答案是：【分析】本题与“将两个按元素值递增次序排列的线性表，归并为一个按元素值非递增次序排列的单链表”问题类似，不同之处在于：一是链表无头结点，为处理方便，给加上头结点，处理结束再删除之；二是数据相同的结点，不合并到结果链表中；三是 表不能被破坏，即将 结点合并到结果链表时，要生成新结点。 【解答】用 C 语言算法描述如下：la;申请头结点以便操作pa= 表的工作指针pb= 表的工作指针向当前待合并结点的前驱pb) 处理 数据pa;pa;pa= 处理 数据。 r=(; 申请空间r->r;r; 将新结点链入结果链表pb=表中工作指针后移处理 pa;pa=两结点数据相等时，只将 数据链入pb=不要 相等数据将两链表中剩余部分链入结果链表pb;释放头结点， ha、针未被破坏 解析：无17已知不带头结点的线性链表 写一算法，将该链表按结点数据域的值的大小从小到大重新链接。 要求链接过程中不得使用除该链表以外的任何链结点空间。 参考答案是：【分析】本题实质上是一个排序问题，要求“不得使用除该链表结点以外的任何链结点空间”。 链表上的排序采用直接插入排序比较方便，即首先假定第一个结点有序，然后，从第二个结点开始，依次插入到前面有序链表中，最终达到整个链表有序。 【解答】用 C 语言算法描述如下：*p= p 是工作指针，指向待排序的当前元素假定第。