【精品】数据结构答疑材料

精品精品 数据结构答疑材料数据结构答疑材料 数据结构答疑材料 1 数据结构是一门研究 的程序设计问题中计算机的操作对象 以及它们之间的关系和运算等的学科 A 数值B 非数值C 字符D 数字答案B 2 快速排序的分区结果唯一吗 答案不唯一 取决于枢轴元素的选 取 3 小顶堆的堆顶元素是序列中 A 最大的元素B 次大的元素C 最小的元素D 次小的元素答案C 4 设s1 GOOD s2 BYE 则字符串s1和s2连接后的结果是 a BYE GOODb GOOD BYEc BYEDGOOD d GOODBYE答案d 5 在一个单链表中 已知p所指结点 若在p之后插入s结点 则执 行 答案s next p next p next s6 数据的逻辑结构中非线性结构有A 集合B 线形结构C 树形结构D 网状结构E 链式结构答案C树形结构 D网状结构7 线 性结构中元素之间存在 关系 树形结构中元素之间存在 关 系 图形结构中元素之间存在 关系A 一对一 多对多 一 对多B 一对多 一对一 多对多C 一对一 一对多 多对多D 多 对多 一对多 一对一E 以上都不正确答案C 一对一 一对多 多对多8 广义表 a a 的表尾是 A a B b C a D a 答案C9 算法有哪些重要特性 答案1 有穷性2 确定性3 可行性4 有输入5 有输出10 数据结构是一门研究什么 内容的学科 答案数据结构是一门研究在非数值计算的程序设计问 题中 计算机的操作对象及对象间的关系和施加于对象的操作等的 学科 11 设有一个空栈 现在有输入序列 1 2 3 4 5 经过push push pop push pop push push pop pop pop后 输出序列是 a 1 2 3 4 5b 2 3 5 4 1c 5 4 3 2 1d 1 3 4 2 5答案b 2 3 5 4 1解析1 2进栈 最先出栈的肯定是2 12 两个串相等的条件是A 长度相等B 对应位置的字符相等C 存 储位置相同D 存储结构相同E 以上都是答案AB13 顺序查找适用 于存储结构为 的线性表A 散列B 顺序或者链式C 压缩D 索引答案B14 设哈希表长m 16 哈希函数H key key 13 表中 已有3个结点H 19 6H 27 1H 23 10其余地址为空 如用线性探测再散列处理冲突 关键字14的 地址是选项 a 1b 2c 3d 0e 以上都不正确答案b解析14 13 1 因为1地址中已经有元素 所以需要再哈希求地址 14 1 13 21 5 最常用的哈希函数构造方法为A 除留余数法B 直接定址法C 折叠法D 数字分析法答案A16 一个链式队列中 假设f和r分别为 队首和队尾指针 则插入s所指结点的运算是 A r next s B r s C s r D s r next E s next r答案AB17 广义表L a x y x 的长度是 深 度是 A 33B C D E 答案A 33解析 广义表LS中的直接元素的个数称为LS的长度 广义表LS中括号的最大 嵌套层数称为LS的深度 18 在一个单链表中 已知p所指结点 若在p之后插入s结点 则执 行 A s next p next B p next s C p next s next D p next s E p next p next next答案AB19 顺序栈S为空的判定条件a S top S base b S S base c S top S d 没有正确答案答案a 20 什么叫循环队列如何区分空满循环队列 当队列采用顺序存储结 构表示时 为避免空间浪费问题发生 便提出了循环队列 相当于 把顺序队列头尾相接形成一个环状空间 判断循环队列是空还是满 通常有两种处理方法其一是在存储区域 中占用一个元素空间设一个标志位以区别队列是空还是满 其二是 少用一个元素空间 约定以 队列头指针在队列尾指针的下一位置 指环状的下一位置 上 作为队列呈满状态的标志 通常采用第二种方法 21 一个队列的入队序列是 1 3 4 2 则队列的首次输出元素是 A 3B 2C 1D 4答案C22 计算机算法指的是 1 它必须具备 2 这三个特性 1 A 计算方法B 排序方法C 解决问题的步骤序列D 调度方法 2 A 可执行性 可移植性 可扩充性B 可执行性 确定性 有穷 性C 确定性 有穷性 稳定性D 易读性 稳定性 安全性答案C B 2 3 从逻辑上可以把数据结构分为 两大类 A 动态结构 静态结构B 顺序结构 链式结构C 线性结构 非线 性结构D 初等结构 构造型结构答案C 24 数据的存储结构由哪 四种基本的存储方法实现 答案四种表示方法 1 顺序存储方式 数据元素顺序存放 每个存储结点只含一个元素 存储位置反映数据元素间的逻辑关系 存储密度大 但有些操作 如插入 删除 效率较差 2 链式存储方式 每个存储结点除包含数据元素信息外还包含一组 至少一个 指针 指针反映数据元素间的逻辑关系 这种方式不要求存储空间连续 便于动态操作 如插入 删除等 但存储空间开销大 用于指针 另外不能折半查找等 3 索引存储方式 除数据元素存储在一地址连续的内存空间外 尚需建立一个索引表 索引表中索引指示存储结点的存储位置 下标 或存储区间端点 下标 兼有静态和动态特性 4 散列存储方式 通过散列函数和解决冲突的方法 将关键字散列在连续的有限的地 址空间内 并将散列函数的值解释成关键字所在元素的存储地址 这种存储方式称为散列存储 其特点是存取速度快 只能按关键字随机存取 不能顺序存取 也 不能折半存取 25 线性表是具有n个 的有限序列 n 0 A 表元素B 字符C 数据元素D 数据项E 信息项答案C26 若长 度为n的线性表采用顺序存储结构 在其第i个位置插入一个新元素 的算法的时间复杂度为 1 i n 1 A O 0 B O 1 C O n D O n2 答案C27 线性表有两种存储结构一是顺序表 二 是链表 试问 1 如果有n个线性表同时并存 并且在处理过程中各表的长度会 动态变化 线性表的总数也会自动地改变 在此情况下 应选用哪种存储结构 为什么 2 若线性表的总数基本稳定 且很少进行插入和删除 但要求以 最快的速度存取线性表中的元素 那么应采用哪种存储结构 为什 么 答案 1 选链式存储结构 它可动态申请内存空间 不受表长度 即表中元素个数 的影响 插入 删除时间复杂度为O 1 2 选顺序存储结构 顺序表可以随机存取 时间复杂度为O 1 28 若较频繁地对一个线性表进行插入和删除操作 该线性表宜采 用何种存储结构 为什么 答案采用链式存储结构 它根据实际需 要申请内存空间 而当不需要时又可将不用结点空间返还给系统 在链式存储结构中插入和删除操作不需要移动元素 29 线性结构包括 和 线性表的存储结构分成 和 答案线性表栈队列串顺序存储结构和链式存储结构30 对于栈操作 数据的原则是 A 先进先出B 后进先出C 后进后出D 不分顺序答案B 31 一个栈的 输入序列为123 n 若输出序列的第一个元素是n 输出第i 1 i n 个元素是 A 不确定B n i 1C i D n i答案B32 有六个元素6 5 4 3 2 1的顺序进栈 问下列哪一 个不是合法的出栈序列 A 543612B 453126C 346521D 234156 答案C 33 栈和队列的共同点是 A 都是先进先出B 都是先进后出C 只允许在端点处插入和删除元素D 没有共同点答案C34 判断栈与队列是一种特殊操作的线性表 答案 35 判断栈和队列都是线性表 只是在插入和删除时受 到了一些限制 答案 36 名词解释栈 答案栈是只准在一端进行插入和删除操作的线性表 允许插入和删 除的一端叫栈顶 另一端叫栈底 最后插入的元素最先删除 故栈也称后进先出 LIFO 表 37 名词解释队列答案队列是允许在一端插入而在另一端删除的线 性表 允许插入的一端叫队尾 允许删除的一端叫队头 最先插入队的元素最先离开 删除 故队列也常称先进先出 FIF O 表 38 若元素的进栈序列为A B C D E 运用栈操作 能否得到出 栈序列B C A E D和D B A C E 为什么 答案能得到出栈 序列B C A E D 不能得到出栈序列D B A C E 其理由为若出栈序列以D开头 说明在D之前的入栈元素是A B和C 三个元素中C是栈顶元素 B和A不可能早于C出栈 故不可能得到D B A C E出栈序列 39 什么叫串的模式匹配算法答案就是给定一个串和子串 定位字 串在串中位置的算法 40 下面关于串的的叙述中 哪一个是不正确的 A 串是字符 的有限序列B 空串是由空格构成的串C 模式匹配是串的一种重要 运算D 串既可以采用顺序存储 也可以采用链式存储答案B41 串 的长度是指 A 串中所含不同字母的个数B 串中所含字符的个 数C 串中所含不同字符的个数D 串中所含非空格字符的个数答案B 42 设s I AMA STUDENT 则字符串的长度Length s A 11B 12C 14D 1543 空格串是指 1 其长度等于 2 答案 1 由空格字符 ASCII值32 所组成的字符串 2 空格个数44 串是一种特殊的线性表 其特殊性表现在 1 串的两种最基本的存储方式是 2 3 两个串相等的充分必要条件是 4 答案 1 其数据元素都是字符 2 顺序存储 3 和链式存储 4 串的长度相等且两串中对应位置的字符也相等45 描述以下概念 的区别空格串与空串答案空格是一个字符 其ASCII码值是32 空格串是由空格组成的串 其长度等于空格的个数 空串是不含任何字符的串 即空串的长度是零 46 广义表有两个特殊的基本运算答案取表头head LS 取表中的第 一个数据元素 不能对空表操作 取表尾tail LS 取除表头外 其余数据元素构成的子表 不能对空 表操作 47 广义表 a b c d 的表头是 表尾是 A a B C a b c d D b c d 答案C48 广义表 a b c d e 的表头为 A a B a b c C a b c D a 答案A 49 广义表 a b c d 的表头是 表尾是 A b B a C a D b c d E b c d答案B a D b c d 50 已知一算术 表达式的中缀形式为A B C D E 后缀形式为ABC DE 其前缀形式为 A A B C DE B A B CD E C ABC DE D A BC DE答案D 51 若采用孩子兄弟链表作为树的存储结构 则树的先根遍历应采 用二叉树的 A 层次遍历B 先序遍历C 中序遍历D 后序遍历答案B 52 二叉树的5个性质53 有关二叉树下列说法正确的是 A 二 叉树的度为2B 一棵二叉树的度可以小于2C 二叉树中至少有一个 结点的度为2D 二叉树中任何一个结点的度都为2答案B55 一棵树 高为K的完全二叉树至少有 个结点A 2k 1B 2k 1 1C 2k 1D 2k答案C56 已知一棵二叉树的前序遍历结果为ABCDEF 中序遍历 结果为CBAEDF 则后序遍历的结果为 A CBEFDA B FEDCBA C CBEDFA D 不定答案A57 线索二叉树是一种 结构 A 逻辑B 逻辑和存储C 物理D 线性答案C58 由3个结点可以构 造出多少种不同的二叉树 A 2B 3C 4D 5答案D59 从概念 上讲 树 森林和二叉树是三种不同的数据结构 将树 森林转化 为二叉树的基本目的是什么 并指出树和二叉树的主要区别 答案树的孩子兄弟链表表示法和二叉树二叉链表表示法 本质是一 样的 只是解释不同 也就是说树 树是森林的特例 即森林中只 有一棵树的特殊情况 可用二叉树唯一表示 并可使用二叉树的一 些算法去解决树和森林中的问题 树和二叉树的区别有三一是二叉树的度至多为2 树无此限制 二是 二叉树有左右子树之分 即使在只有一个分枝的情况下 也必须指 出是左子树还是右子树 树无此限制 三是二叉树允许为空 树一 般不允许为空 个别书上允许为空 60 树和二叉树之间有什么样的区别与联系 答案树和二叉树逻辑 上都是树形结构 区别有以上题1所述三点 二叉树不是树的特例 61 请分析线性表 树 广义表的主要结构特点 以及相互的差异 与关联 答案线性表属于约束最强的线性结构 在非空线性表中 只有一个 第一个 元素 也只有一个 最后一个 元素 除第一个元素外 每个元素有唯一前驱 除最后一个元素外 每个元素有唯一后继 树是一种层次结构 有且只有一个根结点 每个结点可以有多个子 女 但只有一个双亲 根无双亲 从这个意义上说存在一 双亲 对多 子女 的关系 广义表中的元素既可以是原子 也可以是子表 子表可以为它表共 享 从表中套表意义上说 广义表也是层次结构 从逻辑上讲 树和广义表均属非线性结构 但在以下意义上 又蜕变为线性结构 如度为1的树 以及广义表中的元素都是原子时 另外 广义表从元素之间的关系可看成前驱和后继 也符合线性表 但这时元素有原子 也有子表 即元素并不属于同一数据对象 62 已知完全二叉树有30个结点 则整个二叉树有多少个度为0的结 点 答案 1563 假设有向图含n个顶点及e条弧 则表示该图的邻接表中包含 的弧结点个数为 A n B e C 2e D n e答案B64 一个n个顶点的连通无向图 其边的个数至少为 A n 1B n C n 1D nlogn 答案A65 n个结点的完全有向图含有边的数目 A n n n n C n 2D n n l 答案D66 判断一个无 向图是一棵树的条件是 答案有n个顶点 n 1条边的无向连通图67 具有10个顶点的无向图 边的总数最多为 答案4568 求图的最小生成树有两种算法 算法适合于求稀 疏图的最小生成树 答案克鲁斯卡尔69 下面描述的是一种构造最小生成树算法的基本 思想 设要处理的无向图包括n个节点V1 V2 Vn 用相邻矩阵A 表示 边的权全是正数 请在下列划线处填上正确叙述 1 若 Vi Vj 是边 则A i j 的值等于 若 Vi Vj 不是边 则A i j 的值是一个比任何边的权 矩阵 的对角线元素全为0 2 构造最小生成树过程中 若节点Vi已包括进生成树 就把相 邻矩阵的对角线元素A i i 置成 若 Vi Vj 已包括进 生成树 就把矩阵元素A i j 置成 3 算法结束时 相邻矩阵中 的元素指出最小生成树的 答案 1 Vi Vj 边上