a[i][j]=i*j;
A.O(m2)B.O(n2)C.O(m+n)D.O(m*n)
4.在一个长度为n的顺序存储结构的线性表中,向第i个元素(1≤i≤n+1)位置插入一个元素时,需要从后向前依次后移()个元素。
A.n-iB.n-i+lC.n-i-lD.i
5.在一个长度为n的顺序存储结构的线性表中,删除第i个元素(1≤i≤n+1)时,需要从前向后依次后移()个元素。
A.n-iB.n-i+lC.n-i-lD.i
6.在一个长度为n的线性表中,删除值为x的元素时需要比较元素
和移动元素的总次数为()。
A.(n+1)/2B.n/2C.nD.n+1
7.在一个顺序表中的任何位置插入一个元素的时间复杂度为()。
A.O(n)B.O(n/2)C.O
(1)D.O(n2)
8.线性表的链式存储比顺序存储更有利于进行()操作。
A.查找B.表尾插入和删除
C.按值插入和删除D.表头的插入和删除
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->next=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->next=q;
13.栈的插入和删除操作在()进行。
A.栈顶B.栈底C.任意位置D.指定位置
14.若让元素1,2,3,4依次进栈,则出栈次序不可能出现()的情况。
A.3,2,1,4B.2,1,4,3
C.4,3,2,1D.1,4,2,3.
15.假定一个顺序循环队列的队首和队尾指针分别用f和r表示,则
判断队空的条件为()。
A.f+1==rB.r+1==fC.f==0D.f==r
16.假定一个顺序循环队列存储于数组a[N],其队首和队尾指针分别
用f和r表示,则判断队满的条件为()。
A.(r-1)%N==fB.(r+1)%N==f
C.(f-1)%N==rD.(f+1)%N==r
17.二维数组A[12,10]采用行优先存储,每个数据元素占用4个存储
单元,该数组的首地址(A[0,0]的地址)为1200,则A[6,5]的
地址为()。
A.1400B.1404C.1372D.1460
18.在一棵具有n个结点的二叉树中,所有结点的空子树个数等于()。
A.nB.n-1C.n+1D.2n
19.有如图1所示的一棵二叉树,则该二叉树的中序遍历序列为()。
A.ABCDEFGB.CDBGFEAC.CBDAEGFD.ABECDFG
20.有如图1所示的一棵二叉树,则该二叉树的先序遍历序列为()。
A.ABCDEFGB.CDBGFEAC.CBDAEGFD.ABECDFG
21.有如图1所示的一棵二叉树,则该二叉树的后序便利序列为()。
A.ABCDEFGB.CDBGFEAC.CBDAEGFD.ABECDFG
22.利用n个值生成的哈夫曼树中共有()个结点。
A.nB.n+1C.2nD.2n-1
23.利用3,6,8,12这4个值作为叶子结
点的权,生成一棵哈夫曼树,该树的带
权路径长度为()。
A.55B.29C.58D.38
24.在一个具有n个顶点的无向图中,若具有e条边,则所有顶点的
度数为()。
A.nB.eC.n+eD.2e
25.在一个具有n个顶点和e条边的无向图的邻接矩阵中,表示边存
在的元素(又称为有效元素)的个数为()。
A.nB.neC.eD.2e
26.若一个图的边集为{(A,B)(A,C)(B,D)(C,F)(D,E)(D,F)},则从顶点A开始对该图进行深度优先搜索,得到的顶点序列可能为()。
A.ABCFDEB.ACFDEBC.ABDCFED.ABDFEC
27.若一个图的边集为{(A,B)(A,C)(B,D)(C,F)(D,E)(D,F)},则从顶点A开始对该图进行广度优先搜索,得到的顶点序列可能为()。
A.ABCDEFB.ABCFDEC.ABDCEFD.ACBFDE
28.对于顺序存储的有序表(5,12,20,26,37,42,46,50,64),若采用二分查找,则查找元素26的查找长度为()。
A.2B.3C.4D.5
29.若根据查找表(23,44,36,48,52,73,64,58)建立线性哈希表,采用H(K)=K%13计算哈希地址,则元素64的哈希地址为()。
A.4B.8C.12D.13
30.若根据查找表(23,44,36,48,52,73,64,58)建立线形哈希表,采用H(K)=K%13计算哈希地址,则哈希地址为3的元素个数为()。
A.1B.2C.3D.4答案为0
31.若一个元素序列基本有序,则选用()方法较快。
A.直接插入排序B.简单选择排序C.堆排序D.快速排序
二﹑填空题
1.数据的逻辑结构可分为____和____两大类。
线性;非线性
2.数据的存储结构被分为____,_____,_____和____4种。
顺序;链式;索引;散列存储结构
3.一种数据结构的元素集合K和它的二元关系R为:
K={a,b,c,d,e,f,g,h}
R={,,,,,,}
则该数据结构具有____结构。
线性
4.一种数据结构的元素集合K和它的二元关系R为:
K={a,b,c,d,e,f,g,h}
R={,,,,,,}则该数据
结构具有____结构。
非线性
5.线性表的两种存储结构分别为____和____。
顺序;链式
6.在一个单链表中删除指针p所指向结点的后继结点时,需要把____的值赋给p->next指针域。
.p->next->next
7.栈又称为____表,队列又称为____表。
先进后出;先进先出
8.假定一个链栈的栈顶指针为top,每个结点包含值域data和指针域next,当p所指向的结点入栈时,则首先执行____操作,然后执行____操作。
.p->next=top;top=p
ABCE
图2DGIHF
9.队列的插入操作在____进行,删除操作在____进行。
队尾;对头
10.在一棵二叉树中,假定双分支结点数为5个,单分支结点数为6个,则叶子结点数为____。
6
11.对于一棵二叉树,若一个结点的编号i,若它的左孩子结点存在,
则其编号为____,若右孩子结点存在,则其编号为____,若双亲结
点存在,则其编号为____。
2i;2i+1;i/2
12.一个森林转换成二叉树后如图1.9所示,则该森林中包含____棵树。
3
13.若由3,6,8,12,10作为叶子结点的值生成一棵哈夫曼树,则该树的深度为____,带权路径长度为____。
4;87
14.一种数据结构的元素集合K和它的二元关系R为:
K={1,2,3,4,5,6}
R={(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;2
16.若对一组记录(46,79,56,38,40,80,35,50,74)进行直接插入排序,当把第8个记录插入到前面已排序的有序表时,为寻找插入位置需比较_____次。
4
三、简答题
1.已知一棵二叉树的中序遍历序列为CDBAEGF,先序遍历序列为ABCDEFG,试问能不能唯一确定一棵二叉树?
若能,画出该二叉树。
若给定先序遍历序列和后序遍历序列,能否唯一确定?
18.
(1)由中序遍历序列和先序遍历序列,或中序遍历序列和后序遍历序列,可以唯一确定一颗二叉树。
由先序序列知,根结点最先被访问,就可确定根结点为A,而又由中序序列得知一棵树的根结点是其左,右子树的分隔点,从而可确定以A为根的左子树的结点为B,C,D,右子树的结点为E,F,G。
重复进行就可得到二叉树。
(2)由先序遍历序列和后序遍历序列不能唯一确定一棵二叉树。
因为两种遍历方法只能确定根结点,而分不清左右子树。
2.将图1.12所示的树转换成二叉树。
3.试分别画出具有3个结点的树和3个结点的二叉树的所有不同形态。
树的状态如图1.21所示.
3个结点的二叉树的状态如图1.22所示
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),进行冒泡排序,列出每一遍排序后关键字的排列次序,并统计每遍排序进行的关键字比较次数。
初始关键字序列为:
(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次。
排序完毕。
6.已知一个顺序存储的有序表为(15,26,34,39,45,56,58,63,74,6),试画出对应的二分查找判定树,求出其平均查找长度。
折半查找判定树如图1.31所示。
平均查找长度:
ASL=(1+2×2+3×4+4×3)/10=2.9
7.设有一组关键字(17,13,14,153,29,35)需插入到表长为12的散列表中,请回答下列问题: