华东交通大学2004—2005学年第2学期考试卷—承诺:我将严格遵守考场纪律,并知道考试违纪,作弊的严重后果,承担由此引起的一切后果.专业班级学号学生签名:数据结构题号分数评卷人一,选择题(15分)1.假设某算法语句总的执行次数为T(n)=6n4+n,那么该算法的时间复杂性.量级为().A)O(2)B)O(n5)C)O(n4)D)O(1)2.一个向量的第一个元素的存储地址是100,每个元素的长度为2,则第5.个元素的地址是()A,110B,108C)100D)1203.以下关于线性表的说法不正确的是()..A,线性表中的数据元素可以是数字,字符,记录等不同类型.B,线性表中包含的数据元素个数不是任意的.C,线性表中的每个结点都有且只有一个直接前趋和直接后继.D,存在这样的线性表:表中各结点都没有直接前趋和直接后继.4.一个栈的入栈序列是abcde,则栈的不可能的输出序列是()..A,EdcbaB,decbaC,abcdeD,dceab5.一个队列的入列序列是1,2,3,4,则队列的输出序列是()..A,4,3,2,1B,1,2,3,4C,1,4,3,2D,3,2,4,16.向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变,.平均要移动()个元素.A,64B,63C,63.5D,77.线性表采用链式存储结构时,其地址()..A,必须是连续的B,部分地址必须是连续的C,一定是不连续的D,连续与否均可以8.对数组常用的两种基本操作是:().A,建立与删除B,索引和修改C,查找和修改D,查找和索引9.按照二叉树的定义,具有三个节点的二叉树有()种..A,3B,4C,5D,610.在一个图中,所有顶点的度数之和等于所有边数的()倍..A,1/2B,1C,2D,4课程三四课程类别:必五六七八闭卷,开卷(范围):九总分一二11.带头结点的单链表head为空的判定条件是..A,head=NULLB,headnext==headC,headnext==NULLD,head!=NULL12.对一个满二叉树,m个树叶,n个结点,深度为h,则().A,n=h+mB,h+m=2nC,m=h-1D,n=2h-113.具有4个顶点的无向完全图有()条边..A,6B,12C,16D,2014..二,判断题(判断下列各题是否正确,若正确在括号里打"√"错误的打,"×",1.2.3.4.5.6.7.8.9.10.每小题1分,共10分)如果两个串含有相同的字符,则这两个串相等.()数组可以看成线性表结构的一种推广,因此可以对它进行插入,删除等运算.()单链表表示的有序表也可以使用折半查找来提高查找速度.()在栈满的情况下不能作进栈运算,否则产生"上溢".()二路归并排序的核心操作是将两个有序序列归并为一个有序序列.()对任意一个图,从它的某个顶点出发,进行一次深度优先搜索或广度优先搜索,即可访问图的每个顶点.()一个有向图的邻接表和逆邻接表中表结点的个数一定相等.()一个图的邻接矩阵表示法是唯一的,而邻接表表示法是不唯一的.()数据的逻辑结构与数据元素本身的内容和形式无关.()二叉树是深度为2的有序树.()三,填空题(20分)1.根据数据元素之间关系的不同特性,通常有下列4类基本结.构:(1),(2),(3),2.有一棵树如图所示,回答下面的问题:.(4)K1K2K3K4K5K6K7(1)这棵树的根结点是(5);(2)这棵树的叶子结点是(3)结点K3的度是(4)这棵树的度是(5)这棵树的深度是(6)结点K3的子女是(7)结点K3的父结点是(6)(7)(8)(9)(10)(11)3.在一个无向图中,所有顶点的度数之和等于所有边的数目的.(12)倍.4.在二叉树链表上实现中序遍历的递归算法:.voidpostorder(BiTreer){if(r!=NULL){midorder(rlchild);visit(r);(13);}}5.深度优先搜索遍历类似于树的.构是(15).广度优先搜索遍历类似于树的据结构是(17).(14)(16)遍历,它所用到的数据结遍历,它所用到的数6.在顺序表中,虽然仍有空闲,但不能进行入队操作,这被称为是__._(18)_________.7..四,简答题(15分)1.简述算法的重要特征.2.简述空串和空格符有何区别?.3.稀疏矩阵压缩存储采用的三元组顺序表是线性表吗?为什么?.4..五,设计题1,写出下图二叉树的先序遍历,中序遍历和后序遍历序列(6)abcdgef2,给出如图所示的无向图G的邻接矩阵和邻接表两种存储