数据结构复习题1

《数据结构复习题1》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

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

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

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

4、（）。AnB(n-1)2Cn-1Dn210.G是一个非连通无向图，共有28条边，则该图至少有（）个顶点。A6B7C8D911、在一个单链表中，如果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;         D、m —>next=k;k—>next=n;12、 一个栈的入栈序列是A,

5、B,C,D,E,则栈的出栈序列不可能是（     ）。     A、EDCBA      B、DECBA       C、ABCDE     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个顶点的连通图中的任意一条简单路径，其长度不可能超过（）。     A

6、、1         B、n/2         C 、n-1           D、n16、堆的形状是一棵()。A、二叉排序树  B、满二叉树  C 、完全二叉树 D、判定树17、在待排序序列基本有序或个数较小的情况下，最佳的内部排序方法是()。A、直接插入排序B、起泡排序C、简单选择排序D、快速排序18、 判断一个有向图是否存在回路除了可以利用拓扑排序方法外，还可以用（）。A、求关键路径的方法B、深度优先遍历的方法C、广度优先遍历的方法D、求最短路径的方法19.一个高度为h的满二叉树共有n个结点，其中

7、有m个叶子结点，则有（　）成立。An=h+mBh+m=2nCm=h-1Dn=2m-120.在一棵度为3的树中,度为3的结点个数为2,度为2的结点个数为1,则度为0的结点个数为(    )    A．4          B．5            C．6          D．721.对于一个具有n个顶点的无向图，若采用邻接矩阵存储，则该矩阵的大小是（）。AnB(n-1)2Cn-1Dn222.下面关于工程计划的AOE网的叙述中，不正确的是（）A关键活动不按期完成就会影响整个工程的完成时间B任何一个关键活动

8、提前完成，那么整个工程将会提前完成C所有的关键活动都提前完成，那么整个工程将会提前完成D某些关键活动若提前完成，那么整个工程将会提前完23.在一个单链表中，若在p所指结点之后插入s结点，应执行（）。As－>next=p－>next；p－>next=s；Bs－>next=p；p－>next=s－>next；Cq－>next=s；s－>next=p；Dp－>next=s；s－>next=q；24.采用折半搜索算法搜索