数据结构在线测试01-08章

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

《数据结构》第01章在线测试 剩余时间：5 0:49 答题须知：1、本卷满分20分。 2、答完题后，请一定要单击下面的“交卷”按钮交卷，否则无法记录本试卷的成绩。 3、在交卷之前，不要刷新本网页，否则你的答题结果将会被清空。 第一题、单项选择题（每题1分，5道题共5分） 1、计算机算法是指＿＿＿＿＿＿＿＿ A、计算方法和运算结果 C、解决某一问题的有限指令系列 B、调度方法 D、排序方法 2、算法分析的目的是＿＿＿＿＿＿＿＿ A、找出数据结构的合理性 C、研究算法中输入和输出的关系 B、分析算法的效率以求改进 D、分析算法的可读性和可行性 3、设n为正整数。确定下面程序段的时间复杂度： k＝0; for(i＝1;i＜＝n;i++){ for(j＝i;j＜＝n;j++) @ k++; } A、n C、nlogn B、logn D、n^2 4、树型结构和图结构都属于＿＿＿＿＿＿＿＿。 A、线性结构 C、动态结构 B、非线性结构 D、静态结构 5、下列函数中，时间复杂度最小的是＿＿＿＿＿＿＿＿。 A、nlogn+5000n C、n^logn-6000n B、n^2-8000n D、10nlogn-7000n 第二题、多项选择题（每题2分，5道题共10分） 1、根据元素之间关系的不同特性，通常可有下列基本结构＿＿＿＿＿＿＿＿。 A、集合 B、线性结构 C、树结构 D、图结构 2、从逻辑上可以把数据结构分为＿＿＿＿＿＿＿＿。

A、顺序结构 B、链式结构 C、线性结构 D、非线性结构 E、动态结构 F、静态结构

3、下列说法中，不正确的是＿＿＿＿＿＿＿＿。

A、数据是数据元素的基本单位

B、数据元素是数据中不可分割的最小标识单位 C、数据元素可由若干个数据项组成 D、数据项可由若干个数据元素组成

4、影响程序运行时间的因素包括＿＿＿＿＿＿＿＿＿＿＿＿＿＿。

A、书写程序的语言 B、问题的规模

C、编译器产生的机器代码的质量 D、计算机的运行速度 E、算法的策略 F、输出数据量

5、数据结构被形式化的定义为(D,S), 其中D、S分别是＿＿＿＿＿＿＿＿的有限集合。

A、数据元素 B、数据操作 C、数据存储 D、数据关系

第三题、判断题（每题1分，5道题共5分） 1、数据的物理结构是指数据和关系在计算机内的实际存储形式。 正确 错误 2、算法原地工作的含义是指运行时不需要任何临时的辅助空间。 正确 错误 3、数据对象是一组数据元素的集合。 正确 错误 4、计算机算法必须具备的特性有： 输入、输出、易读性、稳定性和安全性。 正确 错误 5、任何一个算法的设计取决于数据的逻辑结构，而算法的实现则依赖于所采用的存储结构。 正确 错误

测试结果如下：

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

1.1 [单选] [对] 计算机算法是指＿＿＿＿＿＿＿＿ 1.2 [单选] [对] 算法分析的目的是＿＿＿＿＿＿＿＿ 1.3 [单选] [错] 设n为正整数。确定下面程序段的时间复杂度： k＝0; for(i＝1;i＜＝n;i++){ for(j＝i;j＜＝n;j++) @ k++; }

1.4 [单选] [对] 树型结构和图结构都属于＿＿＿＿＿＿＿＿。

1.5 [单选] [对] 下列函数中，时间复杂度最小的是＿＿＿＿＿＿＿＿。

2.1 [多选] [对] 根据元素之间关系的不同特性，通常可有下列基本结构＿＿＿＿＿＿＿＿。

