《数据结构》重修试卷(可打印修改).pdf

第 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=,B)D=d1,d2,d3,d4 R=,C)D=d1,d2,d3,d4 R=,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 个结点的单链表存储中，算法的时间复杂度是 O（1）的操作是（）。A）访问第 i 个结点（1in）B）在第 i 个结点后插入一个新结点（1in）得分第 2 页 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，则通过栈调度后不可能存在的输出序列有（）。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从未排序序列中挑选元素，并将其依次插入已排序序列（初始时为空）的一端的方法，称为（）。A)希尔排序 B)归并排序 C)插入排序 D)选择排序14堆的形状是一棵（）。第 3 页 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)一个有限数据元素序列，允许是空 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 的子结点（1im）。供选择的答案：A)有 0 个或 1 个 B)有 0 个或多个 C)有且只有 1 个 D)有 1 个或 1 个以上:A)互不相交 B)允许相交 第 4 页 C)允许叶结点相交 D)允许树枝结点相交二、填空题（20 分）共 12 个小题，20 个空，每空 1 分。1数据结构按物理存储结构划分为 、和索引存储。2在树型结构中，树根结点没有 结点，其余每个结点有且只有 个前驱结点；叶子结点没有 结点，其余每个结点的后续结点数可以3向一个长度为 n 的线性表中删除第 i 个元素(1in)时，需向前移动 个元素。4 是被限定为只能在表的一端进行插入运算，在表的另一端进行删除运算的线性表。5子串的定位运算称为串的模式匹配；称为目标串，称为模式。6三元素组表中的每个结点对应于稀疏矩阵的一个非零元素，它包含有三个数据项，分别表示该元素的 、和 。7一棵深度为 6 的满二叉树有 个分支结点和 个叶子。8设一棵完全二叉树有 70 个结点，则共有 个叶子结点。9N 个结点的完全二叉树的深度为 。10无向图 G 用邻接表矩阵存储，其第 i 行的所有元素之和等于顶点 i 的 。11n 个顶点 e 条边的图采用邻接矩阵存储，广度优先遍历算法的时间复杂度为 ；若采用邻接表存储，该算法的时间复杂度为 。得分第 5 页 12在具有 n 个单元的循环队列中，队满时共有 个元素。三、判断题（10 分）共 10 个小题，每题 1 分，在括号里打或。（）1.链表的每个结点中都只包含一个指针。（）2.链表的删除算法很简单，因为当删除链中某个结点后，计算机会自动将后续各个单元向前移动。（）3.顺序存储方式的特点是存储密度大，且插入、删除运算效率底。（）4.线性表在顺序存储时，逻辑上相邻的元素未必在存储的物理位置次序上相邻。（）5.队列是一种插入与删除操作分别在表的两端进行的线性表，是一种先进后出型结构。（）6.栈和队列的存储方式既可是顺序方式，也可是链接方式。（）7.二叉树中每个结点的两棵子树的高度差等于 1。（）8.二叉树中每个结点有两棵非空子树或有两棵空子树。（）9.具有 24 个结点的完全二叉树有 12 个度为 2 的结点。（）10.归并排序是简单选择排序的改进算法。四、简答分析题（25 分）共 5 个小题，每题 5 分。得分得分第 6 页 1画出下列树对应的二叉数。(5 分)2如图所示二叉树，请写出其先序、中序和后序的遍历序列，然后再图上画出其中序遍历的线索二叉数示意图。(5 分)3已知一个 AOE 网，其中 v0 为源点，v8 为汇点。请求出汇点的最早发生时间，并画出关键路径。（5 分）HDMBINCXG4V4V0V1V5V6V8V7V3V25637922629547第 7 页 4已知如图所示的无向连通图，请画出该图邻接矩阵存储结果示意图。（5 分）5假设用于通信的电文仅由 6 个字母(A、B、C、D、E、F)组成，字母在电文中出现的频率分别为 0.07，0.19，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 )L=M+1;ElseH=M-1;return false;说明：线性表的结构定义如下：typedef struct ElemTpye elemMaxSize;/存储元素 int length;/线性表的长度 SStable;2写出求二叉树深度的算法（5 分）已知二叉树结点的结构声明如下：typedef struct node datatype data;/结点值 struct node *lchild,*rchild;/指针BiTree;3已知顺序存储 n 个元素，编写实现排序的算法，要求采用交换排序方式来实现。（5分）typedef int keyType;/定义关键字类型为整数类型 typedef struct 第 9 页 KeyType key;/关键字项 infoType otherinfo;/其它项 RedType;/记录类型Typedef struct RedType r100;int length;/顺序表长度 SqlList;/顺序表类型其中数组的 0 号单元不存在数据。4编写一个算法实现算术表达式求值。（10 分）说明：涉及的堆栈的函数和判断 C 是否包含在 OP 运算符号中函数 IN(c,oP)，判断运算符的优先级函数 Precede(theta1,theta2)和计算结果函数 Opertate(a,theta,b)直接使用。