2022年哈尔滨师范大学计算机科学与技术专业《数据结构与算法》科目期末试卷A(有答案).pdfVIP

2022年哈尔滨师范大学计算机科学与技术专业《数据结构与算法》科目期末试卷A(有答案)--第1页

2022年哈尔滨师范大学计算机科学与技术专业《数据结构与算法》科

目期末试卷A（有答案）

一、选择题

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

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

2、有一个100*90的稀疏矩阵，非0元素有10个，设每个整型数占2字节，则用三元组

表示该矩阵时，所需的字节数是（）。

A.60B.66C.18000D.33

3、连续存储设计时，存储单元的地址（）。

A.一定连续B.一定不连续C.不一定连续D.部分连续，部分不连续

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

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

A.仅修改队头指针

B.仅修改队尾指针

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

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

5、已知有向图G=(V，E)，其中V={V1，V2，V3，V4，V5，V6，V7}，E=｛V1，V2，

V1，V3，V1，V4，V2，V5，V3，V5，V3，V6，V4，V6，V5，V7，

V6，V7｝，G的拓扑序列是（）。

A.V1，V3，V4，V6，V2，V5，V7B.V1，V3，V2，V6，V4，V5，V7

C.V1，V3，V5，V2，V6，V7D.V1，V2，V5，V3，V4，V6，V7

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

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

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

7、排序过程中，对尚未确定最终位置的所有元素进行一遍处理称为一趟排序。下列排序

方法中，每一趟排序结束时都至少能够确定一个元素最终位置的方法是（）。

2022年哈尔滨师范大学计算机科学与技术专业《数据结构与算法》科目期末试卷A(有答案)--第1页

2022年哈尔滨师范大学计算机科学与技术专业《数据结构与算法》科目期末试卷A(有答案)--第2页

Ⅰ．简单选择排序Ⅱ．希尔排序Ⅲ．快速排序Ⅳ．堆排Ⅴ．二路归并排序

A．仅Ⅰ、Ⅲ、ⅣB．仅Ⅰ、Ⅱ、ⅢC．仅Ⅱ、Ⅲ、ⅣD．仅Ⅲ、Ⅳ、Ⅴ

8、一棵非空的二叉树的前序序列和后序序列正好相反，则该二叉树一定满足（）。

A.其中任意一个结点均无左孩子

B.其中任意一个结点均无右孩子

C.其中只有一个叶结点

D.其中度为2的结点最多为一个

9、下述二叉树中，哪一种满足性质：从任一结点出发到根的路径上所经过的结点序列按

其关键字有序（）。

A.二叉排序树B.哈夫曼树C.AVL树D.堆

10、就平均性能而言，目前最好的内排序方法是（）排序法。

A.起泡B.希尔插入C.交换D.快速

二、填空题

11、如果按关键码值递增的顺序依次将关键码值插入到二叉排序树中，则对这样的二叉排

序树检索时，平均比较次数为______。

12、设用希尔排序对数组{98，36，-9，0，47，23，1，8，10，7}进行排序，给出的步

长（也称增量序列）依次是4，2，1则排序需______趟，写出第一趟结束后，数组中数据

的排列次序______。

13、