数据结构期末试题及答案.doc

E 卷一 单项选择题一 单项选择题 1 线性表若采用链式结构时 要求内存中可用存储单元的地址 A 必须是连续的 B 部分地址必须是连续的 C 一定是不连续的 D 连续不连续都可以 2 判定一个栈ST 最多元素为m0 为空的条件是 A ST top 0 B ST top 0 C ST top m0 D ST top m0 3 数组A中 每个元素A的长度为3个字节 行下标i从1到8 列j下标从 1到10 从首地址SA开始连续存放在存储器内 该数组按行存放时 元 素A 8 5 的起始地址为 A SA 141 B SA 144 C SA 222 D SA 225 4 设哈希表长m 14 哈希函数H key key 11 表中已有4个结点 addr 15 4 addr 38 5 addr 61 6 addr 84 7 其余地址为空 如用二次探测再散列处理冲突 关键字为49的结点的地址是 A 8 B 3 C 5 D 9 5 在线索化二叉树中 t所指结点没有左子树的充要条件是 A t left NULL B t ltag 1 C t ltag 1且t left NULL D 以上都不对 6 将递归算法转换成对应的非递归算法时 通常需要使用 A 栈 B 队列 C 链表 D 树 7 有一个有序表为 1 3 9 12 32 41 45 62 75 77 82 95 100 当二分 查找值为82的结点时 次比较后查找成功 A 1 B 2 C 4 D 8 8 对一个满二叉树 m个树叶 n个结点 深度为h 则 A n h m B h m 2n C m h 1 D n 2h 1 9 如果要求一个线性表既能较快地查找 又能适应动态变化的要求 可以采用 查找方法 A 分块 B 顺序 C 二分 D 散列 10 快速排序方法在 情况下最不利于发挥其长处 A 要排序的数据量太大 B 要排序的数据中含有多个相同值 C 要排序的数据已基本有序 D 要排序的数据个数为奇数 11 在含有n个顶点和e条边的无向图的邻接矩阵中 零元素的个数为 A e B 2e C e D 2e 2 n 2 n 12 假设一个有n个顶点和e条弧的有向图用邻接表表示 则删除与某个 顶点相关的所有弧的时间复杂度是 i V A O n B O e C O n e D O n e 13 用某种排序方法对关键字序列 25 84 21 47 15 27 68 35 20 进行排序时 序列的变化情 况 20 15 21 25 47 27 68 35 84 15 20 21 25 35 27 47 68 84 15 20 21 25 27 35 47 68 84 则所采用的排序方法是 A 选择排序 B 希尔排序 C 归并排序 D 快速排序 14 适宜于对动态查找表进行高效率查找的组织结构是 A 有序表 B 分块有序表 C 三叉排序表 D 线性链表 15 不定长文件是指 A 文件的长度不固定 B 记录的长度不固定 C 字段的长度不固定 D 关键字项的长度不固定 二 填空题二 填空题 16 对数据间关系的描述是数据的逻辑结构 形式地可以用一个二元组 B D R 来表示 其中D表示 R表示 17 数据结构的存储一有两种 分为 和 18 评价一个数据结构 基本来说有两条 一条是 二是 19 栈的类型说明为 typedef struc stack datatype s maxlen int len stack 则 POP stack st 算法是 if st len 0 printf underflow else 20 二叉树的第i层上至多有 结点 深度为k的二叉树至多有 结点 21 图的遍历主要有 和 两种 22 在hq的链队中 判定只有一个结点的条件是 23 在散列函数H key key p中 p应取 24 对于长度为n的线性表 若采用二分法查找 则时间复杂度为 若采用分块查找 假定总块数和每块长度均接近n的平方根 则 时间复杂度为 三 三 解答操作题解答操作题 每小题 每小题 5 5 分 共分 共 2020 分 分 2525 已知一个无向图的顶点集为 已知一个无向图的顶点集为 a b c d e a b c d e 其邻接矩阵如下所示 其邻接矩阵如下所示 1 画出该图的图形 2 根据邻接矩阵从顶点a出发进行深度优先 遍历和广度优先遍历 并写出遍历序列 26 把下列二叉树换成二森林 画出图形 01101 10110 11000 01001 10010 e d c b a 27 已知一个散列表如下表示 3520334859 0 1 2 3 4 5 6 7 8 9 10 11 12 其散列函数h key key 13 处理冲突的方法为双重散列法 探查序列 为 h key i h key m i 0 1 m 1 i h 1 其中 h key key 11 1 1 回答以下问题 1 对表中关键字35 20 33 和 48进行查找时 所需要进行的比较 次数各为多少 2 该散列表在等概率查找时查找成功的平均查找长度为多少 28 已知序列 17 18 60 40 7 32 73 65 85 请给出采用起泡排序法对 该序列作升序排序时的每一趟的结果 四 算法阅读题四 算法阅读题 每小题每小题 6 6 分 共分 共 1212 分分 29 面给出了起泡排序算法 请填写算法中的空框 使算法正确 struct node int key datatype info node lnode int i j int flag node X node R n 每循环一次作一次起泡 循环 i以1为步长 从1到n 1 执行下列语句 1 2 循环 j以1为步长 执行 若 R j key 则flag 1 X R j R j 1 X 3 若 则跳出循环 算法结束 30 下面给出了在对称序穿线树中找指定结点在后序下的前驱算法 请填写算法中的空框 使算法正确 struct node datatype info node llink rlink lnode lnode p p指向指定结点 lnode q q指向指定结点在后序下的前驱 若p rlink 0 则 算法结束 否则q p 1 循环 当 时 反复执行 2 算法结束 五 五 算法设计题 共算法设计题 共 8 8 分 分 31 设有一个循环双链表 其中有一结点的 指针为 p 编写一个函数 p 与其右边的一个结 点进行交换 结点结构为 E 卷 一 单项选择题 1 D 2 B 3 C 4 D 5 B 6 A 7 C 8 D 9 A 10 C 11 D 12 C 13 D 14 C 15 B 二 填空题 16 数据集合 数据间的关系 17 顺序 非顺序 18 时间复杂度 空间复杂度 19 st len st len 1 20 2i 1 2k 1 21 深度 广度 22 hq front hq rear 23 素数 24 O log2n O n 三 解答操作题 每小题 5 分 共 20 分 25 深度优先遍历序列为 abdce 广度优先遍历序列为 abedc 26 27 答 1 比较次数分别为 3 2 1 1 2 平均查找长度 ASL 3 2 1 1 2 5 1 8 28 初始 17 18 60 40 7 32 73 65 85 第 1 趟 17 18 40 7 32 60 65 73 85 第 2 趟 17 18 7 32 40 60 65 73 85 第 3 趟 17 7 18 32 40 60 65 73 85 第 4 趟 7 17 18 32 40 60 65 73 85 第 5 趟 7 17 18 32 40 60 65 73 85 四 算法阅读题 每小题 6 分 共 12 分 29 1 flag 0 2 1 到 n 1 3 R j 1 key 4 R j R j 1 5 flag 0 30 q p rlink q link 0 q 1 q llink q