重大2015年数据结构 ( 第3次作业 ).doc

1、 第 3次作业 一、填空题（本大题共 10 分，共 5 小题，每小题 2 分） 1. 多重表文件和倒排文件都归属于 _ 文件。 2. 数据结构被形式地定义为（ D, R），其中 D是 _ 的有限集合， R是 D上的 _ 有限集合。 3. 在栈的出栈操作中，要先判断栈是否空，否则会产生 _ 现象。 4. 在 n个结点的单链表中要删除已知结点 *p，需找到它的 _ ，其时间复杂度为 _ 。 5. 已知一个图的广度优先生成树如右图所示，则与此相应的广度优先遍历序列为 _ 。 二、程序阅读题（本大题共 40分，共 5 小题，每小题 8 分） 1. 求下列广义表运算的结果： head (p,h,w)。

2、2. 指出下述程序段的功能是什么 ? SeqStack S1, S2, tmp; DataType x; ./假设栈 tmp和 S2已做过初始化 while ( ! StackEmpty ( Push( while ( ! StackEmpty ( Push( Push( 3. 写出下列程序段的输出结果（栈的元素类型 SElem Type为 char）。 void main( ) Stack S; Char x,y; InitStack(S); X=c;y=k; Push(S,x); Push(S,a); Push(S,y); Pop(S,x); Push(S,t); Push(S,x); P

3、op(S,x); Push(S,s); while(!StackEmpty(S) Pop(S,y);printf(y); ; Printf(x); 4. 下述算法的功能是什么 ? LinkList Demo(LinkList L) / L 是无头结点单链表 ListNode *Q,*P; if(LL=L-next;P=L; while (P-next) P=P-next; P-next=Q; Q-next=NULL; return L; / Demo 5. 阅读下列 C程序段，写出相应的执行结果 题目： long int fact(n) int n; long f; if(n1)f=n*fac

4、t(n-1); else f=1; return(f); main() int n; long y; n=5; y=fact(n); printf(“%d,%ld n”,n,y); 三、简答题（本大题共 20 分，共 4 小题，每小题 5 分） 1. 链栈中为何不设置头结点 ? 2. 什么是程序的空间复杂度？ 3. 以关键字序列 (265， 301， 751， 129， 937， 863， 742， 694， 076， 438)为例，写出执行快速排序算法的各趟排序结束时，关键字序列的状态。 4. 一棵度为 2的有序树与一棵二叉树有何区别 ? 四、程序设计题（本大题共 20分，共 2 小题，每小

5、题 10 分） 1. 试按照带头结点的线性链表写一算法实现在线性链表 L中查找给定元素的操作。 2. 写出求 BFS生成树的算法。 五、名词解释题（本大题共 10分，共 2 小题，每小题 5 分） 1. 请解释名词 “ 开始结点 ” 2. 请解释名词 “ 数据类型 ” 答案： 一、填空题（ 10 分，共 5 题，每小题 2 分） 1. 参考答案： 多关键字 解题方案： 评分标准： 每空 2分 2. 参考答案： 数据元素，关系 解题方案： 评分标准： 每空 2分 3. 参考答案： 下溢 解题方案： 评分标准： 每空 2分 4. 参考答案： 前驱结点的地址， O（ n） 解题方案： 评分标准： 每

6、空 2分 5. 参考答案： Abefcdg 解题方案： 评分标准： 每空 2分 二、程序阅读题（ 40 分，共 5 题，每小题 8 分） 1. 参考答案： head (p,h,w)=p。 解题方案： 评分标准： 2. 参考答案： 程序段的功能是利用 tmp栈将一个非空栈 s1 的所有元素按原样复制到一个栈s2当中去。 解题方案： 评分标准： 3. 参考答案： 答：输出为 “stack” 。 解题方案： 答：输出为 “stack” 。 评分标准： 5 4. 参考答案： 答：该算法的功能是：将开始结点摘下链接到终端结点之后成为新的终端结点，而 原来的第二个结点成为新的开始结点，返回新链表的头指针。

7、 解题方案： 答：该算法的功能是：将开始结点摘下链接到终端结点之后成为新的终端结点，而 原来的第二个结点成为新的开始结点，返回新 链表的头指针。 评分标准： 5 5. 参考答案： 答：运行结果为： 5， 120 解题方案： 答：运行结果为： 5， 120 评分标准： 5 三、简答题（ 20 分，共 4 题，每小题 5 分） 1. 参考答案： 链栈不需要在头部附加头结点，因为栈都是在头部进行操作的，如果加了头结点，等于要对头结点之后的结点进行操作，反而使算法更复杂，所以只要有链表的头指针就可以了。 解题方案： 评分标准： 2. 参考答案： 答：一个程序的空间复杂度是指程序运行从开始到结束所需的存

8、储量。 定义算法空间复杂度为 S (n) = O (g(n) 表示随着问题规模 n的增大，算法运行所需辅助存储量的增长率与 g(n)的增长率相同。 解题方案： 答：一个程序的空间复杂度是指程序运行从开始到结束所需的存储量。 定义算法空间复杂度为 S (n) = O (g(n) 表示随着问题规模 n的增大，算法运行所需辅助存储量的增长率与 g(n)的增长率相同。 评分标准： 2 2 2 3. 参考答案： 快速排序：（方括号表示无序区，层表示对应的递归树的层数） 初始态： 265 301 751 129 937 863 742 694 076 438 第二层： 076 129 265 751 93

9、7 863 742 694 301 438 第三层： 076 129 265 438 301 694 742 751 863 937 第四层： 076 129 265 301 438 694 742 751 863 937 第五层： 076 129 265 301 438 694 742 751 863 937 第六层： 076 129 265 301 438 694 742 751 863 937 解题方案： 评分标准： 4. 参考答案： 答：一棵度为二的有序树与一棵二叉树的区别在于 : 有序树的结点次序是相对于另一结点而言的，如果有序树中的子树只有一个孩子时，这个孩子结点就无须区分其左右次

10、序， 而二叉树无论其孩子数是否为 2，均需确定其左右次序，也就是说二叉树的结点次序不是相对于另一结点而言而是确定的。 解题方案： 答：一棵度为二的有序树与一棵二叉树的区别在于 : 有序树的结点次序是相对于另一结点而言的，如果有序树中的子树只有一个孩子时，这个孩子结点就无须区分其左右次序， 而二叉树无论其孩子数是否为 2，均需确定其左右次序，也就是说二叉树的结点次序不是相对于另一结点而言而是确定的。 评分标准： 3 3 四、程序设计题（ 20 分，共 2 题，每小题 10 分） 1. 参考答案： 答： bool LocateElem ( OrderedLinkList L, ElemType e

11、, int ( *compare )( ElemType, ElemType ) ) / 若有序链表 L中存在和 e相同的数据元素，则当前指针指向第 1个和 e相同的结点， /并返回 TRUE，否则当前指针指向第一个大于 e 的元素的前驱，并返回 FALSE。 L.current = L.head; L.curPos = 0; while ( L.current - next / 指针后移，继 续查询 L.curPos +; if ( L.current - next L.curPos +; return TRUE; else return FALSE; / 当前指针所指后继元素大于 e /

12、LocateElem 解题方案： 答： bool LocateElem ( OrderedLinkList L, ElemType e, int ( *compare )( ElemType, ElemType ) ) / 若有序链表 L中存在和 e相同的数据元素，则当前指针指向第 1个和 e相同的结点， /并返回 TRUE，否则当前指针指向第一个大于 e 的元素的前驱，并返回 FALSE。 L.current = L.head; L.curPos = 0; while ( L.current - next / 指针后移，继续查询 L.curPos +; if ( L.current - ne

13、xt L.curPos +; return TRUE; else return FALSE; / 当前指针所指后继元素大于 e / LocateElem 评分标准： 3 3 4 2. 参考答案： 求 BFS生成树 typedef enumFALSE， TRUEBoolean； /FALSE 为 0， TRUE为 1 Boolean visitedMaxVertexNum； /访问标志向量是全局量 void BFSTraverseTREE(ALGraph *G) /求广度优先生成树 (以邻接表表示的图 G)，而以邻接矩阵表示 G 时， /算法完全与此相同 ,只要将 BFSTree(G， i)改为

14、 BFSMTree(G， i)即可 int i； for(i=0;in;i+) visitedi=FALSE； /标志向量初始化 for(i=0;in； i+) if(!visitedi) /vi 未访问过 BFSTree(G， i)； /以 vi为源点开始 BFS搜索 ,求 BFS生成树的边 /BFSTraverse void BFSTree(ALGraph*G， int k) / 以 vk为源点对用邻接表表示的图 G进行广度优先搜索 ,并求出 BFS生成树边 int i； CirQueue Q； /须将队列定义中 DataType 改为 int EdgeNode *p； InitQueue

15、(jn;j+)/依次搜索 vi的邻接点 vj if(G-edgesij=1&!visitedj) /vi未访问 printf(“(%c,%c)n“， G-vexsi,G-vexsj)； /打印边 visitedj=TRUE； EnQueue(&Q， j)； /访问过的 vj人队 /endwhile /BFSMTree 解题方案： 评分标准： 五、名词解释题（ 10 分，共 2 题，每小题 5 分） 1. 参考答案： 开始结点是指链表中的第一个结点，也就是没有直接前趋的那个结点。 解题方案： 评分标准： 2. 参考答案： 数据类型：是一个值的集合以及在这些值上定义的一组操作的总称。通常数据类型可以看作是程序设计语言中已实现的数据结 构。 解题方案： 评分标准：