2022年数据结构线性表试题 .pdf

《2022年数据结构线性表试题 .pdf》由会员分享，可在线阅读，更多相关《2022年数据结构线性表试题 .pdf（10页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数据结构线性表试题 .txt我自横刀向天笑，笑完我就去睡觉。你的手机比话费还便宜。路漫漫其修远兮，不如我们打的吧。第2 章线性表 2.1 选择题1对于线性表最常用的操作是查找指定序号的元素和在末尾插入元素，则选择 （）最节省时间A）顺序表 B）带头结点的双循环链表C）单链表 D）带尾结点的单循环链表【答案】 A 2 若长度为n 的线性表采用顺序存储结构，在其第 i 个位置插入一个新元素的算法时间复杂度为（）(1 i n+1) 。A） O(0) B） O(1) C） O(n) D） O(n2) 【答案】 C 3双向链表中有两个指针域，prior和 next ，分别指向前驱及后继，设 p 指向链表

2、中的一个结点， q 指向一待插入结点，现要求在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; p-prior-next=q; q-next=p; D） p-prior-next=q; q-next=p; q-prior=p-prior; p-prior=q; 【答案】 D 4 在一个具有n 个结点的有序单链表中插入一个新结点并仍

3、然保持有序的时间复杂度是（ ）A）O(nlog2n ） B ） O(1 ） C） O(n ） D） O(n2 ）【答案】 C 5 在一个以 h 为头指针的单循环链中，p 指针指向链尾结点的条件是（）A）p-next=NULL B） p-next=h C）p-next-next=h D） p-data=-1 【答案】 B 6对于一个具有n 个结点的线性表，建立其单链表的时间复杂度是（） A）O(n) B） O(1) C）O(nlog2n) D） O(n2) 【答案】 A 8在双向链表存储结构中，删除p 所指的结点时须修改指针（）A）p-prior-next=p-next p-next-prior

4、=p-prior; B）p-prior=p-prior-prior p-prior-next=p; C）p-next-prior=p p-next=p-next-next D）p-next=p-prior-prior p-prior=p-next-next; 【答案】 A 9线性表采用链式存储时，其元素地址（）A）必须是连续的 B）一定是不连续的C）部分地址是连续的 D）连续与否均可【答案】 D 2.2 填空题名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 10 页 -

5、- - - - - - - - 1线性表L=（a1，a2， an）用数组表示，假定删除表中任一元素的概率相同，则删除一个元素平均需要移动元素的个数是_。【答案】（n-1 ）/2 2在单链表中设置头结点的作用是_。【答案】主要是使插入和删除等操作统一，在第一个元素之前插入元素和删除第一个结点不必另作判断。另外，不论链表是否为空，链表头指针不变。3线性表的顺序存储是通过_来反应元素之间的逻辑关系，而链式存储结构是通过 _来反应元素之间的逻辑关系。【答案】（1）数据元素的前后顺序（2）元素中的指针4当对 一个 线性表 经常进 行的 是存取 操作， 而很少 进行 插入和 删除操 作时 ，则采用_ 存

6、储 结 构 最 节 省 时 间 ， 相 反 当 经 常 进 行 插 入 和 删 除 操 作 时 ， 则 采 用_存储结构最节省时间。【答案】（1）顺序（2）链式5对于一个具有n 个结点的单链表，在已知的结点*p后插入一个新结点的时间复杂度为_，在给定值为x 的结点后插入一个新结点的时间复杂度为_。【答案】（1）O(1) （2）O(n) 7. 对于双向链表，在两个结点之间插入一个新结点需修改的指针共_个，单链表为 _个。【答案】（1）4 （2） 2 8. 循环单链表的最大优点是_。【答案】从任一结点出发都可访问到链表中每一个元素。9若要在一个不带头结点的单链表的首结点*p 结点之前插入一个*s

7、结点时，可执行下列操作： s-next=_; p-next=s; t=p-data; p-data= _; s-data=_; 【答案】（1）p-next （2）s-data （3） t 10某线性表采用顺序存储结构，每个元素占据4 个存储单元，首地址为100，则下标为11的（第 12 个）元素的存储地址为_。【答案】 144 11带头结点的双循环链表L 中只有一个元素结点的条件是_。【答案】 L-next-next=L 2.3 判断题1取线性表的第i 个元素的时间同i 的大小有关（）【答案】2线性表的特点是每个元素都有一个前驱和一个后继（）【答案】3 顺序存储方式的优点是存储密度大，且插入、

8、删除运算效率高（）【答案】4线性表采用链表存储时，结点的存储空间可以是不连续的（）名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 10 页 - - - - - - - - - 【答案】5链表是采用链式存储结构的线性表，进行插入、 删除操作时， 在链表中比在顺序存储结构中效率高（）【答案】6顺序存储方式只能用于存储线性结构（）【答案】【解析】线性结构、树型结构和图状结构均可用顺序存储表示。9顺序存储结构的主要缺点是不利于插入或删除操作（）【答案】10顺序存储方式插入和删除时

9、效率太低，因此它不如链式存储方式好（）【答案】2.4 程序设计题1设顺序表va 中的数据元素递增有序。试设计一个算法，将 x 插入到顺序表的适当位置上，以保持该表的有序性。【算法源代码】void Insert_SqList(SqList va,int x)/*把 x 插入递增有序表va 中*/ int i; if(va.length MAXSIZE) return; for(i=va.length-1;va.elemx&i=0;i-) va.elemi+1=va.elem; va.elemi+1=x; va.length+; /*Insert_SqList*/ 2设 A=（a1，a2， am

10、） 和 B=（b1，b2， bn）均为顺序表，试设计一个比较A ，B大小的算法（请注意：在算法中，不要破坏原表A和 B） 。【算法分析】 比较顺序表A和 B， 并用返回值表示结果，值为 1， 表示 AB； 值为 -1 ， 表示 AB ；值为 0，表示 A=B。1）当两个顺序表可以互相比较时，若对应元素不等，则返回值为1 或-1 ；2）当两个顺序表可以互相比较的部分完全相同时，若表长也相同，则返回值为0；否则，哪个较长，哪个就较大【算法源代码】int ListComp(SqList A,SqList B) for(i=1;i=A.length&iB.elem?1:-1; if(A.length=

11、B.length) return 0; return A.lengthB.length?1:-1; /*当两个顺序表可以互相比较的部分完全相同时，哪个较长，哪个就较大 */ /*ListComp */ 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 10 页 - - - - - - - - - 3已知指针 ha 和 hb 分别指向两个单链表的头结点，并且已知两个链表的长度分别为m和n。 试设计一个算法将这两个链表连接在一起（即令其中一个表的首元结点连在另一个表的最后一个结

12、点之后） ，假设指针hc 指向连接后的链表的头结点，并要求算法以尽可能短的时间完成连接运算。【算法分析】1）单链表ha 的头结点作为连接后的链表的头结点，即hc=ha；2）查找单链表ha 的最后一个结点，由指针p 指向，即p-next=NULL ；3）将单链表hb 的首元结点（非头结点）连接在p 之后，即p-next=hb-next；4）回收单链表hb 的头结点空间【算法源代码】void ListConcat(LinkList ha,LinkList hb,LinkList *hc)/*把链表 hb 接在 ha 后面形成链表 hc*/ *hc=ha; p=ha;/*由指针 p 指向 ha 的尾

13、元结点 */ p=p-next; p-next=hb-next; free(hb); /*ListConcat */ 4试设计一个算法，在无头结点的动态单链表上实现线性表操作INSERT （L，i ，b） ，并和在带头结点的动态单链表上实现相同操作的算法进行比较。【算法分析】1）生成新结点存放元素b，由指针new指向；2）将 new 插入在单链表的第i 个元素的位置上：若i=1 ，new 插在链表首部；否则查找第i-1个结点，由指针p 指向，然后将new插在 p 之后。【算法源代码】void Insert(LinkList *L,int i,int b) LinkList new; new=(

14、LinkList*)malloc(sizeof(LNode); new-data=b; if(i=1) /*插入在链表头部*/ New-next=*L; *L=new; else /*插入在第i 个元素的位置 */ p=*L; while(-i1) p=p-next; new-next=p-next; p-next=new; /*Insert */ 5 已知线性表中的元素以值递增有序排列，并以单链表作存储结构。试设计一个高效的算法，删除表中所有值大于 mink且小于 maxk 的元素（若表中存在这样的元素），同时释放被删结点空间（注意：mink 和 maxk 是给定的两个参变量。它们的值可以和

15、表中的元素相同，也可以不同）。【算法分析】1）查找最后一个不大于mink 的元素结点，由指针p 指向；2）如果还有比mink 更大的元素，查找第一个不小于maxk的元素，由指针q 指向；3）p-next=q ，即删除表中所有值大于 mink 且小于 maxk 的元素。【算法源代码】void Delete_Between(LinkList *L,int mink,int maxk) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 10 页 - - - - - - - - -

16、 p=*L; while(p-next-datanext; /*p是最后一个不大于mink 的元素 */ if(p-next) /*如果还有比mink 更大的元素 */ q=p-next; while(q-datanext; /*q是第一个不小于maxk 的元素 */ p-next=q; /*Delete_Between */ 6 已知线性表中的元素以值递增有序排列，并以单链表作存储结构。试设计一个高效的算法，删除表中所有值相同的多余元素（使得操作后的线性表中所有元素的值均不相同）， 同时释放被删结点空间。【算法分析】1）初始化指针p 和 q，分别指向链表中相邻的两个元素；2）当 p-next

17、不为空时，做如下处理：若相邻两元素不相等时，p 和 q 都向后推一步；否则，当相邻元素相等时，删除多余元素。【算法源代码】void Delete_Equal(LinkList *L) p=(*L)-next;q=p-next; /*p和 q 指向相邻的两个元素*/ while(p-next) if(p-data!=q-data) /*若相邻两元素不相等时，p 和 q 都向后推一步*/ p=p-next; q=p-next; else while(q-data=p-data) /*当相邻元素相等时删除多余元素*/ r=q; q=q-next; free(r); p-next=q;p=q;q=p-

18、next; /*else*/ /*while*/ /*Delete_Equal */ 7试设计一个算法，对带头结点的单链表实现就地逆置。【算法分析】1）空表或长度为1 的表，不做任何处理；2）表长大于2 时，做如下处理：首先将整个链表一分为二，即从链表的第一元素结点处断开；逐个地把剩余链表的当前元素q 插入到链表的头部。【算法源代码】void LinkList_reverse(LinkList L) if(!L-next|!L-next-next) return; p=L-next; q=p-next; s=q-next; p-next=NULL; /*从链表的第一元素结点处断名师资料总结 -

19、 - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 10 页 - - - - - - - - - 开*/ while(s-next) q-next=p;p=q; q=s;s=s-next; /*把 L 的元素逐个插入新表表头*/ q-next=p; s-next=q;L-next=s; /*LinkList_reverse*/ 8设线性表A=（a1，a2， am ） 和 B=（ b1，b2， bn） ，试设计一个按下列规则合并A，B为线性表C的算法，即使得 C=（ a1，b1， am ，bm

20、 ，bm+1 ， bn ）当 m n 时；或者 C=（ a1，b1， an，bn，an+1 ， am ）当 m n 时。线性表 A， B和 C 均以单链表作存储结构，且C 表利用 A 表和 B表中的结点空间构成。注意：单链表的长度值m和 n 均未显式存储。【算法分析】1）初始化指针p 指向链表 A 的当前元素，指针q 指向链表B的当前元素；2）当链表A和 B 均为结束时，做如下处理：将 B的元素插入若 A非空，将A的元素插入指针 p 和 q 同时后移【算法源代码】void merge1(LinkList A,LinkList B,LinkList *C) p=A-next; q=B-next;

21、 *C=A; while(p&q) s=p-next; p-next=q; /*将 B 的元素插入 */ if (s) t=q-next; q-next=s; /* 若 A非空，将A的元素插入 */ p=s; q=t; /*指针 p 和 q 同时后移 */ /*while*/ /*merge1 */ 9假设有两个按元素值递增有序排列的线性表A和 B，均以单链表作存储结构，请设计一个算法将 A 表和 B 表归并成一个按元素值递减有序（即非递增有序，允许表中含有值相同的元素）排列的线性表C，并要求利用原表（即 A 表和 B表）的结点空间构造C 表。【算法分析】 按从小到大的顺序依次把A和 B 的元

22、素插入新表的头部pc 处，最后处理A或 B的剩余元素。【算法源代码】void reverse_merge(LinkList A,LinkList B,LinkList *C) LinkList pa,pb,pre; pa=A-next;pb=B-next; /*pa和 pb 分别指向 A和 B的当前元素 */ pre=NULL; while(pa|pb) if(pa-datadata|!pb) /*将 A 的元素插入新表*/ pc=pa;q=pa-next;pa-next=pre;pa=q; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - -

23、- - - 名师精心整理 - - - - - - - 第 6 页，共 10 页 - - - - - - - - - else /*将 B的元素插入新表*/ pc=pb;q=pb-next;pb-next=pre;pb=q; pre=pc; *C=A; A-next=pc; /*构造新表头 */ /*reverse_merge*/ 10已知A，B 和 C 为三个递增有序的线性表，现要求对A 表作如下操作：删去那些既在B表中出现又在C 表中出现的元素。试对顺序表编写实现上述操作的算法，并分析你的算法的时间复杂度（注意：题中没有特别指明同一表中的元素值各不相同）。【算法分析】先从B和 C中找出共有元

24、素，记为same，再在 A中从当前位置开始，凡小于same的元素均保留( 存到新的位置 ) ， 等于 same的就跳过，到大于 same时就再找下一个same 。【算法源代码】void SqList_Intersect_Delete(SqList *A,SqList B,SqList C) i=0; j=0; k=0; m=0; /*i指示 A 中元素原来的位置，m为移动后的位置*/ while(i(*A).length&jB.length& kC.length) if (B.elemjC.elemk) k+; else same=B.elemj; /*找到了相同元素same*/ while(

25、B.elemj=same) j+; while(C.elemk=same) k+; /*j和 k 后移到新的元素*/ while(i(*A).length&(*A).elemsame) (*A).elemm+=(*A).elemi+; /* 需保留的元素移动到新位置*/ while(i(*A).length&(*A).elem=same) i+; /*跳过相同的元素*/ /*while*/ while(inext!=NULL) /*链表不为空表*/ p=la-next-next; /*p指向第一结点的后继*/ la-next-next=NULL; /*直接插入原则认为第一元素有序，然后从第二元

26、素起依次插入*/ while (p!=NULL) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页，共 10 页 - - - - - - - - - r=p-next;/*暂存 p 的后继 */ q=la; while (q-next!=NULL&q-next-datadata) q=q-next;/*查找插入位置 */ p-next=q-next;/*将 p 结点链入链表*/ q-next=p; p=r; 12设有一个双向循环链表，每个结点中除有 prior， data 和

27、next三个域外，还增设了一个访问频度域freq 。在链表被起用之前，频度域freq的值均初始化为零，而每当对链表进行一次LOCATE （L，X）的操作后，被访问的结点（元素值等于X 的结点）中的频度域freq的值便增1，同时调整链表中结点之间的次序，使其按访问频度非递增的次序顺序排列，以便始终保持被频繁访问的结点总是靠近表头结点。试编写符合上述要求的 LOCATE操作的算法。【算法分析】1）在双向链表中查找数据值为x 的结点，由指针p 指向，若找不到，直接返回，否则执行第2 步；2）修改 x 结点的访问频度freq ，并将结点从链表上摘下；3）顺结点的前驱链查找该结点的位置，即找到一个结点的

28、访问频度大于x 结点的访问频度，由指针 q 指向；若 q 和 p 不是相邻结点，调整位置，把p 插在 q 之后。【算法源代码】DuLNode * Locate_DuList(DuLinkList *L,int x) p=(*L)-next; while(p.data!=x&p!= (*L) p=p-next; if(p=(*L) return NULL; /*没找到 x 结点 */ p-freq+; p-pre-next=p-next;p-next-pre=p-pre; /*将 x 结点从链表上摘下*/ q=p-pre; while(q-freqfreq&p!= (*L) q=q-pre; /

29、*查找插入位置*/ if(q!=p-pre) /*将 x 结点插入 */ q-next-pre=p; p-next=q-next; q-next=p;p-preq; /*调整位置 */ return p; /*Locate_DuList */ 13已知三个带头结点的线性链表A、B 和 C中的结点均依元素值自小至大非递减排列（可能存在两个以上值相同的结点）， 编写算法对A表进行如下操作： 使操作后的链表A中仅留下三个表中均包含的数据元素的结点，且没有值相同的结点，并释放所有无用结点。限定算法的时间复杂度为O（m+n+p ） ，其中 m 、n 和 p 分别为三个表的长度。【算法分析】留下三个链表中

30、公共数据，首先查找两表A 和 B中公共数据，再去C中找有无该数据。要消除重复元素，应记住前驱，要求时间复杂度O（m+n+p ） ，在查找每个链表时，指针不能回溯。【算法源代码】LinkList Common(LinkList A, LinkList B, LinkList C) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 8 页，共 10 页 - - - - - - - - - pa=A-next;pb=B-next; pc=C-next; /*pa，pb 和 pc 是工作指针

31、*/ pre=A; while(pa & pb & pc) /*当三表均不空时，查找共同元素*/ while(pa & pb) if(pa-datadata) /*处理 pa 结点，后移指针*/ u=pa;pa=pa-next;free(u); else if(pa-data pb-data)pb=pb-next; else if (pa & pb) /*处理 A 和 B表元素值相等的结点*/ while(pc & pc-datadata) pc=pc-next; if(pc) if(pc-datapa-data) /*处理 pa 结点，后移指针*/ u=pa;pa=pa-next;free(

32、u); else if(pre=A) /*结果表中第一个结点*/ pre-next=pa;pre=pa;pa=pa-next else if(pre-data=pa-data) /*重复结点不链入A表*/ u=pa;pa=pa-next;free(u); else pre-next=pa;pre=pa;pa=pa-next;/*将新结点链入A表 */ pb=pb-next;pc=pc-next; /* 链表的工作指针后移*/ else if(pa=NULL)pre-next=NULL; /*若 A表已结束，置A表表尾 */ else /*处理原 A表未到尾而B 或 C到尾的情况 */ pre-

33、next=NULL; /*置 A表表尾标记 */ while(pa!=NULL) /*删除原 A 表剩余元素。 */ u=pa;pa=pa-next;free(u); 14设 head 为一单链表的头指针，单链表的每个结点由一个整数域data 和指针域next 组成，整数在单链表中是无序的。编一函数，将 head 链中结点分成一个奇数链和一个偶数链，分别由 p， q 指向，每个链中的数据按由小到大排列。程序中不得使用malloc 申请空间。【算法分析】本题要求将一个链表分解成两个链表，两个链表都要有序，两链表建立过程中不得使用malloc申请空间， 这就是要利用原链表空间，随着原链表的分解，新

34、建链表随之排序。【算法源代码】discreat(LinkList p, LinkList q, LinkList head) p=NULL; q=NULL;/*p和 q 链表初始化为空表*/ s=head; while (s!=NULL) r=s-next; /*暂存 s 的后继 */ if(s-data%2=0) /*处理偶数 */ 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 9 页，共 10 页 - - - - - - - - - if (p=NULL) p=s;p-next

35、=NULL; /*第一个偶数结点*/ else pre=p; if(pre-datas-data) s-next=pre;p=s;/*插入当前最小值结点*/ else while (pre-next!=NULL) if (pre-next-datadata) pre=pre-next;/*查找插入位置 */ s-next=pre-next; /*链入结点 */ pre-next=s; else/*处理奇数链 if (q=NULL) q=s;q-next=NULL; /*第一奇数结点*/ else pre=q; if (pre-datas-data) s-next=pre; q=s; /*修改头指针 */ else while (pre-next!=NULL) /*查找插入位置*/ if (pre-next-datadata) pre=pre-next; s-next=pre-next; /*链入结点 */ pre-next=s; /*结束奇数链结点*/ s=r; /*s指向新的待排序结点*/ 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 10 页，共 10 页 - - - - - - - - -