大连理工大学大工14春《数据结构》在线作业1数据结构

一、单选题

1.  在一个长度为n的线性表中，删除值为x的元素时需要比较元素和移动元素的总次数为（ ）。

A. (n+1)/2

B. n/2

C. n

D. n+1

2.  一个递归算法必须包括（ ）。

A. 递归部分

B. 终止条件和递归部分

C. 迭代部分

D. 终止条件和迭代部分

3.  广义表((e))的表头是()。

A. e

B. (e)

C. ()

D. (())

4.  若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（ ）存储方式最节省时间。

A. 顺序表

B. 双链表

C. 带头结点的双循环链表

D. 单循环链表

5.  队列操作应遵循的原则是( )。

A. 先进先出

B. 后进先出

C. 先进后出

D. 随意进出

6.  数据结构是一门研究非数值计算的程序设计问题中计算机的数据元素以及它们之间的( )和运算等的学科。

A. 结构

B. 关系

C. 运算

D. 算法

7.  一个栈的输入序列为123…n，若输出序列的第一个元素是n，输出第i（1<=i<=n）个元素是（ ）。

A. 不确定

B. n-i+1

C. i

D. n-i

8.  在表长为n的顺序表中,若在每个位置插入数据元素的概率相等，插入一个数据元素平均需要移动（）个数据元素。

A. (n-1)/2

B. n/2

C. n-1

D. n

9.  广义表L=（a，（b，c）），进行Tail（L）操作后的结果为（ ）。

A. c

B. b，c

C. （b，c）

D. （（b，c））

10.  计算机内部数据处理的基本单位是（ ）。

A. 数据

B. 数据元素

C. 数据项

D. 数据库

二、判断题

1.  算法的时间复杂度不仅仅依赖于问题的规模，也取决于输入实例的初始状态。

A. 错误

B. 正确

2.  中缀表达式A-(B+C/D)*E的后缀形式是ABCD/+E*-。（ ）

A. 错误

B. 正确

3.  单链表从任意结点出发都能访问到所有结点。

A. 错误

B. 正确

4.  算法是对解题方法和步骤的描述。

A. 错误

B. 正确

5.  顺序表的长度是表中的数据元素个数。

A. 错误

B. 正确

6.  若n阶方阵的对角线右上方的元素均等于零，称为下三角矩阵。（ ）

A. 错误

B. 正确

7.  插入和删除只能在表的一端进行的线性表，称为栈。

A. 错误

B. 正确

8.  顺序表中存取每一个元素的时间不同。

A. 错误

B. 正确

9.  若n阶方阵的对角线右上方的元素均等于零，称为上三角矩阵。

A. 错误

B. 正确

10.  一个三元组表可用于表示一个稀疏矩阵。

A. 错误

B. 正确

大连理工大学大工14春《数据结构》在线作业2数据结构

一、单选题

1.  已知某二叉树的后序遍历序列是dabec, 中序遍历序列是debac , 它的前序遍历是（ ）。

A. acbed

B. decab

C. deabc

D. cedba

2.  在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的（ ）倍。

A. 1/2

B. 1

C. 2

D. 4

3.  采用邻接表存储的图的深度优先遍历算法类似于树的( )。

A. 先序遍历

B. 中序遍历

C. 后序遍历

D. 按层遍历

4.  每棵树都能惟一地转换成对应的二叉树，由树转换的二叉树中，一个结点N的右孩子是它在原树对应结点的（）。

A. 最左孩子

B. 最右孩子

C. 右邻兄弟

D. 左邻兄弟

5.  在完全二叉树中，若一个结点是叶结点，则它没（ ）。

A. 左子结点

B. 右子结点

C. 左子结点和右子结点

D. 左子结点，右子结点和兄弟结点

6.  concat(s,t)表示连接运算。将串t连接在串s之后，形成新的串s。若s="he",t="llo",则concat(s,t)之后，s="( )"。

A. hello

B. helo

C. hllo

D. hell

7.  设无向图的顶点个数为n，则该图最多有（ ）条边。

A. n-1

B. n(n-1)/2

C. n(n+1)/2

D. 0

8.  若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（ ）

A. 9

B. 11

C. 15

D. 不确定

9.  在一个具有n个顶点和e条边的无向图的邻接表中，边结点的个数为（）。

A. n

B. ne

C. e

D. 2e

10.  设高度为h的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的结点数至少为（ ），设根结点的高度为1。