2.2 [多选] [对] 从逻辑上可以把数据结构分为＿＿＿＿＿＿＿＿。 2.3 [多选] [对] 下列说法中，不正确的是＿＿＿＿＿＿＿＿。

2.4 [多选] [对] 影响程序运行时间的因素包括＿＿＿＿＿＿＿＿＿＿＿＿＿＿。 2.5 [多选] [对] 数据结构被形式化的定义为(D,S), 其中D、S分别是＿＿＿＿＿＿＿＿的有限集合。

3.1 [判断] [对] 数据的物理结构是指数据和关系在计算机内的实际存储形式。 3.2 [判断] [对] 算法原地工作的含义是指运行时不需要任何临时的辅助空间。 3.3 [判断] [对] 数据对象是一组数据元素的集合。

3.4 [判断] [对] 计算机算法必须具备的特性有： 输入、输出、易读性、稳定性和安全性。

3.5 [判断] [对] 任何一个算法的设计取决于数据的逻辑结构，而算法的实现则依赖于所采用的存储结构。

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

《数据结构》第02章在线测试 剩余时间：5 3:30 第一题、单项选择题（每题1分，5道题共5分）

1、顺序表中第一个元素的起始存储地址为100，每个元素的长度为4，则第五个元素的起始地址是＿＿＿＿＿＿＿。

A、105 C、120

B、116 D、124

2、若L是SqList类型的顺序表，则线性表中的第i个元素是＿＿＿＿＿＿＿。

A、L.elem[i] C、L.elem[i+1]

B、L.elem[i-1] D、L.elem[i+2]

3、有头结点的单链表（head为头指针）是空表的条件是＿＿＿＿＿＿＿

A、head-＞next＝＝NULL; C、head-＞next＝＝head;

B、head＝＝NULL;

D、head-＞next-＞next＝＝ NULL;

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

A、p-＞next＝＝NULL; C、p-＞next＝＝head;

B、p＝＝NULL; D、v

5、若在线性表的任何位置上删除元素的概率是相等的，那么在长度为n的顺序表中删除一个元素时需平均移动＿＿＿＿＿＿＿＿个元素。

A、n C、n/2

B、(n-1)/2 D、(n+1)/2

第二题、多项选择题（每题2分，5道题共10分） 1、单链表的特点是＿＿＿＿＿＿＿＿。

A、随机存取 B、顺序存取

C、元素间的逻辑关系由指针指示 D、插入删除元素时需要移动表中元素

E、插入删除元素时不必移动元素，只须修改指针

F、数据元素在存储器内的物理位置顺序与它们的逻辑顺序不一定相同

2、顺序表的特点是＿＿＿＿＿＿＿＿。

A、随机存取

B、顺序存取

C、元素间的逻辑关系由指针指示 D、插入删除元素时需要移动表中元素

E、插入删除元素时不必移动元素，只须修改指针

F、数据元素在存储器内的物理位置顺序与它们的逻辑顺序一定相同 G、元素间的逻辑关系隐含在存储位置中

3、在双向循环链表中，若s是指向表中某结点的指针，则＿＿＿＿＿＿＿＿。

A、s-＞next＝＝s

B、s-＞next-＞prior＝＝s C、s-＞prior-＞next ＝＝s D、s-＞ prior＝＝s

4、顺序表具备的特点有＿＿＿＿＿＿＿＿。

A、随机存取 B、顺序存取

C、插入删除需要移动元素 D、事先估计存储空间的大小 E、插入删除只需要修改指针

5、在双向循环链表（L为头指针）中，指针p所指结点为尾结点的条件是＿＿＿＿＿＿＿＿。

A、p==L

B、p-＞next＝＝L C、L-＞prior＝＝p D、L-＞next＝＝p

第三题、判断题（每题1分，5道题共5分）

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

正确 错误 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

3、以下关于串的存储方式的说法中正确的是＿＿＿＿＿＿＿＿＿＿。

