第一周 绪论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、编程实现查找线性表（0，1，2，......，n-1）中第i（1≤i≤n）个元素的直接前驱，并输出值。要求在顺序表上实现。
第三周 栈和队列
第三周单元测验
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、设长度为n的链队采用但循环链表加以表示，若只设一个头指针指向队首元素，则入队操作的时间复杂度为（ ）。
a、a.o(1)
b、b.o(n)
c、c.o(log)
d、d.o()
7、在顺序栈中，若栈顶指针top指向栈顶元素的下一个存储单元，且顺序栈的最大容量是maxsize，则顺序栈的判空条件是（ ）
a、a.top==0
b、b.top==-1
c、top==maxsize
d、top==maxsize-1
8、栈与队列是限制存取点的线性结构。
9、对不含相同元素的同一输入序列进行两组不同的、合法的入栈和出栈组合操作，所得的输出序列一定相同。
10、设栈采用顺序存储，若已有i-1个元素入栈，则将第i个元素入栈时，入栈算法的时间复杂度为o(i)。
11、在链队列中，即使不设置尾指针，也能进行入队操作。
12、循环顺序队列和循环链队列都存在空间一处问题。
第三周单元作业
1、编写算法，借助栈将一个带都节点的单链表逆置。
2、n个人站成一排，从左向右的编号分别为1n，现从左往右报数“1，2，1，2，”，数到“1”的人出列，数到“2”的立即站到队伍的最右端，报数过程反复进行，直到n个人都出列，请给出他们出列顺序。
第四周 字符串、数组和广义表
第四周单元测试
1、下面关于串的叙述中，哪一个是不正确的？（ ）
a、串是字符的有限序列
b、空串是由空格构成的串
c、模式匹配是串的一种重要运算
d、串既可以采用顺序存储，也可以采用链式存储
2、串的长度是指( )
a、串中包含的字符个数
b、串中包含的不同字符个数
c、串中除空格以外的字符个数
d、串中包含的不同字母个数
3、设有两个串p和q，其中q是p的子串，求q在p中首次出现的位置的算法称为（ ）
a、求子串
b、联接
c、模式匹配
d、求串长
4、设主串的长度为n，模式串的长度为m，则串匹配的kmp算法时间复杂度是( )。
a、o(m)
b、o(n)
c、o(n m)
d、o(n×m)
5、串也是一种线性表，只不过( )。
a、数据元素均为字符
b、数据元素是子串
c、数据元素数据类型不受限制
d、表长受到限制
6、设有一个10阶的对称矩阵a，采用压缩存储方式，以行序为主进行存储，a11为第一元素，其存储地址为1，每个元素占一个地址空间，则a85的地址为（ ）。
a、13
b、33
c、18
d、40
7、有一个二维数组a[1..6, 0..7] ，每个数组元素用相邻的6个字节存储，存储器按字节编址，那么这个数组占用的存储空间大小是（ ）个字节。
a、48
b、96
c、252
d、288
8、设有数组a[1..8,1..10]，数组的每个元素占3字节，数组从内存首地址ba开始以列序为主序顺序存放，则数组元素 a[5，8]的存储首地址为( )。
a、ba 141
b、ba 180
c、ba 222
d、ba 225
9、稀疏矩阵的三元组存储表示方法( )。
a、实现转置操作很简单，只需将每个三元组中行下标和列下标交换即可
b、矩阵的非零元素个数和位置在操作过程中变化不大时较有效
c、是一种链式存储方法
d、比十字链表更高效
10、用十字链表表示一个稀疏矩阵，每个非零元素一般用一个含有( )域的结点表示。
a、5
b、4
c、3
d、2
11、一个串的任意连续字符组成的子序列称为串的 ，该串称为 。（答案用空格隔开）
12、串长度为0的串称为 ，只包含空格的串称为 。
13、若两个串的长度相等且对应位置上的字符也相等，则称两个串 。
14、寻找子串在主串中的位置，称为 。其中，子串又称为 。
15、模式串t="ababaab"的next[]数组值为 。
16、设数组a[1..5,1..6]的基地址为1000，每个元素占5个存储单元，若以行序为主序顺序存储，则元素a[5,5]的存储地址为 。
17、在稀疏矩阵的三元组顺序表存储结构中，除表示非零元的三元组表以外，还需要表示矩阵的行数、列数和 。
第四周单元作业
1、将关键字序列（7、8、30、11、18、9、14）散列存储到散列表中。散列表的存储空间是一个下标从0开始的一维数组，散列函数为： h(key) = (keyx3) mod 7，处理冲突采用线性探测再散列法，要求装填（载）因子为0.7。 (1) 请画出所构造的散列表。 (2) 分别计算等概率情况下查找成功和查找不成功的平均查找长度。
第五周 树和二叉树（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、完全二叉树的存储结构通常采用顺序存储结构（ ）。
第五周单元作业
1、从概念上讲，树，森林和二叉树是三种不同的数据结构，将树，森林转化为二叉树的基本目的是什么，并指出树和二叉树的主要区别。
2、二叉树采用二叉链表存储，编写计算整个二叉树高度的算法。
第六周 树和二叉树（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、已知一棵二叉树的中序序列和后序序列分别为gldhbeiacjfk和lghdiebjkfca （1）给出这颗二叉树；（2）转换为对应的森林。
2、设有正文aadbaacaccdacacaad，字符集为a，b，c，d，设计一套二进制编码，使得上述正文的编码最短。
第七周 图（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、一个无向连通图的生成树是含有该连通图的全部顶点的极大连通子图。（ ）
第七周单元作业
1、请分别用prim算法和kruskal算法构造以下网络的最小生成树，并求出该树的代价。
2、写出邻接矩阵表示的图从顶点a出发的深度优先遍历序列和广度优先遍历序列。
第八周 图（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()
第八周单元作业
1、拓扑排序的结果不是唯一的，试写出下图任意2个不同的拓扑序列。
2、给定带权有向图g和源点v1,利用迪杰斯特拉（dijkstra）算法求从v1到其余各顶点的最短路径。
猜你喜欢
- 2022-12-05 21:51
- 2022-12-05 21:23
- 2022-12-05 21:17
- 2022-12-05 21:11
- 2022-12-05 20:58尔雅教育学精讲3-超星尔雅-学习通-题库零氪题库
- 2022-12-05 20:37
- 2022-12-05 20:32
- 2022-12-05 20:30
- 2022-12-05 19:40
- 2022-12-05 19:19