2007秋数据结构课程考试试题.docVIP

数据结构课程考试试题 分数 专业班级 学号 姓名 (20分)简答题 排序的主要功能是什么？排序的目的是什么？主要的排序方法可以分为哪几类？ 数据结构描述数据元素之间的相互关系, 它可以分为那几种类型的结构? 线性数据结构有什么特点？ 简述线性表、栈和队列的联系与区别。 分别给出具有3个结点的树和二叉树的所有形态。 简述图的广度优先有哪些信誉好的足球投注网站和深度优先有哪些信誉好的足球投注网站算法的思想。 (15分)若对长度为n的有序的顺序表和无序的顺序表分别进行顺序查找，在下列三种情况下分别讨论两者在等概率时的平均查找长度是否相同？ 查找不成功，即表中没有关键字等于给定值K的记录； 查找成功，且表中只有一个关键字等于给定值K的记录； 查找成功，但表中有若干个关键字等于给定值K的记录，要求一次查找要求能找出所有的记录。（此时的平均查找长度应考虑找到所有记录时所用的全部比较次数） (10分)简述以下算法的功能： Status Algorithm(LinkedList L) /* L是无表头结点的单链表 */ { LinkedList P,Q; if ( L L-Next) { Q = L; L = L-Next; P = L; while (P-Next) P = P-Next; P-Next = Q; Q-Next = NULL; } return OK; } (15分)对于下面的图， 用邻接表表示该图； 分别给出该图的深度优先有哪些信誉好的足球投注网站和广度优先有哪些信誉好的足球投注网站的输出； 给出该图的最小生成树； 该图存在关节点吗？  (10分) 一个循环队列，现用一个元素个数为MaxQueueLen的一维数组来存储该队列，试分别给出该队列满、队列空的判断条件。 (10分)算法设计题：试编写一个算法判定一给定的二叉树是否为完全二叉树。（自已定义树的存储结构，不得使用递归算法） (10分)对于一个对称矩阵，其元素均为正整数。试设计一个存储空间最节省的存储该矩阵的方法，并给出访问该矩元素aij 的方法。  (10分)下面是某种排序算法的伪代码， void Sorting(SqlList *L) /* 对顺序表用某种算法进行排序 */ { int i, j; for (i=2; i=L-.Length; ++i) { if (L-r[i].key L-r[i-1].Key) { L-r[0] = L-r[i]; L-r[i] = L-r[i-1]; for ( j=i-2; L-r[0].keyL-r[j].key); --j) L-r[j+1] = L-r[j]; L-r[j+1] = L-r[0]; } } } 试回答下列问题： 指出该算法的名称； 运用该算法，给出对顺序表(49, 38, 65, 97, 76, 13, 27, 49)进行排序的过程。 V41 V71 V61 V51 V11 V21 V31 V11