数据结构考前复习资料.docx
- 文档编号:17407408
- 上传时间:2023-07-25
- 格式:DOCX
- 页数:68
- 大小:63.73KB
数据结构考前复习资料.docx
《数据结构考前复习资料.docx》由会员分享,可在线阅读,更多相关《数据结构考前复习资料.docx(68页珍藏版)》请在冰点文库上搜索。
数据结构考前复习资料
1.算法的计算量的大小称为计算的(B)。
A.效率B.复杂性C.现实性D.难度
2.算法的时间复杂度取决于(C)
A.问题的规模B.待处理数据的初态C.A和B
3.计算机算法指的是(C),它必须具备(B)这三个特性。
(1)A.计算方法B.排序方法C.解决问题的步骤序列
D.调度方法
(2)A.可执行性、可移植性、可扩充性B.可执行性、确定性、有穷
性
C.确定性、有穷性、稳定性D.易读性、稳定性、安全性
4.一个算法应该是(B)。
A.程序B.问题求解步骤的描述C.要满足五个基本特性
D.A和C.
5.下面关于算法说法错误的是(D)
A.算法最终必须由计算机程序实现
B.为解决某问题的算法同为该问题编写的程序含义是相同的
C.算法的可行性是指指令不能有二义性D.以上几个都是错误
的
6.下面说法错误的是(C)
(1)算法原地工作的含义是指不需要任何额外的辅助空间
(2)在相同的规模n下,复杂度O(n)的算法在时间上总是优于复杂度O
(2n)的算法
(3)所谓时间复杂度是指最坏情况下,估算算法执行时间的一个上界
(4)同一个算法,实现语言的级别越高,执行效率就越低
A.
(1)B.
(1),
(2)C.
(1),(4)D.(3)
7.从逻辑上可以把数据结构分为(C)两大类。
A.动态结构、静态结构B.顺序结构、链式结构
C.线性结构、非线性结构D.初等结构、构造型结构
8.以下与数据的存储结构无关的术语是(D)。
A.循环队列B.链表C.哈希表D.栈
9.以下数据结构中,哪一个是线性结构(D)?
A.广义表B.二叉树C.稀疏矩阵D.串
10.以下那一个术语与数据的存储结构无关?
(A)
A.栈B.哈希表C.线索树D.双向链
表
11.在下面的程序段中,对x的赋值语句的频度为(C)
FORi:
=1TOnDO
FORj:
=1TOnDO
x:
=x+1;
A.O(2n)B.O(n)C.O(n2)D.O(log2n)
13.以下哪个数据结构不是多型数据类型(D)
A.栈B.广义表C.有向图D.字符串
14.以下数据结构中,(A)是非线性数据结构
A.树B.字符串C.队D.栈
15.下列数据中,(C)是非线性数据结构。
A.栈B.队列C.完全二叉树D.堆
16.连续存储设计时,存储单元的地址(A)。
A.一定连续B.一定不连续C.不一定连续D.部分连续,部分不连
续
17.以下属于逻辑结构的是(C)。
A.顺序表B.哈希表C.有序表D.单链表
1.数据的物理结构包括(数据元素)的表示和(数据元素间关系)的表示
。
2.对于给定的n个元素,可以构造出的逻辑结构有(集合)(线性结构)
(树形结构)(网状结构)四种。
5.抽象数据类型的定义仅取决于它的一组(逻辑特性),而与(在计算机
内部如何表示和实现)无关
6.数据结构中评价算法的两个重要指标是(算法的时间复杂度和空间复杂
度)
8.一个算法具有5个特性:
(有穷性)、(确定性)、(可行性)
,有零个或多个输入、有一个或多个输出。
1.下述哪一条是顺序存储结构的优点?
(A)
A.存储密度大B.插入运算方便C.删除运算方便D.可方便地用于
各种逻辑结构的存储表示
2.下面关于线性表的叙述中,错误的是哪一个?
(B)
A.线性表采用顺序存储,必须占用一片连续的存储单元。
B.线性表采用顺序存储,便于进行插入和删除操作。
C.线性表采用链接存储,不必占用一片连续的存储单元。
D.线性表采用链接存储,便于插入和删除操作。
3.线性表是具有n个(C)的有限序列(n>0)。
A.表元素B.字符C.数据元素D.数据项E
.信息项
4.若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入
和删除运算,则利用(A)存储方式最节省时间。
A.顺序表B.双链表C.带头结点的双循环链表D.单
循环链表
5.某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第
一个元素,则采用(D)存储方式最节省运算时间。
A.单链表B.仅有头指针的单循环链表C.双链表D.仅
有尾指针的单循环链表
6.设一个链表最常用的操作是在末尾插入结点和删除尾结点,则选用(D
)最节省时间。
A.单链表B.单循环链表C.带尾指针的单循环链表D.带头结点的
双循环链表
7.若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一
个结点。
则采用(D)存储方式最节省运算时间。
A.单链表B.双链表C.单循环链表D.带头结点的双循
环链表
8.静态链表中指针表示的是(C).
A.内存地址B.数组下标C.下一元素地址D.左、右
孩子地址
9.链表不具有的特点是(B)
A.插入、删除不需要移动元素B.可随机访问任一元素
C.不必事先估计存储空间D.所需空间与线性长度成正比
13.若长度为n的线性表采用顺序存储结构,在其第i个位置插入一个新元
素的算法的时间复杂度为(C)(1<=i<=n+1)。
A.O(0)B.O
(1)C.O(n)D.O(n2)
14.对于顺序存储的线性表,访问结点和增加、删除结点的时间复杂度为
(C)。
A.O(n)O(n)B.O(n)O
(1)C.O
(1)O(n)D.
O
(1)O
(1)
15.线性表(a1,a2,…,an)以链接方式存储时,访问第i位置元素的时间
复杂性为(C)
A.O(i)B.O
(1)C.O(n)D.O(i-1)
24.在单链表指针为p的结点之后插入指针为s的结点,正确的操作是:
(
B)。
A.p->next=s;s->next=p->next;B.s->next=p->next;p->next=s;
C.p->next=s;p->next=s->next;D.p->next=s->next;p->next=s;
25.对于一个头指针为head的带头结点的单链表,判定该表为空表的条件
是(B)
A.head==NULLB.head→next==NULLC.head→next==headD.
head!
=NULL
1.链表中的头结点仅起到标识的作用。
(F)
2.顺序存储结构的主要缺点是不利于插入或删除操作。
(T)
3.线性表采用链表存储时,结点和结点内部的存储空间可以是不连续的。
(
T)
4.顺序存储方式插入和删除时效率太低,因此它不如链式存储方式好。
(
F)
5.对任何数据结构链式存储结构一定优于顺序存储结构。
(F)
6.顺序存储方式只能用于存储线性结构。
(F)
7.集合与线性表的区别在于是否按关键字排序。
(F)
8.所谓静态链表就是一直不发生变化的链表。
(F)
9.线性表的特点是每个元素都有一个前驱和一个后继。
(F)
10.取线性表的第i个元素的时间同i的大小有关.(F)
11.循环链表不是线性表.(F)
12.线性表只能用顺序存储结构实现。
(F)
3设单链表的结点结构为(data,next),next为指针域,已知指针px指向单
链表中data为x的结点,指针py指向data为y的新结点,若将结点y插入结
点x之后,则需要执行以下语句:
py->next=p->next;px->next=px->next;
4.在一个长度为n的顺序表中第i个元素(1<=i<=n)之前插入一个元素时
,需向后移动_n-i+1_______个元素。
6.对于一个具有n个结点的单链表,在已知的结点*p后插入一个新结点的
时间复杂度为__o
(1)______,在给定值为x的结点后插入一个新结点的时间
复杂度为__o(n)______。
7.根据线性表的链式存储结构中每一个结点包含的指针个数,将线性链表
分成_单链表_______和_多重链表______;而又根据指针的连接方式,链表
又可分成_动态链表_______和_静态链表_______。
8.在双向循环链表中,向p所指的结点之后插入指针f所指的结点,其操作
是f->next=p->next;f->prior=p;p->next->prior=f;p->next=f;。
10.链接存储的特点是利用__指针______来表示数据元素之间的逻辑关系
。
11.顺序存储结构是通过_物理上相邻_______表示元素之间的关系的;链式
存储结构是通过_指针_______表示元素之间的关系的。
12.对于双向链表,在两个结点之间插入一个新结点需修改的指针共
__4____个,单链表为___2____个。
13.循环单链表的最大优点是:
_从任意节点出发都可以访问到链表中的每
一个元素_______。
14.已知指针p指向单链表L中的某结点,则删除其后继结点的语句是:
_u=p->next;p->next=u->next;free(u);_______
15.带头结点的双循环链表L中只有一个元素结点的条件是:
_L->next-
>next==L______
16.在单链表L中,指针p所指结点有后继结点的条件是:
_p->next!
=null_
【合肥工业
1.对于栈操作数据的原则是(B)。
A.先进先出B.后进先出C.后进后出D.不分顺序
2.在作进栈运算时,应先判别栈是否(B),在作退栈运算时应先判别栈是否(A)。
当栈中元素为n个,作进栈运算时发生上溢,则说明该栈的最大容量为(B)。
为了增加内存空间的利用率和减少溢出的可能性,由两个栈共享一片连续的内存空间时,应将两栈的(D)分别设在这片内存空间的两端,这样,当(C)时,才产生上溢。
①,②:
A.空B.满C.上溢D.下溢
③:
A.n-1B.nC.n+1D.n/2
④:
A.长度B.深度C.栈顶D.栈底
⑤:
A.两个栈的栈顶同时到达栈空间的中心点.
B.其中一个栈的栈顶到达栈空间的中心点.
C.两个栈的栈顶在栈空间的某一位置相遇.
D.两个栈均不空,且一个栈的栈顶到达另一个栈的栈底.
3.一个栈的输入序列为123…n,若输出序列的第一个元素是n,输出第i(1<=i<=n)个元素是(B)。
A.不确定B.n-i+1C.iD.n-i
4.若一个栈的输入序列为1,2,3,…,n,输出序列的第一个元素是i,则第j个输出元素是(D)。
A.i-j-1B.i-jC.j-i+1D.不确定的
5.若已知一个栈的入栈序列是1,2,3,…,n,其输出序列为p1,p2,p3,…,pN,若pN是n,则pi是(D)。
A.iB.n-iC.n-i+1D.不确定
6.有六个元素6,5,4,3,2,1的顺序进栈,问下列哪一个不是合法的出栈序列?
(C)
A.543612B.453126C.346521D.234156
7.设栈的输入序列是1,2,3,4,则(D)不可能是其出栈序列。
A.1,2,4,3,B.2,1,3,4,C.1,4,3,2,
D.4,3,1,2,E.3,2,1,4,
8.一个栈的输入序列为12345,则下列序列中不可能是栈的输出序列的是(B)。
A.23415B.54132C.23145D.15432
9.设一个栈的输入序列是1,2,3,4,5,则下列序列中,是栈的合法输出序列的是(D)。
A.51234B.45132C.43125D.32154
10.某堆栈的输入序列为a,b,c,d,下面的四个序列中,不可能是它的输出序列的是(D)。
A.a,c,b,dB.b,c,d,aC.c,d,b,aD.d,c,a,b
11.设abcdef以所给的次序进栈,若在进栈操作时,允许退栈操作,则下面得不到的序列为(D)。
A.fedcbaB.bcafedC.dcefbaD.cabdef
12.设有三个元素X,Y,Z顺序进栈(进的过程中允许出栈),下列得不到的出栈排列是(C)。
A.XYZB.YZXC.ZXYD.ZYX
13.输入序列为ABC,可以变为CBA时,经过的栈操作为(B)【中山大学1999一、8(1分)】
A.push,pop,push,pop,push,popB.push,push,push,pop,pop,pop
C.push,push,pop,pop,push,popD.push,pop,push,push,pop,pop
14.若一个栈以向量V[1..n]存储,初始栈顶指针top为n+1,则下面x进栈的正确操作是(C)。
A.top:
=top+1;V[top]:
=xB.V[top]:
=x;top:
=top+1
C.top:
=top-1;V[top]:
=xD.V[top]:
=x;top:
=top-1
15.若栈采用顺序存储方式存储,现两栈共享空间V[1..m],top[i]代表第i个栈(i=1,2)栈顶,栈1的底在v[1],栈2的底在V[m],则栈满的条件是(B)。
A.|top[2]-top[1]|=0B.top[1]+1=top[2]C.top[1]+top[2]=mD.top[1]=top[2]
16.栈在(D)中应用。
A.递归调用B.子程序调用C.表达式求值D.A,B,C
17.一个递归算法必须包括(B)。
A.递归部分B.终止条件和递归部分C.迭代部分D.终止条件和迭代部分
18.执行完下列语句段后,i值为:
(B)
intf(intx)
{return((x>0)?
x*f(x-1):
2);}
inti;
i=f(f
(1));
A.2B.4C.8D.无限递归
19.表达式a*(b+c)-d的后缀表达式是(B)。
A.abcd*+-B.abc+*d-C.abc*+d-D.-+*abcd
20.表达式3*2^(4+2*2-6*3)-5求值过程中当扫描到6时,对象栈和算符栈为(D),其中^为乘幂。
A.3,2,4,1,1;(*^(+*-B.3,2,8;(*^-C.3,2,4,2,2;(*^(-D.3,2,8;(*^(-
21.设计一个判别表达式中左,右括号是否配对出现的算法,采用(D)数据结构最佳。
A.线性表的顺序存储结构B.队列C.线性表的链式存储结构D.栈
22.用链接方式存储的队列,在进行删除运算时(D)。
A.仅修改头指针B.仅修改尾指针C.头、尾指针都要修改D.头、尾指针可能都要修改
23.用不带头结点的单链表存储队列时,其队头指针指向队头结点,其队尾指针指向队尾结点,则在进行删除操作时(D)。
A.仅修改队头指针B.仅修改队尾指针
C.队头、队尾指针都要修改D.队头,队尾指针都可能要修改
24.递归过程或函数调用时,处理参数及返回地址,要用一种称为(C)的数据结构。
A.队列B.多维数组C.栈D.线性表
25.假设以数组A[m]存放循环队列的元素,其头尾指针分别为front和rear,则当前队列中的元素个数为(A)。
A.(rear-front+m)%mB.rear-front+1C.(front-rear+m)%mD.(rear-front)%m
26.循环队列A[0..m-1]存放其元素值,用front和rear分别表示队头和队尾,则当前队列中的元素数是(A)。
A.(rear-front+m)%mB.rear-front+1C.rear-front-1D.rear-front
27.循环队列存储在数组A[0..m]中,则入队时的操作为(D)。
A.rear=rear+1B.rear=(rear+1)mod(m-1)
C.rear=(rear+1)modmD.rear=(rear+1)mod(m+1)
28.若用一个大小为6的数组来实现循环队列,且当前rear和front的值分别为0和3,当从队列中删除一个元素,再加入两个元素后,rear和front的值分别为多少?
(B)
A.1和5B.2和4C.4和2D.5和1
29.已知输入序列为abcd经过输出受限的双向队列后能得到的输出序列有(BD)。
A.dacbB.cadbC.dbcaD.bdacE.以上答案都不对
30.若以1234作为双端队列的输入序列,则既不能由输入受限的双端队列得到,也不能由输出受限的双端队列得到的输出序列是(C)。
A.1234B.4132C.4231D.4213
31.最大容量为n的循环队列,队尾指针是rear,队头是front,则队空的条件是(B)。
A.(rear+1)MODn=frontB.rear=front
C.rear+1=frontD.(rear-l)MODn=front
32.栈和队列的共同点是(C)。
A.都是先进先出B.都是先进后出
C.只允许在端点处插入和删除元素D.没有共同点
33.栈的特点是(B),队列的特点是(A),栈和队列都是(C)。
若进栈序列为1,2,3,4则(C)不可能是一个出栈序列(不一定全部进栈后再出栈);若进队列的序列为1,2,3,4则(F)是一个出队列序列。
①,②:
A.先进先出B.后进先出C.进优于出D.出优于进
③:
A.顺序存储的线性结构B.链式存储的线性结构
C.限制存取点的线性结构D.限制存取点的非线性结构
④,⑤:
A.3,2,1,4B.3,2,4,1C.4,2,3,1D.4,3,2,1F.1,2,3,4G.1,3,2,4
34.栈和队都是(C)
A.顺序存储的线性结构B.链式存储的非线性结构
C.限制存取点的线性结构D.限制存取点的非线性结构
35.设栈S和队列Q的初始状态为空,元素e1,e2,e3,e4,e5和e6依次通过栈S,一个元素出栈后即进队列Q,若6个元素出队的序列是e2,e4,e3,e6,e5,e1则栈S的容量至少应该是(C)。
A.6B.4C.3D.2
36.用单链表表示的链式队列的队头在链表的(A)位置。
A.链头B.链尾C.链中
37.依次读入数据元素序列{a,b,c,d,e,f,g}进栈,每进一个元素,机器可要求下一个元素进栈或弹栈,如此进行,则栈空时弹出的元素构成的序列是以下哪些序列?
【AD】
A.{d,e,c,f,b,g,a}B.{f,e,g,d,a,c,b}
C.{e,f,d,g,b,c,a}D.{c,d,b,e,f,a,g}
1.消除递归不一定需要使用栈,此说法(T)
2.栈是实现过程和函数等子程序所必需的结构。
(T)
3.两个栈共用静态存储空间,对头使用也存在空间溢出问题。
(T)
4.两个栈共享一片连续内存空间时,为提高内存利用率,减少溢出机会,应把两个栈的栈底分别设在这片内存空间的两端。
(T)
5.即使对不含相同元素的同一输入序列进行两组不同的合法的入栈和出栈组合操作,所得的输出序列也一定相同。
(F)
6.有n个数顺序(依次)进栈,出栈序列有Cn种,Cn=[1/(n+1)]*(2n)!
/[(n!
)*(n!
)]。
(T)
7.栈与队列是一种特殊操作的线性表。
(T)
8.若输入序列为1,2,3,4,5,6,则通过一个栈可以输出序列3,2,5,6,4,1.(T)
9.栈和队列都是限制存取点的线性结构。
(T)
10.若输入序列为1,2,3,4,5,6,则通过一个栈可以输出序列1,5,4,6,2,3。
(F)
11.任何一个递归过程都可以转换成非递归过程。
( T )
12.只有那种使用了局部变量的递归过程在转换成非递归过程时才必须使用栈。
(F )
13.队列是一种插入与删除操作分别在表的两端进行的线性表,是一种先进后出型结构。
(F)
14.通常使用队列来处理函数或过程的调用。
(F)
15.队列逻辑上是一个下端和上端既能增加又能减少的线性表。
(T)
16.循环队列通常用指针来实现队列的头尾相接。
(F)
17.循环队列也存在空间溢出问题。
(T)
18.队列和栈都是运算受限的线性表,只允许在表的两端进行运算。
(F)
19.栈和队列都是线性表,只是在插入和删除时受到了一些限制。
(T)
20.栈和队列的存储方式,既可以是顺序方式,又可以是链式方式。
(T)
三填空题
1.栈是_或限定仅在表尾进行插入和删除操作______的线性表,其运算遵循__后进先出_____的原则。
2._栈______是限定仅在表尾进行插入或删除操作的线性表。
3.一个栈的输入序列是:
1,2,3则不可能的栈输出序列是_312______。
5.当两个栈共享一存储区时,栈利用一维数组stack(1,n)表示,两栈顶指针为top[1]与top[2],则当栈1空时,top[1]为__0_____,栈2空时,top[2]为__n+1_____,栈满时为__top[1]+1=top[2]_____。
6.两个栈共享空间时栈满的条件___两栈顶指针值相减的绝对值为1(或两栈顶指针相邻)____。
7.在作进栈运算时应先判别栈是否_满_;在作退栈运算时应先判别栈是否_空_;当栈中元素为n个,作进栈运算时发生上溢,则说明该栈的最大容量为_n_。
为了增加内存空间的利用率和减少溢出的可能性,由两个栈共享一片连续的空间时,应将两栈的_栈底_分别设在内存空间的两端,这样只有当_两栈顶指针相邻_时才产生溢出。
8.多个栈共存时,最好用__链式存储结构_____作为存储结构。
9.用S表示入栈操作,X表示出栈操作,若元素入栈的顺序为1234,为了得到1342出栈顺序,相应的S和X的操作串为__S×SS×S××_____。
10.顺序栈用data[1..n]存储数据,栈顶指针是top,则值为x的元素入栈的操作是___data[++top]=x;____。
11.表达式23+((12*3-2)/4+34*5/7)+108/9的后缀表达式是___23.12.3*2-4/34.5*7/++108.9/+_(注:
表达式中的点(.)表示将数隔开,如23.12.3是三个数)___。
12.循环队列的引入,目的是为了克服__假溢出时大量移动数据元素_____。
14.___队列_____又称作先
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 考前 复习资料