2022年数据结构期末考试试题及答案 .pdf

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

1、学而不思则惘，思而不学则殆数据结构期末考试试题及答案一、选择题1. 评价一个算法时间性能的主要标准是( ) 。A、算法易于调试B、算法易于理解C、算法的稳定性和正确性D、算法的时间复杂度2. 计算机算法具备有输入、输出、（）等五个特性。A、可行性、可移植性和可扩充性B、可行性、确定性和有穷性C、确定性、有穷性和稳定性D、易读性、稳定性和安全性3. 带头结点的单链表head为空的判定条件是（）。A、head=NULL B、head-next=NULL C、head-next=head D、head！=NULL 4. 以下关于线性表的说法不正确的是( ) 。A、线性表中的数据元素可以是数字、字符、

2、记录等不同类型。B、线性表中包含的数据元素个数不是任意的。C、线性表中的每个结点都有且只有一个直接前趋和直接后继。D、存在这样的线性表：表中各结点都没有直接前趋和直接后继。5. 在顺序表中，只要知道 ( ) ，就可在相同时间内求出任一结点的存储地址。A、基地址B、结点大小C、向量大小D、基地址和结点大小6. ( ) 运算中，使用顺序表比链表好。A、插入B、删除C、根据序号查找D、根据元素值查找7. 一个长度为 n 的顺序表中，向第i 个元素之前插入一个新元素时，需要向后移动（）个元素A、n-i B、n-i+1 C、n-i-1 精选学习资料 - - - - - - - - - 名师归纳总结 -

3、- - - - - -第 1 页，共 12 页学而不思则惘，思而不学则殆D、i 8. ( ) 适合作为经常在首尾两端操作线性表的存储结构。A、顺序表B、单链表C、循环链表D、双向链表9. 栈和队列的共同点是（）A、都是先进后出B、都是先进先出C、只允许在端点处插入和删除元素D、没有共同点10. 一个队列的入列序列是1 2 3 4 ，则队列的输出序列是 ( ) 。A、4 3 2 1 B、1 2 3 4 C、1 4 3 2 D、3 2 4 1 11. 队列与一般的线性表的区别在于( ) 。A、数据元素的类型不同B、运算是否受限制C、数据元素的个数不同D、逻辑结构不同12. “假上溢”现象会出现在