A. 2h

B. 2h-1

C. 2h+1

D. h+1

二、判断题

1.  空串是任意串的子串。

A. 错误

B. 正确

2.  强连通图的各顶点间均可达。

A. 错误

B. 正确

3.  无向图的邻接矩阵一定是对称矩阵，有向图的邻接矩阵一定是非对称矩阵。

A. 错误

B. 正确

4.  设树根为第1层，在一棵二叉树上第5层的结点数最多为16。（ ）

A. 错误

B. 正确

5.  连通图的生成树不一定是惟一的。

A. 错误

B. 正确

6.  设树根为第1层，在一棵二叉树上第5层的结点数最多为16。

A. 错误

B. 正确

7.  在n个结点的无向图中，若边数大于n-1,则该图必是连通图。

A. 错误

B. 正确

8.  完全二叉树中，若一个结点没有左孩子，则它必是树叶。

A. 错误

B. 正确

9.  有n个顶点的无向图, 采用邻接矩阵表示, 图中的边数等于邻接矩阵中非零元素之和的一半。

A. 错误

B. 正确

10.  有向图的邻接矩阵一定是对称矩阵。

A. 错误

B. 正确

大连理工大学大工14春《数据结构》在线作业3数据结构

一、单选题

1.  对线性表用二分法查找时要求线性表必须是（）。

A. 顺序表

B. 单链表

C. 顺序存储的有序表

D. 散列表

2.  在排序算法中，每次从未排序的记录中挑出最小（或最大）关键码字的记录，加入到已排序记录的末尾，该排序方法是（ ）。

A. 选择

B. 冒泡

C. 插入

D. 堆

3.  哈希表的平均查找长度与（）无直接关系。

A. 哈希函数

B. 装填因子

C. 哈希表记录类型

D. 处理冲突的方法

4.  如果待排序中两个数据元素具有相同的值，在排序前后它们的相互位置发生颠倒，则称该排序算法是不稳定的，（）是不稳定的排序算法。

A. 起泡排序

B. 归并排序

C. 希尔排序

D. 直接插入排序

5.  散列表的地址区间为0-17,散列函数为H(K)=K mod 17。采用线性探测法处理冲突，并将关键字序列26，25，72，38，8，18，59依次存储到散列表中。存放元素59需要搜索的次数是（ ）。

A. 2

B. 3

C. 4

D. 5

6.  排序方法中，从未排序序列中依次取出元素与已排序序列（初始时为空）中的元素进行比较，将其放入已排序序列的正确位置上的方法，称为（）。

A. 插入排序

B. 冒泡排序

C. 希尔排序

D. 选择排序

7.  将10个元素散列到100000个单元的哈希表中，则（ ）产生冲突。

A. 一定会

B. 一定不会

C. 仍可能会

D. 以上都不对

8.  若要求排序是稳定的，且关键字为实数，则在下列排序方法中应选（ ）排序为宜。

A. 直接插入

B. 直接选择

C. 堆

D. 快速

9.  对线性表进行顺序查找时，要求线性表的存储结构是（）。

A. 倒排表

B. 索引表

C. 顺序表或链表

D. 散列表

10.  下面给出的四种排序法中( )排序法是不稳定性排序法。

A. 直接插入排序

B. 冒泡排序

C. 二路归并排序

D. 堆排序

二、判断题

1.  存储在磁带上的顺序文件的查找只能用顺序查找。

A. 错误

B. 正确

2.  用冒泡排序的方法对n个数据进行排序，第一趟共比较n-1对元素。

A. 错误

B. 正确

3.  顺序查找法适用于存储结构为顺序或链接存储的线性表。

A. 错误

B. 正确

4.  通常，磁带只适合于存储散列文件。

A. 错误

B. 正确

5.  在待排数据基本有序的情况下，快速排序效果最好。

A. 错误

B. 正确

6.  对无序表用二分法查找比顺序查找快。

A. 错误

B. 正确

7.  在执行某个排序过程中，出现排序码朝着最终位置相反方向移动，则该算法是不稳定的。

A. 错误

B. 正确

8.  排序的稳定性是指排序算法中的比较次数保持不变，且算法能够终止。

A. 错误

B. 正确

9.  直接选择排序属于选择类排序，是一种稳定的排序方法。

A. 错误

B. 正确

10.  文件是性质相同的记录的集合，文件通常存储在外存上。

A. 错误

B. 正确

