2020年10月自考数据结构导论真题（三）

二、填空题:本大题共13空,每空2分,共26分。

16.数据的四类基本逻辑结构是:线性结构、树形结构、图结构和 _。

17.数据的存储结构有顺序存储、链式存储、索引存储和 _存储。

18.顺序表插入算法的时间复杂度是 _。

19.浙02142# 数据结构导论试题 第 2页(共4页)19.设r指向单链表的最后一个结点,要在最后一个结点之后插入s所指的结点,需执行的语句序列是r->next=s;r=s; _。

20.一般情况下,函数的嵌套调用和程序递归的处理都是用 _来实现的。

21.m 行n列的矩阵有t个非零元素,当t满足 _条件时,称该矩阵为稀疏矩阵。

22.二叉树的第i(i≥1)层上至多有 _个结点。

23.双亲表示法由一个一维数组构成,数组的每个分量包含两个域: _和双亲域。

24.无向图的邻接矩阵是一个 _矩阵。

25.设有散列函数 H 和键值k1、k2,若k1≠k2,但是 H(k1)=H(k2),则称这种现象为 _。

26.向一个长度为n的顺序表中第i(1≤i≤n)个元素之前插入一个元素时,需向后移动 _个元素。

27.直接插入排序的空间复杂度为 _。

28.设记录数为n,冒泡排序算法在最好情况下所作的比较次数为 _。