数据结构含答案

1、数据结构综合练习一、选择题1 .数据的存储结构包括顺序、链接、散列和()4种基本类型。A索引B数组C集合D向量2 .下面程序的时间复杂性的量级为()。inti=0,s1=0,s2=0;while(i+<n)if(i%2)s1+=i;elses2+=i;A.O(1)B.O(1bn)C.O(n)D.O(2n)3 .下面程序段的时间复杂度为()。for(inti=0;i<m;i+)for(intj=0;j<n;j+)aij=i*j;A.O(m2)B.O(n2)C.O(m+n)D.O(m*n)4 .在一个长度为n的顺序存储结构的线性表中，向第i个元素(1WiWn+1)位置插入一个元素

2、时，需要从后向前依次后移()个元素。A.n-iB.n-i+lC.n-i-lD.i5 .在一个长度为n的顺序存储结构的线性表中，删除第i个元素(1WiWn+1)时，需要从前向后依次后移()个元素。A.n-iB.n-i+lC.n-i-lD.i6 .在一个长度为n的线性表中，删除值为x的元素时需要比较元素和移动元素的总次数为()。A.(n+1)/2B.n/2C.nD.n+17 .在一个顺序表中的任何位置插入一个元素的时间复杂度为()。A.O(n)B.O(n/2)C.O(1)D.O(n2)8 .线性表的链式存储比顺序存储更有利于进行()操作。A.查找B.表尾插入和删除C按值插入和删除D.表头的插入和删

3、除9 .线性表的顺序存储比链式存储更有利于进行（）操作。A.查找B.表尾插入和删除C.按值插入和删除D.表头的插入和删除10 .在一个表头指针为ph的单链表中，若要向表头插入一个由指针p指向的结点，则应执行（）操作。A.ph=p;p->next=ph;B.p->next=ph;ph=p;C.p->next=ph;p=ph;D.p->next=ph->next;ph->next=p;11 .在一个表头指针为ph的单链表中，若要在指针q所指结点的后面插入一个由指针p所指向的结点，则执行（）操作。A. q->next=p->next;p->nex

4、t=q;B. p->next=q->next;q=p;C. q->next=p->next;p->next=q;D. p->next=q->next;q->next=p;12 .在一个单链表HL中，若要删除由指针q所指向结点的后继结点（若存在的话），则执行（）操作。A. p=q->next;p->next=q->next;B. p=q->next;q->next=p;C. p=q->next;q->next=p->next;D. q->next=q->next->next;q-&g

5、t;next=q;13 .栈的插入和删除操作在（）进行。A.栈顶B.栈底C.任意位置D.指定位置14 .若让元素1,2,3,4依次进栈，则出栈次序不可能出现（）的情况。A.3,2,1,4B.2,1,4,3C.4,3,2,1D.1,4,2,3.15 .假定一个顺序循环队列的队首和队尾指针分别用f和r表示，则判断队空的条件为（）。A.f+1=rB.r+1=fC.f=0D.f=r16 .假定一个顺序循环队列存储于数组aN,其队首和队尾指针分别用f和r表示，则判断队满的条件为（）。A.（r-1）%N=fB.（r+1）%N=fC.（f-1）%N=rD.（f+1）%N=r17 .二维数组A12,10采用行

6、优先存储，每个数据元素占用4个存储单元，该数组的首地址（A0,0的地址）为1200,则A6,5的地址为（）。A.1400B.1404C.1372D.146018 .在一棵具有n个结点的二叉树中，所有结点的空子树个数等于（）。A.nB.n-1C.n+1D.2n19 .有如图1所示的一棵二叉树，则该二叉树的中序遍历序列为（）。A.ABCDEFGB.CDBGFEAC.CBDAEGFD.ABECDFG20 .有如图1所示的一棵二叉树，则该二叉树的先序遍历序列为（）。A.ABCDEFGB.CDBGFEAC.CBDAEGFD.ABECDFG21 .有如图1所示的一棵二叉树，则该二叉树的后序便利序列为（）。

7、A.ABCDEFGB.CDBGFEAC.CBDAEGFD.ABECDFG22 .利用n个值生成的哈夫曼树中共有（）个结-、点。A.nB.n+1C.2nD.2n-1:，三23 .利用3,6,8,12这4个值作为叶子结尸（点的权，生成一棵哈夫曼树，该树的带一权路径长度为（）。A.55B.29C.58D.38图j-24 .在一个具有n个顶点的无向图中，若具有e条边，则所有顶点的度数为（）。A.nB.eC.n+eD.2e25 .在一个具有n个顶点和e条边的无向图的邻接矩阵中，表示边存在的元素（又称为有效元素）的个数为（）。A.nB.neC.eD.2e26 .若一个图的边集为（A,B）（A,C）（B,D

8、）（C,F）（D,E）（D,F）,则从顶点A开始对该图进行深度优先搜索，得到的顶点序列可能为()A.ABCFDEB.ACFDEBC.ABDCFED.ABDFEC27 .若一个图的边集为(A,B)(A,C)(B,D)(C,F)(D,E)(D,F),则从顶点A开始对该图进行广度优先搜索，得到的顶点序列可能为()。A.ABCDEFB.ABCFDEC.ABDCEFD.ACBFDE28 .对于顺序存储的有序表(5,12,20,26,37,42,46,50,64),若采用二分查找，则查找元素26的查找长度为()。A.2B.3C.4D.529 .若根据查找表(23,44,36,48,52,73,64,58)

