数据结构含答案

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

2、个元素(K i < n+1)位置插入一个元素时，需要从后向前依次后移()个元素。A.n-iB. n-i+IC. n-i-l D.i5在一个长度为n的顺序存储结构的线性表中，删除第i个元素(K iw n+1)时，需要从前向后依次后移()个元素。A.n-iB. n-i+IC. n-i-l D.i6 在一个长度为n的线性表中，删除值为x的元素时需要比较元素和移动元素的总次数为()。A.(n+1)/2 B.n/2 C.n D.n+17 在一个顺序表中的任何位置插入一个元素的时间复杂度为()。A. 0(n) B. O(n/2) C. O(1) D. 0(n2)8. 线性表的链式存储比顺序存储更有利

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

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

5、 ext=p;C. p=q _>n ext; q_>n ext=p->n ext;D. q->n ext=q->n ext->n ext; q->n ext=q;13. 栈的插入和删除操作在（）进行。A.栈顶B.栈底C.任意位置D.指定位置14. 若让元素1，2，3，4依次进栈，则出栈次序不可能出现（）的情况。A.3，2，1，4 B.2，1，4，3C.4，3，2，1 D.1，4，2，3.f和r表示，则15. 假定一个顺序循环队列的队首和队尾指针分别用 判断队空的条件为（）。A.f+ 仁=B.r+ 仁=彳 C.f=0 D.f=r16.假定一个顺序循环队列

6、存储于数组aN,其队首和队尾指针分别用f和r表示，则判断队满的条件为()A. (r-1) %N=f B. (r+1) %N=fC. (f-1) %N=r D. (f+1) %N=r17. 二维数组A12,10采用行优先存储，每个数据元素占用4个存储单元，该数组的首地址（A0，0的地址）为1200，则A6，5的 地址为()。A.1400 B.1404 C.1372 D.146018. 在一棵具有n个结点的二叉树中，所有结点的空子树个数等于（）A.n B.n-1 C.n+1 D.2 n19. 有如图1所示的一棵二叉树，则该二叉树的中序遍历序列为（）A. ABCDEFG B. CDBGFEA C.

7、CBDAEGF D. ABECDFG20. 有如图1所示的一棵二叉树，则该二叉树的先序遍历序列为（）A.ABCDEFG B.CDBGFEA C.CBDAEGF D.ABECDFG21. 有如图1所示的一棵二叉树，则该二叉树的后序便利序列为（）A.ABCDEFGB.CDBGFEA C.CBDAEGF D.ABECDFG22. 利用n个值生成的哈夫曼树中共有（）个结 点。A.n B. n+1 C.2 n D.2 n-123. 利用3，6，8，12这4个值作为叶子结 点的权，生成一棵哈夫曼树，该树的带 权路径长度为（）。A.55 B.29 C.58 D.3824. 在一个具有n个顶点的无向图中，若具

8、有 e 条边，则所有顶点的 度数为()。A. nB.eC. n+eD.2e25. 在一个具有n个顶点和e条边的无向图的邻接矩阵中，表示边存 在的元素（又称为有效元素）的个数为（）。A.n B. ne C.eD.2e26. 若一个图的边集为（ A，B）（ A，C）（B，D）（ C,F）（ D，E）（ D,F），则从顶点A开始 对该图进行深度优先搜索，得到的顶点序列可能为（）A. ABCFDEB. ACFDEB C. ABDCFE D. ABDFEC27. 若一个图的边集为（ A，B）（ A，C）（B, D）（ C, F）（ D，E）（ D, F），则从顶点A开始对该图进行广度优先搜索，得到的顶点