大连理工大学大工14春《数据结构》在线作业1数据结构

一、单选题

1.  在一个长度为n的线性表中，删除值为x的元素时需要比较元素和移动元素的总次数为（ ）。

A. (n+1)/2

B. n/2

C. n

D. n+1

2.  一个递归算法必须包括（ ）。

A. 递归部分

B. 终止条件和递归部分

C. 迭代部分

D. 终止条件和迭代部分

3.  广义表((e))的表头是()。

A. e

B. (e)

C. ()

D. (())

4.  若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（ ）存储方式最节省时间。

A. 顺序表

B. 双链表

C. 带头结点的双循环链表

D. 单循环链表

5.  队列操作应遵循的原则是( )。

A. 先进先出

B. 后进先出

C. 先进后出

D. 随意进出

6.  数据结构是一门研究非数值计算的程序设计问题中计算机的数据元素以及它们之间的( )和运算等的学科。

A. 结构

B. 关系

C. 运算

D. 算法

7.  一个栈的输入序列为123…n，若输出序列的第一个元素是n，输出第i（1<=i<=n）个元素是（ ）。

A. 不确定

B. n-i+1

C. i

D. n-i

8.  在表长为n的顺序表中,若在每个位置插入数据元素的概率相等，插入一个数据元素平均需要移动（）个数据元素。

A. (n-1)/2

B. n/2

C. n-1

D. n

9.  广义表L=（a，（b，c）），进行Tail（L）操作后的结果为（ ）。

A. c

B. b，c

C. （b，c）

D. （（b，c））

10.  计算机内部数据处理的基本单位是（ ）。

A. 数据

B. 数据元素

C. 数据项

D. 数据库

二、判断题

1.  算法的时间复杂度不仅仅依赖于问题的规模，也取决于输入实例的初始状态。

A. 错误

B. 正确

2.  中缀表达式A-(B+C/D)*E的后缀形式是ABCD/+E*-。（ ）

A. 错误

B. 正确

3.  单链表从任意结点出发都能访问到所有结点。

A. 错误

B. 正确

4.  算法是对解题方法和步骤的描述。

A. 错误

B. 正确

5.  顺序表的长度是表中的数据元素个数。

A. 错误

B. 正确

6.  若n阶方阵的对角线右上方的元素均等于零，称为下三角矩阵。（ ）

A. 错误

B. 正确

7.  插入和删除只能在表的一端进行的线性表，称为栈。

A. 错误

B. 正确

8.  顺序表中存取每一个元素的时间不同。

A. 错误

B. 正确

9.  若n阶方阵的对角线右上方的元素均等于零，称为上三角矩阵。

A. 错误

B. 正确

10.  一个三元组表可用于表示一个稀疏矩阵。

A. 错误

B. 正确

大连理工大学大工14春《数据结构》在线作业2数据结构

一、单选题

1.  已知某二叉树的后序遍历序列是dabec, 中序遍历序列是debac , 它的前序遍历是（ ）。

A. acbed

B. decab

C. deabc

D. cedba

2.  在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的（ ）倍。

A. 1/2

B. 1

C. 2

D. 4

3.  采用邻接表存储的图的深度优先遍历算法类似于树的( )。

A. 先序遍历

B. 中序遍历

C. 后序遍历

D. 按层遍历

4.  每棵树都能惟一地转换成对应的二叉树，由树转换的二叉树中，一个结点N的右孩子是它在原树对应结点的（）。

A. 最左孩子

B. 最右孩子

C. 右邻兄弟

D. 左邻兄弟

5.  在完全二叉树中，若一个结点是叶结点，则它没（ ）。

A. 左子结点

B. 右子结点

C. 左子结点和右子结点

D. 左子结点，右子结点和兄弟结点

6.  concat(s,t)表示连接运算。将串t连接在串s之后，形成新的串s。若s="he",t="llo",则concat(s,t)之后，s="( )"。

A. hello

B. helo

C. hllo

D. hell

7.  设无向图的顶点个数为n，则该图最多有（ ）条边。

A. n-1

B. n(n-1)/2

C. n(n+1)/2

D. 0

8.  若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（ ）

A. 9

B. 11

C. 15

D. 不确定

9.  在一个具有n个顶点和e条边的无向图的邻接表中，边结点的个数为（）。

A. n

B. ne

C. e

D. 2e

10.  设高度为h的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的结点数至少为（ ），设根结点的高度为1。

