最终数据结构复习题

1、一、 单项选择题1在一个长度为n的顺序表的表尾插入一个新元素的渐进时间复杂度为（）A. O ( n ) B .O ( 1 ) C. O ( n 2 ) D. O ( log2n )设单链表中结点的结构为（data , link ）。已知指针q所指结点是指针p所指结点的直接前驱，若在*q与 *p之间插入结点*s，则应执行下列哪一个操作？（）A. s link = p link; p link = s B. q link = s ; s link = pC. p link = s link ; s link = pD. p link = s; slink = q在循环队列中用数组A0.m-1 存放

2、队列元素，其队头和队尾指针分别为front和rear，则当前队列中的元素个数是（ ）。 A. ( front - rear + 1) % m B. ( rear - front + 1) % mC. ( front - rear + m) % m D. ( rear - front + m) % m4、设有一个10阶的对称矩阵1010，采用压缩存储方式按行将矩阵中下三角部分的元素存入一维数组 中，00存入0中，则85在 中 ( ) 位置。A. 32 B. 33 C. 41 D. 65具有65个结点的完全二叉树的高度为（ ）。（根的层次号为1）A. 8 B. 7 C. 6 D. 5树中所有结点的

3、度等于所有结点数加（ ）A. 0 B. 1 C. -1 D.27.一个高度为h的满二叉树共有n个结点，其中有m个叶子结点，则有（ ）成立。A n=h+m B h+m=2n C m=h-1 D n=2m-18.讨论树、森林和二叉树的关系，目的是为了（ ）。A 借助二叉树上的运算方法去实现对树的一些运算B 将树、森林按二叉树的存储方式进行存储并利用二叉树的算法解决树的有关问题C 将树、森林转换成二叉树D 体现一种技巧，没有什么实际意义9.对于一个具有n个顶点的无向图，若采用邻接矩阵存储，则该矩阵的大小是（ ）。A n B (n-1)2 C n-1 D n210.G是一个非连通无向图，共有28条边，

4、则该图至少有（ ）个顶点。A 6 B 7 C 8 D 911、在一个单链表中，如果m所指结点是n所指结点的后继，若在n和m之间插入k所指结点，应执行操作（ ）。      A、k >next=m>next; m>next=k;       B、m >next=k>next; k>next=m;      C、n >next=k; k>next=m;

5、           D、m >next=k; k>next=n;12、 一个栈的入栈序列是A,B,C,D,E,则栈的出栈序列不可能是（     ）。      A、EDCBA      B、DECBA       C、ABCDE 

6、60;   D、DCEAB13、一个高度为h的满二叉树共有x个结点，其中m个叶子结点，则有（ ）成立。       A、x=2m-1   B、h+m=2x     C、m=h-1   D、 x=h+m14、二叉排序树中，最大值结点的（ ）。A、左指针一定为空 B、右指针一定为空 C、左右指针均为空 D、左右指针均不为空15、含有n个顶点的连通图中的任意一条简单路径，其长度不可能超过（ ）。    

7、  A、1         B、n/2         C 、n-1           D、n16、堆的形状是一棵( )。A、二叉排序树   B、满二叉树   C 、完全二叉树  D、判定树17、在待排序序列基本有序或

8、个数较小的情况下，最佳的内部排序方法是( )。A、直接插入排序 B、起泡排序 C、简单选择排序 D、快速排序18、 判断一个有向图是否存在回路除了可以利用拓扑排序方法外，还可以用（ ）。A、求关键路径的方法 B、 深度优先遍历的方法C、广度优先遍历的方法 D、求最短路径的方法19.一个高度为h的满二叉树共有n个结点，其中有m个叶子结点，则有（ ）成立。A n=h+m B h+m=2n C m=h-1 D n=2m-120. 在一棵度为3的树中,度为3的结点个数为2,度为2 的结点个数为1,则度为0的结点个数为(    )  

9、  A4           B5            C6          D721.对于一个具有n个顶点的无向图，若采用邻接矩阵存储，则该矩阵的大小是（ ）。A n B (n-1)2 C n-1 D n222.下面关于工程计划的AOE网的叙述中，不正确

