正确 错误 2、在循环链表中设尾指针比设头指针方便。 （ ） 正确 错误 3、线性表的顺序存储结构优于链式存储结构。 （ ） 正确 错误 4、单链表的头结点表示的是线性表中的第一个元素。 正确 错误 5、在双向循环链表中插入或删除元素时仅需要修改结点的指针，不需要移动元素，因此算法的时间复杂度为O(1)。 正确 错误

测试结果如下：

? ? ? ? ? ? ? ? ? ? ? ? ? ? ?

1.1 [单选] [对] 顺序表中第一个元素的起始存储地址为100，每个元素的长度为4，则第五个元素的起始地址是＿＿＿＿＿＿＿。 1.2 [单选] [对] 若L是SqList类型的顺序表，则线性表中的第i个元素是＿＿＿＿＿＿＿。

1.3 [单选] [对] 有头结点的单链表（head为头指针）是空表的条件是＿＿＿＿＿＿＿

1.4 [单选] [错] 非空的循环单链表(head为头指针)的尾结点（由指针p所指示）应满足＿＿＿＿＿＿＿＿。

1.5 [单选] [对] 若在线性表的任何位置上删除元素的概率是相等的，那么在长度为n的顺序表中删除一个元素时需平均移动＿＿＿＿＿＿＿＿个元素。 2.1 [多选] [对] 单链表的特点是＿＿＿＿＿＿＿＿。 2.2 [多选] [对] 顺序表的特点是＿＿＿＿＿＿＿＿。

2.3 [多选] [对] 在双向循环链表中，若s是指向表中某结点的指针，则＿＿＿＿＿＿＿＿。

2.4 [多选] [对] 顺序表具备的特点有＿＿＿＿＿＿＿＿。

2.5 [多选] [对] 在双向循环链表（L为头指针）中，指针p所指结点为尾结点的条件是＿＿＿＿＿＿＿＿。

3.1 [判断] [对] 顺序表能够以元素在计算机内的物理位置的相邻性来表示线性表中元素之间的逻辑关系。

3.2 [判断] [对] 在循环链表中设尾指针比设头指针方便。 （ ） 3.3 [判断] [对] 线性表的顺序存储结构优于链式存储结构。 （ ） 3.4 [判断] [对] 单链表的头结点表示的是线性表中的第一个元素。

3.5 [判断] [对] 在双向循环链表中插入或删除元素时仅需要修改结点的指针，不需要移动元素，因此算法的时间复杂度为O(1)。

《数据结构》第03章在线测试

《数据结构》第03章在线测试

剩余时间：4 5:44

第一题、单项选择题（每题1分，5道题共5分）

1、一个栈的入栈序列是1，2，3，…，n，其输出序列为p1,p2,p3,…pn,若p1＝n, 则pi为＿＿＿＿＿＿＿＿。

A、i C、n-i+1

B、n-i D、不确定

2、在进行递归函数调用时，处理参数和返回地址需要使用一种称为＿＿＿＿＿＿＿＿的数据结构。

A、线性表 C、队列

B、栈 D、树

3、栈和队列的共同点是＿＿＿＿＿＿＿＿。

A、都是后进先出

C、都是只允许在端点处插入和删除元素

B、都是先进先出 D、无共同点

4、在顺序栈中，base、top分别为栈底、栈顶指针，则＿＿＿＿＿＿＿时表明栈空。

A、base＝＝NULL C、base＝＝top

B、top＝＝ NULL D、

5、非空顺序栈中的栈顶指针始终指向栈顶元素的＿＿＿＿＿＿＿位置。

A、上一个 C、下一个

B、当前 D、

第二题、多项选择题（每题2分，5道题共10分）

1、一个栈的入栈序列是{1,2,3,4,5},则栈可能的输出序列是＿＿＿＿＿＿＿。

A、{1,2,3,4,5} B、{5,4,3,2,1} C、{2,1,4,3,5} D、{4,2,3,1,5} E、{5,1,4,3,2} F、{3,4,2,1,5}

2、循环队列中，设队列元素依次存放在Q[0..m]中，f、r分别指示队头元素位置和队尾元素的下一个位置，此时队空、队满的判断条件都是f＝＝r,为解决此矛盾，通常可采用＿＿＿＿＿＿＿。

A、附设标志位，f＝＝r时借助标志判断

