数据结构期末考试试题及答案

数据结构期末考试试题及答案一、选择题1.评价一个算法时间性能的主要标准是()。A、算法易于调试B、算法易于理解C、算法的稳定性和正确性D、算法的时间复杂度2.计算机算法具备有输入、输出、（）等五个特性。A、可行性、可移植性和可扩充性B、可行性、确定性和有穷性C、确定性、有穷性和稳定性D、易读性、稳定性和安全性3.带头结点的单链表head为空的判定条件是（）。A、head==NULLB、head-next==NULLC、head-next==headD、head！=NULL4.以下关于线性表的说法不正确的是()。A、线性表中的数据元素可以是数字、字符、记录等不同类型。B、线性表中包含的数据元素个数不是任意的。C、线性表中的每个结点都有且只有一个直接前趋和直接后继。D、存在这样的线性表：表中各结点都没有直接前趋和直接后继。5.在顺序表中，只要知道()，就可在相同时间内求出任一结点的存储地址。A、基地址B、结点大小C、向量大小D、基地址和结点大小6.()运算中，使用顺序表比链表好。A、插入B、删除C、根据序号查找D、根据元素值查找7.一个长度为n的顺序表中，向第i个元素之前插入一个新元素时，需要向后移动（）个元素。A、n-iB、n-i+1C、n-i-1D、i8.()适合作为经常在首尾两端操作线性表的存储结构。A、顺序表B、单链表C、循环链表D、双向链表9.栈和队列的共同点是（）A、都是先进后出B、都是先进先出C、只允许在端点处插入和删除元素D、没有共同点10.一个队列的入列序列是1234，则队列的输出序列是()。A、4321B、1234C、1432D、324111.队列与一般的线性表的区别在于()。A、数据元素的类型不同B、运算是否受限制C、数据元素的个数不同D、逻辑结构不同12.“假上溢”现象会出现在()中。A、循环队列B、队列C、链队列D、顺序队列二、填空题1．数据的逻辑结构被分为集合、线性结构、树形结构和图结构。2．数据的逻辑结构被分为集合、线性结构、树形结构和图状结构。3．下面程序段的时间复杂度是O（n）。i=s=0;while(sn){i++;s++;;}4．树型结构和图形结构合称是非线性结构。5．在长度为n的顺序存储线性表的第i个元素（1≤i≤n）之前插入一个元素时，需要向后移动n-i+1个元素。6．在一个长度为n的顺序存储的线性表中，删除第i个元素（1≤i≤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;⑦P=L;⑧L=L-next;⑨free(Q);9．在线性结构中，第一个结点无前驱结点，其余每个结点有且只有1个前驱结点。10．单链表是线性表的链式存储表示。11．栈是限定仅在表尾进行插入或删除操作的线性表。12．在栈顶指针为HS的链栈中，判定栈空的条件是HS=NULL。13．假设以S和X分别表示进栈和退栈操作，则对输入序列a、b、c、d、e进行一系列栈操作SSXSXSSXXX之后，得到的输出序列为bceda。14．设栈S和队列Q的初始状态为空，元素a、b、c、d、e、f依次通过栈S，一个元素出栈后即进入队列Q。若这6个元素出队列的顺序是b、d、c、f、e、a，则栈S的容量至少应该是3。三、算法填空1．已知一个顺序表中的元素按关键字值非递减有序，下列算法删除顺序表中关键字相同的多余元素，使每个关键字不同的元素在表中只保留一个。voidpurge_sq(SqList&la){//删除顺序表la中关键字相同的多余元素，即使操作之后的顺序表中只保留操作之前表中所有按关键字值都不相同的元素k=-1;//k指示新表的表尾for(i=0;iLa.length;++i)//顺序考察表中每个元素{j=0;while(j=k&&la.elem[j]!=la.elem[i])++j;//在新表中查询是否存在和la.elem[i]相同的元素if(k==-1||jk)//k=-1表明当前考察的是第一个元素la.elem[++k]=la.elem[i];}//forla.length=k+1;//修改表长}//purge_sq2．一个头指针为head的单链表，其中每个结点存放一个整数，以下算法将其拆分为两个单链表head1和head2，使head1中仅含有正整数，head2中仅含有负整数。voidseparate(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-next;head1-next=p;}else{p-next=head2-next;head2-next=p;}p=q;}//whilefree(head);}//seperate3．设一个长度大于1的循环单链表中，既无头结点也无头指针，p为指向该链表中某个结点的指针，以下为一个删除该结点直接前驱结点的算法。voiddelete(LinkListp){//在一个既无头结点也无头指针的长度大于一的循环链表中，//删除指针p所指的某个结点的直接前驱结点q=p;//查找p结点的前驱结点qwhile(q-next!=p)q=q-next;r=q;//查找q结点的前驱结点rwhile(r-next!=q)r=r-next;r-next=p;free(q);}四、计算题1．设有头指针为head的单链表。写算法要求在链表中查找元素值等于x的结点，若找到则删除之，如此反复，直至所有值为x的元素全部删除为止；若一个也找不到则给出相应提示信息。1．voidelemdelete_x(LinkList&l,ElemTypex){//删除头指针为head的单链表中（带头结点）所有的值为x的元素n=0;pre=l;//记下结点*p的前驱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}//whileif(n==0)printf(“Notfoundx\n”);}//elemdelete_x2．有头指针为head的单链表，写算法在链表中查找出所有按先后顺序出现的元素x和y，并将x和y之间的所有结点全部删除之。2．voiddelete(LinkList&head,ElemTypex,ElemTypey){//在头指针为head的单链表中查找出所有按先后顺序出现的元素x和y，//并将x和y之间的所有结点全部删除p=head-next;while(p){while(p&&p-data!=x)p=p-next;if(!p)exit(1);//没找到xr=p-next;while(r&&r-data!=y)r=r-next;if(!r)exit(1);//没找到相应的ywhile(p-next!=r){q=p-next;p-next=q-next;free(q);}//while}//while}3．设某个单链表以la为头指针，链表中每个元素均为整数且无序，写算法按递增顺序打印链表中元素值，方法是：反复找出链表中最小的元素，打印并删除之，直至表空为止。3．voidrearrange(LinkList&la){//将头指针是la的单链表按递增顺序打印出来p=la-next;p1=la;while(p-next!=NULL){a=p-data;q1=p;q=p-next;while(q!=NULL){if(aq-data){a=q-data;p1=q1;}//ifq1=q;q=q-next;}//whiles=p1-next;printf(s-data);p1-next=p1-next-next;free(s);p1=la;p=la-next;}//whileprintf(p-data);free(p);free(la);}//rearrange4．设有一个头指针为head的单链表，每个结点存放一个整数。写一算法将其按负整数在前部正整数在后部的次序存放（正整数与正整数之间、负整数与负整数之间不要求有序），存储空间仍占用原来的链表。4．huafen(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)if(p-data=’0’&&p-data=’9’){p0=p;p=p-next;}else2分{p0-next=p-next;s=p;p=p-next;pt-next=s;s-next=NULL;pt=s;}}//huafen3分5．设有一顺序表a，写算法在表中查找先后出现的元素x和y，将x和y之间的元素逆置，逆置部分不包含x和y。若找不到相应的x和y则给出提示信息。5．voidrevert(ElemType&R[],ints,intt){//本算法将数组R中下标自s到t的元素逆置//即将（RS,Rs+1,…,Rt-1,Rt）改变为（Rt,Rt-1,…,Rs+1,Rs）for(k=s;k=(s+t)/2;k++){w=R[k];R[k]=R[t-k+s];R[t-k+s]=w;}//for}//revertvoidexchange(SqList&a,ElemTypex,ElemTypey){//本算法实现在顺序表a中查找先后出现的元素x和y之间的元素逆置，//逆置部分不包含x和y。if(!(LocateElem(la,x,equal)&&LocateElem(la,y,equal)))returnerror;//找不到相应的x和yk=LocateElem(la,x,equal);l=LocateElem(la,y,equal);if((k=la.length)||(lla.length)||(l-k=1)||(kl))returnerror;elserevert(la.elem,k+1,l-1)；}//exchange