单项选择(2023年计算机统考

已知一棵二叉树的树形如图,若其后序遍历为 f、d、b、e、c、a,则其先序列为【 】

A、aedfbc

B、acebdf

C、cabefd

D、dfebac

答案解析

A

【解析】

后序遍历即按照“左-右-根”的顺序遍历,遍历过程如下图:

所以,原二叉树为:

再按先序(根-左-右)遍历该二叉树,得序列:aedfbc.

讨论

在有 6 个字符组成的字符集 S 中,各个字符出现的频次分别为 3、4、5、6、8、10,为 S 构造的哈夫曼树的加权平均长度为【 】

若采用三元组表存储结构存储系数矩阵 M.则除三元组外,下列数据中还需要保存的是【 】Ⅰ. M 的行数;Ⅱ. M 中包含非零元素的行数;Ⅲ. M 的列数;Ⅳ. M 中包含非零元素的列数.

现有非空双向链表 L,其结点结构为:prer|data|next。prer 是指向前直接前驱结点的指针,next 是指向直接后继结点的指针。若要在 L 中指针 p 所指向的结点( 非尾结点) 之后插入指针 s 指向的新结点, 则在执行了语句序列: “s->next=p->next;p->next=s”后,还要执行【 】

下列对顺序存储的有序表 (长度为 n)实现给定操作的算法中平均时间复杂度为 O(1)的是【 】

对n个关键码构成的序列采用直接插入排序法进行升序排序的过程是:在插入第i个关键码ki时,其前面的 i-1 个关键码已排好序,因此令k与 ki-1、ki-2、…,依次比较,最多到 k1为止,找到插入位置并移动相关元素后将ki插入有序子序列的适当位置,完成本趟(即第 i-1 趟)排序。以下关于直接插入排序的叙述中,正确的是【 】 。

对于下面的有向图,采用邻接链表存储时,顶点 0的表结点个数为2,顶点3的表结点个数为0,顶点1的表结点个数为【 】。

对于下面的有向图,其邻接矩阵是一个【 】的矩阵。

对下图所示的二叉树进行中序遍历(左子树、根结点、右子树)的结果是【 】。

对关键码序列(12,24,15,56,20,87,69,9)采用散列法进行存储和查找,并设散列函数为H(Key)=Key%11(%表示整除取余运算)。采用线性控查法(顺地探查可用存储单元)解决冲突所构造的散列表为【 】。

对关键码序列(9,12,15,20,24,29,56,69,87)进行二分查找(折半查找),若要查找关键码15,则需依次与【 】进行比较。