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

精选学习资料 - - - - - - - - - 学而不思就惘,思而不学就殆数据结构期末考试试题及答案一、挑选题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、线性表中的数据元素可以是数字、字符、记录等不同类型；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 名师归纳总结 - - - - - - -第 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、数据元素的个数不同 D、规律结构不同 12. “ 假上溢” 现象会显现在 中；A、循环队列 B、队列 C、链队列 D、次序队列名师归纳总结 - - - - - - -第 2 页,共 12 页精选学习资料 - - - - - - - - - 学而不思就惘,思而不学就殆二、填空题1数据的规律结构被分为集合、线性结构、树形结构和图结构；2数据的规律结构被分为集合、线性结构、树形结构和图状结构；3下面程序段的时间复杂度是 O（n）；i=s=0; while s<n i+; s+; 4树型结构和图形结构合称是非线性结构；5在长度为 n 的次序储备线性表的第 需要向后移动 n-i+1 个元素；i 个元素（ 1i n）之前插入一个元素时,6在一个长度为 n 的次序储备的线性表中,删除第 i 个元素（ 1i n）时,需要向前移动 n-i 个元素；7指针 p 指向非空循环单链表head 的尾结点,就 p 满意 p->next=head；8已知 L 是带头结点的非空单链表,且 的答案中挑选合适的语句序列,实现删除P结点既不是第一个数据结点,也不是最终一个结点,试P结点的直接后继结点的语句序列是 ； 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在栈顶指针为 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 中关键字相同的余外元素,即使操作之后的次序表中只保留操作之前表中全部按 不相同的元素 k= -1; /k 指示新表的表尾 for i=0;i<La.length;+i / 次序考察表中每个元素 j=0; while j<=k &&la.elemj.=la.elemi +j; /在新表中查询是否存在和la.elemi相同的元素if k= = -1|j>k /k= -1说明当前考察的是第一个元素la.elem+k= la.elemi; 名师归纳总结 - - - - - - -第 4 页,共 12 页精选学习资料 - - - - - - - - - 学而不思就惘,思而不学就殆/for la.length=k+1; / 修改表长 /purge_sq 2一个头指针为 head的单链表,其中每个结点存放一个整数, 以下算法将其拆分为两个单链表 head 使 head 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; if （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 / 在一个既无头结点也无头指针的长度大于一的循环链表中,/ 删除指针 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 的单链表中（带头结点）全部的值为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有头指针为 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; / 没找到 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->data; q1=p; q=p->next; whileq.=NULL ifa>q->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 的单链表,每个结点存放一个整数；写一算法将其按负整数在前部 正整数在后部的次序存放（正整数与正整数之间、负整数与负整数之间不要求有序）,储备空间仍占用原先的链表；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- >data<=9p0=p; p=p->next; else 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 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<=s+t/2;k+ w=Rk; Rk=Rt-k+s; Rt-k+s=w; /for /revert 名师归纳总结 - - - - - - -第 10 页,共 12 页精选学习资料 - - - - - - - - - 学而不思就惘,思而不学就殆void exchange SqList &a,ElemType x,ElemType y / 本算法实现在次序表a 中查找先后显现的元素x 和 y 之间的元素逆置,/ 逆置部分不包含 x 和 y；if .LocateElem la,x,equal&&LocateElemla,y,equal return error; / 找不到相应的 x 和 y k=LocateElemla,x,equal; l=LocateElemla,y,equal; if k>=la.length|l>la.length|l-k=1|k>l return error; else revert la.elem,k+1,l-1；/exchange名师归纳总结 - - - - - - -第 11 页,共 12 页精选学习资料 - - - - - - - - - 学而不思就惘,思而不学就殆名师归纳总结 - - - - - - -第 12 页,共 12 页