理科数据结构复习题.docx
- 文档编号:18381396
- 上传时间:2023-08-16
- 格式:DOCX
- 页数:11
- 大小:27.87KB
理科数据结构复习题.docx
《理科数据结构复习题.docx》由会员分享,可在线阅读,更多相关《理科数据结构复习题.docx(11页珍藏版)》请在冰点文库上搜索。
理科数据结构复习题
数据结构试题
一、单选题
1、
在数据结构的讨论中把数据结构从逻辑上分为(C)
A内部结构与外部结构B静态结构与动态结构
C线性结构与非线性结构D紧凑结构与非紧凑结构。
2、采用线性链表表示一个向量时,要求占用的存储空间地址(D)
A必须是连续的B部分地址必须是连续的
C一定是不连续的D可连续可不连续
3、采用顺序搜索方法查找长度为n的顺序表时,等概率搜索成功的平均搜索长度为(D)。
AnBn/2C(n-1)/2D(n+1)/2
4、在一个单链表中,若q结点是p结点的前驱结点,若在q与p之间插入结点s,则执行(D)。
As→link=p→link;p→link=s;
Bp→link=s;s→link=q;
Cp→link=s→link;s→link=p;
Dq→link=s;s→link=p;
7、在数组A中,每一个数组元素A[i][j]占用3个存储字,行下标i从1到8,列下标j从1到10。
所有数组元素相继存放于一个连续的存储空间中,则存放该数组至少需要的存储字数是(C)。
A80B100C240D270
8、将一个递归算法改为对应的非递归算法时,通常需要使用(A)。
A栈B队列C循环队列D优先队列
10、在循环队列中用数组A[0..m-1]存放队列元素,其队头和队尾指针分别为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
13、下面程序段的时间复杂度为(C)
for(inti=0;i for(intj=0;j a[i][j]=i*j; AO(m2)BO(n2)CO(m*n)DO(m+n) 14、下面程序段的时间复杂度为(B) intf(unsignedintn){ if(n==0||n==1)return1; elsereturnn*f(n-1); } AO (1)BO(n)CO(n2)DO(n! ) 16、数据结构的定义为(D,S),其中D是(B)的集合。 S指D上的关系 A算法B数据元素C数据操作D逻辑结构 17、算法分析的目的是(A)。 A 找出数据结构的合理性 B 研究算法中输入和输出的关系 C 分析算法的效率以求改进 D 分析算法的易懂性和文档性 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)。 A c,b,aBb,a,cCc,a,bDa,c,b 25、栈和队列的共同特点是(C)。 A 都是先进后出B都是先进先出 C 只允许在端点处插入和删除D没有共同点 26、假定一个顺序存储的循环队列的队头和队尾指针分别为f和r,则判断队空的条件为(D). Af+1==rBr+1==fCf==0Df==r 27、当利用大小为n的数组顺序存储一个队列时,该队列的最大长度为(B) An-2Bn-1CnDn+1 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; 34、广义表A(a),则表尾为(C) AaB(())C空表D(a) 35、下列广义表是线性表的有(C) AE(a,(b,c))BE(a,E)CE(a,b)DE(a,L()) 38、对于任何一棵二叉树T,如果其终端结点数为n0,度为2的结点为n2.,则(A) An0=n2+1Bn2=n0+1Cn0=2n2+1Dn2=2n0+1 40、已知一个顺序存储的线性表,设每个结点需占m个存储单元,若第一个结点的地址为da1,则第I个结点的地址为( A )。 Ada1+(I-1)*m Bda1+I*m Cda1-I*m Dda1+(I+1)*m 42、对线性表进行折半搜索时,要求线性表必须(C) A以链接方式存储且结点按关键码有序排列B以数组方式存储 C以数组方式存储且结点按关键码有序排列D以链接方式存储 43、顺序搜索算法适合于存储结构为(B)的线性表。 A散列存储B顺序存储或链接存储 C压缩存储D索引存储 44、采用折半搜索算法搜索长度为n的有序表时,元素的平均搜索长度为(C) AO(n2)BO(nlog2n)CO(log2n)DO(n) 48、对包含n个元素的散列表进行搜索,平均搜索长度为(C) AO(log2n)BO(n)C不直接依赖于nD上述都不对 二、填空题() 1、 数据的逻辑结构被分为集合结构、线性结构、树形结构、图形结构四种 2、 数据的存储结构被分为顺序结构、链接结构、索引结构、散列结构四种 3、一种抽象数据类型包括(数据)和(操作)两个部分。 5、 栈、队列逻辑上都是(线性存储)结构。 6、线性结构反映结点间的逻辑关系是(一对一)的,图中的数据元素之间的关系是(多对多)的,树形结构中数据元素间的关系是(一对多)的。 7、栈中存取数据的原则( 后进先出),队列中存取数据的原则( 先进先出 ) 10、一维数组的逻辑结构是(线性结构),存储结构是(顺序存储表示)。 对于二维数组,有(行优先顺序)和(列优先顺序)两种不同的存储方式,对于一个二维数组A[m][n],若采用按行优先存放的方式,则任一数组元素A[i][j]相对于A[0][0]的地址为(n*i+j)。 11、向一个顺序栈插入一个元素时,首先使(栈顶指针)后移一个位置,然后把待插入元素(写)到这个位置上。 从一个顺序栈删除元素时,需要前移一位(栈顶指针)。 12、在一个循环队列Q中,判断队空的条件为(Q.front==Q.rear),判断队满的条件为((Q.rear+1)%MaxSize==q.front) 13、对于一棵具有n个结点的树,该树中所有结点的度数之和为(n-1)。 15、若对一棵二叉树从0开始进行结点编号,并按此编号把它顺序存储到一维数组中,即编号为0的结点存储到a[0]中,其余类推,则a[i]元素的左子女结点为(2*i+1),右子女结点为(2*i+2),双亲结点(i>=1 )为(「(i-1)/2┐). 16、在一个最大堆中,堆顶结点的值是所有结点中的(最大值),在一个最小堆中,堆顶结点的值是所有结点中的(最小值)。 17、已知具有n个元素的一维数组采用顺序存储结构,每个元素占k个存储单元,第一个元素的地址为LOC(a1),那么,LOC(ai)=LOC(a1)+(i-1)*k。 20、由一棵二叉树的前序序列和(中序序列)可唯一确定这棵二叉树。 21、以折半搜索方法搜索一个线性表时,此线性表必须是(顺序)存储的(有序)表。 25、在一个无向图中,所有顶点的度数之和等于所有边数的(2)倍。 在一个具有n个顶点的无向完全图中,包含有(n(n-1)/2)条边,在一个具有n个顶点的有向完全图中,包含有(n(n-1))条边。 26、对于一个具有n个顶点和e条边的连通图,其生成树中的顶点数和边数分别为(n)和(n-1)。 28、在插入和选择排序中,若初始数据基本正序,则选择(插入排序),若初始数据基本反序,则最好选择(选择排序)。 29、算法是对特定问题的求解步驟的一种描述,它是(指令)的有限序列,每一条(指令)表示一个或多个操作。 36、假定一组记录的排序码为(56,46,79,38,40,80),对其进行快速排序的第一次划分的结果是([40 4638]56[79 80])。 38、设Ki=Kj(1<=i<=n,1<=j<=n,j<>i)且在排序前的序列中Ri领先于Rj(i 44、从一棵B-树删除关键码的过程,若最终引起树根结点的合并,则新树比原树的高度(减1) 46、在散列存储中,装载因子α又称为装载系数,若用m表示散列表的长度,n表示待散列存储的元素的个数,则α等于(n/m)。 48、在对m阶B-树中,每个非根结点的关键码数最少为(「m/2┐-1)个,最多为(m-1)个,其子树棵数最少为(「m/2┐),最多为(m)。 三、判断题 1、数据元素是数据的最小单位(╳)。 2、 数据的逻辑结构是指各数据元素之间的逻辑关系,是用户按使用需要建立的(√). 3、数据结构是指相互之间存在一种或多种关系的数据元素的全体(╳)。 4、从逻辑关系上讲,数据结构主要分为两大类: 线性结构和非线性结构(√)。 5、线性表的逻辑顺序与物理顺序总是一致的(╳)。 6、每种数据结构都应具备三种基本运算: 插入、删除、搜索(√)。 7、非空线性表中任意一个数据元素都有且仅有一个直接前驱元素。 (╳) 12、完全二叉树就是满二叉树。 (╳) 13、已知一棵二叉树的前序序列和中序序列可以唯一地构造出该二叉树。 (√) 14、带权连通图的最小生成树的权值之和一定小于它的其它生成树的权值之和。 (√) 15、线性表的顺序存储结构的特点是逻辑关系上相邻的两个元素在物理位置上也相邻。 ( √ ) 19、AOE网是一种带权的无环连通图。 (√) 21、二叉排序树可以是一棵空树(√ ) 22、线性表中所有结点的类型必须相同。 (√ ) 24、任何无环的有向图,其结点都可以排在一个拓扑序列里。 (√ ) 25、队列逻辑上是一个下端口和上端能增加又能减少的线性表(╳) 27、用邻接矩阵存储一个图时,在不考虑压缩存储的情况下,所占用的存储空间大小只与图中顶点个数有关,而与图的边数无关(√)。 28、邻接表只能用于有向图的存储,邻接矩阵对于有向图和无向图的存储都适用。 (╳) 29、连通分量是无向图中的极小连通子图。 (╳) 30、在AOE网络中一定只有一条关键路径。 (╳) 31、关键活动不按期完成就会影响整个工程的完成时间。 (√) 32、平衡二叉树的左右子树深度之差的绝对值不超过1。 (√) 34、直接选择排序稳定。 ( ╳ ) 38、在散列法中,一个可用散列函数必须保证绝对不产生冲突。 (╳) 39、任何一个关键活动延迟,那么整个工程将会延迟。 (√) 40、任何一个关键活动提前完成,那么整个工程将会提前完成。 (╳) 四、运算应用题 (1)写出执行f30(a,b)的返回值,其中a和b分别为指向存储集合{2,4,5,7,9,12}和{2,4,5,7,9}的链表的头指针; (2)简述算法f30的功能; intf30(LinkListha,LinkListhb) { //LinkList是带有头结点的单链表 //ha和hb分别为指向存储两个有序整数集合的链表的头指针 LinkListpa,pb; pa=ha->next; pb=hb->next; while(pa&&pb&&pa->data==pb->data) { pa=pa->next; pb=pb->next; } if(pa==NULL&&pb==NULL)return1; elsereturn0; } 2、intAA(LNode*HL,ElemTypex) { intn=0; LNode*p=HL; while(p! =NULL) { if(p->data==x)n++; p=p->next; } returnn; } 编程题 1.设有一单链表L,结点结构为data|next,结点个数至少3个,试画出链表L的结构图,并编写算法判断该单链表L中的元素是否成等差关系,即: 设各元素值次为a1,a2,a3,…,an,判断ai+1-ai=ai-ai-1是否成立,其中i满足2<=i<=n-1.(8分) 2.设有一棵二叉树以二叉链表作为存储结构,结点结构为lchild|data|rchild,其中data域中存放一个字符,设计一个算法按前根遍历顺序仅打印出data域为数字的字符(即‘0’<=data<=‘9’)(6分) 1、 : intisrise(lklistL) {p=L->next;b=p->data–L->data; while(p->next! =NULL) {q=p->next; if(q->data–p->data! =b)return(0) elsep=q; } return (1); } 2.VoidNchar(bitreptrt) {if(t! =Null) {if(t->data>=’0’)&&(t->data<=‘9’)printf(“%d”,t->data); Nchar(t->lchild); Nchar(t->rchild); } }
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 理科 数据结构 复习题
![提示](https://static.bingdoc.com/images/bang_tan.gif)