精选题目及解答(部分)

1、题题1：设数据的逻辑结构定义为S=(D,R),其中D=a,b,c,d,e,R=r,r=,请画出对应的逻辑结构，说明是何种数据结构。 精选习题讲解精选习题讲解2 解：解：S对应的逻辑结构图见下图。由于结点b有两个直接前驱结点a和e,有两个直接后继结点c和d，所以它是一个有向图。aebde数据逻辑结构图精选习题讲解精选习题讲解3精选习题讲解精选习题讲解题题2：分析下列程序段的时间复杂度。(a)for(i=0;im;i+) (b) s=0; for(j=0;jn;j+) for(i=0;in;i+) bij=0; for(j=i;jn;j+)s+=bij; (c) i=1; while(inext;

2、 while( p & jnext; return p;8精选习题讲解精选习题讲解题题5 ：请设计一个在带头结点的单链表中删除所有元素为x的算法。 9精选习题讲解精选习题讲解解：在带头结点的单链表中查找元素x所在结点，在删除该结点时，需将其直接后继结点作为其直接前驱结点的直接后继。由于单链表中结点无指向其直接前驱结点的指针域，故不能从当前访问结点直接找到其直接前驱结点，解决这个问题的方案之一方案之一是：设p指向当前结点，另设一个指针变量q指向p结点的直接前驱结点。方案之二方案之二：查找p结点的直接后继结点数据域值是否等于x，若等于则删除p结点的直接后继结点。本例采用方案二。算法描述如下

3、。10精选习题讲解精选习题讲解void deletex( LNode* h , ElemType x ) LNode* q, *p=h; while(p&p-next) if(p-next-data=x) q=p-next; p-next=q-next; free(q); /if else p=p-next;11精选习题讲解精选习题讲解题题6 ：设线性表有2n个元素，下列算法中，_在单链表上实现要比在顺序表上实现效率更高。（程序员考试)A.在最后一个元素的后面插入一个新元素B.交换第i个元素和第2n-i+1(i=0,1,n-1)C.删除所有值为x的元素D.顺序输出前k个元素12精选习题

4、讲解精选习题讲解解解 ：对于C，在单链表和顺序表上实现的效率基本相同，但后者要移动很多元素，所以在单链表上实现效率更高些。答案：C13精选习题讲解精选习题讲解题题7 ：设顺序表有n个元素，以下算法中，_在顺序表上实现比在链表上实现效率更高。（程序员考试)A.输出第i个元素（0 in-1）B.交换第0个元素和第1个元素的值C.顺序输出这n个元素的值D. 输出与给定值x相等的元素在线性表中的序号14精选习题讲解精选习题讲解解解 ：顺序表具有随机访问的特点，所以输出第i个元素时效率很高，因为可以直接访问到要输出的元素。C,D在效率上相等，B用链表实现更有效率。答案：A15精选习题讲解精选习题讲解题题

5、8 ：某线性表最常用的操作是在最后一个结点之后插入一个结点或删除一个第一个结点，故采用_存储方式最节省运算时间。（程序员考试)A.单链表 B.仅有尾指针的单循环链表C.双链表 D.仅有头结点的单循环链表16精选习题讲解精选习题讲解解解 ：在有尾指针r的单循环链表中，在最后一个结点之后插入结点s的操作是：s-next=r-next; r-next=s; r=s;删除第一个结点的操作是：p=r-next; r-next=p-next; free(p);答案：B17精选习题讲解精选习题讲解题题9 ：设有一个顺序表L，其元素为整型数据，写一算法将小于0的整数放在前半部分，大于0的整数放在后半部分。（程

6、序员考试)18精选习题讲解精选习题讲解解解 ：从L的两端开始查找，前端找大于0的元素，找到后位置用i记录，后端找小于0的元素，找到后用j记录，交换两位置的元素。再重复上一操作。19精选习题讲解精选习题讲解void move(Sqlist &L) int i=0,j=L.length-1,temp; while(ij) while(ij & L.datai0) i+; /找大于找大于0的元素的元素 while(i0) j-; /找大于找大于0的元素的元素 if(i1)的单链表上，设有头和尾两个指针，执行_操作与链表的长度有关。A.删除单链表的第一个元素B.删除单链表的最后一个元素

