2012-2013数据结构试题12050841.doc

2012-2013 学年 第 2 学期末考试试题（A卷） 课程名称 计算机程序设计基础 使用班级 总分 得分 一、判断题（共20 分 每小题 2分） 1不论是入队操作还是入栈操作，在顺序存储结构上都需要考虑“溢出”情况。（ ） 2当向二叉排序树中插入一个结点，则该结点一定成为叶子结点。（ ） 3完全二叉树中的叶子结点只可能在最后两层中出现。（ ） 4哈夫曼树中没有度数为1的结点。（ ） 5对连通图进行深度优先遍历可以访问到图中的所有顶点。（ ） 6先序遍历一查二叉排序树一定可以得到一个有序序列。（ ） 7线性表中的所有元素都有一个前驱元素和一个后继元素。（ ） 8 满二叉树一定是完全二叉树，完全二叉树不一定是满二叉树。（ ） 9 调用一次深度优先遍历算法可以访问到图中的所有顶点。（ ） 10 栈和队列的共同特点是只允许在表的一端进行插入和删除操作。（ ） 得分 二、运算题（共40 分 ） 1请根据你的理解，给出数据结构的定义。(6分) 2请给出稀疏矩阵的概念，举一实例，并给出此实例的三元组表示。（10分） 3有6个元素A、B、C、D、E、F一次进栈，允许任何时候出栈，能否得到下列的每个出栈序列，若能，给出栈操作的过程，若不能，简述其理由。（10分） CDBEFA (2)ABEDFC (3)DCEABF (4)BAEFCD 4 一个AOV网的二元组表示为： V={0，1，2，3，4，5，6，7，8，9，10} E={0,2,0,4,1,2,1,5,2,4,3,5,4,6,4,7,5,7,6,8,7,6,7,8,7,9,8,10,9,10} 在此AOV网的邻接表存储中，若各顶点邻接表中的边接结点是按照邻接顶点序号从大到小链接的，请写出按此邻接表和介绍的拓扑排序算法得到的拓扑序列。提示：先画出图形再运算。（14分，画出图形得4分，正确写出拓扑序列得10分） 得分 三、算法设计题（40分） 1 从单链表中查找出所有元素的最大值，该值由函数返回，若单链表为空，则显示出错信息并停止运行，设单链表的节点类型为Lnode。（10分） Struct Lnode{ int data; Lnode* next; } 2 从线性表中删除具有最小值的元素并由函数返回，空出的位置由最后一个元素填补，若线性表为空则显示出错信息并退出运行。（10分） 3 已知一个集合中的元素为正整数或负整数，设计一个算法，将正整数和负整数分开，使集合的前部分为负整数，后部分为正整数，不要求对它们排序，但要求尽量减少交换次数。函数原型如下。Void separate(int s[],int n)(10分) 4写出直接插入排序的算法，并用该方法对序列（46，74，16，53，14，26，40，38，86，65，27，34）进行排序。 你一定要坚强，即使受过伤，流过泪，也能咬牙走下去。因为，人生，就是你一个人的人生。 ============================================================================== 命运如同手中的掌纹，无论多曲折，终掌握在自己手中 ==============================================================