《数据结构》期中试卷-2014-2015学年第二学期.pdf

第 1 页 共 7 页 装 订 线 此 处 不 能 书 写 此 处 不 能 书 写 此 处 不 能 书 写 此 处 不 能 书 写 此 处 不 能 书 写 此 处 不 能 书 写 此 处 不 能 书 写 北京理工大学珠海学院北京理工大学珠海学院 2012014 4 2012015 5 学年第二学年第二学期学期 数据结构数据结构 期中试卷期中试卷 诚信声明诚信声明 考场是严肃的 作弊是可耻的 对作弊人的处分是严厉的 我承诺遵守考场纪律 不存在抄袭及其它违纪行为 考生 承诺人 签字 专业 专业 班级 班级 学号 学号 适用年级专业 适用年级专业 14 级软件工程 试卷说明 试卷说明 闭卷 考试时间 90 分钟 题号 一 二 三 四 总分 得分 一 一 单项单项选择题 每选择题 每小题小题2 2分分 共共3 30 0分分 得分 得分 1 设计一个判别表达式中左 右括号是否配对出现的算法 采用 数据 结构最佳 A 线性表的顺序存储结构 B 栈 C 队列 D 线性表的链式存储结构 2 下面两段程序的时间复杂性是 1 i 1 while i n i i 2 2 for i 2 i n i for j 2 jnext NULL C head next head D head NULL 4 在一个具有n个单元的顺序栈中 假设栈底是存储地址的低端 现以top作 第 2 页共 7 页 为栈顶指针 指向栈顶元素的下一个位置 当进行出栈操作时 假定栈非空 top的变化是 A top top 1 B top top 1 C top不变 D top不确定 5 一个栈的入栈序列为 a b c d 则出栈序列不可能的是 A a b c d B c b a d C d c b a D d b c a 6 二维数组 SA 中 每个元素的长度为 3 个字节 行下标 I 从 0 到 7 列下标 J 从 0 到 9 从首地址 SA 开始连续存放在存储器内 该数组按行优先存放时 元素 A 6 8 的起始地址为 A SA 210 B SA 171 C SA 204 D 以上都不对 7 在数据结构中 从逻辑上可以把数据结构分成 A 动态和静态结构 B 紧凑接和非紧凑结构 C 线性与非线性结构 D 内部结构和外部结构 8 链表不具有的特点是 A 可随机访问任一元素 B 插入删除不需要移动元素 C 不必事先估计存储空间 D 所需空间与线性表长度成正比 9 在一个单链表中 已知 q 是 p 的前趋结点 若 q 和 p 之间插入结点 s 则 执行 s next p next p next s p next s next s next p q next s s next p p next s s next q 10 若某线性表中最常用的操作是取第 i 个元素和找第 i 个元素的前趋元素 则采用 存储方式最节省时间 A 顺序表 B 单链表 C 双向链表 D 循环链表 11 下面关于串的的叙述中 哪一个是不正确的 A 串是字符的有限序列 B 空串是由空格构成的串 C 模式匹配是串的一种重要运算 D 串既可以采用顺序存储 也可以采用链式存储 12 循环链表主要优点是 A 不再需要头指针了 B 已知某个结点的位置后 能够容易找到它的直接前趋 C 在进行插入 删除运算时 能更好地保证链表不断开 D 从表中任一结点出发都能扫描到整个链表 13 删除双链表中间某个节点时 需要修改 个指针域 A 1 B 2 C 3 D 4 14 循环队列 SQ 采用数组空间 SQ base 0 n 1 存放其元素值 已知其头尾指 针分别是 front 和 rear 则判定此循环队列为空和为满的条件分别是 第 3 页 共 7 页 装 订 线 此 处 不 能 书 写 此 处 不 能 书 写 此 处 不 能 书 写 此 处 不 能 书 写 此 处 不 能 书 写 此 处 不 能 书 写 此 处 不 能 书 写 A Q front Q rear Q front Q rear B Q front Q rear Q front Q rear C Q front Q rear Q front Q rear 1 n D Q front Q rear Q front Q rear 1 n 15 利用栈求表达式的值时 设立操作数栈 OPND 假设 OPND 只有两个存储单 元 在下列表达式中 不发生溢出的是 A A B C D B A B C D C A B C D D A B C D 二二 填空 填空题题 每每空空 2 2 分分 共 共 2020 分分 得分 得分 1 若一个算法中的语句频度之和为 T n 3n n log2n 4 则算法的时间复杂 度为 2 假设为循环队列分配的向量空间为 Q 20 下标从 0 开始 若队列的长度 和队头指针值分别为 13 和 17 则当前队尾指针的值为 3 表长为 N 的顺序表 当在任何位置上插入或删除一个元素的概率相等时 插入一个元素所需移动元素的平均次数为 删除一个元素需要移 动的元素个数为 4 将一个下三角矩阵 A 1 50 1 50 按行优先存入一维数组 B 1 n 中 A 中元素 A 30 20 在 B 数组中的位置为 5 模式串 ababab 采用 KMP 算法的 next 数组为 修正 nextval 数组为 6 设 S I am a Student T good 则 ConCat T SubStr S 7 8 7 栈的特点是 队列的特点是 三 三 简答简答题题 每每题题 5 5 分分 共 共 2 20 0 分分 得分 得分 1 假设 Q 0 9 是一个非循环线性队列 初始状态为 front rear 0 画出做完 下列操作后队列的头尾指针的状态变化情况 如果不能入队 请指出其元素 并说明理由 d e b g h 入队 d e 出队 I j k l m 入队 b 出队 n o p q r 入队 第 4 页共 7 页 2 对于堆栈 给出三个输入项 A B C 如果输入项序列为 ABC 试给出全部 可能的输出序列 并写出每种序列对应的操作 例如 A 进 B 进 C 进 C 出 B 出 A 出 产生的序列为 CBA 3 已知稀疏矩阵如下所以 请写出该稀疏矩阵对应的三元组表示和该矩阵转 制矩阵的三元组表示 4 有程序如下 则此程序的输出结果 栈的元素类型是 SelemType 为 char 是 什么 Void main stack s char x y initstack s x c y k push s x push s a push s y pop s x push s t push s x pop s x push s s while stackempty s pop s y printf y printf x 第 5 页 共 7 页 装 订 线 此 处 不 能 书 写 此 处 不 能 书 写 此 处 不 能 书 写 此 处 不 能 书 写 此 处 不 能 书 写 此 处 不 能 书 写 此 处 不 能 书 写 四四 算法阅读题 算法阅读题 每每题题 6 6 分分 共 共 1818 分分 1 一线性链表如下图 1 所示 以下程序段作用是将该线性链表逆置 逆置后 链表如图 2 所示 请在下划线处填充适当的语句 可以写多条语句 Status InverseList L LinkList L next NULL while p q p next return OK InverseList L 图 1 图 2 2 已知顺序栈存储结构的定义 以下运算实现在顺序栈上的入栈和出栈 请 在下划线处用适当的语句予以填充 可以写多条语句 define STACK INIT SIZE 100 存储空间的初始分配量 define STACKINCREMENT 10 存储空间的分配增量 typedef struct 第 6 页共 7 页 SElemType base 栈底指针 SElemType top 栈指针 int stacksize 当前分配的存储容量 SqStack Status Push SqStack if S base exit OVERFLOW S stacksize STACKINCREMENT return OK Push Status Pop SqStack return OK Pop 3 算法 fun2 实现在带头结点的单链表第 i 个位置的插入元素 e 整型 请在 处补充适当的语句 可以写多条语句 完成算法 typedef struct LNode int data 数据域 struct LNode next 指针域 LNode LinkList Status fun2 LinkList j 0 while p j 寻找第 i 1 个结点 第 7 页 共 7 页 装 订 线 此 处 不 能 书 写 此 处 不 能 书 写 此 处 不 能 书 写 此 处 不 能 书 写 此 处 不 能 书 写 此 处 不 能 书 写 此 处 不 能 书 写 if p j i 1 return ERROR i 小于 1 或大于 表长 1 s LinkList malloc sizeof LNode 生成新结点 return OK fun2 五 算法设计题 五 算法设计题 1 1 小题小题 共 共 1 12 2 分 得分 分 得分 已知栈的基本操作函数