大学MOOC 2016秋数据结构（汉口学院）(中国高校计算机教育大学MOOC联盟)1001756016 最新慕课完整章节测试答案
第一讲基本概念11526[陈越]
文章目录
小测验算法复杂度
1、单选题：
下列函数中，哪个函数具有最快的增长速度：
选项：
A: 
B: 
C: 
D: 
答案: 【 】
2、单选题：
下面一段代码的时间复杂度是？if ( A > B ) {
for ( i=0; i<N; i++ )
for ( j=N*N; j>i; j-- )
A += B;
}
else {
for ( i=0; i<N*2; i++ )
for ( j=N*2; j>i; j-- )
A += B;
}
选项：
A: 
B: 
C: 
D: 
答案: 【 】
线性表顺序表、链表等
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;】
第二讲线性结构21900[何钦铭]
小测验堆栈
1、单选题：
借助堆栈将中缀表达式A-(B-C/D)*E转换为后缀表达式，则该堆栈的大小至少为：
选项：
A: 2
B: 3
C: 4
D: 5
答案: 【 4】
2、单选题：
设1、2、…、n–1、n共n个数按顺序入栈，若第一个出栈的元素是n，则第三个出栈的元素是：
选项：
A: 3
B: n-2
C: n-3
D: 任何元素均可能
答案: 【 n-2】
3、单选题：
若用单向链表实现一个堆栈，当前链表状态为：1->2->3。当对该堆栈执行pop()、push(4)操作后，链表状态变成怎样？ （1）4->2->3 (2) 1->2->4
选项：
A: 只能是（1）
B: 只能是（2）
C: （1）和（2）都有可能
D: （1）和（2）都不可能
答案: 【 只能是（1）】
4、单选题：
如果一堆栈的输入序列是aAbBc，输出为 abcBA，那么该堆栈所进行的操作序列是什么？ 设P代表入栈，O代表出栈。
选项：
A: PPPOOPOPOO
B: POOPPPOPOO
C: POPPOPPOOO
D: PPOPPOOOPO
答案: 【 POPPOPPOOO】
小测验线性表
1、单选题：
对于线性表，在顺序存储结构和链式存储结构中查找第k个元素，其时间复杂性分别是多少？
选项：
A: 都是O(1)
B: 都是O(k)
C: O(1)和O(k)
D: O(k)和O(1)
答案: 【 O(1)和O(k)】
2、单选题：
在顺序结构表示的线性表中，删除第i个元素（数组下标为i-1)，需要把后面的所有元素都往前挪一位，相应的语句是：for (___________ ) PtrL->Data[j-1]=PtrL->Data[j]; 其中空缺部分的内容应该是
选项：
A: j = i; j< = PtrL->Last; j++
B: j =PtrL->Last; j>= i; j--
C: j = i-1; j< = PtrL->Last; j++
D: j =PtrL->Last; j>= i-1; j--
答案: 【 j = i; j< = PtrL->Last; j++】
3、判断题：
下列函数试图求链式存储的线性表的表长，是否正确？int Length ( List *PtrL ){ List *p = PtrL; int j = 0; while ( p ) { p++; j++; } return j;}
选项：
A: 正确
B: 错误
答案: 【 错误】
小测验队列
1、单选题：
在一个链表表示的队列中， f和r分别指向队列的头和尾。下列哪个操作能正确地将s结点插入到队列中：
选项：
A: f->next=s; f=s;
B: r->next=s; r=s;
C: s->next=r; r=s;
D: s->next=f; f=s;
答案: 【 r->next=s; r=s;】
2、单选题：
现采用大小为10的数组实现一个循环队列。设在某一时刻，队列为空且此时front和rear值均为5。经过若干操作后，front为8，rear为2，问：此时队列中有多少个元素？
选项：
A: 4
B: 5
C: 6
D: 7
答案: 【 4】
栈和队列顺序栈、链栈、循环队列、链队
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的容量至少应该是（ ）。
选项：
A: 2
B: 3
C: 4
D: 6
答案: 【 3】
9、单选题：
若一个栈以向量V[1..n]存储，初始栈顶指针top设为n+1，则元素x进栈的正确操作是( )。
选项：
A: top++; V[top]=x;
B: V[top]=x; top++;
C: top--; V[top]=x;
D: V[top]=x; top--;
答案: 【 top--; V[top]=x;】
10、单选题：
设计一个判别表达式中左，右括号是否配对出现的算法，采用（ ）数据结构最佳。
选项：
A: 线性表的顺序存储结构
B: 队列
C: 线性表的链式存储结构
D: 栈
答案: 【 栈】
11、单选题：
用链接方式存储的队列，在进行删除运算时（ ）。
选项：
A: 仅修改头指针
B: 仅修改尾指针
C: 头、尾指针都要修改
D: 头、尾指针可能都要修改
答案: 【 头、尾指针可能都要修改】
12、单选题：
循环队列存储在数组A[0..m]中，则入队时的操作为（ ）。
选项：
A: rear=rear+1
B: rear=(rear+1)%(m-1)
C: rear=(rear+1)%(m-1)
D: rear=(rear+1)%(m+1)
答案: 【 rear=(rear+1)%(m+1)】
13、单选题：
最大容量为n的循环队列，队尾指针是rear，队头是front，则队空的条件是（ ）。
选项：
A: (rear+1)%n==front
B: rear==front
C: rear+1==front
D: (rear-l)%n==front
答案: 【 rear==front】
14、单选题：
栈和队列的共同点是（ ）。
选项：
A: 都是先进先出
B: 都是先进后出
C: 只允许在端点处插入和删除元素
D: 没有共同点
答案: 【 只允许在端点处插入和删除元素