第一周 绪论1.2 数据结构的基本概念随堂测验1、从逻辑结构上，可以把数据结构分为（ ）两大类。
a、动态结构、静态结构
b、顺序结构、链式结构
c、线性结构、非线性结构
d、逻辑结构、物理结构
2、存储数据时，通常不仅要存储各数据元素的值，而且还要存储（ ）。
a、数据的操作方法
b、数据元素的类型
c、数据元素之间的关系
d、数据的存储方法
3、在链式存储结构中，各结点间的存储单元的地址（ ）。
a、一定连续
b、一定不连续
c、不一定连续
d、部分连续，部分不连续
4、可以用（ ）来定义一个完整的数据结构。
a、数据元素
b、数据对象
c、数据关系
d、抽象数据类型
1.3 算法及算法描述随堂测验1、健壮的算法不会因为非法的输入数据而出现莫名其妙的状态。
2、算法必须有输出，但可以没有输入。
3、算法可以用不同的语言进行描述，当用计算机程序设计语言来描述算法时，则算法实际上就是程序。
1.4 算法分析随堂测验1、以下程序片段的时间复杂度是( )。 for (int i=1;i
=i 1;j--) x ;
a、o(n)
b、o()
c、o()
d、o()
2、空间复杂度也是一个算法好坏的标准之一，它所描述的是算法在运行过程中所占用的 的大小。
第一周 单元测验
1、计算机算法指的是（ ）。
a、计算方法
b、排序方法
c、检索方法
d、调度方法
e、解决问题的步骤序列
2、下列（ ）结构中的数据元素的关系是一对多的关系。
a、线性表
b、树
c、集合
d、栈与队列
3、算法的时间复杂度取决于（ ）。
a、问题的规模
b、待处理数据的状态
c、计算机系统的性能
d、a和b
4、在下面的程序段中，最后一行的语句频度在最坏情况下是（ ）。 for(i=n;i>1;i--) for(j=1;ja[j 1]) a[j]与a[j 1]对换；
a、o(n)
b、o(nn)
c、o()
d、o()
5、顺序存储设计时，各结点间的存储单元的地址（ ）。
a、一定连续
b、一定不连续
c、不一定连续
d、部分连续，部分不连续
6、数据元素时数据的最小单位。
7、数据的逻辑结构是指数据的各数据项之间的逻辑关系。
8、程序一定是算法。
9、算法的优劣与描述算法的语言无关，但与所用的计算机的性能有关。
10、健壮的算法不会因为非法的输入数据而出现莫名其妙的状态。
11、数据结构的设计最终为___________服务的
12、数据结构的课程主要讨论的内容是____________________，___________________________，_____________________________
第一周 单元作业
1、常见的逻辑结构有哪几种，各自的特点是什么？常见的存储结构有哪几种，各自的特点是什么？
2、试举一个数据结构的例子，叙述其逻辑结构、存储结构、运算这三方面的内容。
第二周 线性表
第二周 单元测验
1、线性表的顺序存储结构是一种（ ）。
a、随机存取的存储结构
b、顺序存取的存储结构
c、索引存取的存储结构
d、散列存取的存储结构
2、一个顺序表所占用的存储空间大小与（ ）无关。
a、表的长度
b、元素的存放顺序
c、元素的类型
d、元素中各字段的类型
3、在线性表中，若经常要存取第i个数据元素及其前趋，则宜采用（ ）存储方式。
a、顺序表
b、带头结点的单链表
c、不带头结点的单链表
d、循环单链表
4、在单链表中，增加一个头结点的目的是为了（ ）。
a、使单链表至少有一个结点
b、标识表结点中首结点的位置
c、方便运算的实现
d、说明单链表是线性表的链式存储结构
5、将长度为n的单链表链接在长度为m的单链表后面，其算法的时间复杂度为（ ）。
a、o(1)
b、o(n)
c、o(m)
d、o(m n)
6、在顺序表中逻辑上相邻的元素，其对应的物理位置也是相邻的。
7、在顺序表上进行插入、删除操作时需要移动元素的个数与待插入或待删除元素的位置无关。
8、单链表不是一种随机存取的存储结构。
9、一个循环链表可以由给定的头指针或尾指针来唯一标识。
10、所谓随机存取，就是通过首地址和元素的序号可以在o(1)的时间内找到指定的元素。
第二周 单元作业
1、编写算法：public void insert(sqlist l,int x)，实现在有序顺序表l中插入一个整数值为x的新元素，并使顺序表l仍然保持有序。
2、编写一个单链表类的成员函数，实现对带头结点的单链表就地逆置的操作。
第三周 栈和队列
第三周单元测验
1、将整数1、2、3、4依次进栈，则不可能得到的出栈序列是（ ）。
a、1234
b、1324
c、4321
d、1423
2、在链栈中，进行出栈操作时（ ）。
a、需要判断栈是否满
b、需要判断栈是否空
c、需要判断栈元素的类型
d、无须对栈作任何判断
3、若一个栈的输入序列是，，，，，其输出序列是1，2，3，，4，若=1，则的值（ ）。
a、可能是2
b、一定是2
c、不可能是2
d、不可能是3
4、在队列中存取数据元素的原则是（ ）。
a、先进先出
b、先进后出
c、后进后出
d、没有限制
5、已知循环队列存储在一维数组a[0n]中，且队列非空时front和rear分别指向队首元素和队尾元素。若初始队列为空，且要求第一个进入队列的元素存储在a[0]处，则初始时front和rear的值分别时（ ）。
a、0，0
b、0，n-1
c、n-1,0
d、n-1,n-1
6、栈与队列是限制存取点的线性结构。
7、对不含相同元素的同一输入序列进行两组不同的、合法的入栈和出栈组合操作，所得的输出序列一定相同。
8、设栈采用顺序存储，若已有i-1个元素入栈，则将第i个元素入栈时，入栈算法的时间复杂度为o(i)。
9、在链队列中，即使不设置尾指针，也能进行入队操作。
10、循环顺序队列和循环链队列都存在空间一处问题。
第三周单元作业
1、编写算法，借助栈将一个带都节点的单链表逆置。
2、n个人站成一排，从左向右的编号分别为1n，现从左往右报数“1，2，1，2，”，数到“1”的人出列，数到“2”的立即站到队伍的最右端，报数过程反复进行，直到n个人都出列，请给出他们出列顺序。
第五周 树和二叉树（1）
第五周单元测验
1、一棵具有 n个结点的完全二叉树的树高度（深度）是（ ）
a、ëlog2n û 1
b、log2n 1
c、ë log2n û
d、log2n-1
2、有关二叉树下列说法正确的是（ ）
a、二叉树的度为2
b、一棵二叉树的度可以小于2
c、二叉树中至少有一个结点的度为2
d、二叉树中任何一个结点的度都为2
3、由3 个结点可以构造出多少种不同的二叉树？（ d ）
a、2
b、3
c、4
d、5
4、若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（ ）
a、9
b、11
c、15
d、不确定
5、利用二叉链表存储树时，根结点的右指针是（ ）
a、指向最左孩子
b、指向最右孩子
c、空
d、非空
6、完全二叉树一定存在度为1的结点（ ）。
7、用二叉链表存储n个结点的二叉树时，结点的2n个指针中有n 1个空指针（ ）。
8、深度为k的二叉树中结点总数≤-1（ ）。
9、完全二叉树中，若一个结点没有左孩子，则它必是树叶（ ）。
10、完全二叉树的存储结构通常采用顺序存储结构（ ）。
第六周 树和二叉树（2）
第六周单元测验
1、引入二叉线索树的目的是（ ）
a、加快查找结点的前驱或后继的速度
b、为了能在二叉树中方便的进行插入与删除
c、为了能方便的找到双亲
d、使二叉树的遍历结果唯一
2、一棵非空的二叉树的先序遍历序列与后序遍历序列正好相反，则该二叉树一定满足（ ）
a、所有的结点均无左孩子
b、所有的结点均无右孩子
c、只有一个叶子结点
d、是任意一棵二叉树
3、已知一棵二叉树的后序遍历序列为dabec，中序遍历序列为debac，则它的先序遍历序列为（ ）
a、acbed
b、decab
c、deabc
d、cedba
4、若x是中序线索二叉树中一个有左孩子的结点，且x不为根，则x的前驱为（ ）
a、x的双亲
b、x的右子树中最左的结点
c、x的左子树中最右结点
d、x的左子树中最右叶结点
5、n个结点的线索二叉树上含有的线索数为（ ）
a、2n
b、n-1
c、n 1
d、n
6、由一棵二叉树的先序序列和后序序列可以唯一确定它（ ）
7、哈夫曼树是带权路径长度最短的树，路径上权值较大的结点离根较近（ ）
8、在中序线索二叉树中，每一非空的线索均指向其祖先结点（ ）
9、二叉树中序线索化后，不存在空指针域（ ）
10、二叉树的层次遍历需要栈结构的支持。
第七周 图（1）
第七周单元测验
1、设无向图的顶点个数为n，则该图最多有（ ）条边。
a、n-1
b、n(n-1)/2
c、n(n 1)/2
d、n2
2、连通分量指的是（ ）
a、无向图中的极小连通子图
b、无向图中的极大连通子图
c、有向图中的极小连通子图
d、有向图中的极大连通子图
3、有向图中一个顶点的度是该顶点的（ ）
a、入度
b、出度
c、入度与出度之和
d、（入度 出度）/2
4、有e条边的无向图，若用邻接表存储，表中有（ ）边结点。
a、e
b、2e
c、e-1
d、2(e-1)
5、实现图的广度优先搜索算法需使用的辅助数据结构为（ ）
a、栈
b、队列
c、二叉树
d、树
6、图的最小生成树是唯一的。（ ）
7、如果一个图有n个顶点和小于n-1 条边，则一定是非连通图。（ ）
8、用邻接矩阵表示图时，矩阵元素的个数与顶点个数相关，与边数无关。（ ）
9、假设一个有n个顶点和e条弧的有向图用邻接表表示，则删除与某个顶点vi相关的所有弧的时间复杂度是o(n*e) 。（ ）
10、一个无向连通图的生成树是含有该连通图的全部顶点的极大连通子图。（ ）
第八周 图（2）
第八周单元测验
1、关键路径是（ ）
a、aoe网中从源点到汇点的最长路径
b、aoe网中从源点到汇点的最短路径
c、aov网中从源点到汇点的最长路径
d、aov网中从源点到汇点的最短路径
2、下列关于aoe网的叙述中，不正确的是（ ）
a、关键活动不按期完成就会影响整个工程的完成时间
b、任何一个关键活动提前完成，那么整个工程将会提前完成
c、所有的关键活动提前完成，那么整个工程将会提前完成
d、某些关键活动提前完成，那么整个工程将会提前完成
3、单源最短路径算法的时间复杂度为（ ）
a、o(1)
b、o(n)
c、o()
d、o()
4、在aov网络中如果存在环，则拓扑排序不能完成。
5、floyd算法的时间复杂度为o()
猜你喜欢
- 2022-12-05 20:46
- 2022-12-05 20:39
- 2022-12-05 20:35
- 2022-12-05 20:22
- 2022-12-05 20:20
- 2022-12-05 20:06
- 2022-12-05 19:08
- 2022-12-05 19:06
- 2022-12-05 18:50
- 2022-12-05 18:43