10、的是（ ） A 关键活动不按期完成就会影响整个工程的完成时间B 任何一个关键活动提前完成，那么整个工程将会提前完成C 所有的关键活动都提前完成，那么整个工程将会提前完成D 某些关键活动若提前完成，那么整个工程将会提前完23.在一个单链表中，若在p所指结点之后插入s结点，应执行（ ）。A s>next = p>next ；p>next = s； B s>next = p；p>next = s>next ； C q>next = s； s>next = p； D p>next = s；s>next = q；24. 采用折半搜索算法搜索长度

11、为n的有序表时，元素的平均搜索长度为（ ）A O（n2） B O（n log2n） C O（log2n） D O（n）25.判断一个有向图是否存在回路，除了可以利用拓扑排序方法外，还可以利用（ ）。A 求关键路径的方法 B 求最短路径的Dijkstra方法 C 深度优先遍历算法 D 广度优先遍历算法26. 若广义表A满足Head(A)=Tail(A)，则A为（ ）A ( ) B ( ) C ( ),( ) D( ),( ),( )27.已知一个有序表为(12，24，35，47，50，62，85，90)，当折半查找值为35的元素时，经过（ ）次比较后查找成功。A 1 B 2 C 3 D 428、

12、已知一个有向图的邻接表存储结构如下，从顶点V1出发进行广度优先搜索遍历，所得的顶点序列是_。 29、已知一个顺序存储的有序表为(12，24，35，47，50，62，85，90)，当折半查找值为62的元素时，经过 次比较后查找成功。(A) 1 (B) 2 (C) 3 (D) 430、在一个5阶B_树上，每个非终端结点所包含的关键字数目最少为 。(A) 1 (B) 2 (C) 3 (D) 431、一组记录的关键字为(46，79，56，38，40，24)，采用直接插入排序方法，将关键字38插入到有序表后的排序结果为 。(A) (24，38，40，46，56，79) (B) (46，56，38，40，

13、24，79)(C) (38，46，56，79，40，24) (D) (24，40，38，46，56，79)32、对n个记录按关键字进行起泡速排序，该算法的时间复杂度为_。(A) O(nlogn) (B) O(n2) (C) O(n3) (D) O(1)33、具有5个顶点的无向图至少应有_条边，才能确保该图是一个连通图。 (A)3 (B)4 (C)5 (D)6 34、链表不具备的特点是_（A）可随机访问任一结点 （B）插入删除不需要移动元素（C）不必事先估计存储空间 (D) 所需空间与其长度成正比35、在一个单链表中，若在p所指结点之后插入s结点，应执行_。(A) s>next = p&g

14、t;next ；p>next = s；(B) s>next = p；p>next = s>next ； (C) q>next = s； s>next = p；(D) p>next = s； s>next = q；36、一个栈的进栈序列是A,B,C,D,E，则栈的不可能的输出序列是 。(A) DECBA (B) EDCBA (C) ABCDE (D) DCEAB37、循环队列用数组am存放其元素值(m为大于0的正整数)，已知其头尾指针分别是front和rear，则队满的判断条件是 。(A) rear=front (B) rear！=front(C)

15、 rear+1=front (D) (rear+1)%m=front 38、广义表（a）的表头是_。(A) a (B) （a） (C) （） (D) (（a）) 39、对一个满二叉树，m个树叶，n个结点，深度为h，则：(A)n=h+m (B)h+m=2n (C)m=h-1 (D)n=2h-1 40、在具有n个结点的有序单链表中插入一个新结点并仍然有序的算法时间复杂度为 。(A) O(1) (B) O(n) (C) O(n2) (D) O(log2n)41、在一个单链表中，若在p所指结点之后插入s结点，应执行_。(A) s>next = p>next ；p>next = s；