4、( ) 中。A、循环队列B、队列C、链队列D、顺序队列精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 2 页，共 12 页学而不思则惘，思而不学则殆二、填空题1数据的逻辑结构被分为集合、线性结构、树形结构和图结构。2数据的逻辑结构被分为集合、线性结构、树形结构和图状结构。3下面程序段的时间复杂度是O（n）。i=s=0; while (snext=head。8已知 L 是带头结点的非空单链表，且P结点既不是第一个数据结点，也不是最后一个结点，试的答案中选择合适的语句序列，实现删除P结点的直接后继结点的语句序列是 。 P-next = P-next -

5、next; P=P-next-next; while (P-next!=Q) P=P-next; while (P-next-next=Q) P=P-next; Q=P; Q=P-next; 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 3 页，共 12 页学而不思则惘，思而不学则殆 P=L; L=L-next; free(Q); 9在线性结构中，第一个结点无前驱结点，其余每个结点有且只有1 个前驱结点。10单链表是线性表的链式存储表示。11栈是限定仅在表尾进行插入或删除操作的线性表。12在栈顶指针为HS的链栈中，判定栈空的条件是HS=NULL

6、。13假设以 S和 X分别表示进栈和退栈操作，则对输入序列a、b、c、d、e 进行一系列栈操作SS后，得到的输出序列为bceda 。14设栈 S和队列 Q的初始状态为空，元素a、b、c、d、e、f 依次通过栈 S，一个元素出栈后即若这 6 个元素出队列的顺序是b、d、c、f 、e、a，则栈 S的容量至少应该是 3。三、算法填空1已知一个顺序表中的元素按关键字值非递减有序，下列算法删除顺序表中关键字相同的多余元关键字不同的元素在表中只保留一个。void purge_sq(SqList &la) / 删除顺序表 la 中关键字相同的多余元素，即使操作之后的顺序表中只保留操作之前表中所有按不相同的元

7、素k= -1; /k指示新表的表尾for (i=0;iLa.length;+i) /顺序考察表中每个元素j=0; while (jk) /k= -1表明当前考察的是第一个元素la.elem+k= la.elemi; 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 4 页，共 12 页学而不思则惘，思而不学则殆/for la.length=k+1; /修改表长/purge_sq 2 一个头指针为 head的单链表，其中每个结点存放一个整数， 以下算法将其拆分为两个单链表head使 head 1 中仅含有正整数， head 2 中仅含有负整数。void

8、 separate(LinkList &head, LinkList &head1,LinkList &head2) / 将头指针为 head的单链表（带头结点）拆分为两个单链表head1和 head2，/ 使 head1中仅含有正整数， head2中仅含有负整数head1=(LinkList)malloc(sizeof(Lnode); head1-next=NULL; head2=(LinkList)malloc(sizeof(Lnode) ; head2-next=NULL; p=head-next; while(p) q=p-next; if （p-data=0）p-next=head1

9、-next; head1-next=p; else p-next=head2-next; head2-next=p; p=q; /while 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 5 页，共 12 页学而不思则惘，思而不学则殆free(head); /seperate 3设一个长度大于1 的循环单链表中，既无头结点也无头指针，p 为指向该链表中某个结点的指一个删除该结点直接前驱结点的算法。void delete(LinkList p) / 在一个既无头结点也无头指针的长度大于一的循环链表中，/ 删除指针 p 所指的某个结点的直接前驱结点q

10、=p; /查找 p 结点的前驱结点 q while(q-next!=p) q=q-next; r=q; /查找 q 结点的前驱结点 r while(r-next!=q) r=r-next; r-next=p; free(q); 四、计算题1设有头指针为 head 的单链表。写算法要求在链表中查找元素值等于x 的结点，若找到则删除之复，直至所有值为x 的元素全部删除为止；若一个也找不到则给出相应提示信息。1void elemdelete_x(LinkList &l,ElemType x) / 删除头指针为 head 的单链表中（带头结点）所有的值为x 的 元素n=0; pre=l; /记下结点

11、*p 的前驱精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 6 页，共 12 页学而不思则惘，思而不学则殆p=l-next; while(p) /顺序考察表中每个元素 while(p&p-data!=x) pre=p; p=p-next; /在表中查询是否存在和x 相同的元素if(p) /将结点 p 插入到新的表中pre-next=p-next; q=p; p=p-next; free(q); n+; /if /while if(n=0)printf(“Notfound xn”);/elemdelete_x 2有头指针为 head 的单链表，写算法

12、在链表中查找出所有按先后顺序出现的元素x 和 y，并将 x的所有结点全部删除之。2void delete (LinkList &head , ElemType x, ElemType y) / 在头指针为 head 的单链表中查找出所有按先后顺序出现的元素x 和 y，/ 并将 x 和 y 之间的所有结点全部删除p=head-next; while(p) while (p&p-data!=x) 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 7 页，共 12 页学而不思则惘，思而不学则殆p=p-next; if (!p) exit(1); /没找到

13、x r=p-next; while(r&r-data!=y) r=r-next; if(!r) exit(1); /没找到相应的 y while(p-next!=r) q=p-next; p-next=q-next; free(q); /while /while 3设某个单链表以la 为头指针，链表中每个元素均为整数且无序，写算法按递增顺序打印链表中方法是：反复找出链表中最小的元素，打印并删除之，直至表空为止。3void rearrange(LinkList &la) / 将头指针是 la 的单链表按递增顺序打印出来p=la-next; p1=la; while(p-next!=NULL) a

14、=p-data; q1=p; q=p-next; while(q!=NULL) if(aq-data) 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 8 页，共 12 页学而不思则惘，思而不学则殆a=q-data; p1=q1;/if q1=q; q=q-next; /while s=p1-next; printf(s-data); p1-next=p1-next-next; free(s); p1=la; p=la-next; /while printf(p-data); free(p); free(la); /rearrange 4设有一个头

15、指针为head的单链表，每个结点存放一个整数。写一算法将其按负整数在前部正整数在后部的次序存放（正整数与正整数之间、负整数与负整数之间不要求有序），存储空间仍占用原来的链表。4huafen(LinkList &L) /L为带头结点的单链表的头指针p=L-next; while(p-next) p=p-next; pt=p; pr=p; p0=L; p=p0-next; 3分while(p!=pr) 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 9 页，共 12 页学而不思则惘，思而不学则殆if (p-data=0& p-datanext; els

16、e 2分p0-next=p-next; s=p; p=p-next; pt-next=s; s-next=NULL; pt=s; /huafen 3分5设有一顺序表 a，写算法在表中查找先后出现的元素x 和 y，将 x 和 y 之间的元素逆置，逆置部分不包含 x 和 y。若找不到相应的x 和 y 则给出提示信息。 5 void revert(ElemType &R, int s,int t) / 本算法将数组 R中下标自 s 到 t 的元素逆置/ 即将（ RS,Rs+1,Rt-1,Rt）改变为（ Rt,Rt-1, ,Rs+1,Rs）for (k=s;k=la.length)|(lla.length)|(l-k=1)|(kl) return error; else revert (la.elem,k+1,l-1)；/exchange精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 11 页，共 12 页学而不思则惘，思而不学则殆精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 12 页，共 12 页