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

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

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. 以下关于线性表的说法不

2、正确选项 ；A、线性表中的数据元素可以是数字、字符、记录等不同类型；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. 一个队列的入列序列是 A、4 3 2 1 B、1 2 3 4 C、1 4 3 2 D、3 2 4 1 1 2 3 4 ,就队列的输出序列是 ；11. 队列与一般的线性表的区分在于 ；A、数据元素的类型不同 B、运算是否受限制 C、数据元素的个数不同

4、D、规律结构不同 12. “ 假上溢” 现象会显现在 中；A、循环队列 B、队列 C、链队列 D、次序队列名师归纳总结 - - - - - - -第 2 页,共 12 页精选学习资料 - - - - - - - - - 学而不思就惘,思而不学就殆二、填空题1数据的规律结构被分为集合、线性结构、树形结构和图结构；2数据的规律结构被分为集合、线性结构、树形结构和图状结构；3下面程序段的时间复杂度是 O（n）；i=s=0; while snext=head；8已知 L 是带头结点的非空单链表,且 的答案中挑选合适的语句序列,实现删除P结点既不是第一个数据结点,也不是最终一个结点,试P结点的直接后继结

5、点的语句序列是 ； P-next = P-next -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; freeQ; 9在线性结构中,第一个结点无前驱结点,其余每个结点有且只有 1 个前驱结点；10单链表是线性表的链式储备表示；11栈是限定仅在表尾进行插入或删除操作的线性表；12在栈顶指针为

6、HS的链栈中,判定栈空的条件是 HS=NULL ；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_sqSqList &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 使 he

8、ad 1 中仅含有正整数, head 2 中仅含有负整数；void separateLinkList &head, LinkList &head1,LinkList &head2 / 将头指针为 head 的单链表（带头结点）拆分为两个单链表 / 使 head1 中仅含有正整数, head2 中仅含有负整数head1 和 head2,head1=LinkListmallocsizeofLnode; head1-next=NULL; head2=LinkListmallocsizeofLnode ; head2-next=NULL; p=head-next; whilep q=p-next; i

9、f （p-data=0）p-next=head1-next; head1-next=p; else p-next=head2-next; head2-next=p; p=q; /while 名师归纳总结 - - - - - - -第 5 页,共 12 页精选学习资料 - - - - - - - - - 学而不思就惘,思而不学就殆freehead; /seperate 3设一个长度大于1 的循环单链表中,既无头结点也无头指针,p 为指向该链表中某个结点的指一个删除该结点直接前驱结点的算法；void deleteLinkList p / 在一个既无头结点也无头指针的长度大于一的循环链表中,/ 删除

10、指针 p 所指的某个结点的直接前驱结点 q=p; / 查找 p 结点的前驱结点 q whileq-next.=p q=q-next; r=q; / 查找 q 结点的前驱结点 r whiler-next.=q r=r-next; r-next=p; freeq; 四、运算题1设有头指针为 head 的单链表；写算法要求在链表中查找元素值等于 x 的结点,如找到就删除之 复,直至全部值为 x 的元素全部删除为止；如一个也找不到就给出相应提示信息；1void elemdelete_xLinkList &l,ElemType x 名师归纳总结 / 删除头指针为 head 的单链表中（带头结点）全部的值

11、为x 的 元素第 6 页,共 12 页n=0; pre=l; /登记结点 *p 的前驱- - - - - - -精选学习资料 - - - - - - - - - 学而不思就惘,思而不学就殆p=l-next; whilep / 次序考察表中每个元素 whilep&p-data.=x pre=p; p=p-next; / 在表中查询是否存在和 x 相同的元素 ifp / 将结点 p 插入到新的表中pre-next=p-next; q=p; p=p-next; freeq; n+; /if /while ifn=0printf“ Notfound xn” ;/elemdelete_x 2有头指针为

12、head 的单链表,写算法在链表中查找出全部按先后次序显现的元素 的全部结点全部删除之；x 和 y,并将 x2void delete LinkList &head , ElemType x, ElemType y / 在头指针为 head 的单链表中查找出全部按先后次序显现的元素 x 和 y,/ 并将 x 和 y 之间的全部结点全部删除p=head-next; whilep while p&p-data.=x 名师归纳总结 - - - - - - -第 7 页,共 12 页精选学习资料 - - - - - - - - - 学而不思就惘,思而不学就殆p=p-next; if .p exit1;

13、/ 没找到 x r=p-next; whiler&r-data.=y r=r-next; if.r exit1; / 没找到相应的 y whilep-next.=r q=p-next; p-next=q-next; freeq; /while /while 3设某个单链表以 la 为头指针,链表中每个元素均为整数且无序,写算法按递增次序打印链表中 方法是：反复找出链表中最小的元素,打印并删除之,直至表空为止；3void rearrangeLinkList &la / 将头指针是 la 的单链表按递增次序打印出来 p=la-next; p1=la; whilep-next.=NULL a=p-d

14、ata; q1=p; q=p-next; whileq.=NULL ifaq-data 名师归纳总结 - - - - - - -第 8 页,共 12 页精选学习资料 - - - - - - - - - 学而不思就惘,思而不学就殆a=q-data; p1=q1;/if q1=q; q=q-next; /while s=p1-next; printfs-data; p1-next=p1-next-next; frees; p1=la; p=la-next; /while printfp-data; freep; freela; /rearrange 4设有一个头指针为 head 的单链表,每个结点

15、存放一个整数；写一算法将其按负整数在前部 正整数在后部的次序存放（正整数与正整数之间、负整数与负整数之间不要求有序）,储备空间仍占用原先的链表；4huafenLinkList &L /L 为带头结点的单链表的头指针 p=L-next; whilep-next p=p-next; pt=p; pr=p; p0=L; 分 p=p0-next; 3 whilep.=pr 名师归纳总结 - - - - - - -第 9 页,共 12 页精选学习资料 - - - - - - - - - 学而不思就惘,思而不学就殆if p-data=0& p- datanext; else 2 分 p0-next=p-n

16、ext; 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 revertElemType &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 页