1-3章课后习题答案.docx

第1章 绪论填空题1、数据元素，数据元素之间关系2、集合结构，线性结构，树型结构，图型结构3、有穷性，确定性，可行性4、数据元素，关系，基本操作5、逻辑结构，存储结构，运算6、时间，空间单项选择题题号123456答案BCCACC判断题题号123答案×××名词解释数据：客观事物的符号表示，在计算机科学中指所有能输入计算机中并被计算机处理的符号总称。整数、浮点数、字符串、声音、图像。数据元素：数据元素是数据的基本单位，在计算机程序中通常被作为一个整体进行考虑和处理。数据元素有时也被称为元素、结点、顶点、记录等。一个数据元素可由若干个数据项(Data Item)组成。数据结构：数据结构是相互之间存在一种或多种特定关系的数据元素的集合。主要描述的是数据元素之间的逻辑关系、数据在计算机系统中的存储方式和数据的运算三个方面的内容，即数据的逻辑结构、存储结构和数据的操作集合。逻辑结构：数据的逻辑结构独立于计算机，是数据本身所固有的特性。物理结构：数据的物理结构又称为存储结构(Storage Structure)，是数据在计算机中的表示（又叫映像）和存储，包括数据元素的表示和存储以及数据元素之间关系的表示和存储。算法：算法（Algorithm）是指在有限的时间范围内，为解决某一问题而采取的方法和步骤的准确完整的描述，它是一个有穷的规则序列，这些规则决定了解决某一特定问题的一系列运算。算法的时间复杂度：规模为n 的算法的执行时间，称为时间复杂度（time complexity）。应用题(n+3)(n-2)/2解析：外循环i的取值范围是1到n-2,内循环j的取值范围是n到i。当i=1时，内循环变量j从n变化到1，x=x+1将执行n次；当i=2时，内循环变量j从n变化到2，x=x+1将执行n-1次；依次类推，当i=n-2时，内循环变量j从n变化到n-2，x=x+1将执行3次；所以语句x=x+1的总的执行次数为：3+4+…+n-1+n=(n+3)(n-2)/2次。n（n-1）/2或(1)。 (2)。 第2章 线性表填空题1、顺序存储结构，链式存储结构2、也，不一定3、链式，顺序4、n-i+1，n-i5、O(1)6、插入和删除元素不需要移动元素，小7、头指针，头结点的next域，其前驱的next域8、主要是使插入和删除等操作统一，在第一个元素之前插入元素和删除第一个结点不必另作判断。另外，不论链表是否为空，链表指针不变。9、f-next=p-next，p-next-prior=f，f-prior=p，p-next=f10、a. 在p结点后插入s结点的语句序列是：（4）、（1）b. 在p结点前插入s结点的语句序列是：（8）、（12）、（9）、（4）、（1）c. 在表首插入s结点的语句序列是：（5）、（13）d. 在表尾插入s结点的语句序列是：（12）、（10）、（1）、（7）单项选择题题号12345678910答案ABABBABADB题号11121314151617181920答案CCCABBABCC判断题题号12345678910答案××√×××√√××综合题1、答：顺序存储结构可以实现对表中元素的随机存取，但在进行插入或删除操作时，需要移动大量元素。链表在存储空间的合理利用、插入删除操作不需要移动大量元素方面优于顺序表，但链表不能像顺序表那样实现元素的随机存取。2、答：头指针：指向链表第一个结点（或为头结点或为首元结点）的指针，单链表可由头指针唯一地确定。头结点：在链表的第一个结点之前附设的一个结点，头结点的指针域指向表中的第一个结点。首元结点：链表中存放第一个数据元素a1的结点，在带头结点的链表中，它是头结点的下一个结点。3、05U17X23V31Y47Z1001121041161081041120116100120X：116Y：0Z：100首结点的起起始地址为：108末结点的起始地址为：1124、intinsertx(int a[],intR, int x){inti,j; for(i=0; iRa[i]x; i++); /*找到x的插入位置*/for(j=R-1;j=i;j--) a[j+1]=a[j];/*插入位置之后的元素后移*/ a[i]=x; /*插入x*/R=R+1; return R; /*返回新的R值*/}5、（1）?以一维数组作存储结构，设线性表存于a[n]中。void invert1(inta[], int n){ int j,temp; for(j=0; j=(n-1)/2; j++ ){ temp = a[j]; a[j] = a[n-j-1]; a[n-j-1] = temp;} // for} // invert（2）?以单链