A、定长顺序表示和堆分配表示都是串的顺序存储表示

B、定长顺序表示的串的存储空间是编译时预先分配的一个比较大的连续空间 C、堆分配表示的串的存储空间是在程序执行过程中动态分配的 D、堆分配存储表示时的空串不占用连续的存储区

4、串的机内表示方法有＿＿＿＿＿＿＿＿＿＿。

A、定长顺序存储表示 B、堆分配存储表示 C、块链存储表示 D、散列表示

5、串用定长顺序存储方式表示时，有可能发生“截断”的操作有＿＿＿＿＿＿＿＿＿＿。

A、串连接 B、求子串 C、串替换 D、插入串 E、删除子串

第三题、判断题（每题1分，5道题共5分） 1、空串和空格串是一样的。

正确

错误

2、如果一个串中的所有字符均在另一串中出现，则前者是后者的子串。

正确

错误

3、串也有两种存储结构：顺序结构和链式结构。

正确

错误

4、在串的链式存储结构中，结点大小与存储密度之间没有关系。

正确

错误

5、在C语言中，用动态分配函数进行管理的自由存储区称为“堆”。

正确 错误 测试结果如下： ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 1.1 [单选] [对] 设有两个串s1和s2，求s2在s1中首次出现的位置的操作是＿＿＿＿＿＿＿＿。 1.2 [单选] [对] 字符串是一种特殊的线性表，其特殊性在于它的数据元素只能是＿＿＿＿＿＿＿＿。 1.3 [单选] [对] 串是一种特殊的线性表，其特殊性体现在＿＿＿＿＿＿＿＿。 1.4 [单选] [对] 空格串的长度为＿＿＿＿＿＿＿＿。 1.5 [单选] [对] 设串s＝\则s的长度为＿＿＿＿＿＿＿＿。 2.1 [多选] [对] 在定长顺序存储表示中，对串长的表示方法有＿＿＿＿＿＿＿＿＿＿。 2.2 [多选] [对] 以下说法正确的是＿＿＿＿＿＿＿＿＿＿。 2.3 [多选] [错] 以下关于串的存储方式的说法中正确的是＿＿＿＿＿＿＿＿＿＿。 ABC 2.4 [多选] [对] 串的机内表示方法有＿＿＿＿＿＿＿＿＿＿。 2.5 [多选] [对] 串用定长顺序存储方式表示时，有可能发生“截断”的操作有＿＿＿＿＿＿＿＿＿＿。 3.1 [判断] [对] 空串和空格串是一样的。 3.2 [判断] [对] 如果一个串中的所有字符均在另一串中出现，则前者是后者的子串。 3.3 [判断] [对] 串也有两种存储结构：顺序结构和链式结构。 3.4 [判断] [对] 在串的链式存储结构中，结点大小与存储密度之间没有关系。 3.5 [判断] [对] 在C语言中，用动态分配函数进行管理的自由存储区称为“堆”。 《数据结构》第05章在线测试

《数据结构》第05章在线测试 剩余时间：4 6:14 答题须知：1、本卷满分20分。 2、答完题后，请一定要单击下面的“交卷”按钮交卷，否则无法记录本试卷的成绩。 3、在交卷之前，不要刷新本网页，否则你的答题结果将会被清空。 第一题、单项选择题（每题1分，5道题共5分） 1、深度为5的满二叉树有＿＿＿＿＿＿＿＿个结点。 A、16 C、31 B、32 D、10 2、在线索化二叉树中，t所指结点没有左子树的充要条件是＿＿＿＿＿＿＿＿。 A、t-＞lchild＝＝NULL

C、t-＞LTag＝＝1 && t-＞lchild＝＝NULL

B、t-＞LTag＝＝1 D、以上都不对

3、树最适合表示＿＿＿＿＿＿＿＿。

A、有序数据元素

C、元素之间具有分支层次关系的数据

B、无序数据元素 D、元素之间无联系的数据

