数据结构期末考试试题及答案1

一、填空题1.【答案】集合、线性结构、树形结构、图状结构或网状结构【解析】相互之间存在一种或多种特定关系的数据元素的集合称为数据结构，根据数据元素之间关系的不同特性通常分出了以上四种逻辑结构。2．【答案】插入和删除、后进现出（LIFO）【解析】考查的栈的定义及性质，队列的定义及性质也需要牢固掌握。3.【答案】2k-1【解析】考查二叉树的性质2。4.【答案】图【解析】根据图数据结构的特性。５．【答案】有穷性、确定性、可行性、输入（0或多个）、输出（至少有1个）【解析】算法是特定问题的求解步骤的一种描述，其五个基本性质如上。６.【答案】串的长度相等且两串中对应位置的字符也相等【解析】考查两个字符串相等的定义。７．【答案】n2+1【解析】考查二叉树的性质3。８.【答案】树内各结点的度【解析】考查树的度的定义。９．【答案】入度、出度【解析】考查有向图中顶点度的定义。10.【答案】顺序存储、有序【解析】因为折半查找需要拿表中第mid（其中mid=(low+high）/2)个元素与查找的关键字进行比较，所以要求查找表需要能随机存取，因此，要求顺序存储；另外，实施折半查找的前提必须是有序表，顺序表不可以。二、选择题1.【答案】B【解析】根据具有n个顶点的无向完全图的边数为n(n-1)/2，代入公式即可。2.【答案】B【解析】在循环队列中队列满的条件是以牺牲一个存储空间为代价的，即当满足选项B时就判断该队列已满。3.【答案】D【解析】考查数据对象的定义。4.【答案】A、D【解析】无论是循环链表还是单链表都属于线性表的链式存储，所以选A、D。邻接多重表属于图的存储结构，孩子链表属于树的存储结构。5.【答案】C【解析】考查栈的基本性质，选项C中a先于b入栈，因此出栈顺序a应该在b的后面。6.【答案】B、C【解析】考查完全二叉树的定义及二叉树的基本性质。7.【答案】A【解析】该有序表中有8个元素，因此，折半查找时，查找第8个元素，根据判定树可以获得需先后与第4、6、7、8个元素进行比较4次，所以选A。8.【答案】A、B【解析】处理冲突的方法主要有四种：分别是开放定址法（包含线性探测再散列以及二次探测再散列等）、再哈希法、链地址法和建立一个公共溢出区。9.【答案】C【解析】一个排序算法的时间复杂度主要与所需关键字的比较次数有关。10.【答案】B【解析】考查数据元素的概念。三、求解下列问题1．答：根据树与二叉树的转换方法，得出转化为的二叉树如下图所示：ABGHCDFEIJKLM由此可得先序遍历序列为：ABCDFEGHIJKLM中序遍历序列为：CFDEBGJILMKHA;后序遍历序列为：FEDCJMLKIHGBA2．答：根据克鲁斯卡尔算法思想画图表示最小生成树的生成过程如下：012534012534101253412012534123012534123401253412345四、程序填空1．答：low=high;mid=(low+high)/2;return(mid);high=mid-1;low=mid+1;2．答：structnodep=p-next;Linklist或是LNode*(注意字母大小写与类型定义一致)s-next=p-next;p-next=s五、算法设计（本大题共1小题，共10分）答：