一、单选题(每小题 分,共 分)
、在一个单链表 中,若要向 所指结点之后插入一个由指针 指向的结
点,则执行
、、
、、
、在一棵深度为 的完全二叉树中,至少含有 个结点。
、、、、
、从一棵深度为 的二叉搜索树中查找一个元素时,其时间复杂度为
。
、、
、
、!
"、由权值分别为 ,,,, 的叶子结点生成一棵哈夫曼树,该树中双
分支结点数为
、、、"、
二、填空题(每空 分,共 分)
、向一长度为 的有序单链表中插入一个元素时,为寻找插入位置需要平均
比较 个元素。
、在以 为表头指针的单链表和循环单链表中,链表为空的条件分别为
和
、在一个稀疏矩阵的带行指针向量的链接存储中,每个元素结点共包含有
个域,其中 个为指针域。
"、向一个链栈插入一个 所指向的结点时,需要把栈顶指针的值赋给 所指
向的结点的 ,然后把 赋给 。
、在用一个维数 组 #$%存储一个顺序循环队列时,若队列的首、尾指针分
别用 & 和 ' 表示,则队列长度为
。
、对于一棵具有 个结点的二叉树,若一个结点的编号为 ,则它的左孩子
结眯的编号为 ,右孩子结点的编号为 ,双亲结点的编号为
。
(、在一棵高度为 ( 的理想平衡树中,最少含有 个结点,最多含有 个
结点。
、对于一个具有 个结点的堆,对其进行插入运算的时间复杂度和空间复杂
度分别为 和 。
)、在一个具有 个顶点的无向连接通图中,至少包含有 条边,至多包含
有 条边。
、对于一个具有 个顶点和 条边的有向图和无向图,若采用邻接表表示,
则所有顶点单链表中边结点的个数分别为 和 。
、以二分查找方法从长度为 的有序表中查找一个元素时,平均查找长度
为 。
、假定一个线性表为
(,,(",,,",,,,",",(),若散列
函数为 **+(,则散列地址分别为 ",, 的元素个数依次为 、
、和 。