16、(B) s>next = p；p>next = s>next ； (C) q>next = s； s>next = p； (D) p>next = s； s>next = q；42、设栈S和队列Q的初始状态为空，元素a、b、c、d、e、f依次通过栈S，一个元素出栈后即进入队列Q，若这6个元素出队的顺序是b、d、c、f、e、a，则栈S的容量至少应该是 。(A) 3 (B) 4 (C) 5 (D) 643、循环队列用数组am存放其元素值(m为大于0的正整数)，已知其头尾指针分别是front和rear，则队空的判断条件是 。(A) rear=front (B

17、) rear！=front(C) rear+1=front (D) (rear+1)%m=front 44、下列排序算法中，其时间复杂度和记录的初始排列无关的是（） A、插入排序B、快速排序 C、堆排序 D、冒泡排序45、一棵左右子树均不空的二叉树在后序线索化后，其空指针域数为( )。 A、0 B、1 C、2 D、不确定46、设有向图G=(V,E)和G=(V,E)，如G是G的生成树，则下面不正确的说法是（ ）。A、 G为G的连通分量 B、 G为G的无环子图C、 G为G的子图 D、 G为G的极小连通子图且V=V47、下面的说法中，不正确的是（）A、 对称矩阵只须存放包括主对角线元素在内的下（或上

18、）三角的元素即可。B、 对角矩阵只须存放非零元素即可。C、 稀疏矩阵中值为零的元素较多，因此可以采用三元组表方法存储。D、 稀疏矩阵中大量值为零的元素分布有规律，因此可以采用三元组表方法存储48、树若用双亲链表表示，则( ) 。A、可容易地实现求双亲及子孙的运算B、求双亲及子孙的运算均较困难 C、容易地实现求双亲运算，但求子孙运算较困难D、可容易地实现求子孙运算，但求双亲运算较困难49、下面程序段的时间复杂度是( ) 。for(i=0;i<n;i+) for(j=1;j<m;j+) Aij=0； A、O(n) B、O(m+n+1) C、O(m+n) D、O(m*n)50、采用折半搜

19、索算法搜索长度为n的有序表时，元素的平均搜索长度为（ ）A、O（n2） B、O（n log2n） C、O（log2n） D、O（n）51、判断一个有向图是否存在回路，除了可以利用拓扑排序方法外，还可以利用（ ）。A、求关键路径的方法 B、求最短路径的Dijkstra方法 C、深度优先遍历算法 D、广度优先遍历算法52假设有如下遗产继承规则：丈夫和妻子可以相互继承遗产；子女可以继承父亲或母亲的遗产；子女间不能相互继承。则表示该遗产继承关系的最合适的数据结构应该是（ ）。A 树 B 图 C 线性表 D 集合53.使用双链表存储线性表，其优点是可以（ ）。A 提高查找速度 B 更方便数据的插入和删除

20、C 节约存储空间 D 很快回收存储空间54.设栈S和队列Q的初始状态为空，元素e1、e2、e3、e4、e5、e6依次通过栈S，一个元素出栈后即进入队列Q，若6个元素出队的顺序是e2、e4、e3、e6、e5、e1，则栈S的容量至少应该是（ ）。A 6 B 4 C 3 D 255.下面的说法中，不正确的是（）A 对称矩阵只须存放包括主对角线元素在内的下（或上）三角的元素即可。B 对角矩阵只须存放非零元素即可。C 稀疏矩阵中值为零的元素较多，因此可以采用三元组表方法存储。D 稀疏矩阵中大量值为零的元素分布有规律，因此可以采用三元组表方法存储56.在一个单链表中，若在p所指结点之后插入s结点，应执行（

21、 ）。A s>next = p>next ；p>next = s； B s>next = p；p>next = s>next ； C q>next = s； s>next = p； D p>next = s；s>next = q；57.设栈S和队列Q的初始状态为空，元素a、b、c、d、e、f依次通过栈S，一个元素出栈后即进入队列Q，若这6个元素出队的顺序是b、d、c、f、e、a，则栈S的容量至少应该是（ ）。A 3 B 4 C 5 D 6二、填空1、给定序列100， 86， 48， 73， 35， 39， 42， 57， 66， 21

22、，按堆结构的定义，则它一定是【5】堆。设有一个顺序栈S，元素S1 ，S2, S3 , S4 , S5, S6依次进栈，如果6个元素的出栈顺序为S2, , S3 , S4, S6 , S5, S1 ，则顺序栈的容量至少应为（ ）。广义表A(（ a,b,c ），（ d,e,f）)的表尾为（ ） 。稀疏矩阵一般压缩存储方法有两种，分别是【6】和【7】。在一个具有n个顶点的有向图中，若所有顶点的出度之和为s，则所有顶点的入度之和为【8】。已知无向图G的顶点数为n，边数为e，其邻接表表示的空间复杂度为【9】。设单链表中指针p指向结点A，若要删除A的后继结点（假设A存在后继结点），则需修改指针的操作为【1