B、牺牲一个元素空间，(r+1）％ m＝＝f时队满，f＝＝r时队空 C、牺牲一个元素空间，(r+1）％ (m+1)＝＝f时队满，f＝＝r时队空 D、另设表示队列长度的length域来区别队列空、满

3、下列数据结构中，＿＿＿＿＿＿＿是线性结构。

A、线性表 B、栈 C、队列 D、树 E、图

4、队列操作的原则是＿＿＿＿＿＿＿。

A、先进先出 B、后进先出 C、可以进行插入 D、可以进行删除

5、一个队列的入队序列是{1,2,3,4},则队列不可能的输出序列是＿＿＿＿＿＿＿。

A、4321 B、1234 C、1432 D、3241

第三题、判断题（每题1分，5道题共5分） 1、队列是先进先出的线性表。

正确

错误

2、若用户无法估计所用队列的最大长度，则最好采用循环队列

正确 错误 3、一个队列的入队序列是{1,2,3,4},则队列的输出序列只能是{1,2,3,4}。 正确 错误 4、一个栈的入栈序列是{1,2,3,4,5},则{1,2,3,4,5}是不可能的输出序列。 正确 错误 5、队列只能有一种输出序列，即队列中的元素只能按照进入队列的顺序依次出队。 正确 错误

测试结果如下：

? ? ? ? ? ? ?

? ? ? ? ? ? ? ?

1.1 [单选] [对] 一个栈的入栈序列是1，2，3，…，n，其输出序列为p1,p2,p3,…pn,若p1＝n, 则pi为＿＿＿＿＿＿＿＿。

1.2 [单选] [对] 在进行递归函数调用时，处理参数和返回地址需要使用一种称为＿＿＿＿＿＿＿＿的数据结构。

1.3 [单选] [对] 栈和队列的共同点是＿＿＿＿＿＿＿＿。

1.4 [单选] [对] 在顺序栈中，base、top分别为栈底、栈顶指针，则＿＿＿＿＿＿＿时表明栈空。

1.5 [单选] [对] 非空顺序栈中的栈顶指针始终指向栈顶元素的＿＿＿＿＿＿＿位置。

2.1 [多选] [对] 一个栈的入栈序列是{1,2,3,4,5},则栈可能的输出序列是＿＿＿＿＿＿＿。

2.2 [多选] [对] 循环队列中，设队列元素依次存放在Q[0..m]中，f、r分别指示队头元素位置和队尾元素的下一个位置，此时队空、队满的判断条件都是f＝＝r,为解决此矛盾，通常可采用＿＿＿＿＿＿＿。

2.3 [多选] [对] 下列数据结构中，＿＿＿＿＿＿＿是线性结构。 2.4 [多选] [对] 队列操作的原则是＿＿＿＿＿＿＿。

2.5 [多选] [对] 一个队列的入队序列是{1,2,3,4},则队列不可能的输出序列是＿＿＿＿＿＿＿。

3.1 [判断] [对] 队列是先进先出的线性表。

3.2 [判断] [对] 若用户无法估计所用队列的最大长度，则最好采用循环队列 3.3 [判断] [对] 一个队列的入队序列是{1,2,3,4},则队列的输出序列只能是{1,2,3,4}。

3.4 [判断] [对] 一个栈的入栈序列是{1,2,3,4,5},则{1,2,3,4,5}是不可能的输出序列。

3.5 [判断] [对] 队列只能有一种输出序列，即队列中的元素只能按照进入队列的顺序依次出队。

《数据结构》第04章在线测试

第一题、单项选择题（每题1分，5道题共5分） 1、设有两个串s1和s2，求s2在s1中首次出现的位置的操作是＿＿＿＿＿＿＿＿。 A、连接 C、求子串

B、模式匹配 D、求串长

2、字符串是一种特殊的线性表，其特殊性在于它的数据元素只能是＿＿＿＿＿＿＿＿。

A、字符 C、数字

B、字符串 D、字母

3、串是一种特殊的线性表，其特殊性体现在＿＿＿＿＿＿＿＿。

A、可以顺序存储 C、可以链接存储

B、数据元素是一个字符 D、数据元素可以是多个字符

4、空格串的长度为＿＿＿＿＿＿＿＿。

A、0

C、串中空格的个数

B、1 D、

5、设串s＝\则s的长度为＿＿＿＿＿＿＿＿。

A、11 C、15

B、12 D、16

第二题、多项选择题（每题2分，5道题共10分）

1、在定长顺序存储表示中，对串长的表示方法有＿＿＿＿＿＿＿＿＿＿。

A、用域变量表示

B、用下标为0的数组分量表示 C、在串值后加结束标记字符 D、无法明确表示

2、以下说法正确的是＿＿＿＿＿＿＿＿＿＿。

A、串长相等的两个串相等

B、串值的引号不被计算在串长之内 C、空串的长度为0 D、空格串的长度为0