《数据结构复习题.doc》由会员分享，可在线阅读，更多相关《数据结构复习题.doc（9页珍藏版）》请在金锄头文库上搜索。
1、一、选择题1. 设n是描述问题规模的非负整数，下面程序片段的时间复杂度是（ ）。 x=2; while(xn/2) x=2*x;A. O(logn) B. O(n) C. O(nlogn) D. O(n2)2.下面程序段的时间复杂度为（ ） for (int i=0;im;i+) for (int j=0;jnext=s; s-next=p-next; B s-next=p-next; p-next=s;Cp-next=s; p-next=s-next; D p-next=s-next; p-next=s;8.采用线性链表表示一个向量时，要求占用的存储空间地址（ ）A.必须是连续的 B.部分地
2、址必须是连续的 C.一定是不连续的 D.可连续可不连续9.在一个单链表中，若p所指结点不是最后结点，在p之后插入s所指结点，则执行( )。A. s-next=p; p-next=s; B. s-next=p-next; p-next=s;C. s-next=p-next; p=s; D. p-next=s; s-next=p;10.栈的顺序存储结构中，top为栈顶指针，栈空的条件是( )。A. S.top=0 B. S.top=maxSize C. S.top=-1 D. S.top=S.base11. 为解决计算机和打印机之间速度不匹配的问题，通常设置一个打印数据缓冲区，主机将要输出的数据依
3、次写入缓冲区，而打印机则依次从该缓冲区中取出数据。该缓冲区的逻辑结构应该是（ ）。A.栈 B.队列 C.树 D.图12. 一个栈的输入序列为123n，若输出序列的第一个元素是n，输出第i（1=i=n）个元素是（ ）。A. 不确定 B. n-i+1 C. i D. n-i13.有六个元素6，5，4，3，2，1 的顺序进栈，问下列哪一个不是合法的出栈序列？（ ）A. 543612 B. 453126 C. 346521 D. 23415614.假定一个顺序队列的队首和队尾指针分别为front和rear，存放该队列的数组长度为N，则判断队空的条件为（ ）Afront+1=rear Brear+1=f
4、ront Cfront=0 Dfront=rear15.当利用大小为的数组顺序存储一个栈时，假定用top=N表示栈空，则向这个栈插入一个元素后，应执行（ ）语句修改top指针Atop+ Btop- Ctop=0 Dtop16. 栈和队列的共同点是（ ）。A. 都是先进先出 B. 都是先进后出 C. 只允许在端点处插入和删除元素 D. 没有共同点17.在循环队列中用数组A0.m-1 存放队列元素，其队头和队尾指针分别为front和rear，则当前队列中的元素个数是（ ）。 A.( front - rear + 1) % m B.( rear - front + 1) % mC.( front -
5、 rear + m) % m D.( rear - front + m) % m18.当利用大小为n 的数组存储一个循环队列时，该队列的最大长度为（ ）。A. n-2 B. n-1 C. n D. n+119数组A中，每一个数组元素Aij占用3个存储字，行下标i从1到8，列下标j从1到10。所有数组元素相继存放于一个连续的存储空间中，则存放该数组至少需要的存储字数是（ ）。A.80 B.100 C.240 D.27020.由权值分别为11，8，6，2，5的叶子结点生成一棵哈夫曼树，它的带权路径长度为（ ）。18具有35个结点的完全二叉树的深度为( )。A. 5 B. 6 C. 7 D. 821
6、.若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（ ）。A.9 B.11 C.15 D.不确定22. 无向图G=(V,E),其中：V=a,b,c,d,e,f,E=(a,b),(a,e),(a,c),(b,e),(c,f),(f,d),(e,d)，由顶点a开始对该图进行深度优先遍历，得到的顶点序列正确的是（ ）。A.a,b,e,c,d,f B.a,c,f,e,b,d C.a,e,b,c,f,d D.a,e,d,f,c,b23.判断一个有向图是否存在回路，除了可以利用拓扑排序方法外，还可以利用（ ）。A. 求关键路径的方法 B. 求最短路径的Dijkstra方法 C.
7、深度优先遍历算法 D. 广度优先遍历算法24. 给定二叉树如图所示。设N代表二叉树的根，L代表根结点的左子树，R代表根结点的右子树。若遍历后的结点序列为3,7,5,6,1,2,4，则其遍历方式是（ ）。A. LRN B. NRL C. RLN D. RNL25.由权值分别为,的叶子结点生成一棵哈夫曼树，它的带权路径长度为（ ）A24 B55 C72 D5326有n个顶点的完全无向图中，则包含有（ ）条边An(n-1)Bn(n-1)/2Cn Dn27设i为n个结点的完全二叉树结点编号，i=1，2，3.n；若i（n-1）/2时，结点i的右孩子为（ ）A2i B2i+1 C2i-1 Di+128 下
8、列二叉排序树中，满足平衡二叉树定义的是（ ）。29要连通具有n个顶点的有向图，至少需要（ ）条边。An-l Bn Cn+l D2n30下列哪一种图的邻接矩阵是对称矩阵（ ）。A有向图 B无向图 CAOV网 DAOE网31.采用顺序搜索方法查找长度为n的顺序表时，搜索成功的平均搜索长度为（ ）。 A.n B.n/2 C.(n-1)/2 D.(n+1)/232.采用折半搜索算法搜索长度为n的有序表时，元素的平均搜索长度为（ ）。A. O（n2） B. O（n log2n） C. O（log2n） D. O（n）33.从未排序序列中依次取出一个元素与已排序序列中的元素依次进行比较，然后放在已排序序列
9、的合适位置，该排序方法称为（ ）排序法。A插入排序 B选择排序 C希尔排序 D二路归并排序34.为实现快速排序算法，待排序序列宜采用的存储方式是（ ）。A.顺序存储 B.散列存储 C.链式存储 D.索引存储35.为实现快速排序算法，待排序序列宜采用的存储方式是（ ）。A 顺序存储 B 散列存储 C 链式存储 D 索引存储36.适用于折半查找的表的存储方式及元素排列要求为（ ）。 A链接方式存储，元素无序 B链接方式存储，元素有序C顺序方式存储，元素无序 D顺序方式存储，元素有序一、选择题1. 设n是描述问题规模的非负整数，下面程序片段的时间复杂度是（a ）。 x=2; while(xnext=
10、p; p-next=s; B. s-next=p-next; p-next=s;C. s-next=p-next; p=s; D. p-next=s; s-next=p;4.栈的顺序存储结构中，top为栈顶指针，栈空的条件是( ad )。A. S.top=0 B. S.top=maxSize C. S.top=-1 D. S.top=S.base5.当利用大小为n 的数组存储一个循环队列时，该队列的最大长度为（b ）。A. n-2 B. n-1 C. n D. n+16.由权值分别为11，8，6，2，5的叶子结点生成一棵哈夫曼树，它的带权路径长度为（ b）。A. 24 B. 73 C. 48
11、D. 537.具有35个结点的完全二叉树的深度为(b )。A. 5 B. 6 C. 7 D. 88.采用折半搜索算法搜索长度为n的有序表时，元素的平均搜索长度为（c ）。A. O（n2） B. O（n log2n） C. O（log2n） D. O（n）9.判断一个有向图是否存在回路，除了可以利用拓扑排序方法外，还可以利用（ c ）。A. 求关键路径的方法 B. 求最短路径的Dijkstra方法 C. 深度优先遍历算法 D. 广度优先遍历算法10.从未排序序列中依次取出一个元素与已排序序列中的元素依次进行比较，然后放在已排序序列的合适位置，该排序方法称为（ a ）排序法。A插入排序 B选择排序 C希尔排序 D二路归并排序二、填空题（每空1分，共12分）1根据数据元素之间的关系不同，通常有以下四种结构，集合_、 线性结构、_树形结构_ 、图形结构。网状结构。2数据元素之间的关
