数据结构简答题打印版
数据结构简答题
1.1 简述下列术语：数据，数据元素、数据对象、数据结构、存储结构、数据类型和抽象数据类型。
解：数据是对客观事物的符号表示。在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。
数据元素是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。
数据对象是性质相同的数据元素的集合，是数据的一个子集。
数据结构是相互之间存在一种或多种特定关系的数据元素的集合。
存储结构是数据结构在计算机中的表示。
数据类型是一个值的集合和定义在这个值集上的一组操作的总称。
抽象数据类型是指一个数学模型以及定义在该模型上的一组操作。是对一般数据类型的扩展。
1.2 试描述数据结构和抽象数据类型的概念与程序设计语言中数据类型概念的区别。
解：抽象数据类型包含一般数据类型的概念，但含义比一般数据类型更广、更抽象。一般数据类型由具体语言系统内部定义，直接提供给编程者定义用户数据，因此称它们为预定义数据类型。抽象数据类型通常由编程者定义，包括定义它所使用的数据和在这些数据上所进行的操作。在定义抽象数据类型中的数据部分和操作部分时，要求只定义到数据的逻辑结构和操作说明，不考虑数据的存储结构和操作的具体实现，这样抽象层次更高，更能为其他用户提供良好的使用接口。
1.7 在程序设计中，可采用下列三种方法实现输出和输入：
(1) 通过scanf和printf语句；
(2) 通过函数的参数显式传递；
(3) 通过全局变量隐式传递。
试讨论这三种方法的优缺点。
解：(1)用scanf和printf直接进行输入输出的好处是形象、直观，但缺点是需要对其进行格式控制，较为烦琐，如果出现错误，则会引起整个系统的崩溃。
(2)通过函数的参数传递进行输入输出，便于实现信息的隐蔽，减少出错的可能。
(3)通过全局变量的隐式传递进行输入输出最为方便，只需修改变量的值即可，但过多的全局变量使程序的维护较为困难。
2.1 描述以下三个概念的区别：头指针，头结点，首元结点（第一个元素结点）。
解：头指针是指向链表中第一个结点的指针。首元结点是指链表中存储第一个数据元素的结点。头结点是在首元结点之前附设的一个结点，该结点不存储数据元素，其指针域指向首元结点，其作用主要是为了方便对链表的操作。它可以对空表、非空表以及首元结点的操作进行统一处理。
2.2 填空题。
解：(1) 在顺序表中插入或删除一个元素，需要平均移动表中一半元素，具体移动的元素个数与元素在表中的位置有关。
(2) 顺序表中逻辑上相邻的元素的物理位置必定紧邻。单链表中逻辑上相邻的元素的物理位置不一定紧邻。
(3) 在单链表中，除了首元结点外，任一结点的存储位置由其前驱结点的链域的值指示。
(4) 在单链表中设置头结点的作用是插入和删除首元结点时不用进行特殊处理。
2.3 在什么情况下用顺序表比链表好？
解：当线性表的数据元素在物理位置上是连续存储的时候，用顺序表比用链表好，其特点是可以进行随机存取。
3.2 简述栈和线性表的差别。
解：线性表是具有相同特性的数据元素的一个有限序列。栈是限定仅在表尾进行插入或删除操作的线性表。
3.11 简述队列和堆栈这两种数据类型的相同点和差异处。
解：栈是一种运算受限的线性表，其限制是仅允许在表的一端进行插入和删除运算。
队列也是一种运算受限的线性表，其限制是仅允许在表的一端进行插入，而在表的另一端进行删除。
4.1 解：空格串是指一个或多个空格字符(ASCII码为20H)组成的串，而空串中没有任何字符。
4.2 解：串赋值(StrAssign)、串比较(StrCompare)、求串长(StrLength)、串连接(Concat)、求子串(SubString)这五种基本操作构成串类型的最小操作子集。
6.2 一棵度为2的树与一棵二叉树有何区别？
解：二叉树是颗有序树，但度为2的树则未必有序。
三、简答题
1. 描述以下三个概念的区别：头指针，头结点，表头结点。
1．头指针是指向链表中第一个结点（即表头结点）的指针；在表头结点之前附设的结点称为头结点；表头结点为链表中存储线性表中第一个数据元素的结点。若链表中附设头结点，则不管线性表是否为空表，头指针均不为空，否则表示空表的链表的头指针为空。
2. 线性表的两种存储结构各有哪些优缺点？
2．线性表具有两种存储结构即顺序存储结构和链接存储结构。线性表的顺序存储结构可以直接存取数据元素，方便灵活、效率高，但插入、删除操作时将会引起元素的大量移动，因而降低效率：而在链接存储结构中内存采用动态分配，利用率高，但需增设指示结点之间关系的指针域，存取数据元素不如顺序存储方便，但结点的插入、删除操作较简单。
3. 对于线性表的两种存储结构，如果有n个线性表同时并存，而且在处理过程中各表的长度会动态发生变化，线性表的总数也会自动改变，在此情况下，应选用哪一种存储结构？为什么？
3．应选用链接存储结构，因为链式存储结构是用一组任意的存储单元依次存储线性表中的各元素，这里存储单元可以是连续的，也可以是不连续的：这种存储结构对于元素的删除或插入运算是不需要移动元素的，只需修改指针即可，所以很容易实现表的容量的扩充。
4. 对于线性表的两种存储结构，若线性表的总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素，应选用何种存储结构？试说明理由。
4．应选用顺序存储结构，因为每个数据元素的存储位置和线性表的起始位置相差一个和数据元素在线性表中的序号成正比的常数。因此，只要确定了其起始位置，线性表中的任一个数据元素都可随机存取，因此，线性表的顺序存储结构是一种随机存取的存储结构，而链表则是一种顺序存取的存储结构。
5. 在单循环链表中设置尾指针比设置头指针好吗？为什么?
5．设尾指针比设头指针好。尾指针是指向终端结点的指针，用它来表示单循环链表可以使得查找链表的开始结点和终端结点都很方便，设一带头结点的单循环链表，其尾指针为
rear，则开始结点和终端结点的位置分别是rear->next->next 和rear, 查找时间都是O(1)。若用头指针来表示该链表，则查找终端结点的时间为O(n)。
6. 假定有四个元素A, B, C, D依次进栈，进栈过程中允许出栈，试写出所有可能的出栈序列。
6．共有14种可能的出栈序列，即为：
ABCD, ABDC，ACBD, ACDB，BACD，ADCB，BADC，BCAD, BCDA，BDCA,CBAD, CBDA，CDBA, DCBA
7. 什么是队列的上溢现象？一般有几种解决方法，试简述之。
7．在队列的顺序存储结构中，设队头指针为front，队尾指针为rear，队列的容量（即存储的空间大小）为maxnum。当有元素要加入队列（即入队）时，若rear=maxnum，则会发生队列的上溢现象，此时就不能将该元素加入队列。对于队列，还有一种“假溢出”现象，队列中尚余有足够的空间，但元素却不能入队，一般是由于队列的存储结构或操作方式的选择不当所致，可以用循环队列解决。
一般地，要解决队列的上溢现象可有以下几种方法：
（1）可建立一个足够大的存储空间以避免溢出，但这样做往往会造成空间使用率低，浪费存储空间。
（2）要避免出现“假溢出”现象可用以下方法解决：
第一种：采用移动元素的方法。每当有一个新元素入队，就将队列中已有的元素向队头移动一个位置，假定空余空间足够。
第二种：每当删去一个队头元素，则可依次移动队列中的元素总是使front指针指向队列中的第一个位置。
第三种：采用循环队列方式。将队头、队尾看作是一个首尾相接的循环队列，即用循环数组实现，此时队首仍在队尾之前，作插入和删除运算时仍遵循“先进先出”的原则。
8. 下述算法的功能是什么?
LinkList *Demo(LinkList *L)
{ // L是无头结点的单链表
LinkList *q,*p;
if(L&&L->next)
{ q=L; L=L->next; p=L;
while (p->next)
p=p->next;
p->next=q; q->next=NULL;
}
return (L);
}
8．该算法的功能是：将开始结点摘下链接到终端结点之后成为新的终端结点，而原来的第二个结点成为新的开始结点，返回新链表的头指针。
四、应用题
1. 已知一棵树边的集合为{
题：
（1）哪个是根结点？
（2）哪些是叶子结点？
（3）哪个是结点g 的双亲？
（4）哪些是结点g 的祖先？
（5）哪些是结点g 的孩子？
（6）哪些是结点e 的孩子？
（7）哪些是结点e 的兄弟？哪些是结点f 的兄弟？
（8）结点b 和n 的层次号分别是什么？
（9）树的深度是多少？
（10）以结点c 为根的子树深度是多少？
1. 解答：
根据给定的边确定的树如图5-15所示。 其中根结点为a ； 叶子结点有：d 、m 、n 、j 、k 、f 、l ； c 是结点g 的双亲； a 、c 是结点g 的祖先； j 、k 是结点g 的孩子； m 、n 是结点e 的子孙； e 是结点d 的兄弟；
g 、h 是结点f 的兄弟； 结点b 和n 的层次号分别是2和5；
树的深度为5。
2. 一棵度为2的树与一棵二叉树有何区别。
2. 解答：
度为2的树有两个分支，但分支没有左右之分；一棵二叉树也有两个分支，但有左右之分，左右子树不能交换。
3. 试分别画出具有3个结点的树和二叉树的所有不同形态？
3. 解答： 略
4. 已知用一维数组存放的一棵完全二叉树：ABCDEFGHIJKL ，写出该二叉树的先序、中序和后序遍历序列。
4. 解答：
先序序列：ABDHIEJKCFLG
中序序列：HDIBJEKALFCG
后序序列：HIDJKEBLFGCA
5. 一棵深度为H 的满k 叉树有如下性质：第H 层上的结点都是叶子结点，其余各层上每个结点都有k 棵非空子树，如果按层次自上至下，从左到右顺序从1开始对全部结点编号，回答下列问题：
（1）各层的结点数目是多少？
（2）编号为n 的结点的父结点如果存在，编号是多少？
a
b c d e g f h i m n j
k i 图5-15
（3）编号为n 的结点的第i 个孩子结点如果存在，编号是多少？
（4）编号为n 的结点有右兄弟的条件是什么？其右兄弟的编号是多少？
5. 解答：
（1）第i 层上的结点数目是mi-1。
（2）编号为n 的结点的父结点如果存在，编号是((n-2)/m)+1。
（3）编号为n 的结点的第i 个孩子结点如果存在，编号是(n-1)*m+i+1。
（4）编号为n 的结点有右兄弟的条件是(n-1)%m ≠0。其右兄弟的编号是n+1。
6. 找出所有满足下列条件的二叉树：
（1）它们在先序遍历和中序遍历时，得到的遍历序列相同；
（2）它们在后序遍历和中序遍历时，得到的遍历序列相同；
（3）它们在先序遍历和后序遍历时，得到的遍历序列相同；
6. 解答：
（1）先序序列和中序序列相同的二叉树为：空树或者任一结点均无左孩子的非空二叉树；
（2）中序序列和后序序列相同的二叉树为：空树或者任一结点均无右孩子的非空二叉树；
（3）先序序列和后序序列相同的二叉树为：空树或仅有一个结点的二叉树。
7. 假设一棵二叉树的先序序列为EBADCFHGIKJ ，中序序列为ABCDEFGHIJK ，请写出该二叉树的后序遍历序列。
7. 解答：后序序列：ACDBGJKIHFE
8. 假设一棵二叉树的后序序列为DCEGBFHKJIA ，中序序列为DCBGEAHFIJK ，请写出该二叉树的后序遍历序列。
8. 解答：先序序列：ABCDGEIHFJK
9. 给出如图5-14所示的森林的先根、后根遍历结点序列，然后画出该森林对应的二叉树。
9. 解答：
先根遍历：ABCDEFGHIJKLMNO
后根遍历：BDEFCAHJIGKNOML
森林转换成二叉树如图5-16所示。
10．给定一组权值（5，9，11，2，7，16），试设计相应的哈夫曼树。
10. 解答：构造而成的哈夫曼树如图5-17所示。
A B D E F C G H J
I K N
O
M L 图5-14
【例6-5】 一个带权无向图的最小生成树是否一定唯一？在什么情况下构造出的最小生成树可能不唯一？
解：一个带权无向图的最小生成树不一定是唯一的。从Kruskal 算法构造最小生成树的过程可以看出，当从图中选择当前权值最小的边时，如果存在多条这样的边，并且这些边与已经选取的边构成回路，此时这些边就不可能同时出现在一棵最小生成树中，对这些边的不同选择结果可能会产生不同的最小生成树。
三、应用题
1. 已知一个顺序存储的有序表为(15,26,34,39,45,56,58,63,74,76)，试画出对应的折半查找判定树，求出其平均查找长度。
1. 折半查找判定树如图7-3所示，平均查找长度等于29/10。图7-3中的结点与有序表中元素的对应关系如下表所示。
2. 假定一个线性表为(38,52,25,74,68,16,30,54,90,72)，画出按线性表中元素的次序生成的一棵二叉排序树，求出其平均查找长度。
2. 二叉排序树如图7-4所示，平均查找长度等于32/10。
3. 假定一个待哈希存储的线性表为(32,75,29,63,48,94,25,46,18,70)，哈希地址空间为HT[13]，若采用除留余数法构造哈希函数和线性探测法处理冲突，试求出每一元素在哈希表中的初始哈希地址和最终哈希地址，画出最后得到的哈希表，求出平均查找长度。
元素 32 75 29 63 48 94 25 46 18 70
初始哈希地址
最终哈希地址
0 1 2 3 4 5 6 7 8 9 10 11 12
哈希表
3. H(K)=K % 13平均查找长度为14/10，其余解答如下。
12345678910
15 26 34 39 45 56 58 63 74 76 图7-3 10 9 4 5 6 7 8 1 2 3 图7-4 38 52 25 16 74 30
68 90
54 72
元素32 75 29 63 48 94 25 46 18 70
初始哈希地址 6 10 3 11 9 3 12 7 5 5
最终哈希地址 6 10 3 11 9 4 12 7 5 8
0 1 2 3 4 5 6 7 8 9 10 11 12
哈希表29 94 18 32 46 70 48 75 63 25
4. 假定一个待哈希存储的线性表为(32,75,29,63,48,94,25,36,18,70,49,80)，哈希地址空间为HT[12]，若采用除留余数法构造哈希函数和拉链法处理冲突，试画出最后得到的哈希表，并求出平均查找长度。
4. H(K)=K % 11，哈希表如图7-5所示，平均查找长度17/12。
∧
图7-5
三、简答题
2.【严题集1.2②】数据结构和数据类型两个概念之间有区别吗？
答：简单地说，数据结构定义了一组按某些关系结合在一起的数组元素。数据类型不仅定义了一组带结构的数据元素，而且还在其上定义了一组操作。
3. 简述线性结构与非线性结构的不同点。
答：线性结构反映结点间的逻辑关系是一对一的，非线性结构反映结点间的逻辑关系是多对多的。
四、简答题
1. 【严题集
2.3②】试比较顺序存储结构和链式存储结构的优缺点。在什么情况下用顺序表比链表好？
答：①顺序存储时，相邻数据元素的存放地址也相邻（逻辑与物理统一）；要求内存中可用存储单元的地址必须是连续的。
优点：存储密度大（＝1？），存储空间利用率高。缺点：插入或删除元素时不方便。
②链式存储时，相邻数据元素可随意存放，但所占存储空间分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针
优点：插入或删除元素时很方便，使用灵活。缺点：存储密度小（<1），存储空间利用率低。
顺序表适宜于做查找这样的静态操作；链表宜于做插入、删除这样的动态操作。
若线性表的长度变化不大，且其主要操作是查找，则采用顺序表；
若线性表的长度变化较大，且其主要操作是插入、删除操作，则采用链表。
2 .【严题集2.1①】描述以下三个概念的区别：头指针、头结点、首元结点（第一个元素结点）。在单链表中设置头结点的作用是什么？
答：首元结点是指链表中存储线性表中第一个数据元素a1的结点。为了操作方便，通常在链表的首元结点之前附设一个结点，称为头结点，该结点的数据域中不存储线性表的数据元素，其作用是为了对链表进行操作时，可以对空表、非空表的情况以及对首元结点进行统一处理。头指针是指向链表中第一个结点（或为头结点或为首元结点）的指针。若链表中附设头结点，则不管线性表是否为空表，头指针均不为空。否则表示空表的链表的头指针为空。这三个概念对单链表、双向链表和循环链表均适用。是否设置头结点，是不同的存储结构表示同一逻辑结构的问题。
头结点
head data link
头指针首元结点
简而言之，
头指针是指向链表中第一个结点（或为头结点或为首元结点）的指针；
头结点是在链表的首元结点之前附设的一个结点；数据域内只放空表标志和表长等信息（内放头指针？那还得另配一个头指针！！！）
首元素结点是指链表中存储线性表中第一个数据元素a1的结点。
四、简答题（每小题4分，共20分）
1. 【严题集3.2①和3.11①】说明线性表、栈与队的异同点。
刘答：相同点：都是线性结构，都是逻辑结构的概念。都可以用顺序存储或链表存储；栈和队列是两种特殊的线性表，即受限的线性表，只是对插入、删除运算加以限制。
不同点：①运算规则不同，线性表为随机存取，而栈是只允许在一端进行插入、删除运算，因而是后进先出表LIFO；队列是只允许在一端进行插入、另一端进行删除运算，因而是先进先出表FIFO。
②用途不同，堆栈用于子程调用和保护现场，队列用于多道作业处理、指令寄存及其他运算等等。
4. 【统考书P60 4-13】顺序队的“假溢出”是怎样产生的？如何知道循环队列是空还是满？
答：一般的一维数组队列的尾指针已经到了数组的上界，不能再有入队操作，但其实数组中还有空位置，这就叫“假溢出”。
采用循环队列是解决假溢出的途径。
另外，解决队满队空的办法有三：
设置一个布尔变量以区别队满还是队空；
浪费一个元素的空间，用于区别队满还是队空。
使用一个计数器记录队列中元素个数（即队列长度）。
我们常采用法②，即队头指针、队尾指针中有一个指向实元素，而另一个指向空闲元素。
判断循环队列队空标志是：f=rear 队满标志是：f=(r+1)%N
2.【全国专升本资格考试】递归算法比非递归算法花费更多的时间，对吗？为什么？
答：不一定。时间复杂度与样本个数n有关，是指最深层的执行语句耗费时间，而递归算法与非递归算法在最深层的语句执行上是没有区别的，循环的次数也没有太大差异。仅仅是确定循环是否继续的方式不同，递归用栈隐含循环次数，非递归用循环变量来显示循环次数而已。
四、简答题（每小题4分，共20分）
【严题集6.2①】一棵度为2的树与一棵二叉树有何区别？
答：度为2的树从形式上看与二叉树很相似，但它的子树是无序的，而二叉树是有序的。即，在一般树中若某结点只有一个孩子，就无需区分其左右次序，而在二叉树中即使是一个孩子也有左右之分。
三、简答题（每小题4分，共16分）
1.【全国专升本题】对分（折半）查找适不适合链表结构的序列，为什么？用二分查找的查找速度必然比线性查找的速度快，这种说法对吗？
答：不适合！虽然有序的单链表的结点是按从小到大（或从大到小）顺序排列，但因其存储结构为单链表，查找结点时只能从头指针开始逐步搜索，故不能进行折半查找。
二分查找的速度在一般情况下是快些，但在特殊情况下未必快。例如所查数据位于首位时，则线性查找快；而二分查找则慢得多。
3. 【全国专升本题】用比较两个元素大小的方法在一个给定的序列中查找某个元素的时间复杂度下限是什么? 如果要求时间复杂度更小,你采用什么方法？此方法的时间复杂度是多少?
答：查找某个元素的时间复杂度下限，如果理解为最短查找时间，则当关键字值与表头元素相同时，比较1次即可。要想降低时间复杂度，可以改用Hash 查找法。此方法对表内每个元素的比较次数都是O （1）。
四、分析题（每小题6分，共24分）
1. 【严题集9.3②】画出对长度为10的有序表进行折半查找的判定树，并求其等概率时查找成功的平均查找长度。
解：判定树应当描述每次查找的位置： 5
8 1 3 6 9 4 7 10
2. 【全国专升本考题】在一棵空的二叉查找树中依次插入关键字序列为12，7，17，11，16，2，13，9，21，4，请画出所得到的二叉查找树。
答：
12
17
2 11 16 21
4 9 13
验算方法： 用中序遍历应得到排序结果： 2,4,7,9,11,12,13,16,17，21
ASL ＝1/10（1＋2×2＋3×4＋4×3） ＝1/10（1＋4＋12＋12） ＝29/10=2.9
数据结构简答题打印版
数据结构简答题 1.1 简述下列术语：数据，数据元素、数据对象、数据结构、存储结构、数据类型和抽象数据类型。 解：数据是对客观事物的符号表示。在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。 数据元素是数据的基本单位，在计算机程序常作为一个整体进行考虑和处理。 数据对象是性质相同的数据元素的集合，是数据的一个子集。 数据结构是相互之间存在一种或多种特定关系的数据元素的集合。 存储结构是数据结构在计算机中的表示。 数据类型是一个值的集合和定义在这个值集上的一组操作的总称。 抽象数据类型是指一个数学模型以及定义在该模型上的一组操作。是对一般数据类型的扩展。 1.2 试描述数据结构和抽象数据类型的概念与程序设计语言中数据类型概念的区别。 解：抽象数据类型包含一般数据类型的概念，但含义比一般数据类型更广、更抽象。一般数据类型由具体语言系统部定义，直接提供给编程者定义用户数据，因此称它们为预定义数据类型。抽象数据类型通常由编程者定义，包括定义它所使用的数据和在这些数据上所进行的操作。在定义抽象数据类型中的数据部分和操作部分时，要求只定义到数据的逻辑结构和操作说明，不考虑数据的存储结构和操作的具体实现，这样抽象层次更高，更能为其他用户提供良好的使用接口。 1.7 在程序设计中，可采用下列三种方法实现输出和输入： (1) 通过scanf和printf语句； (2) 通过函数的参数显式传递； (3) 通过全局变量隐式传递。 试讨论这三种方法的优缺点。 解：(1)用scanf和printf直接进行输入输出的好处是形象、直观，但缺点是需要对其进行格式控制，较为烦琐，如果出现错误，则会引起整个系统的崩溃。 (2)通过函数的参数传递进行输入输出，便于实现信息的隐蔽，减少出错的可能。 (3)通过全局变量的隐式传递进行输入输出最为方便，只需修改变量的值即可，但过多的全局变量使程序的维护较为困难。 2.1 描述以下三个概念的区别：头指针，头结点，首元结点（第一个元素结点）。 解：头指针是指向链表中第一个结点的指针。首元结点是指链表中存储第一个数据元素的结点。头结点是在首元结点之前附设的一个结点，该结点不存储数据元素，其指针域指向首元结点，其作用主要是为了方便对链表的操作。它可以对空表、非空表以及首元结点的操作进行统一处理。 2.2 填空题。 解：(1) 在顺序表中插入或删除一个元素，需要平均移动表中一半元素，具体移动的元素个数与元素在表中的位置有关。 (2) 顺序表中逻辑上相邻的元素的物理位置必定紧邻。单链表中逻辑上相邻的元素的物理位置不一定紧邻。 (3) 在单链表中，除了首元结点外，任一结点的存储位置由其前驱结点的链域的值指示。 (4) 在单链表中设置头结点的作用是插入和删除首元结点时不用进行特殊处理。 2.3 在什么情况下用顺序表比链表好？
数据结构练习题(含答案)
数据结构练习题(含答案)
数据结构练习题 习题1 绪论 1.1 单项选择题 1. 数据结构是一门研究非数值计算的程序设计问题中,数据元素的①、数据信息在计算机中的②以及一组相关的运算等的课程。 ① A．操作对象Ｂ．计算方法Ｃ．逻辑结构Ｄ．数据映象 ②A．存储结构Ｂ．关系Ｃ．运算Ｄ．算法 2. 数据结构DS(Data Struct)可以被形式地定义为DS=（D，R），其中D是①的有限集合，R是D上的②有限集合。 ① A．算法Ｂ．数据元素Ｃ．数据操作Ｄ．数据对象 ② A．操作Ｂ．映象Ｃ．存储Ｄ．关系 3. 在数据结构中，从逻辑上可以把数据结构分成。 A．动态结构和静态结构Ｂ．紧凑结构和非紧凑结构 Ｃ．线性结构和非线性结构Ｄ．内部结构和外部结构 4. 算法分析的目的是①，算法分析的两个主要方面是②。 ① A. 找出数据结构的合理性 B. 研究算法中的输 入和输出的关系 C. 分析算法的效率以求改进 D. 分析算法的易懂
性和文档性 ② A. 空间复杂性和时间复杂性 B. 正确性和简明性 C. 可读性和文档性 D. 数据复杂性和程序 复杂性 5. 计算机算法指的是①，它必具备输入、输出和②等五个特性。 ① A. 计算方法 B. 排序方法 C. 解决问题的有限运算序列 D. 调度方法 ② A. 可行性、可移植性和可扩充性 B. 可行性、确定性和有穷性 C. 确定性、有穷性和稳定性 D. 易读性、稳定性和安全性 1.2 填空题（将正确的答案填在相应的空中） 1. 数据逻辑结构包括、和三种类型，树形结构和图形结构合称为。 2. 在线性结构中，第一个结点前驱结点，其余每个结点有且只有个前驱结点；最后一个结点后续结点，其余每个结点有且只有个后续结点。 3. 在树形结构中，树根结点没有结点，其余每个结点有且只有个直接前驱结点，叶子结点没有结点，其余每个结点的直接后续结点可以。 4. 在图形结构中，每个结点的前驱结点数和后续结点数可以。 5. 线性结构中元素之间存在关系，树形结构中元素之间存在关系，图形结构中元素之间存在关系。 6. 算法的五个重要特性是__ __ , __ __ , ___ _ ,
数据结构(本)形考作业答案
形考作业一 题目1 把数据存储到计算机中，并具体体现数据元素间的逻辑结构称为（）。 选择一项： A. 逻辑结构 B. 给相关变量分配存储单元 C. 算法的具体实现 D. 物理结构 题目2 下列说法中，不正确的是（）。 选择一项： A. 数据可有若干个数据元素构成 B. 数据元素是数据的基本单位 诃C.数据项是数据中不可分割的最小可标识单位 产_D.数据项可由若干个数据元素构成 题目3 一个存储结点存储一个（）。 选择一项： A. 数据结构 B. 数据类型 C. 数据项 i_D.数据元素 题目4 数据结构中，与所使用的计算机无关的是数据的（）。 选择一项： 题目5
下列的叙述中，不属于算法特性的是（选 ）°择一项： A. 有穷性 B. 可行性
* C.可读性 D. 输入性 题目6 正确 获得2.00分中的2.00分 ◎ A.研究算法中的输入和输出的关系 B. 分析算法的易懂性和文档性 I 圏 C.分析算法的效率以求改进 D.找出数据结构的合理性 题目7 算法指的是（ ）。 选择一项： A. 排序方法 B. 解决问题的计算方法 C. 计算机程序 * D.解决问题的有限运算序列 题目8 算法的时间复杂度与（ 选择一项： A. 所使用的计算机 因B.数据结构 D. i 题目10 设有一个长度为n 的顺序表，要删除第i 个元素移动元素的个数为（ ）。 选择一项： ）有关。 D. 计算机的操作系统 题目9 设有一个长度为n 的顺序表，要在第i 个元素之前（也就是插入元素作为新表的第 i 个元 素），插入一个元素，则移动元素个数为（ ）。 选择一项: A. n-i+1 3 B. n-i-1 rj C. n-i C.算法本身
数据结构书面作业练习题
书面作业练习题 李英龙 湖南科技大学数学与计算科学学院
内容简介 在习题部分，既有选择题、判断题，也有用图表解答的练习题、算法设计题或综合解答分析题。并且配有部分练习题的答案供学生自学、练习、参考。 目录 书面作业练习题 习题一绪论 -------------------------------------------------------------3 习题二顺序表示（线性表、栈和队列）-----------------------------------------6 习题三链表（线性表、栈和队列）---------------------------------------------9 习题四串-----------------------------------------------------------------12 习题五数组 --------------------------------------------------------------13 习题六树与二叉树 -------------------------------------------------------15 习题七图-----------------------------------------------------------------24 习题八查找---------------------------------------------------------------30 习题九排序---------------------------------------------------------------33
数据结构试题14
一、简答题：（每小题3分，共15分） 1.在哈希查找法中，为什么平均查找长度与关键字个数无关？ 2.对于无向图，如何用遍历算法判断图中是否存在回路？ 3.Huffman树是否唯一？请举例说明。 4.栈和队列各有哪些基本操作？ 5.在一个与堆序列对应的完全二叉树中，从根结点到任一个叶结点的路径 上的关键字序列有何特点？为什么？ 二、判断正误：（每小题1分，共5分） 正确在（）内打√，否则打 。 （）1. 折半搜索只适用于有序表，包括有序顺序表和有序单链表。 （）2．由树的中序表示和前序表示可以导出树的后序表示。 （）3. 查找n个关键字的散列表时，平均查找长度与n无关。 （）4. 希尔排序是一种不稳定的排序方法。 （）5. 给定一个关键字集合，将得到唯一的一棵二叉排序树，与关键字的插入顺序无关。 三、单项选择题：(每小题1分，共5分) 1. 某二叉树结点的中序序列为A、B、C、D、E、F、G，后序序列为B、D、C、 A、F、G、E，则该二叉树根的右子是： A）E B）F C）D D）G 2．在长度为n的顺序表的第i ( 1≤ i ≤n+1 )个位置上插入一个元素，元素的移动次数为： A) n-i+1 B) n-i C) i D) i-1 3．下面关于图的存储的叙述中正确的是 A）邻接矩阵占用的存储空间只与图中结点个数有关，而与边数无关； B）邻接矩阵占用的存储空间只与图中边数有关，而与结点个数无关； C）邻接表占用的存储空间只与图中结点个数有关，而与边数无关； D）邻接表占用的存储空间只与图中边数有关，而与结点个数无关。 4. 在待排序记录已基本有序的前提下，下述排序方法中效率最高的是： A)直接插入排序 B)简单选择排序 C)快速排序 D)归并排序 5．栈S最多能容纳4个元素。现在6个元素按A、B、C、D、E、F的顺序进栈，下列哪一个序列是不可能的出栈序列？ A) A、B、C、D、E、F B) A、F、E、D 、C、B C) C、B、E、D、A、F D) C、D、B、F、E、A 四、填空题：(每小题2分,共 20分) 1.向一个有n个元素的有序表中插入一个新元素并保持原来顺序不 变，平均要移动个元素。 2.设广义表L=( ( ), ( ) )，则head(L)是；tail(L)是； L的长度是；深度是。
结构力学知识点复习过程
建筑物和工程设施中承受、传递荷载而起骨架作用的部分称为工程结构，简称为结构。 从几何角度来看，结构可分为三类，分别为：杆件结构、板壳结构、实体结构。 结构力学中所有的计算方法都应考虑以下三方面条件： ①力系的平衡条件或运动条件。 ②变形的几何连续条件。 ③应力与变形间的物理条件（或称为本构方程）。 结点分为：铰结点、刚结点。 铰结点：可以传递力，但不能传递力矩。 刚结点：既可以传递力，也可以传递力矩。 支座按其受力特质分为：滚轴支座、铰支座、定向支座、固定支座。 在结构计算中，为了简化，对组成各杆件的材料一般都假设为：连续的、均匀的、各向同性的、完全弹性或弹塑性的。 荷载是主动作用于结构的外力。 狭义荷载：结构的自重、加于结构的水压力和土压力。 广义荷载：温度变化、基础沉降、材料收缩。 根据荷载作用时间的久暂，可以分为：恒载、活载。 根据荷载作用的性质，可以分为：静力荷载、动力荷载。 结构的几何构造分析 在几何构造分析中，不考虑这种由于材料的应变所产生的变形。 杆件体系可分为两类： 几何不变体系------在不考虑材料应变的条件下，体系的位置和形状是不能改变的。 几何可变体系------在不考虑材料应变的条件下，体系的位置和形状是可以改变的。 自由度：一个体系自由度的个数，等于这个体系运动时可以独立改变的坐标的个数。 一点在平面内有两个自由度（横纵坐标）。 一个刚片在平面内有三个自由度（横纵坐标及转角）。 凡是自由度的个数大于零的体系都是几何可变体系。 一个支杆（链杆）相当于一个约束。可以减少一个自由度。 一个单铰（只连接两个刚片的铰）相当于两个约束。可以减少两个自由度。一个单刚结（刚性结合）相当于三个约束，可以减少三个自由度。 如果在一个体系中增加一个约束，而体系的自由度并不因而减少，则此约束称为多余约束。增加了约束，计算自由度会减少。因为w=s-n . 瞬变体系：本来是几何可变、经微小位移后又成为几何不变的体系称为瞬变体系。 实铰：两个刚片（地基也算一个刚片），如果用两根链杆给链接上，并且两根链杆能在其中一个刚片上交于一点，所构成的铰就叫实铰。 瞬铰：两个刚片（地基也算一个刚片），如果用两根链杆给链接上，两根链杆在两刚片间没有交于一点，而是在两根链杆的延长线上交于一点，从瞬时微小运动来看，这就是瞬铰了。两根链杆所起的约束作用等效于在链杆交点处上面放了一个单铰的约束作用。通常所起作用为转动。 截面上应力沿杆轴切线方向的合力，称为轴力。轴力以拉力为正。 截面上应力沿杆轴法线方向的合力称为剪力。剪力以绕微段隔离体顺时针转者为正。 截面上应力对截面形心的力矩称为弯矩。在水平杆件中，当弯矩使杆件下部受拉时，弯矩为正。 作轴力图和剪力图要注明正负号。作弯矩图时，规定弯矩图的纵坐标应画在受拉纤维一边，不注明正负号。 通常在桁架的内力计算中，采用下列假定： ①桁架的结点都是光滑的铰结点； ②各杆的轴线都是直线并通过铰的中心； ③荷载和支座反力都作用在结点上。 根据几何构造的特点，静定平面桁架可分为三类：简单桁架，联合桁架，复杂桁架。 在单杆的前提下，当结点无荷载作用时，单杆的内力必为零。此单杆称为零杆。 由链杆和梁式杆组成的结构，称为组合结构。 链杆只受轴力作用；梁式杆除受轴力作用外，还受弯矩和剪力作用。 三铰拱受力特点： ①在竖向荷载作用下，梁没有水平反力，而拱则有推力。 ②由于推力的存在，三铰拱截面上的弯矩比简支梁的弯矩小。弯矩的降低，使拱能更充分地发挥材料的作用。 ③在竖向荷载作用下，梁的截面内没有轴力，而拱的截面内轴力较大，且一般为压力。 合理拱轴线：在固定荷载作用下使拱处于无弯矩、无剪力、而只有轴力作用的轴线。 合理轴线：通常指具有不同高跨比的一组抛物线。 影响线 内力影响线：表示单位移动荷载作用下内力变化规律的图形。无论在剪力、弯矩、支座反力的影响线图中都需要标上正负号。影响线是研究移动荷载最不利位置和计算内力最大值（或最小值）的基本工具。 荷载：特定单位移动荷载P=1 固定、任意荷载最不利位置：如果荷载移动到某个位置，使某量Z达到最大值，则此荷载位置称为最不利位置。 影响线的一个重要作用，就是用来确定荷载的最不利位置。 定出荷载最不利位置判断的一般原则是：应当把数量大、排列密的荷载放在影响线竖距较大的部位。 计算结构的位移目的有两个： ①一个目的是验算结构的刚度，即验算结构的位移是否超过允许的位移限值。 ②另一个目的是为超静定结构的内力分析打下基础。 产生位移的原因主要有下列三种： ①荷载作用②温度变化和材料胀缩③支座沉降和制造误差 一组力可以用一个符号P表示，相应的位移也可用一个符号Δ表示，这种夸大了的力和位移分别称为广义力和广义位移。 图乘法的应用条件：①杆段应是等截面直杆段。②两个图形中至少应有一个是直线，标距y0 应取自直线图中。 互等定理包括四个普遍定理：①功的互等定理②位移互等定理 ③反力互等定理④位移反力互等定理。 3、对称结构就是指： ①结构的几何形式和支承情况对某轴对称。 ②杆件截面和材料性质也对此轴对称。（因而杆件的截面刚度EI对此轴对称） 4、对称荷载：对称荷载绕对称轴对折后，左右两部分的荷载彼此重合（作用点相对应、数值相等、方向相同） 反对称荷载：反对称荷载绕对称轴对折后，左右两部分的荷载正好相反（作用点相对应、数值相等、方向相反） 超静定结构有一个重要特点，就是无荷载作用时，由于其他因素（如：支座移动、温度改变、材料收缩、制造误差）的作用也可以产生内力。 超静定结构：由于其他因素（如：支座移动、温度改变、材料收缩、制造误差）的作用可以产生位移也可以产生内力。 静定结构：由于其他因素（如：支座移动、温度改变、材料收缩、制造误差）的作用可以产生位移但不能产生内力。 力法：多余未知力静定结构变形协调（位移相等） 位移法：结构独立结点位移（角、线位移）超静定单杆（是用位移表示的）平衡方程 2、系数EAi /Li是使杆端产生单位位移时所需施加的杆端力，称为杆件的刚度系数。 体系的自由度指的是确定物体位置所需要的最少坐标数目。 拱的基本特点是在竖向荷载作用下会产生水平支座反力。 .静定结构的特性：（1）静定结构的全部约束反力与内力都可以用静力平衡方程求得。（2）温度变化、支座位移不引起静定结构的内力。3)当一个平衡力系作用在静定结构的某一自身几何不变的杆上时，静定结构只在该力系作用的杆段内产生内力。(4).作用在静定结构的某一自身为几何不变的杆 段上的某一荷载，若用在该段上的一个等效 力系来代替，则结构仅在该段上的内力发生 变化，其余部分内力不变。 1.平面杆件结构分类？ 梁、刚架、拱、桁架、组合结构。 2.请简述几何不变体系的俩刚片规则。 两刚片用一个铰和一根不通过该铰链中心的链杆或不全交于一点也不全平行的三根链杆相联，则组成的体系是几何不变的，并且没有多余约束。 3.请简述几何不变体系的三刚片规则。 三刚片用不共线的三个铰两两相联或六根链杆两两相联，则组成的体系是几何不变体系，且没有多余约束。 4.从几何组成分析上来看什么是静定结构，什么是超静定结构？(几何特征) 无多余约束的几何不变体系是静定结构，有多余约束的几何不变体系是超静定结构，有几个多余约束，即为几次超静定。 5.静定学角度分析说明什么是静定结构，什么是超静定结构？ 只需要利用静力平衡条件就能计算出结构全部支座反力和构件内力的结构称为静定结构；全部支座反力和构件内力不能只用静力平衡条件确定的结构称为超静定结构。 6.如何区别拱和曲梁 杆轴为曲线且在竖向荷载作用下能产生水平推力的结构，称为拱；杆轴为曲线，但在竖向荷载作用下无水平推力产生，称为曲梁。 7.合理拱轴的条件？ 在已知荷载作用下，如所选择的三铰拱轴线能使所有截面上的弯矩均等于零，则此拱轴线为合理拱轴线。 仅供学习与参考
结构力学的知识点
双筋计算方法： 一As与As' 1、截面计算 1）假设a s=65mm，a s'=35mm，求得h0=h-a s 2）验算是否需要双筋。Mu= f cd bh02§b（1-0.5§b） 3）取§=§b，求As'=【M- f cd bh02§（1-0.5§）】/【f sd'（h0- a s'）】 4）求As=【f cd bx+f sd'As'】/ f sd 其中x=§b h0 下面选钢筋，钢筋层净距，钢筋间净距（大于30mm和直径d），保护层厚度，再计算a s和a s' 二、已知As'，求As 5）假设a s，求得h0=h-a s 6）求受压区高度x= h0-√h02-2【M- f sd'As'（h0- a s'）】/f cd b 7）当x﹤§b h0且x﹤2 a s'时，As=M/【f sd（h0- a s'）】 当x≤§b h0且x≥2 a s'时，As=【f cd bx+f sd'As'】/ f sd 8）选择受拉钢筋直径的数量，布置截面钢筋（同上） 2、截面复核 1）检查钢筋布置是否符合规要求 2）将As=？As'=？h0=？f cd f sd' f sd 若带入x=【f sd As- f sd'As'】/f cd b ≤§b h0 ﹤2 a s' 用Mu= f sd As（h0- a s'）计算正截面承载力 若2 a s'≤x≤§b h0，矩形截面抗弯承载力 Mu= f cd bx（h0-x/2）+ f sd'As'（h0- a s'）
一、As与As'均未知 1、截面设计 1）求偏心距e0=M/N 长细比l0/h﹥5，考虑偏心增大系数η（l0/h≤5时，取η=1）假设a s= a s'=45.当ηe0﹥0.3 h0时，为大偏心，反之， ξ1=0.27+2.7 e0/ h0 ξ2=1.15-0.01l0/h η=1+1/【1400（e0/ h0）】（l0/h）2ξ1ξ2 2）令§=§b，求As'=【Ne s- f cd bh02§b（1-0.5§b）】/ f sd'（h0- a s'） ≥ρmin bh （ρmin=0.2%）取σs= f sd 求As=【f cd bh0§b+ f sd'As'-N】/ f sd≥ρmin bh 二、已知As'，求As 1）求偏心距e0=M/N 长细比l0/h﹥5，考虑偏心增大系数η（l0/h≤5时，取η=1）假设a s= a s'=45.当ηe0﹥0.3 h0时，为大偏心，反之，2）计算受压区高度x= h0-√h02-2【Ne s - f sd'As'（h0- a s'）】/f cd b 当2 a s'﹤x≤§b h0时，取σs= f sd 求As=【f cd bx+ f sd'As'-N】/ f sd 当x≤§b h0 x≤2 a s'时，As=Ne s'/ f sd（h0- a s'） 3）选钢筋，看配筋率是否符合ρ+ρ'≥0.5%，纵筋最小净距（一般为30mm），重取a s= a s'=？，计算保护层厚度是否满足要求，最小截面宽度b min 2、截面复核 1）垂直于弯矩作用平面
数据结构综合习题集(含答案)
数据结构习题集 一、选择题 1．数据结构中所定义的数据元素，是用于表示数据的。（ C ） A.最小单位 B.最大单位 C.基本单位 D.不可分割的单位 2．从逻辑上可以把数据结构分为（ C ） A.动态结构、静态结构 B.顺序结构、链式结构 C.线性结构、非线性结构 D.初等结构、构造型结构 3．当待排序序列中记录数较少或基本有序时，最适合的排序方法为(A) A.直接插入排序法 B.快速排序法 C.堆排序法 D.归并排序法 4．关于串的的叙述，不正确的是( B) A.串是字符的有限序列 B.空串是由空格构成的串 C.替换是串的一种重要运算 D.串既可以采用顺序存储，也可以采用链式存储 5．带表头结点链队列的队头和队尾指针分别为front和rear，则判断队空的条件为（A ）A.front==rear B.front!=NULL C.rear!=NULL D.front==NULL 6．若构造一棵具有n个结点的二叉排序树，最坏的情况下其深度不会超过（B ） A.n/2 B.n C.(n+1)/2 D.n+1 7．将两个各有n个元素的有序表合并成一个有序表，其最少的比较次数为（A） A.n B.2n-1 C.2n D.n2 8．设顺序表有19个元素，第一个元素的地址为200，且每个元素占3个字节，则第14个元素的存储地址为(B ) A.236 B.239 C.242 D.245 9．一个栈的入栈序列是a,b,c,d,e，则栈的输出序列不可能是(A ) A.dceab B.decba C.edcba D.abcde 10．元素大小为1个单元，容量为n个单元的非空顺序栈中，以地址高端为栈底，以top 作为栈顶指针，则出栈处理后，top的值应修改为(D ) A.top=top B.top=n-1 C.top=top-1 D.top=top+1 11．设有一个10阶的对称矩阵A，采用压缩存储方式以行序为主序存储，a00为第一个元素，其存储地址为0，每个元素占有1个存储地址空间，则a45的地址为（ B ） A.13 B.35 C.17 D.36 12．栈和队列(C) A.共同之处在于二者都是先进先出的特殊的线性表 B.共同之处在于二者都是先进后出的特殊的线性表 C.共同之处在于二者都只允许在顶端执行删除操作
数据结构考试试题
数据结构辅导试题一 一、简答问题： 1．四类数据结构 2．线性结构与非线性结构有何差别？ 3．简述算法的定义与特性。 4．设有1000个无序元素，仅要求找出前10个最小元素，在下列排序方法中（归并排序、基数排序、快速排序、堆排序、插入排序）哪一种方法最好，为什么？ 二、判断正误：（每小题1分，共5分）正确在（）内打√，否则打 。1．（）二叉排序树或是一棵空树，或是具有下列性质的二叉树： 若它的左子树非空，则根结点的值大于其左孩子的值， 若它的右子树非空，则根结点的值大于其右孩子的值。 2．（）索引顺序表的特点是块内可无序，块间要有序。 3．（）子串是主串中任意个连续字符组成的序列。 4．（）线性结构只能用顺序结构存放，非线性结构只能用链表存放。 5．（）快速排序的枢轴元素可以任意选定。 三、单项选择题：(每小题1分，共4分) 1．栈S最多能容纳4个元素。现有6个元素按A、B、C、D、E、F的顺序进栈, 问下列哪一个序列是可能的出栈序列? A)E、D、C、B、A、F B)B、C、E、F、A、D C)C、B、E、D、A、F D)A、D、F、E、B、C 2．将一棵有100个结点的完全二叉树从根这一层开始，每一层从左到右依次对结点进行编号，根结点编号为1，则编号为49的结点的左孩子的编号为： A、98 B、99 C、50 D、48 3. 对下列关键字序列用快速排序法进行排序时，速度最快的情形是： A）{21、25、5、17、9、23、30} B）{25、23、30、17、21、5、9} B）{21、9、17、30、25、23、5} D）{5、9、17、21、23、25、30} 4. 设森林F中有三棵树，第一、第二和第三棵树的结点个数分别为M1、M2和M3。与森林F对应的二叉树根结点的右子树上的结点个数是： A）M1 B）M1+M2 C）M3 D）M2+M3 四、填空题：(每小题2分,共 20分) 1．设一哈希表表长M为100 ，用除留余数法构造哈希函数，即H（K）=K MOD P（P<=M）, 为使函数具有较好性能，P应选 2．N个结点的二叉树采用二叉链表存放，共有空链域个数为 3．单链表与多重链表的区别是 4．在各种查找方法中，平均查找长度与结点个数无关的是 5．深度为6（根层次为1）的二叉树至多有个结点。 6．已知二维数组A[20][10]采用行序为主方式存储,每个元素占2个存储单元,并且A[10][5]的存储地址是1000,则A[18][9]的存储地址是 7．在一个单链表中p所指结点之后插入s所指结点时,应执行 s->next= 和p->next= 的操作. 8．广义表((a,b),c,d)的表头是,表尾是 9．循环单链表LA中，指针P所指结点为表尾结点的条件是 10．在一个待排序的序列中，只有很少量元素不在自己最终的正确位置上，但离他们的正确位置都不远，则使用排序方法最好。 五、构造题：（每小题5分，共25分） 1．已知一棵二叉树，其中序序列DBCAFGE，后序序列DCBGFEA，构造该二叉树。2．设哈希表长度为11，哈希函数H（K）=（K的第一字母在字母表中的序号）MOD11，若输入顺序为（D，BA，TN，M，CI，I，K，X，TA），处理冲突方法为线性探测再散
结构力学主要知识点归纳
结构力学主要知识点 一、基本概念 1、计算简图：在计算结构之前，往往需要对实际结构加以简化，表现其主要特点，略去其次要因素，用一个简化图形来代替实际结构。通常包括以下几个方面： A 、杆件的简化：常以其轴线代表 B 、支座和节点简化： ①活动铰支座、固定铰支座、固定支座、滑动支座； ②铰节点、刚节点、组合节点。 C 、体系简化：常简化为集中荷载及线分布荷载 D 、体系简化：将空间结果简化为平面结构 2、结构分类： A 、按几何特征划分：梁、拱、刚架、桁架、组合结构、悬索结构。 B 、按内力是否静定划分： ①静定结构：在任意荷载作用下，结构的全部反力和内力都可以由静力平衡条件确定。 ②超静定结构：只靠平衡条件还不能确定全部反力和内力，还必须考虑变形条件才能确定。 二、平面体系的机动分析 1、体系种类 A 、几何不变体系：几何形状和位置均能保持不变；通常根据结构有无多余联系，又划分为无多余联系的几何不变体系和有多余联系的几何不变体系。 B 、几何可变体系：在很小荷载作用下会发生机械运动，不能保持原有的几何形状和位置。常具体划分为常变体系和瞬变体系。 2、自由度：体系运动时所具有的独立运动方程式数目或者说是确定体系位置所需的独立坐标数目。 3、联系：限制运动的装置成为联系（或约束）体系的自由度可因加入的联系而减少，能减少一个自由度的装置成为一个联系 ①一个链杆可以减少一个自由度，成为一个联系。②一个单铰为两个联系。 4、计算自由度：)2(3r h m W +-=,m 为刚片数，h 为单铰束，r 为链杆数。 A 、W>0,表明缺少足够联系，结构为几何可变； B 、W=0，没有多余联系； C 、W<0,有多余联系，是否为几何不变仍不确定。 5、几何不变体系的基本组成规则： A 、三刚片规则：三个刚片用不在同一直线上的三个单铰两两铰联，组成的体系是几何不变的，而且没有多余联系。 B 、二元体规则：在一个刚片上增加一个二元体，仍未几何不变体系，而且没有多余联系。 C 、两刚片原则：两个刚片用一个铰和一根不通过此铰的链杆相联，为几何不变体系，而且没有多余联系。 6、虚铰：连接两个刚片的两根链杆的作用相当于在其交点处的一个单铰。虚铰在无穷远处的体系分析可见结构力学P20，自行了解。 7、静定结构的几何构造为特征为几何不变且无多余联系。 三、静定梁与静定钢架 1、内力图绘制： A 、内力图通常是用平行于杆轴线方向的坐标表示截面的位置，用垂直于杆轴线的坐标表示
数据结构形考作业答案
数据结构（本）形考作业1参考答案: 一、单项选择题 1．C 2．D 3．C 4．C 5．D 6．C 7．C 8．C 9．A 10．B 二、填空题 1．n-i+1 2．n-i 3.集合、线性表、树、图 4. 存储结构、物理结构 5.线性表图 6. 有穷性、确定性、可行性、有输入、有输出 7. 图 8.树 9. 线性表 10． n-1 O(n) 11．s->next=p->next; 12．head 13．q->next=p->next; 14．p->next=head; 15．单链表 16．顺序存储链式存储 17．存储结构 18.两个后继结点前驱结点尾结点头结点 19．指向头结点的指针指向第一个结点的指针 20．链式链表 三、问答题 1．简述数据的逻辑结构和存储结构的区别与联系，它们如何影响算法的设计与实现？ 答：若用结点表示某个数据元素，则结点与结点之间的逻辑关系就称为数据的逻辑结构。数据在计算机中的存储表示称为数据的存储结构。可见，数据的逻辑结构是反映数据之间的固有关系，而数据的存储结构是数据在计算机中的存储表示。尽管因采用的存储结构不同，逻辑上相邻的结点，其物理地址未必相同，但可通过结点的内部信息，找到其相邻的结点，从而保留了逻辑结构的特点。采用的存储结构不同，对数据的操作在灵活性，算法复杂度等方面差别较大。 2．解释顺序存储结构和链式存储结构的特点，并比较顺序存储结构和链式存储结构的优缺点。 答：顺序结构存储时，相邻数据元素的存放地址也相邻，即逻辑结构和存储结构是统一的，，要求内存中存储单元的地址必须是连续的。 优点：一般情况下，存储密度大，存储空间利用率高。 缺点：（1）在做插入和删除操作时，需移动大量元素；（2）由于难以估计，必须预先分配较大的空间，往往使存储空间不能得到充分利用；（3）表的容量难以扩充。 链式结构存储时，相邻数据元素可随意存放，所占空间分为两部分，一部分存放结点值，另一部分存放表示结点间关系的指针。 优点：插入和删除元素时很方便，使用灵活。
数据结构综合练习题
数据结构综合练习题
数据结构（一） 一、选择题 1．组成数据的基本单位是（ C ）。 (A) 数据项(B) 数据类型(C) 数据元素(D) 数据变量 2．设数据结构A=(D，R)，其中D={1，2，3，4}，R={r}，r={<1，2>，<2，3>，<3，4>，<4，1>}，则数据结构A 是（ C ）。 (A) 线性结构(B) 树型结构(C) 图型结构(D) 集合 3．数组的逻辑结构不同于下列（ D ）的逻辑结构。(A) 线性表(B) 栈(C) 队列(D) 树 4．二叉树中第i(i≥1)层上的结点数最多有（C ）个。 (A) 2i (B) 2i(C) 2i-1(D) 2i-1 5．设指针变量p指向单链表结点A，则删除结点A的后继结点B需要的操作为（A ）。 (A) p->next=p->next->next (B) p=p->next (C) p=p->next->next (D) p->next=p 6．设栈S和队列Q的初始状态为空，元素E1、E2、E3、E4、E5和E6依次通过栈S，一个元素出栈后即进入队列Q，若6个元素出列的顺序为E2、E4、E3、E6、E5和E1，则栈S的容量至少应该是（ C ）。 (A) 6 (B) 4 (C) 3 (D) 2
7．将10阶对称矩阵压缩存储到一维数组A中，则数组A 的长度最少为（ C ）。 (A) 100 (B) 40 (C) 55 (D) 80 8．设结点A有3个兄弟结点且结点B为结点A的双亲结点，则结点B的度数数为（ B ）。 (A) 3 (B) 4 (C) 5 (D) 1 9．根据二叉树的定义可知二叉树共有（ B ）种不同的形态。 (A) 4 (B) 5 (C) 6 (D) 7 10.设有以下四种排序方法，则（ B ）的空间复 杂度最大。 (A) 冒泡排序(B) 快速排序(C) 堆排序(D) 希尔排序 11、以下说法正确的是（ A ） A.连通图的生成树，是该连通图的一个极小连通子图。 B.无向图的邻接矩阵是对称的，有向图的邻接矩阵一定是不对称的。 C.任何一个有向图，其全部顶点可以排成一个拓扑序列。 D.有回路的图不能进行拓扑排序。 12、以下说法错误的是 ( D ) A.一般在哈夫曼树中，权值越大的叶子离根结点越近 B.哈夫曼树中没有度数为1的分支结点 C.若初始森林中共有n裸二叉树，最终求得的哈夫曼树
数据结构简答题
第二章：线性表 四. 简答题 1. 分析下列情况下，采用何种存储结构更好些。 (1)若线性表的总长度基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素。 (2)如果 n 个线性表同时并存，并且在处理过程中各表的长度会动态发生变化。 (3)描述一个城市的设计和规划。 答： ⑴应选用顺序存储结构。很少进行插入和删除操作，所以空间变化不大，且需要快速存取，所 以应选用顺序存储结构。 ⑵应选用链式存储结构。链表容易实现表容量的扩充，适合表的长度动态发生变化。 ⑶应选用链式存储结构。因为一个城市的设计和规划涉及活动很多，需要经常修改、扩充和删 除各种信息，才能适应不断发展的需要。而顺序表的插入、删除的效率低，故不合适。 第三章：栈和队列 四. 简答题 1. 设有一个栈，元素进栈的次序为 A，B，C，D，E，能否得到如下出栈序列，若能，请写出操作序列，若不能，请说明原因。 ⑴ C，E，A，B，D ⑵ C，B，A，D，E ⑵能，因为在 C、E 出栈后，A 一定在栈中，而且在 B 的下面，不可能先于 B 出栈 ⑵可以，设Ｉ为进栈操作，Ｏ为入栈操作，则其操作序列为 IIIOOOIOIO。 2. 在操作序列 push(1). push(2). pop. push(5). push(7). pop. push(6)之后，栈顶元素和
栈底元素分别是什么？（push(k)表示 k 入栈，pop 表示栈顶元素出栈。） 栈顶元素为 6，栈底元素为 1。 3. 在操作序列 EnQueue(1). EnQueue(3). DeQueue. EnQueue(5). EnQueue(7). DeQueue. EnQueue(9)之后，队头元素和队尾元素分别是什么？（EnQueue(k)表示整数 k 入队，DeQueue 表示队头元素出队）。 队头元素为 5，队尾元素为 9。 第六章：树和二叉树
数据结构选择题
选择一项： 1. 108 2. 110 3. 100 4. 120 2.在n个结点的顺序表中，算法的时间复杂度是O(1)的操作是（ b） 选择一项： a. 删除第i个结点（1≤i≤n） b. 访问第i个结点（1≤i≤n）和求第i个结点的直接前驱（2≤i≤n） c. 将n个结点从小到大排序 d. 在第i个结点后插入一个新结点（1≤i≤n） 3.以下说法错误的是（ d）。 选择一项： a. 由于顺序存储要求连续的存储区域，所以在存储管理上不够灵活 b. 顺序存储的线性表可以随机存取 c. 求表长、定位这两种运算在采用顺序存储结构时实现的效率不比采用链式存储结构时实现的效率低 d. 线性表的链式存储结构优于顺序存储结构 4.单链表的存储密度（ b）。 选择一项： a. 不能确定 b. 小于1 c. 大于1 d. 等于1 5.向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动的元素个数为（ c）。 选择一项： a. 63 b. 7 c. d. 8 6.在一个长度为n的顺序表中，在第i个元素（1≤i≤n+1）之前插入一个新元素时须向后移动（ b）个元素。 选择一项： a. n-i b. n-i+1 c. i d. n-i-1 7.在单链表中，要将s所指结点插入到p所指结点之后，其语句应为（a ）。 选择一项： a. s->next=p->next; p->next=s; b. (*p).next=s; (*s).next=(*p).next; c. s->next=p->next; p->next=s->next;
d. s->next=p+1; p->next=s; 8.在双向循环链表中，在p指针所指的结点后插入q所指向的新结点，其修改指针的操作是（b ）。 选择一项： a. p->next=q; q->prior=p; p->next->prior=q; q->next=q; b. q->prior=p; q->next=p->next; p->next->prior=q; p->next=q; c. p->next=q; p->next->prior=q; q->prior=p; q->next=p->next; d. q->prior=p; q->next=p->next; p->next=q; p->next->prior=q; 9.在双向链表存储结构中，删除p所指的结点时须修改指针（c ）。 选择一项： a. p->prior=p->next->next; p->next=p->prior->prior; b. p->next=p->next->next; p->next->prior=p; c. p->next->prior=p->prior; p->prior->next=p->next; d. p->prior->next=p; p->prior=p->prior->prior; 10.将两个各有n个元素的有序表归并成一个有序表，其最少的比较次数是（c ）。 选择一项： a. 2n b. n-1 c. n d. 2n-1 11.线性表L=(a1，a2,……an)，下列说法正确的是（ b）。 选择一项： a. 表中诸元素的排列必须是由小到大或由大到小 b. 除第一个和最后一个元素外，其余每个元素都有一个且仅有一个直接前驱和直接后继。 c. 每个元素都有一个直接前驱和一个直接后继 d. 线性表中至少有一个元素 12.线性表若采用链式存储结构时，要求内存中可用存储单元的地址（d ）。 选择一项： a. 部分地址必须是连续的 b. 一定是不连续的 c. 必须是连续的 d. 连续或不连续都可以 13.线性表Ｌ在（d ）情况下适用于使用链式结构实现。 选择一项： a. Ｌ中结点结构复杂 b. Ｌ中含有大量的结点 c. 需经常修改Ｌ中的结点值 d. 需不断对Ｌ进行删除插入 14.若指定有n个元素的向量，则建立一个有序单链表的时间复杂性的量级是（ b）。 选择一项：
结构力学
第一讲平面体系的几何组成分析及静定结构受力分析 【内容提要】 平面体系的基本概念，几何不变体系的组成规律及其应用。静定结构受力分析方法，反力、内力计算与内力图绘制，静定结构特性及其应用。 【重点、难点】 静定结构受力分析方法，反力、内力计算与内力图绘制 一、平面体系的几何组成分析 (一)几何组成分析 按机械运动和几何学的观点，对结构或体系的组成形式进行分析。 (二)刚片 结构由杆(构)件组成，在几何分析时，不考虑杆件微小应变的影响，即每根杆件当做刚片。 (三)几何不变体系 体系的形状(或构成结构各杆的相对位置)保持不变，称为几何不变体系，如图6-1-1 (四)几何可变体系 体系的位置和形状可以改变的结构，如图6-1-2。 图6-1-1 图6-1-2 (五)自由度 确定体系位置所需的独立运动参数数目。如一个刚片在平面内具有3个自由度。(六)约束
减少体系独立运动参数(自由度)的装置。 1．外部约束 指体系与基础之间的约束，如链杆(或称活动铰)，支座(固定铰、定向铰、固定支座)。2．内部约束 指体系内部各杆间的联系，如铰接点，刚接点，链杆。 规则一：一根链杆相当于一个约束。 规则二：一个单铰(只连接2个刚片)相当于两个约束。 推论：一个连接n 个刚片的铰(复铰)相当于(n－ 1)个单铰。 规则三：一个单刚性结点相当于三个约束。 推论：一个连接个刚片的复刚性结点相当于( n－ 1)个单刚性结点。 3．必要约束 如果在体系中增加一个约束，体系减少一个自由度，则此约束为必要约束。 4．多余约束 如果体系中增加一个约束，对体系的独立运动参数无影响，则此约束称为多余约束。(七)等效作用 1．虚铰 两根链杆的交叉点或其延长线的交点称为(单)虚铰，其作用与实铰相同。 平行链杆的交点在无限远处。 2．等效刚片 一个内部几何不变的体系，可用一个刚片来代替。 3．等效链杆。 两端为铰的非直线形杆，可用一连接两铰的直线链杆代 二、几何组成分析 (一)几何不变体系组成的基本规则
数据结构-综合练习题-打印
数据结构综合练习题 1填空题 1.数据结构包含三个方面的内容，分别是数据的逻辑结构、数据的存储结构和数据的运算。 2.实现数据结构的四种存储方法有顺序存储方法、链接存储方法、索引存储方法和散列存储方法。 3.数据结构的逻辑结构有线性结构和非线性结构两大类。 4.一种抽象数据类型包括抽象数据的组织和与之相关的操作两个部分。 5.算法的五个重要特性是输入、输出、确定性、可行性和有穷性。 6.栈顶的位置是随进栈和出栈操作而变化的。 7.在链队列只有一个元素的情况下，对其做删除操作时，应当把对头指针和队尾指针都置为null。 8.操作系统中先来先服务是数据结构中的队列应用的典型例子。 9.在解决计算机主机与打印机之间速度不匹配问题时，通常设置一个打印数据缓冲区，主机将要输 出的数据依次写入该缓冲区，而打印机从该缓冲区中取出数据打印。该缓冲区应该是一个队列结构。 10.有一棵树如下图所示，回答下列问题。11.有一棵树如下图所示，回答下列问题。 （1）这棵树的根结点是K1；（1）结点k3的度是 2 ； （2）这棵树的叶子结点是K2，K4，K5，K7；（2）这棵树的度为 3 ；
12.有一棵树如下图所示，回答下列问题。 13有一棵树如下图所示，回答下列问题。 这棵树的深度为 4 ； （1）结点K3的子女是 K5 ，K6 ； （2）结点K3的双亲结点是 K1 。 14.在一棵二叉树中，度为零的结点个数为n0，度为2的结点的个数为n2，则有n0=n2+1。 15.n （n>0）个结点的二叉树高度最大是 n ，其深度最小是?log 2(n+1)?或??1log 2+n 。 16.n(n>0)个结点的满二叉树深度是)1(log 2+n ，叶子结点数是 (n+1)/2。阿 17.下面二叉树的中序序列是GDHABC 。 18.n （n>0）个结点的哈夫曼树中度为2的结点共 (n-1)/2 个，叶子结点共(n+1)/2个。 19.n 个顶点的有向图最多有 n*(n-1) 条边。 20.n （n>0）个顶点的连通无向图各顶点度之和最少是 2(n-1) 。 21.有6个顶点的无向图至少应有 5 条边才能确保是一个连通图。 22. n(n>0)个顶点的连通无向图至少有 n-1 条边。 23. 恰有 n(n-1) 条边的有向图称为有向完全图。