东北大学：《数据结构》课程教学资源（学习资料）第三章 参考答案

第三章参考答案 、名词解释(略) 、填空题 1、先进后出、后进先出,后进先出,进栈,入栈,退栈,出栈 2、初始化 Initstack(S)、进栈Push(S,X),退栈Pop(S),读栈顶Top(S),判栈空 Empty(S) 3、下溢 4、上溢 5、顺序、链接 6、栈空、下溢、栈满、上溢 9, sq->data(sq->top), sq->top- sq->top==0, sq->data sq->topl 12 IS=NULL 13、 14、p->data,free(p) *x=Is->data 16、 更小的“尺度”、递归 队、队尾、队头 队列初始化 InitQueue(Q)、入队列 EnQueue(QX)、出队 Out Queue(Q,X)、判队列空 Empty Queue(Q、读队头eadQ,x) 假溢出 21 sq->front, sq->rear=(sq->rear+1)%maxsize, sq->data[ sq->rear]=x 22. sq->rear, sq->fornt=(sq->rear+ 1)%maxsize, *x=sq->data( sq->rear sq rear= sq front 24, sq front, (sq front+ 1)%maxsize 队满、队空 1q->front=p, NULL 27、p-> data,p,lq >rear-p Iq. rear==lq. front 30、p= =lq. front->next* 31 ,读、写 顺序、列序、行序、行、列 特殊、稀疏 n(n+1)/2 i(i-)/2+j当i j(-1)/2+i当i 36、nt+1,(i-1)(2n1+2)2J-i+1

1 第三章 参考答案 一、名词解释（略） 二、填空题 1、 先进后出、后进先出，后进先出，进栈，入栈，退栈，出栈 2、 初始化 InitStack(S)、进栈 Push(S,X), 退栈 Pop(S)，读栈顶 Top(S),判栈空 Empty(S) 3、 下溢 4、 上溢 5、 顺序、链接 6、 栈空、下溢、栈满、上溢 7、 sq->top=0 8、 sq->top++,sq->data[sq->top] 9、 sq->data[sq->top],sq->top— 10、 sq->top= =0 11、 sq->top= =0,sq->data[sq->top] 12、 ls=NULL 13、 p->data=x,ls=p 14、 p->data,free(p) 15、 *x=ls->data 16、 更小的“尺度”、递归 17、 队、队尾、队头 18、 队列初始化 InitQueue(Q)、入队列 EnQueue(Q,X)、出队 OutQueue(Q,X)、判队列空 EmptyQueue(Q)、读队头 ead(Q,x) 19、 假溢出 20、 sq->front=0 21、 sq->front,sq->rear=(sq->rear+1)%maxsize,sq->data[sq->rear]=x 22、 sq->rear,sq->fornt=(sq->rear+1)%maxsize,*x= sq->data[sq->rear] 23、 sq.rear= sq.front 24、 sq.front,(sq.front+1)%maxsize 25、 队满、队空 26、 lq->front=p,NULL 27、 p->data,p,lq->rear=p 28、 *x,s->next 29、 lq.rear= =lq.front 30、 p=lq.front->next,*x 31、 n-1,读、写 32、 顺序、列序、行序、行、列 33、 特殊、稀疏 34、 n(n+1)/2 35、 i(i-1)/2+j 当 i≧j k= j(j-1)/2+i 当 i<j 36、n-t+1,(i-1)(2n-i+2)/2,j-i+1

(i-1)(2n-计+2)2+计+1当i nn+1)/2+1 1)/2+j当ij n(n+1)/2+1 38, col<=a. nu, a data[p].j, q++ 39. col<=a. nu, cpot(col-1+num(col-1, cpot[coll++ 40、先进后出(后进先出) 41、先进先出(后进后出) 42, Is==NULL, x=p->info 43、2230.2374 46、EA+222EA+117 47 48、540,108,M3[10 三、单项选择题 1、④2、①3、④4、①5、③6、②7、①8、③9、④10② ll、②12、③13、①②14、②15、④16、①17、②18、③19、④20、① 21、②22、①23、③24、①25、②26、③27、②28、②29、②30 四、简答及应用 1、顺序栈类型定义如下 define sqstack maxsize顺序栈的容量 typedef struct sqstack Data lype maxsize 它有两个域:data和top。Data为一个一维数组,用于存储栈中元素, DataType为栈元素的 数据类型。Top为int型,它的实际取值范围为0- sqstack maxsize-1 2、链栈的类型定义如下 typedef stuct node t DataType data; 单链表的第一个结点就是链栈栈顶结点,链栈由栈顶指针惟一确定。栈中的其它结点通过它 们的next域链接起来不。栈底结点的next域为NULL 3、顺序队列的类型定义如下 # define maxsize顺序栈的容量 typedef struct sqqueue data mansize int fornt iSqQueueTp

2 (i-1)(2n-i+2)/2+j-i+1 当 i<=j k= n(n+1)/2+1 当 i>j n(n+1)/2+1 37、 (i-1)/2+j 当 i≧j k= n(n+1)/2+1 当 i<j 38、col<=a.nu,a.data[p].j,q++ 39、col<=a.nu,cpot[col-1]+num[col-1],cpot[col]++ 40、先进后出（后进先出） 41、先进先出（后进后出） 42、ls= =NULL,*x=p->info 43、2230,2374 44、n-1 45、栈 46、EA+222,EA+117 47、lq->front->next= =lq->rear 48、540,108,M[3][10] 三、单项选择题 1、④2、①3、④4、①5、③6、②7、①8、③9、④10②、 11、②12、③13、①②14、②15、④16、①17、②18、③19、④20、① 21、②22、①23、③24、①25、②26、③27、②28、②29、②30、③ 31、②32、②33、③34、②35、④ 四、简答及应用 1、顺序栈类型定义如下： #define sqstack_maxsize 顺序栈的容量 typedef struct sqstack {DataType data[sqstack_maxsize]; int top }SqStackTp 它有两个域：data 和 top。Data 为一个一维数组，用于存储栈中元素，DataType 为栈元素的 数据类型。Top 为 int 型，它的实际取值范围为 0~sqstack_maxsize－1。 2、链栈的类型定义如下： typedef stuct node { DataType data; struct node *next; }LstackTp; 单链表的第一个结点就是链栈栈顶结点，链栈由栈顶指针惟一确定。栈中的其它结点通过它 们的 next 域链接起来不。栈底结点的 next 域为 NULL。 3、顺序队列的类型定义如下： #define maxsize 顺序栈的容量 typedef struct sqqueue {DataType data[maxsize]; int fornt,rear }SqQueueTp

SqQueueTp 该类型变量有三个域:data, front rear。其中data存储队中元素的一维数组。队头指针 front 和队尾指针rear定义为整型变量,实际取值范围为0~ maxsize-1。 循环队列的类型定义如下 #define maxsize 循环队的容量 typedef struct cycqueue( Data Type data( maxsize] I CycqueueTp 4 typedef struct linked queue i Data Type data; i LqueueTp typedef struct queueptr i LqueueTp *front, *rear; P QueptrTp ueptrTp lq 5、# define maxnum 非零元素的容量 typedef struct node Int 1,;/*非零元素所在的行号、列号*/ Data lype v,/*非零元素的值* ANODE typedef struct smatrix Int mu,nu,tu,/*行数、列数、非零元素的个数 NODE data maxnum+1]}/*这里假定三元组的下标的起始值为1*/ 6、 int length( flen=(sq. rear-sq front+maxsize)%m return(len) 7、1234、4321、2143、3421、3241、1324、1432、1342、1243、3214、2134、2314、2341、 2431 1(2n-计+1)/2当i fI(i= 当 当i三j 当 n(n+1)2+1当pj 9、(1)k=2i+j-2;(iJ=1,2,…n) (2)F=ceil((k+1)/3) j=floor(k/)+k mod 3 10、运行结果: ABCDEFGHIJKLM

3 SqQueueTp sq; 该类型变量有三个域：data,front,rear。其中 data 存储队中元素的一维数组。队头指针 front 和队尾指针 rear 定义为整型变量，实际取值范围为 0~maxsize－1。 循环队列的类型定义如下： #define maxsize 循环队的容量 typedef struct cycqueue{ DataType data[maxsize] Int front,rear }CycqueueTp; CycqueueTp sq; 4、typedef struct linked_queue { DataType data; struct linked_queue *next; }LqueueTp; typedef struct queueptr { LqueueTp *front, *rear; }QueptrTp; QueptrTp lq; 5、#define maxnum 非零元素的容量 typedef struct node { int i,j ; /*非零元素所在的行号、列号*/ DataType v; /*非零元素的值*/ }NODE; typedef struct spmatrix { int mu,nu,tu; /*行数、列数、非零元素的个数*/ NODE data[maxnum+1];/*这里假定三元组的下标的起始值为 1*/ }SpMatrixTp 6、int length(CycqueueTp sq) {len=(sq.rear-sq.front+maxsize)%maxsize; return(len); } 7、1234、4321、2143、3421、3241、1324、1432、1342、1243、3214、2134、2314、2341、 2431 8、 i(2n-i+1)/2 当 i<=j f1(i)= 0 当 i>j j 当 i<=j f2 (j)= 0 当 i>j -n 当 i<=j c= n(n+1)/2+1 当 i>j 9、(1)k=2i+j-2; (i,j=1,2,…..n) (2)i=ceil((k+1)/3) j=floor(k/3)+k mod 3 10、运行结果：ABCDEFGHIJKLM

MLKJIHGFEDCBA l1、借助栈将一个带头结点的单链表倒置 Iop>区s Top-> 调用f(5)前调用f(5)前调用f(4)前调用f(3)前调用f(2)前调用f(1)前 ToD-> 返回f(1)后 返回f(2)后返回 返回f(4)后运回f5)后 五、算法设计 1.本程序中,将客车类定义一个队KE,货车类定义一个队HE,过江渡船定义成一个栈 DC。栈采用顺序存储结构,队采用链式存储结构。 #define sqstack maxsize 10 typedef struct sqstack Data Type data( sqstack maxsize] i SqStackTp typedef struct linked queue i Data lype data; struct linked queue "next G Queue typedef struct queueptr QueptrTp int InitStack (SqStackTp *sq) (sq->top=0; return(1); void Init Queue( QueptrTp "lp) ueue p=(lqueueTp *)malloc(sizeof(lqueueTp)) lq->rear=p;

4 MLKJIHGFEDCBA 11、借助栈将一个带头结点的单链表倒置。 12- Top-> Top-> Top-> Top-> Top-> Top-> 1 r’’’’ 2 r’’’ 2 r’’’ 3 r’’ 3 r’’ 3 r’’ 4 r’ 4 r’ 4 r’ 4 r’ 5 r 5 r 5 r 5 r 5 r 调用 f(5)前 调用 f(5)前 调用 f(4)前 调用 f(3)前 调用 f(2)前 调用 f(1)前 Top-> Top-> Top-> Top-> Top-> 2 r’’’ 3 r’’ 3 r’’ 4 r’ 4 r’ 4 r’ 5 r 5 r 5 r 5 r 返回 f(1)后 返回 f(2)后 返回 f(3)后 返回 f(4)后 返回 f(5)后 五、算法设计 1．本程序中，将客车类定义一个队 KE，货车类定义一个队 HE，过江渡船定义成一个栈 DC。栈采用顺序存储结构，队采用链式存储结构。 #define sqstack_maxsize 10 typedef struct sqstack {DataType data[sqstack_maxsize]; int top; }SqStackTp; typedef struct linked_queue {DataType data; struct linked_queue *next; }LqueueTp; typedef struct queueptr {LqueueTp *front,*rear; }QueptrTp; int InitStack(SqStackTp *sq) {sq->top=0; return(1);} void InitQueue (QueptrTp *lp) {LqueueTp *p; p=(LqueueTp * )malloc(sizeof(LqueueTp)); lq->front=p; lq->rear=p;

( lq->front) ULL. int Qut Queue( QueptrTp *lp, Data Type*x) queueT if(lq→ front==lq>rear){eror(“队空”); return(O), else (s=(lq->front)->nest (1q->front)->next=s->next; if(s->next== NULL) lq->rear=llq->front free(s) return(1); int Empty Queue(Queptr Tp Iq) fif(lq. rear=lq front )return(1) int Push(SqStackTp *sq, Data Type x) f if(sq->top==sqstack maxsize-q)(return(0) else (sq->top++; sq->data(sq->top=x return(1); i oid maino SqStackTp DO,∥DC表示渡船 QueptrtTp KE,H;∥KE表示客车E、HE表示货车 Intt j=0 Initstack(DC) While(dc. top<sqstack maxsize) for(=j<=4I++)∥先上4辆客车 if (lemptyqueue(KE)&&(DC. top <sqstack maxsize) f outqueue(&KE, &t); Push(&DC, t ) ;j++ for(l=j<5,++)再上1辆货车或客车不足时用货车补足 if (lemptyqueue(HE)&&(DC. top< sqstack maxsize) foutqueue(&HE, &t); Push(&DC, t); j++ f(<5)for(1=j<5,I++)∥当货车不足时用客车补足 f(lemptyqueue( KE)&&(DC. top <sqstack maxsize)) foutqueue(&Ke, &t); Push( &DC, t); j++ else printf(“客车、货车合计不足10辆!”); 2. typedef struct dustack Data Typeelem[1: MI

5 ( lq->front)->next=NULL; } int QutQueue(QueptrTp *lp,Data Type *x) {LqueueTp *s; if (lq->front==lq->rear) {error(“队空”);return(0);} else {s=(lq->front)->nest; *x=s->data; (lq->front)->next=s->next; if (s->next == NULL) lq->rear=llq->front; free(s); return(1); } } int EmptyQueue(QueptrTp lq) {if (lq.rear==lq.front) return(1); return(0); } int Push (SqStackTp *sq , DataType x) { if (sq ->top = =sqstack_maxsize-q) {return(0);} else {sq ->top++; sq->data[sq->top]=x; return(1);} } void main() { SqStackTp DC; //DC 表示渡船 QueptrtTp KE ,HE; // KE 表示客车 E、HE 表示货车 Int t ,j=0; Initstack(DC); Initqueue(KE); Initqueue(HE); While(DC.top<sqstack_maxsize) {j=o; for (I=I;j<=4;I++) //先上 4 辆客车 if (!emptyqueue(KE)&&(DC.top <sqstack_maxsize)) { outqueue (&KE, &t);Push (&DC, t ); j++:} for (I=j;I<5;I++) //再上 1 辆货车或客车不足时用货车补足 if (!emptyqueue(HE)&& (DC.top < sqstack _maxsize)) {outqueue(&HE,&t); Push(&DC, t);j++;} if (j<5) for (I=j;I<5;I++) // 当货车不足时用客车补足 if (!emptyqueue(KE)&&(DC.top <sqstack_maxsize)) {outqueue(&KE,&t);Push (&DC,t ) ; j++} else printf (“客车、货车合计不足 10 辆！”); } } 2.typedef struct dustack {DataTypeelem[1:M];