数据结构（本）形成性考核作业答案.doc

数据结构（本）形成性考核作业答案 作业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 23．C 24．B 25．D 26．A 27．C 28．D 29．D 30．C 31．A 32．D 二、填空题 1．后进先出 2．下一个 3．增1 增1 4．假上溢 5． 栈是否满 s-top=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操作串是什么？ 答：应是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．写出以下运算式的后缀算术运算式 ⑴ 3x2+x-1/x+5 ⑵ (A+B)*C-D/(E+F)+G 答；对应的后缀算术运算式 ⑴ 3x2^*x+1x/-5+ ⑵ AB+C*DEF+/-G+ 8． 简述广义表和线性表的区别和联系。 答：广义表是线性表的的推广，它也是n(n0)个元素a1