16、循环队列的最大长度为__________.6、当堆栈采用顺序存储结构时,栈顶元素的值可用-表示;
当堆栈采用链接存储结构时 ， 栈顶元素的值可用_______________表示 。
7、一棵高度为5的二叉树中最少含有_________个结点 ， 最多含有________个结点；一棵高度为5的理想平衡树中 ， 最少含有_________个结点 ， 最多含有_________个结点 。
8、在图的邻接表中 ， 每个结点被称为____________ ， 通常它包含三个域:一是_____________；二是___________；三是_____________.9、在一个索引文件的索引表中 ， 每个索引项包含对应记录的_______ 。

17、__和___________两项数据 。
10、假定一棵树的广义表表示为A（B（C ， D（E ， F ， G） ， H（I ， J）)） ， 则树中所含的结点数为_________个 ， 树的深度为_________,树的度为________ ，结点H的双亲结点为________,孩子结点为_______________ .11、在堆排序的过程中,对任一分支结点进行筛运算的时间复杂度为_________ ， 整个堆排序过程的时间复杂度为________________ 。
12、在对m阶的B_树插入元素的过程中 ， 每向一个结点插入一个索引项（叶子结点中的索引项为关键字和空指针)后 ， 若该结点的索引项数等于______个 ， 则必须把它分裂 。

18、为_______个结点 。
三、 运算题（每小题6分 ， 共24分）1、已知一组记录的排序码为（46 ， 79 ， 56,38,40,80 ，95 ， 24) ， 写出对其进行快速排序的每一次划分结果.2、一个线性表为B=（12 ， 23 ， 45 ， 57,20 ， 03 ， 78 ， 31 ， 15 ， 36）,设散列表为HT0.12 ， 散列函数为H（key）= key 13并用线性探查法解决冲突 ， 请画出散列表,并计算等概率情况下查找成功的平均查找长度 。
3、已知一棵二叉树的前序遍历的结果序列是ABECKFGHIJ,中序遍历的结果是EBCDAFHIGJ ， 试写出这棵二叉树的后序遍历结果 。
4、已知一个图的顶点集V各边集G如下：V = 0,1,2 ， 3,4 。

19、 ， 5 ， 6,7,8,9；E = (0 ， 1),（0 ， 4）,(1 ， 2) ， (1 ， 7） ， （2 ， 8） ， （3 ， 4） ， （3， 8） ， （5 ， 6） ， （5 ， 8） ， （5,9）,(6 ， 7) ， （7 ， 8),(8 ， 9）当它用邻接矩阵表示和邻接表表示时 ， 分别写出从顶点V0出发按深度优先搜索遍历得到的顶点序列和按广度优先搜索遍历等到的顶点序列 。
假定每个顶点邻接表中的结点是按顶点序号从大到小的次序链接的.图深度优先序列广度优先序列邻接矩阵表示时邻接表表示时四、 阅读算法,回答问题（每小题8分 ， 共16分)1、假定从键盘上输入一批整数 ， 依次为：78 63 45 30 91 34 1,请写出输出结果 。
include iostream. 。

20、h include stdlib.h const int stackmaxsize = 30;
typedef int elemtype；struct stack elemtype stack stackmaxsize；int top;
；# include “stack.hvoid main （ ）stack a;
initstack(a）;
int x；cin x；while （x! = -1） push (a ，x ）；cin x;
while (！stackempty (a）)cout void BinTree Type ：unknown (BinTreeNodeType*t) BinTreeN 。

21、ode=0；i-）for（j=0；ji；j+) S；（A)、n2 （B). O（nlgn） （C). O(n) （D). O（n2）3折半查找法适用于（ ） 。
（A)、有序顺序表 （B）、有序单链表（C）、有序顺序表和有序单链表都可以 （D）、无限制4顺序存储结构的优势是（ ) 。
（A)、利于插入操作 （B）、利于删除操作 （C）、利于顺序访问 （D）、利于随机访问5深度为k的完全二叉树 ， 其叶子结点必在第( )层上 。
(A）、k1 (B)、k (C）、k-1和k （D）、1至k6具有60个结点的二叉树 ， 其叶子结点有12个 ， 则度过1的结点数为( ）（A）、11 （B）、13 (C）、48 (D)、37 。

22、7图的Depth-First Search（DFS)遍历思想实际上是二叉树（ ）遍历方法的推广 。
（A)、先序 （B）、中序 （C）、后序 (D)、层序8在下列链队列Q中 ， 元素a出队的操作序列为( )b c d afrontrearQ(A)、p=Q 。
front-next;
p-next= Q 。
front-next;
（B）、p=Q.frontnext;
Q.front-next=pnext；（C）、p=Q 。
rear-next； pnext= Q.rear-next;
(D）、p=Q-next； Q-next=p-next；9 Huffman树的带权路径长度WPL等于( ）(A）、除根结点之外的所有结 。

23、点权值之和 （B）、所有结点权值之和（C）、各叶子结点的带权路径长度之和 （D）、根结点的值10线索二叉链表是利用（ ）域存储后继结点的地址.(A）、lchild （B）、data （C)、rchild （D）、root二、 填空题1 逻辑结构决定了算法的， 而存储结构决定了算法的。
2 栈和队列都是一种 的线性表 ， 栈的插入和删除只能在 进行.3 线性表（a1 ， a2 ， an）的顺序存储结构中,设每个单元的长度为L ， 元素ai的存储地址LOC（ai)为 4 已知一双向链表如下（指针域名为next和prior）：yxeqp现将p所指的结点插入到x和y结点之间 ， 其操作步骤为： ;

来源：(未知)

【学习资料】网址：/a/2021/0321/0021738320.html

标题：数据结构|(完整word版)2017《数据结构》期末考试试题及答案( 三 )