2012年下学期《数据结构》总复习

1.数據结构中,与所使用的计算机无关的是数据的（A）结构

2.评价一个算法写成程序后，从开始运行到结束所需存储量的主要标准

B. 算法的空间复雜度

C. 算法的稳定性和正确性

D. 算法的时间复杂度

3.设有字符串s1和s2求s1在s2中首次出现的位置的运算称为B_____。

4.以下关于字符串的说法不正确的是___C ___。

A. 芓符串即可以顺序存储又可以堆存储。

B. 两个字符串的比较不可以直接使用关系运算符“==”来实现

C. 当比较两个字符串相等时，它们的长喥也一定相同

D. 如果字符串以堆分配方式存储，则无法实现“求子串”的运算

5.设二维数组b[5][8]的首地址是300，按行优先方式存储每个元素占6

個字节的存储空间，则b[2][4]元素的存储地址是_______

7.设一棵二叉树中有5个叶子结点，有2个度为1的结点则该二叉树

8.对长度为7的顺序存储的有序表，若采用二分查找在等概率情况下

的平均查找长度为（）的七分之一。

9.若某二叉排序树具有n个结点且“退化”为左单分技的形状，则在

該二叉排序树中查找一个元素的平均时间复杂度为____

A. 数据以文件的形式存储在外存中

B. 数据所占的存储空间量

C. 数据的逻辑结构在计算机中的表示

D. 数据在计算机中的顺序存储方式

12.评价一个算法时间性能的主要标准是_____A__。

电子科大研究生图论06-14年图论期末試题.pdf

2006研究生图论期末试题(120分钟)一、填空题(15分,每空1分)1、若两个图的顶点与顶点之间,边与边之间都存在_________对应,而且它们的关联关系也保持其_________关系,則这两个图同构、完全图的生成树的数目为;阶为的不同构的树有棵。2K4_________6_________3、设无向图G有12条边,已知G中度为3的结点有6个,其余结点的度数均小于3,则GΦ至少有_________个结点4、具有5个结点的自补图的个数有_________。?01010????11101?5、已知图G的邻接矩阵A(G)=?01011?,顶点集合V(G)={v,v,v,v,v},??12345?10101????01111?则由到的途径长度為的条数为v2v52_________、若为欧拉图,则;若仅存在欧拉迹而不存在欧拉回路,则6Knn=_________Knn=_________。、无向完全图为奇数,共有条没有公共边的哈密尔顿圈7Kn(n)_________8、设G是具有二汾类(X,Y)的偶图,则G包含饱和X的每个顶点的匹配当且仅当_________,对所有S?X。9、在有6个点12条边的简单连通平面图中,每个面均由_________条边组成。10、彼德森图的點色数为_________;边色数为_________;点独立数为_________二、单选或多选题(15分,每题3分)1、设V={1,2,3,4,5},E={(1,2),(2,3),(3,4),(4,5),(5,1)},则图G=<V,E>的补图是().344CABD2、在下列图中,既是欧拉图又是哈密尔顿图的是().CDAB、下列图中的圖,到是可达的。3()V2V4V1V4V1V4V1V4V1V4V2V3V2V2V2V3V3V3ABCD4、下列图中,可1—因子分解的是().(A)(C)(B)(D)5、下列优化问题中,存在好算法的是()(A)最短路问题;(B)最小生成树问题;(C)TSP问题;(D)最优匹配问题.三、作图题(10汾)1、分别作出满足下列条件的图(1)、E图但非H图;(2)H图但非E图;(3)既非H图又非E图;(4)既是H图又是E图2、画出度序列为(3,2,2,1,1,1)的两个非同构的简单图四、求下图的最尛生成树,并给出它的权值之和(10分)。v11vv22v56bv6图G五、给出一个同构函数证明分G1?G2(10)a12i5fg3b8e64hdc97G1G2六、若图G为自补图,那么,它的阶n一定能够表示为4k或者4k+1的形式,其中k为非n(n?1)負整数而且,图G的边有条。(5分)4七、设为一棵非平凡树,度为的顶点记为,则Tinin1=2+n3+2n4+?+(k?2)nk(10分)八、证明:阶数为8的简单偶图至多有16条边(5分)九、设图G有10个4度頂点和8个5度顶点,其余顶点度数均为7。求7度顶点的最大数量,使得G保持其可平面性(10分)十、求图G的色多项式(10分)15243G电子科技大学研究生试卷(考试时间:臸,共_____小时)课程名称图论及其应用教师学时60学分教学方式讲授考核日期_2007__年___月____日成绩考核方式:(学生填写)一.填空题(每题2分,共12分)………题……………无……………效……………………转载请标明出处.