7、C.在单链表的第一个元素前插入一个新元素D.在单链表的最后一个元素后插入一个新元素23精选习题讲解精选习题讲解答案答案: B24精选习题讲解精选习题讲解题题13 ：在表长大于1的不带头结点的单循环链表中，查找p所指向的结点的直接前驱结点，请设计一个算法。25精选习题讲解精选习题讲解解：无头结点的单循环链表如图所示。最后一个结点的直接后继结点是首元结点，从表中任一结点可访问表中所有结点。故从p出发可找到其直接前驱结点（*q），即q-next=p。算法描述如下：246p.q26精选习题讲解精选习题讲解LNode*Prior(LNode* p) LNode* q=p-next; while(q-ne

8、xt!=p) q=q-next; return q;27精选习题讲解精选习题讲解题题14 ：在带头结点的双循环链表中，数据域值为整数，已按数据域值从小到大顺序排列，请设计一个算法，实现将x插入到该循环链表中。28精选习题讲解精选习题讲解解：解：先从带头结点的双向循环链表h中，查找第一个不小于x的结点，若找到满足这个条件的*p结点则可将新结点插入到p之前，否则将新结点插入到表头结点之前（即尾结点之后）。算法描述如下：29精选习题讲解精选习题讲解void Insertx(DLnode* h,ElemType x) DLnode* s=new DLnode; s-data=x; if( h-next

9、=h) ) /空表处理 h-next=s; s-prior=h; s-next=h; h-prior=s; return; /if 30精选习题讲解精选习题讲解 DLnode* p=h-next; while(p!=h & xp-data) p=p-next; s-prior=p-prior; p-prior-next=s; p-prior=s; s-next=p;/Insertx31精选习题讲解精选习题讲解题题15 ：下列算法的功能是什么？下列算法的功能是什么？bool fun(DLinklist L) /L是带头结点的双向循环链表是带头结点的双向循环链表 flag=true; fr

10、ont=L-next; rear=L-pre; while(front!=rear) & (front-next!=rear) if(front-data=rear-data) front=front-next;rear=rear-pre; else flag=false; return flag; 32精选习题讲解精选习题讲解解：解：判断带头结点的双循环链表L是否对称。对称是指以头结点为中心，左右两边对称位置上的结点值相等。front和rear分别指向头结点的右左两端，通过后继和前驱指针域，找左、右两边对称位置上的结点，比较它们的值，若相等，则修改front和rear，继续进行下一对

11、的比较；否则设置不对称标志flag=false。循环结束时，front和rear相遇或交错。33精选习题讲解精选习题讲解题题16 ：设有n个元素进栈，请给出全部可能的出栈序列个数和不可能的出栈序列个数。34精选习题讲解精选习题讲解解：解：先设全部可能的出栈序列个数为bn。当n=3时，b3=5对n个元素组成的序列，全部可能的排列数Pn=n!，所以不可能出栈序列的个数为Pn-bn。当n=3时，P3-b3=1。(2 )!11211! !nnnnnn nbnC35精选习题讲解精选习题讲解题题17 ：设（静态）顺序栈定义如下：#define MAX 100 /顺序栈的最大容量typedef struct

12、 SNode ElemType dataMAX; int top; /栈顶栈顶元素在数组中存储位置（下标）SqStack;请写出实现栈的6种基本操作的算法。36精选习题讲解精选习题讲解解：解：6种基本操作：（1）初始化栈; （2）入栈；（3）出栈；（4）判栈是否为空；（5）判栈是否为满；（6）取栈顶元素。37精选习题讲解精选习题讲解(1) void InitStack(SqStack& s) s.top=-1;38精选习题讲解精选习题讲解(2) bool Push(SqStack& s, ElemType e) if(s.top=MAX-1) cout“ Stack is fu

13、ll!”;return false; s.data+s.top=e; return true;39精选习题讲解精选习题讲解(3) bool Pop(SqStack& s, ElemType& e) if(s.top=-1) cout“ Stack is empty!”;return false; e =s.datas.top-; return true;40精选习题讲解精选习题讲解(4) bool Empty( SqStack s) if(s.top=-1) return true;else return false;(5) bool Full( SqStack s) if(s

14、.top=MAX-1) return true;else return false;41精选习题讲解精选习题讲解(6) bool Gettop( SqStack s, ElemType& e) if( !Empty(s) ) e = s.datas.top; return true;else return false;42精选习题讲解精选习题讲解题题18 ：利用题利用题8定义的顺序栈及其基本操作，定义的顺序栈及其基本操作，实现输出实现输出num说对应的说对应的r进制的各位数字。进制的各位数字。43精选习题讲解精选习题讲解void Convert ( int num, int r ) S

15、qStack s; InitStack(s); int e; while(num!=0) Push( s, num%r ); num/=r; /while while(!Empty(s) Pop(s,e); coutdata=x; if(qu-rear=NULL) / 循环队列为空，循环队列为空， / 则建立一个结点的循环队列则建立一个结点的循环队列 qu-rear=s; qu-rear-next=s; else /循环队列不为空，则循环队列不为空，则*s插入到后面插入到后面 s-next=qu-rear-next; qu-rear-next=s; qu-rear=s; /qu-rear始终指向最后一个结点始终指向最后一个结点 50精选习题讲解精选习题讲解(2)队列的删除是在队头进行的，所以应删除该队列的删除是在队头进行的，所以应删除该循环链表的第一个结点，其算法如下循环链表的第一个结点，其算法如下：51精选习题讲解精选习题讲解int Dequeue ( Qtype* &qu ,El