9、序列可能为（）。A.ABCDEF B.ABCFDE C.ABDCEF D.ACBFDE28. 对于顺序存储的有序表（5，12, 20，26，37，42，46，50，64），若采用二分查找，则 查找元素26的查找长度为（）。A.2 B.3 C.4 D.529. 若根据查找表（23, 44, 36，48，52，73, 64，58）建立线性哈希表，采用H （K）=K%13计算哈希地址，则元素 64的哈希地址为（）。A.4 B.8 C.12 D.1330. 若根据查找表（23, 44, 36, 48, 52, 73, 64, 58）建立线形哈希表，采用H （K）=K%13计算哈希地址，则哈希地址为3的

10、元素个数为（）。A.1 B.2 C.3 D.4 答案为 031. 若一个元素序列基本有序，则选用（）方法较快。A.直接插入排序 B.简单选择排序 C.堆排序D.快速排序二、填空题1. 数据的逻辑结构可分为和_两大类。线性；非线性2. 数据的存储结构被分为 _, , 和_4种。顺序；链式；索弓|；散列存储结构3. 一种数据结构的元素集合K和它的二元关系R为：K=a,b,c,d,e,f,g,hR=<a,b>, <b,c>, <c,d>, <d,e>, <e,f>, <f,g>, <g,h>则该数据结构具有结构。线性

11、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>则该数据结构具有结构。非线性5. 线性表的两种存储结构分别为 和。顺序；链式6. 在一个单链表中删除指针p所指向结点的后继结点时，需要把 的值赋给p->next指针域。.p->next->next7栈又称为 表，队列又称为 表。先进后出；先进先出8假定一个链栈的栈顶指针为top，每个结点包含值域 data和指针域n

12、ext，当p所指向的结点入栈时，则首先执行 操作，然后执行 操作。.p->next二top;top二pABCE图 2DGIHF9队列的插入操作在 进行，删除操作在 进行。队尾；对头10. 在一棵二叉树中，假定双分支结点数为 5个，单分支结点数为6个，则叶子结点数为 。611. 对于一棵二叉树，若一个结点的编号i，若它的左孩子结点存在,则其编号为 ，若右孩子结点存在，则其编号为 ，若双亲结点存在，则其编号为。2i; 2i+1; i/212. 一个森林转换成二叉树后如图1.9所示，则该森林中包含棵树。313. 若由3, 6 , 8, 12, 10作为叶子结点的值生成一棵哈夫曼树，则该树的深度

13、为,带权路径长度为_4; 8714. 一种数据结构的元素集合K和它的二元关系 R为:K=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作为哈希函数,采用线性探测再散列法处理冲突，则在建立哈希表过程中，将会碰到次冲突，平均查找长度为。 5; 216. 若对一组记录(46 , 79 , 56 , 38 , 40 , 80 , 35 , 50

14、, 74)进行直接插入排序，当把第 8个记录插入到前面已排序的有序表时，为寻找插入位置需比较 次。4三、简答题 1.已知一棵二叉树的中序遍历序列为 CDBAEGF先序遍历序列为 ABCDEFG试问能不能唯 一确定一棵二叉树？若能，画出该二叉树。若给定先序遍历序列和后序遍历序列， 能否唯一 确定？18.(1)由中序遍历序列和先序遍历序列，或中序遍历序列和后序遍历序列，可以唯一确定颗二叉树。由先序序列知，根结点最先被访冋，就可确定根结点为A，而又由中序序列得知一棵树的根结点是其左，右子树的分隔点，从而可确定以A为根的左子树的结点为 B,C,D,右子树的结点为E,F,G。重复进行就可得到二叉树。（2

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

16、列次序，并统计每遍排序进行的关键字比较次数。(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次后成为：(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次。排序完毕。初始关键字序列为:1729图1 . 2$6已知一个顺序存储的有序表为(15, 26 , 34, 39, 45, 56, 58, 63, 74 , 6),试画出对应的二分查找判定树，求出其平均查找长度。折半查找判定树如图1. 31所示。平均查找长度： ASL= (1+2 X 2 + 3X 4+ 4X 3) /10=2.9Hk 317. 设有一组关键字(17, 13, 14, 153, 29, 35)需插入到表