工程图学总复习题

数据结构和算法的基本概念一判断题（下列各题，正确的请在前面的括号内打；错误的打 ）（） （1）数据的逻辑结构与数据元素本身的内容和形式无关。（） （2）一个数据结构是由一个逻辑结构和这个逻辑结构上的一个基本运算集构成的整体。（） （3）数据元素是数据的最小单位。（） （4）数据的逻辑结构和数据的存储结构是相同的。（） （5）程序和算法原则上没有区别，所以在讨论数据结构时可以通用。（） （6）从逻辑关系上讲，数据结构主要分为线性结构和非线性结构两类。（） （7）数据的存储结构是数据的逻辑结构的存储映像。（） （8）数据的物理结构是指数据在计算机内实际的存储形式。（） （9）数据的逻辑结构是依赖于计算机的。（） （10）算法是对解题方法和步骤的描述。三选择题（1 ）数据结构通常是研究数据的（ A ）及它们之间的相互联系。A. 存储结构和逻辑结构 B. 存储和抽象 C. 联系和抽象 D. 联系与逻辑（2 ）在逻辑上可以把数据结构分成：（ C ） 。A. 动态结构和静态结构 B. 紧凑结构和非紧凑结构 C. 线性结构和非线性结构 D. 内部结构和外部结构（3 ）数据在计算机存储器内表示时，物理地址和逻辑地址相同并且是连续的，称之为（ C ） 。A. 存储结构 B. 逻辑结构 C. 顺序存储结构 D. 链式存储结构（4 ）非线性结构中的每个结点（ D ） 。无直接前趋结点无直接后继结点只有一个直接前趋结点和一个直接后继结点可能有多个直接前趋结点和多个直接后继结点（5 ）链式存储的存储结构所占存储空间（ A ） 。A 分两部分，一部分存放结点的值，另一部分存放表示结点间关系的指针B 只有一部分，存放结点的值C 只有一部分，存储表示结点间关系的指针D 分两部分，一部分存放结点的值，另一部分存放结点所占单元素（6 ）算法的计算量大小称为算法的（ C ） 。A. 现实性 B. 难度 C. 时间复杂性 D. 效率（7 ）数据的基本单位是（ B ） 。A. 数据结构 B. 数据元素 C. 数据项 D. 文件（8 ）每个结点只含有一个数据元素，所有存储结点相继存放在一个连续的存储区里，这种存储结构称为（ A ）结构。A. 顺序存储 B. 链式存储 C. 索引存储 D. 散列存储（9 ）每一个存储结点不仅含有一个数据元素，还包含一组指针，该存储方式是（ B ）存储方式。A. 顺序 B. 链式 C. 索引 D. 散列（10 ）以下任何两个结点之间都没有逻辑关系的是（ D ） 。A. 图形结构 B. 线性结构 C. 树形结构 D. 集合（11 ）在数据结构中，与所使用的计算机无关的是（ C ） 。A. 物理结构 B. 存储结构 C. 逻辑结构 D. 逻辑和存储结构（12 ）下列四种基本逻辑结构中，数据元素之间关系最弱的是（ A ） 。A. 集合 B. 线性结构 C. 树形结构 D. 图形结构（13 ）与数据元素本身的形式、内容、相对位置、个数无关的是数据的（ A ） 。A. 逻辑结构 B. 存储结构 C. 逻辑实现 D. 存储实现（14 ）每一个存储结点只含有一个数据元素，存储结点存放在连续的存储空间，另外有一组指明结点存储位置的表，该存储方式是（ C ）存储方式。A. 顺序 B. 链式 C. 索引 D. 散列（15 ）算法能正确的实现预定功能的特性称为算法的（ A ） 。A. 正确性 B. 易读性 C. 健壮性 D. 高效性（16 ）算法在发生非法操作时可以作出处理的特性称为算法的（ C ） 。A. 正确性 B. 易读性 C. 健壮性 D. 高效性（17 ）下列时间复杂度中最坏的是（ D ） 。A. O（1） B. O（ n） C. O（log 2n） D. O（n 2）（18 ）下列算法的时间复杂度是（ D ） 。for (i=0;iprior-next=p-next 。在 如 图 所 示 的 链 表 中 ， 若 在 指 针 P所 在 的 结 点 之 后 插 入 数 据 域 值 为 a和 b的 两 个 结点 ， 则 可 用 下 列 两 个 语 句 ： S-next-next=P-next; 和 P-next=S;来 实 现 该操 作 。a b三选择题（1 ）在具有 n 个结点的单链表中，实现（ A ）的操作，其算法的时间复杂度都是O（n） 。A遍历链表或求链表的第 i 个结点 B在地址为 P 的结点之后插入一个结点C删除开始结点 D删除地址为 P 的结点的后继结点（2 ）设 a、b 、c 为三个结点， p、10、20 分别代表它们的地址，则如下的存储结构称为（ B ） 。循环链表 B 单链表 C双向循环链表 D 双向链表（3 ）单链表的存储密度（ C ） 。A 大于 1 B 等于 1 C小于 1 D 不能确定（4 ）已知一个顺序存储的线性表，设每个结点占 m 个存储单元，若第一个结点的地址为B，则第 i 个结点的地址为（ A ） 。A B+(i-1)*m BB+i*m C B-i*m D B+(i+1)*m（5 ）在有 n 个结点的顺序表上做插入、删除结点运算的时间复杂度为（ B ） 。AO（1） BO（n） CO（n 2） DO（log 2n）（6 ）设 Llink、Rlink 分别为循环双链表结点的左指针和右指针，则指针 P 所指的元素是双循环链表 L 的尾元素的条件是（ D ） 。AP= L B P-Llink= L CP= NULL DP-Rlink=L（7 ） 两个指针 P 和 Q，分别指向单链表的两个元素，P 所指元素是 Q 所指元素前驱的条件是（ B ） 。AP-next=Q-next BP-next= Q CQ-next= P DP= Q（8 ）用链表存储的线性表，其优点是（ C ） 。A 便于随机存取 B 花费的存储空间比顺序表少C 便于插入和删除 D 数据元素的物理顺序与逻辑顺序相同（9 ）在单链表中，增加头结点的目的是（ C ） 。A 使单链表至少有一个结点 B 标志表中首结点的位置C 方便运算的实现 D 说明该单链表是线性表的链式存储结构（10 ）下面关于线性表的叙述中，错误的是（ D ）关系。A顺序表必须占一片地址连续的存储单元 B顺序表可以随机存取任一元素C链表不必占用一片地址连续的存储单元 D链表可以随机存取任一元素（11 ）L 是线性表，已知 LengthList（L）的值是 5，经 DelList（L，2）运算后，LengthList（L）的值是（ C ） 。A2 B 3 C4 D5（12 ）单链表的示意图如下：LA B C D 指向链表 Q 结点的前趋的指针是（ B ） 。AL BP CQ DR（13 ）设 p 为指向单循环链表上某结点的指针，则*p 的直接前驱（ C ） 。A找不到 B查找时间复杂度为 O（1）C查找时间复杂度为 O（n） D查找结点的次数约为 n（14 ）等概率情况下，在有 n 个结点的顺序表上做插入结点运算，需平均移动结点的数目为（ C ） 。An B(n-1)/2 C n/2 D(n+1)/2（15 ）在下列链表中不能从当前结点出发访问到其余各结点的是（ C ） 。A双向链表 B单循环链表 C单链表 D双向循环链表（16）在顺序表中，只要知道（ D ） ，就可以求出任一结点的存储地址。A基地址 B结点大小 C 向量大小 D基地址和结点大小（17 ）在双链表中做插入运算的时间复杂度为（ A ） 。AO（1） BO（n） CO（n 2） DO（log 2n）（18 ）链表不具备的特点是（ A ） 。A随机访问 B不必事先估计存储空间C插入删除时不需移动元素 D所需空间与线性表成正比（19 ）以下关于线性表的论述，不正确的为（ C ） 。A线性表中的元素可以是数字、字符、记录等不同类型B线性顺序表中包含的元素个数不是任意的C线性表中的每个结点都有且仅有一个直接前趋和一个直接后继D存在这样的线性表，即表中没有任何结点（20 ）在（ B ）的运算中，使用顺序表比链表好。A插入 B根据序号查找 C 删除 D根据元素查找栈和队列一判断题（下列各题，正确的请在前面的括号内打；错误的打 ）（） （1 ） 栈 是 运 算 受 限 制 的 线 性 表 。（） （2） 在 栈 空 的 情 况 下 ， 不 能 作 出 栈 操 作 ， 否 则 产 生 下 溢 出 。（） （3）栈一定是顺序存储的线性结构。（） （4 ） 栈 的 特 点 是 “后 进 先 出 ”。（） （5）空栈就是所有元素都为 0 的栈。（） （6）在 C 或 C+语言中设顺序栈的长度为 MAXLEN，则 top=MAXLEN 时表示队满。（） （7） 链 栈 与 顺 序 栈 相 比 ， 其 特 点 之 一 是 通 常 不 会 出 现 栈 满 的 情 况 。（） （8）一个栈的输入序列为： A，B，C，D，可以得到输出序列：C，A，B，D。（） （9 ） 递 归 定 义 就 是 循 环 定 义 。（） （1 0） 将 十 进 制 数 转 换 为 二 进 制 数 是 栈 的 典 型 应 用 之 一 。二填空题（ 1） 在 栈 结 构 中 ， 允 许 插 入 、 删 除 的 一 端 称 为 栈 顶 。（ 2） 在 顺 序 栈 中 ， 当 栈 顶 指 针 top=-1时 ， 表 示 栈 空 。（ 3） 在 有 n个 元 素 的 栈 中 ， 进 栈 操 作 的 时 间 复 杂 度 为 O（ 1） 。（ 4） 在 栈 中 ， 出 栈 操 作 的 时 间 复 杂 度 为 ： O(1) 。（ 5） 已 知 表 达 式 ， 求 它 的 后 缀 表 达 式 是 栈 的 典 型 应 用 。 （ 6） 在 一 个 链 栈 中 ， 若 栈 顶 指 针 等 于 NULL， 则 表 示 栈 空 。（ 7） 向 一 个 栈 顶 指 针 为 top的 链 栈 插 入 一 个 新 结 点 *p时 ， 应 执 行 p-next=top； 和 top=p； 操 作 。（ 8） 顺 序 栈 S存 储 在 数 组 S-data0.MAXLEN-1中 ， 进 栈 操 作 时 要 执 行 的 语 句 有 ：S-top + 。 （ 或 = S-top+1）（ 9） 链 栈 LS， 指 向 栈 顶 元 素 的 指 针 是 LS-next 。（10 ）从一个栈删除元素时，首先取出 栈顶元素 ，然后再移动栈顶指针。（11 ）由于链栈的操作只在链表的头部进行，所以没有必要设置 头 结点。（12 ）已知顺序栈 S，在对 S 进行进栈操作之前首先要判断 栈是否满 。（13 ）已知顺序栈 S，在对 S 进行出栈操作之前首先要判断 栈是否空 。（14 ）若内存空间充足， 链 栈可以不定义栈满运算。（ 15） 链 栈 LS是 空 的 条 件 是 LS-next=NULL 。（ 16） 链 栈 LS的 栈 顶 元 素 是 链 表 的 首 元 素 。（ 17） 同 一 栈 的 各 元 素 的 类 型 相 同 。（18 ）若进栈的次序是 A、B 、C 、D 、E，执行三次出栈操作以后，栈顶元素为 B 。（19 ）A+B/C-D*E 的后缀表达式是： ABC/+DE*- 。（ 20） 四 个 元 素 按 A、 B、 C、 D顺 序 进 S栈 ， 执 行 两 次 Pop（ S， x） 运 算 后 ， x的 值是 C 。三选择题（ 1） 插 入 和 删 除 只 能 在 一 端 进 行 的 线 性 表 ， 称 为 ( C )。A 队 列 B 循 环 队 列 C 栈 D 循 环 栈 （ 2） 设 有 编 号 为 1， 2， 3， 4的 四 辆 列 车 ， 顺 序 进 入 一 个 栈 结 构 的 站 台 ， 下 列 不 可 能的 出 站 顺 序 为 ( D )A 1234 B 1243 C 1324 D 1423（ 3） 如 果 以 链 表 作 为 栈 的 存 储 结 构 ， 则 出 栈 操 作 时 （ B ）A 必 须 判 别 栈 是 否 满 B 必 须 判 别 栈 是 否 空C 必 须 判 别 栈 元 素 类 型 D 队 栈 可 不 做 任 何 判 别（ 4） 元 素 A,B,C,D依 次 进 栈 以 后 ， 栈 顶 元 素 是 （ D ）A A B B C C D D（ 5） 顺 序 栈 存 储 空 间 的 实 现 使 用 （ B ） 存 储 栈 元 素 。A 链 表 B 数 组 C 循 环 链 表 D 变 量（ 6） 在 C或 C+语 言 中 ， 一 个 顺 序 栈 一 旦 被 声 明 ， 其 占 用 空 间 的 大 小 （ A ） 。A 已 固 定 B 不 固 定 C 可 以 改 变 D 动 态 变 化（ 7） 带 头 结 点 的 链 栈 LS的 示 意 图 如 下 ， 栈 顶 元 素 是 （ A ）LSH A B C D A A B B C C D D（ 8） 链 栈 与 顺 序 栈 相 比 ， 有 一 个 比 较 明 显 的 优 点 是 （ B ） 。A 插 入 操 作 更 加 方 便 B 通 常 不 会 出 现 栈 满 的 情 况 。C 不 会 出 现 栈 空 的 情 况 D 删 除 操 作 根 加 方 便（ 9） 从 一 个 栈 顶 指 针 为 top的 链 栈 中 删 除 一 个 结 点 时 ， 用 x保 存 被 删 除 的 结 点 ， 应执 行 下 列 ( D )命 令 。A x=top;top=top-next; B top=top-next;x=top-data;C x=top-data; D x=top-data;top=top-next;（ 10） 在 一 个 栈 顶 指 针 为 HS的 链 栈 中 ， 将 一 个 S指 针 所 指 的 结 点 入 栈 ， 应 执 行 下 列 ( B )命 令 。A HS-next=S; B S-next=HS-next;HS-next=S;C S-next=HS-next;HS=S; D S-next=HS;HS=HS-next;（ 11） 四 个 元 素 按 A、 B、 C、 D顺 序 进 S栈 ， 执 行 两 次 Pop（ S， x） 运 算 后 ， 栈 顶 元素 的 值 是 （ B ） 。A A B B C C D D（ 12） 元 素 A,B,C,D依 次 进 栈 以 后 ， 栈 底 元 素 是 （ A ） 。A A B B C C D D（ 13） 经 过 下 列 栈 的 运 算 后 ， 再 执 行 ReadTop(s)的 值 是 （ A ） 。InitStack(s) （ 初 始 化 栈 ） ;Push(s,a);Push(s,b); Pop(s)A a B b C 1 D 0（ 14） 经 过 下 列 栈 的 运 算 后 ， x的 值 是 （ B ） 。InitStack(s) （ 初 始 化 栈 ） ;Push(s,a);Push(s,b); ReadTop(s);Pop(s,x);A a B b C 1 D 0（ 15） 经 过 下 列 栈 的 运 算 后 ， x的 值 是 （ B ） 。InitStack(s) （ 初 始 化 栈 ） ;Push(s,a);Pop(s,x);Push(s,b);Pop(s,x);A a B b C 1 D 0（ 16） 经 过 下 列 栈 的 运 算 后 ， SEmpty(s)的 值 是 （ C ） 。InitStack(s) （ 初 始 化 栈 ） ; Push(s,a); Push(s,b);Pop(s,x); Pop(s,x);A a B b C 1 D 0（ 17） 向 顺 序 栈 中 压 入 元 素 时 ， （ B ） 。先 存 入 元 素 ， 后 移 动 栈 顶 指 针 B 先 移 动 栈 顶 指 针 ， 后 存 入 元 素C 谁 先 谁 后 无 关 紧 要 D 同 时 进 行（ 18） 初 始 化 一 个 空 间 大 小 为 5的 顺 序 栈 S后 ， S-top的 值 是 （ B ） 。A 0 B -1 C 不 再 改 变 D 动 态 变 化（ 19） 一 个 栈 的 入 栈 次 序 ABCDE， 则 栈 的 不 可 能 的 输 出 序 列 是 ( C )。A EDCBA B DECBA C DCEAB D ABCDE（ 20） 设 有 一 个 顺 序 栈 S， 元 素 A,B,C,D,E,F,依 次 进 栈 ， 如 果 六 个 元 素 出 栈 的 顺 序是 B， D， C， F， E， A， 则 栈 的 容 量 至 少 应 是 ( A )。A 3 B 4 C 5 D 6队列一判断题（下列各题，正确的请在前面的括号内打；错误的打 ）（） （1 ） 队 列 是 限 制 在 两 端 进 行 操 作 的 线 性 表 。（） （2） 判 断 顺 序 队 列 为 空 的 标 准 是 头 指 针 和 尾 指 针 都 指 向 同 一 个 结 点 。（） （3）在链队列上做出队操作时，会改变 front 指针的值。（） （4）在循环队列中，若尾指针 rear 大于头指针 front，其元素个数为 rear- front。（） （5）在单向循环链表中，若头指针为 h，那么 p 所指结点为尾结点的条件是 p=h。（） （6）链队列在一定范围内不会出现队满的情况。（） （7）在循环链队列中无溢出现象。（） （8）栈和队列都是顺序存储的线性结构。（） （9 ） 在 队 列 中 允 许 删 除 的 一 端 称 为 队 尾 。（） （1 0） 顺 序 队 和 循 环 队 关 于 队 满 和 队 空 的 判 断 条 件 是 一 样 的 。二填空题在 队 列 中 存 取 数 据 应 遵 循 的 原 则 是 先 进 先 出 。队 列 是 被 限 定 为 只 能 在 表 的 一 端 进 行 插 入 运 算 ， 在 表 的 另 一 端 进 行 删 除 运 算 的线 性 表 。在 队 列 中 ， 允 许 插 入 的 一 端 称 为 队 尾 。在 队 列 中 ， 允 许 删 除 的 一 端 称 为 队 首 （ 或 队 头 ） 。队 列 在 进 行 出 队 操 作 时 ， 首 先 要 判 断 队 列 是 否 为 空 。顺 序 队 列 在 进 行 入 队 操 作 时 ， 首 先 要 判 断 队 列 是 否 为 满 。顺 序 队 列 初 始 化 后 ， front=rear= -1 。解决顺序队列“假溢出”的方法是采用 循环队列 。循环队列的队首指针为 front，队尾指针为 rear，则队空的条件为 front = rear 。链 队 列 LQ为 空 时 ， LQ-front-next= NULL 。设 长 度 为 n的 链 队 列 用 单 循 环 链 表 表 示 ， 若 只 设 头 指 针 ， 则 入 队 操 作 的 时 间 复 杂 度 为 O（ n） 。设 长 度 为 n的 链 队 列 用 单 循 环 链 表 表 示 ， 若 只 设 尾 指 针 ， 则 出 队 操 作 的 时 间 复 杂 度 为 0（ 1） 。在 一 个 链 队 列 中 ， 若 队 首 指 针 与 队 尾 指 针 的 值 相 同 ， 则 表 示 该 队 列 为 空 。设 循 环 队 列 的 头 指 针 front指 向 队 首 元 素 ， 尾 指 针 rear指 向 队 尾 元 素 后 的 一 个 空 闲元 素 ， 队 列 的 最 大 空 间 为 MAXLEN， 则 队 满 标 志 为 ： front=(rear+1)%MAXLEN 。在 一 个 链 队 列 中 ， 若 队 首 指 针 为 front， 队 尾 指 针 为 rear， 则 判 断 该 队 列 只 有 一 个结 点 的 条 件 为 ： front=rear InQueue(Q,a); InQueue(Q,b);OutQueue(Q,x); ReadFront(Q,x);QEmpty(Q);后的值是 0 。（20）队列 Q 经过 InitQueue(Q)(初 始 化 队 列 );InQueue(Q,a);InQueue(Q,b); ReadFront(Q,x)后，x 的值是 a 。三选择题（ 1） 队 列 是 限 定 在 （ D ） 进 行 操 作 的 线 性 表 。A 中 间 B 队 首 C 队 尾 D 端 点（ 2） 队 列 中 的 元 素 个 数 是 ( B )。A 不 变 的 B 可 变 的 C 任 意 的 D 0（ 3） 同 一 队 列 内 各 元 素 的 类 型 ( A )。A 必 须 一 致 B 不 能 一 致 C 可 以 不 一 致 D 不 限 制（ 4） 队 列 是 一 个 ( C )线 性 表 结 构 。A 不 加 限 制 的 B 推 广 了 的 C 加 了 限 制 的 D 非（ 5） 当 利 用 大 小 为 n的 数 组 顺 序 存 储 一 个 队 列 时 ， 该 队 列 的 最 后 一 个 元 素 的 下 标 为 （ B ） 。A n-2 B n-1 C n D n+1（ 6） 一 个 循 环 队 列 一 旦 说 明 ， 其 占 用 空 间 的 大