数据结构与算法(大连理工大学) 中国大学MOOC答案2024版100分完整版

1 绪论 绪论单元测验

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

答案: 每个结点占用一片连续的存储区域

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

答案: 相同的逻辑结构对应的存储结构也必须相同

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

答案: 可以通过计算得到第i个节点的存储地址

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

答案: 数据元素

5、 算法指得是 。

答案: 对特定问题求解步骤的一种描述，是指令的有限序列

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

答案: 高效性

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

答案: 执行时间与n^2成正比

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

答案: O(nlgn)

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

答案: 事前分析估算的方法

2 线性表 线性表单元测验

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

答案: n

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

答案: O(n)

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

答案: 随机存取

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

答案: 删除指定的元素

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

答案: 顺序表

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

答案: 访问前后相邻结点更灵活

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

答案: L->next==NULL

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

答案: q->next=s ; s->next=p;

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

答案: 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

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

答案: dceab 

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

答案: push,push,push,pop,pop,pop