2020 数据结构(上海海事大学) 最新满分章节测试答案

本答案对应课程为:点我自动跳转查看
本课程起止时间为:2020-03-02到2020-06-30
本篇答案更新状态:已完结

第二章线性表 线性表测试

1、 问题:线性表中（ ）称为线性表的长度。
选项：
A:元素的长度
B:数据项的数目
C:数据的长度
D:元素的个数
答案: 【元素的个数】

2、 问题:在下列关于线性表的叙述中，错误的是（）
选项：
A:采用顺序存储的线性表，必须占用一片连续的存储单元
B:采用顺序存储的线性表，便于进行插入和删除操作
C:采用链式存储的线性表，不必占用一片连续的存储单元
D:采用链式存储的线性表，便于进行插入和删除操作
答案: 【采用顺序存储的线性表，便于进行插入和删除操作】

3、 问题:设顺序表的每个元素占8个存储单元。第1个单元的存储地址是100，则第6个元素占用的最后一个存储单元的地址为（ ）
选项：
A:139
B:140
C:147
D:148
答案: 【147】

4、 问题:在一个表头指针为ph的单链表中，若要在指针q所指结点的后面插入一个由指针p所指向的结点，则执行（ ）操作
选项：
A:q->next=p->next; p->next=q;
B:p->next=q->next; q=p;
C:q->next=p->next; p->next=q;
D:p->next=q->next; q->next=p;
答案: 【p->next=q->next; q->next=p;】

5、 问题:设顺序表的长度为n，并设从表中删除元素的概率相等。则在平均情况下，从表中删除一个元素需移动的元素个数是（ ）
选项：
A:(n-1)/2
B:n/2
C:n(n-1)/2
D:n(n+1)/2
答案: 【(n-1)/2】

6、 问题:在线性链表存储结构下，插入操作算法（ ）
选项：
A:需要判断是否表满
B:需要判断是否表空
C:不需要判断表满
D:需要判断是否表空和表满
答案: 【不需要判断表满】

7、 问题:若某链表最常用的操作是在最后一个结点之后插入一个元素和删除最后一个元素，则采用（ ）存储方式最节省运算时间
选项：
A:单链表
B:双向链表
C:单循环链表
D:顺序表
答案: 【顺序表】

8、 问题:设有一个二维数组A[m][n]，假设A[0][0]存放位置在644，A[2][2]存放位置在676，每个元素占一个空间，问A[3][3]的存储位置是（ ）
选项：
A:688
B:678
C:692
D:696
答案: 【692】

9、 问题:已知两个长度分别为m和n的升序链表，若将它们合并为一个长度为m+n的降序链表，则最坏情况下的时间复杂度是（ ）
选项：
A:○(n)
B:○(m*n)
C:○(min(m,n))
D:○(max(m,n))
答案: 【○(max(m,n))】

10、 问题:在一个长度为n的顺序存储结构的线性表中，向第i个元素（1≤i≤n+1）位置插入一个元素时，需要后移（ ）个元素
选项：
A:n-i
B:n-i+l
C:n-i-l
D:i
答案: 【n-i+l】

11、 问题:链表不具有的特点是（ ）
选项：
A:可随机访问任一元素
B:插入删除元素时不需移动
C:不必事先估计存储空间
D:所需空间与表长成正比
答案: 【可随机访问任一元素】

12、 问题:（ ）是线性表。
选项：
A:(1,2,3,…)
B:{a,b,c,d,e}
C:(1,3,5,7)
D:{‘A’,’B’,’C’}
答案: 【(1,3,5,7)】

13、 问题:若某链表中最常用的操作是在最后一个结点之后插入一个结点和删除最后一个结点，则采用（ ）存储方式最节省运算时间。
选项：
A:带头结点的双循环链表
B:单链表
C:单循环链表
D:双链表
答案: 【带头结点的双循环链表】

14、 问题:若线性表最常用的操作是存取第I个元素及其前驱的值，则采用（ ）存储方式节省时间
选项：
A:单链表
B:双链表
C:单循环链表
D:顺序表
答案: 【顺序表】

第三章栈和队列 栈和队列单元测试

1、 问题:一个栈的进栈序列是a，b，c，d，e，则栈的不可能的输出序列是（）
选项：
A:edcba
B:decba
C:dceab
D:abcde
答案: 【dceab】

2、 问题:若用一个大小为6的一维数组来实现循环队列，且当前rear和front的值分别为0和3。当从队列中删除一个元素，再加入两个元素后，rear和front的值分别是（）
选项：
A:1和5
B:4和2
C:5和1
D:2和4
答案: 【2和4】

3、 问题:若链队列的队头指针和队尾指针分别为front和rear，则从队列中删除一个节点的操作是（）
选项：
A:p=front;rear=p->next;free(p);
B:p=rear; front=p; free(p);
C:p=front; front=p->next;free(p);
D:p=rear; front=p->next;free(p)
答案: 【p=front; front=p->next;free(p);】

4、 问题:假设栈S和队列Q的初始状态均为空，元素a,b,c,d,e,f,g依次进入栈S。若每个元素出栈后立即进入队列Q，且7个元素的出队的顺序是b,d,c,f,e,a,g，则栈的容量至少是（ ）
选项：
A:1
B:2
C:3
D:4
答案: 【3】

5、 问题:单循环链表表示的队列长度为n，若只设头指针，则入队的时间复杂度为（ ）
选项：
A:O(n)
B:O(1)
C:O()
D:O(nlogn)
答案: 【O(n) 】

6、 问题:用链接方式存储的队列，在进行删除运算时（ ）
选项：
A:仅修改头指针
B:仅修改尾指针
C:头、尾指针都有修改
D:头尾指针都可能要修改
答案: 【头尾指针都可能要修改】

7、 问题:栈的顺序表示中，用top表示栈顶指针，那么栈空的条件是（ ）
选项：
A:top==STACKSIZE
B:top==1
C:top==0
D:top==-1
答案: 【top==-1】

8、 问题:已知一个空队列，进行如下操作序列 EnQueue(1), EnQueue(2), DeQueue(),EnQueue(3), EnQueue(4), DeQueue(),EnQueue(5)后，队头元素是（）
选项：
A:5
B:4
C:3
D:2
答案: 【3】

9、 问题:假定一个循环队列的队头和队尾指针分别为p和q，则判断队空的条件为（）
选项：
A:p==0
B:q==0
C:q+1==p
D:p==q
答案: 【p==q 】

10、 问题:若已知一个栈的进栈序列是p1,p2,p3, … ,pn 。其输出序列为1，2，3，…，n ，若p3=1，则p1为( )
选项：
A:可能是2
B:一定是2
C:不可能是2