问南广播电视大季现教中心 数据结构（本）形成性考核作业答案 数茄结构（本）作业2 (本部分作业覆盖敏材第35章的内容) 一、单灵选年是 (1)C (2)B (3)A (4》 (5) D (6) A (7) B (8) C (9) (10)C (11)B (12)C (13)B (14)B (15)A (16)C (17)B (18)A (19)C (20)D (21)B (22)D 说明：字串个数为7+6+5+4+3+2+1=28 (23)C (24)B (25)D (26)A (27)C 说明：，0C(a[i])=0C(a[0])+(i-l)R 100L.0C(a[0)(6-1)6 .C(a[0j)=70 (28)D (29)D (30)C (3I)A 说明，若设一个×n的矩阵A,以行序为主序，计算A们[]地址的公式分别为 第1页北6页 版权所有河南电大现教中心植额，都箱dpm恒cm
河南广播电视大学现教中心 第1页 共6页 版权所有 河南电大现教中心范颖，邮箱 fy@open.ha.cn 数据结构（本）形成性考核作业答案 数据结构（本）作业 2 （本部分作业覆盖教材第 3-5 章的内容） 一、单项选择题 （1） C （2） B （3） A （4） C （5） D （6） A （7） B （8） C （9） C （10） C （11） B （12） C （13） B （14） B （15） A （16） C （17） B （18） A （19） C （20） D （21） B （22） D 说明：字串个数为 7+6+5+4+3+2+1=28 （23） C （24） B （25） D （26） A （27） C 说明：∵ LOC（a[i]）= LOC(a[0])+（i-1）*R 100= LOC(a[0])+（6-1）*6 ∴ LOC(a[0])=70 （28） D （29） D （30） C （31） A 说明：若设一个 mn 的矩阵 A，以行序为主序，计算 A[i][j]地址的公式分别为
河南广播电现大学现数中心 10c(i,j)=1.0c(0.0)+(in+j)d ,0C(4,4)=1000+(46+4）*5=1140 (32)D 说明：i≥j时，ai,j对应下标为i(i-1)/2+j 1(1时.ai,j应下标为j1)/2+1 a9,2的下标：i(i-1》/2+j9*8/2-2-38 二、填空恩 (1)后进先出 (2)下一个 (3)增1增1 (4) 假上溢 (5) 栈是否满 s>top-MAXSD正.】 栈厦指针找顶对应的数组元素栈是否空 ￥30pl 栈顶元素修改栈顶指针 (6)beeda (7) 终止条件递归部分 (8》 LU->front==LU->rear (9) 运算符操作数b+e划 (10)s>next=h: (11)hmh->next (12)r->next-s; (13)ff-> (14)字符 (15)顺序存储方式 链式存储方式 (16)0空格字符的个数 (17)特味稀琉 (18)()()》2 (19)((d.e.) (20)串长度相等且对应位置的字符相等 (21)1(1-10/2-j (22)行下标列下标非零元素值 三、问答题 1、简述栈和一般线性表的区别。 容：候是一种先进后出的线性表。栈的插入和酬除操作都只能在栈顶进行，面一校的线 性表可以在线性表的任何位置进行插入和刷除操作。 2、简述队列和一般线性表的区别。 队列是一种先进先出的线性表，队列的插入只能在队尾进行，队列的副除只能在队头进 行，而一般的线性表可以在线性表的任何位置进行辅入和剩除操作， 3、链栈中为何不设头结点？ 答：因为链栈具在蛙头插入和制除结点，不可能在链表中问插入和别除结点，算法实残 很简单。所以一般不设置头结点。 4、利用一个栈。则： (1)如果输入序列由A,B。C组成，试给出全部可能的输出序列和不可能的输出序列， (2》年果输入序列由A,B,C,D组成，试给出全部可能的输出序列和不可能的输出序列。 第2风共6页 版权所有河南电大现教中心范额，邮箱5@m加m
河南广播电视大学现教中心 第2页 共6页 版权所有 河南电大现教中心范颖，邮箱 fy@open.ha.cn LOC( i, j ) = LOC(0, 0) + ( i*n + j ) * d ∴ LOC( 4, 4 ) = 1000 + ( 4*6 + 4 ) * 5=1140 （32） D 说明：i≥j 时，ai,j 对应下标为 i(i-1)/2+j itop=MAXSIZE-1 栈顶指针 栈顶对应的数组元素 栈是否空 s->top=-1 栈顶元素 修改栈顶指针 （6） bceda （7） 终止条件 递归部分 （8） LU->front==LU->rear （9） 运算符 操作数 ab+c/fde/-- （10） s->next=h; （11） h=h->next; （12） r->next=s; （13） f=f->next; （14） 字符 （15） 顺序存储方式 链式存储方式 （16） 0 空格字符的个数 （17） 特殊 稀疏 （18） （） （（）） 2 （19） （（d,e,f）） （20） 串长度相等且对应位置的字符相等 （21） i(i-1)/2+j （22） 行下标 列下标 非零元素值 三、问答题 1、 简述栈和一般线性表的区别。 答：栈是一种先进后出的线性表，栈的插入和删除操作都只能在栈顶进行，而一般的线 性表可以在线性表的任何位置进行插入和删除操作。 2、 简述队列和一般线性表的区别。 队列是一种先进先出的线性表，队列的插入只能在队尾进行，队列的删除只能在队头进 行，而一般的线性表可以在线性表的任何位置进行插入和删除操作。 3、 链栈中为何不设头结点？ 答：因为链栈只在链头插入和删除结点，不可能在链表中间插入和删除结点，算法实现 很简单，所以一般不设置头结点。 4、 利用一个栈，则： （1）如果输入序列由 A，B，C 组成，试给出全部可能的输出序列和不可能的输出序列。 （2）如果输入序列由 A，B，C，D 组成，试给出全部可能的输出序列和不可能的输出序列
河南广播电视大学现数中心 容： (1)栈的操作特点是后进先出。因此输出序列有： A入，A出，B入，B出，C入C出，输出序列为ABC A入，A出，B入，C入，C出，B出，输出序列为ACB A入，B入，B出，A出，C入，C出，输出序列为BAC. A入，B入，B出。C入，C出，A出，输出序列为BCA。 A入，B入，C入，C出，B出，A出，输出序列为CBA, 由A,B,C组成的数据项，除上述五个不列的组合外，还有一个C,A,B组合。国 不可能先把C出栈，再把A出栈，《A不在栈顶位置)，最后把B出栈，所以序列CAB不 可能由输入序列A,B,C通过栈得到。 (2)按题上述方法，可能的输出序列有： ABCD.ABDC,ACBD.ACDB.ADCB.BACD.BADC.BCAD.BCDA.BDCA. CBAD.CBDA.CDBA.DCBA 不可能的输出序列有， DABC.ADBC.DACB.DBAC.BDAC.DBCA.DCAB.CDAB,CADB.CABD 5、用S表示入栈操作，X表示出栈操作，若元素入栈顺序为1234，为了得到1342出栈顺 序，相应的S和X操作申是什么？ 答：应是SX图SXSXX。各操作结果如下： S1入栈 X1出战 输出序列：1 S2入栈 S3入栈 X3出慢 输出序列：13 S4入栈 X4出钱输出序列：134 X2出栈输出序列：1342 6、有S个元素，其入钱次序为：A,B,C、D、E,在各种可能的出栈次序中。以元素C D最先的次序有爆几个？ 容：从题中可知，要使C第一个且D第二个出战，型是A入找，B入栈，C入栈，C 出栈，D入栈。之后可以有以下几种情况： (1)B出栈，A出慢，E入栈，E出栈，输出序列为：CDBAE, (2)B出栈，E入栈，E出栈，A出栈，输出序列为CDBEA, (3)E入栈，E出栈，B出钱，A出找，输出序列为CDEBA 所以可能的次序有CDBAE,CDBEA,CDEBA 7、写出以下运算式的后最算术运算式 (1)3x2+x-1/%+5 (2)(A+B)C-D(E+F)+G 容：对应的后褪算术运算式 (1)32x+1-5+ (2)AB+CDEF+/G+ 8、简述广义表和线性表的区别和联系。 答：广义表是线性表的的推广，它也是n(0)个元素，品的有限序列，其中 。或者是原子成者是一个广义表。所以，广义表是一种递归数据结构，而线性表没有这种特 性，线性表可以看成广义表的特露情况，当都是原子时，广义表退化成线性表。 第3项共6页 版权所有河南电大规赖中心范霸，配箱5@p鱼m
河南广播电视大学现教中心 第3页 共6页 版权所有 河南电大现教中心范颖，邮箱 fy@open.ha.cn 答： （1）栈的操作特点是后进先出，因此输出序列有： A 入，A 出，B 入，B 出，C 入 C 出，输出序列为 ABC。 A 入，A 出，B 入，C 入，C 出，B 出，输出序列为 ACB。 A 入，B 入，B 出，A 出，C 入，C 出，输出序列为 BAC。 A 入，B 入，B 出，C 入，C 出，A 出，输出序列为 BCA。 A 入，B 入，C 入，C 出，B 出，A 出，输出序列为 CBA。 由 A，B，C 组成的数据项，除上述五个不同的组合外，还有一个 C，A，B 组合。但 不可能先把 C 出栈，再把 A 出栈，（A 不在栈顶位置），最后把 B 出栈，所以序列 CAB 不 可能由输入序列 A，B，C 通过栈得到。 （2）按照上述方法，可能的输出序列有： ABCD，ABDC，ACBD，ACDB，ADCB，BACD，BADC，BCAD，BCDA，BDCA， CBAD，CBDA，CDBA，DCBA。 不可能的输出序列有： DABC，ADBC，DACB，DBAC，BDAC，DBCA，DCAB，CDAB，CADB，CABD 5、 用 S 表示入栈操作，X 表示出栈操作，若元素入栈顺序为 1234，为了得到 1342 出栈顺 序，相应的 S 和 X 操作串是什么？ 答：应是 SXSSXSXX。各操作结果如下： S 1 入栈 X 1 出栈 输出序列：1 S 2 入栈 S 3 入栈 X 3 出栈 输出序列：13 S 4 入栈 X 4 出栈 输出序列：134 X 2 出栈 输出序列：1342 6、 有 5 个元素，其入栈次序为：A、B、C、D、E，在各种可能的出栈次序中，以元素 C、 D 最先的次序有哪几个？ 答：从题中可知，要使 C 第一个且 D 第二个出栈，应是 A 入栈，B 入栈，C 入栈，C 出栈，D 入栈。之后可以有以下几种情况： （1）B 出栈，A 出栈，E 入栈，E 出栈，输出序列为：CDBAE。 （2）B 出栈，E 入栈，E 出栈，A 出栈，输出序列为 CDBEA。 （3）E 入栈，E 出栈，B 出栈，A 出栈，输出序列为 CDEBA 所以可能的次序有：CDBAE，CDBEA，CDEBA 7、 写出以下运算式的后缀算术运算式 （1）3x2+x-1/x+5 （2）（A+B）*C-D/（E+F）+G 答：对应的后缀算术运算式 （1）3x2^*x+1x/-5+ （2）AB+C*DEF+/-G+ 8、 简述广义表和线性表的区别和联系。 答：广义表是线性表的的推广，它也是 n（n>0）个元素 a1 ,a2…ai… an 的有限序列，其中 ai 或者是原子或者是一个广义表。所以，广义表是一种递归数据结构，而线性表没有这种特 性，线性表可以看成广义表的特殊情况，当 ai 都是原子时，广义表退化成线性表
可南广播电视大学现黄中心 四、程序填空题 1.(1)q->front->next"p->next; (2)fee(p): (3)q->rcarq>front 五、综合题 1. 答：出队序列是e2,e4.e3,e6.e5,el的过程： (1)el入栈（栈底到栈质元素是el) (2)e2入栈（栈底到栈暖元素是el,e2) 《3)2出钱（栈底到栈暖元素是e1) (4)e3入栈（栈底到栈项元素是el,e3) (5)4入栈（栈底到栈质元素是cl,e3,e4) (6)c4出栈（栈底到栈溪元素是el,e3) (?)e3出战（栈底到栈顺元素是©l) (8)e5入战（栈底到栈膜元素是el,e5) (9)5入栈（栈底到栈质元素是cl,e5,c5) (10)c6出栈（栈底到栈顶元素是el,e5) (1)e5出栈（栈底到栈项元素是el) (12)1出栈（栈底到栈顶元素是空） 栈中最多时有3个元素，所以栈S的容量至少是3。 2、 算法设计如下： /产只有一个指针过的链式队的基本操作/ #include <stdio.h typedef char elemtype. 0k俨定义链队列结点/ clemtype data. cruct node◆net ypedef struct qucue快定义链飘列数据类裂/ s威ruct node*ear LinkQucue: odnl4ueue(LinkQucue*Q》产初始化队列/ Q(s女ut9guee◆）malloc(sizeof(struct qucue)》, Q-rear-NULL: void enqueue (LinkQueue *Q.elemtype x) 作入队算法 stno水*&'p, g(中uct node◆)malloc(of(struct node)》: 第4顶北6页 版权所有河南电大现教中心范额，起箱dp加面
河南广播电视大学现教中心 第4页 共6页 版权所有 河南电大现教中心范颖，邮箱 fy@open.ha.cn 四、程序填空题 1、 （1）q->front->next=p->next; （2）free（p）; （3）q->rear=q->front 五、综合题 1、 答：出队序列是 e2,e4,e3,e6,e5,e1 的过程： （1）e1 入栈（栈底到栈顶元素是 e1） （2）e2 入栈（栈底到栈顶元素是 e1,e2） （3）e2 出栈（栈底到栈顶元素是 e1） （4）e3 入栈（栈底到栈顶元素是 e1,e3） （5）e4 入栈（栈底到栈顶元素是 e1,e3,e4） （6）e4 出栈（栈底到栈顶元素是 e1,e3） （7）e3 出栈（栈底到栈顶元素是 e1） （8）e5 入栈（栈底到栈顶元素是 e1,e5） （9）e6 入栈（栈底到栈顶元素是 e1,e5,e6） （10）e6 出栈（栈底到栈顶元素是 e1,e5） （11）e5 出栈（栈底到栈顶元素是 e1） （12）e1 出栈（栈底到栈顶元素是空） 栈中最多时有 3 个元素，所以栈 S 的容量至少是 3。 2、 算法设计如下： /*只有一个指针 rear 的链式队的基本操作*/ #include typedef char elemtype; struct node /*定义链队列结点*/ { elemtype data; struct node *next; }; typedef struct queue /*定义链队列数据类型*/ { struct node *rear; } LinkQueue; void initqueue（LinkQueue *Q）/*初始化队列*/ { Q=（struct queue *）malloc（sizeof（struct queue））; Q->rear=NULL; } void enqueue（LinkQueue *Q,elemtype x） /*入队算法*/ { struct node *s,*p; s=（struct node *）malloc（sizeof（struct node））;
河南厂播电现大学现数中心 多>dax if (Q>rear--NULL) 中原为空队时/ Q.Srears; S-PnexE-=s. else 严原队不为空时) pQ>rer>netp指向第一个结点/ Q>ea->next=s伊将s链接到队尾/ Q-rear=s, Q-e指向队尾/ 多>extg oid delqucue(LinkQucue *Q)俨出队算法/ struct node "t. if (Q->rear=-NULL) printf(“队列为空In): return(0》, else if(Q>rer>net一Q>rer)*贝有一个结点时/ FQ->rear. Q->rear-NULL: g有多个结点时 tQ>rear->next; 1指向第一个结点 Q->rear->ncxt-1->next; :引成循环陆/ free (t); elemtype gethead (LinkQucue "Q) 取队首元素算法/ if (Q->rear-NULL) pnt(队列为空n'): clse return (Qrear.>next->data); 第5项共6项 版权所有河南电大现教中心范制，邮箱5@m加m
河南广播电视大学现教中心 第5页 共6页 版权所有 河南电大现教中心范颖，邮箱 fy@open.ha.cn s->data=x; if （Q->rear==NULL） /*原为空队时*/ { Q->rear=s; s->next=s; } else /*原队不为空时*/ { p=Q->rear->next; /*p 指向第一个结点*/ Q->rear->next=s; /*将 s 链接到队尾*/ Q->rear=s; /*Q->rear 指向队尾*/ s->next=p; } } void delqueue（LinkQueue *Q） /*出队算法*/ { struct node *t; if （Q->rear==NULL） { printf（"队列为空!\n"）; return（0）; } else if （Q->rear->next==Q->rear） /*只有一个结点时*/ { t=Q->rear; Q->rear=NULL; } else /*有多个结点时*/ { t=Q->rear->next; /*t 指向第一个结点*/ Q->rear->next=t->next; /*引成循环链*/ } free（t）; } elemtype gethead（LinkQueue *Q） /*取队首元素算法*/ { if （Q->rear==NULL） printf（"队列为空!\n"）; else return（Q->rear->next->data）; }
河南广播电视大学现黄中心 int emptyqucue (LinkQucue*Q) 判断队列是否为空算法司 if(Qrar一NULL)return《1),为空，则返回rue/ else return《0);P不为空，则返回ac/ void dispqueue (LinkQueue *Q) 产显示队列中元素算法/ struct node 'p=Q-rear->next: pin(队列元素.")： while (pl-Q->rear) printf(9%c"-p-d》, p-p-2nexL printf(%en”,p-da）, 六、完成：实验2一一楼、队列、端归程序设计 根据实验要求《见教材P)认真完成本实验，并提交实验报告。 第5页共6页 版权所有河南电大规教中心范隔，配箱5@p鱼田
河南广播电视大学现教中心 第6页 共6页 版权所有 河南电大现教中心范颖，邮箱 fy@open.ha.cn int emptyqueue（LinkQueue *Q） /*判断队列是否为空算法*/ { if （Q->rear==NULL） return（1）; /*为空,则返回 true*/ else return（0）; /*不为空,则返回 flase*/ } void dispqueue（LinkQueue *Q） /*显示队列中元素算法*/ { struct node *p=Q->rear->next; printf（"队列元素:"）; while （p!=Q->rear） { printf（"%c ",p->data）; p=p->next; } printf（"%c\n",p->data）; } 六、完成：实验 2――栈、队列、递归程序设计 根据实验要求（见教材 P203）认真完成本实验，并提交实验报告