《数据结构》重修试卷

1、成都理工大学数据结构重修考试试卷大题一二三四五总分得分得分一、选择题（20分）单项选择题，共19个小题，20个选项，每个选项1分。1. 树型结构是指数据元素之间存在哪种关系。（ ）A）一对多关系 B）多对多关系 C）多对一关系 D）一对一关系2. 数据结构中算法分析的目的是（ ）。A) 找出数据结构的合理性 B) 研究算法中的输入和输出的关系C) 分析算法的效率以求改进 D) 分析算法的易懂性和文档性3数据结构的二元组表示S=（D,R），D表示数据元素，R表示数据关系。下面表示为树型结构的是（ ）。A) D=d1,d2,d3,d4 R=<d1,d2>,<d2,d3>,&

2、lt;d3,d4> ,< d4,d1>B) D=d1,d2,d3,d4 R=<d1,d2>,<d1,d3>,<d3,d4> C) D=d1,d2,d3,d4 R=<d1,d2>,<d1,d3>,>d3,d2> D) D=d1,d2,d3,d4 R=(d1,d2),(d1,d3),(d3,d4),(d4,d2) 4已知C+语言中的字符型数组A45,第一个元素A00的存储单元位置为100，元素A33的存储位置为（ ）A）117 B）118 C）119 D）1205. 在n个结点的单链表存储中，算法的时间复杂度

3、是O（1）的操作是（ ）。A）访问第i个结点（1in）B）在第i个结点后插入一个新结点（1in）C）删除第1个结点 D）在链表最后插入一个结点6. 判定一个队列QU（最多元素为m0）为空队列的条件是( )。A) QU->rearQU->front = m0 B) QU->rear QU->front 1= m0 C) QU->front = QU->rear D) QU->front = QU->rear+17队列中元素的进出原则是（ ）。A) 先进先出 B) 后进先出 C) 空则进入 D) 任意位置8一个字符栈的入栈序列依此为ABDCE，则通过

4、栈调度后不可能存在的输出序列有（ ）。A) ABCDE B) EDCBAC) DBACE D) ACEDB9串是一种特殊的线性表，其特殊性体现在（ ）。A） 可以顺序存储 B） 数据元素是一个字符 C） 可以链式存储 D） 数据元素可以是多个字符10. 有8个结点的无向连通图最少有（ ）条边。A） 5 B） 6 C） 7 D） 8 11广度优先遍历类似于二叉树的（ ）。A) 先序遍历 B) 中序遍历 C) 后序遍历 D) 层次遍历12 对22个记录的有序表作折半查找，当查找成功时，至多需要比较 次关键字。（ ）A) 3 B) 4 C) 5 D) 613从未排序序列中挑选元素，并将其依次插入已排

5、序序列（初始时为空）的一端的方法，称为（ ）。A) 希尔排序 B) 归并排序 C) 插入排序 D) 选择排序14堆的形状是一棵（ ）。A) 二叉排序树 B) 满二叉树 C) 完全二叉树 D) 平衡二叉树15 对有n个记录的表作简单交换排序，在最坏情况下，算法的时间复杂度是A) O(n) B) O(n2) C) O(nlog2n) D) O(n3)16中序遍历二叉树，是指（ ）。A) 先访问根结点，再依次访问左子树和右子树B) 先访问左子树，再访问根结点，然后访问右子树C) 先访问左子树，再访问右子树，然后访问根结点D) 先访问根结点，再依次访问右子树和左子树17线性表指的是（ ）。A) 一个有

6、限数据元素序列，允许是空 B) 一个有限数据元素序列，不能为空 C) 一个无限数据元素序列，允许是空 D) 一个无限数据元素序列，不能为空18. 设矩阵A是一个下三角矩阵，按行序存放在一维数组B 0, n(n-1)/2-1 中，对下三角部分中任一元素ai,j(ij), 在一维数组B中下标k的值是（ ）。A) i(i-1)/2+j-1 B) i(i-1)/2+j C) i(i+1)/2+j-1 D) i(i+1)/2+j19. 树是结点的有限集合，它( )根结点，记为T。其余的结点分成为m（m0）个( )的集合T1，T2，Tm，每个集合又都是树，此时结点T称为Ti的父结点，Ti称为T的子结点（1

