2016秋数据结构（汉口学院）(中国高校计算机教育MOOC联盟) 中国大学慕课答案2024完整版100分

对应课程:点击查看
起止时间:2016-09-19到2016-12-31
更新状态:已完结

第一讲 基本概念（1：15：26）[陈越] 线性表（顺序表、链表等）

1、 顺序表中第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是（ ）。

A:110
B:108
C:100
D:120
E:106
答案: 108

2、 在n个结点的顺序表中，算法的时间复杂度是O(1)的操作是（ ）。

A:访问第i个结点（1≤i≤n）和求第i个结点的直接前驱（2≤i≤n）
B:在第i个结点后插入一个新结点（1≤i≤n）
C:删除第i个结点（1≤i≤n）
D:将n个结点从小到大排序
答案: 访问第i个结点（1≤i≤n）和求第i个结点的直接前驱（2≤i≤n）

3、 向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动 的元素个数为（ ）。

A:8
B:63
C:63.5
D:7
E:127
答案: 63.5

4、 链接存储的存储结构所占存储空间（ ）。

A:分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针
B:只有一部分，存放结点值
C:只有一部分，存储表示结点间关系的指针
D:分两部分，一部分存放结点值，另一部分存放结点所占单元数
答案: 分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针

5、 线性表若采用链式存储结构时，要求内存中可用存储单元的地址（ ）。

A:必须是连续的
B:部分地址必须是连续的
C:一定是不连续的
D:连续或不连续都可以
答案: 连续或不连续都可以

6、 线性表Ｌ在（ ）情况下适用于使用链式结构实现。

A:需经常修改Ｌ中的结点值
B:需不断对Ｌ进行删除插入
C:Ｌ中含有大量的结点
D:Ｌ中结点结构复杂
答案: 需不断对Ｌ进行删除插入

7、 单链表的存储密度（ ）。注：存储密度是指一个结点数据本身所占的存储空间和整个结点所占的存储空间之比

A:大于1
B:等于1
C:小于1
D:不能确定
答案: 小于1

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

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

9、 在一个长度为n的顺序表中，在第i个元素（1≤i≤n+1）之前插入一个新元素时须向后移动（ ）个元素。

A:n-i
B:n-i+1
C:n-i-1
D:I
答案: n-i+1

10、 线性表L=(a1，a2,……an)，下列说法正确的是（ ）。

A:每个元素都有一个直接前驱和一个直接后继
B:线性表中至少有一个元素
C:表中诸元素的排列必须是由小到大或由大到小
D:除第一个和最后一个元素外，其余每个元素都有一个且仅有一个直接前驱和直接后继。
答案: 除第一个和最后一个元素外，其余每个元素都有一个且仅有一个直接前驱和直接后继。

11、 创建一个包括n个结点的有序单链表的时间复杂度是（ ）。

A:O(1)
B:O(n)
C:O(n2)
D:O(nlog2n)
答案: O(n2)

12、 以下说法错误的是（ ）。

A:求表长、定位这两种运算在采用顺序存储结构时实现的效率不比采用链式存储结构时实现的效率低
B:顺序存储的线性表可以随机存取
C:由于顺序存储要求连续的存储区域，所以在存储管理上不够灵活
D:线性表的链式存储结构优于顺序存储结构
答案: 线性表的链式存储结构优于顺序存储结构

13、 在单链表中，要将s所指结点插入到p所指结点之后，其语句应为（ ）。

A:s->next=p+1; p->next=s;
B:(p).next=s; (s).next=(*p).next;
C:s->next=p->next; p->next=s->next;
D:s->next=p->next; p->next=s;
答案: s->next=p->next; p->next=s;

14、 在双向链表存储结构中，删除p所指的结点时须修改指针（ ）。

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

15、 在双向循环链表中，在p指针所指的结点后插入q所指向的新结点，其修改指针的操作是（ ）。

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

第二讲 线性结构（2：19：00）[何钦铭] 栈和队列（顺序栈、链栈、循环队列、链队）

1、 若让元素1，2，3，4，5依次进栈，则出栈次序不可能出现在（ ）种情况。

A:5，4，3，2，1
B:2，1，5，4，3
C:4，3，1，2，5
D:2，3，5，4，1
答案: 4，3，1，2，5

2、 若已知一个栈的入栈序列是1，2，3，…，n，其输出序列为p1，p2，p3，…，pn，若p1=n，则pi为（ ）。

A:i
B:n-i
C:n-i+1
D:不确定
答案: n-i+1

3、 数组Ｑ［ｎ］用来表示一个循环队列，ｆ为当前队列头元素的前一位置，ｒ为队尾元素的位置，假定队列中元素的个数小于ｎ，计算队列中元素个数的公式为（ ）。

A:r-f
B:(n+f-r)%n
C:n+r-f
D:（n+r-f)%n
答案: （n+r-f)%n

4、 链式栈结点为：(data,link)，top指向栈顶.若想摘除栈顶结点，并将删除结点的值保存到x中,则应执行操作（ ）。

A:x=top->data;top=top->link；
B:top=top->link;x=top->link；
C:x=top;top=top->link；
D:x=top->link；
答案: x=top->data;top=top->link；

5、 设有一个递归算法如下 int fact(int n) { //n大于等于0 if(n<=0) return 1; else return n*fact(n-1); }则计算fact(n)需要调用该函数的次数为（ ）。

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

6、 栈在 （ ）中有所应用。

A:递归调用
B:函数调用
C:表达式求值
D:前三个选项都有
答案: 前三个选项都有

7、 为解决计算机主机与打印机间速度不匹配问题，通常设一个打印数据缓冲区。主机将要输出的数据依次写入该缓冲区，而打印机则依次从该缓冲区中取出数据。该缓冲区的逻辑结构应该是（ ）。

A:队列
B:栈
C:线性表
D:有序表
答案: 队列

8、 设栈S和队列Q的初始状态为空，元素e1、e2、e3、e4、e5和e6依次进入栈S，一个元素出栈后即进入Q，若6个元素出队的序列是e2、e4、e3、e6、e5和e1，则栈S的容量至少应该是（　）。