《数据结构》复习卷

1、数据结构复习卷一、填空题1、组成数据的基本单位是 数据元素 ，最小单位是 数据项 。2、算法的五个重要特性是 有穷性 、 确定性 、 可行性 、 1个或多个输出 、 0个或多个输入 。3、数据的存储结构主要分为 顺序存储结构 和 链式存储结构 两种。4、下面程序段的时间复杂度是 n*m 。for(i=0;i<n;i+) for(j=0;j<m;j+) Aij=0;5、栈的特点是 先进后出 ，队列的特点是 先进先出 ，栈和队列都属于 线性 结构。6、图定义为：G=(V，E)，其中，V是_顶点的有穷非空 的集合，E是 顶点间关系的有穷 的集合。k1k2k3k4k5k6k77、有一棵树如

2、图所示，请回答以下问题：（1）这棵树的根结点是_ K1_；（2）这棵树的叶子结点是_ K2 K5 K7 K4_；（3）这棵树的深度是_4_；8、二叉树的三种遍历方法分别为 先根遍历 、 中根遍历 、 后根遍历 。 9、图的遍历方法_深度优先搜索遍历_和_广度优先搜索遍历_。10、按照排序过程中存储器的不同，可将排序分为 内部排序 和 外部排序 。11、算法的复杂度分为 时间复杂度 、 空间复杂度 两种。12、算法的五个重要特性是1个或多个输出 、 0个或多个输入 、有穷性、 确定性 、 可行性 。13、数据的存储结构主要分为 逻辑存储结构 和 物理存储结构 两种。14、栈和队列都是 运算受限

3、的线性表，栈的特点是 先进后出 ，队列的特点是 先进先出 。15、图定义为：G=(V，E)，其中，V是_顶点的有穷非空_的集合，E是_顶点间关系的有穷_的集合。16、有一棵树如图所示，请回答以下问题：（1）这棵树的根结点是_a _；（2）这棵树的叶子结点是_ g,e,i _；（3）这棵树的深度是_5 _；（4）结点c的孩子结点是_ e,f _；（5）结点h的双亲结点是_f _；（6）结点e的堂兄弟是 d ，兄弟是 f 。17、线性表中 元素的个数 称为表的长度。18、在任意二叉树中，若叶子结点的个数为n0，度为1的结点数为n1，度为2的结点数为n2，则满足关系 n0= n2+1 。19、图的遍

4、历方法_深度优先搜索_和 广度优先搜索_。20、按照排序过程中存储器的不同，可将排序分为 内部排序 和 外部排序 。二、选择题（将答案写在题后的方框内）1、一个向量第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是（B）。A、110 B、108 C、100 D、1202、树最适合用来表示（ C ）。A、有序数据元素B、无序数据元素C、元素之间具有分支层次关系的数据D、元素之间无联系的数据3、一棵二叉排序树T，用（ B ）方法进行遍历，可以得到各结点键值的递增序列。  A、先根遍历B、中根遍历C、层次遍历D、后根遍历4、在下述的排序方法中，不属于内部排序的是（ C

5、）。A、选择排序法 B、插入排序法 C、拓扑排序法 D、归并排序法5、线性表是一个（A ）。A、有限序列，可以为空B、有限序列，不能为空C、无限序列，可以为空D、无限序列，不能为空6、以下数据结构中，（ A ）是非线性数据结构。A、树 B、字符串 C、队 D、栈7、如果最常用的操作是取第i个结点及其前驱，最节省时间的存储方式是（ D ）。A、单链表B、双向链表C、单循环链表D、顺序表8、按照二叉树的定义，具有3个结点的二叉树有（ C ）种.A、3 B、4 C、5 D、69、算法指的是（ D ）。A、计算机程序B、解决问题的计算方法C、排序算法D、解决问题的有限运算序列10、深度为5的二叉树至多