7、im）。供选择的答案： A)有0个或1个 B) 有0个或多个 C) 有且只有1个 D) 有1个或1个以上 : A) 互不相交 B) 允许相交 C) 允许叶结点相交 D) 允许树枝结点相交得分二、填空题（20分）共12个小题，20个空，每空1分。1数据结构按物理存储结构划分为 、 、 和索引存储。2在树型结构中，树根结点没有 结点，其余每个结点有且只有 个前驱结点；叶子结点没有 结点，其余每个结点的后续结点数可以3向一个长度为n的线性表中删除第i个元素(1in)时，需向前移动 个元素。4 是被限定为只能在表的一端进行插入运算，在表的另一端进行删除运算的线性表。5子串的定位运算称为串的模式匹配；

8、称为目标串， 称为模式。6三元素组表中的每个结点对应于稀疏矩阵的一个非零元素，它包含有三个数据项，分别表示该元素的 、 和 。7一棵深度为6的满二叉树有 个分支结点和 个叶子。8设一棵完全二叉树有70个结点，则共有 个叶子结点。9N个结点的完全二叉树的深度为 。10无向图G用邻接表矩阵存储，其第i行的所有元素之和等于顶点i的 。11n个顶点e条边的图采用邻接矩阵存储，广度优先遍历算法的时间复杂度为 ；若采用邻接表存储，该算法的时间复杂度为 。12在具有n个单元的循环队列中，队满时共有 个元素。得分三、判断题 （10分）共10个小题，每题1分，在括号里打或×。（ ）1. 链表的每个结点

9、中都只包含一个指针。 （ ）2. 链表的删除算法很简单，因为当删除链中某个结点后，计算机会自动将后续各个单元向前移动。 （ ）3. 顺序存储方式的特点是存储密度大，且插入、删除运算效率底。（ ）4. 线性表在顺序存储时，逻辑上相邻的元素未必在存储的物理位置次序上相邻。（ ）5. 队列是一种插入与删除操作分别在表的两端进行的线性表，是一种先进后出型结构。 （ ）6. 栈和队列的存储方式既可是顺序方式，也可是链接方式。 （ ）7.二叉树中每个结点的两棵子树的高度差等于1。 （ ）8.二叉树中每个结点有两棵非空子树或有两棵空子树。 （ ）9. 具有24个结点的完全二叉树有12个度为2的结点。（ ）1

10、0. 归并排序是简单选择排序的改进算法。得分四、简答分析题（25分）共5个小题，每题5分。1画出下列树对应的二叉数。(5分)2如图所示二叉树，请写出其先序、中序和后序的遍历序列，然后再图上画出其中序遍历的线索二叉数示意图。(5分)HDMBINCXG3已知一个AOE网，其中v0为源点，v8为汇点。请求出汇点的最早发生时间，并画出关键路径。（5分）4V4V0V1V5V6V8V7V3V256379226295474已知如图所示的无向连通图，请画出该图邻接矩阵存储结果示意图。（5分）12435假设用于通信的电文仅由6个字母(A、B、C、D、E、F)组成，字母在电文中出现的频率分别为0.07，0.19，

11、0.02，0.06，0.32，0.03。设计哈夫曼树。五、算法设计题（25分）共4个小题，1、 2、3小题各5分，4小题10分1算法填空(共5个空，每空1分)二分查找排序，实现过程如下：bool Search(SStable S,KeyType key) int L,H,M;L=1;H= ;while (L<=H) M= if ( S.elemM= ) return ; else if ( S.elemM> )L=M+1;ElseH=M-1;return false;说明： 线性表的结构定义如下： typedef struct ElemTpye elemMaxSize; /存储元素

12、 int length; /线性表的长度 SStable;2写出求二叉树深度的算法（5分）已知二叉树结点的结构声明如下：typedef struct node datatype data; /结点值 struct node *lchild, *rchild; / 指针BiTree;3已知顺序存储n个元素，编写实现排序的算法，要求采用交换排序方式来实现。（5分） typedef int keyType; /定义关键字类型为整数类型 typedef struct KeyType key; /关键字项 infoType otherinfo; /其它项 RedType; /记录类型Typedef struct RedTy