吉大19年11月《数据结构》作业考核考试试题满分答案

吉大 19年11月《数据结构》作业考核试题 总分：100 分 一、单选题共 10 题，40 分 1 4 分 带头结点的单链表 head 为空的判断条件是()。 Ahead=NULL Bhead->next=NULL Chead->next=head Dhead!=NULL 学生答案：B 2 4 分 在 一个单链表中，已知 q 所指结点是 p 所指结点的直接前趋，若在 p,q 之间插入 s 结点，这执行（ ）操作。 As->next=p->next;p->next=s Bq->next=s;s->next=p Cp->next=s->next;s->next=p; Dp->next=s;s->next=q; 学生答案：B 3 4 分 线性表是具有 n 个（ ）的有限序列 A 表元素 B 字符 C 数据元素 D 数据项 学生答案：C 4 4 分 在单链表中，删除 p 所指结点的直接后继的操作是( ) Ap->next=p->next->next; Bp=p->next;p->next=p->next->next; Cp->next=p->next; Dp=p->next->next;

学生答案：A 5 4 分 任何一颗二叉树的叶结点在其先根、中根、后跟遍历序列中的相对位置( )。 A 肯定发生变化 B 有时发生变化 C 肯定不发生变化 D 无法确定 学生答案：C 6 4 分 在无向图中，所有顶点的度数之和是所有边数的( )倍。 A0.5 B1 C2 D4 学生答案：C 7 4 分 单链表中，增加头结点的目的是为了( )。 A 方便运算的实现 B 用于标识单链表 C 使单链表中至少有一个结点 D 用于标识起始结点的位置 学生答案：A 8 4 分 链栈与顺序栈相比，有一个比较明显得优点是( ) A 通常不会出现栈满的情况 B 通常不会出现栈空的情况 C 插入操作更加方便 D 删除操作更加方便 学生答案：A 9

4 分 深度为 6 的二叉树最多有( )个结点。 A64 B63 C32 D31 学生答案：B 10 4 分 在数据结构中，逻辑上数据结构可分为：（ ） A 动态结构和静态结构 B 线性结构和非线性结构 C 紧凑结构和非紧凑结构 D 内部结构和外部结构 学生答案：B 二、多选题共 5 题，20 分 1 4 分 类 string 中包含的串运算有（ ） AFind() BSubstr() CInsert() DLength() 学生答案：ABCD 2 4 分 二叉树的遍历方式有（） A 先根遍历 B 中根遍历 C 后根遍历 D 深度遍历 学生答案：ABC 3 4 分 图的存储结构有（） A 邻接矩阵

B 邻接表 C 数组表示法 D 十字链表 学生答案：ABCD 4 4 分 对线性表，可进行如下基本操作（ ） A 随机存取 B 插入 C 删除 D 查找 学生答案：ABCD 5 4 分 对有序表的查找方式有以下几种（） A 折半查找 B 斐波那契查找 C 插值查找 D 二叉树查找 学生答案：ABC 三、判断题共 10 题，40 分 1 4 分 设有两个串 p 和 q，求 q 在 p 中首次出现的位置的运算称作模式匹配 A 错误 B 正确 学生答案：B 2 4 分 具有 n（n>0）个顶点的无向图最多含有 n(n-1)/2 条边 A 错误 B 正确 学生答案：B 3

4 分 不是所有的 AOV 网都有一个拓朴序列 A 错误 B 正确 学生答案：B 4 4 分 在第一趟排序之后，一定能把数据表中最大或最小元素放在其最终的排序算法是冒泡排序 A 错误 B 正确 学生答案：B 5 4 分 字符串是一种线性表，其特殊性表现在它的数据元素是一个字符 A 错误 B 正确 学生答案：B 6 4 分 判断一个表达式中左右括号是否匹配，采用栈实现较为方便 A 错误 B 正确 学生答案：B 7 4 分 任何一棵二叉树中至少有一个结点的度为 2。( ) A 错误 B 正确 学生答案：A 8 4 分 算法在发生非法操作时可以作出处理的特性称为健壮性 A 错误

B 正确 学生答案：B 9 4 分 从未排序的序列中依次取出一个元素与已排序序列中的元素进行比较，然后将其放在已排序序列的合适位置上，该排序方法称为插入排序 A 错误 B 正确 学生答案：B 10 4 分 在最好和最坏情况下的时间复杂度均为 O(nlogn)且稳定的排序方法是归并排序 A 错误 B 正确 学生答案：B