4、具有100个结点的完全二叉树的深度为＿＿＿＿＿＿＿＿。

A、6 C、8

B、7 D、9

5、对于表达式(a-b+c)*d/(e+f),其前缀表达式为＿＿＿＿＿＿＿＿。

A、/*+-abcd+ef C、/*-a+bcd+ef

B、a-b+c*d/e+f D、ab-c+d*ef+/

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

1、下列关于完全二叉树的叙述中，正确的有＿＿＿＿＿＿＿＿。

A、完全二叉树一定是满二叉树 B、满二叉树一定是完全二叉树

C、完全二叉树中要么没有结点的度为1，要么只可能有一个结点的度为1 D、只有一个结点的度为1的二叉树一定是完全二叉树

2、下列关于树和二叉树的叙述中，正确的有＿＿＿＿＿＿＿＿。

A、森林和二叉树之间可以相互转换 B、树和二叉树之间可以相互转换

C、二叉树的子树有左右之分，而树的子树没有左右之分 D、二叉树结点的最大度数为2，而树的结点的最大度数没有限制

3、树可采用的存储结构有＿＿＿＿＿＿＿＿。

A、顺序结构 B、多重链表

C、二叉链表 D、孩子链表

4、用二叉树的＿＿＿＿＿＿＿＿序列可唯一的确定一棵二叉树。

A、先序和中序 B、先序和后序 C、后序和中序 D、层序和中序

5、树可采用的存储结构有＿＿＿＿＿＿＿＿。

A、顺序结构 B、多重链表 C、二叉链表 D、孩子链表

第三题、判断题（每题1分，5道题共5分）

1、二叉树的先、中、后序遍历序列中，叶子结点的相对顺序不会发生改变。

正确

错误

2、将一棵树转换成相应的二叉树后，二叉树的根结点肯定没有左子树。

正确

错误

3、用树的先序遍历和中序遍历序列可以导出树的后序遍历。

正确

错误

4、在一棵非空二叉树的中序遍历序列中，根结点的右边只有其右子树上的所有结点。

正确

错误

5、二叉树的先序遍历序列中，任意一个结点均处在其孩子结点的前面。

正确

错误

测试结果如下：

? ?

1.1 [单选] [对] 深度为5的满二叉树有＿＿＿＿＿＿＿＿个结点。

1.2 [单选] [对] 在线索化二叉树中，t所指结点没有左子树的充要条件是＿＿＿＿＿＿＿＿。

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

1.3 [单选] [对] 树最适合表示＿＿＿＿＿＿＿＿。

1.4 [单选] [对] 具有100个结点的完全二叉树的深度为＿＿＿＿＿＿＿＿。

1.5 [单选] [错] 对于表达式(a-b+c)*d/(e+f),其前缀表达式为＿＿＿＿＿＿＿＿。

2.1 [多选] [错] 下列关于完全二叉树的叙述中，正确的有＿＿＿＿＿＿＿＿。 2.2 [多选] [对] 下列关于树和二叉树的叙述中，正确的有＿＿＿＿＿＿＿＿。 2.3 [多选] [对] 树可采用的存储结构有＿＿＿＿＿＿＿＿。

2.4 [多选] [对] 用二叉树的＿＿＿＿＿＿＿＿序列可唯一的确定一棵二叉树。 2.5 [多选] [对] 树可采用的存储结构有＿＿＿＿＿＿＿＿。

3.1 [判断] [对] 二叉树的先、中、后序遍历序列中，叶子结点的相对顺序不会发生改变。

3.2 [判断] [对] 将一棵树转换成相应的二叉树后，二叉树的根结点肯定没有左子树。

3.3 [判断] [对] 用树的先序遍历和中序遍历序列可以导出树的后序遍历。

3.4 [判断] [错] 在一棵非空二叉树的中序遍历序列中，根结点的右边只有其右子树上的所有结点。

3.5 [判断] [对] 二叉树的先序遍历序列中，任意一个结点均处在其孩子结点的前面。

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

《数据结构》第06章在线测试 剩余时间：4 8:56 答题须知：1、本卷满分20分。 2、答完题后，请一定要单击下面的“交卷”按钮交卷，否则无法记录本试卷的成绩。 3、在交卷之前，不要刷新本网页，否则你的答题结果将会被清空。 第一题、单项选择题（每题1分，5道题共5分） 1、一个有n个顶点的无向图若是连通图，则至少有＿＿＿＿＿＿＿＿条边。 A、n-1 C、n+1 B、n D、(n+1)/2 2、无向图的邻接矩阵是一个＿＿＿＿＿＿＿＿。 A、对称矩阵 C、对角矩阵 B、零矩阵 D、上三角矩阵 3、图的深度优先遍历算法类似于二叉树的＿＿＿＿＿＿＿＿。 A、先序遍历 C、后序遍历 B、中序遍历 D、层序遍历 4、如果从无向图的任意顶点出发进行一次深度优先遍历就能访问到图中所有顶点，则该图一定是＿＿＿＿＿＿＿＿。

A、完全图 C、有回路

B、连通图 D、一棵树

5、对＿＿＿＿＿＿＿＿，用Prim算法求最小生成树较为合适。

A、非连通图 C、稀疏图

B、连通图 D、稠密图

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

1、如果对无向图G必须进行二次广度优先遍历才能访问到图中所有顶点，则下列说法中正确的是＿＿＿＿＿＿＿＿。

A、G肯定不是完全图 B、G肯定不是连通图 C、G中一定有回路 D、G有两个连通分量

2、在拓扑排序中，拓扑序列的第一个顶点一定是＿＿＿＿＿＿＿＿的顶点。

A、入度为0 B、没有前驱 C、出度为0 D、没有后继

3、对图分别进行深度优先遍历和广度优先遍历，得到的顶点访问序列＿＿＿＿＿＿＿＿。

A、一定相同 B、一定不同 C、不一定相同 D、可能相同

4、下列关于最短路径的说法中，正确的有＿＿＿＿＿＿＿＿。

A、Dijkstra算法是按路径长度递增的顺序依次产生从某一固定源点到其他各顶点之间的最短路径。 B、若仅求单一源点到某一特定顶点之间的最短路径，则其算法的时间复杂度可以达到O(n)。

C、求图中每一对顶点间最短路径的Floyd算法的时间复杂度为O(n^3)。 D、求图中每一对顶点间的最短路径也可用Dijkstra算法实现。 5、已知一个无向图的邻接矩阵表示，计算第i个顶点的度的方法是＿＿＿＿＿＿。 A、计算邻接矩阵中第i行的元素之和 B、计算邻接矩阵中第i列的元素之和 C、计算邻接矩阵中第i行的非零元个数 D、计算邻接矩阵中第i列的非零元个数 第三题、判断题（每题1分，5道题共5分） 1、若从无向图的一个顶点出发进行广度优先遍历可访问到图中的所有顶点，则该图一定是连通图。 正确 错误 2、在n个顶点的无向图中，若边数大于n-1，则该图一定是连通图。 正确 错误 3、对稀疏图，用Prim算法求最小生成树较为合适 正确 错误 4、利用拓扑排序，可检测一个有向图中是否存在环 正确 错误 5、若从无向图的一个顶点出发进行深度优先遍历可访问到图中的所有顶点，则该图一定是连通图。 正确 错误

测试结果如下：

? ? ? ? ? ? ?

1.1 [单选] [对] 一个有n个顶点的无向图若是连通图，则至少有＿＿＿＿＿＿＿＿条边。

1.2 [单选] [对] 无向图的邻接矩阵是一个＿＿＿＿＿＿＿＿。

1.3 [单选] [对] 图的深度优先遍历算法类似于二叉树的＿＿＿＿＿＿＿＿。 1.4 [单选] [对] 如果从无向图的任意顶点出发进行一次深度优先遍历就能访问到图中所有顶点，则该图一定是＿＿＿＿＿＿＿＿。

1.5 [单选] [对] 对＿＿＿＿＿＿＿＿，用Prim算法求最小生成树较为合适。 2.1 [多选] [对] 如果对无向图G必须进行二次广度优先遍历才能访问到图中所有顶点，则下列说法中正确的是＿＿＿＿＿＿＿＿。

2.2 [多选] [对] 在拓扑排序中，拓扑序列的第一个顶点一定是＿＿＿＿＿＿＿＿的顶点。

? ? ? ? ? ? ? ?

2.3 [多选] [对] 对图分别进行深度优先遍历和广度优先遍历，得到的顶点访问序列＿＿＿＿＿＿＿＿。

2.4 [多选] [对] 下列关于最短路径的说法中，正确的有＿＿＿＿＿＿＿＿。 2.5 [多选] [对] 已知一个无向图的邻接矩阵表示，计算第i个顶点的度的方法是＿＿＿＿＿＿。

3.1 [判断] [对] 若从无向图的一个顶点出发进行广度优先遍历可访问到图中的所有顶点，则该图一定是连通图。

3.2 [判断] [对] 在n个顶点的无向图中，若边数大于n-1，则该图一定是连通图。

3.3 [判断] [对] 对稀疏图，用Prim算法求最小生成树较为合适 3.4 [判断] [对] 利用拓扑排序，可检测一个有向图中是否存在环

3.5 [判断] [对] 若从无向图的一个顶点出发进行深度优先遍历可访问到图中的所有顶点，则该图一定是连通图。

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

《数据结构》第07章在线测试 剩余时间：4 9:55 答题须知：1、本卷满分20分。 2、答完题后，请一定要单击下面的“交卷”按钮交卷，否则无法记录本试卷的成绩。 3、在交卷之前，不要刷新本网页，否则你的答题结果将会被清空。 第一题、单项选择题（每题1分，5道题共5分） 1、＿＿＿＿＿＿＿二叉排序树可得到一个关键字的有序序列。 A、先序遍历 C、后序遍 B、中序遍历 D、层序遍历 2、用折半查找对长度为12的有序表进行查找，则等概率下查找成功时的平均查找长度为＿＿＿＿＿＿＿。 A、35/12 C、39/12 B、37/12 D、43/12 3、用链地址法处理冲突构造的散列表中，每个地址单元所链接的同义词表的＿＿＿＿＿＿＿相同。 A、关键字 C、散列地址 B、元素值 D、含义 4、如果要求一个线性表既能较快的查找，又能适应动态变化的要求，可以采用＿＿＿＿＿＿＿查找方法。 A、折半 C、分块 B、顺序 D、散列 5、高度为5的二叉平衡树至少有＿＿＿＿＿＿＿个结点。 A、10 C、15

B、12 D、17

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

1、平衡二叉树上结点的平衡因子可以为＿＿＿＿＿＿＿。

A、-2 B、-1 C、0 D、1 E、2

2、构造散列函数时通常考虑的因素有＿＿＿＿＿＿＿。

A、计算函数的工作量 B、关键字的长度 C、散列表长 D、关键字的分布情况

3、构造散列表时解决冲突常用的方法有＿＿＿＿＿＿＿。

A、链地址法 B、数字分析法 C、开放定址法 D、平方取中法 E、再哈希法 F、求余法 G、建立公共溢出区

4、对于10个元素的有序表进行折半查找，须比较3次方可查找成功的元素在表中的位置有＿＿＿＿＿＿＿。

A、1

B、2 C、3 D、4 E、6 F、7 G、8 H、9

5、在顺序表的顺序查找算法中，监视哨的位置＿＿＿＿＿＿＿。

A、只能在表头 B、只能在表尾 C、可以在表头 D、可以在表尾

第三题、判断题（每题1分，5道题共5分） 1、折半查找和二叉排序树查找的时间性能相同。

正确

错误

2、在散列函数H(key)＝key mod p中，函数的好坏与p的选择没有任何关系。

正确

错误

3、平衡二叉树是指左、右子树的高度差的绝对值不大于1的二叉树。

正确

错误

4、在分块查找中，对索引表的查找既可用顺序查找法，也可用折半查找法。

正确

错误

5、若散列表的装填因子小于1，则可避免冲突的产生

正确

错误

测试结果如下：

?

1.1 [单选] [对] ＿＿＿＿＿＿＿二叉排序树可得到一个关键字的有序序列。

? ? ? ? ? ? ? ? ? ? ? ? ? ? 1.2 [单选] [对] 用折半查找对长度为12的有序表进行查找，则等概率下查找成功时的平均查找长度为＿＿＿＿＿＿＿。

1.3 [单选] [对] 用链地址法处理冲突构造的散列表中，每个地址单元所链接的同义词表的＿＿＿＿＿＿＿相同。

1.4 [单选] [对] 如果要求一个线性表既能较快的查找，又能适应动态变化的要求，可以采用＿＿＿＿＿＿＿查找方法。

1.5 [单选] [对] 高度为5的二叉平衡树至少有＿＿＿＿＿＿＿个结点。 2.1 [多选] [对] 平衡二叉树上结点的平衡因子可以为＿＿＿＿＿＿＿。 2.2 [多选] [对] 构造散列函数时通常考虑的因素有＿＿＿＿＿＿＿。 2.3 [多选] [对] 构造散列表时解决冲突常用的方法有＿＿＿＿＿＿＿。 2.4 [多选] [对] 对于10个元素的有序表进行折半查找，须比较3次方可查找成功的元素在表中的位置有＿＿＿＿＿＿＿。

2.5 [多选] [对] 在顺序表的顺序查找算法中，监视哨的位置＿＿＿＿＿＿＿。 3.1 [判断] [对] 折半查找和二叉排序树查找的时间性能相同。

3.2 [判断] [对] 在散列函数H(key)＝key mod p中，函数的好坏与p的选择没有任何关系。

3.3 [判断] [对] 平衡二叉树是指左、右子树的高度差的绝对值不大于1的二叉树。

3.4 [判断] [对] 在分块查找中，对索引表的查找既可用顺序查找法，也可用折半查找法。

3.5 [判断] [对] 若散列表的装填因子小于1，则可避免冲突的产生

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

《数据结构》第08章在线测试 剩余时间：5 6:05 答题须知：1、本卷满分20分。 2、答完题后，请一定要单击下面的“交卷”按钮交卷，否则无法记录本试卷的成绩。 3、在交卷之前，不要刷新本网页，否则你的答题结果将会被清空。 第一题、单项选择题（每题1分，5道题共5分） 1、下列方法中，＿＿＿＿＿＿＿＿是稳定的排序方法。 A、折半插入排序 C、快速排序 B、希尔排序 D、堆排序 2、在待排序的元素序列基本有序的前提下，效率最高的排序方法是＿＿＿＿＿＿＿。 A、直接插入排序 C、快速排序 B、起泡排序 D、堆排序 3、一组记录的关键字序列为{46，79，56，38，40，84}，则利用快速排序方法，以第一个记录为枢轴得到的一次划分结果是＿＿＿＿＿＿＿。 A、{38，40，46，56，79，84} C、{40，38，46，56，79，84}

B、{40，38，46，79，56，84} D、{40，38，46，84，56，79}

4、在下列排序方法中，平均情况下占用内存量最大的是＿＿＿＿＿＿＿方法。

A、快速排序 C、冒泡排序

B、插入排序 D、堆排序

5、对n个记录的序列进行堆排序，最坏情况下的时间复杂度为＿＿＿＿＿＿。

A、O(logn) C、O(n)

B、O(nlogn) D、O(n^2)

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

1、下列方法中，＿＿＿＿＿＿＿＿算法的时间复杂度为O(nlogn)。

A、希尔排序 B、堆排序 C、快速排序 D、简单选择排序 E、直接插入排序

2、下列序列中，＿＿＿＿＿＿＿＿是堆。

A、{15,30,22,93,52,71} B、{15,22,30,52,71,93} C、{15,52,22,93,30,71} D、{15,52,22,71,30,93}

3、在下列排序方法中，每一趟排序结束后都能选出一个元素放在其最终位置上的是＿＿＿＿＿＿＿。

A、简单选择排序 B、起泡排序 C、快速排序

D、直接插入排序 E、堆排序

4、下列排序方法中，在最坏情况下算法的时间复杂度为O(n^2)的有＿＿＿＿＿＿＿＿。

A、堆排序 B、快速排序 C、希尔排序 D、冒泡排序

5、下列序列中，＿＿＿＿＿＿＿＿不是堆。

A、{96,83,27,38,11,9} B、{12,36,24,85,47,30,53,91} C、{49,38,65,97,76,13,27} D、{38，24，15，20，30，46}

第三题、判断题（每题1分，5道题共5分） 1、在一个大顶堆中，最小元素不一定在最后。

正确

错误

2、对一个堆按层次遍历，一定能得到一个有序序列。

正确

错误

3、在数据表基本有序时，冒泡排序方法的时间复杂度一定接近O(n)。

正确

错误

4、由于希尔排序的最后一趟与直接插入排序过程相同，所以前者一定比后者花费的时间多。

正确

错误

5、快速排序算法在每趟排序结束时都能找到一个元素放到其最终位置上。

正确

错误

测试结果如下：

? ?

1.1 [单选] [对] 下列方法中，＿＿＿＿＿＿＿＿是稳定的排序方法。

1.2 [单选] [对] 在待排序的元素序列基本有序的前提下，效率最高的排序方法是＿＿＿＿＿＿＿。

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

1.3 [单选] [对] 一组记录的关键字序列为{46，79，56，38，40，84}，则利用快速排序方法，以第一个记录为枢轴得到的一次划分结果是＿＿＿＿＿＿＿。

1.4 [单选] [对] 在下列排序方法中，平均情况下占用内存量最大的是＿＿＿＿＿＿＿方法。

1.5 [单选] [对] 对n个记录的序列进行堆排序，最坏情况下的时间复杂度为＿＿＿＿＿＿。

2.1 [多选] [对] 下列方法中，＿＿＿＿＿＿＿＿算法的时间复杂度为O(nlogn)。

2.2 [多选] [对] 下列序列中，＿＿＿＿＿＿＿＿是堆。

2.3 [多选] [对] 在下列排序方法中，每一趟排序结束后都能选出一个元素放在其最终位置上的是＿＿＿＿＿＿＿。

2.4 [多选] [对] 下列排序方法中，在最坏情况下算法的时间复杂度为O(n^2)的有＿＿＿＿＿＿＿＿。

2.5 [多选] [对] 下列序列中，＿＿＿＿＿＿＿＿不是堆。 3.1 [判断] [对] 在一个大顶堆中，最小元素不一定在最后。

3.2 [判断] [对] 对一个堆按层次遍历，一定能得到一个有序序列。

3.3 [判断] [对] 在数据表基本有序时，冒泡排序方法的时间复杂度一定接近O(n)。

3.4 [判断] [对] 由于希尔排序的最后一趟与直接插入排序过程相同，所以前者一定比后者花费的时间多。

3.5 [判断] [对] 快速排序算法在每趟排序结束时都能找到一个元素放到其最终位置上。

本文来源：https://www.bwwdw.com/article/rxbr.html