大学MOOC 数据结构与算法(广州中医药大学)1458261171 最新慕课完整章节测试答案
1 绪论
什么是数据结构-随堂测验
1、单选题：
数据结构研究的对象不包括()
选项：
A: 数据的各种逻辑结构
B: 数据在计算机中的存储结构
C: 各种操作的算法
D: 数据在计算机中的大小关系
答案: 【 数据在计算机中的大小关系】
2、判断题：
数据结构主要研究非数值计算的问题()
选项：
A: 正确
B: 错误
答案: 【 正确】
3、判断题：
数据结构是计算机及相关学科的一门核心课程()
选项：
A: 正确
B: 错误
答案: 【 正确】
什么是算法-随堂测验
1、单选题：
计算机的算法是指
选项：
A: 计算方法
B: 排序方法
C: 解决问题的操作步骤的集合
D: 调度方法
答案: 【 解决问题的操作步骤的集合】
2、单选题：
计算机算法必须具备输入、输出和（ ）等5个特性。
选项：
A: 可行性、可移植性和可扩充性
B: 可行性、确定性和有穷性
C: 确定性、有穷性和稳定性
D: 易读性、稳定性和安全性
答案: 【 可行性、确定性和有穷性】
3、单选题：
算法包含的所有运算必做是充分基本的，可以通过已经实现的基本运算执行有限次来实现，指的是算法的()特性
选项：
A: 可行性
B: 确定性
C: 有穷性
D: 输出
答案: 【 可行性】
4、单选题：
算法的设计目标不包括
选项：
A: 正确
B: 健壮
C: 可读
D: 易实现
答案: 【 易实现】
5、多选题：
算法可以用( )来描述
选项：
A: 文字
B: 流程图
C: 程序语言
D: 伪代码
答案: 【 文字;
流程图;
程序语言;
伪代码】
数据结构基本概念-随堂测验
1、单选题：
数据结构中，与所使用的计算机无关的是数据的（ ）结构。
选项：
A: 存储
B: 物理
C: 逻辑
D: 物理和存储
答案: 【 逻辑】
2、单选题：
在数据结构中，从逻辑上可以把数据结构分成（ ）
选项：
A: 动态结构和静态结构
B: 紧凑结构和非紧凑结构
C: 线性结构和非线性结构
D: 内部结构和外部结构
答案: 【 线性结构和非线性结构】
3、单选题：
线性结构是数据元素之间存在一种（ ）
选项：
A: 一对多关系
B: 多对多关系
C: 多对一关系
D: 一对一关系
答案: 【 一对一关系】
4、判断题：
数据在计算机中的表示和存储属于逻辑结构
选项：
A: 正确
B: 错误
答案: 【 错误】
5、判断题：
顺序存储结构的特点的逻辑上相邻的数据元素物理上也相邻
选项：
A: 正确
B: 错误
答案: 【 正确】
算法分析与度量-随堂测验
1、单选题：
以下时间复杂度数量级别最高的是（ ）。
选项：
A: O(log2n)
B: O(nlog2n)
C: O(n3)
D: O(n)
答案: 【 O(n3)】
2、单选题：
给出算法的时间复杂度是属于一种（ ）
选项：
A: 事前统计的方法
B: 事前分析估算的方法
C: 事后统计的方法
D: 事后分析估算的方法
答案: 【 事前分析估算的方法】
3、单选题：
以下程序段的时间复杂度是( )void Add(int n){ int sum =0; for(int i=0;i<n;i++) { sum +=i; }}
选项：
A: O(1)
B: O(n)
C: O(nlog2n)
D: O(n1.3)
答案: 【 O(n)】
4、多选题：
算法实际运行的时间受到( )的影响
选项：
A: 程序设计语言
B: 机器代码质量
C: 机器执行指令的速度
D: 问题的规模
答案: 【 程序设计语言;
机器代码质量;
机器执行指令的速度;
问题的规模】
5、判断题：
采用事前分析估算来评价算法，不需要运行程序
选项：
A: 正确
B: 错误
答案: 【 正确】
绪论单元测验
1、单选题：
以下不属于数据的逻辑结构的是( )
选项：
A: 顺序存储
B: 树
C: 图
D: 集合
答案: 【 顺序存储】
2、单选题：
以下数据结构中,( )是非线性数据结构
选项：
A: 树
B: 字符串
C: 队列
D: 栈
答案: 【 树】
3、单选题：
从逻辑上可以把数据结构分为( )两大类
选项：
A: 动态结构，静态结构
B: 顺序结构，链式结构
C: 线性结构，非线性结构
D: 初等结构，构造型结构
答案: 【 线性结构，非线性结构】
4、单选题：
算法的时间复杂度主要取决于( )
选项：
A: 问题的规模
B: 待处理数据的初态
C: 描述的准确性
D: 程序设计语言
答案: 【 问题的规模】
5、单选题：
计算机的算法是指( )
选项：
A: 计算方法
B: 排序方法
C: 解决问题的步骤序列
D: 调度方法
答案: 【 解决问题的步骤序列】
6、单选题：
计算机的算法必须具备( )这三个特性
选项：
A: 可执行性、可移植性、可扩充性
B: 可执行性、确定性、有穷性
C: 确定性、有穷性、稳定性
D: 易读性、稳定性、安全性
答案: 【 可执行性、确定性、有穷性】
7、单选题：
以下时间复杂度数量级别最高的是（ ）
选项：
A: O(1)
B: O(log2n)
C: O(n3)
D: O(n)
答案: 【 O(n3)】
8、单选题：
要求同一逻辑结构的所有数据元素具有相同的特性，这意味着（ ）。
选项：
A: 数据元素具有同一的特点
B: 不仅数据元素包含的数据项的个数要相同，而且对应数据项的类型要一致
C: 每个数据元素都一样
D: 数据元素所包含的数据项的个数要相等
答案: 【 不仅数据元素包含的数据项的个数要相同，而且对应数据项的类型要一致】
9、单选题：
线性表若采用链式存储结构时，要求内存中可用存储单元的地址( )。
选项：
A: 必须连续的
B: 部分地址必须连续的
C: 一定是不续的
D: 连续不连续都可以
答案: 【 连续不连续都可以】
10、单选题：
树形结构中元素之间存在( )关系
选项：
A: 一对多关系
B: 多对多关系
C: 多对一关系
D: 一对一关系
答案: 【 一对多关系】
11、单选题：
图形结构中元素之间存在( )关系
选项：
A: 一对多关系
B: 多对多关系
C: 多对一关系
D: 一对一关系
答案: 【 多对多关系】
12、单选题：
以下程序的时间复杂度为int i,j,xFor(i=0;i<n-1;i++) For(j=1;j<n;j++) X++;
选项：
A: O(1)
B: O(n)
C: O(log2n)
D: O(n2)
答案: 【 O(n2)】
13、单选题：
有实现同一功能的四个算法F1、F2、F3、F4，它们的时间复杂度分别是O(nlog2n),O(n2),O(2的n次方),O(n!)，仅从时间复杂度的角度来看，较好的算法时( )
选项：
A: F1
B: F2
C: F3
D: F4
答案: 【 F1】
14、单选题：
某算法的时间复杂度为O(n2)。若该算法在规模为n的数据集上，运行时间为10秒；如果数据规模扩大为2n，该算法大约需要运行（ ）
选项：
A: 6-7分钟
B: 100秒
C: 10秒
D: 以上都不对
答案: 【 以上都不对】
15、单选题：
以下函数中时间复杂度最小的是（ ）
选项：
A: T(n)=2n
B: T(n)=n-10log2n
C: n2log2n
D: 10logn2n
答案: 【 10logn2n】
16、单选题：
以下程序段的时间复杂度是( )count=0;for (k=1;k<=n;k*=2) for (j=1;j<=n;j+1) count++;
选项：
A: O(1)
B: O(n)
C: O(log2n)
D: O(n2)
答案: 【 O(log2n)】
17、单选题：
下面的数据结构是（ ）DS=(D,R)，其中D={a,b,c,d,e}，R={r}，r={<a,b>,<a,e>,<b,c>,<d,e>}。注：“<>"表示有序对。
选项：
A: 图
B: 集合
C: 树
D: 顺序存储结构
答案: 【 图】
18、单选题：
下面的数据结构是（ ）,S=(D, R),其中D={ a, b, c, d, e, f }R={<a,e>, <b,c>, <c,a>, <e,f>, <f,d>}.注：“<>"表示有序对。
选项：
A: 图
B: 集合
C: 树
D: 线性
答案: 【 线性】
19、单选题：
下面的数据结构是（ ）,S=(D, R),其中D={di | 1≤i≤5},R={<di , dj >, i<j}.注：“<>"表示有序对。
选项：
A: 图
B: 集合
C: 树
D: 线性
答案: 【 图】
20、单选题：
下面程序段的时间复杂度是( )i = 1;while ( i <= n )i = i * 3;
选项：
A: O(log3n)
B: O(n)
C: O(log2n)
D: O(n2)
答案: 【 O(log3n)】
2 线性表
线性表单元测验
1、单选题：
数据在计算机内存表示时，地址连续，并且逻辑上相邻的元素物理上也相邻，称为()
选项：
A: 存储结构
B: 逻辑结构
C: 顺序存储结构
D: 链式存储结构
答案: 【 顺序存储结构】
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、单选题：
链表的存储占存储空间:()
选项：
A: 分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针
B: 只有一部分，存放结点值
C: 只有一部分，存储表示结点间关系的指针
D: 分两部分，一部分存放结点值，另一部分存放结点所占的单元数
答案: 【 分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针】
4、单选题：
链表是一种采用()存储结构存储的线性表
选项：
A: 顺序
B: 链式
C: 星式
D: 网状
答案: 【 链式】
5、单选题：
线性表L在()情况下适用于使用链式结构实现
选项：
A: 需经常修改L的结点值
B: 需不断对L进行删除插入
C: L中含有大量的结点
D: L中结点的结构复杂
答案: 【 需不断对L进行删除插入】
6、单选题：
不带头结点的单链表first为空的判定条件是()
选项：
A: first=NULL
B: first->next=NULL
C: first->next=first
D: First!=NULL
答案: 【 first=NULL】
7、单选题：
设单链表结点的结构为(data,next).已知指针q所指结点是指针p所指结点的直接前驱，叵在*q与*p之间插入结点*s，则应执行的操作是()
选项：
A: s->next=p->next;p->next=s;
B: q->next=s;s->next=p;
C: p->next=s->next;s->next=p
D: p->next=s;s->next=q;
答案: 【 q->next=s;s->next=p;】
8、单选题：
设单链表结点的结构为(data,next).已经指针p所指的结点不是尾结点，若在*p之后再插入结点*s，则应执行的操作是()
选项：
A: s->next=p;p->next=s;
B: P->next=s;s->next=p;
C: s->next=p->next;p=s;
D: s->next=p->next;p->next=s;
答案: 【 s->next=p->next;p->next=s;】
9、单选题：
设单链表结点的结构为(data,next).若想摘除p->next所指向的结点，则应执行的操作是()
选项：
A: p->next =p->next->next;
B: p=p->next;p->next =p->next->next;
C: p->next = p;
D: p =p->next->next;
答案: 【 p->next =p->next->next;】
10、单选题：
已经L是一个不带表头的单链表，在表首插入结点*p的操作是（）
选项：
A: p=L;p->next=L;
B: P->next=L;p=L;
C: p->next=L;L=p;
D: L=p;p->next=L;
答案: 【 p->next=L;L=p;】
11、单选题：
利用双向链表作线性表的存储结构的优点是()
选项：
A: 便于单向进行插入和删除的操作
B: 便于双向进行插入和删除的操作
C: 节省空间
D: 便于销毁结构释放空间
答案: 【 便于双向进行插入和删除的操作】
12、单选题：
在一个单链表中，若删除p所指结点的后续结点，则执行（）
选项：
A: p->next = p->next->next;
B: p = p->next; p->next=p->next->next;
C: p->next = p->next;
D: p =p->next ->next;
答案: 【 p->next = p->next->next;】
13、单选题：
对于顺序表的优缺点，以下说法错误的是（）
选项：
A: 无需为表示结点间的逻辑关系而增加额外的存储空间
B: 可以方便地随机存取表中的任一结点
C: 插人和删除运算较方便
D: 由于顺序表要求占用连续的空间，存储分配只能预先进行(静态分配)
答案: 【 插人和删除运算较方便】
14、单选题：
以下说法错误的是（）
选项：
A: 对循环链表来说，从表中任一结点出发都能通过前后操作而扫描整个循环链表
B: 对单链表来说，只有从头结点开始才能扫描表中全部结点
C: 双链表的特点是找结点的前趋和后继都很容易
D: 对双链表来说，结点P的存储位置既存放在其前趋结点的后继指针域中，也存放在它的后继结点的前趋指针域中
答案: 【 对循环链表来说，从表中任一结点出发都能通过前后操作而扫描整个循环链表】
15、单选题：
以下说法正确的是（ ）
选项：
A: 单链表中，任两个元素的存储位置都有固定的联系，因为可以从头结点进行查找任何一个元素
B: 单链表中，要取得某个元素，只要知道该元素的指针即可，因此，单链表是随机存取的存储结构
C: 顺序存储结构属于静态结构，链式结构属于动态结构
D: 顺序存储方式只能用于存储线性结构
答案: 【 顺序存储结构属于静态结构，链式结构属于动态结构】
16、单选题：
线性表若采用链表存储结构时，要求内存中可用存储单元的地址（ ）
选项：
A: 必须是联系的
B: 部分地址必须是连续的
C: 一定是不连续的
D: 连续不连续都可以
答案: 【 连续不连续都可以】
17、单选题：
带头结点的单链表Head为空的判定条件是( )。
选项：
A: Head=Null
B: Head->next=NULL
C: Head->next=Head
D: Head->next！=NULL
答案: 【 Head->next=NULL】
18、单选题：
若某线性表中最常用的操作是取第i个元素和找第i个元素的前趋元素，则采用（ ）存储方式最节省时间。
选项：
A: 顺序表
B: 单链表
C: 双链表
D: 单循环链表
答案: 【 顺序表 】
19、单选题：
在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）】
20、单选题：
已知指针 p 指向某双向链表的一个中间结点，下列语句序列实现的操作是（ ）q = p -> prior; p -> prior = q -> prior;q -> prior -> next = p;free(q);
选项：
A: 删除 p 结点的直接前驱结点
B: 删除 p 结点
C: 删除 p 结点及其所有后继结点
D: 删除 p 结点的直接后继结点
答案: 【 删除 p 结点的直接前驱结点】
线性表基本概念-随堂测验
1、单选题：
以下数据结构不属于线性结构的是( )
选项：
A: 线性表
B: 队列
C: 树
D: 字符串
答案: 【 树】
2、单选题：
以下对线性结构的描述,错误的是( )
选项：
A: 最简单且应用最广泛的一种数据结构
B: 有且仅有一个开始结点和一个终端结点
C: 所有结点都最多只有一个直接前趋和一个直接后继
D: 所有的元素为一对多的关系
答案: 【 所有的元素为一对多的关系】
3、单选题：
线性表相邻的元素之间，存在着前后的序偶关系，中间的任一个元素ai，它前面的一个数据元素ai-1，称为ai( )
选项：
A: 直接前趋
B: 直接后继
C: 直接元素
D: 直接数据
答案: 【 直接前趋】
4、单选题：
线性表中的数据元素关系是( )
选项：
A: 一对一
B: 多对一
C: 一对多
D: 多对多
答案: 【 一对一】
5、判断题：
数据元素的类型是抽象数据类型ElemType.当软件设计问题具体确定时，ElemType将被具体的数据类型取代()
选项：
A: 正确
B: 错误
答案: 【 正确】
线性表的链式存储结构-练习
1、单选题：
顺序表中逻辑上相邻的元素的物理位置（ ）相邻，单链表中逻辑上相邻的元素的物理位置（ ）相邻
选项：
A: 一定/不一定
B: 不一定/不一定
C: 一定/一定
D: 不一定/一定
答案: 【 一定/不一定】
2、单选题：
以下哪种不是线性表的链式存储结构（）
选项：
A: 顺序表
B: 单链表
C: 循环链表
D: 双向链表
答案: 【 顺序表】
3、单选题：
带头结点的循环链表与单链表的区别仅仅在于其尾结点的链域是指向( )的指针
选项：
A: 头结点
B: 首结点
C: 头指针
D: NULL
答案: 【 头结点】
4、单选题：
链表中元素的逻辑上的相邻关系通过( )来表示
选项：
A: 指针
B: 物理相邻
C: 人为指定
D: 数据域
答案: 【 指针】
5、判断题：
链表按实现的方式可以分为动态链表和静态链表（）
选项：
A: 正确
B: 错误
答案: 【 正确】
线性表的顺序存储结构-随堂测验
1、单选题：
线性表主要有两种存储结构,( )和链式存储结构
选项：
A: 顺序存储结构
B: 散列存储结构
C: 树形存储结构
D: 图形存储结构
答案: 【 顺序存储结构】
2、单选题：
对于顺序表，以下说法错误的是（ ）
选项：
A: 顺序表是用一维数组实现的线性表，数组的下标可以看成是元素的绝对地址
B: 顺序表的所有存储结点按相应数据元素间的逻辑关系决定的次序依次排列
C: 顺序表的特点是:逻辑结构中相邻的结点在存储结构中仍相邻
D: 顺序表的特点是:逻辑上相邻的元素，存储在物理位置也相邻的单元中
答案: 【 顺序表是用一维数组实现的线性表，数组的下标可以看成是元素的绝对地址】
3、单选题：
顺序表是线性表的（ ）
选项：
A: 链式存储结构
B: 顺序存储结构
C: 索引存储结构
D: 散列存储结构
答案: 【 顺序存储结构】
4、单选题：
顺序表的一个存储结点仅仅存储线性表的一个（ ）
选项：
A: 数据元素
B: 数据项
C: 数据
D: 数据结构
答案: 【 数据元素】
5、单选题：
一个数组第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是（ ）
选项：
A: 110
B: 108
C: 100
D: 120
答案: 【 108】
线性表链式存储结构相关操作1-练习
1、单选题：
带头结点的单链表Head为空的判定条件是( )
选项：
A: Head=NUll
B: Head->next=NULL
C: Head->next=Head
D: Head->next！=NULL
答案: 【 Head->next=NULL】
2、单选题：
不带头结点的单链表Head为空的判定条件是( )
选项：
A: Head=Nll
B: Head->next=NULL
C: Head->next=Head
D: Head->next！=NULL
答案: 【 Head=Nll】
3、单选题：
删除单链表中p结点的后继结点的语句为( )
选项：
A: p->next=p->next->next
B: p=p->next->next
C: p=p->next->next
D: p->next=p
答案: 【 p->next=p->next->next】
4、单选题：
在一单链表中，删除p所指结点的直接后继结点时，应执行以下操作：（1）q = p->next；（2）p->next =( )；（3）free (q)；
选项：
A: q->next
B: q
C: q->next->next
D: NULL
答案: 【 q->next】
5、判断题：
删除单链表的结点时，不需要释放被删除结点的空间
选项：
A: 正确
B: 错误
答案: 【 错误】
线性表链式存储结构相关操作2-练习
1、单选题：
非空的循环单链表head的尾结点（由p所指向）满足( )
选项：
A: p->next==NULL
B: p==NULL
C: p->next==head
D: p==head
答案: 【 p->next==head】
2、单选题：
在循环双链表的p所指结点之后插入s所指结点的操作是( )
选项：
A: p->right=s;s->left=p;p->right->left=s;s->right=p->right;
B: p->right=s;p->right->left=s;s->left=p;s->right=p->right;
C: s->left=p;s->right=p->right;p->right=s;p->right->left=s;
D: s->left=p;s->right=p->right; p->right->left=s;p->right=s;
答案: 【 s->left=p;s->right=p->right; p->right->left=s;p->right=s; 】
3、单选题：
设指针P指向双链表的某一结点，则双链表结构的对称性可用（ ）式来描述
选项：
A: p->prior->next->==p->next->next
B: p->prior->prior->==p->next->prior
C: p->prior->next->==p->next->prior
D: p->next->next==p->prior->prior
答案: 【 p->prior->next->==p->next->prior】
4、单选题：
设rear是指向非空带头结点的循环单链表的尾指针,则删除表首结点的语句为( )
选项：
A: p=rear; rear=rear->next;
B: rear=rear->next;
C: rear=rear->next->next;
D: p=rear->next->next; rear->next->next=p->next;
答案: 【 p=rear->next->next; rear->next->next=p->next;】
5、单选题：
从一个具有n个结点的单链表中查找其值等于x结点时，在查找成功的情况下，需平均比较( )个结点。
选项：
A: n
B: n/2
C: (n-1)/2
D: (n+1)/2
答案: 【 (n+1)/2】
顺序表的相关操作-练习
1、单选题：
在一个长度为n的数组中删除第i个元素（0≤i≤n-1）时，需平均向前移动（）个元素
选项：
A: （n-1）/2
B: n/2
C: （n+1）/2
D: n
答案: 【 （n-1）/2】
2、单选题：
在一个长度为n的数组中第i个位置（0≤i≤n）前插入一个元素时，需平均向前移动()个元素
选项：
A: （n-1）/2
B: n/2
C: （n+1）/2
D: n
答案: 【 n/2】
3、单选题：
关于顺序表的特点,以下描述错误的是（）
选项：
A: 逻辑关系上相邻的两个元素在物理存储位置上也相邻
B: 可以随机存取表中任一元素
C: 插入或删除某一元素时，需要移动大量元素
D: 在表头插入元素时,移动元素最少
答案: 【 在表头插入元素时,移动元素最少】
4、判断题：
顺序表在读取元素值时,需要移动大量元素（）
选项：
A: 正确
B: 错误
答案: 【 错误】
5、判断题：
顺序表在删除最后一个元素时,也需要移动元素
选项：
A: 正确
B: 错误
答案: 【 错误】
3 字符串
KMP算法-练习
1、单选题：
下面关于KMP算法的描述，不正确的是()
选项：
A: 尽量利用已经得到的“部分匹配”的结果信息
B: 尽量不要让i回溯
C: 加快子串向右滑动的速度
D: 一定比朴素算法要好
答案: 【 一定比朴素算法要好】
2、单选题：
next[j]表明当子串中第j个字符与主串中的相应字符不相等时，在子串中需要重新与主串中该字符进行比较的字符位置.若next[j]=1，则说明，下一趟匹配时，应该()
选项：
A: 把T[1]与S[i]进行比较
B: 把S[1]与T[i]进行比较
C: 把T[1]和S[1]进行比较
D: 把T[i]和S[i]进行比较
答案: 【 把T[1]与S[i]进行比较】
3、单选题：
关于next[j]的描述，正确的是()
选项：
A: 与主串无关,与子串无关
B: 与主串无关,与子串有关
C: 与主串有关,与子串有关
D: 与主串有关,与子串无关
答案: 【 与主串无关,与子串有关】
4、单选题：
有字符串S=”abaabcac”,则next[3]=()
选项：
A: 0
B: 1
C: 2
D: 3
答案: 【 1】
5、单选题：
设n为主串S的长度，m为子串T的长度，下面描述错误的是()
选项：
A: 求next数组的算法时间复杂度为O(m)
B: 朴素算法时间复杂度为O(n*m)
C: KMP算法时间复杂度为O(n)
D: KMP算法一定优于朴素算法
答案: 【 KMP算法一定优于朴素算法】
串的应用-练习
1、单选题：
关于朴素算法和KMP算法的描述,正确的是()
选项：
A: 朴素算法无回溯,KMP算法无回溯
B: 朴素算法无回溯,KMP算法有回溯
C: 素算法有回溯,KMP算法无回溯
D: 朴素算法有回溯,KMP算法有回溯
答案: 【 素算法有回溯,KMP算法无回溯】
2、判断题：
文本编辑程序，把整个文本看成一个长字符串，页是文本串的子串，行又是页的子串()
选项：
A: 正确
B: 错误
答案: 【 正确】
串的概念和存储结构-练习
1、单选题：
串是一种特殊的线性表，其特殊性体现在()
选项：
A: 可以顺序存储
B: 数据元素是一个字符
C: 可以链接存储
D: 数据元素可以是多个字符
答案: 【 数据元素是一个字符】
2、单选题：
有字符串d =“BEI_JING”，它的长度是()
选项：
A: 3
B: 4
C: 7
D: 8
答案: 【 8】
3、单选题：
有字符串A=“This_is_a_demo”和 B=“is”，B在A中的位置是()
选项：
A: 1
B: 2
C: 3
D: 6
答案: 【 3】
4、单选题：
字符串A=“string”和B=“demo”执行 Concat(T,A,B)后,T=()
选项：
A: “stringdemo”
B: “string”
C: “demo”
D: “demostring”
答案: 【 “stringdemo”】
5、判断题：
空串与空格串是相同的()
选项：
A: 正确
B: 错误
答案: 【 错误】
串的模式匹配-练习
1、单选题：
设两个字符串p和q，求q在p中首次出现的位置的运算称作()
选项：
A: 连接
B: 模式匹配
C: 求子串
D: 求串长
答案: 【 模式匹配】
2、单选题：
下面的操作与串的模式匹配不相关的是()
选项：
A: 文本查找
B: 搜索引擎
C: 垃圾邮件过滤
D: 文本连接
答案: 【 文本连接】
3、判断题：
使用朴素算法时,第一轮匹配需要将主串S的第1个字符和子串T的第1个字符比较()
选项：
A: 正确
B: 错误
答案: 【 正确】
4、判断题：
使用朴素算法,当某轮匹配失败时,主串的指针i都不需要回溯()
选项：
A: 正确
B: 错误
答案: 【 错误】
5、判断题：
设n为主串S的长度，m为子串T的长度,朴素算法在最坏的情况下,其时间复杂度是
选项：
A: 正确
B: 错误
答案: 【 正确】
字符串单元测验
1、单选题：
串是一种特殊的线性表,其特殊性体现在()
选项：
A: 可以顺序存储
B: 数据元素是一个字符
C: 可以链接存储
D: 数据元素可以是多个字符
答案: 【 数据元素是一个字符】
2、单选题：
空串和空格串的区别在于()
选项：
A: 没有区别
B: 两串的长度不相等
C: 两串的长度相等
D: 两串包含的字符不相同
答案: 【 两串包含的字符不相同】
3、单选题：
两个串相等的条件是()
选项：
A: 两串的长度相等
B: 两串包含的字符相同
C: 两串的长度相等,且两串包含的字符相同
D: 两串的长度相等,且对应位置的字符相同
答案: 【 两串的长度相等,且对应位置的字符相同】
4、单选题：
一个子串在包含它的主串中的位置是指()
选项：
A: 子串的最后那个字符在主串中的位置
B: 子串的最后那个字符在主串中首次出现的位置
C: 子串的第一个字符在主串中的位置
D: 子串的第一个字符在主串中首次出现的位置
答案: 【 子串的第一个字符在主串中首次出现的位置】
5、单选题：
在长度为n的串S的第i个位置插入另一个串,则i的合法值应该是()
选项：
A: i>0
B: I<=n
C: 1<=i<=n
D: 1<=i<=n+1
答案: 【 1<=i<=n+1】
6、单选题：
设串s1=’ABCDEFG’，s2=’PQRST’，函数con (x, y) 返回x与y串的连接串，函数subs (s, i, j) 返回串s的从序号i的字符开始的j个字符组成的子串，函数len (s) 返回串s的长度，则con (subs (s1, 2, len (s2)), subs (s1, len (s2), 2)) 的结果串是()
选项：
A: BCDEF
B: BCDEFG
C: BCPQRST
D: BCDEFEF
答案: 【 BCDEFEF】
7、单选题：
设s = ‘I_AM_A_TEACHER’，其长度是()
选项：
A: 11
B: 12
C: 13
D: 14
答案: 【 14】
8、单选题：
设两个字符串p和q，求q在p中首次出现的位置的运算称作()
选项：
A: 连接
B: 模式匹配
C: 求子串
D: 求串长
答案: 【 模式匹配 】
9、单选题：
模式串 T=”abaabcac”, 则next[6]=()
选项：
A: 1
B: 2
C: 3
D: 4
答案: 【 3】
10、单选题：
文本编辑器中为了便于管理文本的页和行，在进入文本编辑前会先为文本建立相应的页表和行表，页表的每一项给出了页号和该页的起始行号，而行表的每一项则指示了每一行的行号、起始地址和该行子串的长度。就文本编辑过程中行表和页表的维护而言，下列说法中正确的是（ ）
选项：
A: 若被删除的行是所在页的起始行，只需修改页表中相应页的起始行号
B: 在某行内插入若干字符，只需要修改行表中该行的长度
C: 插入一行，不仅涉及行表的插入，可能还要涉及页表的修改或插入
D: 在某行内修改若干字符，一定会改变行表中该行的长度
答案: 【 插入一行，不仅涉及行表的插入，可能还要涉及页表的修改或插入】
11、单选题：
已知字符串 S 为 “abaabaabacacaabaabcc” ，模式串 t 为 “abaabc” 。采用 KMP 算法进行匹配，第一次出现 “失配” （ s[i] ≠ t[j] ）时，i = j = 5，其中,提示：这里i、j的取值范围是从0开始的,则下次开始匹配时，i 和 j 的值分别是()
选项：
A: i=5,j=0
B: i=6,j=0
C: i=1,j=0
D: i=5,j=2
答案: 【 i=5,j=2】
12、单选题：
下列关于串的叙述，错误的是()
选项：
A: KMP算法的特点是在模式匹配时指示主串的指针不会回溯
B: 串是一种数据对象和操作都特殊的线性表
C: 若串 S 的长度为 n ，则 S 的子串个数为 n(n+1)/2
D: 串只能使用顺序存储
答案: 【 串只能使用顺序存储】
13、单选题：
设串s1=’ABCDEFG’，s2=’PQRST’，函数con(x,y)返回x和y串的连接串，subs(s, i, j)返回串s的从序号i开始的j个字符组成的子串，len(s)返回串s的长度，则con(subs(s1, 2, len(s2)), subs(s1, len(s2), 2))的结果串是()
选项：
A: BCDEFG
B: BCPQRST
C: BCDEFEF
D: BCDEF
答案: 【 BCDEFEF】
14、单选题：
下列哪些为空串？（ ）
选项：
A: S=""
B: S="θ"
C: S=" "
D: S="φ"
答案: 【 S=""】
15、单选题：
假设S=“abcaabcaaabca”，T=“bca”，Index (S,T,3) 的结果是（ ）(假设第一个字符的位置为1)
选项：
A: 2
B: 11
C: 0
D: 6
答案: 【 6】
16、单选题：
串的最基本两种存储方式是()
选项：
A: 顺序存储和链式存储
B: 顺序存储和散列存储
C: 散列存储和链式存储
D: 顺序存储和索引存储
答案: 【 顺序存储和链式存储】
17、单选题：
若串S="software"，其子串的个数是（）
选项：
A: 8
B: 37
C: 36
D: 9
答案: 【 36】
18、单选题：
串的长度是指()
选项：
A: 串中所含不同字母的个数
B: 串中所含字符的个数
C: 串中所含不同字符的个数
D: 串中所含非空格字符的个数
答案: 【 串中所含字符的个数】
19、单选题：
下面关于串的叙述中，哪一个不正确（）
选项：
A: 串是字符的有限序列
B: 空串是由空格构成的串
C: 模式匹配是串的一种重要运算
D: 串既可以用顺序存储，也可以采用链式存储
答案: 【 空串是由空格构成的串】
20、判断题：
可以使用递推的方法来求解next数组()
选项：
A: 正确
B: 错误
答案: 【 正确】
4 栈和队列
栈与队列单元测验
1、单选题：
设进栈序列是1，2，3，…，n，输出序列为p1，p2，p3，…，pn。若p1=3，则p2为( )。
选项：
A: 可能是2
B: 不可能是2
C: 必是1
D: 可能是1
答案: 【 可能是2 】
2、单选题：
数组q[M]（M等于6）存储一个循环队，first和last分别是首尾指针。已知first和last的当前值分别等于2和5，且q[5]存放的是队尾元素。当从队列中删除两个元素，再插入一个元素后，first和last的值分别等于（）。
选项：
A: 1和3
B: 3和6
C: 4和0
D: 5和1
答案: 【 4和0】
3、单选题：
数组S[M]存储一个栈，top为栈顶指针。如果条件top==M表示栈满，那么条件( )表示栈空。
选项：
A: top!=0
B: top==1
C: top==0
D: top==-1
答案: 【 top==0】
4、单选题：
设数组data[20]作为循环队列SQ的存储空间，front为队头标识，rear为队尾标识，当front==4，rear==15时，以下说法正确的是( )。
选项：
A: 队列中还能存放数据元素的空闲位置数量为9个
B: 队列中还能存放数据元素的空闲位置数量为8个
C: 队列中还能存放数据元素的空闲位置数量为6个
D: 队列中还能存放数据元素的空闲位置数量为7个
答案: 【 队列中还能存放数据元素的空闲位置数量为8个】
5、单选题：
3 2+5*4-（表达式中相邻数字以空格相隔）的计算结果是( ) 。
选项：
A: 19
B: 18
C: 20
D: 21
答案: 【 21】
6、单选题：
在循环队列中，元素的排列顺序（ ）。
选项：
A: 由元素进队的先后顺序确定
B: 与元素值的大小有关
C: 与队头和队尾指针的取值有关
D: 与队中数组大小有关
答案: 【 由元素