习题一(第一章到第三章)答案.pdf

1 一线性表存储在带头结点的双向循环链表中 L 为头指针 将双向循环链表 结点的数据域按值自小到大排序 成为非递减有序双向循环链表 如下算法 void unknown BNODETP L p L next q p next r q next while q L while p L 将q结点摘下 以便插入到适当位置 2 p next prior q 2 3 将q结点插入 3 p next q 4 r r next 或r q next 后移指针 再将新结点插入到适当位置 2 栈和队列的共同特点是 只允许在端点插入和删除元素 3 向一个栈顶指针为HS的链中插入一个s所指结点时 则执行 s next HS HS s 4 向一个栈顶指针为HS的链中删除一个s所指结点时 用x保存被删除结点的值 则执行 x HS data HS HS next 5 判定一个队列QU 最多元素为MaxSize 为空的条件是 QU front QU rear 6 判定一个队列QU 最多元素为MaxSize 为满队列的条件是 QU rear QU front MaxSize 7 判定一个循环队列QU 最多元素为MaxSize 为空的条件是 QU front QU rear 8 判定一个循环队列QU 最多元素为MaxSize 为满队列的条件是 QU front QU rear 1 MaxSize 9 循环队列用数组A 0 m 1 存放其元素 已知其头为指针分别是front和rear 则当前队列元素个数是 rear front m m 10 在一个链队列中 假设f和r分别指向对头和队尾指针 则插入s所指结点的 操作是 r next s r s 11 栈的静态顺序存储结构为 define MAXSTACK 500 typedef struct seqstack ElemType data MAXSTACK int top SQSTACK SQSTACK ss 这时设置栈底位置固定在数组最低段 即top 1表示栈空 栈中存放元素的 位置是事实ss data 0 ss data MAXSTACK 1 共MAXSTACK个元素 元素进 栈ss top加1 出栈减1 问 栈空的条件是 ss top 1 栈满的条件是 ss top MAXSTACK 1 栈顶元素 的表达式是 ss data ss top 栈底元素的表达式是 ss data 0 12 在一个具有n个结点的有序单链表中 插入一个新结点并仍然有序的时间复 杂度为 O n 13 给定有n个元素的向量 建立一个有序单链表的时间复杂度是 O n2 14 数据的逻辑结构只抽象反映数据元素的逻辑关系 数据的存储 物理 结 构是数据的逻辑结构在计算机存储器中的实现 15 计算机执行下面的语句时 语句s的执行次数为 n 3 n 2 2 FOR i l i i j s 16 对于给定的n 个元素 可以构造出的逻辑结构有 集合 线性结构 树形结构 图状结构 四种 17 数据结构中评价算法的两个重要指标是算法的时间复杂度和空间复杂度 18 一个算法具有5 个特性 1 有穷性 2 确定性 3 可行性 有零 个或多个输入 有一个或多个输出 19 线性表L a1 a2 an 用数组表示 假定删除表中任一元素的概率相同 则删除一个元素平均需要 移动元素的个数是 n 1 2 20 带头结点的双循环链表L中只有一个元素结点的条件是 L next next L 21 在单链表L 中 指针p 所指结点有后继结点的条件是 p next null 22 带头结点的双循环链表L 为空表的条件是 L next L q next p p q 2 3 1 L L next 暂存后继 2 q L 待逆置结点 3 L p 头指针仍 为L 24 对单链表中元素按插入方法排序的C 语言描述算法如下 其中L 为链表头 结点指针 请填充算法中标 出的空白处 完成其功能 typedef struct node int data struct node next linknode link void Insertsort link L link p q r u p L next 1 while 2 r L q L next while 3 q q next u p next 4 5 p u 1 L next null 置空链表 然后将原链表结点逐个插入到有序表中 2 p null 当链表尚未到尾 p为工作指针 3 q null 查p结点在链表中的插入位置 这时q是工作指针 4 p next r next 将p结点链入链表中 5 r next p r是q的前驱 u是下个待插入结点的指针 选择题 1 设一个链表最常用的操作是在末尾插入结点和删除尾结点 则选用 D 最节省时间 A 单链表 B 单循环链表 C 带尾指针的单循环链表 D 带头结点的双循环链 表 2 若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和 删除运算 则利用 A 存储方式最节省时间 A 顺序表 B 双链表 C 带头结点的双循环链表 D 单循环链表 3 某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个 元素 则采用 D 存 储方式最节省运算时间 A 单链表 B 仅有头指针的单循环链表 C 双链表 D 仅有尾指针的单循环链 表 4 线性表 a1 a2 an 以链接方式存储时 访问第i 位置元素的时间复杂性 为 C A O i B O 1 C O n D O i 1 5 对于顺序存储的线性表 访问结点和增加 删除结点的时间复杂度为 C A O n O n B O n O 1 C O 1 O n D O 1 O 1 6 在双向链表指针p 的结点前插入一个指针q 的结点操作是 C A p Llink q q Rlink p p Llink Rlink q q Llink q B p Llink q p Llink Rlink q q Rlink p q Llink p Llink C q Rlink p q Llink p Llink p Llink Rlink q p Llink q D q Llink p Llink q Rlink q p Llink q p Llink q 7 对于一个头指针为head 的带头结点的单链表 判定该表为空表的条件是 B A head NULL B head next NULL C head next head D head NULL 8 下列数据中 A 是非线性数据结构 A 树 B 字符串 C 队 D 栈 9 一个栈的输入序列为123 n 若输出序列的第一个元素是n 输出第i 1 i n 个元素是 B A 不确定 B n i 1 C i D n i 10 有六个元素6 5 4 3 2 1 的顺序进栈 问下列哪一个不是合法的出栈 序列 C A 5 4 3 6 1 2 B 4 5 3 1 2 6 C 3 4 6 5 2 1 D 2 3 4 1 5 6 11 若栈采用顺序存储方式存储 现两栈共享空间V 1 m top i 代表第i 个 栈 i 1 2 栈顶 栈1 的 底在v 1 栈2 的底在V m 则栈满的条件是 B A top 2 top 1 0 B top 1 1 top 2 C top 1 top 2 m D top 1 top 2 12 用链接方式存储的队列 在进行删除运算时 D A 仅修改头指针 B 仅修改尾指针 C 头 尾指针都要修改 D 头 尾指针可 能都要修改 13 循环队列A 0 m 1 存放其元素值 用front 和rear 分别表示队头和队尾 则当前队列中的元素数是 A A rear front m m B rear front 1 C rear front 1 D rear front 14 若用一个大小为6 的数组来实现循环队列 且当前rear 和front 的值分别 为0 和3 当从队列中删除 一个元素 再加入两个元素后 rear 和front 的值分别为多少 B A 1 和 5 B 2 和4 C 4 和2 D 5 和1 15 设栈S 和队列Q 的初始状态为空 元素e1 e2 e3 e4 e5 和e6 依次通过 栈S 一个元素出栈后即进 队列Q 若6 个元素出队的序列是e2 e4 e3 e6 e5 e1 则栈S 的容量至少应该 是 C A 6 B 4 C 3 D 2 编写一递归函数 实现求m和n的最大公约数 include usi