数据结构总练习题PPT课件.ppt

1 1什么是数据结构 1 2基本概念和术语 1 4算法和算法分析 第一章绪论 1 3抽象数据类型的表示与实现 1 1 熟悉各名词 术语的含义 掌握基本概念 本章学习要点 2 估算算法时间复杂度的方法 2 第1章练习题 1 数据结构是研究数据的 以及它们之间的相互关系 A 物理结构 逻辑结构B 理想结构 抽象结构C 理想结构 物理结构D 抽象结构 逻辑结构2 从逻辑上可以把数据结构分为 两大类 A 动态结构 静态结构B 顺序结构 链式结构C 线性结构 非线性结构D 初等结构 构造型结构3 在发生非法操作时 算法能够做出适当处理的特性称为 A 正确性B 健壮性C 可读性D 可移植性4 以下 不是算法的基本特性 A 可行性B 长度有限C 在规定的时间内完成D 确定性 A C B B 3 5 算法的时间复杂度与 有关 A 问题规模B 计算机硬件性能C 编译程序质量D 程序设计语言6 某算法的时间复杂度为O n2 表明该算法的 A 问题规模是n2B 执行时间等于n2C 执行时间与n2成正比D 问题规模与n2成正比 A C 4 第二章线性表 2 1线性表的类型定义 2 2线性表的顺序表示和实现 2 3线性表的链式表示和实现 2 4一元多项式的表示及相加 5 本章学习要点 1 了解线性表的逻辑结构特性 在计算机中表示这种关系的两类不同的存储结构 2 熟练掌握两类存储结构的描述方法 以及线性表的各种基本操作的实现 3 能够从时间复杂度的角度综合比较线性表两种存储结构的不同特点及其适用场合 6 1 在线性表的下列存储结构中 读取指定序号的元素花费时间最少的是 A 单链表B 双链表C 循环链表D 顺序表2 在一个具有n个结点的有序单链表中插入一个新结点使得仍然有序 其算法的时间复杂度为 A O 1 B O n C O n2 D O log2n 3 线性表采用链式存储结构时 其地址 A 必须是连续的B 一定是不连续的C 部分地址必须是连续的D 连续与否均可 D B D 第2章练习题 7 4 对于用一维数据d 1 n 顺序存储的线性表 其算法的时间复杂度为O 1 的操作是 A 将n个元素从小到大排序B 从线性表中删除第i个元素 1 i n C 查找第i个元素 1 i n D 向线性表中第i个元素之后插入一个元素 1 i n 5 在表头指针为head且表长大于1的单向循环链表中 指针p指向表中的某个结点 若p next next head 则 A p指向头结点B p的直接后继是尾结点C p指向尾结点D p的直接后继是头结点 C B 8 第三章栈和队列 3 1栈的类型定义 3 3栈的应用举例 3 2栈类型的实现 3 4队列的类型定义 3 5队列类型的实现 9 1 掌握栈和队列类型的特点 并能在相应的应用问题中正确选用它们 2 熟练掌握栈类型的基本操作和实现算法 3 熟练掌握循环队列的基本操作实现算法 本章学习要点 4 理解使用栈实现非递归的原理 10 1 栈和队列的共同点是 A 都是先进先出B 都是先进后出C 只允许在端点处插入和删除元素D 没有共同点2 经过以下栈运算后 StackEmpty s 的值是 InitStack s Push s a Push s b Pop s x Pop s y A aB bC 1D 03 4个元素a b c和d依次入栈 入栈过程中允许元素出栈 假设某一时刻栈的状态是c 栈顶 b a 栈底 则不可能的出栈顺序是 A d c b aB c b d aC c a d bD c d b a 第3章练习题 C C C 11 4 设有一顺序栈S 元素a b c d e f依次进栈 如果6个元素出栈的顺序是b d c f e a 则栈的容量至少应该是 A 2B 3C 5D 65 若用一个大小为6的数组来实现循环队列 且当前rear和front的值分别为0和3 当从队列中删除一个元素 再加入两个元素后 rear和front的值分别为 A 1和5B 2和4C 4和2D 5和1 B B 12 8 设循环队列中数组的下标是0 N 1 其头尾指针分别为f和r 则其元素个数为 A r fB r f 1C r f N 1D r f N N9 设有编号为1 2 3 4的四辆列车 顺序进入一个栈式结构的车站 具体写出这四辆列车开出车站的所有可能的顺序 答案 至少有14种 全进之后再出情况 只有1种 4 3 2 1 进3个之后再出的情况 有3种 3 4 2 13 2 4 13 2 1 4 进2个之后再出的情况 有5种 2 4 3 12 3 4 12 1 3 42 1 4 32 3 1 4 进1个之后再出的情况 有5种 1 4 3 21 3 2 41 3 4 21 2 3 41 2 4 3 D 13 第四章串 4 1串类型的定义 4 2串的表示和实现 1 熟悉串的基本操作 2 熟练掌握在不同的存储结构下 串的特点 本章学习要点 14 1 串是一种特殊的线性表 其特殊性体现在 A 可以顺序存储B 数据元素是一个字符C 可以链式存储D 数据元素可以是多个字符2 若串S software 其子串数目是 A 8B 37C 36D 9 B B 15 第五章数组 5 1数组的类型定义 5 2数组的顺序表示和实现 本章学习要点 1 掌握二维数组以行为主序和以列为主的存储结构中的地址计算方法 16 1 数组A 0 5 0 6 的每个元素占5个单元 将其按列优先次序存储在起始地址为1000的连续内存单元中 则元素a 5 5 的地址为 A 1175B 1180C 1205D 1210 A 17 第六章树和二叉树 6 1树的类型定义 6 2二叉树的类型定义和实现 6 3遍历二叉树和线索二叉树 6 4树和森林 6 5Huffman树与Huffman编码 18 本章学习要点 1 熟练掌握二叉树的性质 了解相关性质证明 2 熟悉二叉链表的存储结构的特点 3 掌握各种二叉树遍历策略的递归和非递归算法 灵活运用遍历算法实现其它操作 4 理解线索二叉树以及二叉树的线索化过程 5 熟悉树的存储结构及其基本操作 6 掌握树和森林与二叉树的转换方法 7 了解最优二叉树的特性 掌握建立最优二叉树和Huffman编码的方法 19 1 对于一颗具有n个结点 度为4的树来说 A 树的高度至多是n 3B 至少在某一层上正好有4个结点C 树的高度至多是n 4D 第i层上至多有4 i 1 个结点2 用双亲存储结构表示树 其优点之一是比较方便 A 找指定结点的双亲结点B 找指定结点的孩子结点C 找指定结点的兄弟结点D 判断某结点是不是叶子结点3 用孩子链存储结构表示树 其优点之一是比较方便 A 判断两个指定结点是不是兄弟B 找指定结点的双亲C 判断指定结点在第几层D 计算指定结点的度数4 如果在树的孩子兄弟链存储结构中有6个空的左指针域 7个空的右指针域 则该树中树叶的个数为 A 7个B 6个C 13个D 不能确定 A A D B 20 5 设森林F中有3棵树 第一 第二 和第三棵树的结点个数分别为m1 m2和m3 与森林F对应的二叉树根结点的右子树上的结点个数是 A m1B m1 m2C m3D m2 m36 如果T1是由树T转换而来的二叉树 那么T中结点的后根序列就是T1中结点的 序列A 先序B 中序C 后序D 层次7 二叉树和度为2的树的相同之处包括 A 每个结点都有一个或两个孩子结点B 至少有一个根结点C 至少有一个度为2的结点D 每个结点至多只有一个双亲结点 D B D 21 8 若一棵二叉树具有10个度为2的结点 5个度为1的结点 则度为0的结点个数是 A 9B 11C 15D 不确定9 一棵完全二叉树上有1001个结点 其中叶子结点的个数是 A 500B 501C 254D 50510 一棵有124个叶子结点的完全二叉树 最多有 个结点 A 247B 248C 249D 25011 在一棵具有n个结点的完全二叉树中 分支结点的最大编号为 A n 1 2 B n 1 2 C n 2 D n 2 B B B D 22 12 如果一棵二叉树的先序序列是 a b 中序序列是 b a 则 A 结点a和结点b分别在某结点的左子树和右子树中B 结点b在结点a的右子树中C 结点b在结点a的左子树中D 结点a和结点b分别在某结点的两棵非空子树中13 设有13个值 用它们组成一棵哈夫曼树 则该哈夫曼树共有 个结点 A 13B 12C 26D 2514 根据使用频率为5个字符设计的哈夫曼编码不可能的是 A 111 110 10 01 00B 000 001 010 011 1C 100 11 10 1 0D 001 000 01 11 10 C D C 23 15 若二叉树采用二叉链表存储结构 要交换其所有分支结点左右子树的位置 采用 遍历方法最合适 A 先序B 中序C 后序D 层次16 若二叉树的中序序列是abcdef 且c为根结点 则 A 结点c有两个孩子B 二叉树有两个度为0的结点C 二叉树的高度为5D 以上都不对17 在任何一棵二叉树中 如果结点a有左孩子b 右孩子c 则在结点的先序序列 中序序列 后序序列中 A 结点b一定在结点a的前面B 结点a一定在结点c的前面C 结点b一定在结点c的前面D 结点a一定在结点b的前面 C A C 24 第七章图 7 1图的类型定义 7 2图的存储结构 7 3图的遍历 7 4最小生成树 7 5有向无环图及关键路径 7 6最短路径 25 2 熟悉图的各种存储结构 解实际问题的求解效率与采用何种存储结构有密切联系 本章学习要点 3 熟练掌握图的两种搜索路径的遍历 深度优先搜索和广度优先搜索的算法 4 掌握图的最小生成树 拓扑排序 关键路径和最短路径的求解方法 1 熟练掌握图的各相关定义 26 1 在一个有向图中 所有顶点的度数之和等于图的弧数的 倍 A 1 2B 1C 2D 42 无向图的邻接矩阵是一个 A 对称矩阵B 零矩阵C 上三角矩阵D 对角矩阵3 一个有n个结点的有向完全图有 条弧 A nB n n 1 C n n 1 2D 2n4 具有6个顶点的无向图至少应有 条边才能确保是一个连通图 A 5B 6C 7D 85 G是一个非连通无向图 共有28条边 则该图至少有 个顶点 A 6B 7C 8D 9 C A B A D 第7章练习题 27 练习题 6 下面结构中最适于表示稀疏无向图的是 A 邻接矩阵B 邻接表C 邻接多重表D 十字链表7 任何一个无向连通图有 最小生成树 A 只有一棵B 有一棵或多棵C 一定有多棵D 可能不存在8 n条边的无向图的邻接表的存储中 边结点的个数有 个 A nB 2nC n 2D n n9 如果从无向图的任一顶点出发进行一次深度优先搜索即可访问所有顶点 则该图一定是 A 完全图B 连通图C 有回路D 一棵树 C B B B 28 练习题 10 采用邻接表存储的图的深度优先遍历算法类似于二叉树的 算法 A 先序遍历B 中序遍历C 后序遍历D 层次遍历11 对于含有n个顶点的带权连通图 它的最小生成树是指图中任意一个 A 由n 1条权值最小的边构成的子图B 由n 1条权值之和最小的边构成的子图C 由n 1条权值之和最小的边构成的连通子图D 由n个顶点构成的边的权值之和最小的连通子图 A D 29 练习题 12 判断一个有向图是否存在回路除了可以利用拓扑排序方法外 还可以用 A 求关键路径的方法B 求最短路径的方法C 广度优先遍历算法D 深度优先遍历算法13 若图的邻接矩阵中主对角线上的元素全是0 其余元素全是1 则可以断定该图一定是 A 无向图B 不是带权图C 有向图D 完全图14 关键路径是AOV网中 A 从源点到汇点的最长路径B 最长的回路C 从源点到汇点的最短路径D 最短的回路15 最短路径的生成算法可用 A Prim算法B Kruskal算法C Dijkstra算法D Huffman算法 D D A C 30 练习题 填空题1 一个图的示法是唯一的 而表示法是不唯一的 2 用一个邻接矩阵存储有向图G 其第i行的所有元素之和等于顶点i的 3 图的逆邻接表存储结构只适用于图 4 连通分量是无向图的连通子图 5 一个连通图的是一个极小连通子图 6 Prim算法适用于求网的最小生成树 7 Kruskal适用于求网的最小生成树 8 如果n个顶点的图是一个环 则它有棵生成树 9 拓扑排序算法是通过重复选择具有个前驱顶点的过程来完成的 邻接矩阵 邻接表 出度 有向 极大 生成树 边稠密 边稀疏 n 0 31 第九章查找 9 1静态查找表 9 2动态查找表 9 3哈希表 32 1 顺序表和有序表的查找方法及其平均查找长度的计算方法 2 熟练掌握折半查找和判定树的构造 3 熟练掌握二叉排序树的构造和查找方法 4 熟练掌握哈希表的构造方法 深刻理解哈希表与其它结构的表的实质性的差别 5 掌握按定义计算各种查找方法在等概率情况下查找成功时的平均查找长度 本章学习要点 33 填空题1 在数据的存放无规律而言的线性表中进行查找的最佳方法是 2 线性有序表 a1 a2 a3 a256 是从小到大排列的 对一个给定的值k 用折半查找法查找表中与k相等的元素 在查找不成功的情况下 最多需要比较 次 设有100个结点 用折半查找法查找时 最大比较次数是 3 假设在有序线性表a 20 上进行折半查找 则比较一次查找成功的结点数为1 比较两次查找成功的结点数为 比较四次查找成功的结点数为 平均查找长度为 顺序查找 2 8 3 7 9 7 1 1 2 2 4 3 8 4 5 5 20 74 20 3 7 第9章练习题 34 4 折半查找有序表 4 6 12 20 28 38 50 70 88 100 若查找表中元素20 它将依次与表中元素 比较大小 5 对二叉排序数进行 遍历 可以得到按关键字从小到大排列的结点序列 6 评价哈希函数好坏的标准是 7 哈希表存储的基本思想是由 决定数据的存储地址 选择题1 静态查找表与动态查找表的根本区别在于 A 逻辑结构不一样B 施加在其上的操作不一样C 所包含的数据元素类型不一样D 存储实现不一样 28 6 12 20 中序 哈希函数取值是否均匀 B 关键字的值 35 2 在表长为n的顺序表上实施顺序查找 在查找不成功时与关键字比较的次数为 A nB 1C n 1D n 13 顺序查找适用于存储结构为 的线性表 A 哈希存储B 压缩存储C 顺序或链式存储D 索引存储4 适于折半查找的表的存储方式及元素排列要求为 A 链式 无序B 链式 有序C 顺序 无序D 顺序 有序5 对22个记录的有序表作折半查找 当查找失败时 至少需要比较 次关键字 A 3B 4C 5D 6 A C D B 36 6 二叉排序树中 键值最小的结点一定 A 左指针为空B 右指针为空C 左右指针均为空D 左右指针均非空7 在有序表 1 3 9 12 32 41 62 75 77 82 95 100 上进行折半查找关键字为82的数据元素需要比较 次 A 1B 2C 4D 58 采用分块查找时 若线性表中共有62