23、0】。某二叉树的中序遍历序列是CBDAFGE,前序遍历序列为ABCDEFG,则后序遍历序列为（ ）。树的后序遍历结果和二叉树的（ ）序遍历结果相同。在一个有向图中，所有顶点的出度之和等于所有边数的（ ）倍。对于n个顶点，e条边的连通图，利用Prim算法求最小生成树的时间复杂度为（ ）。长度为10的有序表采用折半查找，共有（ ）个元素的查找长度为4。已知具有n个元素的一维数组采用顺序存储结构，每个元素占2个存储单元，第一个元素a1的地址为200，那么，第a5个元素的地址为【1】。 冒泡排序在最坏情况下其算法的时间复杂度【2】。如果一个有向图不存在【3】，则该图的全部顶点可以排列成一个拓扑序列。

24、在一棵三叉树中，度为3的结点数为2个，度为2的结点数有1个，度为1的结点数为2个，那么度为0的结点数有【4】个。 对于一个具有n个顶点和e条边的连通图，其生成树中的顶点数和边数分别为【10】和【11】。 一组记录（50，40，95，20，15，70，60，45，80）进行直接插入排序时，当把第5个记录15插入到有序表时，为寻找插入位置需比较【12】次。 假设为循环队列分配的向量空间为Q20，若队列的长度和队头指针值分别为13和17，则当前尾指针的值为【13】。广义表 ( a , b ), c , d, ( e , ( f , g ) 的表头是【14】，表尾是【15】。已知一棵度为3的树有2个度

25、为1的结点，3个度为2的结点，4个度为3的结点。则该树种有 个叶子结点。有向图G用邻接矩阵Ann存储，其第i行的所有元素之和等于顶点i的 。一个图的_存储方式是唯一的，而_存储方式不是唯一的。_可作为实现递归函数调用的一种数据结构。若待散列的序列为(18,25,63,50,42,32,9)，散列函数为H(key)=key MOD 9，与18发生冲突的元素有【8】个。插入排序法、选择排序法、拓扑排序法与归并排序法中，【9】不是内排序方法。如果从无向图的任一顶点出发进行一次深度优先搜索即可访问所有顶点，则该图一定是【10】。广义表 ( a , b ), c , d, ( e , ( f , g )

26、 的表头是【11】，表尾是【12】，表的长度为【13】，表的深度为【14】 。假设以 S 和 X 分别表示进栈和出栈操作，则对输入序列 a , b , c , d , e 进行一系列操作 SSXSXSSXXX 之后，得到的输出序列为【15】。冒泡排序在最坏情况下其算法的时间复杂度【2】。如果一个有向图不存在【3】，则该图的全部顶点可以排列成一个拓扑序列。 已知广义表LS=(a，(b，c，d)，e)，用Head和Tail函数取出LS中原子b的运算是【4】。 【5】可作为实现递归函数调用的一种数据结构。 稀疏矩阵一般压缩存储方法有两种，分别是【6】和【7】。在一个具有n个顶点的有向图中，若所有顶点

27、的出度之和为s，则所有顶点的入度之和为【8】。三、 判断题1. 算法的运行时间涉及加、减、乘、除、转移、存、取等基本运算。要想准确地计算总运算时间是不可行的。（ ）2. 线性表采用顺序存储表示时，必须占用一片连续的存储单元。（ ）3在只有度为0和度为k的结点的k叉树中，设度为0的结点有n0个，度为k的结点有nk 个，则有 n0 = nk + 1。（ ）4 在霍夫曼编码中，当两个字符出现的频率相同时，其编码也相同，对于这种情况应当特殊处理。（ ）5、数据元素是数据的最小单位（ ）。6、满二叉树就是完全二叉树。（ ）7、已知一棵二叉树的前序序列和中序序列可以唯一地构造出该二叉树。（ ）8、单链表是

28、随机存取结构。（ ）9、任一棵二叉搜索树的平均搜索时间都小于用顺序搜索法搜索同样结点的顺序表的平均搜索时间。（ ）10、在AOE网络中，任何一个关键活动提前完成，整个工程将会提前完成。.（ ）11、一个有向图的邻接表和逆邻接表中结点个数一定相等。.( )12、对任意一个图，从某顶点出发进行一次深度优先和广度优先遍历，可访问图的所有顶点。 .（ ）13、二叉排序树的充要条件是任一结点的值均大于其左孩子的值，小于其右孩子的值。. .( )14、当装填因子小于1时，向散列表中存储元素时不会引起冲突。 （ ）15、二叉排序树的充要条件是任一结点的值均大于其左孩子的值，小于右孩子的值。（ ）16、用邻接

29、矩阵存储一个图时，在不考虑压缩存储的情况下，所占用的存储空间大小只与图中顶点个数有关，而与图的边数无关（ ）。17、任何一个关键活动延迟，那么整个工程将会延迟。（ ）18、一个有向图的邻接表和逆邻接表中的结点个数一定相等。（ ）19、AOE网是一种带权的无环连通图。（ ）20、完全二叉树就是满二叉树。（ ）21、已知一棵二叉树的前序序列和中序序列可以唯一地构造出该二叉树。（ ）22、带权连通图的最小生成树的权值之和一定小于它的其它生成树的权值之和。（ ）23、在散列法中采取开散列法来解决冲突时，其装载因子的取值一定在（，）之间。（ ）24、设目标串T=“abccdcdccbaa”,模式P=“c

30、dcc”则第6次匹配成功( )。25、关键活动不按期完成就会影响整个工程的完成时间。（ ）26、数据的逻辑结构是指各数据元素之间的逻辑关系，是用户按使用需要建立的( ).27、非空线性表中任意一个数据元素都有且仅有一个直接前驱元素。（ ）28、深度为h的非空二叉树的第h层最多有2h-1个结点。（ ）29、用邻接矩阵存储一个图时，在不考虑压缩存储的情况下，所占用的存储空间大小只与图中顶点个数有关，而与图的边数无关（ ）。30、任何一个关键活动延迟，那么整个工程将会延迟。（ ）31、任何一个关键活动提前完成，那么整个工程将会提前完成。（ ）32、AOE网是一种带权的无环连通图。（ ）33、数据元素

31、是数据的最小单位。（ ）34、完全二叉树就是满二叉树。（ ）四、按要求完成下列各题1根据下图所示的有向图，写出一个拓扑序列。132547685153101227962、下图所示为一个无向带权图，请利用Kruskal算法求最小的生成树，要求从顶点1出发。 3、输入关键字序列19，24，37，90，50,给出构造一棵AVL树的步骤。4、一组记录的关键字为46，79，56，38，40，84，利用快速排序的方法，以第一个记录的关键字为基准元素，写出一趟排序的过程和结果。5已知一个如下连通图，试给出图的邻接矩阵和邻接表存储示意图，若从顶点v1出发对该图进行遍历，分别给出一个按深度优先遍历和广度优先遍历的

32、顶点序列。（7分）6设有稀疏矩阵A，如图所示，请将稀疏矩阵A表示成三元组表。（6分）7对下图所示的带权图，用普里姆算法画出该图的最小生成树的过程。（6分）8、已知二叉树的先序遍历序列是stuwv，中序遍历序列是uwtvs，请由中序和先序序列求解二叉树的树形，并写出后序遍历该二叉树所得到的结点序列。9、输入关键字序列19，24，37，90，50,给出构造一棵平衡二叉树的步骤。10、一组记录的排序码为（46，79，56，38，40，84），利用堆排序（建立大根堆）的方法建立初始堆，写出建立初始堆的过程和结果。11、已知一个有向图的邻接表存储结构如下，从顶点v1出发进行深度和广度优先搜索遍历，写出所

33、得的顶点序列。v1v3v5 v6 v2 v5 v4 v4 v6 v3 v2v3v4v5v612将下面的森林变换成二叉树（7分）。ACDBFEKJGHI13用普里姆算法画出该图给定的图简化为最小的生成树，要求从顶点a出发。14、已知有五个待排序的记录，其关键字分别为：25，30，75，12，93,86，74，69，07，43请用快速排序的方法将它们从小到大排列（注意：只写出每趟排序结果，不用写每趟排序过程）。15、利用Prim算法从下图的顶点1出发，构造最小生成树,按并入最小生成树中边的顺序，画出最小生成树，并写出最小生成树的各条边，求最小生成树的权。613245665155246 316、对如

34、下AOE网G3， 计算每个事件的最早发生时间Ve、最迟发生时间Vl、各项活动的最早开始时间Ee及最迟开始时间El。事件VeVlV1V2V3V4(1) 填充右边的两个表格。(2) 求解关键活动和关键路径。(3) 求解完成整项工程的最短工期。(4)G3： 活动EeEla1a2a3a4a5 17、输入关键字序列19，24，37，90，50,给出构造一棵AVL树的步骤。18、一组记录的关键字为38,27,55,50,13,49,65，利用快速排序的方法，写出一趟排序的过程和结果。19、将如下所示树T转换成为二叉树，并画出该二叉树的先序线索二叉树。 T: 20、现有一段用于通讯的电文仅由A、B、C、D、

35、E、F 6种字符组成，其出现的频度分别为2、3、4、7、8、9，为每个字符设计哈夫曼编码。 画出构造的 Huffman 树 (按左子树根结点的权值小于等于右子树根结点的权值的次序构造)。 写出每个字符的Huffman编码。 求该段电文的总长度。21、 对关键字序列 (19,14,23,1,68,20,84,27,55,11,10,79)，设哈希函数为H(key)=key %13，用链地址法解决冲突。请画出构造的哈希表，并求出等概率情况下查找成功时的平均查找长度ASL。22、利用Kruskal 算法，构造图G1的最小生成树，按并入最小生成树中边的顺序，写出最小生成树的各条边，求最小生成树的权。G

36、1: 12 5 158 20 6 10 8 4 9 23、利用Dijkstra 算法，在图G2中，求从源点1到其余各顶点的最短路径及最短路径长度。 G2: 3 26 15 6 5 7 10 4 8 24已知有五个待排序的记录，其关键字分别为：256，301，751，129，937,863，742，694，076，438请用快速排序的方法将它们从小到大排列。25、设输入元素为1,2,3,P,A，输入次序为123PA，元素经过栈到达输出序列，当所有元素均到达输出序列后，写出5种可作为高级语言变量名的输出序列。 123PA 输出次序 输入次序 栈26、一组记录的关键字为46，79，56，38，40，

37、84，利用快速排序的方法，以第一个记录的关键字为基准元素，写出一趟排序的过程和结果。27、对长度为10的顺序存储的有序表进行折半查找，画出其二叉判定树，并求其等概率情况下查找成功时的平均查找长度。28已知一棵二叉树如下，请分别写出按前序、中序、后序遍历时得到的结点序列。ABCDFHEG29. 某二叉树的结点采用顺序存储表示如下：0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19EAFDHCGIB试画出此二叉树的图形表示。写出结点D的双亲结点及左、右子女。将此二叉树看作森林的二叉树表示，试将它还原为森林。30设待排序序列为10，18，4，3，6，1

38、2，1，9，15，8，请给出用希尔排序每一趟的结果。增加量序增量d分别取为5，3，2，1。31请对下面的无向带权图，写出它的邻接表，按克鲁斯卡尔算法求其最小生成树（逐步画出）。32试利用Dijkstra算法求下图中从顶点a到其他各顶点间的最短路径，写出执行算法中各步的状态。五、算法设计题1、设计一个算法，将值为x的新结点插入到单链表的第i个位置。 2、设计一个算法，按前序次序打印二叉树中的叶子结点并求出叶结点个数3、设计算法求二叉树的深度。 4、设计算法，向有序单链表中插入元素，插入后结点仍按元素值有序。5、设计算法求单链表的长度（注意：非循环链表）。（本题共10分）6、按后序序列打印二叉树的非叶子结点。（本题共10分）7、设计算法输