郑州大学现代远程教育
《数据结构》课程（本科）
学习指导书
郭纯一编
课程内容与基本要求
“数据结构”在计算机科学中是一门综合性的专业基础课。本课程将主要介绍数据结构的基本概念和术语、非数值计算中常用的数据结构（线性表、栈和队列、串、树和图）和基本技术（查找和排序方法）三大部分。
本课程要求学生在掌握线性表、栈和队列、串、树和二叉树、图等基本数据类型的基础上，会分析各种数据结构的特性，会根据应用需求为所涉及的数据合理选择适当的逻辑结构和存储结构，并能据此设计实现问题的算法；还应初步掌握算法的时间和空间效率的分析方法。
课程学习进度与指导
章节课程内容学时分配
学习指导
（均以课件学习为主）
第一章绪论4学时
重点掌握基本概念和时间复杂度的计算
方法
第二章*线性表10学时重点掌握顺序结构和链式结构表示线性表的方法和操作的实现；结合具体例子理解编程实现一个问题的2种方法
第三章栈和队列8学时重点掌握栈和队列的特点以及它们各自的存储表示，尤其是顺序栈和循环队列的实现；结合具体例子理解栈和队列的应用
第四章串2学时
重点掌握串的术语、串操作结果和不同存
储结构的特点
第七章*树和二叉树10学时重点掌握二叉树的定义、存储、性质、遍历算法（递归）及应用、线索化；掌握树和森林与二叉树的转换以及Huffman树和
第一章绪论
一、章节学习目标与要求
1、理解数据抽象和信息隐蔽原则
2、掌握所有的基本概念和术语、掌握时间复杂度的计算方法、会用C语言描述抽象数据类型和算法；能够熟练使用C语言编写程序
二、本章重点、难点
重点：基本概念和术语，C语言描述算法的方式，简单程序的时间复杂度的求法。难点：时间复杂度的计算方法和原则。
三、章节练习
（一）选择题：
1．具有线性结构的数据结构是__________。
A.图
B. 树
C. 集合
D. 栈
2．计算机算法是指________。
A.计算方法和运算结果
B.调度方法
C. 解决某一问题的有限运算系列
D. 排序方法
3．线性结构中，最后一个结点有________个后继结点。
A. 0
B. 1
C. 任意多
4. 算法分析的目的是________。
A. 找出数据结构的合理性
B. 研究算法中输入和输出的关系
C. 分析算法的效率以求改进
D.分析算法的可读性和可行性
5. 具有非线性结构的数据结构是__________。
A.图
B. 线性表
C. 串
D. 栈
6．算法具有5个特性：________、________、________、输入和输出。
A. 稳定性、确定性、可行性
B. 有穷性、确定性、可行性
C. 有穷性、安全性、可行性
D. 有穷性、确定性、可移植性
7．设n为正整数。则下面程序段的时间复杂度为________。
i=1; k=0;
while(i<=n-1){
@ k+=10*i;
i++;
}
(1) B. O(n) C. O(nlogn) D. O(n2)
8．设n为正整数。则下面程序段的时间复杂度为________。
k=0;
for(i=1;i<=n;i++){
for(j=i;j<=n;j++) @ k++;
}
(1) B. O(n) C. O(nlogn) D. O(n2)
（二）判断题：
1．在数据结构中，从逻辑上可以把数据结构分为动态结构和静态结构两大类。（）2．任何一个算法的设计取决于数据的逻辑结构，而算法的实现则依赖于所采用的存储结构。（）
3. 数据元素是数据的不可分割的最小单位。（）
4. 算法分析的两个主要方面是时间复杂度和空间复杂度。（）
第二章线性表
一、章节学习目标与要求
1、理解线性表的逻辑结构特性、顺序表和链表表示线性表的优缺点、循环链表和双向链表的特点。
2、掌握线性表的两种存储方式及其实现：熟练掌握顺序表和链表的创建、插入元素、删除元素以及定位等常用操作的实现算法并会求相应算法的时间复杂度。
二、本章重点、难点
重点：线性表的特点、两种表示方式及它们的运算实现，会求算法的时间复杂度。难点：单链表结构、特点及其实现
三、章节练习
（一）选择题：
1．顺序表是一种________的存储结构，单链表是________的存储结构。
A. 顺序存取
B. 随机存取
C. 索引存取
2．顺序表中第一个元素的起始存储地址为100，每个元素的长度为4，则第五个元素的起始地址是_______。
A. 105
B. 110
C. 116
D. 120
3．非空循环单链表(head为头指针)的尾结点（由指针p所指示）应满足________。
A. p->next==NULL;
B. p==NULL;
C. p->next==head;
D. p==head; 4．若在线性表的任何位置上插入元素的概率是相等的，那么在长度为n的顺序表中插入一个元素时需平均移动________个元素。
A. n
B. (n-1)/2
C.n/2
D. (n+1)/2
5．在带头结点的非空单链表中，头结点的位置由________指示，首元结点的存储位置由________指示，除首元结点外，其它任一元素结点的存储位置由________指示。
A. 头指针
B. 头结点的指针域的指针
C.前驱结点的指针域的指针
6. 单链表的头指针为p，若有头结点，则表空的判断条件是______________；
若不带头结点，则表空的判断条件是______________。
A. p==NULL
B. p->next==NULL
C. p->next->next==NULL
（二）判断题：
1．在单链表中插入或删除元素时是以结点的指针变化来反映逻辑关系的变化，因此不需要移动元素。（）
2．顺序表能够以元素在计算机内的物理位置的相邻性来表示线性表中元素之间的逻辑关系。（）
3. 在不带头结点的非空单链表中，首元结点的存储位置由头指针指示，除首元结点外，其它任一元素结点的存储位置由前驱结点的指针域的指针指示。（）（三）问答题：
1．若线性表要求以最快的速度存取而表中元素变动不大，则应采取什么存储结构（顺序或链式结构）为什么
2．若线性表经常做插入/删除操作，则应采取什么存储结构为什么
3. 在单链表中设置头结点有什么作用
（四）算法题：
1.设带头结点的单链表(L为头指针)中的数据元素递增有序。设计算法，将x插入到链表的适当位置上，并仍保持该表的有序性。
2.设顺序表va中的数据元素递增有序。设计算法，将x插入到顺序表的适当位置上，并仍保持该表的有序性。
3.设计算法，实现单链表的就地逆置，即利用原表的存储空间将线性表
（a
1,a
2
,…,a
n
）逆置为（a
n
,a
n-1
,…,a
1
）。
第三章栈和队列
一、章节学习目标与要求
1、理解用栈和队列解决实际问题的方法。
2、掌握栈和队列的定义以及特性、它们的2种不同的存储表示方法（特别是顺序栈和循环队列）以及各种常见操作（如入、出操作）在不同表示方式上的实现。
二、本章重点、难点
重点：栈和队列的定义、各种表示和实现方法，加深对线性结构的理解
难点：循环队列的表示及为解决循环队列队空、队满判断条件相同而使用的不同实现方式；能在具体问题中灵活运用栈和队列结构。
三、章节练习
（一）选择题：
1．一个栈的入栈序列是a,b,c,d,e,则栈的不可能的输出序列是________。
A. edcba
2．栈和队列的共同点是_______。
A. 都是后进先出
B. 都是先进先出
C. 都是只允许在端点处插入和删除元素
D.无共同点
3．一个队列的入队序列是{1,2,3,4},则队列的输出序列是______。
A. {4321}
B. {1234}
C. {1432}
D. {3241}
4．栈的入栈序列是1，2，…，n，输出序列为p1,p2,…pn,若p1=n, 则pi为_____。
A. i
B. n-i
C. n-i+1
D. 不确定
5．队列是限定在________进行插入，在________进行删除的线性表。
A. 队头
B. 队尾
C. 任意位置
6．循环队列中，设队列元素依次存放在Q[0..m]中，f、r分别指示队头元素位置和队尾元素的下一个位置，约定存储m个元素时为队满。则队列空的判定方法是_______,队列满的判定方法是_______。
==r B. (f+1)%(m+1)==r C. (r+1)%(m+1)==f D. (r+1)% m==f （二）判断题：
1．若用户无法估计所用队列的最大长度，则最好采用链队列。（）
2．在链队列上删除队头元素时，只需修改头结点中的指针，不必修改尾指针。（）
3. 栈是限定仅在栈顶进行插入或删除操作的线性表。（）
4. 队列是限定在队尾插入元素，在队头删除元素的线性表。（）
（三）问答与算法题：
1．对于一个栈，若输入序列依次为{A,B,C}, 试给出所有可能的输出序列。
2．假设将循环队列定义为：以整型域变量front和length分别指示循环队列中队头元素位置和队列中元素个数，指针elem指示存放队列元素的连续空间的首地址，写出相应的入队列和出队列的算法。
第四章串
一、章节学习目标与要求
1、理解串的抽象数据类型的定义以及相关术语、理解串在文本编辑中的作用。
2、掌握字符串的定义及各种基本操作的运算结果以及串的各种存储表示的特点。
二、本章重点、难点
重点：串的基本运算、串的各种存储表示和特点。继续加深对线性结构的理解难点：串的不同存储结构，区分它们和高级语言中串的存储方式的不同。
三、章节练习
（一）选择题：
1．设串s="I AM A STUDENT", 则其串长是______。
A. 13
B. 14
C. 15
D. 16
2. 设s ="HE IS A WORKER",t="WORKER"。则StrIndex(s,t,5)的返回值是_____。
A. 4
B. 5
C. 6
D. 9
E. 10
3. 串是一种特殊的线性表，其特殊性体现在_____。
A. 可以顺序存储
B. 数据元素是一个字符
C. 可以链接存储
D. 数据元素可以是多个字符
4.已知串s="ABCDEFGH’,则s的所有不同子串的个数为________。
A. 8
B. 9
C. 36
D. 37
5.设串s="I am a teacher.’,则s的第8个字符起、长度为7的子串为_______。
A. "teacher. "
B. "teacher"
C. "a teacher"
D. " teacher"
6. 设串s="student.",t=“good ",则执行StrInsert(s,1,t)后，s为____。
A. "good student."
B. "good student"
C. "goodstudent"
D. " good teacher"
（二）判断题：
1．空串和空格串是相同的。（）
2. 如果两个串含有相同的字符，则它们是相同的。（）
3. 串的基本操作和线性表的一样，都是以“单个元素”作为操作对象的。（）
4. 在串的链式存储结构中，结点大小与存储密度之间没有关系。（）
第七章树和二叉树
一、章节学习目标与要求
1、理解树、二叉树和森林的概念，理解线索化二叉树的特性、创建方法及在线索二叉树上寻找某结点的前驱和后继的方法；理解树与森林的存储方法。
2、掌握二叉树的性质及表示；掌握二叉树的各种遍历方法（尤其是递归形式的）以及遍历在实际问题中的应用；掌握树及森林与二叉树的转换及遍历方式的对应；掌握Huffman树的构造方法以及构造Huffman编码的方法。
二、本章重点、难点
重点：二叉树的性质（及证明）、存储结构及各种遍历算法，二叉树的线索化过程，树和森林与二叉树的转换关系，Huffman树及Huffman编码的构造方法
难点：各种遍历算法的递归实现以及在具体问题中能灵活运用遍历思想解题
三、章节练习
（一）选择题：
1．下列关于二叉树的说法中，正确的有_______。
A. 二叉树的度为2
B. 二叉树的度可以小于2
C.二叉树中至少有一个结点的度为2
D. 二叉树中任一个结点的度都为2 2．任何一棵二叉树的叶子结点在先、中、后序遍历序列中的相对次序_______。
A. 不发生改变
B. 发生改变
C. 不能确定
D. 以上都不对3．下面几个符号串编码集合中，不是前缀编码的是_____。
A. {0，10，110，1111}
B. {11，10，001，101，0001}
C. {00，010，0110，1000}
D. {b,c,aa,ac,aba,abb,abc}
4．二叉树按某种顺序线索化后，任意结点均有指向其前驱和后继的线索，这种说法_______。
A. 正确
B. 不正确
C. 无法确定
（二）判断题：
1.哈夫曼树是带权叶子数目固定的二叉树中带权路径长度最小的。（）
2.根据二叉树的定义，具有3个结点的二叉树有5种不同的形态。（）
3.深度为k的完全二叉树至少有2k-1个结点，至多有2k－1个结点。（）
4. 具有n个结点的满二叉树，其叶子结点个数为
21
n
个。（）5. 在哈夫曼树中，通常权值较大的结点离根较远。（）（三）问答题：
1．下图所示森林转化为相应的二叉树，并在其上标出中序全线索。
2．证明：深度为k的二叉树上至多有2k-1个结点（k≥1）。
3. 证明：任何一棵满二叉树中的分支数B满足B=2(n
0－1)，其中n
为叶子结点
个数。
4. 以数据集{15，3，14，2，6，9，16，17}为叶子的权值构造Huffman树，画出此树并计算其带权路径长度。
（四）算法题：
1. 假设二叉排序树（t为指向根结点的指针）中各元素值均不相同，设计一个递归算法按递增顺序输出树上各元素值。
2．编写递归算法, 交换二叉链表存储的二叉树中每个结点的左、右子树。
3. 编写递归算法，求以二叉链表存储的二叉树的深度。
4. 设计递归算法计算以二叉链表存储的二叉树的叶子结点数目。
第八章图
一、章节学习目标与要求
1、理解图的基本概念和术语。
2、掌握图的邻接矩阵和邻接表2种表示方法；掌握图的两种遍历算法及其求解连通性问题的方法；掌握用Prim算法和Kruskal算法构造最小生成树的过程和性能分析；掌握AOV网的拓扑排序方法 (不要求算法)，掌握用Dijkstra方法求解单源最短路径问题的方法(不要求算法)。
二、本章重点、难点
重点：图的数组表示法和邻接表表示法存储结构以及图的两种遍历方式，求最小生成树的两种方法，AOV网的拓扑排序方法，掌握单源最短路径的求法
难点：图的两种遍历算法的实现以及在图的连通性问题中的应用
三、章节练习
（一）选择题：
1. 4个顶点的无向完全图有_______条边。
A. 6
B. 12
C. 16
D. 20
2．无向图的邻接矩阵是一个_____。
A. 对称矩阵
B. 零矩阵
C. 对角矩阵
D. 上三角矩阵
3．图的广度优先遍历算法类似于二叉树的_____，图的深度优先遍历算法类
似于二叉树的_____。
A. 先序遍历
B. 中序遍历
C. 后序遍历
D. 层序遍历
4. 对________，用Prim算法求最小生成树较为合适，而Kruskal算法适于构造____________图的最小生成树。
A. 完全图
B. 连通图
C. 稀疏图
D.稠密图
5. 对于含n个顶点、e条边的无向连通图，利用Prim算法构造最小生成树的时间复杂度______________，用Kruskal算法构造最小生成树的时间复杂度为______________。
A. O(n)
B. O(n2)
C. O(e)
D. O(eloge) F. O(e2)
（二）判断题：
1. 若从无向图的一个顶点出发进行广度优先遍历可访问到图中所有顶点，则该图一定是连通图。 （ ）
2. 若从无向图的一个顶点出发进行深度优先遍历可访问到图中所有顶点，则该图一定是连通图。 （ ）
3. 任何有向图的顶点都可以排成拓扑有序序列，而且拓扑序列不唯一。 （ ）
4. 有n 个顶点和n-1条边的无向图一定是生成树。 （ ）
5. 一棵有n 个顶点的生成树有且仅有n-1条边。 （ ）
6.连通分量是无向图的极大连通子图，而生成树是无向图的极小连通子图。（ ） （三）问答及算法题：
1. 一个图的邻接矩阵=??
??
?
?????110101010，该图有多少个顶点如果是有向图，该图共有多少条弧如果是无向图，该图共有多少条边
2.已知如右图所示的有向图，写出该图的: (1)邻接矩阵 (2）一个可能的拓扑有序序列 （3）写出从1出发的深度优先遍历序列 （4）写出从5出发的广度优先遍历序列。
3. 假设有5项活动C1～C5，每项活动要求的前驱活动如下：
C1：无； C2：C1，C3； C3：C1； C4：C3，C5 C5：C2；
试根据上述关系，画出相应的有向图，再写出一个拓扑排序序列。 4. 基于图的深度优先遍历策略写一算法，判断以邻接表方式存储的无向图中连通分量的个数。
第九章 查找
一、章节学习目标与要求
1、理解各种查找表的定义、各种查找方法的思想以及构造查找表所依据的原则。
2、掌握线性表表示的静态查找表的顺序查找和折半查找算法及其性能分析方法；掌握二叉排序树的创建、查找、插入、删除算法及其性能分析方法；掌握AVL 树的平衡化旋转方法及其性能分析；掌握B-树的插入和删除时结点的分裂和合并方法；掌握Hash法的查找、构造方法平均查找长度的计算方法。
二、本章重点、难点
重点：各种树结构表示的动态查找表和Hash表的构造方法
难点：二叉排序树的删除、AVL树的旋转处理、B-树的插入和删除、Hash法的构造以及各种查找表的平均查找长度的计算方法
三、章节练习
（一）选择题：
1. ________二叉排序树可得到一个关键字的有序序列。
A. 先序遍历
B. 中序遍历
C. 后序遍历
D. 层序遍历
2．用链地址法处理冲突构造的散列表中，每个地址单元所链接的同义词表中结点的_____相同。
A. 关键字
B. 元素值
C. 散列地址
D. 含义
3．利用折半查找方法在长度为n的有序表中查找一个元素的平均查找长度是______。
(n2) (nlogn) (n) D. O(logn)
4．散列表的装填因子越大，则发生冲突的可能性就________。
A. 越小
B. 越大
C. 不确定
5．线性表中共有256个元素，采用分块查找，若查找每个元素的概率相等，用顺序查找确定结点所在的块，每块有_____个元素时查找效率最佳。
A. 16
B. 20
C. 25
D. 256
6．用折半查找对长度为7的有序表进行查找，则等概率下查找成功时的平均查找长度为______。
A. 15/7
B. 17/7
C. 18/7
D. 19/7
7．有序表（1，32，41，45，62，75，77，82，95，100），使用折半查找关键字
为95的元素时，需要经过____次比较后才能查找成功。 A. 2 B. 3 C. 4 （二）判断题：
1. 折半查找和二叉排序树的查找时间性能一样。 （ ）
2. 在任意一棵非空的二叉排序树中，删除某结点后又将其插入，则所得的二叉排序树与删除前的二叉排序树形态相同。 （ ）
3. 根据B-树的定义，在9阶B-树中，除根以外的任何一个非叶子结点中的关键字数目均在5～9之间。 （ ）
4.折半查找时，要求线性表必须是有序的且以顺序结构存储。 （ ） （三）问答题：
1. 设有一组关键字序列{19，1，23，14，55，20，84，27，68，11，40}， （1） 按表中元素顺序构造一棵二叉排序树，画出这棵树，并求其在等概率情 况下查找成功时的平均查找长度。
（2）从空树开始，按表中元素顺序构造一棵2_3树(3阶B_树)，若此后再删除55，84，画出每一步执行后2_3树的状态。
2. 设散列函数H(key)=key MOD 7,用线性探测再散列法解决冲突。对关键字序列{ 13，28，72，5，16，8，7，11 }在地址空间为0-10的散列区中建散列表，画出此表，并求等概率情况下查找成功时的平均查找长度。
3. 关键字序列：13，28，72，5，16，18，7，11，24，h (key) = key mod 11,
表长为11，用线性探测再散列处理冲突，试填写下表并计算每个关键字的比较次数和等概率情况下查找成功时的平均查找长度。
4. 在地址空间为0-16的散列区中，对以下关键字序列(Jan,Feb,Mar,Apr,May, June,July,Aug,Sep,Oct,Nov,Dec)按链地址法处理冲突构造散列表，设散列函数H(x)=i/2,其中i 为关键字中第一个字母在字母表中的序号。画出该散列表并求
哈希表
比较次数 ASL=
在等概率情况下查找成功时的平均查找长度。
第十章排序
一、章节学习目标与要求
1、理解排序相关的定义以及排序方法的各种分类，理解各种排序方法的基本思想和依据原则。
2、掌握内部排序的基本概念和性能分析方法；掌握插入排序、交换排序、选择排序等内排序的方法及其性能分析方法。
二、本章重点、难点
重点：各类内部排序方法所依据的原则、特点及典型算法。
难点：希尔排序、快速排序、堆排序
三、章节练习
（一）选择题：
1. 下列方法中，________是稳定的排序方法。
A．堆排序 B. 希尔排序 C. 快速排序 D. 折半插入排序
2. 设有1000个无序的元素，希望用最快的速度选出其中前20个最大的元素，最好用________排序方法。
A. 冒泡排序
B. 快速排序
C. 堆排序
D. 希尔排序
3．下列序列中，______是堆。
A. {12，35，20，60，40，30}
B. {100，85，120，38，10，9，36}
C. {1，5，6，24，7，3，4 }
D. {38，24，15，20，30，46}
4．在待排序的元素序列基本有序时，效率最高的排序方法是__ ____。
A.插入排序
B.选择排序
C.快速排序
D. 归并排序
5．在下列排序方法中，某一趟结束后未必能选出一个元素放在其最终位置上的是_______。
A. 堆排序
B. 起泡排序
C. 快速排序
D. 直接插入排序
6．对序列{22,86,19,49,12,30,65,35,18}进行一趟排序后得到的结果为{18,12,19,22,49,30,65,35,86}，则其使用的排序方法为_______。
A. 插入排序
B. 选择排序
C. 快速排序
D. 起泡排序
7. 下列方法中，________算法的时间复杂度为O(n2)。
A. 堆排序
B. 希尔排序
C. 快速排序
D. 直接插入排序
8. 对n个记录的序列进行堆排序，最坏情况下的时间复杂度为______。
A. O(logn)
B. O(nlogn)
C. O(n) (n2)
（二）判断题：
1.快速排序的速度在所有排序方法中是最快的，而且所需的附加空间也最少。（）
2.对一个堆按层次遍历，不一定能得到一个有序序列。（）
3.由于希尔排序的最后一趟与直接插入排序过程相同，所以前者一定比后者花费的时间多。（）
4.快速排序算法在待排序数据有序时最不利于发挥其长处。（）（三）问答题：
1.在快速排序过程中，通常取序列中的第1个记录作为枢轴，以它为“分界线”重排其余记录。但当初始记录序列按关键字有序或基本有序时，快速排序将蜕化为起泡排序，为改进之，应如何选取枢轴记录
2.判断以下序列是否是堆，若不是，把它调整为堆（要求记录交换次数最少），写出调整后的序列。
1）{ 5，26，20，60，80，35，53，70 }
2）{ 26，33，35，29，19，12，22 }
3.已知关键字序列{70，83，100，65，10，9，7，32}，写出直接插入排序和快速排序每一趟结束时的关键字状态。
4.设关键字集合为{10，2，14，8，12，13}，
(1)写出用希尔排序方法对序列排序时每一趟结束时的关键字状态。
(2)用堆排序方法对其从小到大排序，画出堆排序的初态、建堆和排序过程中重建堆的过程。
考试模拟题
客观题部分
一、单项选择题：（每空2分，共20分）
1.单链表是线性表的一种________的存储结构。
A. 顺序存取
B. 随机存取
C. 索引存取
2.栈和队列的共同点是________。
A. 都是后进先出
B. 都是先进先出
C. 都是只允许在端点处插入和删除元素
D.无共同点
3.设s="HE IS A WORKER",t="WORKER"。则
index(s,t,5)的返回值是________。
A. 4
B. 5
C. 6
D. 9
E. 10
4.串是一种特殊的线性表，其特殊性体现在________。
A. 可以顺序存储
B. 数据元素是一个字符
C. 可以链接存储
D. 数据元素可以是多个字符
5．树最适合用来表示_________。
A. 有序数据元素
B. 无序数据元素
C．元素之间具有分支层次关系的数据 D. 元素之间无关联的数据6．4个顶点的无向完全图有__________条边。
A. 6
B. 12
C. 16
D. 20
7．散列表的装填因子越大，则发生冲突的可能性就_________。
A. 越小
B. 越大
C. 不确定
8. 在长度为n的有序表中折半查找一个元素的平均查找长度是_____。
(n2) (nlogn) (n) D. O(logn)
9.下列方法中，________是不稳定的排序方法。
A. 折半插入排序
B. 直接插入排序
C. 冒泡排序
D. 堆排序
10．________二叉排序树可得到一个关键字的有序序列。
A. 先序遍历
B. 中序遍历
C. 后序遍历
D. 层序遍历
二、是非题：（每题1分，共10分）（说明：正确的选“A”,错误选“B”）
1．线性表的顺序存储结构优于链式存储结构。（）
2．空串和空格串是相同的。（）
3．图结构中，每个结点的前驱和后续都可以有任意多个。（）
4．快速排序算法在待排序数据有序时最不利于发挥其长处。（）
5．连通网的最小生成树是唯一的。（）
6．栈是FIFO的线性表。（）
7．由二叉树的先序和后序遍历序列不能唯一确定这棵二叉树。（）
8．若从无向图的一个顶点出发进行广度优先遍历可访问到图中的所有顶点，则该图一定是连通图。（）9．折半查找方法要求查找表必须是关键字的有序表，但是对存储结构没有限制。（）10．在一棵非空二叉树的中序遍历序列中，根结点的右边只有其右子树上的所有结点。（）
主观题部分
一、简答题：（50分）
1. 若线性表要求以最快的速度存取而表中元素变动不大，则应采取什么存储结构（顺序或链式结构）为什么（10分）
2.将下图所示森林转化为二叉树并在其上标出中序全线索。（10分）
3.已知如右图所示的有向图，写出该图的:
(1)邻接矩阵 (2）一个可能的拓扑有序序列。（10分）
4．设散列函数H(key)=key MOD 7,用线性探测再散列法解决冲突。对关键字序列{ 13，28，72，5，16，8，7，9，11，29 }在地址空间为0-10的散列区中建散列表，画出此表，并求等概率情况下查找成功时的平均查找长度。（10分）
5．对于序列{ 26，33，35，29，19，12，22 }，
（1）判断它是否是堆，若是，写出其是大顶堆还是小顶堆；若不是，把它调整为堆，写出调整的过程和调整后的序列。（5分）（2）写出对该序列进行直接插入排序每一趟结束时的关键字状态。（5分）
二、算法设计题：（20分）
1、编写递归算法，计算二叉链表存储的二叉树的结点数目。（10分）
2、基于图的深度优先遍历策略写一算法，判断以邻接表方式存储的无向图中连通分量的个数。（10分）
附：答案或答案要点
第一章章节练习答案
（一）选择题：
1．D 2．C 3．A 4．C 5．A 6．B 7．B 8．D
（二）判断题： 1．× 2．√ 3. × 4．√
第二章章节练习答案
（一）选择题： 1．B, A 2．C 3．C 4．C 5．A, B, C , A （二）判断题： 1．√ 2．√ 3．√
（三）问答题：
1．应采用顺序结构。因为顺序表是随机存取的存储结构，在顺序表中存取任何元素所花的时间都一样。而链表是顺序存取的存储结构。
2．应采用链式结构。因为在链表中是以结点的指针变化来反映逻辑关系的变化，因此不需要移动元素，效率高。
3．头结点在位置上可视为首元结点的前驱，则做插入/输出操作时，i=1（即插入或删除的位置是1）时不需要做特别处理，否则i=1时需要修改头指针。（四）算法题：
1． status insert_L (LinkList L, ElemType x)
{/*带头结点*/
LinkList p,s;
for (p=L; p->next && p->next->data
s=(LinkList )malloc(sizeof(LNode));
if (!s) return OVERFLOW;
s->data=x; s->next=p->next; p->next=s;
return OK;
}
2．status insert_Sq(SqList *va,ElemType x)
数据结构 一、单选题 1. 计算机算法指的是（b ）。 A．程序B．问题求解步骤的描述C．调度方法D．排序方法 2. 以下数据结构中，（a ）个是非线性数据结构。 A．树B．字符串C．队D．栈 3. 对于顺序存储的线性表，访问元素和插入元素的时间复杂度分别为：（c ）。 A．O(n) O(n) B．O(n) O(1) C．O(1) O(n) D．O(1) O(1) 4. 在单链表指针为p的结点之后插入指针为s的结点，正确的操作是（b ）。 A.p->next=s;s->next=p->next B.s->next=p->next; p->next=s C.p->next=s;p->next=s->next D.p->next=s->next; p->next=s 5. n个顶点的有向图中,含有向边的数目最多为( d ) A．n-1 B．n C．n(n-1)/2 D．n(n-1) 6. 循环队列存储在数组A[0..m]中，则入队时的操作为（ d ） A．rear=rear+1 B．rear=(rear+1)mod(m-1) C．rear=(rear+1)mod m D．rear=(rear+1)mod(m+1) 7. 字符串?ababaabab?的next函数为（d ） A.011232232 B.012341234 C.011122334 D. 011234234 8. 若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数为（ b ）A．9 B．11 C．15 D．不确定 9. 设有数组A[i,j]，数组的每个元素长度为3字节，i的值为1到8，j的值为1到10，数组从内存首地址BA开始顺序存放，当以列为主序存放时，元素A[5,8]的首地址为（ b ）。A．BA+141 B．BA+180 C．BA+222 D．BA+225 10. n个顶点的带权无向连通图的最小生成树包含(b )个顶点 A．n-1 B．n C．n/2 D．n+1 11．有关二叉树的下列说法正确的是（ b ） A．二叉树的度为2 B．一棵二叉树的度可以小于2 C．二叉树中至少有一个结点的度为2 D．二叉树中任何一个结点的度都为2 12．关键路径是AOE网中（ a ）。 A．从源点到汇点的最长路径B．从源点到汇点的最短路径 C．最长回路 D．最短路径（从源点到汇点的所有路径中，经过弧的数目最多的路径） 13．若查找每个记录的概率相等，则在具有n个记录的连续文件中采用顺序查找查找一个记录，其平均查找长度ASL为（c）。 A．(n-1)/2 B．n/2 C．(n+1)/2 D．n 14．就平均性能而言，目前最好的内部排序方法是（d ） A．冒泡排序B．希尔排序C．堆排序D．快速排序 15．已知广义表LS=((a,b,c),(d,e,f))，运用head和tail函数取出LS中原子e的运算是（d ）A．head(tail(LS)) B．tail (head (LS) C．head(tail(head(tail(LS)))) D．head(tail(tail (head (LS)))) 17．在n个结点的顺序表中，算法的时间复杂度是O（1）的操作是：( a ) A. 访问第i个结点（1≤i≤n）和求第i个结点的直接前驱（2≤i≤n） B. 在第i个结点后插入一个新结点（1≤i≤n）
一、单选题（每题 2 分，共20分） 1. 1.对一个算法的评价，不包括如下（B ）方面的内容。 A．健壮性和可读性B．并行性C．正确性D．时空复杂度 2. 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. 3.对线性表，在下列哪种情况下应当采用链表表示？( ) A.经常需要随机地存取元素 B.经常需要进行插入和删除操作 C.表中元素需要占据一片连续的存储空间 D.表中元素的个数不变 4. 4.一个栈的输入序列为1 2 3，则下列序列中不可能是栈的输出序列的是 ( C ) A. 2 3 1 B. 3 2 1 C. 3 1 2 D. 1 2 3 5. 5.AOV网是一种（）。 A．有向图B．无向图C．无向无环图D．有向无环图 6. 6.采用开放定址法处理散列表的冲突时，其平均查找长度（）。 A．低于链接法处理冲突 B. 高于链接法处理冲突 C．与链接法处理冲突相同D．高于二分查找 7.7.若需要利用形参直接访问实参时，应将形参变量说明为（）参数。 A．值B．函数C．指针D．引用 8.8.在稀疏矩阵的带行指针向量的链接存储中，每个单链表中的结点都具 有相同的（）。 A．行号B．列号C．元素值D．非零元素个数 9.9.快速排序在最坏情况下的时间复杂度为（）。 A．O(log2n) B．O(nlog2n) C．0(n) D．0(n2) 10.10.从二叉搜索树中查找一个元素时，其时间复杂度大致为( )。 A. O(n) B. O(1) C. O(log2n) D. O(n2) 二、二、运算题（每题 6 分，共24分） 1. 1.数据结构是指数据及其相互之间的______________。当结点之间存在M 对N（M：N）的联系时，称这种结构为_____________________。 2. 2.队列的插入操作是在队列的___尾______进行，删除操作是在队列的 ____首______进行。 3. 3.当用长度为N的数组顺序存储一个栈时，假定用top==N表示栈空，则 表示栈满的条件是___top==0___(要超出才为满)_______________。 4. 4.对于一个长度为n的单链存储的线性表，在表头插入元素的时间复杂度 为_________，在表尾插入元素的时间复杂度为____________。
结构力学》第01章在线测试剩余时间：53:32 答题须知：1、本卷满分20分。 2、答完题后，请一定要单击下面的“交卷”按钮交卷，否则无法记录本试卷的成绩。 3、在交卷之前，不要刷新本网页，否则你的答题结果将会被清空。 第一题、单项选择题（每题1分，5道题共5分） 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、四个 第二题、多项选择题（每题2分，5道题共10分） 1、下列哪些约束可以约束杆端的转动 A、可动铰支座 B、固定铰支座 C、定向支座 D、滑动支座
E、固定端 2、下列哪种情况应按空间结构处理 A、所有杆件的轴线都位于同一平面内，荷载与该平面垂直 B、所有杆件的轴线都不位于同一平面内 C、所有杆件的轴线都位于同一平面内，荷载也作用在该平面内 D、所有杆件的轴线都位于同一平面内，荷载与该平面平行 E、荷载不作用在结构的平面内 3、为了保证结构既经济又安全，要计算结构 A、强度 B、刚度 C、稳定性 D、内力 E、位移 4、铰结点的受力特点是 A、可以传递轴力 B、可以传递剪力 C、不能传递力矩 D、不能传递力 E、能传递力矩 5、定向支座的特点是 A、允许杆端沿一定方向自由移动而沿其它方向不能移动 B、不允许杆端转动 C、只有一个反力 D、有一个反力和一个反力偶
《结构力学》第01章在线测试 《结构力学》第01章在线测试剩余时间：38:46 答题须知：1、本卷满分20分。 2、答完题后，请一定要单击下面的“交卷”按钮交卷，否则无法记录本试卷的成绩。 3、在交卷之前，不要刷新本网页，否则你的答题结果将会被清空。 第一题、单项选择题（每题1分，5道题共5分） 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、四个 第二题、多项选择题（每题2分，5道题共10分） 1、下列哪种情况不是平面结构 A、所有杆件的轴线都位于同一平面内，荷载也作用在该平面内 B、所有杆件的轴线都位于同一平面内，荷载与该平面垂直 C、所有杆件的轴线都位于同一平面内，荷载与该平面平行 D、所有杆件的轴线都不位于同一平面内 E、荷载不作用在结构的平面内 2、对结构进行几何组成分析，是为了 A、保证结构既经济又安全 B、保证结构不致发生过大的变形 C、使结构美观实用 D、保证结构不发生刚体运动 E、保证结构中各构件不发生相对刚体运动 3、铰结点的受力特点是 A、可以传递轴力 B、可以传递剪力 C、不能传递力矩
郑州大学远程教育学院机械设计基础作业答案 YKK standardization office【 YKK5AB- YKK08- YKK2C- YKK18】
郑州大学现代远程教育《机械设计基础》课程考核要 求 一．作业内容 （一）.选择题（在每小题的四个备选答案中选出一个正确的答案，并将正确答案的号码填在题干的括号内，每小题1分，共20分） 1．在平面机构中，每增加一个高副将引入。 （ B ） A．0个约束 B．1个约束 C．2个约束 D．3个约束 2.无急回特性的平面四杆机构，其极位夹角为。 ( B ) A.θ?0 3．在圆柱凸轮机构设计中，从动件应采用从动件。 （ B ） A．尖顶 B．滚子 C．平底 D．任意
4．齿轮的齿形系数 Y只与有关。 F （ B ） A．模数 B．齿形 C．传动比 D．中心距 5．闭式硬齿面齿轮传动中，齿轮的主要失效形式为。 （ C ） A．齿面胶合 B．齿面磨损 C．齿根断裂 D．齿面点蚀 6．在其它条件相同的蜗杆传动中，蜗杆导程角越大，传动效 率。（ B ） A．越低 B．越高 C．不变 D．不确定 7、带传动正常工作时不能保证准确的传动比是因为 _____。 （ C ） A.带的材料不符合胡克定律 B.带容易变形和磨损 C.带的弹性滑动. D带在带轮上打滑 8、链传动设计中，当载荷大，中心距小，传动比大时，宜选用_____。（ B ）
A 大节距单排链 B 小节距多排链 C 小节距单排链 D 大节距多排链 9、平键联接选取键的公称尺寸b × h的依据是_____。 （ D ） A.轮毂长 B.键长 C.传递的转矩大小 D.轴段的直径 10、齿轮减速器的箱体和箱盖用螺纹联接，箱体被联接处的厚度不太 大，且经常拆装，一般用联接. （ C ） A.螺栓联接 B.螺钉联接 C. 双头螺柱联接 11、自行车的前轮轴是。 （ C ） A．转轴 B．传动轴 C．心轴 D．曲轴 12、通常把轴设计为阶梯形的主要目的在于。 （ C ） A．加工制造方便 B．满足轴的局部结构要求 C．便于装拆轴上零件 D．节省材料
数据结构试题? 一、?单选题（每题 2 分，共20分） 1.1.???? 对一个算法的评价，不包括如下（ B ）方面的内容。 A．健壮性和可读性B．并行性 C．正确性 D．时空复杂度 2.2.???? 在带有头结点的单链表HL中，要向表头插入一个由指针p指向的结点， 则执行( A )。 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.3.???? 对线性表，在下列哪种情况下应当采用链表表示？( B ) A.经常需要随机地存取元素 B.经常需要进行插入和删除操作 C.表中元素需要占据一片连续的存储空间 D.表中元素的个数不变 4.4.???? 一个栈的输入序列为 1 2 3，则下列序列中不可能是栈的输出序列的是 ( C ) A. 2 3 1 B. 3 2 1 C. 3 1 2 D. 1 2 3 5.5.???? AOV网是一种（ D ）。 A．有向图 B．无向图 C．无向无环图D．有向无环图 6.6.???? 采用开放定址法处理散列表的冲突时，其平均查找长度（ B ）。 A．低于链接法处理冲突 B. 高于链接法处理冲突 C．与链接法处理冲突相同 D．高于二分查找 7.7.???? 若需要利用形参直接访问实参时，应将形参变量说明为（ D ）参数。 A．值 B．函数 C．指针 D．引用 8.8.???? 在稀疏矩阵的带行指针向量的链接存储中，每个单链表中的结点都具有 相同的（ A ）。 A．行号B．列号 C．元素值 D．非零元素个数 9.9.???? 快速排序在最坏情况下的时间复杂度为（ D ）。 A．O(log 2n) B．O(nlog 2 n) C．O(n) D．O(n2) 10.10. 从二叉搜索树中查找一个元素时，其时间复杂度大致为( C )。 A. O(n) B. O(1) C. O(log 2 n) D. O(n2) 二、运算题（每题 6 分，共24分） 1. 1.?数据结构是指数据及其相互之间的_对应关系(联系)。当结点之间存在M对N（M： N）的联系时，称这种结构为图（或图结构）。 2. 2.队列的插入操作是在队列的__队尾___进行，删除操作是在队列的_对头_进行。 3. 3.??当用长度为N的数组顺序存储一个栈时，假定用top==N表示栈空，则表示栈 满的条件是_top==0__。 4. 4.???对于一个长度为n的单链存储的线性表，在表头插入元素的时间复杂度为
大学现代远程教育《结构力学》课程学习指导书(本科) 作者：樊友景 大学土木工程学院 结构力学课程学习指导书
第一章 绪论 一、本章学习目标： 1、了解结构力学的任务，及其与其他课程间的关系、常见杆件结构的类型。 2、掌握结构计算简图的概念和确定计算简图的原则。 3、掌握杆件结构的支座分类及结点分类。掌握杆件结构的支座和结点的受力性能和 约束性质。。 二、本章重点、要点： 1、识记：各种支座能产生的反力，全铰与半铰的区别，计算简图的含义，确定计算 简图的原则。 2、领会：铰结点、刚结点和组合结点的受力特征和变形特征。 第二章 平面体系的几何组成分析 一、本章学习目标： 1、理解几何不变体系、几何可变体系、刚片、自由度和计算自由度、约束等概念并理解瞬变体系和常变体系的区别。 2、掌握无多余约束的几何不变体系的几何组成规则，并能运用这些规则分析体系的几何组成。 3、理解体系的几何特性与静力特性。 二、本章重点、要点： 1、识记：几何不变体系、几何可变体系、常变体系、瞬变体系的概念；可用作建筑 结构的体系；自由度、刚片、约束的概念；把复铰折算成单铰的算式；无多余约束的几何不变体系的组成规则；二元体的概念。 2、领会：点与刚片的自由度；连杆、单铰的约束作用；虚铰的概念及其约束作用。 静定结构的几何特性和静力特性。 3、应用：体系的几何组成分析。 三、本章练习题： 1、判断题 1.1多余约束是体系中不需要的约束。 （ ） 1.2瞬变体系在很小的荷载作用下会产生很大的力，所以不能作为结构使用。（ ） 1.3两根链杆的约束作用相当于一个单铰。 （ ） 1.4每一个无铰封闭框都有三个多余约束。 （ ） 1.5连接四个刚片的复铰相当于四个约束。 （ ） 1.6图示体系是由三个刚片用三个共线的铰ABC 相连，故为瞬变体系。 （ ） 1.7图示体系是由三个刚片用三个共线的铰ABC 相连，故为瞬变体系。 （ ） 题1.7图 题1.6图
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 .没有共同点
郑州大学现代远程教育《机电一体化技术》 课程考核要求 说明：本课程考核形式为提交作业，完成后请保存为WORD 2003版本格式的文档，登陆学习平台提交，并检查和确认提交成功（能够下载，并且内容无误即为提交成功）。 一．作业要求 请任选一题，认真、独立完成。 二．作业内容 题目一送料小车运行控制系统设计 1. 设计目的：通过对送料小车运行的控制系统设计，使学生们掌握控制系统硬件设计及软件编程方法，具有灵活运用相关知识的能力； 2. 设计内容及要求：下图为送料小车运行过程图。当小车处于后端，按下起动按钮，小车向前运行，压下前限位开关后，翻斗门打开；7s后小车向后运行，到后端，即压下后限位开关后，打开小车底门，完成一次工作循环。 小车运行过程图 设计要求：能够控制小车的远行，并具有以下几种方式：(1)手动；(2)自动单周期，即小车住复运行一次后停在后端等待下次起动；(3)自动连续，即小车起动后自动往复运行；(4)单步运行，即每步动作都要起动；(5)往复运行2次即小车往复运行2次后，回到后端停下，等待起动。 3. 设计成果： 1）相关硬件电路图 2）相关程序 设计成果： 1）相关硬件电路图：
深入了解和分析小车运料控制系统的控制要求，画出工序图。 1）小车在初始位置处，Y420为ON，若按下开始按钮SB，则小车前行，电机正转，2）小车到达当运行至料斗下方时，Y410为ON，电机停转，小车停止，打开料斗门，延时7S； 3）7S时间到，装料完成，翻斗门关闭，小车后退，电机反转； 4）返回至Y420处，电机停转，小车停止，打开小车底门卸料， 5）卸料完毕，一个工作过程结束，1）步开始一个新的工作周期。 根据小车的工作过程，画出小车工作工序图，如图： 1、确定I/O设备 1）小车前行和后退需要一交流电机（电机的选择要根据小车的最大载荷确定），电机正反转控制需要2个接触器KM1、KM2，KM1控制小车前行，KM2控制小车后退； 2）为检测小车是否到达原位和料斗下方，需要两个限位开关：Y420原位，Y410料斗处； 3）为打开和关闭料斗门和小车底门，需要两个继电器：KA1料斗门，KA2小车底门，
第 1 章绪论 课后习题讲解 1. 填空 ⑴（）是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。 【解答】数据元素 ⑵（）是数据的最小单位，（）是讨论数据结构时涉及的最小数据单位。 【解答】数据项，数据元素 【分析】数据结构指的是数据元素以及数据元素之间的关系。 ⑶从逻辑关系上讲，数据结构主要分为（）、（）、（）和（）。 【解答】集合，线性结构，树结构，图结构 ⑷数据的存储结构主要有（）和（）两种基本方法，不论哪种存储结构，都要存储两方面的内容：（）和（）。 【解答】顺序存储结构，链接存储结构，数据元素，数据元素之间的关系 ⑸算法具有五个特性，分别是（）、（）、（）、（）、（）。 【解答】有零个或多个输入，有一个或多个输出，有穷性，确定性，可行性 ⑹算法的描述方法通常有（）、（）、（）和（）四种，其中，（）被称为算法语言。 【解答】自然语言，程序设计语言，流程图，伪代码，伪代码 ⑺在一般情况下，一个算法的时间复杂度是（）的函数。 【解答】问题规模 ⑻设待处理问题的规模为n，若一个算法的时间复杂度为一个常数，则表示成数量级的形式为（），若为n*log25n，则表示成数量级的形式为（）。 【解答】Ο(1)，Ο(nlog2n) 【分析】用大O记号表示算法的时间复杂度，需要将低次幂去掉，将最高次幂的系数去掉。 2. 选择题 ⑴顺序存储结构中数据元素之间的逻辑关系是由（）表示的，链接存储结构中的数据元素之间的逻辑关系是由（）表示的。 A 线性结构 B 非线性结构 C 存储位置 D 指针 【解答】C，D 【分析】顺序存储结构就是用一维数组存储数据结构中的数据元素，其逻辑关系由存储位置（即元素在数组中的下标）表示；链接存储结构中一个数据元素对应链表中的一个结点，元素之间的逻辑关系由结点中的指针表示。
郑州大学远程教育在线测试答案结构力学
————————————————————————————————作者：————————————————————————————————日期：
《结构力学》第06章在线测试 《结构力学》第06章在线测试剩余时间：58:36 答题须知：1、本卷满分20分。 2、答完题后，请一定要单击下面的“交卷”按钮交卷，否则无法记录本试卷的成绩。 3、在交卷之前，不要刷新本网页，否则你的答题结果将会被清空。 第一题、单项选择题（每题1分，5道题共5分） 1、与力法方程中的系数δki互等的系数是 A、δik B、δii C、δkk D、Δki 2、去掉一个定向支座，相当于去掉几个约束？ A、1 B、2 C、3 D、4 3、力法方程的实质是 A、平衡条件 B、互等定理 C、位移条件 D、物理条件 4、单跨对称刚架在对称荷载作用下，其半边结构是将对称轴上的截面设置成 A、自由端 B、可动铰支座 C、固定铰支座 D、定向支座 5、单跨对称刚架在反对称荷载作用下，其半边结构是将对称轴上的截面设置成 A、自由端 B、可动铰支座 C、固定铰支座 D、定向支座 第二题、多项选择题（每题2分，5道题共10分） 1、用力法计算超静定结构时，下列结论正确的是 A、多余未知力通过位移条件求解 B、所有未知力通过位移条件求解 C、多余未知力通过平衡条件求解
D、所有未知力通过平衡条件求解 E、多余未知力以外的其他未知力通过平衡条件求解 2、不考虑轴向变形时，两跨对称结构在对称荷载作用下，中柱的 A、弯矩为零 B、剪力为零 C、轴力为零 D、轴向变形为零 E、弯曲变形为零 3、单跨对称结构在反对称荷载作用下，对称轴上的截面 A、沿对称轴方向上的位移为零 B、垂直对称轴方向上的位移为零 C、角位移为零 D、弯矩为零 E、轴力为零 4、在力法方程中可正可负可为零的是 A、δik B、δii C、δkk D、ΔkP E、δki 5、下列关于立法的论述正确的是 A、力法的基本未知量是多余未知力 B、力法的基本体系是静定结构 C、力法方程是位移条件
数据结构期末考试题及标准答案
————————————————————————————————作者：————————————————————————————————日期：
2012年数据结构期末考试题及答案 一、选择题 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．算法分析的目的是C，算法分析的两个主要方面是A。 （1）A．找出数据结构的合理性B．研究算法中的输入和输出的关系 C．分析算法的效率以求改进C．分析算法的易读性和文档性 （2）A．空间复杂度和时间复杂度B．正确性和简明性 C．可读性和文档性D．数据复杂性和程序复杂性 8．下面程序段的时间复杂度是O（n2）。
s ＝0； for（I ＝0；i＜n；i＋＋） for（j＝0；j＜n；j＋＋） s ＋＝B[i][j]； sum ＝s ； 9．下面程序段的时间复杂度是O（n*m）。 for（i ＝0；i＜n；i＋＋） for（j＝0；j＜m；j＋＋） A[i][j] ＝0； 10．下面程序段的时间复杂度是O（log3n）。 i ＝0； while（i＜＝n） i ＝i * 3； 11．在以下的叙述中，正确的是B。 A．线性表的顺序存储结构优于链表存储结构 B．二维数组是其数据元素为线性表的线性表 C．栈的操作方式是先进先出 D．队列的操作方式是先进后出 12．通常要求同一逻辑结构中的所有数据元素具有相同的特性，这意味着B 。 A．数据元素具有同一特点 B．不仅数据元素所包含的数据项的个数要相同，而且对应的数据项的类型要一致 C．每个数据元素都一样 D．数据元素所包含的数据项的个数要相等 13．链表不具备的特点是A。 A．可随机访问任一结点B．插入删除不需要移动元素 C．不必事先估计存储空间D．所需空间与其长度成正比 14．不带头结点的单链表head为空的判定条件是A。
38877166.doc Page 1 of 6 2005A 卷 合分人: 复查人: 一、单选题:(每题 2分,共 20分 (说明:将认为正确答案的字母填写在每小题后面的括号内 1.图示体系能形成虚铰的是链杆 ( A 1和 2 B 2和 3 C 1和 4 D 都能 2.图示结构有多少根零杆 ( A 4根 B 5根 C 6根 D 7根 3.图示结构弯矩图形状正确的是 ( 4.为了减小三铰拱的水平推力,应采取下列哪种措施 (
A 不改变三铰的位置调整拱轴线形状 B 增大跨度 C 增大拱的截面尺寸 D 增大矢高 5.图示同一结构的两种状态,根据位移互等定理下列式子正确的是 ( A θ3=Δ2 B θ3=θ4 C Δ1=θ4 D Δ1=Δ2 题一 .3图 题一 .1图 题一 .2图 题一 . 6图
题一 .5图 38877166.doc Page 2 of 6 6.图(a 结构如选图(b 为力法基本体系,其力法方程为 ( 11111111111111111101///P P P P A X B X k C X X k D X X k δδδδ+?=+?=+?=-+?= 7.图示结构横梁刚度为无穷大,柱子弯矩图形状正确的是 ( 8.在图示约束情况下,用先处理法集成的结构的刚度矩阵 [K ]= ( 3 3333333120121212012201212120EA EI EA l l l A B EA EI EI EA EI l l l l l EA EI EA l l l C D EA EI EI EI l l l l ??
?? ???? ? ? ?? ????++???????????? ???? ???? ????+????? ? ?? 9.单自由度体系在简谐荷载作用下,若荷载频率远远大于体系的自振频率时,则体系的动力反映 ( A 接近于荷载幅值引起的静力反映 B 接近于零 C 很大,但是有限值 D 接近无限大 10.图示为两个自由度体系的两个主振型,其中 Y 22等于 ( A -1 B -6.2435 C 1 D 6.2435
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-3 平面机构具有确定的运动条件是什么？ 答：必须使原动件数目等于机构的自由度数。 1-5 试确定下列平面机构的自由度（图中绘有箭头的活动构件为原动件）：a)推土机的推土机构；d)渣口堵塞机构；f)筛料机机构。 解：a)推土机的推土机构 活动构件数n＝5，低副PL＝7（6 个转动副，一个移动副）高副PH＝0。 F＝3×5－2×7－ 0 ＝1 等于原动件数∴有确定运动。 d) 渣口堵塞机构 由分析可知与杆 1 相连的滚子2，属于局部自由度 ∴计算机构自由度时应排除。 则n＝6 PL＝8（7 个转动副， 1 个移动副）PH＝ 1 ∴F＝3×6－2×8－1＝ 1 等于原动件数 f) 筛选机的筛料机构 由图：杆 1 和杆 2 焊在一起属于一体，与杆 3 相连的滚子 4 绕其中心的转动是一个局部自 由度 ∴n＝6 PL＝8（6 个转动副， 2 个移动副）PH＝ 1 ∴F＝3×6－2×8－1＝ 1 等于原动件数 3-5.已知一曲柄滑块机构的滑块行程H=60mm, 偏距e=20mm,行程速比系数K=1.4,试确定曲柄和连杆的长度l2 和l3。（规定用作图法求之）
解：(1) 由行程速比系数K，求出极位夹角θ。 θ＝180°×(K－1)／(K+1) ＝180°×(1.4－1) ／(1.4＋1)＝30° 选比例尺u＝1:2，作图，可得： (2) 连接C1 和C2，并作C1M 垂直于C1C2,C1C2 ＝H; (3) 作∠C1C2N ＝90°－θ＝60°，C2N 与C1M 相交于P 点, 由图可见, ∠C1PC2＝θ＝30°; 4)作三角形PC1C2 的外接圆O,则曲柄的固定铰链中心 A 必在该圆上。 (5)作与C1C2 线相距为 e 的平行线，与外接圆O 交于的点即为 A 点，连接AC1 、AC2，则∠C1AC2 ＝θ。 (6)因极限位置处曲柄与连杆共线，故AC1＝l3－l2, AC2= l3 ＋l2，所以曲柄长度l2=(AC2 －AC1) ／2; 由比例尺量得：AC1＝28mm,AC2＝82mm, 所以l2＝(82－28) ／2＝27mm。 (7)以A 为圆心和l2 为半径作圆，交C1A 延线于B1，交C2A 于B2，即得B1C1＝l3,由比例尺量得： l3＝B1C1＝56mm。 综上可知：曲柄长度l2 为27mm，连杆长度l3 为56mm。 3-6．已知一导杆机构的固定件长度l1＝1000 ㎜，行程速比系数K＝1.5，确定曲柄长度l2 及导杆摆角φ。（解析法求解） 解：导杆机构的极位夹角 θ＝180（K-1 ）／(K＋1) ＝180°×（ 1.5-1）／(1.5＋1) = 36° 所以由图可得，导杆摆角φ＝θ＝36°
第一章概论 一、选择题 1、研究数据结构就是研究（Ｄ）。 Ａ. 数据的逻辑结构?B。数据的存储结构 C。数据的逻辑结构和存储结构?D．数据的逻辑结构、存储结构及其基本操作(研究非数值计算的程序设计问题中，计算机操作对象以及他们之间的关系和操作) 2、算法分析的两个主要方面是（Ａ）。 A．空间复杂度和时间复杂度???B。正确性和简单性 C。可读性和文档性D．数据复杂性和程序复杂性 3、具有线性结构的数据结构是（ D ）。(线性结构就是：在非空有限集合中，存在为一个被称为第一个的数据元素和最后一个元素,有除了第一个元素，集合中每一个元素均只有一个前驱，除了最后一个元素有唯一后继)（链表、栈、队列、数组、串） A. 图Ｂ. 树??C．广义表(线性表的推广) D．栈 4、计算机中的算法指的是解决某一个问题的有限运算序列,它必须具备输入、输出、（ B ）等5个特性。 Ａ．可执行性、可移植性和可扩充性? B. 可执行性、有穷性和确定性 C。确定性、有穷性和稳定性??? D. 易读性、稳定性和确定性 5、下面程序段的时间复杂度是( C ）。 for(i=0；i 2005A 卷） 合分人： 复查人： 一、单选题：（每题2分，共20分） （说明：将认为正确答案的字母填写在每小题后面的括号内） 1．图示体系能形成虚铰的是链杆 （ ） A 1和2 B 2和3 C 1和4 D 都能 2．图示结构有多少根零杆 （ ） A 4根 B 5根 C 6根 D 7根 3．图示结构弯矩图形状正确的是 （ ） 4．为了减小三铰拱的水平推力，应采取下列哪种措施 （ ） A 不改变三铰的位置调整拱轴线形状 B 增大跨度 C 增大拱的截面尺寸 D 增大矢高 5 ．图示同一结构的两种状态，根据位移互等定理下列式子正确的是 （ ） A θ3=Δ2 B θ3=θ4 C Δ1=θ4 D Δ1=Δ2 题一.3图 题一.1图 题一.2图 6．图（a ）结构如选图（b ）为力法基本体系，其力法方程为 （ ） 11111111111111111101///P P P P A X B X k C X X k D X X k δδδδ+?=+?=+?=-+?= 7．图示结构横梁刚度为无穷大，柱子弯矩图形状正确的是 （ ） 8．在图示约束情况下，用先处理法集成的结构的刚度矩阵[K ]= ( ) 3 3333333120121212012201212120EA EI EA l l l A B EA EI EI EA EI l l l l l EA EI EA l l l C D EA EI EI EI l l l l ?? ?? ???? ? ? ??????++???????????? ???? ???? ????+????? ? ?? 9．单自由度体系在简谐荷载作用下，若荷载频率远远大于体系的自振频率时，则体系的动力反映 （ ） A 接近于荷载幅值引起的静力反映 B 接近于零 C 很大，但是有限值 D 接近无限大 10．图示为两个自由度体系的两个主振型，其中Y 22等于 （ ） A －1 B －6.2435 C 1 D 6.2435 C D A B 题一.7图 题一-10图 题一.8图 2012年数据结构期末考试题及答案 一、选择题 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．算法分析的目的是C，算法分析的两个主要方面是A。 （1）A．找出数据结构的合理性B．研究算法中的输入和输出的关系 C．分析算法的效率以求改进C．分析算法的易读性和文档性 （2）A．空间复杂度和时间复杂度B．正确性和简明性 C．可读性和文档性D．数据复杂性和程序复杂性 8．下面程序段的时间复杂度是O（n2）。 s ＝0； for（I ＝0；i＜n；i＋＋） for（j＝0；j＜n；j＋＋） s ＋＝B[i][j]； sum ＝s ； 9．下面程序段的时间复杂度是O（n*m）。 for（i ＝0；i＜n；i＋＋） for（j＝0；j＜m；j＋＋） A[i][j] ＝0； 10．下面程序段的时间复杂度是O（log3n）。 i ＝0； while（i＜＝n） i ＝i * 3； 11．在以下的叙述中，正确的是B。 A．线性表的顺序存储结构优于链表存储结构 B．二维数组是其数据元素为线性表的线性表 C．栈的操作方式是先进先出 D．队列的操作方式是先进后出 12．通常要求同一逻辑结构中的所有数据元素具有相同的特性，这意味着B 。 A．数据元素具有同一特点 B．不仅数据元素所包含的数据项的个数要相同，而且对应的数据项的类型要一致 C．每个数据元素都一样 D．数据元素所包含的数据项的个数要相等 13．链表不具备的特点是A。 A．可随机访问任一结点B．插入删除不需要移动元素 C．不必事先估计存储空间D．所需空间与其长度成正比 14．不带头结点的单链表head为空的判定条件是A。 郑州大学现代远程教育《机械设计基础》课程 考核要求 说明：本课程考核形式为提交作业，完成后请保存为WORD 2003格式的文档，登陆学习平台提交，并检查和确认提交成功（能够下载，并且内容无误即为提交成功）。 院系远程教育学院 专业机电一体化（专科） 班级2015年春 学号 姓名 成绩 一．作业要求 1. 作业题中涉及到的公式、符号以教材为主； 2. 课程设计题按照课堂上讲的“课程设计任务与要求”完成。设 计计算说明书不少于20页。 二． 作业内容 （一）.选择题（在每小题的四个备选答案中选出一个正确的答案，并将正确答案的号 码填在题干的括号内，每小题1分，共20分） 1．在平面机构中，每增加一个低副将引入（C ）。 A ．0个约束 B ．1个约束 C ．2个约束 D ．3个约束 2.铰链四杆机构ABCD 中，AB 为曲柄，CD 为摇杆，BC 为连杆。若杆长l AB =30mm,l BC =70mm ，l CD =80mm ，则机架最大杆长为（ C ） A.80mm B.100mm C.120mm D.150mm 3．在凸轮机构中，当从动件以 运动规律运动时，存在刚性冲击。 （ A ） A ．等速 B ．摆线 C ．等加速等减速 D ．简谐 4.棘轮机构中采用了止回棘爪主要是为了( a ) A.防止棘轮反转 B.对棘轮进行双向定位 C.保证棘轮每次转过相同的角度 D.驱动棘轮转动 5．在标准直齿轮传动中，硬齿面齿轮应按 设计。 （ B ） A ．齿面接触疲劳强度 B ．齿根弯曲疲劳强度 C ．齿面接触疲劳强度和齿根弯曲疲劳强度 D ．热平衡 6．在一对标准直齿轮传动中，大、小齿轮的材料及热处理方式相同时，小齿轮的齿面接触 应力1H σ和大齿轮的齿面接触应力2H σ的关系为 。 （ c ） A ．1H σ>2H σ B ．1H σ<2H σ C ．1H σ=2H σ D ．不确定 7．提高蜗杆传动效率的措施是 。 （ D ） A ．增加蜗杆长度 B ．增大模数 C ．使用循环冷却系统 D ．增大蜗杆螺旋升角 8.在传动中，各齿轮轴线位置固定不动的轮系称为( B ) A.周转轮系 B.定轴轮系郑州大学结构力学课程试卷解析
2015年数据结构期末考试题及答案
郑州大学现代远程教育《机械设计基础》课程答案
相关主题
文本预览