6、有（ C ）个结点。A、16B、32C、31D、1011、一个向量第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是（ B ）。A、110 B、108 C、100 D、12012、树最适合用来表示（ C ）。A、有序数据元素B、无序数据元素C、元素之间具有分支层次关系的数据D、元素之间无联系的数据13、一棵二叉排序树T，用（ B ）方法进行遍历，可以得到各结点键值的递增序列。  A、先根遍历B、中根遍历C、层次遍历D、后根遍历14、在下述的排序方法中，不属于内部排序的是（ C ）。A、选择排序法 B、插入排序法 C、拓扑排序法 D、归并排序法15、有关二叉树下列说

7、法正确的是（ A ）A、二叉树的度为2B、一棵二叉树的度可以小于2C、二叉树中至少有一个结点的度为2D、二叉树中任何一个结点的度都为216、以下数据结构中，（ A ）是非线性数据结构。A、树 B、字符串 C、队 D、栈17、链表不具备的特点是（ A ）。A、可随机访问任意一个结点B、插入和删除不需要移动任何元素C、不必事先估计存储空间D、所需空间与其长度成正比18、向一个有126个元素的顺序表中插入一个新元素并保存，原来顺序不变，平均要移动（ C ）个元素。A、8B、63.5C、63D、719、如果最常用的操作是取第i个结点及其前驱，最节省时间的存储方式是（ D ）。A、单链表B、双向链表C、

8、单循环链表D、顺序表20、按照二叉树的定义，具有3个结点的二叉树有（ C ）种. A. 3 B. 4 C. 5 D. 621、深度为5的二叉树至多有（ C ）个结点。A、16B、32C、31D、1022、算法指的是（ D ）。A、计算机程序B、解决问题的计算方法C、排序算法D、解决问题的有限运算序列23、以下何种排序是稳定的？（ A ）A、直接插入排序 B、希尔排序C、快速排序 D、直接选择排序24、对线性表，在下列情况下应当采用链表表示的是（ B ）。A、经常需要随机地存取元素B、经常需要进行插入和删除操作C、表中元素需要占据一片连续的存储空间D、表中元素的个数不变25、在单链表中，指针p指

9、向元素为x的结点，实现“删除x的后继”的语句是（ B ）。A、p =pnext；B、pnext=pnextnext；C、pnext=p；D、p=pnextnext；26、在（ C ）运算中，使用顺序表比链表好。 A、插入 B、删除 C、根据序号查找 D、根据元素值查找27、线性表是一个（ A ）。A、有限序列，可以为空B、有限序列，不能为空C、无限序列，可以为空D、无限序列，不能为空28、一个有n个顶点的无向图最多有（ C ）条边。A、n B、n (n-1) C、n (n-1)/2 D、2n29、对线性表进行折半查找时，要求线性表必须（ C ）。A、以顺序方式存储B、以链接方式存储C、以顺序方

10、式存储，且结点按关键字有序排列D、以链接方式存储，且结点按关键字有序排列30、若让元素1，2，3依次进栈，则出栈次序不可能出现（ C ）的情况。A、3，2，1 B、2，1，3 C、3，1，2 D、1，3，2三、综合题1、请画出具有3个结点的所有二叉树形状。ABCABCABCABCABC2试写出右图所示的二叉树的前序、中序和后序序列。前序序列：abdgcefhi中序序列：dgbaechif后序序列：gdbeihfca3、请将下图所给的树转换为的二叉树。HIKLMJABCDEFHABCDEFIKJML4、对于权值W=14，7，4，20，2，试写出构造哈夫曼树的过程，并计算其带权路径长度WPL。27147204261347带权路径长度WPL=2*4+4*4+7*3+14*2+20*1=935、已知序列30，50，60，35，86，10 ，请给出采用起泡排序法对该序列作降序排序时的每一趟的结果。初始关键字：30 5060358610第一趟：506035863010第二趟：605086353010第三趟：608650353010第四趟：8660503530106、（1）将树转换成二叉树。（2）将二叉树转换成森林。ABCDEFABCEGDF（1）（2）ABCDEF7、对于权值W=14，7