电子科大数据结构(专)网络教育试卷A3.doc

姓名_ 专业名称_班号_学号_教学中心_ 密 封 线 电子科技大学网络教育考卷（A3卷）(20 年至20 学年度第 学期)考试时间 年 月 日(120分钟) 课程 数据结构(专) 教师签名_ 大题号一二三四五六七八九十合 计得 分一、名词解释(每题2分，共10分) 1. 数据对象答：是性质相同的数据元素的集合，它是数据的一个子集。2. 链表答：以链式结构存储的线性表称之为链表。3. 广义表答：广义表是 n ( 0 )个表元素组成的有限序列 ，记作 LS = (a1, a2, a3, , an)LS 是表名，ai 是表元素，它可以是表 ( 称为子表) ，可以是数据元素( 称为原子) 。n 为表的长度。n = 0 的广义表为空表。4. 连通图答：若图G中任意两个顶点都是连通的，则称G为连通图。5. 最小生成树答：权最小的生成树称为最小生成树。二、判断正误(正确打，错误划，每题1分，共10分)1. 算法时间复杂度是衡量算法性能的唯一标准。()2. 二叉树可以使用顺序存储结构。()3. 图属于线性结构。( )4. 链式存储能够实现随机存取。()5. 深度为k的二叉树至多有2k1个结点。()6. 用邻接矩阵法存储一个图时，在不考虑压缩存储的情况下，所占用的存储空间大小只与图中顶点个数有关，而与图的边数无关( )7. 若以某个顶点开始，对有n个顶点的有向图G进行深度优先遍历，所得的遍历序列唯一，则可以断定其边数为n-1()8. 若一个无向图以顶点V1为起点进行深度优先遍历，所得的遍历序列唯一，则可以唯一确定该图()9. 带权图的最小生成树是唯一的()10. 直接插入排序是一种稳定的排序方法。()三、填空(每空2分，共10分)1. 在一个循环队列中，队首指针指向队首元素的()位置。2. 在具有n个单元的循环队列中，队满时共有()个元素。3. 若图G中每条边都()方向，则G为无向图。4. 图的邻接矩阵是表示()之间相邻关系的矩阵。5. 用邻接表表示图进行广度优先遍历时，通常是采用()来实现算法的。四、选择题(单选或多选)(每题2分，共30分) 1. 用单链表表示的链式队列的队头是在链表的()位置。A. 表尾B. 表头C. 指针域D. 任意2. 在一棵二叉树中，度为0 的结点的个数为n0 ，度为2 的结点的个数为n2 ，则有n0=() A. n2+1B. n2C. n2+2D. n2+33. 一棵有n(n0)个结点的满二叉树共有()个叶子结点A. n+1B. nC. n-1/2D. n+1/24. 关于循环链表的说法正确的是（ ）A. 属于顺序存储结构 B. 属于非线性结构 C.通过任意结点可遍历整个链表 D.能随机存取5. 关于空格串的说法正确的是（ ）A. 由空格字符组成的串 B. 属于空串的一种 C. 串的长度为零D. 只能采用链式存储6. 对于满二叉树，共有n个结点，其中m个叶子结点，深度为h，则()。A. n=h+m B. 2n=h+m C. m=h-1 D. n=2h-17. 设n、m为一棵二叉树上的两个结点，在中根遍历时，n在m之前的条件是()。A. n 在m 右方B. n 是m 的祖先 C. n 在m 左方D. n 是m 的子孙8. 用邻接表表示图进行深度优先遍历时，通常是采用()来实现算法的.A栈 B. 队列 C. 树 D. 图9. 任何一个无向连通图的最小生成树()A. 只有一棵B. 有一棵或多棵 C. 一定有多棵 D. 可能不存在 10. 生成树的构造方法有()。A. 深度优先B. 深度优先和广度优先 C. 无前驱的顶点优先D. 无后继的顶点优先11. 无向图顶点v的度为关联于该顶点()的数目.A. 顶点 B. 边 C. 序号 D. 下标12. 有一个长度为12的有序表，按折半查找法对该表进行查找，在表内各元素等概率的情况下查找成功所需的平均比较次数为()A. 35/12B. 37/12 C. 39/12 D. 43/12。13. 关于广义表的说法正确的有()A. 广义表的长度定义为最外层包含的元素个数B. 广义表的深度定义为所含括弧的重数C. 广义表属于线性结构D. 广义表可递归方式定义14. 关于顺序查找的说法正确的有()A. 可用于顺序存储结构 B. 要求线性表是有序表C. 可用于链式存储结构 D. 平均查找长度为n15. 关于堆排序的说法正确的有()A. 属于交换排序 B. 采用完全二叉树顺序存储结构C. 属于选择排序 D. 堆中任一子树也是堆五、简述题 (每题10分，共30分)1. 数据的逻辑结构主要包括哪几类？答：数据的逻辑结构通常有下列4 类： 集合 ：数据元素之间除了“ 属于同一个集合” 的关系以外，别无其他关系。 线性结构 ：数据元素之间存在一对一的关系。 树型结构 ：数据元素之间存在一对多的关系。 图状结构2.在单链表、双链表和单循环链表中，若仅知道指针p指向某结点，而不知道头指针，能否将结点*p从相应的链表中删去？单链表 每个结点数据结构只有一个指针域，指向下一个结点，没有前驱结点指针，因此不能找到该结点的直接前驱，故无法删除该结点双链表每个结点有两个指针，分别指向直接前驱和直接后继结点，根据指针可以找到该结点的直接前驱和直接后继，因此，能够删除该结点 单循环链表 每个结点只有一个指向直接后继的指针，但尾结点指针不为空，而是指向头结点或链表的第一个结点，因此，根据指针可以进行循环查找，直到找到结点的直接前驱，因此，该结点可以被删除。3. 堆排序有哪些特点？答：堆排序是一种树型选择排序，其特点是：在排序过程中，将R1Rn看成是完全二叉树顺序存储结构， 利用完全二叉树中双亲结点和孩子结点之间的内在关系来选择关键字最大( 或最小) 的记录。六. 程序分析与设计(每题5分，共10分)。1. 设n为正整数，请用大O表示法描述下列程序段的时间复杂度i=1;k=0;while(in)k=k+10*i;i+;. 答：上述程序段中，循环体的执行次数为n ，所以时间复杂度为O(n)。2. 试用顺序表作为存储结构，实现将线性表(a0,a1,an-1)就地逆置的操作，“就地”是指辅助空间应为O(1)。答：