数据结构自测题答案

《数据结构自测题答案》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第1章绪论一、选择题12345678CCADABCC二、填空题1.4种基本结构是：集合、线性结构、树形结构、图状结构。2.树形结构中元素的关系是一对多，图形结构中元素的关系是多对多。3.顺序存储结构中数据元素的存储位置与其逻辑顺序是对应的。4.算法效率的度量方法有：事后统计方法和事前分析估算方法。5.好算法应达到的目标：正确性、可读性、健壮性、执行时间短、存储量低。6.抽象数据类型可细分为3种：原子类型、固定聚合类型和可变聚合类型。7.抽象数据类型的定义包括：数据对象的定义、数据关系的定义、基本操作的定义。三

2、、判断题1234567891011√×√×√√×××√×五、应用题1.按增长率从小到大的顺序排列下列各函数：(2/3)n，，n，n2，n!2.写出以下各函数的功能，并求出其时间复杂度。(1)功能是判断n是否为素数，时间复杂度为O(√n)。(2)功能是计算1!+2!+…+n!，时间复杂度为O(n)。(3)功能是计算1!+2!+…+n!，时间复杂度为O(n2)。六、算法题1.编写算法计算1!+2!+…+n!，并使算法的时间复杂度为O(n)。算法思想：用循环实现阶乘的累加求和，注意在求n!时，使用前一次循环中已经求

3、出的(n-1)!的结果。doublefactorial(intn){inti;doublep=1,sum=0;for(i=1;i<=n;i++){p=p*i;sum=sum+p;}return(sum);}2.编写算法计算2i(i=0,1,2,…,n)，并将计算结果存入数组a中，设计算机中允许的最大整数值为MAXINT，则当2k>MAXINT（0≤k≤n）时，应进行出错处理。算法思想：先判断n的取值是否合法，若非法则直接退出程序，若n合法则继续计算2i，在计算2i时，需要判断2i的值是否大于MAXINT/2，

4、这个条件其实就是判断2i+1的值是否大于MAXINT#definearrsize100#defineMAXINT65535voidcalculate(inta[],intn){inti;if(n<=0

5、

6、n>arrsize){printf("nerror!");exit(-1);}a[0]=1;printf("a[0]=%d",a[0]);for(i=1;iMAXINT/2){print

7、f(“i=%d,ERROR!”,i+1)；break;}}}第2章线性结构一、选择题1234567891011121314151617ABCADBBACACBBBDCD二、填空题1.需向后移动__n-i+1____个元素。2.应采用__顺序___存储结构。3.有n个结点的单链表，在x的结点后插入一个新结点的时间复杂度为__O(n)____。4．可以将线性链表分成__单链表__和多重链表。5．链接存储的特点是利用__指针_来表示数据元素之间的逻辑关系。6.顺序存储结构是通过_物理位置相邻___表示元素之间的

8、关系的;链式存储结构是通过___指针____表示元素之间的关系的。7.循环单链表的最大优点是：__从任一结点出发都可访问到链表中每一个元素___。8.带头结点的单循环链表L，L为空表的条件是：__L->next==L___。三、判断题12345678×××××××√四、简答题1.对线性表中的插入操作，分别写出顺序存储结构和链式存储结构下的时间复杂度。答：O(n),O(1)2.线性结构的特点是什么？答：在数据元素的非空有限集中，(1)存在唯一的一个被称为“第一个”的数据元素;(2)存在唯一的一个被称为“最后一个

9、”的数据元素;(3)除第一个之外，集合中的每个元素均只有一个前驱;(4)除最后一个之外，集合中每个元素均只有一个后继3.说明在线性表的链式存储结构中，头指针与头结点之间的根本区别；头结点与首元结点的关系。答：在线性表的链式存储结构中，头指针指链表的指针，若链表有头结点则是链表的头结点的指针，头指针具有标识作用，故常用头指针冠以链表的名字。头结点是为了操作的统一、方便而设立的，放在第一元素结点之前，其数据域一般无意义（有些情况下也可存放链表的长度、用做监视哨等），有头结点后，对在第一元素结点前插入结点和删除第一

10、结点，其操作与对其它结点的操作统一了。而且无论链表是否为空，头指针均不为空。首元结点也就是第一元素结点，它是头结点后边的第一个结点。4.在单链表和双向链表中，能否从当前结点出发访问到任何一个结点?答：在单链表中不能从当前结点（若当前结点不是第一结点）出发访问到任何一个结点，链表只能从头指针开始，访问到链表中每个结点。在双链表中求前驱和后继都容易，从当前结点向前到第一结点，向后到最后结点，可以访问到任