2018年电大考试数据结构复习题填空题小抄.doc

电大数据结构复核习题（填空题）1、 在一个长度为n的顺序存储结构的线性表中，向第i(1in+1)个元素之前插入新元素时，需向后移动 n-i+1 个数据元素。2、 从长度为n的采用顺序存储结构的线性表中删除第i(1in+1)个元素 ，需向前移动 n-i 个元素。3、 数据结构按结点间的关系，可分为4种逻辑结构： 集合 、 线性结构 、 树形结构 、 图状结构 。4、 数据的逻辑结构在计算机中的表示称为 物理结构 或 存储结构 。5、 除了第1个和最后一个结点外，其余结点有且只有一个前驱结点和后继结点的数据结构为 线性结构 ，每个结点可有任意多个前驱和后继结点数的结构为 非线性结构 。6、 算法的5个重要特性是 有穷性 、 确定性 、 可形性 、 有零个或多个输入 、 有零个或多个输出 。7、 数据结构中的数据元素存在多对多的关系称为 图状结构 结构。8、 数据结构中的数据元素存在一对多的关系称 树形结构 结构。9、 数据结构中的数据元素存在一对一的关系称为 线性结构 结构。10、 要求在n个数据元素中找其中值最大的元素，设基本操作为元素间的比较。则比较的次数和算法的时间复杂度分别为 n-1 和 O(n) 。11、 在一个单链表中p所指结点之后插入一个s所指结点时，应执行_s-next=p-next;_和p-next=s;的操作。12、 设有一个头指针为head的单向循环链表，p指向链表中的结点，若p-next= = head ，则p所指结点为尾结点。13、 在一个单向链表中，要删除p所指结点，已知q指向p所指结点的前驱结点。则可以用操作 q-next=p-next; 。14、 设有一个头指针为head的单向链表，p指向表中某一个结点，且有p-next= =NULL,通过操作 p-next=head; ,就可使该单向链表构造成单向循环链表。15、 每个结点只包含一个指针域的线性表叫 单链表 。16、 线性表具有 顺序存储 和 链式存储 两种存储结构。17、 数据的逻辑结构是从逻辑关系上描述数据，它与数据的关系 存储结构 无关，是独立于计算机的。18、 在双向循环链表的每个结点中包含 两个 指针域，其中next指向它的 直接后继 ，prior指向它的 直接前驱 ，而头结点的prior指向 尾结点 ，尾结点的next指向 头结点 。19、 单向循环链表是单向链表的一种扩充，当单向链表带有头结点时，把单向链表中尾结点的指针域由空指针改为 头结点的指针 ；当单向链表不带头结点时，则把单向链表中尾结点的指针域由空指针改为指向 指向第一个结点的指针 。20、 线性链表的逻辑关系时通过每个结点指针域中的指针来表示的。其逻辑顺序和物理存储顺序不再一致，而是一种 链式 存储结构，又称为 链表 。21、 栈是限定在表的一端进行插入和删除操作的线性表，又称为 后进先出表 。22、 队列的特性是 先进先出表 。23、 往栈中插入元素的操作方式是：先 移动栈顶指针 ，后 存入元素 。24、 删除栈中元素的操作方式是：先 取出元素 ，后 移动栈顶指针 。25、 循环队列队头指针在队尾指针 下一个 位置，队列是“满”状态26、 在队列的顺序存储结构中，当插入一个新的队列元素时，尾指针 增1 ，当删除一个元素队列时，头指针 增1 。27、 循环队列的引入，目的是为了克服 假上溢 。28、 向顺序栈插入新元素分为三步：第一步进行 栈是否满 判断，判断条件是 s-top=MAXSIZE-1 ；第二步是修改 栈顶指针 ；第三步是把新元素赋给 栈顶对应的数组元素 。同样从顺序栈删除元素分为三步：第一步进行 栈是否空 判断，判断条件是 s-top=-1 。第二步是把 栈顶元素 ；第三步 修改栈顶指针 。29、 假设以S和X分别表示入栈和出栈操作，则对输入序列a,b,c,d,e一系列栈操作SSXSXSSXXX之后，得到的输出序列为 bceda 。30、 一个递归算法必须包括 终止条件 和 递归部分 。31、 判断一个循环队列LU（最多元素为m0）为空的条件是 LU-front=LU-rear 。32、 在将中缀表达式转换成后缀表达式和计算后缀表达式的算法中，都需要使用栈，对于前者，进入栈中的元素为表达式中的 运算符 ，而对于后者，进入栈的元素为 操作数 ，中缀表达式(a+b)/c-(f-d/c)所对应的后缀表达式是 ab+c/fde/- 。 33、 向一个栈顶指针为h的链栈中插入一个s所指结点时，可执行 s-next=h; 和h=s;操作。(结点的指针域为next)。34、 从一个栈顶指针为h的链栈中删除一个结点时，用x保存被删结点的值，可执行x=h-data;和 h=h-next; 。(结点的指针域为next)35、 在一个链队中，设f和r分别为队头和队尾指针，则插入s所指结点的操作为 r-next=s; 和r=s; (结点的指针域为next)36、 在一个链队中，设f和r分别为队头和队尾指针，则删除一个结点的操作为 f=f-next; 。 (结点的指针域为next)37、 串是一种特殊的线性表，其特殊性表现在组成串的数据元素都是 字符 。38、 串的两种最基本的存储方式是 顺序存储方式 和 链式存储方式 。39、 空串的长度是 0 ；空格串的长度是 空格字符的个数 。40、 需要压缩存储的矩阵可分为 特殊 矩阵和 稀疏 矩阵两种。41、 设广义表L=（），（），则表头是 （） ，表尾是 （） ，L的长度是 2 。42、 广义表A（a,b,c）,(d,e,f)）的表尾为 （d,e,f） 。43、 两个串相等的充分必要条件是 串长度相等且对应位置的字符相等 。44、 设有n阶对称矩阵A，用数组s进行压缩存储，当ij时，A的数组元素aij相应于数组s的数组元素的下标为 i(i-1)/2+j 。（数组元素的下标从1开始）。45、 对稀疏矩阵进行压缩存储，矩阵中每个非零元素对应的三元组包括该元素的 行下标 、 列下标 和 非零元素值 三项信息。46、 结点的度是指结点所拥有的 子树树木或后继结点数 。47、 树的度是指 树中所有结点的度的最大值 。48、 度大于0的结点称作 分支结点 或 非终端结点 。49、 度等于0的结点称作 叶子结点 或 终端结点 。50、 在一棵树中，每个结点的 子树的根 或者说每个结点的 后继结点 称为该结点的 孩子结点 ，简称为孩子。51、 一个结点称为其后继结点的 双亲结点（简称双亲） 。52、 具有 同一双亲 的结点互称为兄弟结点，简称为兄弟。53、 每个结点的所有子树中的结点被称为该结点的 子孙 。54、 从根结点到该结点所经分支上的所有结点称为该结点的 祖先 。55、 树的深度或高度是指 树中结点的最大层数 。56、 m(m0)棵互不相交的树的集合称为 森林 。57、 度为k的树中的第i层上最多有 Ki-1 结点。 58、 深度为k的二叉树最多有 2k-1 结点。59、 在一棵二叉树中，如果树中的每一层都是满的，则称此树为 满二叉树 ；但如果出最后一层外，其余层都是满的，并且最后一层是满的，或者是在缺少若干连续个结点，则称此二叉树为 完全二叉树 。60、 具有n个结点的完全二叉树的深度是。61、 先序遍历二叉树的的操作定义为；若二叉树为空，则为空操作，否则进行如下操作，访问二叉树的 根结点 ；先序遍历二叉树的 左子树 ，先序遍历二叉树的 右子树 。62、 中序遍历二叉树的的操作定义为；若二叉树为空，则为空操作，否则进行如下操作，中序遍历二叉树的 左子树 ；访问而叉树的 根结点 ，中序遍历二叉树的 右子树 。63、 后序遍历二叉树的的操作定义为；若二叉树为空，则为空操作，否则进行如下操作，后序遍历二叉树的 左子树 ；后序遍历二叉树的 右子树 ，访问而叉树的 根结点 。64、 将树中结点赋上一个有着某种意义的实数，称此实数为该结点的 权 。65、 树的带权路径长度为树中所有叶子结点的 带权路径长度之和 。66、 哈夫曼树又称为 最优二叉树 ，它是n个带权叶子结点构成的所有二叉树中带权路径长度WPL 最小的二叉树 。67、 若以4，5，6，7，8作为叶子结点的权值构造哈夫曼树，则其带权路径长度是 69 。68、 具有m个叶子结点的哈夫曼树共有 2m-1 结点。69、 在图中，任何两个数据元素之间都可能存在关系，因此图的数据元素之间是一种 多对多 的关系。70、 图的邻接矩阵表示法是用一个 二维数组 来表示图中顶点之间的相邻关系。71、 邻接表是图中的每个顶点建立一个邻接关系的 单链表 。72、 图的遍历是从图的某一顶点出发，按照一定的搜索方法对图中 所有顶点 各做 一次 访问的过程。73、 图的深度优先搜索遍历类似于树的 先序 遍历。74、 图的广度优先搜索类似于树的 按层次 遍历。75、 具有n个顶点的有向图的邻接矩阵，其元素个数为 n2 。76、 具有n个顶点的无向图至少有 条边，才能确保其为一个连通图。77、 图常用的两种存储结构是 邻接矩阵 和 邻接表 。78、 一个AOV网（顶点活动图）应该是一个 有向无环图 。即不应该带有回路，否则回路上的所有活动都 无法进行 。79、 用邻接矩阵存储有向图G，其第i行的所有元素之和等于顶点i的 出度 。80、 在有n个顶点的有向图中，每个顶点的度最大可达 2(n-1) 。81、 在一个带权图中，两顶点之间的最段路径最多经过 n-1 条边。82、 为了实现图的深度优先搜索遍历，其非递归的算法中需要使用的一个辅助数据结构为 栈 。83、 在各种查找方法中，平均查找长度与结点个数n无关的查找方法是 哈希表查找法 。84、 如果对查找表只进行查询某个特定的数据元素是否在查找表中，以及查找某个特定数据元素的各种属性两种类型的基本操作，而不进行插入和删除操作数据元素的查找表称为 静态查找表 。85、 如果在查找表中进行查询的过程中，同时插入查找表中不存在的数据元素，或者从查找表中删除已存在的某个数据元素，则称此类查找表为 动态查找表 。86、 关键字是记录某个 数据项的值 ，用它可以识别、确定一个 记录 。87、 在一个查找表中，能够唯一地确定一个记录的关键字称为 主关键字 。88、 平均查找长度是指为确定记录在查找表中的位置，需要与给定值进行比较的关键字个数的 数学期望值 。89、 顺序 查找是一种最简单的查找方法。90、 折半查找又称为 二分查找 。使用该查找算法的前提条件是，查找表中记录相应的关键字值必须按 升序或降序排列 。91、 折半查找只适用于 顺序存储结构 的有序表 。92、 分块查找又称为 索引顺序查找 ，它是一种介于 顺序查找 和折半查找之间的查找方法。93、 二叉排序树或者是一棵空树，或者是具有下列性质的一棵二叉树：（1）若左子数不空，则左子树所有结点的值 均小于根结点的值 。（2）若右子数不空，则右子树所有结点的值 均大于根结点的值 。（3）左右子树又分别是 二叉排序树 。94、 哈希表是用来存放查找表中记录序列的表，每一个记录的存储位置是以该记录得到关键字为 自变量 ，由相应哈希函数计算所得到的 函数值 。95、 在有序表A1.18中，采用二分查找算法查找元素值等于A17的元素，所比较过的元素的下标依次是 9， 14， 16 ，17 。96、 根据排序过程中所用的存储器不同，可以将排序方法分为 内部排序 和 外部排序 。97、 冒泡排序是一种比较简单的 交换排序 方法。98、 在对一组记录（50，40，95，20，15，70，60，45，80）进行直接插入排序时，当把第7个记录60插入到有序表时，为寻找插入位置需要比较 3 次。99、 在归并排序中，在第3趟归并中，是把长度为 4 的有序表归并为长度为 8 有序表。100、 在堆排序和快速排序中，若原始记录接近正序和反序，则选用 堆排序 ，若原始记录无序，则最好选用 快速排序 。101、 对记录序列排序是指按记录的某个关键字排序，记录序列按 主关键字 排序结果是唯一的。102、 按某关键字对记录序列排序， 关键字相等的记录 若在排序前和排序后仍保持它们的前后关系，则排序算法是稳定的，否则是不稳定的。103、 n个元素进行冒泡法排序，通常需要进行 n-1 趟冒泡，第j趟冒泡要进行 n-j 次元素间的比较。104、 当从一个小根堆中删除一个元素时，需要把 堆尾 元素填补到 堆顶 位置，然后再按条件把它逐层 向下 调整复习资料