数据结构与算法(山东工商学院) 中国大学慕课答案2024完整版100分

坟聪愤拌江经寿皖兢际叛极番

对应课程:点击查看
起止时间:2020-02-24到2020-06-20
更新状态:已完结

1 绪论 绪论单元测验

1、 在链接存储结构中，要求 。

A:每个结点占用一片连续的存储区域
B:所有结点占用一片连续的存储区域
C:结点的最后一个域是指针类型
D:每个结点有多少个后继就设多少个指针
答案: 每个结点占用一片连续的存储区域

2、 对于数据结构的描述，下列说法中不正确的是 。

A:相同的逻辑结构对应的存储结构也必须相同
B:数据结构由逻辑结构、存储结构和基本操作三个方面构成
C:数据结构基本操作的实现与存储结构有关
D:数据的存储结构是数据的逻辑结构的机内实现
答案: 相同的逻辑结构对应的存储结构也必须相同

3、 以下关于链接存储结构的叙述中， 是不正确的。

A:结点除数据信息外还包括指针域，因此存储密度小于顺序存储结构
B:逻辑上相邻的结点在物理上不一定相邻
C:可以通过计算得到第i个节点的存储地址
D:插入和删除操作方便，不必移动结点
答案: 可以通过计算得到第i个节点的存储地址

4、 可以用 、数据关系和基本操作定义一个完整的抽象数据类型。

A:数据元素
B:数据对象
C:原子类型
D:存储结构
答案: 数据元素

5、 算法指得是 。

A:对特定问题求解步骤的一种描述，是指令的有限序列
B:计算机程序
C:解决问题的计算方法
D:数据处理
答案: 对特定问题求解步骤的一种描述，是指令的有限序列

6、 下面 不是算法所必须具备的特性。

A:有穷性
B:确切性
C:高效性
D:可行性
答案: 高效性

7、 某算法的时间复杂度是O(n^2)，表明该算法 。

A:问题规模是n^2
B:执行时间等于n^2
C:执行时间与n^2成正比
D:问题规模与n^2成正比
答案: 执行时间与n^2成正比

8、 设某算法完成对n个元素进行处理，所需的时间是T(n)=100nlgn+200n+500，则该算法的时间复杂度是 。

A:O(1)
B:O(n)
C:O(nlgn)
D:O(nlgn)+O(n)
答案: O(nlgn)

9、 算法的时间复杂度属于一种 。

A:事前统计的方法
B:事前分析估算的方法
C:事后统计的方法
D:事后分析估算的方法
答案: 事前分析估算的方法

2 线性表 线性表单元测验

1、 将两个各有n个元素的有序顺序表归并成一个有序顺序表，其最少的比较次数是 。

A:n
B:2n-1
C:2n
D:n-1
答案: n

2、 在长度为n的线性表中查找值为x的数据元素的时间复杂度为 。

A:O(0)
B:O(1)
C:O(n)
D:O(n^2)
答案: O(n)

3、 线性表的顺序存储结构是一种 的存储结构。

A:随机存取
B:顺序存取
C:索引存取
D:散列存取
答案: 随机存取

4、 设线性表中有2n个元素，以下操作中， 在单链表上实现要比在顺序表上实现效率更高。

A:删除指定的元素
B:在最后一个元素的后面插入一个新元素
C:顺序输出前k个元素
D:交换第i个元素和第2n-i-1个元素的值（i=0,1,…,n-1）
答案: 删除指定的元素

5、 如果最常用的操作是取第i个节点及其前驱，则采用 存储方式最节省时间。

A:单链表
B:双链表
C:单循环链表
D:顺序表
答案: 顺序表

6、 与单链表相比，双链表的优点之一是 。

A:插入、删除操作更简单
B:可以进行随机访问
C:可以省略表头指针或表尾指针
D:访问前后相邻结点更灵活
答案: 访问前后相邻结点更灵活

7、 带头结点的单链表L为空的判定条件是 。

A:L==NULL
B:L->next==NULL
C:L->next==L
D:L!=NULL
答案: L->next==NULL

8、 在一个单链表中，已知q所指结点是p所指结点的直接前驱，若在q和p之间插入s所指结点，则执行 操作。

A:s->next=p->next ; p->next=s;
B:q->next=s ; s->next=p;
C:p->next=s->next ; s->next=p;
D:p->next=s ; s->next=q;
答案: q->next=s ; s->next=p;

9、 设指针rear指向带头结点的循环单链表的尾结点，若要删除链表的第一个元素结点，正确的操作是 。

A:s=rear ; rear=rear->next;
B:rear=rear->next;
C:rear=rear->next->next;
D:s=rear->next->next ; rear->next->next=s->next;
答案: s=rear->next->next ; rear->next->next=s->next;

10、 经过以下栈运算后，x的值是 。InitStack(s);Push(s,a);Push(s,b);Pop(s,x);GetTop(s.x);

A:a
B:b
C:0
D:1
答案: a

11、 一个栈的进栈a,b,c,d,e则栈的不可能的输出序列是 。

A:edcba
B:decba
C:dceab
D:abcde
答案: dceab

12、 已知一个栈的进栈序列是ABC，出栈序列是CBA，经过的栈操作是 。

A:push,pop,push,pop,push,pop
B:push,push,push,pop,pop,pop
C:push,push,pop,pop,push,pop
D:push,pop,push,push,pop,pop
答案: push,push,push,pop,pop,pop

13、 判定一个顺序栈st为（元素个数最多为MaxSize）空的条件为 。

A:st.top==-1
B:st.top!=-1
C:st.top!=MaxSize
D:st.top==MaxSize
答案: st.top==-1

14、 链栈与顺序栈相比有一个明显的优点，即 。

A:插入操作更方便
B:通常不会出现栈满的情况