四川大学“精品课程”
计算机科学与技术专业（本科）
《数据结构与算法分析》课程
考试说明与模拟试卷
第一部分考试说明
数据结构与算法分析》是计算机科学与技术专业统设的一门重要的必修专业基础课，它主要研究数据的各种逻辑结构和在计算机中的存储结构，还研究对数据进行的插入、查找、删除、排序、遍历等基本运算或操作以及这些运算在各种存储结构上具体实现的算法。由于本课程的主教材采用C++语言描述算法，期末卷面考试也采用C++语言描述，因而要求在做平时作业和上机实验操作时用C++开发工具（如：Visual C++或C++ Builder或Borland C++）。
下面按照主教材中各章次序给出每章的具体复习要求，以便同学们更好地进行期末复习。
第一章绪论
重点掌握的内容：
1. 数据结构的二元组表示，对应的图形表示，序偶和边之间的对应关系。
2. 集合结构、线性结构、树结构和图结构的特点。
3. 抽象数据类型的定义和表示方法。
4. 一维和二维数组中元素的按下标和按地址的访问方式以及相互转换，元素地址和数组地址的计算，元素占用存储空间大小和数组占用存储空间大小的计算。
5. 普通函数重载和操作符函数重载的含义，定义格式和调用格式。
6. 函数定义中值参数和引用参数的说明格式及作用，函数被调用执行时对传送来的实际参数的影响。
7. 算法的时间复杂度和空间复杂度的概念，计算方法，数量级表示。
8. 一个简单算法的最好、最差和平均这三种情况的时间复杂度的计算。
对于本章的其余内容均作一般掌握。
第二章线性表
重点掌握的内容：
1. 线性表的定义及判别和抽象数据类型的描述，线性表中每一种操作的功能，对应的函数名、返回值类型和参数表中每个参数的作用。
2. 线性表的顺序存储结构的类型定义，即List类型的定义和每个域的定义及作用。
3. 线性表的每一种运算在顺序存储结构上实现的算法，及相应的时间复杂度。
4.链接存储的概念，线性表的单链接和双链接存储的结构，向单链表中一个结点之
后插入新结点或从单链表中删除一个结点的后继结点的指针链接过程。
5. 单链表中结点的结构，每个域的定义及作用，即LNode类型的定义及结构。
6. 带表头附加结点的链表、循环链表、双向链表的结构特点。
7. 线性表的每一种运算在单链表上实现的算法及相应的时间复杂度。
8. 在顺序存储或链接存储的线性表上实现指定功能的算法的分析和设计。
9．Josephus问题的求解过程。
10．顺序表和线性链表的性能比较及各自使用背景。
对于本章的其余内容均作一般掌握。
第三章数组和广义表
重点掌握的内容：
1.多维数组的逻辑结构特征。
2. 多维数组的顺序存储结构及地址计算公式。
3．数组是一种随机存取结构的原因。
4．特殊矩阵和稀疏矩阵的概念。
5．特殊矩阵（包括对角矩阵）和压缩存储的下标变换方法及所需存储空间。
6. 稀疏矩阵的定义和三元组线性表及三列二维数组表示。
7. 稀疏矩阵的顺序存储、带行指针向量的链接存储，在每一种存储中非零元素结点的结构。
8. 稀疏矩阵的转置运算。
9. 广义表的定义和表示，广义表长度和深度的计算。
10．广义表上的求表头、表尾运算。
5. 广义表的链接存储结构中结点类型的定义，分别求广义表长度和深度的递归算法，它们对应的时间复杂度。
一般掌握的内容：
稀疏矩阵转置的算法描述。
对于本章的其余内容均作一般了解。
第四章栈和队列
重点掌握的内容：
1. 栈的定义和抽象数据类型的描述，栈中每一种操作的功能，对应的函数名、返回值类型和参数表中每个参数的作用。
2. 栈的顺序存储结构的类型定义，即Stack类型的定义和每个域的定义及作用。
3．栈的每一种运算在顺序存储结构上实现的算法，及相应的时间复杂度。
4. 栈的每一种运算在链接存储结构上实现的算法及相应的时间复杂度。
5. 算术表达式的中缀表示和后缀表示，以及相互转换的规则，后缀表达式求值的方法。
6．给定n个栈元素, 出栈可能或不可能的序列数。
7. 队列的定义和抽象数据类型的描述，队列中每一种操作的功能，对应的函数名、返回值类型和参数表中每个参数的作用。
8. 队列的顺序存储结构的类型定义，即Queue类型的定义和每个域的定义及作用。
9. 队列的每一种运算在顺序存储结构上实现的算法及相应的时间复杂度。
10. 利用栈和队列解决简单问题的算法分析和设计。
11．双端队的概念及可能出队序列。
12．队和栈的应用背景，如cpu队、进程队、打印机队。
13．链队的各种存储表示。
一般掌握的内容：
1. 后缀表达式求值的算法，把中缀表达式转换为后缀表达式的算法。
2. 队列的链接存储结构，以及实现每一种队列运算的算法和相应的时间复杂度。
对于本章的其余内容均作一般了解。
第五章字符串
重点掌握的内容：
1. 串的有关概念及基本运算。
2. 串与线性表的关系。
3．串的各种存储结构。
4．一个串中真子串和子串个数的确定。
一般掌握的内容：
1. 串上各种运算的实现及其时间性能分析。
2. 使用C++提供的操作函数构造与串相关的算法解决简单的应用问题。
第六章树和二叉树
重点掌握的内容：
1. 树和二叉树的定义，对于一棵具体树和二叉树的二元组表示及广义表表示。
2. 树和二叉树的概念，如结点的度、树的度、树叶、分枝结点、树的层数、树的深度等。
3．不同结点数的树和二叉树的形态。
4. 树和二叉树的性质，如已知树或二叉树的深度h可求出相应的最多结点数，已知结点数n可求出对应树或二叉树的最大和最小高度。
5. 二叉树中结点的编号规则和对应的顺序存储结构。
6. 二叉树的链接存储结构及存储结点的类型定义，即BTreeNode类型的定义和每个域的定义及作用。
7. 二叉树的先序、中序、后序、遍历的递归过程和递归算法，中序遍历的非递归算法，按层遍历的过程和算法，每种算法的时间复杂度。
8．二叉树的先序、中序、后序遍历序列，唯一确定一棵二叉树的原则。
9．算术表达式的二叉树表示及逆波兰表达式、中缀表示。
一般掌握的内容：
1. 普通树的链接存储结构，GTreeNode类型的定义和每个域的定义及作用。
2．普通树的先根、后根和按层遍历的过程及算法。
3. 在链接存储的二叉树上实现指定功能的算法分析和设计。
对于本章的其余内容均作一般了解。
二叉树的应用
重点掌握的内容：
1. 二叉搜索树的定义和性质、建立。
2. 二叉搜索树查找的递归算法和非递归算法，相应的时间复杂度，查找一个元素的查找长度，即从树根结点到该结点的路径上的结点数。
3. 二叉搜索树插入的递归算法和非递归算法，相应的时间复杂度，根据一组数据生成一棵二叉搜索树的过程。
4.堆的定义和顺序存储结构，小根堆和大根堆的异同及堆的判别、建立堆的过程。
5. 向堆中插入元素的过程、算法描述及时间复杂度。
6. 从堆中删除元素的过程、算法描述及时间复杂度。
7.哈夫曼树的定义，树的带权路径长度的计算，根据若干个叶子结点的权构造哈夫曼树的过程。
8．顺序二叉树及二叉链表表示二叉树。
9．已知关键字序列{22,16,38,89,56，16，79}，试构造平衡二叉树。
对本章的其余内容均作一般了解。
第七章图
重点掌握的内容：
1. 图的顶点集和边集的表示。
2. 图的一些概念的含义，如顶点、边、度、完全图、子图、路径、路径长度、连通图、权、网等。
3.图的邻接矩阵、邻接表、邻接多重表和十字链表四种存储结构及相应的空间复杂度。
4. 存储图使用的vexlist, adjmatrix, adjlist, edgenode, edgeset, edge等类型的定义及用途。
5. 图的深度优先和广度优先搜索遍历的过程。
6. 对分别用邻接矩阵和用邻接表表示的图进行深度优先搜索遍历的过程、算法描述以及相应的时间复杂度。
7. 对分别用邻接矩阵和用邻接表表示的图进行广度优先搜索遍历的过程、算法描述以及相应的时间复杂度。
8.图的生成树（若一个具有n个顶点，e条边的无向图是一个森林（n＞e），
则该森林中必有多少棵树。）、深度优先生成树和广度优先生成树、生成树的权、最
小生成树等的定义。
9.根据普里姆算法求图的最小生成树的过程。
10．根据克鲁斯卡尔算法求图的最小生成树的过程。
11. 图的拓扑序列和拓扑排序的概念，求图的拓扑序列的方法，对用邻接表表示的图进行拓扑排序的过程。
12．强连通图的最少边数。
一般掌握的内容：
1．根据普里姆算法求图的最小生成树的算法描述。
2．根据克鲁斯卡尔算法求图的最小生成树的算法描述。
3. 对用邻接表表示的图进行拓扑排序的和算法描述。
对本章的其余内容均作一般了解。
第八章查找
重点掌握的内容：
1. 在一维数组及单链表上进行顺序查找的过程、算法、成功及不成功的平均查找长度和时间复杂度。
2. 在一维数组上进行二分查找的过程、递归和非递归算法、平均查找长度和时间复杂度，二分查找一个给定值元素的查找长度（即查找路径上的元素数），二分查找对应的判定树的性质。
3. 散列存储的概念，散列函数、散列表、冲突、同义词、装填因子等术语的含义。
4. 利用除留余数法建立散列函数求元素散列地址的方法。
5. 利用开放定址法中的线性探查法处理冲突进行散列存储和查找的过程，利用链接法处理冲突进行散列存储和查找的过程。
6. 根据除留余数法构造散列函数，采用线性探查法或链接法处理冲突，把一组数据散列存储到散列表中，计算出一个给定值元素的查找长度和查找所有元素的平均查找长度。
7. B_树中每个结点的结构，树根结点或非树根结点中关键字的个数范围和子树的个数范围，B_的结构特性，从B_树上查找一个给定值元素的过程。
一般掌握的内容：
1. B_树查找算法。
2. 向B_树中插入元素的过程。
对本章的其余内容均作一般了解。
第九章排序
重点掌握的内容：
1. 直接插入、直接选择和冒泡排序的方法，排序过程及时间复杂度。
2. 在堆排序中建立初始堆的过程和利用堆排序的过程，对一个分支结点进行筛运算
的过程、算法及时间复杂度，整个堆排序的算法描述及时间复杂度。
3. 快速排序的方法，对一组数据的排序过程，对应的二叉搜索树，快速排序过程中划分的层数和递归排序区间的个数。
4. 递归排序的递归算法，它在平均情况下的时间和空间复杂度，在最坏情况下的时间和空间复杂度。
5. 二路归并排序的方法和对数据的排序过程，每趟排序前、后的有序表长度，二路归并排序的趟数、时间复杂度和空间复杂度。
6．各种排序方法的不同数据序的比较、最好、最坏、平均情况。
7．哪些排序不受初始数据的影响。
一般掌握的内容：
1. 每一种排序方法的稳定性。
2. 直接插入排序和直接选择排序的算法。
一般了解的内容：
1. 二路归并排序过程中涉及的每个算法描述。
2. 冒泡排序算法。
第十章文件
重点掌握的内容：
1. 文件的有关概念。
2. 文件的逻辑结构及其操作。
3. 索引文件的组织方式和特点。
4．索引文件的的查询和更新操作的基本思想。
5. 两种最常用的索引顺序文件(ISAM文件和VSAM文件) 的组织方式和特点。
6. 在ISAM文件和VSAM文件上查找和更新操作的基本思想。
7. 散列文件的组织方式和特点。
8. 散列文件的查询和更新操作的基本思想。
9. 多关键字文件和其它文件的差别。
10. 多重表文件和倒排文件组织方式和特点。
11. 多重表文件和倒排文件查询和更新操作的基本思想。
本章其它内容一般掌握
第二部分模拟试卷
模拟试题（一）
一、单项选择题（每小题2 分，共20分）
（1）以下数据结构中哪一个是线性结构？（）
A）有向图B）队列C）线索二叉树D）B树（2）在一个单链表HL中，若要在当前由指针p指向的结点后面插入一个由q指向的结点，则执行如下（）语句序列。
A）p=q; p->next=q; B）p->next=q; q->next=p;
C）p->next=q->next; p=q; D）q->next=p->next; p->next=q;
（3）（）不是队列的基本运算。
A）在队列第i个元素之后插入一个元素B）从队头删除一个元素
C）判断一个队列是否为空D）读取队头元素的值（4）字符A、B、C依次进入一个栈，按出栈的先后顺序组成不同的字符串，至多可以组成（）个不同的字符串。
A）14 B）5 C）6 D）8
（5）由权值分别为3,8,6,2的叶子生成一棵哈夫曼树，它的带权路径长度为（）。
A）11 B）35 C）19 D）53 以下6-8题基于下图：
（6）该二叉树结点的前序遍历的序列为（）。
A）E、G、F、A、C、D、B B）E、A、G、C、F、B、D
C）E、A、C、B、D、G、F D）E、G、A、C、D、F、B （7）该二叉树结点的中序遍历的序列为（）。
A）A、B、C、D、E、G、F B）E、A、G、C、F、B、D
C）E、A、C、B、D、G、F D）B、D、C、A、F、G、E （8）该二叉树的按层遍历的序列为（）。
A）E、G、F、A、C、D、B B）E、A、C、B、D、G、F
C）E、A、G、C、F、B、D D）E、G、A、C、D、F、B （9）下面关于图的存储的叙述中正确的是（）。
A）用邻接表法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关
B）用邻接表法存储图，占用的存储空间大小与图中边数和结点个数都有关
C）用邻接矩阵法存储图，占用的存储空间大小与图中结点个数和边数都有关
D）用邻接矩阵法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关
（10）设有关键码序列(q,g,m,z,a,n,p,x,h)，下面哪一个序列是从上述序列出发建堆的结果?（）
A）a,g,h,m,n,p,q,x,z B）a,g,m,h,q,n,p,x,z C）g,m,q,a,n,p,x,h,z D）h,g,m,p,a,n,q,x,z
二、（每小题4分，共8分）
已知一个6?5稀疏矩阵如下所示，试：
?????????
?
?????
??
???--00
70
00000520000000100000010000 （1）写出它的三元组线性表；
（2）给出三元组线性表的顺序存储表示。 三、（本题8分）
求网的最小生成树有哪些算法？它们的时间复杂度分别下多少，各适用何种情况？ 四、（每小题4分，共8分）
对于如下图所示的有向图若存储它采用邻接表，并且每个顶点邻接表中的边结点都是按照终点序号从小到大的次序链接的，试写出：
（1）从顶点v1出发进行深度优先搜索所得到的深度优先生成树； （2）从顶点v2出发进行广度优先搜索所得到的广度优先生成树。
五、（本题8分）
已知一个图的顶点集V 和边集E 分别为： V={1,2,3,4,5,6,7};
E={<2,1>,<3,2>,<3,6>,<4,3>,<4,5>,<4,6>,<5,1>,<5,7>,<6,1>,<6,2>,<6,5>};
若存储它采用邻接表，并且每个顶点邻接表中的边结点都是按照终点序号从小到大的次序链接的，试给出得到的拓扑排序的序列。
六、（本题8分）
对于序列{8,18,6,16,29,28}，试写出堆顶元素最小的初始堆。 七、（本题8分）
一棵二叉树的先序、中序和后序序列分别如下，其中有一部分未显示出来。试求出空格处的内容，并画出该二叉树。
先序序列： B F ICEH G 中序序列：D KFIA EJC 后序序列： K FBHJ G A 八、（每小题2分，共8分）
设有序列：w={23,24,27,80,28}，试给出： （1）二叉排序树； （2）哈夫曼树；
（3）平衡二叉树；
（4）对于增量d=2按降序执行一遍希尔排序的结果。 九、（本题9分）
有关键字序列{7,23,6,9,17,19,21,22,5}，Hash 函数为H(key)=key % 5，采用链地址法处理冲突，试构造哈希表。
十、（本题15分）
假设二叉树中每个结点所含数据元素均为单字母，以二叉链表为存储结构，试编写算法按如下图所示的树状显示二叉树。
模拟试题（一）参考答案
一、单项选择题
（1）B （2）D （3）A （4）B （5）B
（6）C （7）A （8）C （9）B （10）B
二、（每小题4分，共8分）
（1） ((1,5,1),(3,2,-1),(4,5,-2),(5,1,5),(6,3,7)) （2）三元组线性表的顺序存储表示如下所示：
?
?????????
?????????
?--726515254123151556 三、（本题8分）
求网的最小生成树可使用Prim 算法，时间复杂度为O(n 2)，此算法适用于边较多的稠密图，也可使用Kruskal 算法，时间复杂度为O(eloge)，此算法适用于边较少的稀疏图。
四、（每小题4分，共8分） （1）DFS ：v1 v2 v3 v4 v5 （2）BFS ：v2 v3 v4 v5 v1 五、（本题8分）
拓扑排序为： 4 3 6 5 7 2 1 六、（本题8分）
所构造的堆如下图所示：
七、（本题8分）
在先序序列空格中依次填ADKJ，中序中依次填BHG，后序中依次填DIEC。
八、（每小题2分，共8分）
（1）二叉排序树如下图所示：
（2）哈夫曼树如下图所示：
（3）平衡二叉树如下图所示：
（4）对于增量d=2按降序执行一遍希尔排序的结果：28,80,27,24,23
九、（本题9分）
哈希表如下图所示：
十、（本题15分）
从上图来看，二叉树的第一层显示在第一列，第二层显示在第二列，第三层显示在第三列；每行显示一个结点，从上至下是先显示右子树，再显示根，最后最左子树，也就是以先遍历右子树，最后遍历左子树的中序遍历次序显示各结点。
C++语言版测试程序见exam1\10c++，具体算当如下：
template
void display_BT_with_tree_shape(const Binary_tree
{
aux_display_BT_with_tree_shape
}
template
void aux_display_BT_with_tree_shape(Binary_node
// 按树状形式显示二叉树，level为层次数，可设根结点的层次数为1
{
if(sub_root != NULL)
{ //空树不显式，只显式非空树
aux_display_BT_with_tree_shape
cout< for(int i=0;i cout<<" "; //确保在第level列显示结点 cout< aux_display_BT_with_tree_shape } C语言版测试程序见exam1\10c，具体算当如下： void DisplayBTWithTreeShape(BiTree T,int level=1) // 按树状形式显示二叉树，level为层次数，可设根结点的层次数为1 { if(T) { //空树不显式，只显式非空树 DisplayBTWithTreeShape(T->rchild,level+1); //显示右子树 cout< for(int i=0;i cout<<" "; //确保在第level列显示结点cout< DisplayBTWithTreeShape(T->lchild,level+1); //显示左子树 } } 模拟试题（二） 一、单项选择题（每小题2 分，共20分） （1）设Huffman树的叶子结点数为m，则结点总数为（）。 A）2m B）2m-1 C）2m+1 D）m+1 （2）若顺序存储的循环队列的QueueMaxSize=n，则该队列最多可存储（）个元素。 A）n B）n-1 C）n+1 D）不确定 （3）下述哪一条是顺序存储方式的优点？（） A）存储密度大B）插入和删除运算方便 C）获取符合某种条件的元素方便D）查找运算速度快 （4）设有一个二维数组A[m][n]，假设A[0][0]存放位置在600(10)，A[3][3]存放位置在678(10)，每个元素占一个空间，问A[2][3](10)存放在什么位置？（脚注(10)表示用10进制表示，m>3）（）。 A）658 B）648 C）633 D）653 （5）下列关于二叉树遍历的叙述中，正确的是（）。 A）若一个叶子是某二叉树的中序遍历的最后一个结点，则它必是该二叉树的前序遍历最后一个结点 B）若一个结点是某二叉树的前序遍历最后一个结点，则它必是该二叉树的中序遍历的最后一个结点 C）若一个结点是某二叉树的中序遍历的最后一个结点，则它必是该二叉树的前序最后一个结点 D）若一个树叶是某二叉树的前序最后一个结点，则它必是该二叉树的中序遍历最后一个结点 （6）k层二叉树的结点总数最多为（）。 A）2k-1 B）2k+1C）2K-1 D）2k-1（7）对线性表进行二分法查找，其前提条件是（）。 A）线性表以链接方式存储，并且按关键码值排好序 B）线性表以顺序方式存储，并且按关键码值的检索频率排好序 C）线性表以顺序方式存储，并且按关键码值排好序 D）线性表以链接方式存储，并且按关键码值的检索频率排好序（8）对n个记录进行堆排序，所需要的辅助存储空间为（）。 A）O(1og2n) B）O(n)C）O(1) D）O(n2) （9）对于线性表（7，34，77，25，64，49，20，14）进行散列存储时，若选用H（K）=K%7作为散列函数，则散列地址为0的元素有（）个。 A）1 B）2 C）3 D）4 （10）下列关于数据结构的叙述中，正确的是（）。 A）数组是不同类型值的集合 B）递归算法的程序结构比迭代算法的程序结构更为精炼 C）树是一种线性结构 D）用一维数组存储一棵完全二叉树是有效的存储方法 二、（本题8分） 假定一棵二叉树广义表表示为a(b(c),d(e,f))，分别写出对它进行先序、中序、后序、按层遍历的结果。 三、（每小题4分，共8分） 已知一个无向图的顶点集为{a, b, c, d, e}，其邻接矩阵如下所示： ??????? ?????????1011001101000111001001001 （1）画出该图的图形； （2）根据邻接矩阵从顶点a 出发进行深度优先遍历和广度优先遍历，写出相应的遍历序列。 四、（本题8分） 树有哪些遍历方法？它们分别对应于把树转变为二叉树的哪些遍历方法？ 五、（本题8分） 设有数组A[-1:3,0:6,-2:3]，按行为主序存放在2000开始的连续空间中，如元素的长度是5，试计算出A[1,1,1]的存储位置。 六、（本题8分） 试列出如下图中全部可能的拓扑排序序列。 七、（本题8分） 已知哈希表地址空间为0..8，哈希函数为H(key)=key%7，采用线性探测再散列处理冲突，将数据序列{100,20,21,35,3,78,99,45}依次存入此哈希表中，列出插入时的比较次数，并求出在等概率下的平均查找长度。 八、（本题8分） 设有一个输入数据的序列是 { 46, 25, 78, 62, 12, 80 }, 试画出从空树起，逐个输入各个 数据而生成的二叉搜索树。 九、（本题9分） 试画出表达式(a+b/c)*(d-e*f)的二叉树表示，并写出此表达式的波兰式表示，中缀表示及逆波兰式表示。 十、（本题15分） 以二叉链表作存储结构，试编写计算二叉树中叶子结点数目的递归算法。 模拟试题（二）参考答案 一、单项选择题（每小题 2 分，共20分） （1）B （2）B （3）A （4）D （5）A （6）A （7）C （8）C （9）D （10）D 二、（本题8分） 先序：a,b,c,d,e,f 中序：c,b,a,e,d,f 后序：c,b,e,f,d,a 按层：a,b,d,c,e,f 三、（每小题4分，共8分） 【解答】 （1）该图的图形如下图所示： （2）深度优先遍历序列为：abdce；广度优先遍历序列为：abedc。 四、（本题8分） 树的遍历方法有先根序遍历和后根序遍历，它们分别对应于把树转变为二叉树后的先序遍历与中序遍历方法。 五、（本题8分） A[1,1,1]的存储位置=2000+((1-(-1))*(6-0+1)*(3-(-2)+1)+(1-0)*(3-(-2)+1)+(1-(-2)))*5=2465。 六、（本题8分） 全部可能的拓扑排序序列为：1523634、152634、156234、561234、516234、512634、512364 七、（本题8分） 哈希表及查找各关键字要比较的次数如下所示： 1(4×1+1×2+1×4+2×5)=2.5 ASL= 8 八、（本题8分） 九、（本题9分） 表达式的波兰式表示，中缀表示及逆波兰式表示分别是此表达式的二叉树表示的前序 遍历、中序遍历及后序遍历序列。 二叉树表示如下图所示： 波兰式表示：*+a/bc-d*ef 中缀表示：a+b/c*d-e*f 逆波兰式表示：abc/+def*-* 十、（本题15分） 本题只要在遍历二叉树的过程序中对叶子结点进行记数即可。 C++语言版测试程序见exam2\10c++，具体算当如下： template long leaf_count(const Binary_tree // 计算二叉树中叶子结点数目 { return aux_leaf_count } template long aux_leaf_count(Binary_node // 按树状形式显示二叉树，level为层次数，可设根结点的层次数为1 { if(sub_root==NULL) return 0; //空树返回0 else if(sub_root->left==NULL&&sub_root->right==NULL) return 1; //只有一个结点的树返回1 else //叶子结点数为左右子树的叶子结点数之和 return aux_leaf_count(sub_root->left)+aux_leaf_count(sub_root->right); } C语言版测试程序见exam2\10c，具体算当如下： long LeafCount(BiTree T) // 计算二叉树中叶子结点数目 { if(T==NULL) return 0; //空树返回0 else if(T->lchild==NULL&&T->rchild==NULL) return 1; //只有一个结点的树返回1 else //叶子结点数为左右子树的叶子结点数之和 return LeafCount(T->lchild)+LeafCount(T->rchild); } 模拟试题（三） 一、单项选择题（每小题2 分，共20分） （1）对一个算法的评价，不包括如下（）方面的内容。 A）健壮性和可读性B）并行性C）正确性D）时空复杂度（2）在带有头结点的单链表HL中，要向表头插入一个由指针p指向的结点，则执行（）。 A）p->next=HL->next; HL->next=p B）p->next=HL; HL=p C）p->next=HL; p=HL D）HL=p; p->next=HL （3）对线性表，在下列哪种情况下应当采用链表表示？（） A）经常需要随机地存取元素B）经常需要进行插入和删除操作 C）表中元素需要占据一片连续的存储空间D）表中元素的个数不变（4）一个栈的输入序列为1 2 3，则下列序列中不可能是栈的输出序列的是（）。 A）2 3 1 B）3 2 1 C）3 1 2 D）1 2 3 （5）每一趟都能选出一个元素放在其最终位置上，并且不稳定的排序算法是（）。 A）冒泡排序B）简单选择排序C）希尔排序D）直接插入排序（6）采用开放定址法处理散列表的冲突时，其平均查找长度（）。 A）低于链接法处理冲突B）高于链接法处理冲突 C）与链接法处理冲突相同D）高于二分查找 （7）若需要利用形参直接访问实参时，应将形参变量说明为（）参数。 A）值B）函数C）指针D）引用（8）在稀疏矩阵的带行指针向量的链接存储中，每个单链表中的结点都具有相同的（）。 A）行号B）列号C）元素值D）非零元素个数（9）快速排序在最坏情况下的时间复杂度为（）。 A）O(log2n) B）O(nlog2n) C）O(n) D）O(n2) （10）从二叉搜索树中查找一个元素时，其时间复杂度大致为（）。 A）O(n) B）O(1) C）O(log2n) D）O(n2) 二、（本题8分） 已知一个图的顶点集V和边集E分别为： V={1,2,3,4,5,6,7}; E={(1,2)3,(1,3)5,(1,4)8,(2,5)10,(2,3)6,(3,4)15,(3,5)12,(3,6)9,(4,6)4,(4,7)20,(5,6)18,(6,7)25}; 用克鲁斯卡尔算法得到最小生成树，试写出在最小生成树中依次得到的各条边。 三、（本题8分） 请画出如下图所示的邻接矩阵和邻接表。 四、（每小题4分，共8分） 设有如下图所示的AOE网（其中vi（i=l，2，…，6）表示事件，弧上表示活动的天数）。 （1）找出所有的关键路径。 （2）v3事件的最早开始时间是多少。 五、（本题8分） 如果在1000000个记录中找出两个最小的记录，你认为采用什么样的排序方法所需的关键字比较次数最少？最多比较多少次？ 六、（本题8分） 假设把n个元素的序列（a1,a2,…a n）满足条件a k 七、（每小题4分，共8分） 设内存有大小为6个记录的缓冲区供内排序使用，文件的关键字序列为｛29,50,70,33,38,60,28,31,43,36,25,9,80,100,57,18,65,2,78,30,14,20,17,99），试列出：（1）用内排序求出初始归并段； （2）用置换一选择排序求初始归并段。 八、（本题8分） 已知一组关键字为（19,14,23,1,68,20,84,27,55,11,10,79），哈希函数：H(key)=key MOD 13，哈希地址空间为0~12，请构造用链地址法处理冲突的哈希表，并求平均查找长度。 九、（本题9分） 已知关键字序列{23，13，5，28，14，25}，试构造二叉排序树。 十、（本题15分） 编写一个算法求二又树的深度。 模拟试题（三）参考答案 一、单项选择题（每小题 2 分，共20分） （1）B （2）A （3）B （4）C （5）B （6）B （7）D （8）A （9）D （10）C 二、（本题8分） 用克鲁斯卡尔算法得到的最小生成树为： (1,2)3, (4,6)4, (1,3)5, (1,4)8, (2,5)10, (4,7)20 三、（本题8分） 邻接矩阵：??? ? ??? ??????? ?? 01110 10101110111010101110 邻接表如下图所示： 四、（每小题4分，共8分） （1）找出所有的关键路径有：v1→v2→v3→v5→v6，以及v1→v4→v6。 （2）v3事件的最早开始时间是13。 五、（本题8分） 采用树形选择排序方法所需的关键字比较次数最少，最多比较次数=999999+??1000000log 2=1000019次。 六、（本题8分） 不对，例如序列｛3、3、4、2、l ｝的“逆序元素”个数是2，2和1是“逆序元素”；但是将第二个3和2交换后，成为｛3、2、4、3、l ｝，此时“逆序元素”个数是3，2、3和1是“逆序元素”。然而交换后一定减少的是“逆序对”的个数，例如上例中｛3、3、4、2、l ｝的逆序对的个数是 7，交换第二个 3和2后，｛3、2、4、3、1｝的逆序对的个数是6。 七、（每小题4分，共8分） （1）用内排序求出初始归并段为： 归并段1：29,33,38,50,60,70: 归并段2：9,25,28,31,36,43 归并段3：2,18,57,65,80,100: 归并段4：14,17,20,30,78,99. （2）用置换一选择排序求初始归并段为： 归并段1：29,33,38,50,60,70,80,100 归并段2：9,18,25,28,31,36,57,65,78,99; 归并段3：2,14,17,20,30. 八、（本题8分） 用链地址法处理冲突的哈希表如下图所示： 1(1*6+2*4+3*1+4*1)=1.75 ASL= 12 九、（本题9分） 构造二叉排序树的过程如下图所示。 构造的二叉排序树如下图所示： 十、（本题15分） 若二叉树为空，深度为0；若二叉树不空，则二叉树的深度为左右子树深度的最大值加1。本题最简单算法是递归算法。 C++语言版测试程序见exam3\10c++，具体算当如下： template int bitree_depth(const Binary_tree // 求二叉树的深度 { return aux_bitree_depth(T.get_root()); } template int aux_bitree_depth(Binary_node // 求二叉树的深度 { if(sub_root==NULL) return 0; //空二叉树的深度为0 else { int d_lsub,d_rsub; d_lsub=aux_bitree_depth(sub_root->left); //左子树的深度 d_rsub=aux_bitree_depth(sub_root->right); //右子树的深度 //返回左右子树的深度最大值加1 return ((d_lsub>d_rsub)?d_lsub:d_rsub)+1; } } C语言版测试程序见exam3\10c，具体算当如下： int BiTreeDepth(BiTree T) // 求二叉树的深度 { if(T==NULL) return 0; //空二叉树的深度为0 else { int d_lsub,d_rsub; d_lsub=BiTreeDepth(T->lchild); //左子树的深度 d_rsub=BiTreeDepth(T->rchild); //右子树的深度 //返回左右子树的深度最大值加1 return ((d_lsub>d_rsub)?d_lsub:d_rsub)+1; } } 一、单项选择题（本题共15小题，每小题2分，共30分） 在每小题列出的四个备选项中只有一个是符合题目要求的，请将其正确答案涂写在答题卡上。 1. 以“.js”为文件扩展名的文件是______。 (A) html文件(B) 网页文件(C) Java文件(D) Javascript文件 2.以下合法的变量名是______。 (A) new (B) _123 (C) null (D) 2abc 3.以下正确的字符串是______。 (A) xyz (B) ‘xyz” (C) “xyz’ (D) ‘xyz’ 4.设有语句： var st1=’test’; st1=st1+ 25; 则st1的值是______。 (A) ‘test25’ (B) 25 (C) ‘test’(D) 语法错误 5.123+”789”的值是______。 (A) ‘123789’ (B) 912 (C) “789”(D) 语法错误 6.表达式（a=2,b=5,a>b?a:b）的值是______。 (A) 2 (B) 5 (C) 1 (D) 0 7.设有语句var a=3,b=5,c=3,d=8,m=3,n=2; 则逻辑表达式(m=a>b)&&(n=c>d)运算后，n的值为_______。 (A) 0 (B) 1 (C) 2 (D) 3 8.设var a=2,b=3; 则a++==b?(a-1):b的结果是___________。 A) 0 B) 1 C) 2 D) 3 9. 下面while循环执行的次数为________。 var i=5; while (i==0) i--; A)无限B) 1 C) 5 D) 0 10. 以下数组的定义中____________是错误的。 A) var a=new Array(); B) var a=new Array(10); C) var a[10]={ 1,2,3}; D) var a=["1",2,"3"]; 11.设var x=3,y=4; 下列表达式中y的值为9的是________。 A）y*=x-3 B）y/=x*9 C）y-=x+10 D）y+=x+2 12. 在程序中有多个相关联的选项，若要默认选择某一项，应在该项中增加_________属性。 A) checked B) default C) selected D) defaultValue 13．结果为NaN的表达式是______。 (A) "80"+"19" (B) "十九"+"八十" (C) "八十"*"十九" (D) "80"*"19" 14．执行下面语句后c的值是_______。 var a=2,b=1,c=3; if(a 一、判断题： 1、力矩分配法中的分配系数、传递系数与外来因素（荷载、温度变化等）有关。（ ） 2、若图示各杆件线刚度i 相同，则各杆A 端的转动刚度S 分别为：4 i , 3 i , i 。（√ ） A A A 3、图示结构EI =常数，用力矩分配法计算时分配系数4 A μ= 4 / 11。（ ） 1 2 3 4 A l l l l 4、图示结构用力矩分配法计算时分配系数μAB =12/，μAD =18/。（√ ） B C A D E =1i =1 i =1i =1 i 5、用力矩分配法计算图示结构，各杆l 相同，EI =常数。其分配系数μBA =0.8，μBC =0.2， μBD =0。（√ ） A B C D 6、单元刚度矩阵反映了该单元杆端位移与杆端力之间的关系。（√ ） 7、单元刚度矩阵均具有对称性和奇异性。（ X ） 8、局部坐标系与整体坐标系之间的坐标变换矩阵T 是正交矩阵。（√ ） 9、结构刚度方程矩阵形式为：[]{}{}K P ?=，它是整个结构所应满足的变形条件。（ X ） 10、矩阵位移法中，等效结点荷载的“等效原则”是指与非结点荷载的结点位移相等。（√ ） 二．选择题 (1)欲使图2－1所示体系的自振频率增大，在下述办法中可采用：（ D ） A．增大质量 m； B．将质量 m 移至梁的跨中位置；C．减小梁的 EI； D．将铰支座改为固定支座。 图2－1 (2)平面杆件结构一般情况下的单元刚度矩阵[]66? k，就其性质而言，是：（ B ） A．非对称、奇异矩阵； B．对称、奇异矩阵； C．对称、非奇异矩阵； D．非对称、非奇异矩阵。 (3)已知图2－3所示刚架各杆 EI = 常数，当只考虑弯曲变形，且各杆单元类型相同时，采用先处理法进行结点位移编号，其正确编号是：（A ） 图2－3 2017年数据结构期末考试题及答案 一、选择题（共计50分，每题2分，共25题） 1 ?在数据结构中，从逻辑上可以把数据结构分为 C 。 A. 动态结构和静态结构B?紧凑结构和非紧凑结构 C.线性结构和非线性结构 D .内部结构和外部结构 2?数据结构在计算机内存中的表示是指 A ° A. 数据的存储结构 B.数据结构 C.数据的逻辑结构 D .数据元 素之间的关系 3.在数据结构中，与所使用的计算机无关的是数据的 A 结构。 A. 逻辑B?存储 C.逻辑和存储 D.物理 4 .在存储数据时，通常不仅要存储各数据元素的值，而且还要存储 C ° A.数据的处理方法B?数据元素的类型 C.数据元素之间的关系 D.数据的存储方法 5. 在决定选取何种存储结构时，一般不考虑 A ° A.各结点的值如何B?结点个数的多少 C?对数据有哪些运算 D.所用的编程语言实现这种结构是否方便。 6. 以下说法正确的是D ° A. 数据项是数据的基本单位 B. 数据元素是数据的最小单位 C. 数据结构是带结构的数据项的集合 D. —些表面上很不相同的数据可以有相同的逻辑结构 7. 在以下的叙述中，正确的是B ° A. 线性表的顺序存储结构优于链表存储结构 B. 二维数组是其数据元素为线性表的线性表 C?栈的操作方式是先进先出 D.队列的操作方式是先进后出 8. 通常要求同一逻辑结构中的所有数据元素具有相同的特性，这意味着 A. 数据元素具有同一特点 B. 不仅数据元素所包含的数据项的个数要相同，而且对应的数据项的类型要一致 C. 每个数据元素都一样 D. 数据元素所包含的数据项的个数要相等 9 ?链表不具备的特点是 A 。 A.可随机访问任一结点 B.插入删除不需要移动元素 C?不必事先估计存储空间 D.所需空间与其长度成正比 10. 若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一 个结点，则采用 D 存储方式最节省运算时间。 A.单链表B ?给出表头指针的单循环链表 C.双链表D ?带头结点 的双循环链表 11. 需要分配较大空间，插入和删除不需要移动元素的线性表，其存储结构是 B 。 A.单链表B .静态链表 C.线性链表 D .顺序存储结构 12 .非空的循环单链表head的尾结点（由p所指向）满足C 。 A. p—>next 一NULL B. p — NULL C. p—>next == head D. p = = head 13 .在循环双链表的p所指的结点之前插入s所指结点的操作是 D 。 A .p—> prior-> prior=s B .p—> prior-> n ext=s C.s —> prior—> n ext = s D.s —> prior—> prior = s 14 .栈和队列的共同点是C 。 A.都是先进后出 B .都是先进先出 C.只允许在端点处插入和删除元素 D .没有共同点 四、程序设计题（本大题共2小题，每小题15分，共30分） 1.对于教学数据库的三个基本表 学生student (sno,sname,sex,sage,sdept) 学习sc(sno,cno,grade) 课程course(cno,cname,cpno,ccredit) 试用SQL语句表示：下列语句。 （1）"查询全男同学信息情况" "select * from student where sex='男'" （2）"查询选修了1号课的学生的学号和成绩" "select sno,grade from sc where cno='1'" （3）"查询所有选修过课的学生的姓名，课程名及成绩" "select sname,cname,grade from student,sc,course where student.sno=sc.sno and https://www.doczj.com/doc/8118198224.html,o=https://www.doczj.com/doc/8118198224.html,o" （4）"查询选修了数据库原理课的最高成绩" "select max(grade) as '最高成绩' from student,sc,course where student.sno=sc.sno and https://www.doczj.com/doc/8118198224.html,o=https://www.doczj.com/doc/8118198224.html,o and cname='数据库原理'" （5）查询所有选修了1号课程的同学的姓名" " select sname from student where student.sno in (select sc.sno from sc where cno='1')" 2．设有一个SPJ数据库，包括S，P，J，SPJ四个关系模式（20分）供应商表S（SNO,SNAME,STATUS,CITY）; 零件表P(PNO,PNAME,COLOR,WEIGHT); 工程项目表J(JNO,JNAME,CITY); 供应情况表SPJ(SNO,PNO,JNO,QTY)；SPJ表 J表 S表 P表 请用关系代数完成如下查询： 1．求供应工程J1零件的供应商号 SNO 2．求供应工程J1零件P1的供应商号吗SNO 3．求供应工程J1零件为红色的供应商号码SNO 4．求没有使用天津供应商生产的红色零件的工程号JNO 5．求至少用了供应商S1所供应的全部零件的工程号JNO 1.∏sno（σJNO＝‘J1’（SPJ）） 2.∏sno（σJNO＝‘J1’ΛPNO=’P1’（SPJ）） 3.∏sno（σJNO＝‘J1’（SPJ）∞σcolor＝‘红’（P）） 4.∏jno（SPJ）-∏jno（∏sno（σcity＝‘天津’（S））∞∏sno，jno （SPJ）∞∏jno σcolor＝‘红’（P）） 5.∏jno, pno（SPJ）÷∏pno（σsno＝‘s1’（SPJ）） 五、分析题（本大题共2小题，每小题15分本大题共30分） 1. 学生运动会模型: (1)有若干班级,每个班级包括: 班级号,班级名,专业,人数 (2)每个班级有若干运动员,运动员只能属于一个班,包括:运动员号,姓名,性别,年龄 一、判断题(共223小题） 1。结构的类型若按几何特征可分为平面结构和空间结构。(A) 2、狭义结构力学的研究对象是板、壳结构(B)。 3 单铰相当于两个约束。(A) 4、单刚节点相当于三个约束。(A) 5、静定结构可由静力平衡方程确定全部约束力和内力。A 6、超静定结构可由静力平衡方程确定全部约束力和内力B。 7 无多余约束的几何不变体系是静定结构。A 8 三刚片规则中三铰共线为可变体系。B 9 两刚片用一个单铰和一个不通过该铰的链杆组成的体系为静定结构。A 10 两刚片用一个单铰和一个不通过该铰的链杆组成的体系为超静定结构B。 11链杆相当于两个约束。B 12 平面上的自由点的自由度为2 A 13 平面上的自由刚体的自由度为3 A 14 铰结点的特征是所联结各杆可以绕结点中心自由转动。A 15 有多余约束的几何不变体系是超静定结构。A 16 无多余约束的几何可变体系是超静定结构。B 17、无多余约束的几何可变体系是静定结构。B 18刚结点的特征是当结构发生变形时汇交于该点的各杆端间相对转角为零。A 19 三刚片规则中三铰共线为瞬变体系。A 20三个本身无多余约束的刚片用三个不共线的单铰两两相连，则组成的体系为静定结构。A 21 一个刚结点相当于3个约束。 22 一个连接3个刚片的复铰相当于2个单铰。A 23 一个铰结三角形可以作为一个刚片。A 24 一个铰结平行四边形可以作为一个刚片。B 25 一根曲杆可以作为一个刚片。A 26 一个连接４个刚片的复铰相当于2个单铰．B 27 任意体系加上或减去二元体，改变体系原有几何组成性质。B 28 平面几何不变体系的计算自由度一定等于零。B 29 平面几何可变体系的计算自由度一定等于零。B 30 三刚片体系中若有1对平行链杆，其他2铰的连线与该对链杆不平行，则该体系为几何不变体系。A 31 三刚片体系中，若有三对平行链杆，那么该体系仍有可能是几何不变的。B 32 三刚片体系中，若有２对平行链杆，那么该体系仍有可能是几何不变的。A 33 一个单铰相当于一个约束。B 34 进行体系的几何组成分析时，若体系通过三根支座链杆与基础相连，可以只分析体系内部。B 35 三刚片体系中，若有两个虚铰在无穷远处，则该体系一定为几何可变。B 36 有多余约束的体系为静定结构。B 37 静定结构一定几何不变。A 38 超静定结构一定几何不变．A 39 几何不变体系一定是静定结构。B 40几何不变体系一定是超静定结构。B 41力是物体间相互的机械作用。A 42 力的合成遵循平行四边形法则。A 43 力的合成遵循三角形法则。A 44 力偶没有合力。A 45 力偶只能用力偶来平衡。A 46 力偶可以和一个力平衡。B 47 力偶对物体既有转动效应，又有移动效应。B 48 固定铰支座使结构在支承处不能移动也不能转动。B 49 可动铰支座使结构在支承处能够转动，但不能沿链杆方向移动。A 50 结点法求解桁架内力应按照结构几何组成相反顺序来求解。A 51 将一个已知力分解为两个力可得到无数解答。A 52 作用力和反作用力是作用在同一物体上的两个力。B 53 作用力和反作用力是作用在不同物体上的两个力。A 54 两个力在同一轴上的投影相等，此两力必相等 B 55 力偶对平面内任一点的矩等于力偶矩A 56 力偶在坐标轴上的投影的代数和等于零A 57 一个固定铰支座相当于两个约束。A 58三个本身无多余约束的刚片用三个不共线的单铰两两相连，则组成的体系为超静定结构B 59 桁架是“只受结点荷载作用的直杆、铰结体系”。A 60桁架结构的内力有轴力。A 61 拱的合理拱轴线均为二次抛物线。B 62无铰拱属于超静定结构。A 63 三铰刚架和三铰拱都属于推力结构。A 64 简支刚架属于推力结构。B 65 三铰拱属于静定结构。A 66 相同竖向载荷作用下，同跨度拱的弯矩比代梁的弯矩大得多。B 67 桁架结构中，杆的内力有轴力和剪力。B 68 竖向载荷作用下，简支梁不会产生水平支反力．A 69 竖向载荷作用下，拱不会产生水平支反力。B 70 竖向载荷作用下，拱的水平推力与拱高成正比。B 数据结构期末考试题及答案 、选择题 1.在数据结构中, 从逻辑上能够把数据结构分为 A. 动态结构和静态结构 B ．紧凑结构和非紧凑结构 C.线性结构和非线性结构 D .内部结构和外部结构 2. 数据结构在计算机内存中的表示是指 A.数据的存储结构 B.数据结构 C.数据的逻辑结构 D.数据元素之间的关系 3. 在数据结构中, 与所使用的计算机无关的是数据的 结构。 A.逻辑 B.存储 C.逻辑和存储 D.物理 4. 在存储数据时, 一般不但要存储各数据元素的值, 而且还 要存储C A. 数据的处理方法 B. 数据元素的类型 C.数据元素之间的关系 D.数据的存储方法 5.在决定选取何种存储结构时般不考虑A 。 A. 各结点的值如何 B. 结点个数的多少 C.对数据有哪些运算 D.所用的编程语言实现这种结构是否方便。 6.以下说法正确的是 A. 数据项是数据的基本单位 B. 数据元素是数据的最小单位 C. 数据结构是带结构的数据项的集合 D. —些表面上很不相同的数据能够有相同的逻辑结构7．算法分析的目的是C , 算法分析的两个主要方面是A 。 (1) A.找出数据结构的合理性 和输出的关系 C. 分析算法的效率以求改进 档性 ( 2) A .空间复杂度和时间复杂度 C. 可读性和文档性 性 8. 下面程序段的时间复杂度是 s = 0; for( I = 0; i v n; i + + ) for( j = 0; j v n; j ++ ) s +二B[i][j]; sum = s ; 9. 下面程序段的时间复杂度是 for( i = 0; i v n; i + + ) for( j = 0; j v m; j ++ ) B .研究算法中的输入 C .分析算法的易读性和文 B .正确性和简明性D .数据复杂性和程序复杂 O( n2) 。 O( n*m) 。 期末考试模拟试题（二） 一．听句子，选出句子中含有的信息。（10分） ( ) 1. A. Singapore B. Paris C. Toronto ( ) 2. A. the biggest city B. the smallest city C. the hottest city ( ) 3. A. come to tea B. come to a party C. go for a walk ( ) 4. A. had a fever B. had a cold C. have a fever ( ) 5. A. Spring Festival B. Mid-autumn Festival C. Christmas ( ) 6. A. play cards B. play games C. play chess ( ) 7. A. food B. drink C. fruit ( ) 8. A. next Wednesday B. next Thursday C. next Saturday ( ) 9. A. the Monkey King B. the Lion King C. Mickey Mouse ( ) 10. A. go fishing B. play badminton C. go to the circus 二．听句子，写出句子中所缺的词。（5分） 1. Adults usually give to children during Spring festival in China. 2. We are going to the Great the day after . 3. I my house and other housework yesterday. 4. This is the time to be in . 5. What’s the of ? 三．听对话及问题，选出问题的正确答案。（10分） ( ) 1. A English. B. Chinese. C. Maths. ( ) 2. A. At school. B. At home. C. Sorry, I don’t know. ( ) 3. A. A new watch. B. Some flowers. C. A new clock. ( ) 4. A.Go shopping. B. See her friend in hospital. C. Go sightseeing. ( ) 5. A. Guangzhou. B. Beijing. C. Guilin. ( ) 6. A. Yes, she does. B. No, she didn’t. C. Yes, she did. ( ) 7. A. Washed his dog. B. Played football. C. Saw a film on TV. ( ) 8. A. Tuesday, May 3rd. B. Sunday, May 1st. C. Monday, May 2nd. ( ) 9. A. Yes, it is. B. No, it isn’t. C. No, it wasn’t. ( ) 10. A. Go boating. B. Go swimming. C. Go to see a film. 四．听短文，判断对错。对的T，错的F。（5分） ( ) 1. The shops and department stores are quiet. ( ) 2. People are doing their Christmas shopping. ( ) 3. Lots of families have their Christmas trees. ( ) 4. Mr. Brown and his family are getting ready for the Christmas. ( ) 5. They are going to have a big dinner. 五．看图写出所缺的单词或词组。（5分） 1. d 2. F C 3. S F 4. B 5. c 六．找出不同类的单词。（4分） ( ) 1. A. Christmas B. Easter C. Thanksgiving D. festival ( ) 2. A. Saturday B. April C. August D. December ( ) 3. A. important B. popular C. interesting D. present ( ) 4. A. sweet B. merry C. cake D. egg ( ) 5. A. winter B. summer C. season D. spring ( ) 6. A. painted B. had C. have D. was ( ) 7. A. housework B. lesson C. house D. dirty ( ) 8. A. mark B. prepare C. food D. feel 第1题第2题2.图示外伸梁，跨中截面C的弯矩为（ ? m D．17kN m 题7图图（a）图（b）图（c）图（d）位移法典型方程中系数k ij=k ji反映了（） A.位移互等定理 B.反力互等定理 第9题第10题 10.FP=1在图示梁AE上移动，K截面弯矩影响线上竖标等于零的部分为（）．DE、AB段B．、DE段C．AB、BC段D．BC、CD段 二、填空题：（共10题，每题2分，共20分） 两刚片用一个铰和_________________相联，组成无多余约束的几何不变体系。 所示三铰拱的水平推力 第3题机动法作静定结构内力影响线依据的是_____________。 ．静定结构在荷截作用下，当杆件截面增大时，其内力____________。 D处的纵标值y D为_________。 第6题第7题 7.图示结构，各杆EI=常数，用位移法计算，基本未知量最少是_________个。 8.图示结构用力法计算时，不能选作基本结构的是______。 3．用力法计算图示刚架，并绘其M 图，EI D 4m N/m EI 10kN/m A B C D 2EI EI 4m 2m 4m G F EI 10k N /m C F l ql 12 2 G A 一、选择题:（共10题，每小题2分，共20分） 1.A 2.D 3. A 4.D 5.A 6.C 7.D 8.B 9.C 10.C 二、填空题（共10空，每空2分，共20分） 1.不通过此铰的链杆 2. FP/2（→） 3.l θ（↓） 4. 刚体体系虚功原理 5.不变 6.-1/2 7.6 8.（c ） 9.反对称 10.无侧移的超静定结构 三、问答题：（共2题，每小题5分，共10分） 1．图乘法的应用条件是什么？求变截面梁和拱的位移时可否用图乘法？ 答.图乘法的应用条件：1）杆轴线为直线，2）杆端的EI 为常数3）MP 和M 图中至少有一个为直线图形。否。（7分） 2．超静定结构的内力只与各杆件的刚度相对值有关，而与它们的刚度绝对值无关，对吗？为什么？ 答：不对。仅受荷载作用的超静定结构，其内力分布与该结构中的各杆刚度相对值有关；而受非荷载因素作用的超静定结构，其内力则与各杆刚度的绝对值有关。（7分） 四、计算题. （1、2题8分，3题10分，4、5题12分,4题共计50分） 1．图示桁架，求1、2杆的轴力。 解：F N1=75KN ，F N2=2 13 5 KN 2．图示刚架，求支座反力，并绘弯矩图。 解：F Ay =22KN （↓）F Ax =48KN （←）F By =42KN （↑） 最终的弯矩图为： 3．用力法计算图示刚架，并绘其M 图，EI 为常数。 2011-2012学年第一学期期末考查 《数据结构》试卷 （答案一律写在答题纸上，在本试卷上做答无效） 一、选择（每题1分，共10分） 1.长度为n的线性表采用顺序存储结构，一个在其第i个位置插入新元素的算法时间复杂度为（D） A.O(0) B.O(1) C.O(n) D.O(n2) 2.六个元素按照6，5，4，3，2，1的顺序入栈，下列哪一个是合法的出栈序列？（D） A.543612 B.453126 C.346512 D.234156 3.设树的度为4，其中度为1、2、3、4的结点个数分别是4、2、1、2，则树中叶子个数为（B ） A.8 B.9 C.10 D.11 4.设森林F对应的二叉树B有m个结点，B的右子树结点个数为n，森林F中第一棵树的结点个数是（ B ） A. m-n B.m-n-1 C.n+1 D.m+n 5.若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（B） A.9 B.11 C.15 D.不确定 6.下列哪一个方法可以判断出一个有向图是否有环。（A） A.深度优先遍历 B.拓扑排序 C.求最短路径 D.求关键路径 7.第7层有10个叶子结点的完全二叉树不可能有（B ）个结点。 A.73 B.234 C.235 D.236 8.分别用以下序列构造二叉排序树，与用其他三个序列构造的结果不同的是（B） A.（100,80,90,60,120,110,130） B.（100, 120, 110,130,80, 60,90） C.（100,60,80,90,120,110,130） D.（100,80, 60,90, 120, 130,110） 9.对一组数据（84，47，25，15，21）排序，数据的排列次序在排序过程中变化如下：（1）84 47 25 15 21 （2）15 47 25 84 21 （3）15 21 25 84 47（4）15 21 25 47 84则采用的排序方法是（B ） A.选择排序 B.起泡排序 C.快速排序 D.插入排序 10.对线性表进行折半查找时，要求线性表必须（D） A.以顺序方式存储 B.以顺序方式存储，且数据元素有序 一年级语文期末考试模拟试题 一、阅读： 1、大自然的邮票 春天的树上，长出嫩嫩的芽瓣。夏天的树上，挂满肥肥的叶片。秋天的树上，树叶涂满鲜红和金黄。冬天的树下，树叶落地化成土壤。落叶是大自然的邮票，把一年四季寄给你，寄给我，寄给大家。 （1）这一段话共有（）； （2）填空 a、一年有、、、四个季节。 b、春天的树上，芽瓣是；夏天的树上，叶片是；秋天的树叶颜色有和；冬天的树下，满地是。 c、大自然的邮票指。 2、人有两件宝 人有两件宝，双手和大脑。双手会做工，大脑会思考。 用手不用脑，事情做不好。用脑不用手，啥也做不好。 用手又用脑，才能有创造。一切创造靠劳动，劳动要用手和脑。 （一）这是一首儿歌，一共有（）话。 （二）填空： （1）人有两件宝是指和。做工靠，思考靠。 （2）做事情要用又用。这样才能。 （三）词语搭配： （1）认真地劳动（2）一双手指 辛勤地双手一根手表 勤劳的头脑一只小手 聪明的思考一块手套 3、夏天 初夏，石榴花开了。远看，那红色的花朵像一簇簇火焰。近看，一朵朵石榴花像一个个小喇叭。淡黄色的花蕊在风中摇动，就像一群仙女在翩翩起舞。 1、这段话共有（）句。 2、用“ ”划出第2、3两句句子。 3、石榴花在开放。它的花蕊是的， 花朵是的。 4、我喜欢石榴花是因为。 5、石榴花很多，从（）、（）等词可以看出。 4、斧子 老爷爷微笑着说：“孩子，你很诚实。我要把这两把斧子也送给你吧！”孩子说：“老爷爷，不是我的东西，我不要。”说完，拿着自己的斧子走了。 （1）老爷爷说了（）句话，孩子说了（）话。 （2）老爷爷送给孩子两把斧子，他有没有要？为什么？ （） （3）学了本文后，我们也要做个（）的孩子。 5、时钟花 小白兔没有钟，不知道时间，它请小山羊帮忙想办法。小山羊送给它三盆花。 太阳出来了，牵牛花开了，张开了小喇叭。中午，午时花开了，张开了笑脸。天黑了，夜来香开了，张开了小嘴请轻地唱歌。 1、这篇短文有（）段话。 2、小山羊送给小白兔什么花？ -----------、--------------、-------------- 3、（）花早晨开，（）花中午开，（）花晚上开。 6、金鱼 鱼池中的金鱼各种各样，有圆头的，有大眼的，也有尾巴像花朵的。颜色也不少，有金色、黑色、白色，也有白色和金色相间的，很好看。 它们非常活泼，常在水里游，有时互相追逐，有时一起游戏，加上色彩美丽，真令人喜 第二章算法分析 1.算法分析是计算机科学的基础 2.增长函数表示问题（n）大小与我们希望最优化的值之间的关系。该函数表示了该算法的时间复杂度或空间复杂度。增长函数表示与该问题大小相对应的时间或空间的使用 3.渐进复杂度：随着n的增加时增长函数的一般性质，这一特性基于该表达式的主项，即n 增加时表达式中增长最快的那一项。 4.渐进复杂度称为算法的阶次，算法的阶次是忽略该算法的增长函数中的常量和其他次要项，只保留主项而得出来的。算法的阶次为增长函数提供了一个上界。 5.渐进复杂度：增长函数的界限，由增长函数的主项确定的。渐进复杂度类似的函数，归为相同类型的函数。 6.只有可运行的语句才会增加时间复杂度。 7. O() 或者大O记法：与问题大小无关、执行时间恒定的增长函数称为具有O（1）的复杂度。 增长函数阶次 t(n)=17 O(1) t(n)=3log n O(log n) t(n)=20n-4 O(n) t(n)=12n log n + 100n O(n log n) t(n)=3n2+ 5n - 2 O(n2) t(n)=8n3+ 3n2O(n3) t(n)=2n+ 18n2+3n O(2n) 8.所有具有相同阶次的算法，从运行效率的角度来说都是等价的。 9.如果算法的运行效率低，从长远来说，使用更快的处理器也无济于事。 10.要分析循环运行，首先要确定该循环体的阶次n，然后用该循环要运行的次数乘以它。（n 表示的是问题的大小） 11.分析嵌套循环的复杂度时，必须将内层和外层循环都考虑进来。 12.方法调用的复杂度分析： 如：public void printsum(int count){ int sum = 0 ; for (int I = 1 ; I < count ; I++) sum += I ; System.out.println(sun); } printsum方法的复杂度为O（n）,计算调用该方法的初始循环的时间复杂度，只需把printsum方法的复杂度乘以该循环运行的次数即可。所以调用上面实现的printsum方法的复 杂度为O（n2）。 13指数函数增长> 幂函数增长> 对数函数增长 诚信应考 考出水平 考出风格 浙江大学城市学院 2013 — 2014 学年第 一 学期期末考试试卷 《 数据结构基础 》 开课单位： 计算分院 ；考试形式：闭卷；考试时间： 2014 年 1 月 14 日； 所需时间： 120 分钟 一．选择题 (本大题共 18 题，每题 1 分，共 18 分) 1. 数据的 包括集合、线性结构、树形结构和图形结构四种基本类型。 A. 存储结构 B. 逻辑结构 C. 基本运算 D. 算法描述 2. 中任何两个结点之间都没有逻辑关系。 A. 树形结构 B. 集合 C. 图形结构 D. 线性结构 3. 下面的程序段违反了算法的 原则。 void fun() { int x=2; while (!(x%2)) x=x*2; printf(“%d ”,x); } A. 健壮性 B. 确定性 C. 可行性 D. 有穷性 4. 算法分析的两个主要方面是 。 A. 空间复杂性和时间复杂性 B. 正确性和简明性 C. 可读性和文档性 D. 数据复杂性和程序复杂性 5. 用数组表示线性表的优点是。 A. 便于插入和删除操作 B. 便于随机存取 C. 可以动态地分配存储空间 D. 不需要占用一片相邻的存储空间 6. 循环链表的主要优点是。 A. 节约存储空间 B. 已知某个结点的位置后，能够很容易找到它的直接前驱 C. 在进行插入、删除运算时，能更好的保证链表不断开 D. 从表中的任意结点出发都能访问到任何一个结点 7. 可以用带表头附加结点的链表表示线性表，也可以用不带头结点的链表表示线性表，前者最主要的好处是。 A. 可以加快对表的遍历 B. 节省存储空间 C. 使空表和非空表的处理统一 D. 可以提高存取表元素的速度 8. 在头指针为h且表长大于1的单向循环链表中，指针p指向表中的某个结点，若p->next->next==h，则。 A. p指向头结点 B. p指向尾结点 C. *p的直接后继是头结点 D. *p的直接后继是尾结点 9. 线性表中，只有直接前驱而无后继的元素是。 A. 首元素 B. 尾元素 C. 中间元素 D. 全部元素 10. 以下不是栈的基本运算的是。 A. 删除栈顶元素 B. 删除栈底元素 C. 判断栈是否为空 D. 将栈置为空栈 11. 若用一个大小为6的数组来实现循环队列，且当前rear和fornt的值分别为1和4。从当前队列中删除一个元素，再加入两个元素后，rear和front的值分别为。 A. 3和5 B. 2和0 C. 0和2 D. 5和3 12. 最不适合用作链队的链表是_____。 A. 只带队头指针的非循环双链表 B. 只带队头指针的循环双链表 C. 只带队尾指针的循环双链表 D. 只带队尾指针的循环单链表 13. 最不适合用作栈的链表是。 A. 只有表头指针没有表尾指针的循环双链表 B. 只有表尾指针没有表头指针的循环双链表 C. 只有表尾指针没有表头指针的循环单链表 D. 只有表头指针没有表尾指针的循环单链表 14. 一个递归的定义可以用递归过程求解，也可以用非递归过程求解，但单从运行时间来看，通常递归过程比非递归过程效率。 A. 高 B. 低 C. 相同 D. 无法确定 开放英语(1)期末考试模拟试题(及答案) 一、语音知识 ( 每题1分, 共5分) 比较下列各组单词的读音, 从A、 B、 C、 D中找出一个其划线部分与其它三个划线部分发音不同的选题。 1.( ) A. fast B. water C. dance D. ask 2. ( ) A. cup B. but C. rush D. during 3. ( ) A. food B. soon C. cool D. book 4. ( ) A. hear B. earn C. dear D. near 5. ( ) A. article B. sharp C. quarter D. harm 二、词语填空 ( 每题1分, 共5分) 6. The boy looked, but he could not ________ anything. A. look B. looked C. look at D. see 7. Speak loudly, please. I can’t ________ you. A. listen B. listen to C. hear D. heard 8. Lei Feng liked helping ________. A. some B. another C. other D. others 9. He was late ________ the bus. A. because B. because of C. for D. but 10. She can ________ English well. A. say B. talk C. speak D. tell 二、判断改错题。 1. 位移法仅适用于超静定结构，不能用于分析静定结构。( × ) 2位移法未知量的数目与结构的超静定次数有关。( × ) .3 位移法的基本结构为超静定结构。( × ) 4. 位移法中角位移未知量的数目恒等于刚结点数。（×） 提示：与刚度无穷大的杆件相连的结点不取为角位移未知量。 1. 瞬变体系的计算自由度一定等零。 2. 有多余约束的体系一定是几何不变体系。 1、三刚片用三个铰两两相联不一定成为几何不变体系。（×） 2、对静定结构，支座移动或温度改变不会产生内力。（×） 3、力法的基本体系不一定是静定的。（×） 4、任何三铰拱的合理拱轴不一定是二次抛物线。（×） 5、图乘法不可以用来计算曲杆。（×） 6、静定结构的影响线全部都由直线段组成。（√） 7、多跨静定梁若附属部分受力，则只有附属部分产生内力。（×） 8、功的互等定理成立的条件是小变形和线弹性。（√） 9、力法方程中，主系数恒为正，副系数可为正、负或零。（√） 10.三个刚片用不在同一条直线上的三个虚铰两两相连，则组成的体系是无多余约束的几何不变体系。( √） 三、选择题。 1. 体系的计算自由度W≤0是保证体系为几何不变的 A 条件。 A.必要 B.充分 C.非必要 D. 必要和充分 1、图示结构中当改变B点链杆方向（不能通过A铰）时，对该梁的影响是（ d ） A、全部内力没有变化 B、弯矩有变化 C、剪力有变化 D、轴力有变化 2、图示桁架中的零杆为（ b ） A 、DC, EC, DE, DF, EF B 、DE, DF, EF C 、AF, BF, DE, DF, EF D 、DC, EC, AF, BF 4、右图所示桁架中的零杆为（ b A 、CH BI DG ,, B 、DG DE ,, C 、AJ BI BG ,, D 、BI BG CF ,, 5、静定结构因支座移动，（ b ） A 、会产生内力，但无位移 B 、会产生位移，但无内力 C 、内力和位移均不会产生 D 、内力和位移均会产生 7、下图所示平面杆件体系为（ b ） A 、几何不变，无多余联系 B 、几何不变，有多余联系 C 、瞬变体系 D 、常变体系 广东创新科技职业学院期末考试试题（标明A 卷、B 或C 卷） 2018 —2019 学年第二学期考试科目：《数据结构》 (闭（开）卷 90分钟) 院系____________ 班级____________ 学号___________ 姓名 __________ 一、选择题（每小题 2 分，共 40 分） 1.计算机识别、存储和加工处理的对象被统称为（）。 A ．数据 B ．数据元素 C ．数据结构 D ．数据类型 2.数据结构指的是数据之间的相互关系，即数据的组织形式。数据结构一般包括（）三方面内容。 A ．数据的逻辑结构、数据的存储结构、数据的描述 B ．数据的逻辑结构、数据的存储结构、数据的运算 C ．数据的存储结构、数据的运算、数据的描述 D ．数据的逻辑结构、数据的运算、数据的描述3．数据的逻辑结构包括（）。 A ．线性结构和非线性结构 B ．线性结构和树型结构 C ．非线性结构和集合结构 D ．线性结构和图状结构 4.（）的特征是：有且仅有一个开始结点和一个终端结点，且所有结点都最多只有一个直接前驱和一个直接后继。 A ．线性结构 B ．非线性结构 C ．树型结构 D ．图状结构 5. 评价一个算法时间性能的主要标准是（）。 A ．算法易于调试 B ．算法易于理解 C ．算法的稳定性和正确性 D ．算法的时间复杂度 6. 下述程序段①中各语句执行频度的和是（）。 s=0; ① for(i=1;i<=i;j++) s+=j; A ．n-1 B ．n C ．2n-1 D ．2n 7. 下面程序段的时间复杂度为（）。 for(i=0;i 九、期末考试试题及参考大案 古代汉语试题（A） 一.填空题（每空2分，10空，共20分） _ 1.许慎六书“假借”的定义____________________________。 2.本义_________________________________________。_ 3.异体字______________________________________。_ 4.文字学家辨别汉字的本义主要依靠汉字的_________。 5.我国第一部字典是东汉许慎着的_________________。 6.判断句是以___________________作谓语。 7.上古汉语判断句很少用判断词_______来表示。 8.教材第一篇文章《郑伯克段于鄢》选自《十三经》中的_______。 9.“莫”的本义是______，“莫”的今字是________。二．解释下列词语意义并指出词性（每题1分，共20题，共20分） 1.都城过百雉，国之害也。 雉： 2.昭王之不复，君其问诸水滨！ 诸： 3.一之为甚，其可再乎？ 其： 4.行李之往来，共其乏困。 行李： 5.必死是间，余收尔骨焉。 焉： 6.靡不有初，鲜克有终。 克： 7.贼民之主，不忠。 贼： 8.此车一人殿之，可以集事。 殿： 9.虽然，必告不谷。 不谷： 10.晋侯问嗣焉，称解狐。 称： 11.于是乘其车，揭其剑，过其友。过： 12齐王使使者问赵威后，书未发。 发： 13.见兔而顾犬，未为晚也。 顾： 14.赵诚发使尊秦昭王为帝，秦必喜，罢兵去。 诚： 15.老臣贱息舒祺，最少，不肖。 息： 16.君子于其言，无所茍而已矣。 茍： 宁夏大学期末考试试卷 2006至2007学年第 一 学期 考试科目 算法与数据结构 学分 学院 数计学院 年级 二年级 专业 软件工程 任课教师 肖军 试题来源 一、填空题（每空1分，计15分） 1、数据的存储结构是数据在计算机存储器里的表示，主要有四种基本存 储方法： 、 、散列和索引。 2、将下列复杂度由小到大重新排序，结果是 。 2n n! n 5 100000 n*log 2(n) 3、栈下溢是指在____________时进行出栈操作。 4、已知substr(s,i,len)函数的功能是返回串s 中第i 个字符开始长度为len 的子串，strlen(s)函数的功能是返回串s 的长度。若s=″ABCDEFGHIJK ″,t=″ABCD ″,执行运算substr(s,strlen(t), strlen(t))后的返回值为 。 5、在有向图中，以顶点v 为终点的边的数目称为v 的 。 6、产生冲突现象的两个关键字称为该散列函数的 。 7、在有 n 个叶子结点的哈夫曼树中，总结点数是_______ 。 8、在一个小根堆中，堆顶结点的值是所有结点中的 ，在一个大根堆中， 堆顶结点的值是所有结点中的 。 9、在线性表的散列存储中，处理冲突有 和 两种方法。 10、在一棵树中， 结点没有前驱结点。 11、已经一棵完全二叉树中共有653个结点，则该树中共有 个分支结点。 12、一种抽象数据类型包括数据类型定义和 两个部分。 二、选择题（每题2分，计30分） 1、栈和队列的共同点是（ ）。 A 、都是先进后出 B 、都是先进先出 C 、只容许在端点处插入和删除元素 D 、没有共同点 2、已知二叉树后根周游序列是DABEC ，中根周游序列是DEBAC ，它的先根周游序列是（ ） 题号 一 二 三 四 五 六 七 八 九 总分 得分 评阅人 学号 姓名javascript期末考试模拟题
结构力学2期末考试复习题
2017年数据结构期末考试题及答案A
数据库期末考试模拟试题及答案(一)
结构力学期末考试题库
数据结构期末考试题及答案
期末考试模拟试题2
结构力学期末考试试题及答案
《数据结构》期末考试题及答案
一年级语文期末考试模拟试题
数据结构复习资料,java数据结构期末考试
数据结构期末考卷13-14
开放英语期末考试模拟试题及答案
结构力学期末复习题及答案
《数据结构》期末考试试卷
古代汉语期末考试模拟题和答案
2006学年数据结构期末考试试卷
相关主题
文本预览