《数据结构复习资料》由会员分享，可在线阅读，更多相关《数据结构复习资料（3页珍藏版）》请在装配图网上搜索。
1、一、填空题1、栈的特点是先进后出（或后进先出），队列的特点是先进先出。2、顺序表中逻辑上相邻的元素物理位置也相邻， 单链表中逻辑上相邻的元素物理位置不相邻。3、算法的5 个重要特性是、。4、线性表、栈、队列都是线性结构，可以在线性表的任何位置插入和删除元素，对于栈只能在栈顶 位置插入和删除元素，对于队列只能在队尾位置插入和只能在队头删除元素。5、下面树的先序、中序、后续遍历的结果依次为、B. 修改尾指针D. 头、尾指针可能都要修改B.都是先进先出D.没有共同点B. 无序数据元素C.元素之间具有分支层次关系的数据D. 元素之间无联系的数据6、当数据量特别大需借助外部存储器对数据进行排序时，则这种
2、排序称为外部排序。7、在堆排序、快速排序和归并排序中，若从节省存储空间的角度考虑，则应首先选取堆排序方法； 若只从排序结果的稳定性考虑，则应选择归并排序方法；若只从平均情况下排序的速度来考虑，则 应选取快速排序方法。、选择题1、算法分析的两个主要方面是（）。A. 时间复杂度和空间复杂度B. 正确性和简明性C. 可读性和文档性D. 健壮性和科学性2、对于线性表最常用的操作是查找指定序号的元素和在末尾插入元素，则选择（）最节省时间。A. 顺序表B. 带头结点的双循环链表C. 单链表D. 带尾结点的单循环链表5、循环队列在进行删除运算时（）A. 仅修改头指针C. 头、尾指针都要修改6、栈和队列的共同
3、点是（）。A.都是先进后出C.只允许在端点处插入和删除元素7、树最适合用来表示（）A.有序数据元素8、如果结点A有3个兄弟，而且B是A的双亲，则B的度是（）A. 4B. 5C. 19、有关二叉树下列说法正确的是（）A. 二叉树的度为 2C. 二叉树中至少有一个结点的度为2D. 3B. 一棵二叉树的度可以小于 2D. 二叉树中任何一个结点的度都为210、一棵完全二叉树上有 1001 个结点，其中叶子结点的个数是（）A. 250B. 500C. 505D. 以上答案都不对11、静态查找表与动态查找表二者的根本差别在于（B）A. 它们的逻辑结构不一样B. 施加在其上的操作不同C. 所包含的数据元素的
4、类型不一样D. 存储实现不一样12、顺序查找法适合于存储结构为（B）的线性表。A. 散列存储B. 顺序存储或链接存储C. 压缩存储D. 索引存储13 、下面描述不正确的是（ D ）A. 顺序查找对表中元素存放位置无任何要求，当n较大时，效率低。B. 静态查找表中关键字有序时，可用二分查找。C. 分块查找也是一种静态查找表。D. 经常进行插入和删除操作时可以采用二分查找。14、分块查找时确定块的查找可以用顺序查找，也可以用（），而在块中只能是（A）A. 二分查找，顺序查找B. 静态查找，顺序查找C. 二分查找，二分查找D. 散列查找，顺序查找15、从末排序的序列中依次取出一个元素与已排序序列中的
5、元素依次进行比较，然后将其放在排序 序列的合适位置，该排序方法称为（A）排序法A. 插入B. 选择C. 希尔D. 二路归并16、快速排序方法在（C）情况下最不利于发挥其长处。A. 要排序的数据量太大B. 要排序的数据中含有多个相同值C. 要排序的数据已基本有序D. 要排序的数据个数为奇数17、下述几种排序方法中，要求内存量最大的是（D）A. 插入排序B. 选择排序C. 快速排序D. 归并排序20、使用顺序存储结构对二叉进行存储时，一个深度为k的二叉树需要（）个存储空间。A. 2kB. 2kC. 2k+1D. 2k-1三、判断1、在线性表的顺序存储结构中，逻辑上相邻的两个元素在物理位置上并不一定
6、紧邻。 （）2、在线性表的顺序存储结构中，插入和删除时，移动元素的个数与该元素的位置有关。 （）3、栈和队列都是运算受限的线性表，只允许在表端点处进行操作。（）4、若队列中只有一个元素，删除该元素后，队头队尾指针都需要修改。（）5、树的度是树内各结点的度之和。（）6、一棵树中的叶子结点数一定等于与其对应的二叉树中的叶子结点数。（）7、二叉树就是结点度为2的树。 （）8、二分查找只适用于有序表，包括有序的顺序表和有序的链表。（）9、若二叉树中每个结点的值均大于其左孩子的值，小于其右孩子的值，则该二叉树一定是二叉查找 树。（）10、内排序中的快速排序方法，在任何情况下均可得到最快的排序效果。（）五、简答题1、简述栈和队列之间的相同点和不同点。2、请简述顺序表的特点。3、请简述二叉树的遍历有哪几种，每种遍历的特点是什么。4、简述二分查找的基本原理。5、什么是内排序? 什么是外排序?六、分析题请将下面的森林转换为二叉树，绘图并说明整个转换过程。
数据结构复习资料
