学期-数据结构习题及补充考研-第3章.ppt

第三章习题,#define MAX 100 typedef struct node Elemtype *base2; Elemtype *top2; BDStacktype; /双向栈类型,3.15 顺序双向栈-初始化、入栈、出栈,status Init_Stack(BDStacktype /Init_Stack,3.15 顺序存储结构双向栈-初始化,status push(BDStacktype /push,3.15 顺序存储结构双向栈-入栈,status pop(BDStacktype /pop,3.15 顺序存储结构双向栈-出栈,3.28假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾元素结点（注意不设头指针），试编写相应的队列初始化、入队列和出队列的算法。,typedef struct CiLNode Elemtype data; struct CiLNode *next; *CiQueue; CiQueue Q；,队列初始化： void InitCiQueue(CiQueue /InitCiQueue,Q,struct CiLNode型结点,x,void EnCiQueue(CiQueue /修改尾指针,入队列,status DeCiQueue(CiQueue /DeCiQueue,struct CiLNode型结点,x,出队列,3.29如果希望循环队列中的元素都能得到利用，则需设置一个标志域tag，并以tag的值为0或1来区分，尾指针和头指针值相同时的队列状态是 “空”还是“满”。试编写与此结构相应的入队列和出队列的算法。,看3.29前回忆课本：,#define MAXQSIZE 100 /最大队列长度 /与栈不同，循环队列不能进行再分配。 typedef struct QElemType *base; / 动态分配存储空间 int front; / 头指针，若队列不空，指向队列头元素 int rear; / 尾指针，若队列不空，指向队列尾元素 的下一个位置 SqQueue;,循环队列顺序映象,base,front,rear,status EnQueue(SqQueue ,循环队列顺序映象,#define MAXQSIZE 100 /最大队列长度。 typedef struct QElemType *base; / 动态分配存储空间 int front; / 指向队头元素 int rear; / 指向队尾元素的下一个位置 int tag; CyQueue ;,3.29如果希望循环队列中的元素都能得到利用，则需设置一个标志域tag，并以tag的值为0或1来区分，尾指针和头指针值相同时的队列状态是 “空”还是“满”。试编写与此结构相应的入队列和出队列的算法。,0,Q.tag,CyQueue Q;,设规定：Q.front=Q.rear 且tag域的值为0时表示“空“, Q.front=Q.rear 且tag域的值为1时表示“满“.,status EnCyQueue(CyQueue ,Q.tag,CyQueue Q;,入队列,Q.tag,CyQueue Q;,出队列,status DeCyQueue(CyQueue ,3.30假设将循环队列定义为：以域变量rear和length分别指示循环队列中队尾元素的位置和内含元素的个数。试给出此循环队列的队满条件，并写出相应的入队列和出队列的算法（在出队列的算法中要返回队头元素）。,J5,J4,J3,一般情况,CyQueue Q;,Q.rear,Q.length,设MAXSIZE=6,#define MAXQSIZE 6 /最大队列长度。 typedef struct int rear; / 指向队尾元素的下一个位置 int length; CyQueue ;,status EnCyQueue(CyQueue ,3.30假设将循环队列定义为：以域变量rear和length分别指示循环队列中队尾元素的位置和内含元素的个数。试给出此循环队列的队满条件，并写出相应的入队列和出队列的算法（在出队列的算法中要返回队头元素）。,J5,J4,J3,一般情况,CyQueue Q;,Q.rear,Q.length,设MAXSIZE=6,status DeCyQueue(CyQueue ,J5,J4,J3,一般情况,CyQueue Q;,Q.rear,Q.length,设MAXSIZE=6,3.30假设将循环队列定义为：以域变量rear和length分别指示循环队列中队尾元素的位置和内含元素的个数。试给出此循环队列的队满条件，并写出相应的入队列和出队列的算法（在出队列的算法中要返回队头元素）。,补充题目,递归问题：,求最大（小）值,/例1.11：有一个不带表头结点的单链表，输出以h为头指针的单链表中最大结点值。 typedef int ElemType; const int MaxSize=32767; const int Minnum=-32768;/表示最小的数 /单链表结点 typedef struct node ElemType data; struct node *next; Node;,data,next,Node单链表结点类型,例1.11：有一个不带表头结点的单链表，输出以h为头指针的单链表中最大结点值。 ElemType maxv(Node *h) static ElemType m=Minnum; /静态变量m，用来保存到目前为止求得的最大值，m初始时刻为可表示的最小值 if(h=NULL) m=NULL; else if(h-datam) m=h-data; if(h-next=NULL)/递归结束的条件 return m; else return maxv(h-next); ,递归问题：,求最大（小）值,/例1.12 求顺序表a1,a2,a3,.an中最大元素。 typedef int ElemType; const int MaxSize=32767; const int Minnum=-32768;/表示最小的数 /顺序表 typedef struct List ElemType listMaxSize; int size; Sqlist;,递归问题：,求最大（小）值,list,size,Sqlist顺序表类型,/例1.12 求顺序表a1,a2,a3,.an中最大元素。 ElemType max(Sqlist A,int n) /n为顺序表中元素个数 static ElemType m=Minnum; /静态变量m，用来保存到目前为止求得的最大值，m初始时刻为可表示的最小值. if(n0) if(A.Listn-1m) m=A.Listn-1; if(n=1)/递归结束的条件 return m; else return Max(A,n-1); ,递归问题：,求最大（小）值,list,size,Sqlist 顺序表A,例1.15有一个不带头结点的单链表，求以h为头指针的单链表的结点个数. int count(Node *h) if(h=NULL) return 0; else return 1+count(h-next); ,/单链表结点 typedef struct node ElemType data; struct node *next; Node;,递归问题：,/例1.19判断两个单链表是否相同（不带头结点） int sameL(Node *L1,Node *L2) if(L1=NULL ,判断特殊性,递归问题：,L1,例1.23有一个不带头结点的单链表，删除以h为头指针的单链表中值为x的所有结点 void delall(Node */递归 ,删除元素,递归问题：,例1.24有一个不带头结点的单链表，删除以h为头指针的单链表中值为x的第一个结点。 void del(Node * ,删除元素,递归问题：,例2.1-原例1.15有一个不带头结点的单链表，求以h为头指针的单链表的结点个数。 int count(Node *h) int sum=0; if(h=NULL) return 0; else while(h!=NULL) sum+; h=h-next; return sum; ,递归转非递归,例2.2该原例1.23有一个不带头结点的单链表，删除以h为头指针的单链表中值为x的所有结点 void delall(Node * ,递归转非递归,例2.4改原例1.19判断两个单链表是否相同（不带头结点）。 int sameL(Node *L1,Node *L2) while(L1!=NULL ,L1,递归转非递归,数据结构考研知识点,栈S,队列Q,a,b,c,d,e,f,g,1.若某线性表中最常用的操作是取第i 个元素和找第i个 元素的前趋元素，则采用（ ）存储方式最节省时间。 单链表 双链表 单向循环 顺序表 2.若某线性表中最常用的操作是在最后一个元素之后插 入一个元素和删除最后一个元素，则采用（ ）存储方 式最节省运算时间。 单链表 双链表 带头结点的双循环链表 容量足够大的顺序表 3.栈操作的原则是（ ）。 先进先出 后进先出 栈顶插入 栈顶删除 4.如果以链表作为栈的存储结构，则退栈操作时（ ） 必须判别栈是否满 对栈不作任何判别 必须判别栈是否空 判别栈元素的类型,单项选择题,5在双向链表指针p的结点前插入一个指针q的结点操作是（ ）。 【青岛大学 2000 五、2（2分）】 Ap-Llink=q;q-Rlink=p;p-Llink-Rlink=q;q-Llink=q； Bp-Llink=q;p-Llink-Rlink=q;q-Rlink=p;q-Llink=p-Llink; Cq-Rlink=p;q-Llink=p-Llink;p-Llink-Rlink=q;p-Llink=q; Dq-Llink=p-Llink;q-Rlink=q;p-Llink=q;p-Llink=q; 6在单链表指针为p的结点之后插入指针为s的结点，正确的操作是：（ ）。【青岛大学 2001 五、3（2分）】 Ap-next=s;s-next=p-next; Bs-next=p-next;p-next=s; Cp-next=s;p-next=s-next; Dp-next=s-next;p-next=s;,p,q,p,s,7. 一个栈的输入序列为1 2 3 4 5，则下列序列中不可能是栈的输出序列的是（ ）。 A. 2 3 4 1 5 B. 5 4 1 3 2 C. 2 3 1 4 5 D. 1 5 4 3 2 【南开大学 2000 一、1】【山东大学 2001 二、4 (1分)】 8. 用链式存储的队列，在进行删除运算时（ ）。 【北方交通大学 2001 一、12（2分）】 A.仅修改头指针 B. 仅修改尾指针 C. 头、尾指针都要修改 D. 头、尾指针可能都要修改 9. 循环队列存储在数组A0m中，则入队时的操作为（ ）。 【中山大学 1999 一、6（1分）】 A. rear=rear+1 B. rear=(rear+1) mod (m-1) C. rear=(rear+1) mod m D. rear=(rear+1)mod(m+1),1.在顺序表中取出第i个元素所花费的时间与i成正比。 （ ） 2.对链表进行插入和删除操作时，不必移动结点。（ ） 3.栈可以作为实现程序设