9、建立线性哈希表，采用H(K)=K%13计算哈希地址，则元素64的哈希地址为()。A.4B.8C.12D.1330 .若根据查找表(23,44,36,48,52,73,64,58)建立线形哈希表，采用H(K)=K%13计算哈希地址，则哈希地址为3的元素个数为()。A.1B.2C.3D.4答案为031 .若一个元素序列基本有序，则选用()方法较快。A.直接插入排序B.简单选择排序C.堆排序D.快速排序二、填空题1 .数据的逻辑结构可分为和两大类。线性；非线性2 .数据的存储结构被分为，,和4种。顺序；链式；索引；散列存储结构3 .一种数据结构的元素集合K和它的二元关系R为：K=a,b,c,d,e,

10、f,g,hR=<a,b><b,c>,<c,d>,<d,e>,<e,f>,<f,g>,<g,h>则该数据结构具有结构。线性4 .一种数据结构的元素集合K和它的二元关系R为：K=a,b,c,d,e,f,g,hR=<d,b>,<d,g>,<b,a>,<b,c>,<g,e>,<g,h>,<e,f>贝U该数据结构具有结构。非线性5 .线性表的两种存储结构分别为和。顺序；链式6 .在一个单链表中删除指针p所指向结点的后继结点时，需要把的值赋

11、给p->next指针域。.p->next->next7 .栈又称为表，队列又称为表。先进后出；先进先出8 .假定一个链栈的栈顶指针为top,每个结点包含值域data和指针域next,当p所指向的结点入栈时，则首先执行操作，然后执行操作。.p->next=top;top=pABCE图2DGIHF9 .队列的插入操作在进行，删除操作在进行。队尾；对头10 .在一棵二叉树中，假定双分支结点数为5个，单分支结点数为6个，则叶子结点数为。611 .对于一棵二叉树，若一个结点的编号i,若它的左孩子结点存在，则其编号为，若右孩子结点存在，则其编号为，若双亲结点存在，则其编号为。2i;

12、2i+1;i/212 .一个森林转换成二叉树后如图1.9所示，则该森林/7k中包含棵树。313 .若由3,6,8,12,10作为叶子结点的值生成一棵哈夫曼树，则该树的深度为，带权路径长度为。''<'、二4;8714 .一种数据结构的元素集合K和它的二元关系R为：图L9K=1,2,3,4,5,6R=(1,2)(2,3)(2,4)(3,4)(3,5)(3,6)(4,5)(4,6)则该数据结构具有一数据结构。图状15 .假定对线性表(38,25,74,52,48),进行散列存储，采用H(K)=K%7作为哈希函数，采用线性探测再散列法处理冲突，则在建立哈希表过程中，将会碰

13、到次冲突，平均查找长度为。5；216 .若对一组记录(46,79,56,38,40,80,35,50,74)进行直接插入排序，当把第8个记录插入到前面已排序的有序表时，为寻找插入位置需比较次。4三、简答题1.已知一棵二叉树的中序遍历序列为CDBAEGF先序遍历序列为ABCDEFG试问能不能唯一确定一棵二叉树？若能，画出该二叉树。若给定先序遍历序列和后序遍历序列，能否唯一确定？18.(1)由中序遍历序列和先序遍历序列，或中序遍历序列和后序遍历序列，可以唯一确定一颗二叉树。由先序序列知，根结点最先被访问，就可确定根结点为A,而又由中序序列得知一棵树的根结点是其左，右子树的分隔点，从而可确定以A为根

14、的左子树的结点为B,C,D,右子树的结点为E,F,G。重复进行就可得到二叉树。(2)由先序遍历序列和后序遍历序列不能唯一确定一棵二叉树。因为两种遍历方法只能确定根结点，而分不清左右子树。2 .将图1.12所示的树转换成二叉树。L印3 .试分别画出具有3个结点的树和3个结点的二叉树的所有不同形态。树的状态如图1.21所示.4.假定用于通信的电文由8个字母组成，分别是A,B,C,D,E,F,G,和H,各字母在电文中出现的概率为：5%,25%,4%,7%,9%,12%,30%,8%,试为8个字母设计哈夫曼编码。5.给出一组关键字(19,01,26,92,87,11,43,87,21),进行冒泡排序，

15、列出每一遍排序后关键字的排列次序，并统计每遍排序进行的关键字比较次数。初始关键字序列为：(19,01,26,92,87,11,43,87,21)第一遍排序比较8次，交换6次后成为：(01,19,26,87,11,43,87,21,92)第二遍排序比较7次，交换3次后成为：(01,19,26,11,43,87,21,87,92)第三遍排序比较6次，交换2次后成为：1(01,19,11,26,43,21,87,87,92)第四遍排序比较5次，交换2次后成为：(01,11,19,26,21,43,87,87,92)第五遍排序比较4次，交换1次后成为：(01,11,19,21,26,43,87,87,92)第六遍排序比较3次，交换0次。排序完毕。6 .已知一个顺序存储的有序表为(15,26,34,的二分查找判定树，求出其平均查找长度。39,45,56,58,63,74,6),试画出对应平均查找长度：ASL=(1+2X2+3X4+4X3)/10=2.9折半查找判定树如图1.31所示。7 .设有一组关键字(17,13,14,153,29,35)需插入到表长为1