数据结构清考试卷.doc

班级：考位号：装订线（答题不得超过此线）学号：姓名：200 年 月 日 考试 (查) 用 XXXXXXXXXX课程考试试卷 课程名称：数据结构 考试形式：（开、闭卷）题 号一二三总分应得分402040100实得分评卷人一、单项选择题（每小题2分，共40分）1. 数据结构是指（ ）。A.数据元素的组织形式B.数据类型C.数据存储结构 D.数据定义2. 树形结构是数据元素之间存在一种（ ）。A.一对一关系B.多对多关系 C.多对一关系D.一对多关系3. 线性表是_。A一个有限序列，可以为空B一个有限序列，不可以为空C一个无限序列，可以为空D一个无限序列，不可以为空4. 在一个长度为n的顺序表中删除第i个元素(0=inext=p-next-next;Bp=p-next;Cp=p-next-next; Dp-next=p;6. 设有一个栈，元素的进栈次序为A, B, C, D, E,下列是不可能的出栈序列_。AA, B, C, D, E BB, C, D, E, ACE, A, B, C, D DE, D, C, B, A 4考试过程中不得将试卷拆开 第 页（共 页）XXXXXXXXXX课程考试试卷7. 两个字符串相等的条件是（ ）。A.两串的长度相等 B.两串包含的字符相同C.两串的长度相等，并且两串包含的字符相同D.两串的长度相等，并且对应位置上的字符相同8. 已知二维数组A1010中，元素a20的地址为560，每个元素占4个字节，则元素a10的地址为（ ）。A.520B.522C.524D.5189. 通常对数组进行的两种基本操作是（ ）。A.建立与删除B.索引和修改 C.查找和修改 D.查找与索引10. 在一棵度为3的树中，度为3的结点数为2个，度为2的结点数为1个，度为1的结点数为2个，则度为0的结点数为（ ）个。A. 4B. 5C. 6D. 711. 假设在一棵二叉树中，双分支结点数为15，单分支结点数为30个，则叶子结点数为（ ）个。A. 15B. 16C. 17D. 4712. 假定一棵三叉树的结点数为50，则它的最小高度为（ ）。A. 3 B. 4C. 5D. 613. 在一棵二叉树上第4层的结点数最多为（ ）。A. 2B. 4 C. 6D. 814. 在一个具有n个顶点的有向图中，若所有顶点的出度数之和为s，则所有顶点的入度数之和为()。A. sB. s-1C. s+1D. n 15. 由一个具有n个顶点的连通图生成的最小生成树中，具有( )条边。A. n B. n-1 C. n+1 D. 2n16. 若查找每个元素的概率相等，则在长度为n的顺序表上查找任一元素的平均查找长度为()。A. nB. n+1C. (n-1)/2D. (n+1)/217. 对于顺序存储的有序表(5,12,20,26,37,42,46,50,64)，若采用折半查找，则查找元素26的比较次数为()。A. 2 B. 3 C. 4 D. 518. 若对n个元素进行直接插入排序，在进行第i趟排序时，假定元素ri+1的插入位置为rj，则需要移动元素的次数为（ ）。A. j-i B. i-j-1 C. i-j D. i-j+1 19. 若一个元素序列基本有序，则选用（ ）方法较快。 A. 直接插入排序 B. 简单选择排序 C. 堆排序 D. 快速排序20. 在平均情况下速度最快的排序方法为（ ）。 A. 简单选择排序 B. 归并排序 C. 堆排序 D. 快速排序二、填空题 （每空1分，共20分）1. 线性结构反映结点间的逻辑关系是_的，非线性结构反映结点间的逻辑关系是_的。2. 一个算法的效率可分为_效率和_效率。3. 线性表是一种典型的_结构。4. 线性表、栈和队列都是_结构，可以在线性表的_位置插入和删除元素；对于栈只能在_位置插入和删除元素；对于队列只能在_位置插入元素和在_位置删除元素。5. 空串是指_，空格串是指_。6. 数组A110，-26，28以行优先的顺序存储，设第一个元素的首地址是100，每个元素占3个存储长度的存储空间，则元素A5，0，7的存储地址为_。7. 由带权为3，9，6，2，5的5个叶子结点构成一棵哈夫曼树，则带权路径长度为_。8. 一棵深度为k的满二叉树的结点总数为_，一棵深度为k的完全二叉树的结点总数的最小值为_，最大值为_。9. 对于一棵具有n个结点的二叉树，若一个结点的编号为i(1in)，则它的左孩子结点的编号为_，右孩子结点的编号为_，双亲结点的编号为_。三、应用题（每小题10分，共40分）1. 已知用一维数组存放的一棵完全二叉树：ABCDEFGHIJKL，写出该二叉树的先序、中序和后序遍历序列。2给定一组权值（5，9，11，2，7，16），试设计相应的哈夫曼树。3. 已知下图所示的一个