一单项选择(每空 分共分)
若某线性表中最常用的操作是在最后一个元素之前插入和删除元素则采用___________最节省运算时间
A单链表 B仅有头指针的单循环链表
C仅有尾指针的单循环链表 D双链表
哈夫曼树的带权路径长度WPL等于___________
A除根以外的所有结点的权植之和 B所有结点权值之和
C各叶子结点的带权路径长度之和 D根结点的值
设输入序列为借助一个栈不可能得到的输出序列是___________
AB
CD
对于下面二叉树按后序遍历所得的结点序列为___________
AB
CD
栈和队列都是___________
A顺序存储的线性结构 B链式存储的线性结构
C限制存储点的线性结构 D限制存储点的非线性结构
已知完全二叉树有个结点则整个二叉树有___________个度为的结点
AB
CD不确定
对下图不能得到的拓扑序列是___________
AB
CD
下列排序算法中第一趟排序完毕后其最大或最小元一定在其最终位置上的算法是___________
A归并排序 B直接选择排序
C快速排序 D基数排序
下列排序方法中排序所花费时间不受数据初始排列特性影响的算法是___________
A直接插入排序 B冒泡排序
C直接选择排序 D快速排序
下列排序方法中最好情况下时间复杂度为O(N)的算法是___________
A选择排序 B归并排序
C快速排序 D直接插入排序
二判断题(每小题 分共分)
( )线性表的长度是线性表占用的存储空间的大小
( )双循环链表中任一结点的后继指针均指向其逻辑后继
( )队列只能采用链式存储方式
( )树(或森林)转化为对应的二叉树后两者的分支数相等
( )由二叉树的先序序列和中序序列能唯一确定一棵二叉树
( )图中一个顶点i的出度等于其邻接矩阵中第i列的非元个数
( )在用线性探查法解决沖突所构造的闭散列表中每组同义词中至少有一个元素的地址正好等于其散列地址
( )所谓沖突即是两个关键字的值相同的元素其散列地址相同
( )对n个元素的有序表用快速排序方法进行排序时间复杂是O(n )
( )存在有偶数个结点的满二叉树
三填空题(每空 分共分)
在单链表中若要删除指针P所指结点的后继结点则需执行下列三条语句 U=P↑next;P↑next=U↑next;___________
设有一个链队列结点结构为队尾指针为Ls(≠nil)则执行入队操作时 S↑next=Ls↑next;___________;___________
单链表中指针P所指结点不为尾结点的条件是___________
设数组B[]中的任一元素均占个单元从首地址SA开始把数组B按行优先存储 则元素B[]的地址为___________
在有n(n>)个结点的二叉链表中非空链域的个数为___________
深度为(根的层次号为i)的完全二叉树至多有___________个结点
一个具有n个顶点的连通有向图至多有___________条边
一棵二叉排序树中若存在个结点其成功的查找长度≤则有___________个结点其成功的查找长度=
在对有个数据的有序表作二分查找时有___________个结点的查找长度是
在完全二叉树中编号为i的结点的左孩子结点的编号为___________
四解答下列各题(共 分)
以数据集{}为叶子结点的权值
()构造一棵哈夫曼树(分)
()计算其带权路径长度(分)
已知二叉树的先序中序和后序序列分别如下但其中有一些已模糊不清构造出该二叉树(分)
先序序列_BC_EF__
中序序列BDE_AG_H
后序序列_DC_GH_A
如图所示
()写出邻接矩阵(分)
()求出其最小生成树(分)
设散列函数H(X)=K MOD 若输入序列为 {}求
()构造出开散列表
()求出在等概率查找情况下查找成功的平均查找长度
有一个数据序列现采用堆排序算法进行排序写出每趟的结果
五算法设计题(共 分)
设计一个用带头结点的单链表表示的直接插入排序算法各结点结构如图
要求用类PASCAL语言写出算法(分)
设二叉树采用二叉链表表示各结点结构为其中data为整数型字段设计算法判别一棵二叉树是否是二叉排序树(分)
