《数据结构》课后参考答案.docx
- 文档编号:12314227
- 上传时间:2023-06-05
- 格式:DOCX
- 页数:128
- 大小:548.80KB
《数据结构》课后参考答案.docx
《《数据结构》课后参考答案.docx》由会员分享,可在线阅读,更多相关《《数据结构》课后参考答案.docx(128页珍藏版)》请在冰点文库上搜索。
《数据结构》课后参考答案
单元练习1
一.判断题(下列各题,正确的请在前面的括号内打√;错误的打╳)
(√)
(1)数据的逻辑结构与数据元素本身的内容和形式无关。
(√)
(2)一个数据结构是由一个逻辑结构和这个逻辑结构上的一个基本运算集构成的整体。
(ㄨ)(3)数据元素是数据的最小单位。
(ㄨ)(4)数据的逻辑结构和数据的存储结构是相同的。
(ㄨ)(5)程序和算法原则上没有区别,所以在讨论数据结构时可以通用。
(√)(6)从逻辑关系上讲,数据结构主要分为线性结构和非线性结构两类。
(√)(7)数据的存储结构是数据的逻辑结构的存储映像。
(√)(8)数据的物理结构是指数据在计算机内实际的存储形式。
(ㄨ)(9)数据的逻辑结构是依赖于计算机的。
(√)(10)算法是对解题方法和步骤的描述。
二.填空题
(1)数据有逻辑结构和存储结构两种结构。
(2)数据逻辑结构除了集合以外,还包括:
线性结构、树形结构和图形结构。
(3)数据结构按逻辑结构可分为两大类,它们是线性结构和非线性结构。
(4)树形结构和图形结构合称为非线性结构。
(5)在树形结构中,除了树根结点以外,其余每个结点只有1个前趋结点。
(6)在图形结构中,每个结点的前趋结点数和后续结点数可以任意多个。
(7)数据的存储结构又叫物理结构。
(8)数据的存储结构形式包括:
顺序存储、链式存储、索引存储和散列存储。
(9)线性结构中的元素之间存在一对一的关系。
(10)树形结构结构中的元素之间存在一对多的关系,
(11)图形结构的元素之间存在多对多的关系。
(12)数据结构主要研究数据的逻辑结构、存储结构和算法(或运算)三个方面的内容。
(13)数据结构被定义为(D,R),其中D是数据的有限集合,R是D上的关系的有限集合。
(14)算法是一个有穷指令的集合。
(15)算法效率的度量可以分为事先估算法和事后统计法。
(16)一个算法的时间复杂性是算法输入规模的函数。
(17)算法的空间复杂度是指该算法所耗费的存储空间,它是该算法求解问题规模n的函数。
(18)若一个算法中的语句频度之和为T(n)=6n+3nlog2n,则算法的时间复杂度为O(nlog2n)。
(19)若一个算法中的语句频度之和为T(n)=3n+nlog2n+n2,则算法的时间复杂度为O(n2)。
(20)数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象,以及它们之间的关系和运算的学科。
三.选择题
(1)数据结构通常是研究数据的(A)及它们之间的相互联系。
A.存储结构和逻辑结构B.存储和抽象C.联系和抽象D.联系与逻辑
(2)在逻辑上可以把数据结构分成:
(C)。
A.动态结构和静态结构B.紧凑结构和非紧凑结构
C.线性结构和非线性结构D.内部结构和外部结构
(3)数据在计算机存储器内表示时,物理地址和逻辑地址相同并且是连续的,称之为(C)。
A.存储结构B.逻辑结构C.顺序存储结构D.链式存储结构
(4)非线性结构中的每个结点(D)。
A.无直接前趋结点
B.无直接后继结点
C.只有一个直接前趋结点和一个直接后继结点
D.可能有多个直接前趋结点和多个直接后继结点
(5)链式存储的存储结构所占存储空间(A)。
A.分两部分,一部分存放结点的值,另一部分存放表示结点间关系的指针
B.只有一部分,存放结点的值
C.只有一部分,存储表示结点间关系的指针
D.分两部分,一部分存放结点的值,另一部分存放结点所占单元素
(6)算法的计算量大小称为算法的(C)。
A.现实性B.难度C.时间复杂性D.效率
(7)数据的基本单位是(B)。
A.数据结构B.数据元素C.数据项D.文件
(8)每个结点只含有一个数据元素,所有存储结点相继存放在一个连续的存储区里,这种存储结构称为(A)结构。
A.顺序存储B.链式存储C.索引存储D.散列存储
(9)每一个存储结点不仅含有一个数据元素,还包含一组指针,该存储方式是(B)存储方式。
A.顺序B.链式C.索引D.散列
(10)以下任何两个结点之间都没有逻辑关系的是(D)。
A.图形结构B.线性结构C.树形结构D.集合
(11)在数据结构中,与所使用的计算机无关的是(C)。
A.物理结构B.存储结构C.逻辑结构D.逻辑和存储结构
(12)下列四种基本逻辑结构中,数据元素之间关系最弱的是(A)。
A.集合B.线性结构C.树形结构D.图形结构
(13)与数据元素本身的形式、内容、相对位置、个数无关的是数据的(A)。
A.逻辑结构B.存储结构C.逻辑实现D.存储实现
(14)每一个存储结点只含有一个数据元素,存储结点存放在连续的存储空间,另外有一组指明结点存储位置的表,该存储方式是(C)存储方式。
A.顺序B.链式C.索引D.散列
(15)算法能正确的实现预定功能的特性称为算法的(A)。
A.正确性B.易读性C.健壮性D.高效性
(16)算法在发生非法操作时可以作出处理的特性称为算法的(C)。
A.正确性B.易读性C.健壮性D.高效性
(17)下列时间复杂度中最坏的是(D)。
A.O
(1)B.O(n)C.O(log2n)D.O(n2)
(18)下列算法的时间复杂度是(D)。
for(i=0;i for(j=0;i c[i][j]=i+j; A.O (1)B.O(n)C.O(log2n)D.O(n2) (19)算法分析的两个主要方面是(A)。 A.空间复杂性和时间复杂性B.正确性和简明性 C.可读性和文档性D.数据复杂性和程序复杂性 (20)计算机算法必须具备输入、输出和(C)。 A.计算方法B.排序方法 C.解决问题的有限运算步骤D.程序设计方法 四.分析下面各程序段的时间复杂度 (1)for(i=0;i for(j=0;j A[i][j] 解: O(n*m) (2)s=0; for(i=0;i for(j=0;j s+=B[i][j]; sum=s; 解: O(n2) (3)T=A; A=B; B=T; 解: O (1) (4)s1(intn) {intp=1,s=0; for(i=1;i<=n;i++) {p*=i;s+=p;} return(s); } O(n) (5)s2(intn) x=0; y=0; for(k=1;k<=n;k++) x++; for(i=1;i<=n;i++) for(j=1;j<=n;j++) y++; 解: O(n2) 五.根据二元组关系,画出对应逻辑图形的草图,指出它们属于何种数据结构。 (1)A=(D,R),其中: D={a,b,c,d,e}, R={} 解: ab cde 属于集合 (2)B=(D,R),其中: D={a,b,c,d,e,f},R={r} 解: 属于线性结构。 (3)F=(D,R),其中: D={50,25,64,57,82,36,75,55},R={r} R={<50,25>,<50,64>,<25,36>,<64,57>,<64,82>,<57,55>,<57,75>} 解: 属于树结构 (4)C=(D,R),其中: D={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)}(园括号表示结点之间关系是有向的) 解: 属于图结构 (5)E=(D,R),其中: D={a,b,c,d,e,f,g,h},R={r} R={ 解: 属于树结构。 单元练习2 一.判断题(下列各题,正确的请在前面的括号内打√;错误的打╳) (×) (1)线性表的链式存储结构优于顺序存储。 (×) (2)链表的每个结点都恰好包含一个指针域。 (√)(3)在线性表的链式存储结构中,逻辑上相邻的两个元素在物理位置上并不一定紧邻。 (×)(4)顺序存储方式的优点是存储密度大,插入、删除效率高。 (×)(5)线性链表的删除算法简单,因为当删除链中某个结点后,计算机会自动地将后续的各个单元向前移动。 (×)(6)顺序表的每个结点只能是一个简单类型,而链表的每个结点可以是一个复杂类型。 (√)(7)线性表链式存储的特点是可以用一组任意的存储单元存储表中的数据元素。 (√)(8)线性表采用顺序存储,必须占用一片连续的存储单元。 (×)(9)顺序表结构适宜于进行顺序存取,而链表适宜于进行随机存取。 (ㄨ)(10)插入和删除操作是数据结构中最基本的两种操作,所以这两种操作在数组中也经常使用。 二.填空题 (1)顺序表中逻辑上相邻的元素在物理位置上必须相连。 (2)线性表中结点的集合是有限的,结点间的关系是一对一关系。 (3)顺序表相对于链表的优点是: 节省存储和随机存取。 (4)链表相对于顺序表的优点是: 插入、删除方便。 (5)采用顺序存储结构的线性表叫顺序表。 (6)顺序表中访问任意一个结点的时间复杂度均为O (1)。 (7)链表相对于顺序表的优点是插入、删除方便;缺点是存储密度小。 (8)在双链表中要删除已知结点*P,其时间复杂度为O (1)。 (9)在单链表中要在已知结点*P之前插入一个新结点,需找到*P的直接前趋结点的地址,其查找的时间复杂度为O(n)。 (10)单链表中需知道头指针才能遍历整个链表。 (11)性表中第一个结点没有直接前趋,称为开始结点。 (12)在一个长度为n的顺序表中删除第i个元素,要移动n-i个元素。 (13)在一个长度为n的顺序表中,如果要在第i个元素前插入一个元素,要后移n-i+1个元素。 (14)在无头结点的单链表中,第一个结点的地址存放在头指针中,而其它结点的存储地址存放在前趋结点的指针域中。 (15)当线性表的元素总数基本稳定,且很少进行插入和删除操作,但要求以最快速度存取线性表中的元素时,应采用顺序存储结构。 (16)在线性表的链式存储中,元素之间的逻辑关系是通过指针决定的。 (17)在双向链表中,每个结点都有两个指针域,它们一个指向其前趋结点,另一个指向其后继结点。 (18)对一个需要经常进行插入和删除操作的线性表,采用链式存储结构为宜。 (19)双链表中,设p是指向其中待删除的结点,则需要执行的操作为: p->prior->next=p->next。 (20)在如图所示的链表中,若在指针P所在的结点之后插入数据域值为a和b的两个结点,则可用下列两个语句: S->next->next=P->next;和P->next=S;来实现该操作。 Λ a b S 三.选择题 (1)在具有n个结点的单链表中,实现(A)的操作,其算法的时间复杂度都是O(n)。 A.遍历链表或求链表的第i个结点B.在地址为P的结点之后插入一个结点 C.删除开始结点D.删除地址为P的结点的后继结点 (2)设a、b、c为三个结点,p、10、20分别代表它们的地址,则如下的存储结构称为(B)。 A.循环链表B.单链表C.双向循环链表D.双向链表 (3)单链表的存储密度(C)。 A.大于1B.等于1C.小于1D.不能确定 (4)已知一个顺序存储的线性表,设每个结点占m个存储单元,若第一个结点的地址为B,则第i个结点的地址为(A)。 A.B+(i-1)*mB.B+i*mC.B-i*mD.B+(i+1)*m (5)在有n个结点的顺序表上做插入、删除结点运算的时间复杂度为(B)。 A.O (1)B.O(n)C.O(n2)D.O(log2n) (6)设Llink、Rlink分别为循环双链表结点的左指针和右指针,则指针P所指的元素是双循环链表L的尾元素的条件是(D)。 A.P==LB.P->Llink==LC.P==NULLD.P->Rlink==L (7)两个指针P和Q,分别指向单链表的两个元素,P所指元素是Q所指元素前驱的条件是(B)。 A.P->next==Q->nextB.P->next==QC.Q->next==PD.P==Q (8)用链表存储的线性表,其优点是(C)。 A.便于随机存取B.花费的存储空间比顺序表少 C.便于插入和删除D.数据元素的物理顺序与逻辑顺序相同 (9)在单链表中,增加头结点的目的是(C)。 A.使单链表至少有一个结点B.标志表中首结点的位置 C.方便运算的实现D.说明该单链表是线性表的链式存储结构 (10)下面关于线性表的叙述中,错误的是(D)关系。 A.顺序表必须占一片地址连续的存储单元B.顺序表可以随机存取任一元素 C.链表不必占用一片地址连续的存储单元D.链表可以随机存取任一元素 (11)L是线性表,已知LengthList(L)的值是5,经DelList(L,2)运算后,LengthList(L)的值是(C)。 A.2B.3C.4D.5 (12)单链表的示意图如下: L A B C D Λ Q 指向链表Q结点的前趋的指针是(B)。 A.LB.PC.QD.R (13)设p为指向单循环链表上某结点的指针,则*p的直接前驱(C)。 A.找不到B.查找时间复杂度为O (1) C.查找时间复杂度为O(n)D.查找结点的次数约为n (14)等概率情况下,在有n个结点的顺序表上做插入结点运算,需平均移动结点的数目为(C)。 A.nB.(n-1)/2C.n/2D.(n+1)/2 (15)在下列链表中不能从当前结点出发访问到其余各结点的是(C)。 A.双向链表B.单循环链表C.单链表D.双向循环链表 (16)在顺序表中,只要知道(D),就可以求出任一结点的存储地址。 A.基地址B.结点大小C.向量大小D.基地址和结点大小 (17)在双链表中做插入运算的时间复杂度为(A)。 A.O (1)B.O(n)C.O(n2)D.O(log2n) (18)链表不具备的特点是(A)。 A.随机访问B.不必事先估计存储空间 C.插入删除时不需移动元素D.所需空间与线性表成正比 (19)以下关于线性表的论述,不正确的为(C)。 A.线性表中的元素可以是数字、字符、记录等不同类型 B.线性顺序表中包含的元素个数不是任意的 C.线性表中的每个结点都有且仅有一个直接前趋和一个直接后继 D.存在这样的线性表,即表中没有任何结点 (20)在(B)的运算中,使用顺序表比链表好。 A.插入B.根据序号查找C.删除D.根据元素查找 四.分析下述算法的功能 (1) (2) 解: (1)返回结点*p的直接前趋结点地址。 (2)交换结点*p和结点*q(p和q的值不变)。 五.程序填空 (1)已知线性表中的元素是无序的,并以带表头结点的单链表作存储。 试写一算法,删除表中所有大于min,小于max的元素,试完成下列程序填空。 Voiddelete(lklisthead;datatypemin,max) {q=head->next; while(p! =NULL) {if((p->data<=min)||(p->data>=max) {q=p;p=p->next;} else {q->next=p->next; delete(p); p=q->next;} } } (2)在带头结点head的单链表的结点a之后插入新元素x,试完成下列程序填空。 structnode {elemtypedata; node*next; }; voidlkinsert(node*head,elemtypex) {node*s,*p; s=newnode; s->data=x; p=head->next; while(p! =NULL)&&(p->data! =a) ____p=p->next; if(p==NULL) cout<<"不存在结点a! "; else{_____s->next=p->next______; ___p->next=s__________; } } 六.算法设计题 (1)写一个对单循环链表进行遍历(打印每个结点的值)的算法,已知链表中任意结点的地址为P。 解: voidShow(ListNode*P) {ListNode*t=P; do {printf("%c",t->data); t=t->rear; } while(t! =P); } (2)对给定的带头结点的单链表L,编写一个删除L中值为x的结点的直接前趋结点的算法。 解: voiddelete(ListNode*L) {ListNode*p=L,*q; if(L->next->data==X) { printf(“值为x的结点是第一个结点,没有直接前趋结点可以删除”); return; } For(p->next->data! =X;q=p;p=p->next);//删除指针p所指向的结点 q->next=p->next; deletep; } (3)已知一个单向链表,编写一个函数从单链表中删除自第i个结点起的k个结点。 解: voidDel(node*head,inti,intk) { node*p,*q; intj; if(i==1) for(j=1;j<=k;j++)//删除前k个元素 { p=head;//p指向要删除的结点 head=head->next; deletep; } else { p=head; for(j=1;j<=i-2;j++) p=p->next;//p指向要删除的结点的前一个结点 for(j=1;j<=k;j++) { q=p->next;//q指向要删除的结点 p->next=q->next; deleteq; } } } (4)有一个单向链表(不同结点的数据域值可能相同),其头指针为head,编写一个函数计算值域为x的结点个数。 解: //本题是遍历单链表的每个结点,每遇到一个结点,结点个数加1,结点个数存储在变量n中。 实现本题功能的函数如下: intcounter(head) node*head; {node*p; intn=0; p=head; while(p! =NULL) {if(p->data==x) n++; p=p->next; } return(n); } (5)有两个循环单向链表,链头指针分别为head1和head2,编写一个函数将链表head1链接到链表head2,链接后的链表仍是循环链表。 解: //本题的算法思想是: 先找到两链表的尾指针,将第一个链表的尾指针与第二个链表的头结点链接起来,使之成为循环的。 函数如下: node*link(node*head1,*head2) {node*p,*q; p=head1; while(p->next! =head1) p=p->next; q=head2; while(q->next! =head2) q=q->next; p->next=head2; q->next=head1; return(head1); } 单元练习3 一.判断题(下列各题,正确的请在前面的括号内打√;错误的打╳) (√) (1)栈是运算受限制的线性表。 (√) (2)在栈空的情况下,不能作出栈操作,否则产生下溢出。 (ㄨ)(3)栈一定是顺序存储的线性结构。 (√)(4)栈的特点是“后进先出”。 (ㄨ)(5)空栈就是所有元素都为0的栈。 (ㄨ)(6)在C或C++语言中设顺序栈的长度为MAXLEN,则top=MAXLEN时表示队满。 (√)(7)链栈与顺序栈相比,其特点之一是通常不会出现栈满的情况。 (ㄨ)(8)一个栈的输入序列为: A,B,C,D,可以得到输出序列: C,A,B,D。 (ㄨ)(9)递归定义就是循环定义。 (√)(10)将十进制数转换为二进制数是栈的典型应用之一。 二.填空题 (1)在栈结构中,允许插入、删除的一端称为栈顶。 (2)在顺序栈中,当栈顶指针top=-1时,表示栈空。 (3)在有n个元素的栈中,进栈操作的时间复杂度为O (1)。 (4)在栈中,出栈操作的时间复杂度为: O (1)。 (5)已知表达式,求它的后缀表达式是栈的典型应用。 (6)在一个链栈中,若栈顶指针等于NULL,则表示栈空。 (7)向一个栈顶指针为top的链栈插入一个新结点*p时,应执行p->next=top;和top=p;操作。 (8)顺序栈S存储在数组S->data[0..MAXLEN-1]中,进栈操作时要执行的语句有: S->top++。 (或=S->top+1) (9)链栈LS,指向栈顶元素的指针是LS->next。 (10)从一个栈删除元素时,首先取出栈顶元素,然后再移动栈顶指针。 (11)由于链栈的操作只在链表的头部进行,所以没有必要设置头结点。 (12)已知顺序栈S,在对S进行进栈操作之前首先要判断栈是否满。 (13)已知顺序栈S,在对S进行出栈操作之前首先要判断栈是否空。 (14)若内存空间充足,链栈可以不定义栈满运算。 (15)链栈LS是空的条件是LS->next=NULL。 (16)链栈LS的栈顶元素是链表的首元素。 (17)同一栈的各元素的类型相同。 (18)若进栈的次序是A、B、C、D、E,执行三次出栈操作以后,栈顶元素为B。 (19)A+B/C-D*E的
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 课后 参考答案