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

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

期末试卷A（有答案）

一、选择题

1、将线性表的数据元素进行扩充，允许带结构的线性表是（）。

A.串B.树C.广义表D.栈

2、将两个各有N个元素的有序表归并成一个有序表，其最少的比较次数是（）。

A.NB.2N-1C.2ND.N-1

3、单链表中，增加一个头结点是为了（）。

A.使单链表至少有一个结点B.标识表结点中首结点的位置

C.方便运算的实现D.说明单链表是线性表的链式存储

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

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

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

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

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

5、用不带头结点的单链表存储队列，其队头指针指向队头结点，队尾指针指向队尾结点，

则在进行出队操作时（）。

A.仅修改队头指针

B.仅修改队尾指针

C.队头、队尾指针都可能要修改

D.队头、队尾指针都要修改

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

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

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

7、循环队列放在一维数组A中，end1指向队头元素，end2指向队尾元素的后一个位置。

假设队列两端均可进行入队和出队操作，队列中最多能容纳M－1个元素。初始时为空，

下列判断队空和队满的条件中，正确的是（）。

A．队空：end1＝＝end2；队满：end1＝＝（end2＋1）modM

B．队空：end1＝＝end2；队满：end2＝＝（end1＋1）mod（M－1）

C．队空：end2＝＝（end1＋1）modM；队满：end1＝＝（end2＋1）modM

D．队空：end1＝＝（end2＋1）modM；队满：end2＝＝（end1＋1）mod（M－1）

8、每个结点的度或者为0或者为2的二叉树称为正则二叉树。n个结点的正则二叉树中

有（）个叶子。

A.lognB.（n－1）/2C.logn+1D.（n＋1）/2

22

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

字。

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

10、一组记录的关键码为（46，79，56，38，40，84），则利用快速排序的方法，以第

一个记录为基准得到的一次划分结果为（）。

A.（38，40，46，56，79，84）B.（40，38，46，79，56，84）

C.（40，38，46，56，79，84）D.（40，38，46，84，56，79）

二、填空题

11、在哈希函数H（key）=key%p中，p值最好取______。

12、分别采用堆排序，快速排序，起泡排序和归并排序，对初态为有序的表，则最省时间

的是______算法，最费时间的是______算法。

13、设单链表的结点结构为（data，next），next为指针域，已知指针px指向单链表中

data为x的结点，指针py指向data为y的新结点，若将结点y插入结点x之后，则需

要执行以下语句：______

14、在基于关键字比较且时间为O（nlog2n）的排序中，若要求排序是稳定的，则可选用

______排序；若要求就地排序（及辅助空间为O（1