2022年青海大学计算机科学与技术专业《数据结构与算法》科目期末试卷A(有答案).pdf

2022年青海大学计算机科学与技术专业《数据结构与算法》科目期末

试卷A（有答案）

一、选择题

1、哈希文件使用哈希函数将记录的关键字值计算转化为记录的存放地址，因为哈希函数

是一对一的关系，则选择好的（）方法是哈希文件的关键。

A.哈希函数

B.除余法中的质数

C.冲突处理

D.哈希函数和冲突处理

2、下列排序算法中，占用辅助空间最多的是（）。

A.归并排序B.快速排序C.希尔排序D.堆排序

3、计算机算法指的是解决问题的步骤序列，它必须具备（）三个特性。

A.可执行性、可移植性、可扩充性

B.可执行性、确定性、有穷性

C.确定性、有穷性、稳定性

D.易读性、稳定性、安全性

4、最大容量为n的循环队列，队尾指针是rear，队头：front，则队空的条件是（）。

A.（rear+1）MODn=front

B.rear=front

C.rear+1=front

D.（rear-1）MODn=front

5、下列关于AOE网的叙述中，不正确的是（）。

A.关键活动不按期完成就会影响整个工程的完成时间

B.任何一个关键活动提前完成，那么整个工程将会提前完成

C.所有的关键活动提前完成，那么整个工程将会提前完成

D.某些关键活动若提前完成，那么整个工程将会提前完成

6、若一棵二叉树的前序遍历序列为a，e，b，d，c，后序遍历序列为b，c，d，e，a，

则根结点的孩子结点（）。

A．只有eB．有e、bC．有e、cD．无法确定

7、下列叙述中，不符合m阶B树定义要求的是（）。

A．根结点最多有m棵子树B．所有叶结点都在同一层上

C．各结点内关键字均升序或降序排列D．叶结点之间通过指针链接

8、一棵哈夫曼树共有215个结点，对其进行哈夫曼编码，共能得到（）个不同的码

字。

A.107B.108C.214D.215

9、有n（n0）个分支结点的满二叉树的深度是（）。

A.n-1

2

B.log（n+1）+1

2

C.log（n+1）

2

D.log（n-l）

2

10、若查找每个记录的概率均等，则在具有n个记录的连续顺序文件中采用顺序查找法查

找一个记录，其平均查找长度ASL为（）。

A.(n-1)/2

B.n/2

C.(n+1)/2

D.n

二、填空题

11、在有n个顶点的有向图中，每个顶点的度最大可达______。

12、无用单元是指______，例______

13、如下的算法分别是后序线索二叉树求给定结点node的前驱结点与后继结点的算法，

请在算法空格处填上正确的语句。设线索二叉树的结点数据结构为（lflag，left，data，

right，rflag），其中：lflag=0，left指向其左孩子，lflag=1，left指向其前驱；rflag=0，

right指向其右孩子，rflag=1，right指向其后继。

14、设有两个算法在同一机器上运行，其执行时闻分别为100n2和2n，要使前者快于后

者，n至少为______。

15、对于一个具有n个结点的单链表，在已知的结点半p后插入一个新结点的时间复杂

度为______，在给定值为x的结点后插入一个新结点的时间复杂度为______。

16、已知U=‘xyxyxyxxyxy’；t=‘xxy’；ASSIGN（S，U）；ASSIGN（V，SUBSTR（S，

INDEX（S，t），LEN（t）+1））；ASSIGN（m，’ww’），求REPLACE（S，V，m）

=______。

17、假设一个15阶的上三角矩阵A按行优先顺序压缩存储在一维数组B中，则非零元素

A9.9在B