数据结构题库.docx
- 文档编号:16040011
- 上传时间:2023-07-10
- 格式:DOCX
- 页数:37
- 大小:123.20KB
数据结构题库.docx
《数据结构题库.docx》由会员分享,可在线阅读,更多相关《数据结构题库.docx(37页珍藏版)》请在冰点文库上搜索。
数据结构题库
第一章绪论
一,选择题
1.组成数据的基本单位是(C)
A.数据项B.数据类型C.数据元素D.数据变量
2.数据结构是研究数据的(C)以及它们之间的相互关系。
A.理想结构,物理结构B.理想结构,抽象结构
C.物理结构,逻辑结构D.抽象结构,逻辑结构
3.算法分析的两个主要方面是(D)
A.正确性和简单性B.可读性和文档性
C.数据复杂性和程序复杂性D.时间复杂度和空间复杂度
4.算法分析的目的是(C)。
A.找出数据结构的合理性B.研究算法中的输入和输出的关系
C.分析算法的效率以求改进D.分析算法的易懂性和文档性
5.算法的时间复杂度取决于(C)
A.问题的规模B.待处理数据的初态C.A和BD.以上都不是
6.一个算法应该是(B)。
A.程序B.问题求解步骤的描述C.要满足五个基本特性D.A和C.
7.下面关于算法说法错误的是(D)
A.算法最终必须由计算机程序实现
B.为解决某问题的算法同为该问题编写的程序含义是相同的
C.算法的可行性是指指令不能有二义性D.以上几个都是错误的
8.从逻辑上可以把数据结构分为(C)两大类。
A.动态结构、静态结构B.顺序结构、链式结构
C.线性结构、非线性结构D.初等结构、构造型结构
9.程序段for(i=n-1;i>=1;i--)
for(j=1;j<=i;j++)
if(A[j]>A[j+1])
A[j]与A[j+1]对换;
其中n为正整数,则最后一行的语句频度在最坏情况下是(D)
A.O(n)B.O(nlogn)C..O(n3)D.O(n2)
10.连续存储设计时,存储单元的地址(A)。
A.一定连续B.一定不连续C.不一定连续D.部分连续,部分不连续
二,判断题
1.数据结构的抽象操作的定义与具体实现有关。
(×)
2.数据结构是数据对象与对象中数据元素之间关系的集合。
(√)
3.在顺序存储结构中,有时也存储数据结构中元素之间的关系。
(×)
4.数据的逻辑结构是指各数据元素之间的逻辑关系,是用户按使用的需要建立的。
(√)
5.算法和程序原则上没有区别,在讨论数据结构是两者是通用的。
(×)
6.同一数据逻辑结构中的所有数据元素都具有相同的特性是指数据元素所包含的数据项的个数都相等。
(×)
7.数据的逻辑结构与数据元素本身的内容和形式无关。
(√)
8.算法的优劣与算法描述语言无关,但与所用计算机有关。
(×)
9.健壮的算法不会因非法的输入数据而出现莫名其妙的状态。
(√)
10.算法可以用不同的语言描述,如果用C语言或PASCAL语言等高级语言来描述,则算法实际上就是程序了。
(×)
三,填空
1.数据的物理结构包括数据元素的表示和数据元素间关系的表示。
2.对于给定的n个元素,可以构造出的逻辑结构有,,__图状结构或网状结构_四种。
3.一个数据结构在计算机中称为存储结构。
4.抽象数据类型的定义仅取决于它的一组_实现_无关,即不论其内部结构如何变化,只要它的_数学特性_不变,都不影响其外部使用。
5.线性结构中元素之间存在关系,树形结构中元素之间存在关系,图形结构中元素之间存在6.一个算法有5个特性:
,有零个或多个输入、有一个或多个输出。
7.已知如下程序段
for(i=n;i<=1;i++){语句1}
{
x:
=x+1;
for(j=n;j<=i;j++)
y:
=y+1;
}
语句1执行的频度为;语句2执行的频度为3执行的频度为4执行的频度为。
8.在下面的程序段中,对x的赋值语句的频度为__O(n3)___(表示为n的函数)//1+(1+2++(1+2+3)+…+(1+2+…+n)=n(n+1)(n+2)/6
for(i=1;i<=n;i++)
for(j=1;j<=i;j++)
for(k=1;k<=j;j++)
x=x+delta;
9.计算机执行下面的语句时,语句s的执行次数为_(n+3)(n-2)/2______。
for(i=l;i for(j=n;j>=i;j--) s; 10.下面程序段的时间复杂度为___O(n)_____。 (n>1) sum=1; for(i=0;sum 四,应用题 1.1.什么是数据? 它与信息是什么关系? 信息就是消息。 信息的特征为: 可识别、可存储、可变换、可处理、可传递、可再生、可压缩、可利用、可共享。 什么是数据? 数据(data)是信息的载体,是描述客观事物的数、字符、以及所有能输入到计算机中并被计算机程序识别和处理的符号的集合。 在计算机中,信息必须以数据的形式出现。 {语句2}{语句3}{语句4} 什么是数据结构? 数据结构是研究什么内容的学科? 有关数据结构的讨论涉及哪三方面? 2. 数据结构是指数据以及相互之间的关系。 记为: 数据结构={D,R}。 其中,D是某一数据对象,R是该对象中所有数据成员之间的关系的有限集合。 数据结构是一门研究在非数值计算的程序设计问题中,计算机的操作对象及对象间的关系和施加于对象的操作等的学科。 有关数据结构的讨论一般涉及以下三方面的内容: (1)数据成员以及它们相互之间的逻辑关系,也称为数据的逻辑结构,简称为数据结构; (2)数据成员及其关系在计算机存储器内的存储表示,也称为数据的物理结构,简称为存储结构; (3)施加于该数据结构上的操作。 数据的逻辑结构是从逻辑关系上描述数据,它与数据的存储不是一码事,是与计算机存储无关的。 因此,数据的逻辑结构可以看作是从具体问题中抽象出来的数据模型,是数据的应用视图。 数据的存储结构是逻辑数据结构在计算机存储器中的实现(亦称为映像),它是依赖于计算机的,是数据的物理视图。 数据的操作是定义于数据逻辑结构上的一组运算,每种数据结构都有一个运算的集合。 例如搜索、插入、删除、更新、排序等。 3.评价一个好的算法,从哪几方面考虑? 评价好的算法有四个方面。 一是算法的正确性;二是算法的易读性;三是算法的健壮性;四是算法的时空效率(运行)。 4.若将数据结构定义为一个二元组(D,R),说明符号D,R应分别表示什么? D是数据元素的有限集合,R是D上数据元素之间关系的有限集合。 5.解释算法与程序的区别? 算法是为了解决某类问题而规定的一个有限长的操作序列。 一个算法必须满足以下五个重要特性: 有穷性确定性可行性有输入有输出 算法与程序的联系和区别: (1)算法代表了对问题的解,而程序则是算法在计算机上的特定的实现。 一个程序不一定满足有穷性。 例如,操作系统,只要整个系统不遭破坏,它将永远不会停止。 因此,操作系统不是一个算法。 (2)程序中的指令必须是机器可执行的,而算法中的指令则无此限制。 (3)算法是面向功能的,通常用面向过程的方式描述;程序可以用面向对象方式搭建它的框架。 (4)算法与数据结构是相辅相承的: 解决某一特定类型问题的算法可以选定不同的数据结构,而且选择恰当与否直接影响算法的效率。 反之,一种数据结构的优劣由各种算法的执行来体现。 6.有下列几种用二元组表示的数据结构,画出它们分别对应的逻辑图形表示,并指出它们分别属于何种结构。 (1)A=(K,R),其中: K={a,b,c,d,e,f,g} R={r} r={〈a,b〉,〈b,c〉,〈c,d〉,〈d,e〉,〈e,f〉,〈f,g〉} (2)B=(K,R),其中: K={a,b,c,d,e,f,g,h} R={r} r={〈d,b〉,〈d,g〉,〈d,a〉,〈b,c〉,〈g,e〉,〈g,h〉,〈a,f〉} (3)C=(K,R),其中: K={1,2,3,4,5,6} R={r} r={(1,2),(2,3),(2,4),(3,4),(3,5),(3,6),(4,5),(4,6)}这里的圆括号对表示两结点是双向的。 (1)A 对应逻辑图形如下,它是一种线性结构。 (2)B 对应逻辑图形如下,它是一种树形结构。 (3)C 对应逻辑图形如下,它是一种图形结构。 7.分析以下程序段的时间复杂度。 (1) a=0;b=1;① for(i=2;i〈=n;i++)② { s=a+b;③ b=a;④ a=S;⑤ } (2) inti,j,k; for(i=0;i〈n;i++〉① for(j=0;j〈n;j++〉② { c[i][j]=0;③ for(k=0;k〈n;k++〉④ c[i][j]=c[i][j]+a[i][k]+b[k][j];⑤ } (1)解: 语句①的频度是2; 语句②的频度是n; 语句③的频度是n-1; 语句④的频度是n-1; 语句⑤的频度是n-1; 故,该程序段的时间复杂度T(n)=2+n+3*(n-1)=4n-1=O(n)。 (2)解: 语句①的频度为n+1; 语句②作为语句①循环体内的语句应该执行n次,但语句②本身要执行n+1次,故语句②的频度是n(n+1); 同理可得语句③、④和⑤的频度分别是n2,n2(n+1)和n3。 该程序段所有语句的频度之和为: T(n)=2n3+3n2+2n+1 其复杂度为O(n3)。 8.求下列算法段的语句频度及时间复杂度 (1) for(i=1;i<=n;i++) for(j=1;j<=i;j++) x=x+1; (2) for(i=1;i<=n;i++) for(j=1;j<=i;j++) for(k=1;k<=j;k++) x=i+j-k; (1)分析: 该算法为一个二重循环,执行次数为内、外循环次数相乘,但内循环次数不固 2定,与外循环有关,因此,时间频度T(n)=1+2+3+…+n=n*(n+1)/2。 有1/4≤T(n)/n≤1, 22故它的时间复杂度为O(n),即T(n)与n数量级相同。 (2)分析算法规律可知时间频度T(n)=1+(1+2)+(1+2+3)+...+(1+2+3+…+n)。 由于有1/6≤ 33T(n)/n≤1,故时间复杂度为O(n) 第二章线性表 一,选择 1.在一个以h为头的单循环链中,p指针指向链尾的条件是(A) A.p->next=hB.p->next=NILC.p->next->next=hD.p->data=-1 2.下面关于线性表的叙述中,错误的是哪一个? (B) A.线性表采用顺序存储,必须占用一片连续的存储单元。 B.线性表采用顺序存储,便于进行插入和删除操作。 C.线性表采用链接存储,不必占用一片连续的存储单元。 D.线性表采用链接存储,便于插入和删除操作。 3.线性表是具有n个(C)的有限序列(n>0)。 A.表元素B.字符C.数据元素D.数据项 4.若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算,则利用(A)存储方式最节省时间。 A.顺序表B.双链表C.带头结点的双循环链表D.单循环链表 5.某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素,则采用(D)存储方式最节省运算时间。 A.单链表B.仅有头指针的单循环链表 C.双链表D.仅有尾指针的单循环链表 6.设一个链表最常用的操作是在末尾插入结点和删除尾结点,则选用(D)最节省时间。 A.单链表B.单循环链表C.带尾指针的单循环链表D.带头结点的双循环链表 7.在带有头结点的单链中插入一个新结点时不可能修改(A)。 A.头指针B.头结点指针域C.开始结点指针域D.其它结点指针域 8.双向链表中有两个指针域,llink和rlink,分别指向前驱及后继,设p指向链表中的一个结点,q指向一待插入结点,现要求在p前插入q,则正确的插入为(D)。 A.p->llink=q;q->rlink=p;p->llink->rlink=q;q->llink=p->llink; B.q->llink=p->llink;p->llink->rlink=q;q->rlink=p;p->llink=q->rlink; C.q->rlink=p;p->rlink=q;p->llink->rlink=q;q->rlink=p; D.p->llink->rlink=q;q->rlink=p;q->llink=p->llink;p->llink=q; 9.对于一个头指针为head的带头结点的单链表,判定该表为空表的条件是(B)。 A.head==NULLB.head→next==NULLC.head→next==headD.head! =NULL 10.在顺序表中查找第i个元素的时间效率最高的算法时间复杂度是(A)。 A.O (1)B.O()C.O(log2n)D.O(n) 11.最好的情况下,在顺序表中按值查找一个元素的算法时间复杂度是(D)。 A.O(n)B.O(n)C.O(log2n)D.O (1) 12.若长度为n的线性表采用顺序存储结构,在其第i个位置插入一个新元素的算法的时间复杂度为(C)(1<=i<=n+1)。 2A.O(0)B.O (1)C.O(n)D.O(n) 13.对于顺序存储的线性表,访问结点和增加、删除结点的时间复杂度为(C)。 A.O(n)O(n)B.O(n)O (1)C.O (1)O(n)D.O (1)O (1) 14.线性表(a1,a2,…,an)以链接方式存储时,访问第i位置元素的时间复杂性为(C)。 A.O(i)B.O (1)C.O(n)D.O(i-1) 15.非空的循环单链表head的尾结点p满足(A)。 A.p->link=headB.p->link=NILC.p=NILD.p=head 二,判断 1.链表中的头结点仅起到标识的作用。 (×) 2.线性表采用链表存储时,结点和结点内部的存储空间可以是不连续的。 (√) 3.顺序存储方式插入和删除时效率太低,因此它不如链式存储方式好。 (×) 4.顺序存储方式只能用于存储线性结构。 (×) 5.线性表的链接存储,表中元素的逻辑顺序与物理顺序一定相同。 (×) 6.线性表的特点是每个元素都有一个前驱和一个后继。 (×) 7.取线性表的第i个元素的时间同i的大小有关。 (×) 8.循环链表不是线性表。 (×) 9.线性表就是顺序存储的表。 (×) 10.顺序存储方式的优点是存储密度大,且插入、删除运算效率高。 (×) 三,填空 1.当线性表的元素总数基本稳定,且很少进行插入和删除操作,但要求以最快的速度存取线性表中的元素时,应采用存储结构。 2.线性表L=(a1,a2,…,an)用数组表示,假定删除表中任一元素的概率相同,则删除一个元素平均需要移动元素的个数是(n-1)/2。 3.在一个长度为n的顺序表中第i个元素(1<=i<=n)之前插入一个元素时,需向后移动n-i+1个元素。 4.对于一个具有n个结点的单链表,在已知的结点*p后插入一个新结点的时间复杂度为___O (1)_____,在给定值为x的结点后插入一个新结点的时间复杂度为__O(n)__。 5.在双向循环链表中,向p所指的结点之后插入指针f所指的结点,其操作是6.在双向链表结构中,若要求在p指针所指的结点之前插入指针为s所指的结点,则需执行下列语句: s->next=p;s->prior==s; 7.顺序存储结构通过物理上相邻表示元素之间的关系;链式存储结构通过指针表示元素之间的关系。 8.对于双向链表,在两个结点之间插入一个新结点需修改的指针共4个,单链表为2个。 9.已知指针p指向单链表L中的某结点,则删除其后继结点的语句是: 时间复杂度是O (1);。 10.带头结点的双循环链表L中只有一个元素结点的条件是L->next->next==L。 四,算法设计 1LNode*Locate(LinkListL,intx)//链表上的元素查找,返回指针 { for(p=l->next;p&&p->data! =x;p=p->next); returnp; }//Locate intLength(LinkListL)//求链表的长度 { for(k=0,p=L;p->next;p=p->next,k++); returnk; }//Length 为(avoidreverse(SqList&A)//顺序表的就地逆置 { for(i=0,j=A.length-1;i A.elem[i]<->A.elem[j]; }//reverse voidLinkList_reverse(Linklist&L)//链表的就地逆置;为简化算法,假设表长大于2{ p=L->next;q=p->next;s=q->next;p->next=NULL; while(s->next) { q->next=p;p=q; q=s;s=s->next;//把L的元素逐个插入新表表头 } q->next=p;s->next=q;L->next=s; }//LinkList_reverse 分析: 本算法的思想是,逐个地把L的当前元素q插入新的链表头部,p为新表表头. 性表C的算法,即使得 线性表A,B和C均以单链表作存储结构,且C表利用A表和B表中的结点空间构成。 voidmerge1(LinkList&A,LinkList&B,LinkList&C) //把链表A和B合并为C,A和B的元素间隔排列,且使用原存储空间 { p=A->next;q=B->next;C=A; while(p&&q) { s=p->next;p->next=q;//将B的元素插入 if(s) { t=q->next;q->next=s;//如A非空,将A的元素插入 } p=s;q=t; }//while }//merge1 第三章栈和队列 一,选择 1.对于栈操作数据的原则是(B)。 A.先进先出B.后进先出C.后进后出D.不分顺序 2.已知输入序列为abcd经过输出受限的双向队列后能得到的输出序列有(B)。 A.dacbB.cadbC.dbcaD.badc 3.最大容量为n的循环队列,队尾指针是rear,队头是front,则队空的条件是(B)。 A.(rear+1)MODn=frontB.rear=front C.rear+1=frontD.(rear-l)MODn=front 4当利用大小为n的数组顺序存储一个栈时,假定用top==n表示栈空,则向这个栈插入一个元素时首先应执行语句修改top指针。 (B) A.top++B.top--C.top=0D.top 5.若已知一个栈的入栈序列是1,2,3,…,n,其输出序列为p1,p2,p3,…,pN,若pN是n,则pi是(D)。 A.iB.n-iC.n-i+1D.不确定 6.一个递归算法必须包括(B)。 A.递归部分B.终止条件和递归部分C.迭代部分D.终止条件和迭代部分 7.执行完下列语句段后,i值为: (B) intf(intx) {return((x>0)? x*f(x-1): 2);} inti; i=f(f (1)); A.2B.4C.8D.无限递归 8.设栈S和队列Q的初始状态为空,元素e1,e2,e3,e4,e5和e6依次通过栈S,一个元素出栈后即进队列Q,若6个元素出队的序列是e2,e4,e3,e6,e5,e1则栈S的容量至少应该是(C)。 A.6B.4C.3D.2 9.栈和队列的共同点是(C)。 A.都是先进先出B.都是先进后出 C.只允许在端点处插入和删除元素D.没有共同点 10.设计一个判别表达式中左,右括号是否配对出现的算法,采用(D)数据结构最佳。 A.线性表的顺序存储结构B.队列C.线性表的链式存储结构D.栈 11.用不带头结点的单链表存储队列时,其队头指针指向队头结点,其队尾指针指向队尾结点,则在进行删除操作时(D)。 A.仅修改队头指针B.仅修改队尾指针 C.队头、队尾指针都要修改D.队头,队尾指针都可能要修改 12.递归过程或函数调用时,处理参数及返回地址,要用一种称为(C)的数据结构。 A.队列B.多维数组C.栈D.线性表 13.假设以数组A[m]存放循环队列的元素,其头尾指针分别为front和rear,则当前队列中的元素个数为(A)。 A.(rear-front+m)%mB.rear-front+1C.(front-rear+m)%mD.(rear-front)%m 14.循环队列存储在数组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) 15.若用一个大小为6的数组来实现循环队列,且当前rear和front的值分别为0和3,当从队列中删除一个元素,再加入两个元素后,rear和front的值分别为多少? (B) A.1和5B.2和4C.4和2D.5和1 二,判断 1. 2. 3. 4.任何一个递归过程都可以转换成非递归过程。 (√)只有那种使用了局部变量的递归过程在转换成非递归过程时才必须使用栈。 (×)队列逻辑上是一个下端和上端既能增加又能减少的线性表。 (√)循环队列也存在空间溢出问题。 (√)循环队列只是一个大小为maxsize的数组空间有限自然存在溢出问题 5.栈和队列的存储方式,既可以是顺序方式,又可以是链式方式。 (√) 三,填空 1.栈是限定仅在表尾进行插入或删除操作的线性表。 3.中缀表达式3*(x+2)-5所对应的后缀表达式为;后缀表达式“45*32+-”的值为15。 4.顺序栈用data[1..n]存储数据,栈顶指针是top,则值为x的元素入栈的操作是data[++top]=x;。 5.向一个循环队列中插入一元素时,需首先移动,然后再向所指位置6.用下标0开始的N元数组实现循环队列时,为实现下标变量M加1后在数组有效下标范围内循环,可采用的表达式是: M=7.用长度为n的数组顺序存储一个栈时,若用top==n表示栈空,则表示栈满的条件为四,应用题 1.链栈中为何不设置头结点? 链栈不需要在头部附加头结点,因为栈都是在头部进行操作的,如果加了头结点,等于要对头结点之后的结点进行操作,反而使算法更复杂,所以只要有链表的头指针就可以了。 2.指出下列程序段的功能 (1)voidDemo1(SeqStack*S){ inti;arr[64];n=0; while(StackEmpty(S))arr[n++]=Pop(S); for(i=0,i }//Demo1 (1)程序段的功能是将一栈中的元素按反序重新排列,也就是原来在栈顶的元素放到栈底,栈底的元素放到栈顶。 此栈中元素个数限制在64个以内。 (2)SeqStackS1,S2,tmp; DataTypex; ...//假设栈tmp和S2已做过初始化 while(! StackEmpty(&S1)) { x=Pop(&S1); Push(&tmp,x); } while(! StackEmpty(&tmp)) { x=Pop(&tmp); Push(&S1,x); Push(&S2,x); } (2)程序段的功能是利用tmp栈将一个非空栈s1的所有元素按原样复制到一个栈s2当中去。 3.试证明: 若借助栈由输入序列1,2,…,n得到输出序列为P1,P2,…,Pn(它是输入序列的一 个排列),则在输出序列中不可能出现这样的情形: 存在着i 如果i 而对于pi>pj的情况,则说明 要将pj压到pi之上,也就是在pj出栈之后pi才能出栈。 这就说明,对于i 现pj
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 题库