版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
数据结构试题
单选题
在数据结构的讨论中把数据结构从逻辑上分为(C)
A内部结构与外部结构B静态结构与动态结构
C线性结构与非线性结构D紧凑结构与非紧凑结构。
2、采用线性链表表示•个向量时,要求占用的存储空间地址(D)
A必须是连续的B部分地址必须是连续的
C一定是不连续的D可连续可不连续
3、采用顺序搜索方法查找长度为n的顺序表时,搜索成功的平均搜索长度为(D)。
AnBn/2C(n-l)/2D(n+l)/2
4、在一个单链表中,若q结点是p结点的前驱结点,若在q与p之间插入结点s,则执行
(D)。
Asflink=pflink;pfink=s;
Bp—link=s;s—link=q;
Cpflink=sflink;s->link=p;
Dq—link=s;link=p;
5、如果想在4092个数据中只需要选择其中最小的5个,采用(C)方法最好。
A起泡排序B堆排序C锦标赛排序D快速排序
6、设有两个串t和p,求p在t中首次出现的位置的运算叫做(B),
A求子串B模式匹配C串替换D串连接
7、在数组A中,每一个数组元素占用3个存储字,行下标i从1至U8,列下标j从1
到10。所有数组元素相继存放于一个连续的存储空间中,则存放该数组至少需要的存储字
数是(C)。
A80B100C240D270
8、将一个递归算法改为对应的非递归算法时,通常需要使用(A)。
A栈B队列C循环队列D优先队列
9、一个队列的进队列顺序是1,2,3,4,则出队列顺序为(C
10、在循环队列中用数组存放队列元素,其队头和队尾指针分别为front和rear,
则当前队列中的元素个数是(D)。
A(front-rear+1)%mB(rear-front+1)%m
C(front-rear+m)%mD(rear-front+m)%m
11、一个数组元素a[i]与(A)的表示等价。
A*(a+i)Ba+iC*a+iD&a+i
12、若需要利用形参直接访问实参,则应把形参变量说明为(B)参数。
A指针B引用C值D变量
13、下面程序段的时间复杂度为C)
for(inti=0;i〈m;i++)
for(intj=0;j<n;j-H-)
a[i][j]=i*j;
AO(m2)BO(n2)CO(m*n)DO(m+n)
14、下面程序段的时间复杂度为B)
int^unsignedintn){
if(n==0||n==1)return1;
elsereturnn*f(n-l);
)
A0(1)B0(n)C0(n2)D0(n!)
15、线性表若是采用链式存储结构时,要求内存中可用存储单元的地址(D)o
A必须是连续的
B部分地址必须是连续的
C一定是不连续的
D连续或不连续都可以
16、数据结构的定义为(D,S),其中口是(B)的集合。
A算法B数据元素C数据操作D逻辑结构
17、算法分析的目的是(A)。
A找出数据结构的合理性
B研究算法中输入和输出的关系
C分析算法的效率以求改进
D分析算法的易懂性和文档性
18、在一个单链表中,若p所指结点不是最后结点,在p之后插入s所指结点,则执行(B)。
As->link=p;p->link=s;
Bs->link=p->link;p->link=s;
Cs->link=p->link;p=s;
Dp->link=s;s->link=p;
19、设单链表中结点结构为(data,link).已知指针q所指结点是指针p所指结点的直接前驱,
若在*q与*p之间插入结点*s,则应执行下列哪一个操作(B)
As->link=p->link;p->link=s;Bq->link=s;s->link=p
Cp->link=s->link;s->link=p;Dp->link=s;s->link=q;
20、设单链表中结点结构为(data,link).若想摘除结点*p的直接后继,则应执行下列哪一个操
作(A)
Ap->link=p->link->link;
Bp=p->link;p->link=p->link->link;
Cp->link=p->link;Dp=p->link->link;
21、设单循环链表中结点的结构为(data,link),且rear是指向非空的带表头结点的单循环链
表的尾结点的指针。若想删除链表第一个结点,则应执行下列哪一个操作(D)
As=rear;rear=rear->link;deletes;
Brear=rear->link;deleterear;
Crear=rear->link->link;deleterear;
Ds=rear->link->link;rear->link->link=s->link;deletes;
22、设单循环链表中结点的结构为(data,link),且first为指向链表表头的指针,current为链
表当前指针,在循环链表中检测current是否达到链表表尾的语句是(D)。
Acurrent->link=nullBfirst->link=current
Cfirst=currentDcurrent->link=first
23、一个栈的入栈序列为a,b,c,则出栈序列不可能的是(C)o
Ac,b,aBb,a,cCc,a,bDa,c,b
24、栈的数组表示中,top为栈顶指针,栈空的条件是(A)。
Atop=0Btop=maxSizeCtop=maxSizeDtop="l
25、栈和队列的共同特点是(C)。
A都是先进后出B都是先进先出
C只允许在端点处插入和删除D没有共同点
26、假定一个顺序存储的循环队列的队头和队尾指针分别为f和r,则判断队空的条件为
(D).
ARl==rBr+l==fC4=0Df==r
27、当利用大小为n的数组顺序存储•个队列时,该队列的最大长度为(B)
An-2Bn-1CnDn+1
28、当利用大小为n的数组顺序存储一个栈时,假定用top==n表示栈空,则向这个栈插
入一个元素时,首先应执行()语句修改top指针。
Atop-H-;Btop—;Ctop=0;Dtop;
29、设链式栈中结点的结构为(data,link),且top是指向栈顶的指针。若想摘除链式栈的栈
顶结点,并将被摘除结点的值保存到x中,则应执行下列(A)操作。
Ax=top->data;top=top->link;Btop=top->link;x=top->data;
Cx=top;top=top->link;Dx=top->data;
30、设循环队列的结构是:
constintMaxsize=100;
typedefintDataType;
typedefstruct{
DataTypedata[Maxsize];
Intfront,rear;
}Queue;
若有一个Queue类型的队列Q,试问判断队列满的条件应是下列哪一个语句(D)
AQ.front==Q.rear;BQ.front-Q.rear==Maxsize;
CQ.front+Q.rear==Maxsize;DQ.front==(Q.rear+1)%Maxsize;
31、设有一个递归算法如下:
intfact(intn)
{if(n<=0)return1;
elsereturnn*fact(n-l);
}
下面正确的叙述是(B)
A计算fhct(n)需要执行n次递归Bfhct⑺=5040
C此递归算法最多只能计算到fact(8)D以上结论都不对
32、设有一个递归算法如下
intx(intn){
if(n<=3)return1;
elsereturnx(n-2)+x(n-4)+l;
试问计算x(x(8))时需要计算(D)次x函数。
A8次B9次C16次D18次
33、设有广义表D(a,b,D),其长度为(B),深度为(A)
A8B3C2D5
34、广义表A(a),则表尾为(C)
AaB(())C空表D(a)
35、下列广义表是线性表的有(C)
AE(a,(b,c))BE(a,E)CE(a,b)DE(a,L())
36、递归表、再入表、纯表、线性表之间的关系为(C)
A再入表>递归表〉纯表〉线性表B递归表>线性表〉再入表〉纯表
C递归表>再入表〉纯表〉线性表D递归表,再入表>线性表〉纯表
37、某二叉树的前序和后序序列正好相反,则该二叉树一定是(B)的二叉树。
A空或只有•个结点B高度等于其结点数
C任一结点无左孩子D任一结点无右孩子
38、对于任何一棵二叉树T,如果其终端结点数为n0,度为2的结点为n2.,则(A)
An0=n2+lBn2=nO+1Cn0=2n2+lDn2=2n0+l
39、由权值分别为11,8,6,2,5的叶子结点生成•棵哈夫曼树,它的带权路径长度为(B)
A24B73C48D53
40、已知一个顺序存储的线性表,设每个结点需占m个存储单元,若第一个结点的地址为
dal,则第I个结点的地址为(A)。
Adal+(I-l)*mBdal+I*mCdal-I*mDdal+(I+l)*m
41、34具有35个结点的完全二叉树的深度为(A)
A5B6C7D8
42、对线性表进行折半搜索时,要求线性表必须(C)
A以链接方式存储且结点按关键码有序排列B以数组方式存储
C以数组方式存储且结点按关键码有序排列D以链接方式存储
43、顺序搜索算法适合于存储结构为(B)的线性表。
A散列存储B顺序存储或链接存储
C压缩存储D索引存储
44、采用折半搜索算法搜索长度为n的有序表时,元素的平均搜索长度为(C)
AO(n2)BO(nlog2n)CO(log2n)DO(n)
45、对于一个具有n个顶点和e条边的无向图,进行拓扑排序时,总的时间为(A)
AnBn+1Cn-1Dn+e
46、判断一个有向图是否存在回路,除了可以利用拓扑排序方法外,还可以利用(C)。
A求关键路径的方法B求最短路径的Dijkstra方法
C深度优先遍历算法D广度优先遍历算法
47、在10阶B-树中根结点所包含的关键码个数最多为(C),最少为(A)
AIB2C9D10
48、对包含n个元素的散列表进行搜索,平均搜索长度为(C)
AO(log2n)BO(n)C不直接依赖于nD上述都不对
填空题()
1、数据的逻辑结构被分为集合结构、线性结构、树形结构、图形结构四种
2、数据的存储结构被分为顺序结构、链接结构、索引结构、散列结构四种
3、一种抽象数据类型包括(数据)和(操作)两个部分。
设有两个串p和q,求p在q中首次出现的位置的运算称为(模式匹配)
栈、队列逻辑上都是(线性存储)结构。
线性结构反映结点间的逻辑关系是(一对一)的,图中的数据元素之间的关系是(多对多)
的,树形结构中数据元素间的关系是(一对多)的。
栈中存取数据的原则(后进先出),队列中存取数据的原则(先进先出)
8、串是由(零个或多个)字符组成的序列。(长度为零的串)称为空串,(由一个
或多个空格组成的串)称为空格串。
9、设目标串T="abccdcdccbaa”,模式P="cdcc"则第(6)次匹配成功。
10、一维数组的逻辑结构是(线性结构),存储结构是(顺序存储表示)。对于二维数组,有
(行优先顺序)和(列优先顺序)两种不同的存储方式,对于一个二维数组A[m][n],若采用
按行优先存放的方式,则任一数组元素相对于A[0][0]的地址为(n*i+j)o
11、向一个顺序栈插入一个元素时,首先使(栈顶指针)后移一个位置,然后把待插入元
素(写)到这个位置上。从一个顺序栈删除元素时,需要前移一位(栈顶指针)。
12、在一个循环队列Q中,判断队空的条件为(Q.front==Q.rear),判断队满的条件为
((Q.rear+l)%MaxSize==q.front)
13、对于一棵具有n个结点的树,该树中所有结点的度数之和为(n-1)。
14、・棵高度为5的满二叉树中的结点数为(63)个,一棵高度为3满四叉树中的结点
数为(85)个。
15、若对一棵二叉树从0开始进行结点编号,并按此编号把它顺序存储到一维数组中,即编
号为0的结点存储到a[0]中,其余类推,则a[i]元素的左子女结点为(2*i+l),右子女结
点为(2*i+2),双亲结点(i>=l)为(「(i-l)/2-I).
16、在一个最大堆中,堆顶结点的值是所有结点中的(最大值),在一个最小堆中,堆顶结
点的值是所有结点中的(最小值)。
17、已知具有n个元素的一维数组采用顺序存储结构,每个元素占k个存储单元,第一个元
素的地址为LOC(al),那么,LOC(ai尸LOC(al)+(i-l)*k。
18、在霍夫曼编码中,若编码长度只允许小于等于4,则除掉已对两个字符编码为。和10外,
还可以最多对(4)个字符编码。
19、设高度为h的空二叉树的高度为-1,只有一个结点的二叉树的高度为0,若设二叉树只
有度为2上度为0的结点,则该二叉树中所含结点至少有(2h+l)个。
20、由棵二叉树的前序序列和(中序序列)可唯确定这棵二叉树。
21、以折半搜索方法搜索一个线性表时,此线性表必须是(顺序)存储的(有序)表。
22、已知完全二叉树的第8层有8个结点,则其叶子结点数是(68)。若完全二叉树的第7
有10个叶子结点,则整个二叉树的结点数最多是(235)
23、对于折半搜索所对应的判定树,它既是一棵(二叉搜索树),又是一棵(理想平衡树)。
24、假定对长度n=50的有序表进行折半搜索,则对应的判定树高度为(5),判定树中
前5层的结点数为(31),最后一层的结点数为(19)。
25、在一个无向图中,所有顶点的度数之和等于所有边数的(2)倍。在一个具有n个顶点
的无向完全图中,包含有(n(n-l)/2)条边,在一个具有n个顶点的有向完全图中,包含
有(n(n-l))条边。
26、对于一个具有n个顶点和e条边的连通图,其生成树中的顶点数和边数分别为(n)和
(n-1)»
27、设线性表中元素的类型是实型,其首地址为1024,则线性表中第6个元素的存储位置
是(1044)。
28、在插入和选择排序中,若初始数据基本正序,则选择(插入排序),若初始数据基本反
序,则最好选择(选择排序)。
29、算法是对特定问题的求解步骤的一种描述,它是(指令)的有限序列,每一条(指令)
表示一个或多个操作。
30、对于一个具有n个顶点肯e条边的无向图,进行拓朴排序时,总的进间为(n)
31、构造哈希函数有三种方法,分别为(平方取中)法、(除留余数)法、(折迭移位)法。
32、处理冲突的三种方法,分别为(线性探测)、(随机探测)、(链地址法)。
33、对于含有n个顶点和e条边的无向连通图,利用普里姆算法产生的最小生成树,其时间
复杂度为(0(n2))、利用克鲁斯卡尔算法产生的最小生成树,其时间复杂度为(0
(elog2e))
34、快速排序在平均情况下的忖间复杂度为(。(nlog2n)),在最坏情况下的时间复杂度为
(0(n2));快速排序在平均情况下的空间复杂度为(0(log2n)),在最坏情况下的空间
复杂度为(0(n)).
35、假定一组记录的排序码为(46,79,56,38,40,80),对其进行归并排
序的过程中,第二趟排序后的结果是([38465679][40803)
36、假定一组记录的排序码为(46,79,56,38,40,80),对其进行快速排
序的第一次划分的结果是([3840]46[567980])。
37、一个结点的子树的(个数)称为该结点的度。度为(零)的结点称为叶结点
或终端结点。度不为(零)的结点称为分支结点或非终端结点。树中各结点度的(最
大值)称为树的度。
38、设Ki=Kj(l<=i<=n,l<=jv=n,joi)且在排序前的序列中Ri领先于Rj(i<j),若排序后的序
列中Ri仍领先于Rj,则这种排序方法是(稳定的),反之是(不稳定的)。
40、在堆排序的过程中,对任一分支结点进行调整运算的时间复杂度为(0(log2n)),整
个排序过程的时间复杂度为(0(nlog2n))。
41、在索引表中,每个索引项至少包含有(关键码值)域和(子表地址)域这两项。
42、假定一个线性表为(“abcd",“baabd”,”bce「,"ca”,“ahij",“bkwte”,“ccdt",“aayb”),若按照字
符串的第一个字母进行划分,使得同一个字母被划分在一个子表中,则得到的a,b,c三个子
表的长度分别为(3),(3),(2
43、对于包含50个关键码的3阶B-树,其最小高度为(4),最大高度为(5)。
44、从•棵B-树删除关键码的过程,若最终引起树根结点的合并,则新树比原树的高度(减
1)
45、假定要对长度n=100的线性表进行散列存储,并采用开散列法处理冲突,则对于长度
m=20的散列表,每个散列地址的同义词子表的长度平均为(5)。
46、在散列存储中,装载因子a乂称为装裁系数,若用m表示散列表的长度,n表示待散列
存储的元素的个数,则a等于(n/m)。
47、在有向图的邻接矩阵中,第i行中“1”的个数是第i个顶点的(出度),第i列中“1”
的个数是第i个顶点的(入度)。在无向图的邻接矩阵中,第i行(列)中“1”的个数是第
i个顶点的(度),矩阵中“1”的个数的一半是图中的(边数)。
48、在对m阶B-树中,每个非根结点的关键码数最少为(Fm/2-1-1)个,最多为(m-1)个,
其子树棵数最少为(Fm/2-i),最多为(m)。
判断题
数据元素是数据的最小单位(X)。
数据的逻辑结构是指各数据元素之间的逻辑关系,是用户按使用需要建立的N).
数据结构是指相互之间存在一种或多种关系的数据元素的全体(义)。
从逻辑关系上讲,数据结构主要分为两大类:线性结构和非线性结构川)。
线性表的逻辑顺序与物理顺序总是一致的(义)。
二维数组是其数组元素为线性表的线性表(X)。
每种数据结构都应具备三种基本运算:插入、删除、搜索(4)。
非空线性表中任意个数据元素都有且仅有一个直接前驱元素。(X)
空串与由空格组成的串没有区别。(X)
10、将T在S中首次出现的位置作为T在S中的位置的操作称为串的模式匹配。(4)
11、深度为h的非空二叉树的第h层最多有2h-l个结点(义)
12、完全二叉树就是满二叉树。(X)
13、已知一棵二叉树的前序序列和中序序列可以唯地构造出该二义树。(4)
14、带权连通图的最小生成树的权值之和一定小于它的其它生成树的权值之和。(4)
15、线性表的顺序存储结构的特点是逻辑关系上相邻的两个元素在物理位置上也相邻。
(4)
若有一个结点是二叉树中某个子树的中序遍历结果序列的最后一个结点,则它一定是该子树
的前序遍历结果序列的最后一个结点。(4)
17、任一棵二叉搜索树的平均搜索时间都小于用顺序搜索法搜索同样结点的顺序表的平均搜
索时间。(X)
18、最优二叉搜索树一定是平衡的二叉搜索树。(4)
19、AOE网是一种带权的无环连通图。3)
20、对于同一组待输入的关键码集合,虽然各关键码的输入次序不同,但得到的二义搜索树
都是相同的(X)。
21、二叉排序树可以是一棵空树W)
22、线性表中所有结点的类型必须相同。(4)
23、n个结点的有向图,若它有n(n—1)条边,则它一定是强连通的。(4)
24、任何无环的有向图,其结点都可以排在一个拓扑序列里。)
25、队列逻辑上是一个下端口和上端能增加又能减少的线性表(X)
26、二叉树是树的一种特殊情况(4)
27、用邻接矩阵存储一个图时,在不考虑压缩存储的情况下,所占用的存储空间大小只与图
中顶点个数有关,而与图的边数无关(<)。
28、邻接表只能用于有向图的存储,邻接矩阵对于有向图和无向图的存储都适用。(X)
29、连通分量是无向图中的极小连通子图。(义)
30、在AOE网络中一定只有一条关键路径。(X)
31、关键活动不按期完成就会影响整个工程的完成时间。(4)
32、平衡二义树的左右子树深度之差的绝对值不超过1。(<)
33、快速排序是对起泡排序的一种改进。(<)
34、直接选择排序稳定。(X)
35、堆排序占用的辅助空间很大。(X)
36、在散列法中采取开散列法来解决冲突时,其装载因子的取值淀在(0,1)之间。(X)
37、B-树是一种动态索引结构,它既适用于随机搜索,也适用于顺序搜索。(X)
38、在散列法中,一个可用散列函数必须保证绝对不产生冲突。(义)
39、任何一个关键活动延迟,那么整个工程将会延迟。2
40、任何一个关键活动提前完成,那么整个工程将会提前完成。(X)
四、运算应用题
1、在一个有n个元素的顺序表的第i个元素(1<i<n)之前插入一个新元素时,需要向后
移动多少个元素?
答案:需要向后移动n-i+1个元素
当一个栈的进栈序列为1234567时,可能的出栈序列有多少种?6457321是否是合理的出栈
序列?
答案:
可能的出栈序列有种,6457321不是合理的出栈序列。
1-114*13*12*11*10*9*8
——C,4=-*----------------------------=429
7+187*6*5*4*3*2*1
简单(直接)选择排序是一■种稳定的排序方法吗?试举例说明?
答案:是不稳定的排序方法。下面就是不稳定的例子。只要能举出反例即可。
{275275*512061}i=1
{061275*512275}i=2
{061275*512275}i=3
(061275*275512}
4、设有序顺序表为{10,20,30,40,50,60,70},采用折半搜索时,搜索成功的平均搜索长
度是多少?
答案:ASLsucc=(l*l+2*2+3*4)/7=17/7
5、在结点个数为n(n>l)的各棵树中,高度最小的树的高度是多少?它有多少个叶结点?多
少个分支结点?高度最大的树的高度是多少?它有多少个叶结点?多少个分支结点?
答案:结点个数为n时,高度最小的树的高度为1,有2层;它有n-1个叶结点,1个分支
结点;高度最大的树的高度为n-1,有n层;它有1个叶结点,n-1个分支结点。
6、一棵高度为h的满k义树有如下性质:第h层上的结点都是叶结点,其余各层上每个结
点都有k棵非空子树,如果按层次自顶向下,同一层自左向右,顺序从1开始对全部结点进
行编号,试问:
(1)各层的结点个数是多少?
(2)编号为i的结点的父结点(若存在)的编号是多少?
(3)编号为i的结点的第m个孩子结点(若存在)的编号是多少?
(4)编号为i的结点有右兄弟的条件是什么?其右兄弟结点的编号是多少?
(5)若结点个数为n,则高度h是n的什么函数关系?
答案:
(1)各层的结点个数是ki(i=0,l,2,....,h)
(2)编号为i的结点的父结点(若存在)的编号是L(i+k-2)/kJ
(3)编号为i的结点的第m个孩子结点(若存在)的编号是(i-l)*k+m+l
(4)当时有右兄弟,右兄弟的编号为i+1
(5)若结点个数为n,则高度h和n的关系为:h=logk(n*(k-1)+1)-1(n=0时h=-l)
7、写出下列中缀表达式的后缀形式:
(1)A*-B+C
(2)(A+B)*D+E/(F+A*D)+C
(3)A&&B||!(E>F){注:按C++的优先级)
(4)!(A&&!((B<C)||(C>D)))||(C<E)
答案:各中缀表达式的后缀形式如下:
(1)AB・*C+
(2)AB+D*EFAD*+/+C+
(3)AB&&EF>!||
(4)ABC<CD>||!&&!CE<||
8、画出下列广义表的图形表示和它们的存储表示:
(l)D(A(c),B(e),C(a,L(b,c,d)))
(2)Jl(J2(Jl,a,J3(J1)),J3(J1))
答案:广义表(1)的图形表示为:
广义表(1)的存储表示为:
广义表(2)的存储表示为:
D
9、题目:11、将下面的森林变换成二叉树(7分)。
答案:
10、将算术表达式((a+b)+c*(d+e)+f)*(g+h)转化为二义树。(7分)
答案:
11、根据所给有向图,写出个拓扑序列。(5分)
其中的一个拓扑序列为:VI,V2,V3,V4,V5,V6,V7
12、将给定的图简化为最小的生成树,要求从顶点1出发。(7分)
答案:
13、某子系统在通信联络中只可能出现8种字符,其出现的概率分别为0.05,0.29,0.07,
0.08,0.14,0.23,0.03,0.11试设计赫夫曼编码。
答案:
为方便起见,设各种字符的权值w={5,29,7,8,14,23,3,11}。因为n=8,所以要构造的赫夫曼树
概率为0.05的字符编码为:0110
概率为0.03的字符编码为:0111
概率为0.29的字符编码为:10
概率为0.14的字符编码为:110
概率为0.07的字符编码为:1110
概率为0.08的字符编码为:1111
14、已知•棵二义树的前序遍历的结果是ABECDFGHIJ,中序遍历的结果是EBCDAFHIGJ,
试画出这棵二叉树,并给出这棵二叉树的后序遍历序列。
答案:根据前序序列和中序序列能得到唯一的二叉树,所得二叉树如图:
这棵二叉树的后序遍历序列为:EDCBIHJGFAO
15、在结点个数为n(n>l)的各棵树中,高度最小的树的高度是多少?它有多少个叶结点?多
少个分支结点?高度最大的树的高度是多少?它有多少个叶结点?多少个分支结点?
答案:结点个数为n时,高度最小的树的高度为1,有2层;它有n-1个叶结点,1个分支
结点:高度最大的树的高度为n-1,有n层;它有1个叶结点,n-1个分支结点。
16、对于一个高度为h的AVL树,其最少结点数是多少?反之,对于一个有n个结点的
AVL树,其最大高度是多少?最小高度是多少?
答案:设高度为h(空树的高度为-1)的AVL树的最少结点为Nh,则Nh=Fh+3-l。
Fh是斐波那契数。又设AVL树有n个结点,则其最大高度不超过3/2*log2(n+l),
最小高度为Flog2(n+l)-]-lo
17、7-7设有序顺序表中的元素依次为017,094,154,170,275,503,509,512,553,612,677,
765,897,908o试画出对其进行折半搜索时的判定树,并计算搜索成功的平均搜索长度和搜
索不成功的平均搜索长度。
ASLSUCC=l/14(14-2*2+3*4+4*7)=45/14
ASLUNSUCC=1/15(3*1+4*14)=59/15
(1)这个工程最早可能在什么时间结束。
(2)求每个事件的最早开始时间Ve[i]和最迟开始时间Vl[i]o
(3)求每个活动的最早开始时间e()和最迟开始时间l()o
(4)确定哪些活动是关键活动。画出由所有关键活动构成的图,指出哪些活动加速可使整个
工程提前完成。
答案:按拓朴有序的顺序计算各个顶点的最早可能开始时间Ve和最迟允许开始时间VI,然
后再计算各个活动的最早可能开始时间e和最迟允许开始时间1,根据1-e是否等于0来确定
答案:
第一次排序:(076,129),256,(751,937,863,742,694,301,439)
第二次排序:076,129,256,(438,301,694,742),751,(863,937)
第三次排序:076,129,256,301,438,(694,742),75L(863,937)
第四次排序:076,129,256,301,438,694,742,751,(863,937)
第五次排序:076,129,256,301,438,694,742,751,863,937
20、设有150个记录要存储到散列表中,并利用线性探查法解决冲突,要求找到所需记录的
平均比较次数不超过2次。试问散列表需要设计多大?(设a是散列表的装载因子,则有
ASLsucc=(1+1/(1-a))/2)。
答案:已知要存储的记录数为n=150,查找成功的平均查找长度为ASLsuccW2,则有:
ASLsucc=1/2(1+1/(1-a))<2解得aW2/3,又有:a=n/m=150/m
两式联立得:150/mW2/3,解得:m2225.
所以散列表需要设计225个单位。
五、算法分析题
1、给出下列递归过程的执行结果
voidunknown(intw){
if(w){
unknown(w-1);
for(inti=1;i<=w;i++)cout«w«'
cout«endl;
}
)
调用语句为unknown(4)。
答案:
(1)1
22
333
4444
2、给出递归过程的执行结果
voidunknown(intn){
cout«n%10;
if(int(n/10))unknown(int(n/10));
}
调用语句为unknown(582)。
答案:285
3、给出递归过程的执行结果
intunknown(intm){
intvalue;
if(!m)value=3;
elsevalue=unknown(m-1)+5;
returnvalue;
}
执行语句为cout«unknown(3)»
答案:18
4、设有一个二维数组A[m][n],假设A[0][0]存放位置在644(10),A⑵[2]存放位置在676
(10),每个元素占一个空间,问A[3][3](10)存放在什么位置?脚注(10)表示用10进
制表小。
答案:设数组元素存放在起始地址为Loc(ij)的存储单元中。
因为:Loc(2,2)=Loc(0,0)+2*n+2=644+2*n+2=676
所以:n=(676-2-644)/2=15
所以:Loc(3,3)=Loc(0,0)+3*15+3=644+45+3=692
5、设单链表结构为structListNode{
intdata;
ListNode*link;
);
下面的程序是以单链表为存储结构,实现二路归并排序的算法,要求链表不另外占用存储空
间,排序过程中不移动结点中的元素,只改各链结点中的指针,排序后r仍指示结果链表的
第个结点。在初始状态下,所有待排序记录链接在一个以r为头指针的单链表中。例如,
在算法实现时,利用了一个队列做为辅助存储,存储各有序链表构成的归并段的链头指针。
初始时,各初始归并段为只有一个结点的有序链表。队列的数据类型为Queue,其可直接使
用的相关操作有
■置空队列操作:makeEmpty();
■将指针x加入到队列的队尾操作:EnQueue(ListNode*x);
■退出队头元素,其值由函数返回的操作:ListNode*DlQueue();
■判队列空否的函数,空则返回1,不空则返回0:intIsEmpty()。
解决方法提示:
>程序首先对待排序的单链表进行一次扫描,将它划分为若干有序的子链表,其表头指针
存放在一个指针队列中。
>当队列不空时,从队列中退出两个有序子链表,对它们进行二路归并,结果链表的表头指
针存放到队列中。
>如果队列中退出一个有序子链表后变成空队列,则算法结束。这个有序子链表即为所求。
在算法实现时有6处语句缺失,请阅读程序后补上。
(1)两路归并算法
voidmerge(ListNode*ha,ListNode*hb„ListNode*&he){
ListNode*pa,*pb,*pc;
if(ha_*data<=hb-*data){he=ha;pa=ha-*link;pb=hb;}
else{he=hb;pb=hb->link;pa=ha;}
pc=he;
while(pa&&pb)
if(pafdata<=pbfdata)
{pc->link=pa;pc=pa;
pa=p-flink__________________;
else
{peflink=pb;pc=pb;
pb=pb-»link
if(pa)pc->link=pa;
elsepc-*link=pb;
};
(2)归并排序主程序
voidmergesort(ListNode*r){
ListNode*s,t;QueueQ;
if(!r)return;
s=r;|Q.EsQueue(r)];
while(s){
t=sflink;
while(t!=0&&s~^data<=t->data){s=t;t=t->link;}
if(t){
s-*link=0;s=t;Q.EnQueue(s);
while(!Q.IsEmpty()){
r=Q.DlQueue();
if(Q.IsEmpty())break;
s=Q.DlQueue();
merge(r,s,t);|Q.EnQueue(t)|;
6、请读下列程序,该程序是在单链表中删除一个结点的算法,为空出的地方填上正确的语
句。(7分)
voiddemo2(LinkListhead,ListNode*p)
{//head是带头结点的单链表,删除P指向的结点
ListNode*q=head;
while(q&&q->next!=p)q=q->next;
if(q)Error(tc*pnotinhead^^);
q->next=p->next;
free(p);
)
已知•完全二叉树从根结点开始,自顶向下,同一层自左向右连续编号,根结点的编号为0,
阅读以卜程序请回答该程序所实现的功能:
template<classtype>
voidlinkedtosequent(Bintreenode<Type>*t,typea[],inti){
if(t!=Null){
a[]=t->getData();
linkedtosequent(t->getleftchild(),a,2*i+l);
linkedtosequent(t->getrightchild(),a,2*i+2);
}}
主程序调用方式:Iinkedtosequent(t.root,a,0);
答案:该程序的功能是:将用二叉链表表示的完全二叉树转换为二叉树的顺序(数组)表示。
8、设散列表为HT[13],散列函数为H(key)=key%13。用闭散列法解决冲突,对下列关键
码序列12,23,45,57,20,03,78,31,15,36造表。
(1)采用线性探查法寻找下•个空位,画出相应的散列表,并计算等概率下搜索成功的平均
搜索长度和搜索不成功的平均搜索长度。
(2)采用双散列法寻找下一个空位,再散列函数为RH(key)=(7*key)%10+1,寻找下一个
空位的公式为Hi=(Hi-1+RH(key))%13,Hl=H(key)。画出相应的散列表,并计算等概率
卜搜索成功的平均搜索长度。
答案:使用散列函数H(key尸keymod13有:
H(12)=12,H(23)=10,H(45)=6,H(57)=5,H(20)=7,H(03)=3,H(78)
=0,H(31)=5,H(15)=2,H(36)=10
利用线性探查法造表:
0123456789101112
78150357452031233612
1111114121
搜索成功的平均搜索长度为:
ASLsucc=l/10(1+1+1+1+1+1+4+1+2+1)=14/10
搜索不成功的平均搜索长度为:
ASLunsucc=l/13(2+1+3+2+1+5+4+3+2+1+5+4+3)=36/13
利用双散列法造表:
Hi=(Hi-1+RH(key))%13^Hi=H(key)
0123456789101112
78150357452031362312
1111113511
9、阅读下面程序,指出其算法的功能并求出其时间复杂度。
intPrime(intn){
inti=2,x=(int)sqrt(n);
while(i<=x){
if(n%i==O)break;
if
}
iRi>x)return1;
elsereturn0;
}
(2)intsum1(intn){
intp=l,s=O;
for(inti=l;i<=n;i++)
{p*=i;s+=p;}
returns;
答案:(1)程序功能是判断n是否是一个素数,若是则返回数值1,否则返回数值
0,该算法的时间复杂度为O(sqrt(n)).
(2)程序功能是计算Eni=li!,该算法的时间复杂度为O(n).
10、判断一个带表头结点的双向循环链表L是否对称相等的算法如下所示,请在算法的
处填入正确的语句。
intsymmetry(DbIListDL){
intsym=l;
DblNodep=DL->rLink,q=DL->lLink;
While(p!=q&&p->lLink==q)&&sym=1)
if(p->data=q->data){
p=p->rLink;
q=q->lLink;
)
elsesym=0;
returnsym;}
11、阅读下面程序,指出其算法的功能
#include"stack.h"
intBaseTrans(intN,intB)
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 组件对象模型
- 机场助航跑道如何选择风向标
- 施工员专业综合知识试题
- 华法林的临床应用课件
- 自驾用电解决方案(2篇)
- 酒店消防应急预案方案(2篇)
- 物流企业营销策划方案(2篇)
- 食堂餐厅设计方案(2篇)
- 2022年公务员考试珙县《行政职业能力测验》临考冲刺试卷含解析
- 《行政职业能力测验》河北省邯郸市丛台区2022年公务员考试高分冲刺试卷含解析
- 医疗质量持续改进记录本(全套模板)
- 报联商——有效沟通PPT课件
- 七巧板蒙板(A4直接打印)
- 二年级口算题大全(可直接打印)
- 毛概说课(毛概)(课堂PPT)
- 建设银行个人流水模板(精编)
- 2014新媒体平面模特大赛参赛报名表
- 外贸 发票 invoice 形式发票
- 220kV变电站初步设计
- 常见对讲机调频方法
- (word完整版)高中物理弹簧问题
评论
0/150
提交评论