数据结构18习题集含答案Word文档下载推荐.docx
- 文档编号:8122018
- 上传时间:2023-05-10
- 格式:DOCX
- 页数:22
- 大小:189.39KB
数据结构18习题集含答案Word文档下载推荐.docx
《数据结构18习题集含答案Word文档下载推荐.docx》由会员分享,可在线阅读,更多相关《数据结构18习题集含答案Word文档下载推荐.docx(22页珍藏版)》请在冰点文库上搜索。
A.顺序存储的线性结构B.链式存储的非线性结构
C.限制存取点的线性结构D.限制存取点的非线性结构
9.从逻辑上可以把数据结构分为(C)两大类。
A.动态结构、静态结构B.顺序结构、链式结构
C.线性结构、非线性结构D.初等结构、构造型结构
10.下列四个序列中,哪一个是堆(C)。
A.75,65,30,15,25,45,20,10B.75,65,45,10,30,25,20,15
C.75,45,65,30,15,25,20,10D.75,45,65,10,25,30,20,15
11.在下述结论中,正确的是(D)
①只有一个结点的二叉树的度为0;
②二叉树的度为2;
③二叉树的左右子树可任意交换;
④深度为K的完全二叉树结点个数小于或等于深度相同的满二叉树。
A.①②③B.②③④C.②④D.①④
12.若一棵二叉树具有10个度为2的结点,5个度为1的结点,则度为0的结点个数是(B)
A.9B.11C.15D.不确定
13.在下面的程序段中,对x的赋值语句的频度为(C)。
for(i=1;
i<
n;
i++)
for(j=1;
j<
i;
j++)
x=x+1;
A.O(2n)B.O(n)C.O(n2)D.O(log2n)
14.一个n个顶点的连通无向图,其边的个数至少为(A)。
A.n-1B.nC.n+1D.nlogn;
15.根结点在第1层的二叉树的第I层上最多含有结点数为(C)
A.2IB.2I-1-1C.2I-1D.2I-1
16.下列排序算法中(C)排序在一趟结束后不一定能选出一个元素放在其最终位置上。
A.选择B.冒泡C.归并D.堆
17.散列文件使用散列函数将记录的关键字值计算转化为记录的存放地址,因为散列函数是一对一的关系,则选择好的(D)方法是散列文件的关键。
A.散列函数B.除余法中的质数
C.冲突处理D.散列函数和冲突处理
18.在一个长度为n的顺序表中,向第i个元素(1≤i≤n+1)之前插入一个新元素时,需向后移动(B)个元素。
A.n-1B.n-i+1C.n-i-1D.i
19.在一个具有n个单元的顺序栈中,假定以地址低端作为栈底,以top作为栈顶指针,则当做退栈处理时,top变化为(C)。
A.top不变B.top=-nC.top=top-1D.top=top+1
20.向顺序栈中压入元素时,是()。
A.先存入元素,后移动栈顶指针B.先移动栈顶指针,后存入元素
说明:
若顺序栈top初始值为-1,则选B,若初始值为0,则可以选A
21.在一个顺序存储的循环队列中,队首指针指向队首元素的(C)。
A.前一个位置B.后一个位置C.队首元素位置D.队尾元素位置
22.若进栈序列为1,2,3,4,进栈过程中可以出栈,则(C)不可能是一个出栈序列。
A.3,4,2,1B.2,4,3,1C.1,4,2,3D.3,2,1,4
23.在具有n个单元的顺序存储的循环队列中,假定front和rear分别为队首指针和队尾指针,则判断队空的条件是(C)。
A.front==rear+1B.front+1==rearC.front==rearD.front==0
24.在具有n个单元的顺序存储的循环队列中,假定front和rear分别为队首指针和队尾指针,则判断队满的条件是(D)。
A.rear%n==frontB.(rear-1)%n==front
C.(rear-1)%n==rearD.(rear+1)%n==front
25.从一个具有n个节点的单链表中查找其值等于x结点时,在查找成功的情况下,需平均比较(D)个结点。
A.nB.n/2C.(n-1)/2D.(n+1)/2
26.在一个单链表中,已知*q结点是*p结点的前驱结点,若在*q和*p之间插入*s结点,则执行(C)。
A.s->
B.p->
next=p;
C.q->
D.p->
s>
next=q;
27.向一个带头结点的链栈中插入一个*s结点时,其中栈顶指针为hs,则执行(B)。
A.hs->
B.s->
next=hs->
hs->
C.s->
next=hs;
hs=s;
D.s->
next=hs;
hs=hs->
注:
若不带头结点,C也可以
28.在一个链队列中,假定front和rear分别为队首指针和队尾指针,则进行插入*s结点的操作时应执行(B)。
A.front->
front=s;
B.rear->
rear=s;
C.front=front->
D.front=rear->
29.线性表是(A)。
A.一个有限序列,可以为空B.一个有限序列,不能为空
C.一个无限序列,可以为空D.一个无限序列,不能为空
30.对顺序存储的线性表,设其长度为n,在任何位置上插入或删除操作都是等概率的,删除一个元素时大约要移动表中的(C)个元素。
A.n+1B.n-1C.(n-1)/2D.n
31.线性表采用链式存储时,其地址(D)。
A.必须是连续的B.部分地址必须是连续的
C.一定是不连续的D.连续与否均可以
32.设单链表中指针p指着结点(数据域为m),指针f指着将要插入的新结点(数据域为x),当x插在结点m之后时,只要先修改(B)后修改p->
link=f即可。
A.f->
link=p;
B.f->
link=p->
link;
C.p->
link=f->
D.f=nil;
33.根据线性表的链式存储结构,每个结点所含指针的个数,链表分为单链表和(B)。
A.循环链表B.多重链表C.普通链表D.无头结点链表
34.在数据结构中,与所使用的计算机无关的数据叫(C)结构。
A.存储B.物理C.逻辑D.物理和存储
35.二分法查找(A)存储结构。
A.只适用于顺序B.只适用于链式C.既适用于顺序也适用于链式
D.既不适合于顺序也不适合于链式
36.在线性表的链式存储结构中,逻辑上相邻的元素在物理位置上(B)。
A.一定相邻B.不一定相邻C.有时相邻
37.设字符串s1='
abcdefg'
s2='
pqrst'
,则运算s=concat(sub(s1,2,len(s2)),sub(s1,len(s2),2))后串值为(D)。
A.'
bcdef'
B.'
bcdefg'
C.'
bcpqrst'
D.'
bcdefef'
注:
concat连接字符串,sub求子串
38.假定在一棵二叉树中,双分支结点数为15个,单分支结点数为32个,则叶子结点数为(B)。
A.15B.16C.17D.47
39.假定一棵二叉树的结点数为18个,则它的最小高度(B)。
A.4B.5C.6D.18
40.在一棵二叉树(根结点所在的层为1)中第五层上的结点数最多为(C)。
A.8B.15C.16D.32
41.在一棵具有五层的满二叉树中,结点总数为(A)。
A.31B.32C.33D.16
42.已知8个数据元素为(34、76、45、18、26、54、92、65),按照依次插入结点的方法生成一棵二叉排序树后,最后两层上的结点总数为(B)。
A.1B.2C.3D.4
43.由分别带权为9、2、5、7的四个叶子结点构造一棵哈夫曼树,该树的带权路径长度为(C)。
A.23B.37C.44D.46
44.下面答案(D)是查找二叉树(又称二叉排序树)。
A.二叉树中的每个结点的两棵子树的高度差的绝对值不大于1
B.二叉树中的每个结点的两棵子树的高度差等于1
C.二叉树中的每个结点的两棵子树是有序的
D.二叉树中的每个结点的关键字大于其左子树(如果存在)所有结点的关键字值,且小于其右子树(如果存在)所有结点的关键字值。
45.如果结点A有三个兄弟,而且B是A的双亲,则B的出度是(B)。
A.3B.4C.5D.1
46.一个深度为L的满k叉树有如下性质:
第L层上的结点都是叶子结点,其余各层上每个结点都有k棵非空子树。
如果按层次顺序从1开始对全部结点编号,编号为n的有右兄弟的条件是(B)。
A.(n-1)%k==0B.(n-1)%k!
=0C.n%k==0D.n%k!
=0
以满三叉树为例
47.在完全二叉树(结点编号从1开始)中,当i为奇数且不等于1时,结点i的左兄弟是结点(D),否则没有左兄弟。
A.2i-1B.i+1C.2i+1D.i-1
48.在一个有向图中,所有顶点的入度之和等于所有顶点的出度之和的(B)倍。
A.1/2B.1C.2D.4
49.对于一个具有n个顶点和e条边的无向图,若采用邻接表表示,则表头向量的大小为(A)。
A.nB.n+1C.n-1D.n+e
50.具有n个顶点的无向完全图,边的总数为(D)条。
A.n-1B.nC.n+1D.n*(n-1)/2
51.设图G有n个顶点和e条边,当G是非孤立顶点的连通图时有2e>
=n,故可推得深度优先搜索的时间复杂度为(A)。
(最坏的情况就是把所有的边都遍历了一边)
A.O(e)B.O(n)C.O(ne)D.O(n+e)
52.最小代价生成树(B)。
A.是唯一的B.不一定是唯一的,但最小代价是唯一的。
53.在无向图G的邻接矩阵A中,若A[i,j]等于1,则A[j,i]等于(C)。
A.i+jB.i-jC.1D.0
54.对于长度为9的顺序存储的有序表,若采用折半查找,在等概率情况下的平均查找长度为( C )。
A.20/9B.18/9C.25/9D.22/9
55.已知一个有序表为(12、18、24、35、47、50、62、83、90、115、134),当二分查找值为90的元素时,(B)次比较后查找成功;
当二分查找值为47的元素时,(D)次比较后查找成功。
A.1B.2C.3D.4
56.散列函数有一个共同性质,即函数值应当以(D)取其值域的每个值。
A.最大概率B.最小概率C.平均概率D.同等概率
57.设散列地址空间为0~m-1,k为关键字,用p去除k,将所得的余数作为k的散列地址,即H(k)=k%p。
为了减少发生冲突的频率,一般取p为(D)。
A.小于m的最大奇数B.小于m的最大偶数
C.mD.小于等于m的最大素数
58.设关键字序列为:
3,7,6,9,8,1,4,5,2。
进行简单选择排序的最少交换次数是(A)。
A.6B.7C.8D.20
59.一组记录排序码为(46、79、56、38、40、84),则利用堆排序的方法建立的初始堆为(B)。
A.(79、46、56、38、40、80)B.(84、79、56、38、40、46)
C.(84、79、56、46、40、38)D.(84、56、79、40、46、38)
60.一组记录的关键码为(46、79、56、38、40、84),则利用快速排序的方法,以第一个记录为基准得到的一次划分结果为(C)。
A.(38、40、46、56、79、84)B.(40、38、46、79、56、84)
C.(40、38、46、56、79、84)D.(40、38、46、84、56、79)
二、填空题
1.在线性结构中第一结点无前驱结点,其余每个结点有且只有一个前驱结点;
最后一个结点无后继结点,其余每个结点有且只有一个后继结点。
2.在树型结构中,树根结点没有父亲结点,其余每个结点有且仅有一个父亲结点;
树叶结点没有孩子结点,其余每个结点的孩子结点数不受限制。
3.广义表((((a),b),c),d,(c))的表头(head)是(((a),b),c);
表尾(tail)是(d,(c))。
4.一个n阶下三角矩阵A按行优先顺序压缩存放在一维数组B中,则B中的元素个数是n(n+1)/2+1。
(需要一个元素,存储非下三角元素的值)
5.对于长度为n的顺序表,插入或删除元素的时间复杂性为O(n);
对于顺序栈或队列,插入或删除元素的时间复杂性为O
(1)。
6.设有一顺序栈S,元素s1,s2,s3,s4,s5,s6依次进栈,如果6个元素出栈的顺序是s2,s3,s4,s6,s5,s1,则栈的容量至少应该是3。
7.在线性表的顺序存储中,元素之间的逻辑关系是通过下标决定的;
在线性表的链接存储中,元素之间的逻辑关系是通过指针决定的。
8.一棵结点总数为9的完全二叉树,有5个叶子结点。
9.单链表如下图,完成对它的基本操作
(1)删除*p结点时,应执行如下操作:
(1)q=p->
(2)p->
data=p->
next->
data;
(3)p->
next=q->
next;
(4)free(q);
(2)若要在一个单链表中的*p结点之前插入一个*s结点时,可执行如下操作
(1)s->
next=p->
(3)t=p->
(4)p->
data=s->
data;
(5)s->
data=t;
10.无论对于顺序存储还是链接存储的栈和队列来说,进行插入或删除运算的时间复杂性均相同,则为O
(1)。
┏0020┓
11.一个稀疏矩阵为┃3000┃,则对应的三元组线性表为
┃00-15┃
┗0000┛
{{0,2,2},{1,0,3},{2,2,-1},{2,3,5}}。
12.对于一棵具有n个结点的树,则该树中所有结点的度之和为n-1。
13.在一棵二叉树中,度为0的结点的个数为n0,度为2的结点的个数为n2,则n0=n2+1。
14.在二叉树的顺序存储中(下标从1开始),对于下标为5的结点,它的双亲结点的下标为2,若它存在左孩子,则左孩子结点的下标为10,若它存在右孩子,则右孩子结点的下标为11。
15.9.若广义表表示为(b(c,d(e,f),g(h)),i(j,k(x,y))),则广义表的长度为1,深度为4(假设根结点的层数为1)
16.假定一棵二叉树的广义表表示为A(B(,D),C(E(,G),F)),则该树的深度为4,度为0的结点数为3,度为1的结点数为2,度为2的结点数为2;
C结点是A结点的右孩子,E结点是C结点的左孩子。
17.在一棵二叉排序树中,按中序遍历得到的结点序列是一个有序序列。
18.由分别带权为3,9,6,2,5的共五个叶子结点构成一棵哈夫曼树,则带权路径长度为55。
left
data
right
19.假定在二叉树的链接存储中,每个结点的结构为
data为值域,left和right分别为链接左、右孩子结点的指针域,请在下面中序遍历算法中画有横线的地方填写合适的语句。
voidinorder(node*bt)(bt是指向结点的指针)
{if(bt!
=null){
(1)inorder(bt->
left);
(2)printf(bt->
data);
(3)inorder(bt->
right);
}
}
20.在图G的邻接表表示中,每个顶点邻接表中所含的结点数,对于无向图来说等于该顶点的度数,对于有向图来说等于该顶点的出度数。
21.假定一个无向连通网图具有n个顶点和e条边,则采用邻接矩阵表示的空间复杂性为O(n2),采用邻接表表示的空间复杂性为O(n+e),采用Prim算法求最小生成树的时间复杂度是O(n2),采用克鲁斯卡尔算法求最小生成树的时间复杂度是O(elog2e)。
22.已知一个无向图的邻接矩阵如下所示,则从顶点A出发按深度优先搜索遍历得到的顶点序列为ABCDFE,按广度优先搜索遍历得到的顶点序列为ABCEFD。
23.在索引查找或分块查找中,首先查找索引表,然后再查找相应的子表,整个索引查找的平均查找长度等于查找索引表的平均查找长度与查找相应子表的平均查找长度之和。
24.在散列存储中,装填因子α的值越大,存取元素时发生冲突的可能性就大,当α的值越小,存取元素时发生冲突的可能性就小。
25.给定线性表(18,25,63,50,42,32,90),用散列方式存储,若选用h(K)=K%9作为散列函数,则元素18的同义词元素共有2个,元素25的同义词元素共有0个,元素50的同义词元素共有1个。
26.在对一组记录(54,38,96,23,15,72,60,45,83)进行直接选择排序时,第四次选择和交换后,未排序记录(即无序表)为(54,72,60,96,83)。
27.已知一个图如下所示,在该图的最小生成树的代价为47。
28.给出从顶点1到顶点8的关键路径长度97。
(最长路径)
29.假定在有序表A[1..20]上进行二分查找,则比较一次查找成功的结点数为1,比较两次查找成功的结点数为2,比较三次查找成功的结点数为4,比较四次查找成功结点数为8,比较五次查找成功的结点数为5,平均查找长度为74/20。
30.在对一组记录(54,38,96,23,15,72,60,45,38)进行冒泡排序时,第一趟需进行相邻记录交换的次数为7,在整个冒泡排序过程中共需进行6趟后才能完成。
这里是从后往前冒泡的结果
31.在归并排序中,若待排序记录的个数为20,则共需要进行5趟归并,在第三趟归并中,是把长度为4的有序表归并为长度为8的有序表。
32.在直接插入和简单选择排序中,若初始数据基本正序,则选用直接插入,若初始数据基本反序,则选用简单选择。
33.在堆排序、快速排序和归并排序中,若只从节省空间考虑,则应首先选取堆排序方法,其次选取快速排序方法,最后选取归并排序方法;
若只从排序结果的稳定性考虑,则应选取归并排序;
若只从平均情况下排序最快考虑,则应选取快速方法;
若只从最坏情况下排序最快并且要节省内存考虑,则应选取堆排序方法。
三、判断题
1.数据元素是数据的最小单位(Ⅹ)。
(数据项是最小单位,数据元素是基本单位)
2.数据项是数据的基本单位(Ⅹ)。
3.顺序存储的线性表可以随机存取(√)。
4.线性表中的元素可以是各种各样的,但同一线性表中的数据元素具有相同的特性,因此,是属于同一数据对象(√)。
5.在单链表中,任何两个元素的存储位置之间都有固定的联系,因为可以从头结点查找任何一个元素(Ⅹ)。
(链表中的元素的存储位置,没有固定联系)
6.在单链表中,要取得某个元素,只要知道该元素的指针即可,因此,单链表是随机存取的存储结构(Ⅹ)。
(顺序表才是随机存储)
7.链表的每个结点中,都恰好包含一个指针(Ⅹ)。
(双向链表就有两个指针)
8.使用三元组表示稀疏矩阵的元素,有时并不能节省存储时间(√)。
(如果非零元个数太多,就不节省时间了)
9.由树转换成二叉树,其根结点的右子树总是空的(√)。
(根结点没有兄弟)
10.后序遍历树和中序遍历与该树对应的二叉树,其结果不同(Ⅹ)。
(可能相同,也可能不同)
11.若有一个结点是某二叉树子树的中序遍历序列中的最后一个结点,则它必是该子树的前序遍历序列中的最后一个结点(√)。
(都是最右的结点)
12.已知二叉树的前序遍历和后序遍历序列并不能唯一地确定这棵树,因为不知道树的根结点的左子树和右子树中分别包含哪些结点。
(√)
13.有回路的图不能进行拓扑排序(√)。
14.连通分量是无向图中的极小连通子图(Ⅹ)。
15.散列法存储的基本思想是由关键码的值决定数据的存储地址(√)。
16.散列表的查找效率取决于散列表造表时选取的散列函数和处理冲突的方法(√)。
17.中序遍历二叉排序树的结点就可以得到排好序的结点序列(√)。
18.在二叉排序树上插入新的结点时,不必移动其它结点,仅需改动某个结点的指针,由空变为非空即可(√)。
19.当待排序的元素很多时,为了交换元素的位置,移动元素要占用较多的时间,这是影响时间复杂性的主要因素(Ⅹ)。
(比较次数多才是主要因素)
20.对于n个记录的集合进行快速排序,所需要的平均时间是O(nlog2n)(√)。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 18 习题集 答案