A. 2h

B. 2h-1

C. 2h+1

D. h+1

二、判断题

1.  空串是任意串的子串。

A. 错误

B. 正确

2.  强连通图的各顶点间均可达。

A. 错误

B. 正确

3.  无向图的邻接矩阵一定是对称矩阵，有向图的邻接矩阵一定是非对称矩阵。

A. 错误

B. 正确

4.  设树根为第1层，在一棵二叉树上第5层的结点数最多为16。（ ）

A. 错误

B. 正确

5.  连通图的生成树不一定是惟一的。

A. 错误

B. 正确

6.  设树根为第1层，在一棵二叉树上第5层的结点数最多为16。

A. 错误

B. 正确

7.  在n个结点的无向图中，若边数大于n-1,则该图必是连通图。

A. 错误

B. 正确

8.  完全二叉树中，若一个结点没有左孩子，则它必是树叶。

A. 错误

B. 正确

9.  有n个顶点的无向图, 采用邻接矩阵表示, 图中的边数等于邻接矩阵中非零元素之和的一半。

A. 错误

B. 正确

10.  有向图的邻接矩阵一定是对称矩阵。

A. 错误

B. 正确

大连理工大学大工14春《数据结构》在线作业3数据结构

一、单选题

1.  对线性表用二分法查找时要求线性表必须是（）。

A. 顺序表

B. 单链表

C. 顺序存储的有序表

D. 散列表

2.  在排序算法中，每次从未排序的记录中挑出最小（或最大）关键码字的记录，加入到已排序记录的末尾，该排序方法是（ ）。

A. 选择

B. 冒泡

C. 插入

D. 堆

3.  哈希表的平均查找长度与（）无直接关系。

A. 哈希函数

B. 装填因子

C. 哈希表记录类型

D. 处理冲突的方法

4.  如果待排序中两个数据元素具有相同的值，在排序前后它们的相互位置发生颠倒，则称该排序算法是不稳定的，（）是不稳定的排序算法。

A. 起泡排序

B. 归并排序

C. 希尔排序

D. 直接插入排序

5.  散列表的地址区间为0-17,散列函数为H(K)=K mod 17。采用线性探测法处理冲突，并将关键字序列26，25，72，38，8，18，59依次存储到散列表中。存放元素59需要搜索的次数是（ ）。

A. 2

B. 3

C. 4

D. 5

6.  排序方法中，从未排序序列中依次取出元素与已排序序列（初始时为空）中的元素进行比较，将其放入已排序序列的正确位置上的方法，称为（）。

A. 插入排序

B. 冒泡排序

C. 希尔排序

D. 选择排序

7.  将10个元素散列到100000个单元的哈希表中，则（ ）产生冲突。

A. 一定会

B. 一定不会

C. 仍可能会

D. 以上都不对

8.  若要求排序是稳定的，且关键字为实数，则在下列排序方法中应选（ ）排序为宜。

A. 直接插入

B. 直接选择

C. 堆

D. 快速

9.  对线性表进行顺序查找时，要求线性表的存储结构是（）。

A. 倒排表

B. 索引表

C. 顺序表或链表

D. 散列表

10.  下面给出的四种排序法中( )排序法是不稳定性排序法。

A. 直接插入排序

B. 冒泡排序

C. 二路归并排序

D. 堆排序

二、判断题

1.  存储在磁带上的顺序文件的查找只能用顺序查找。

A. 错误

B. 正确

2.  用冒泡排序的方法对n个数据进行排序，第一趟共比较n-1对元素。

A. 错误

B. 正确

3.  顺序查找法适用于存储结构为顺序或链接存储的线性表。

A. 错误

B. 正确

4.  通常，磁带只适合于存储散列文件。

A. 错误

B. 正确

5.  在待排数据基本有序的情况下，快速排序效果最好。

A. 错误

B. 正确

6.  对无序表用二分法查找比顺序查找快。

A. 错误

B. 正确

7.  在执行某个排序过程中，出现排序码朝着最终位置相反方向移动，则该算法是不稳定的。

A. 错误

B. 正确

8.  排序的稳定性是指排序算法中的比较次数保持不变，且算法能够终止。

A. 错误

B. 正确

9.  直接选择排序属于选择类排序，是一种稳定的排序方法。

A. 错误

B. 正确

10.  文件是性质相同的记录的集合，文件通常存储在外存上。

A. 错误

B. 正确