做在答题纸上,在试题纸上做解答按零分处理。数据结构的

《做在答题纸上,在试题纸上做解答按零分处理。数据结构的》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、做在答题纸上,在试题纸上做解答按零分处理。数据结构的保持青春的秘诀，是有一颗不安分的心。　　请将所有答案做在答题纸上，在试题纸上做解答按零分处理。数据结构的算法试题可使用C或C++语言的风格描述。　一．单项选择题(本大题共10小题，每小题2分，共20分)将答案选项与题目编号写在答题纸上，错选或未选均无分。1.将长度为n的单链表接在长度为m的单链表之后的算法时间复杂度为()。A.O(n)B.O(1)C.O(m)D.O(m+n)2.设数组data[m]作为循环队列SQ的存储空间，front为队头指针，rear为队尾指针，则执行出队操作后其

2、头指针front的值为()。A.front=front+1B.front=(front+1)%(m-1)C.front=(front-1)%mD.front=(front+1)%m3.一个非空广义表的表头()。A.不可能是子表B.只能是子表C.只能是原子D.可以是原子或子表4.堆排序在最坏的情况下的时间复杂度是()。　　A.O(log2n)B.O(log2n2)　　C.O(nlog2n)D.O(n2)5.设G1=(V1,E1)和G2=(V2,E2)为两个图，如果V1?V2，E1?E2，则称()A.G1是G2的子图B.G2是G1的子图C

3、.G1是G2的连通分量D.G2是G1的连通分量6.在一棵度为3的树中，度为3的结点个数为2，度为2的结点个数为1，则度为0的结点个数为()。A.4B.5C.6D.77.设一个有n个顶点和e条弧的有向图用邻接表表示，则删除与某顶点vi相关的所有弧的时间复杂度是A.O(n)B.O(e)C.O(n+e)D.O(n*e)8.算法指的是A.计算机程序B.解决问题的计算方法C.排序算法D.解决问题的有限运算序列9.若派生类的成员函数不能直接访问基类中继承来的某个成员，则该成员一定是基类中的A.私有成员　　B.公有成员C.保护成员D.保护成员或私有

4、成员10.在C++程序中，对象之间的相互通信通过A.继承实现　　B.调用成员函数实现C.封装实现D.函数重载实现二．填空题(本大题共16小题，除第26小题5分外，其余每小题2分，共35分)不写解答过程，将正确答案与题目编号写在答题纸上。11.仅允许在同一端进行插入删除的线性表称为。12.在一个长度为n的顺序表中第i个元素(1?i?n)之前插入元素时，需向后移动元素个数是。13.在串S="structure"中，以t为首字符的子串有个。14.在拓扑排序中，拓扑序列的第一个顶点必定是的顶点。15.数据的逻辑结构是从逻辑关系上描述数据，它与

5、数据的　　无关，是独立于计算机的。16.在含n个顶点和e条边的无向图的邻接矩阵中，零元素的个数为　　。17.设用S和X分别表示进栈和出栈操作，则对输入序列a,b,c,d和e进行一系列栈操作SSXSXSSXXX之后，得到的输出序列为　　。18.对表长为n的顺序表进行分块查找，若以顺序查找确定块，且每块的长度为s，则在等概率查找的情况下，查找成功时的平均查找长度为　　。19.已知一棵完全二叉树中共有768个结点，则该树中共有　　个叶子结点。20.设一个9阶的上三角矩阵A按列优先顺序压缩存储在一维数组B中，其中B[0]存储矩阵中第一个元素a

6、1,1,则B[31]中存放的元素是　　。(注：矩阵元素下标从1起计)21.C++支持的两种多态性分别是多态性和多态性。22.定义类的动态对象数组时，系统只能够自动调用该类的构造函数对其进行初始化。23.初始化类模板时，相对于它的每个参数要提供。24.面向对象程序设计的机制提供了重复利用程序资源的一种途径。25.删除一个动态对象时，将自动调用该对象所属类的函数。26.在下面的程序横线处补填上适当的内容（写到答题纸上），以使该程序有如下的结果输出：CreatingBendofBendofA具体的程序如下：#include

7、.h>classA｛public：　　　A(){}　　　(1)｛cout<<＂endofA＂<

8、　　　　　28.由五个分别带权值为9，2，5，7，14的叶子结点构成哈夫曼树，写出该树的带权路径长度并示明计算的步骤。29.设a1,a2,a3是不同的关键字且a1>a2>a3，可组成6种不同的输入顺序。画出其中哪几种输入