网课《数据结构与算法》章节测试答案
第一章
1、在数据结构中，从逻辑上可以把数据结构分成（ ）。
A:紧凑结构和非紧凑结构
B:线性结构和非线性结构
C:内部结构和外部结构
D:动态结构和静态结构
正确答案：线性结构和非线性结构
2、在数据结构中，从存储结构上可以将之分为（ ）。
A:动态结构和静态结构
B:顺序存储和非顺序存储
C:紧凑结构和非紧凑结构
D:线性结构和非线性结构
正确答案：顺序存储和非顺序存储
3、某算法的时间复杂度是O(n^2)，表明该算法的（ ）。
A:执行时间与n^2成正比
B:问题规模是n^2
C:执行时间等于n^2
D:问题规模与n^2成正比
正确答案：执行时间与n^2成正比
4、在下面的程序段中，x=x+1;的语句频度为（ ）。for( i=1;i<=n;i++) for( j=1;j<=n;j++) x=x+1;
A:O(2n)
B:O(n)
C:O(n^2)
D:O(log2n)
正确答案：O(n^2)
5、以下数据结构中，（ ）是非线性数据结构。
A:树
B:字符串
C:队
D:栈
正确答案：树
6、顺序存储，存储单元的地址（ ）。
A:一定连续
B:一定不连续
C:不一定连续
D:部分连续，部分不连续
正确答案：一定连续
7、评价一个算法性能好坏的重要标准是( )。
A:算法的正确性
B:算法易于调试
C:算法的时间和空间复杂度
D:算法易于理解
正确答案：算法的时间和空间复杂度
8、若需要利用形式参数直接访问修改实参值，则应将形参说明为（ ）参数。
A:值参数
B:实地址
C:指针
D:地址参数
正确答案：指针
9、顺序存储方式的优点是存储密度大，且插入、删除运算效率高。
A:对
B:错
正确答案：错
10、数据结构中评价算法的两个重要指标是算法的时间复杂度和空间复杂度。
A:对
B:错
正确答案：对
第二章
1、下述哪一条是顺序存储结构的优点（）。
A:可方便地用于各种逻辑结构的存储表示
B:插入运算方便
C:删除运算方便
D:存储密度大
正确答案：存储密度大
3、设某顺序表中第一个元素的地址是se（下标从1开始），每个结点占m个单元，则第i个结点的地址为（）。
A:se+(i-1)×m
B:se+(i+1)×m
C:se+i×m
D:se-i×m
正确答案：se+(i-1)×m
4、某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（）存储方式最节省运算时间。
A:单链表
B:仅有尾指针的单循环链表
C:仅有头指针的单循环链表
D:双链表
正确答案：仅有尾指针的单循环链表
5、若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为（）。
A:O(n)
B:O(0)
C:O(1)
D:O(n^2)
正确答案：O(n)
6、在单链表指针为p的结点之后插入指针为s的结点，正确的操作是（）。
A:s->next=p->next;p->next=s;
B:p->next=s;s->next=p->next;
C:p->next=s;p->next=s->next;
D:p->next=s->next;p->next=s;
正确答案：s->next=p->next;p->next=s;
7、 对于一个头指针为head的带头结点的单链表，判定该表为空表的条件是（）。
A:head→next==NULL;
B:head==NULL;
C:head→next==he;
D:head!=NULL;
正确答案：head→next==NULL;
8、 静态链表与动态链表在元素的插入、删除上类似，不需做元素的移动。
A:对
B:错
正确答案：对
9、 顺序表适宜于顺序存取，而链表适宜于随机存取。
A:对
B:错
正确答案：错
10、线性表的链式存储结构中，逻辑上相邻的两个元素在物理位置上并不一定相邻。
A:对
B:错
正确答案：对
第三章
1、栈和队列都是（ ）。
A:限制存取点的非线性结构
B:顺序存储的线性结构
C:链式存储的非线性结构
D:限制存取点的线性结构
正确答案：限制存取点的非线性结构
2、设栈S和队列Q的初始状态为空，元素e1，e2，e3，e4，e5和e6依次通过栈S，一个元素出栈后随即进入队列Q，若6个元素出队的序列是e2，e4，e3，e6，e5，e1，则栈S的容量至少应该是（ ）。
A:3
B:6
C:4
D:2
正确答案：A
3、设计一个判别表达式中括号是否匹配出现的算法，采用（ ）的数据结构最佳。
A:栈
B:顺序表
C:队列
D:单链表
正确答案：A
4、表达式a*(b+c)-d的后缀表达式是( )。
A:abc+d-
B:cb+ad-
C:abc+*d-
D:abcd+-
正确答案：abc+*d-
5、递归过程或函数调用时，处理参数及返回地址需要用一种（ ）的数据结构。
A:栈
B:队列
C:多维数组
D:线性表
正确答案：A
6、最大容量为n的循环队列，队尾指针为rear，队头指针为front，则队空的条件是（ ）。
A:rear==front
B:(rear+1)%n==front
C:rear+1==front
D:(rear-l)%n==front
正确答案：rear==front
7、用带头结点的单链表表示队长大于1的队列时，其队头指针指向队头结点，其队尾指针指向队尾结点，则在进行删除操作时（ ）。
A:仅修改队头指针
B:仅修改队尾指针
C:队头、队尾指针都要修改
D:队头,队尾指针都可能要修改
正确答案：仅修改队头指针
8、对于一个具有n个结点的单链表，在已知的结点p后插入一个新结点的时间复杂度和在给定值为x的结点后插入一个新结点的时间复杂度分别为（ ）。
A:O(1),O(n)
B:O(n),O(n)
C:O(1),O(1)
D:O(n),O(1)
正确答案：A
9、两顺序栈共享空间，也存在空间溢出问题。
A:对
B:错
正确答案：A
10、在对不带头结点的链队列作出队操作时，不会改变头指针的值。
A:对
B:错
正确答案：B
第四章
1、串是一种特殊的线性表，其特殊性体现在（ ）。
A:数据元素是单个字符
B:顺序存储
C:链式存储
D:逻辑结构是线性结构
正确答案：数据元素是单个字符
2、若串S= ‘software’，其前缀真子串的数目是( )。
A:7
B:10
C:9
D:8
正确答案：A
3、设有两个串p和q ，其中q是p的子串，求q在p中首次出现的位置的算法称为( )。
A:串的模式匹配
B:求子串
C:串联接
D:求串长
正确答案：A
4、已知串 S=‘aaab’，其next函数值为（ ）。
A:0123
B:1123
C:1231
D:1211
正确答案：A
5、函数strcmp(‘stcabuc’,’stbabuc’)的返回值是（ ）。
A:0
B:-1
C:2
D:1
正确答案：D
6、KMP算法的特点是在模式匹配时指示主串的指针不会回溯。
A:对
B:错
正确答案：A
7、模式串 P=‘abaabcac’的next函数值序列为01122312。
A:对
B:错
正确答案：A
8、串的存储结构有顺序串、堆串和块链串三种。
A:对
B:错
正确答案：A
9、子串的定位运算称为串的模式匹配。
A:对
B:错
正确答案：A
10、串’student’和’Student’相等。
A:对
B:错
正确答案：B
第五章
1、假设以行序为主序存储二维数组A=array[1…100，1…100]，设每个数组元素占2个存储单元，基地址为10，则LOC[5，5]=( )。
A:818
B:808
C:1010
D:1020
正确答案：A
2、若对n阶对称矩阵A以行序为主序方式将其下三角形的元素(包括主对角线上所有元素)依次存放于一维数组B［1…(n(n+1))/2］中，则在B中确定aij（i<j）的位置k的计算公式为（ ）。
A:j(j-1)/2+i
B: j*(j-1)/2+i
C: i(i+1)/2+j
D: j(j+1)/2+i
正确答案：j*(j-1)/2+i
3、设广义表L=（（a,b,c）），则L的长度和深度分别为（ ）。
A:1和2
B:1和1
C:1和3
D:2和3
正确答案：A
4、在稀疏矩阵的三元组顺序表中，每个三元组表示（ ）。
A:矩阵中数据元素的行号、列号和数据值
B: 矩阵中非零元素的数据值
C: 矩阵中数据元素的行号和列号
D: 矩阵中非零元素的行号、列号和数据值
正确答案：B
5、 多维数组可以看作是一种特殊的线性表。
A:对
由于篇幅有限，完整版可移步公号免费下载，见个人简介。
