学院(系) 专业 级 班 学号 姓名
…………………………
密…………………………封………………………线…………………………
题号 一 二 三 四 五 六 七 八 九 十 总分
复核人
得分
一、判断正误(在正确的说法前面打勾,反之打叉)
( 每小题 1 分,共 15 分 )
( )1. 链表的每个结点中都恰好包含一个指针。
( )2. 当删除链表中某个结点后,计算机会自动地将后续的各个结点向前移动。
( )3. 线性表的每个结点只能是一个简单类型,而链表的每个结点可以是一个复杂类型。
( )4. 线性表在物理存储空间中也一定是连续的。
( )5. 顺序存储方式只能用于存储线性结构。
( )6. 栈是一种对所有插入、删除操作限于在表的一端进行的线性表,是一种后进先出型结构。
( )7. 对于不同的使用者,一个表结构既可以是栈,也可以是队列,也可以是线性表。
( )8. 栈和队列是一种非线性数据结构。
( )9. 栈和队列的存储方式既可是顺序方式,也可是链接方式。
( )10. 队是一种插入与删除操作分别在表的两端进行的线性表,是一种先进后出型结构。
( )11. 若二叉树用二叉链表作存贮结构,则在 n 个结点的二叉树链表中只有 n—1 个非空指针域。
( )12. 二叉树中每个结点的两棵子树的高度差等于 1。
( )13. 二叉树中每个结点的两棵子树是有序的。
( )14. 二叉树中每个结点有两棵非空子树或有两棵空子树。
( )15. 二叉树中所有结点,如果不存在非空左子树,则不存在非空右子树。
二、填空题(每空 1 分,共 25 分)
1. 数据结构常表示为: Data_Structure =(D, S), 其中 D 是 ,S 是
。
2. 在顺序表中访问任意一结点的近似时间复杂度均为 ,因此,顺序表也称为 存取的
数据结构。
3. 根据数据元素之间的关系的不同特性,通常有以下四类基本结构:(1) ;( 2)线性
结构;(3)树型结构;(4) 。
4. 顺序表中逻辑上相邻的元素的物理位置 相邻。单链表中逻辑上相邻的元素的物理位置__
_______相邻。
5. 数据元素间的关系在计算机中有以二种不同的表示方法,对应二种不同的存储结构,分别称之
为:______________ 及 。
6. 算法的评价主要从正确性、_____________ 、健壮性、_____________________这四个方面评价一
个算法的优劣。
7. 串是一种特殊的线性表,其特殊性体现在其 ______________ 是一个字符。
8. 假设有 60 行 70 列的二维数组 a[1…60, 1…70]以列序为主序顺序存储,其基地址为 10000,
每个元素占 2 个存储单元,那么第 32 行第 58 列的元素 a[32,58]的存储地址为 ______________
。(无第 0 行第 0 列元素)
9. 由一个或多个空格(仅由空格符)组成的串称为空白串;_________________________ 称为空
串。
10.求广义表的操作结果:GetTail【GetHead【GetTail【((a,b),(c,d))】】】 = ______ 。
11.一棵具有 257 个结点的完全二叉树,它的深度为 ___ 。
12.中序遍历的递归算法平均空间复杂度为 ____ 。
13.若要求一个稀疏图 G 的最小生成树,最好用 ______________ 算法来求解。
14.图有邻接矩阵 、 _______ 等存储结构,遍历图有 __________ 、广度优先遍历等方法。
15.有向图 G 用邻接矩阵存储,其第 i 行的所有元素之和等于顶点 i 的 。
16.在数据的存放无规律而言的线性表中进行检索的一般方法是 。
17.对于 n 个记录的集合进行冒泡排序,其平均时间复杂度是 。若对其进行快速排序,则平
均时间复杂度是 。
三、解答题(共 7 小题,合计 35 分)
1. 设循环队列的容量为 40(序号从 0 到 39),现经过一系列的入队和出队运算后,有 ①
front=11,rear=19; ② front=19,rear=11,问在这两种情况下,循环队列中各有元素多少个?
2. 请以图示方式列出具有三个结点的二叉树的所有形态。
评论1