《数据结构》期末考试卷-B卷

高二《计算机应用基础》期中考试试卷东莞理工学院城市学院（本科）试卷（B卷）2016-2017学年第二学期开课单位：计信系，考试形式：闭卷，允许带入场科目：数据结构班级：级软件工程∽班，姓名：学号：一二三四总分题序得分评卷人一、填空题（每题分，共分）、数据结构、栈又称为堆栈是操作受限的线性结构，删除元素的一端称为、深度为（根的深度为）的完全二叉树至少有个结点，至多有个结点。、对于一个有个顶点的完全无向图，具有条边；而对于一个有个顶点的完全有向图，具有、在进行排序时，最基本的操作是和、哈希函数是一种映象，是从到在计算机中基本存储方式有结构和结构。其操作的基本原则是，插入和。条弧。。的一种映象。高二《计算机应用基础》期中考试试卷二、单项选择题（请将答案写在题目后的括号中。每题分，共分）、下面结构中（）线性链表（）线性结构（）网状结构，不属于数据逻辑结构的是（）。（）树形结构、下面说法正确的是（）。（）数据元素是数据的最小单位（）数据项是数据的基本单位（）数据结构是带有结构的各数据项的集合（）上述说法都是错误的、有下列算法，其时间复杂度是（）。（）（）（）㏒（）㏒、线性表若采用存储单元的地址是（链式存储结构，要求内存中可用）。（）必须是连续的（）部分地址必须是连续的（）一定是不连续的（）连续或不连续都可以、设是非空单链表中结点的直接前驱结点，删除的正确操作是（）。（）；（）；（）；（）；高二《计算机应用基础》期中考试试卷、栈和队列的共同点时（（）都是先进先出（）都是后进先出（）只允许在端点处插入和删除元素（）没有共同点）。、设有一个栈顶指针为的顺序栈，为时表示栈空，则向堆栈中压入一个元素执行的操作是（）。（）；（）；（）；（）；、设循环队列的最多元素个数为，队尾指针是，队首指针是，则队列为满的条件是（）。（）；（）；（）；（）；、广义表的长度是，深度是。（）（）（）（）（）、有一个阶下三角矩阵，上三角的所有元素均为，的地址是，若每个元素占个存储单元，采用行优先压缩存储，则的地址是（）。（）（）（）（）、在二叉树中，指针所指的结点是非叶子结点的条件是（）。（）；高二《计算机应用基础》期中考试试卷（）；（）；（）；、将一棵一般的树转换为二叉树后，这棵二叉树的形态是（）。（）唯一的（）有多种（）有多种，但根结点都没有右子结点、设由（≥）个权值都字符构成的哈夫曼树，关于该树的叙述中，错误的是（）。（）该树一（）树中一定没有度为的结点（）树中两个权值最小的结点一定是兄弟结点（）树中任一非叶子结点的层任一结点的权值、以下描述中，特性不正确的是（）。（）邻接矩阵是（）有多种，但根结点都没有左子结点互不相同的定是一棵完全二叉树权值一定不小于下一关于无向图邻接矩阵的对称方阵。（）若顶点在顶点存储位置为，则其度数是第行的非元素的数组中的个数。（）无向图的上或下三角形非元素个数。边数是矩阵中（）图的、对于有（）顶点的（）图的度是矩阵中非元素个数。顶点的度、入度、出度的论述中，错误的是（）。入度、出度之和入度、出度之和向图，下述关于图、度是顶点的度是图的（）顶点的入度等于顶点的出度（）图的入度等于图的出度高二《计算机应用基础》期中考试试卷、对于有个顶点条边的带权无向图，以下关于该图的最小生成树的描述正确的是（）。（）最小生成树是唯一的。（）最小生成树中所有边上的权值之和是唯一的。（）最小生成树有条边。（）最小生成树有个顶点条边。、适用于折半查找的表的存储方式以及元素排列要求是（）。（）顺序存储方式，元素有序（）顺序存储方式，元素无序（）链接存储方式，元素无序（）链接存储方式，元素有序、采用线性探测法解决冲突，可能要探测多个位置，在查找成功的情况下，所探测的这些位置上的关键字（）。（）不一定都是同义词（）一定都不是同义词（）都相同、从未排序序列中将其放入已排序序列的正确位置上的方法，这排种序方法称为（）。（）归并排序（）冒泡排序（）选择排序（）插入排序（）一定都是同义词依次取出元素与已排序序列（初始时为空）中的元素进行比较，、若一组记录的排序码为（，，，，，），则采用快速排序法，以第一个记录为基准得到的依次划分结果是（）。（），，，，，（），，，，，（），，，，，（），，，高二《计算机应用基础》期中考试试卷，，三、分析题（每题分，共分）、设有一棵二叉树的顺序存储结构如下。⑴画出该二叉树；⑵分别写出该二叉树的中序遍历序列和后序遍历序列；、若以作为叶子结点的权值，请构造对应的树，然后求出其带权路径长度。高二《计算机应用基础》期中考试试卷、设有带权的无向图的顺序存储结构如下：⑴画出该图；⑵给出用普里姆算法从顶点出发的最小生成树。∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞高二《计算机应用基础》期中考试试卷、将关键字序列（，，，，，，，，）依次插入到初态为空的二叉排序树中，请画出所得到的树；然后画出删除之后的二叉排序树；最后再画出在中插入之后的二叉排序树。高二《计算机应用基础》期中考试试卷、线性表的关键字集合，，，，，，，，，，，，，共有个元素，已知散列函数为：（），采用链地址法处理冲突，请给出对应的散列表结构。四、编写算法（分）设单链表的结点结构定义如下，试写一个函数实现通过一趟遍历删除以为头结点的单链表中值在到的大小任意之间的所有结点。数据域，保存结点的值指针域结点的类型