24 - 25
一、选择题(在每个小题四个备选答案中选出一个正确答案)(本大题共10小题,每小题2分,总计20分)
-
下面关于广义表的叙述中,不正确的是________。 A) 广义表可以是一个多层次的结构 B) 广义表至少有一个元素 C) 广义表可以被其他广义表所共享 D) 广义表可以是一个递归表
-
以下数据结构中哪一个是线性结构? A) 有向图 B) 栈 C) 二叉树 D) B树
-
字符 A、B、C、D 依次进入一个栈,按出栈的先后顺序组成不同的字符串,至多可以组成________个不同的字符串。 A) 15 B) 16 C) 14 D) 21
-
对线性表,在下列哪种情况下应当采用链表表示? A) 经常需要随机地存取元素 B) 经常需要进行插入和删除操作 C) 表中元素需要占据一片连续的存储空间 D) 表中元素的个数不变
-
为解决计算机与打印机之间速度不匹配的问题,通常设置一个打印数据缓冲区,主机将要输出的数据依次写入该缓冲区,而打印机则依次从该缓冲区中取出数据。该缓冲区的逻辑结构应该是________。 A) 栈 B) 队列 C) 树 D) 图
-
栈和队列的共同点是________。 A) 都是先进先出 B) 都是先进后出 C) 只允许在端点处插入和删除元素 D) 没有共同点
-
设有一个二维数组A[m][n],假设A[0][0]存放位置在600₍₁₀₎,A[3][3]存放位置在678₍₁₀₎,每个元素占一个空间,问A[2][3]₍₁₀₎存放在什么位置?(脚注₍₁₀₎表示用10进制表示,m>3) A) 658 B) 648 C) 633 D) 653
-
下列关于数据结构的叙述中,哪一个是正确的? A) 数组是不同类型值的集合 B) 线性表的链式存储结构优于线性存储结构 C) 树是一种线性结构 D) 用一维数组存储一棵完全二叉树是有效的存储方法
-
已知串 S=‘aaab’,其 Next 数组值为________。 A) 0123 B) 1123 C) 1231 D) 1211
-
下面关于串的叙述中,哪一个是不正确的? A) 串是字符的有限序列 B) 空串是由空格构成的串 C) 模式匹配是串的一种重要运算 D) 串既可以采用顺序存储,也可以采用链式存储
二、填空题(本大题共10小题,每小题2分,总计20分)
-
数据结构被形式地定义为 (D, S),其中 D 是数据元素的有限集合,S 是 D 上________的有限集合。
-
邻接矩阵的存储空间大小与图的________有关。
-
________是被限定为只能在表的一端进行插入操作,在表的另一端进行删除操作的线性表。
-
设有一稀疏图 G,则 G 采用________存储方式较省空间。
-
如果 n 个顶点的图是一个环,则它有________棵生成树。
-
若串 S=‘computer’,其子串的数目是________。
-
对于 n 个记录的集合进行冒泡排序,在最坏的情况下的时间复杂度是________。
-
已知广义表 L=((x, y, z), a, (u, t, w)),则 L 的深度为________。
-
一棵深度为 6 的满二叉树有________个分支结点。
-
一棵具有 257 个结点的完全二叉树,它的深度为________。
三、算法应用(本大题共4小题,第1~3小题每小题8分,第4小题16分,总计40分)
1. 有向带权图问题(ACM式Input格式)
有向带权图如下:
6 8
0 2 10
0 5 100
0 4 30
1 2 5
2 3 50
3 5 10
4 3 20
4 5 60题目描述:
(1) 以顶点0为出发点,分别写出一条深度优先遍历序列和一条广度优先遍历序列;
(2) 填表格展示应用迪杰斯特拉算法求从顶点0到其余各点的最短路径的过程。
2. 哈希表问题
将关键字序列 {7, 8, 11, 18, 9, 14, 30} 散列存储到哈希表中,其存储空间是一个大小为10、下标从0开始的一维数组,哈希函数为:
h(key) = (key * 3) % 10,
处理冲突采用线性探测再散列法。(注:% 是求余运算)
(1) 请画出所构造的哈希表;
(2) 并计算查找成功的平均查找长度。
3. 排序算法问题
给定关键字序列 {24, 19, 32, 43, 38, 6, 13, 22},
(1) 请写出快速排序第一趟的结果;
(2) 请画出堆排序时所建的初始堆(大顶堆)。
4. 树结构问题
设有序列:w = {23, 24, 27, 80, 28},
(1) 试画出二叉排序树;
(2) 试画出平衡二叉树;
(3) 试画出哈夫曼树;
(4) 请给出对于增量 d = 2 按降序执行一趟希尔排序的结果。
四、算法设计(本大题共2小题,每小题10分,总计20分)
1. 单链表插入算法设计
请设计算法 ListInsert_L,用以实现:在带头结点的单链表 L 中第 i 个位置之前插入元素 e。结点结构如下:
typedef struct LNode {
ElemType data;
struct LNode *next;
} LNode, *LinkList;
Status ListInsert_L(LinkList &L, int i, ElemType e) { ... }
// 在带头结点的单链表 L 中第 i 个位置之前插入元素 e。c2. 二叉树中序遍历非递归算法设计
以二叉链表作存储结构,请设计中序遍历非递归算法 InOrderTraverse,对每个数据元素调用函数 Visit。二叉树的二叉链表存储表示如下:
typedef struct BiTNode {
TElemType data;
struct BiTNode *lchild, *rchild; // 左右孩子指针
} BiTNode, *BiTree;
Status InOrderTraverse(BiTree T, Status(* Visit)(TElemType e)) { ... }
// 采用二叉链表存储结构,Visit 是对数据元素操作的应用函数。
// 中序遍历二叉树 T 的非递归算法,对每个数据元素调用函数 Visit。c23 - 24
一、填空题(本大题每空 3 分,共 30 分)
-
对于给定的 个元素,可以构造出的逻辑结构有集合、线性结构、、 四种。
-
数据结构中评价算法的两个重要指标是 ________ 和空间复杂度。
-
下面程序段的时间复杂度为 ________。()
for (j = 1; j <= n; ++j)
for (k = 1; k <= n; ++k)
{++x; s += x;}c-
已知数组 的每个元素占 5 个存储单元,将其按列优先次序存储在起始地址为 1000 的连续的内存单元中,则元素 的地址为 ________。
-
设广义表 ,则 ________。
-
模式串