资源描述：
《数据结构期末试题及答案》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、.E卷一、单项选择题1、线性表若采用链式结构时，要求内存中可用存储单元的地址()。A.必须是连续的B.部分地址必须是连续的C.一定是不连续的D.连续不连续都可以2、判定一个栈ST(最多元素为m0)为空的条件是()。A.ST->top!=0B.ST->top==0C.ST->top!=m0D.ST->top==m03、数组A中，每个元素A的长度为3个字节，行下标i从1到8，列j下标从1到10，从首地址SA开始连续存放在存储器内，该数组按行存放时，元素A[8][5]的起始地址为()。A.SA+141
2、B.SA+144C.SA+222D.SA+2254、设哈希表长m=14，哈希函数H(key)=key%11。表中已有4个结点：addr(15)=4addr(38)=5addr(61)=6addr(84)=7其余地址为空如用二次探测再散列处理冲突，关键字为49的结点的地址是()。A.8B.3C.5D.95、在线索化二叉树中，t所指结点没有左子树的充要条件是()。A.t->left==NULLB.t->ltag==1C.t->ltag==1且t->left==NULLD.以上都不对word资料.6、
3、将递归算法转换成对应的非递归算法时，通常需要使用()。A.栈B.队列C.链表D.树7、有一个有序表为{1,3,9,12,32,41,45,62,75,77,82,95,100},当二分查找值为82的结点时，()次比较后查找成功。A.1B.2C.4D.88、对一个满二叉树，m个树叶，n个结点，深度为h，则()。A.n=h+mB.h+m=2nC.m=h-1D.n=2h-19、如果要求一个线性表既能较快地查找，又能适应动态变化的要求，可以采用_____查找方法。A.分块B.顺序C.二分D.散列10、快
4、速排序方法在()情况下最不利于发挥其长处。A.要排序的数据量太大B.要排序的数据中含有多个相同值C.要排序的数据已基本有序D.要排序的数据个数为奇数11、在含有n个顶点和e条边的无向图的邻接矩阵中，零元素的个数为________.A.eB.2eC.-eD.-2e12.假设一个有n个顶点和e条弧的有向图用邻接表表示，则删除与某个顶点相关的所有弧的时间复杂度是_________.A.O(n)B.O(e)C.O(n+e)D.O(n*e)word资料.13.用某种排序方法对关键字序列（25，84，21，
5、47，15，27，68，35，20）进行排序时，序列的变化情况：20，15，21，25，47，27，68，35，8415，20，21，25，35，27，47，68，8415，20，21，25，27，35，47，68，84则所采用的排序方法是_________.A.选择排序B.希尔排序C.归并排序D.快速排序14.适宜于对动态查找表进行高效率查找的组织结构是_____.A.有序表B.分块有序表C.三叉排序表D.线性链表15.不定长文件是指__________.A.文件的长度不固定B.记录的长度不固
6、定C.字段的长度不固定D.关键字项的长度不固定二、填空题16、对数据间关系的描述是数据的逻辑结构，形式地可以用一个二元组B=（D，R）来表示，其中D表示________；R表示___________。17、数据结构的存储一有两种，分为_______和________.18、评价一个数据结构，基本来说有两条，一条是_______，二是_______。19、栈的类型说明为：typedefstrucstack{datatypes(maxlen);intlen;}stack;word资料.则：POP（s
7、tackst）;算法是：ifst.len=0printf(“underflow”)else__________;20、二叉树的第i层上至多有______结点，深度为k的二叉树至多有________结点。21、图的遍历主要有________和_________两种.22、在hq的链队中，判定只有一个结点的条件是____________。23、在散列函数H(key)=key%p中，p应取_________。24、对于长度为n的线性表，若采用二分法查找，则时间复杂度为_____；若采用分块查找(假定总
8、块数和每块长度均接近n的平方根)，则时间复杂度为_________。三、解答操作题（每小题5分，共20分）25、已知一个无向图的顶点集为{a,b,c,d,e},其邻接矩阵如下所示：（1）画出该图的图形。（2）根据邻接矩阵从顶点a出发进行深度优先遍历和广度优先遍历，并写出遍历序列。26、把下列二叉树换成二森林，画出图形word资料.27、已知一个散列表如下表示：35203348590123456789101112其散列函数h(key)=key%13,处理冲突的方法为双重散列法，探查序列为：=(h(
