《数据结构》期中试卷-2015-2016学年第一学期(1).pdf

北京理工大学珠海学院 2015 2016学年第一学期 数据结构 期中试卷 诚信声明 考场是严肃的 作弊是可耻的 对作弊人的处分是严厉的 我承诺遵守考场纪律 不存在抄袭及其它违纪行为 考生 承诺人 签字 专业 班级 学号 适用年级专业 14级计科 网工 数媒专业 试卷说明 闭卷 考试时间90分钟 题号一二三四总分 得分 一 单项选择题 每小题2分 共30分 得分 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 1 设计一个判别表达式中左 右括号是否配对出现的算法 采用 数据结构最佳 A 线性表的顺序存储结构 B 栈 C 队列 D 线性表的链式存储结构 2 以下算法的时间复杂度为 void fun int n int i l while inext NULL C head next head D head NULL 4 在一个具有n个单元的顺序栈中 假设栈底是存储地址的低端 现以 top作为栈顶指针 指向栈顶元素的下一个位置 当进行出栈操作 时 假定栈非空 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 在单链表中只能通过节点的next指针向后查找节点 D 在单链表中查找第i个节点的时间复杂度为0 1 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 插入 删除操作更简单 B 可以进行随机访问 C 可以省略表头指针或表尾指针 D 前后访问相邻节点更灵活 14 循环队列SQ采用数组空间SQ base 0 n 1 存放其元素值 已知其头 尾指针分别是front和rear 则判定此循环队列为空和为满的条件分 别是 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分 共10分 得分 1 若一个算法中的语句频度之和为T n 3n n log2n 4 则算法的时 间复杂度为 2 对于n阶对称矩阵 进行压缩存储 如果以行序或列序放入一维 数组中 则需要 个存储单元 3 在非空双向循环链表中 在结点q的前面插入结点p的过程如下 p prior q prior q prior next p p next q 4 将一个下三角矩阵A 1 50 1 50 按行优先存入一维数组B 1 n 中 A中元素A 30 20 在B数组中的位置为 5 设S I am a Student T good 则ConCat T SubStr S 7 8 三 简答题 每题6分 共30分 得分 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入队 2 已知稀疏矩阵如下所以 请写出该稀疏矩阵对应的三元组表示和该 矩阵转制矩阵的三元组表示 3 设有多项式a x 9 8x 9x4 5x10 b x 2x 22x7 5x10 c x a x b x 用单链表给出a x b x 和c x 的存储表示 4 若较频繁地对一个线性表进行插入和删除操作 该线性表宜采用哪种 存储结构 为什么 5 对于堆栈 给出三个输入项A B C 如果输入项序列为ABC 试给 出全部可能的输出序列 并写出每种序列对应的操作 例如 A进B进C进C出B出A出 产生的序列为CBA 四 算法阅读题 每空2分 共 16分 1 以下为头插法建立单链表的算法 请在下划线处填上适当的语句 void CreateList L LinkList 先建立一个带头结点的单链表 for i n i 0 i p LinkList malloc sizeof LNode scanf L next p CreateList L 2 已知循环队列存储结构的定义 以下运算实现在循环队列上的入队 列和出队列 请在下划线处用适当的语句予以填充 define MAXQSIZE 100 最大队列长度 typedef struct QElemType base 初始化的动态分配存储空间 int front 头指针 若队列不空 指向队列头元素 int rear 尾指针 若队列不空 指向队列尾元素的下一个位置 SqQueue Status EnQueue SqQueue 队列满 Q base Q rear e return OK EnQueue Status DeQueue LinkQueue 队列空 e Q base Q front return OK DeQueue 3 以下为带头结点的单链表的定位运算 分析算法 请在下划线处填 上适当的语句 int LocateElem LinkList head DataType x 求表head中第一个值等于x的结点的序号 不存在这种结点时结果为 0 p head next j 1 while p NULL j if p else return 0 五 算法设计题 1小题 共14分 得分 1 已知栈的基本操作函数 int InitS