1、试描述头指针、头结点、开始结点的区别、并说明头指针和头结点的作用。
答：开始结点是指链表中的第一个结点，也就是没有直接前趋的那个结点。
链表的头指针是一指向链表开始结点的指针(没有头结点时)，单链表由头指针唯一确定，因此单链表可以用头指针的名字来命名。
头结点是我们人为地在链表的开始结点之前附加的一个结点。有了头结点之后，头指针指向头结点，不论链表否为空，头指针总是非空。而且头指针的设置使得对链表的第一个位置上的操作与在表其他位置上的操作一致(都是在某一结点之后)。
2、何时选用顺序表、何时选用链表作为线性表的存储结构为宜?
答：在实际应用中，应根据具体问题的要求和性质来选择顺序表或链表作为线性表的存储结构，通常有以下几方面的考虑：
1) 基于空间的考虑。当要求存储的线性表长度变化不大，易于事先确定其大小时，为了节约存储空间，宜采用顺序表；反之，当线性表长度变化大，难以估计其存储规模时，采用动态链表作为存储结构为好。
2) 基于时间的考虑。若线性表的操作主要是进行查找，很少做插入和删除操作时，采用顺序表做存储结构为宜；反之，若需要对线性表进行频繁地插入或删除等操作时，宜采用链表做存储结构。并且，若链表的插入和删除主要发生在表的首尾两端，则采用尾指针表示的单循环链表为宜。
3、在顺序表中插入和删除一个结点需平均移动多少个结点?具体的移动次数取决于哪两个因素?
答：在等概率情况下，顺序表中插入一个结点需平均移动n/2个结点，删除一个结点需平均移动(n-1)/2个结点。具体的移动次数取决于顺序表的长度n以及需插入或删除的位置i。i 越接近n则所需移动的结点数越少。
4、为什么在单循环链表中设置尾指针比设置头指针更好?
答：尾指针是指向终端结点的指针，用它来表示单循环链表可以使得查找链表的开始结点和终端结点都很方便，设一带头结点的单循环链表，其尾指针为rear，则开始结点和终端结点的位置分别是rear->next->next 和rear, 查找时间都是O(1)。
若用头指针来表示该链表，则查找终端结点的时间为O(n)。
5、在单链表、双链表和单循环链表中，若仅知道指针p指向某结点，不知道头指针，能否将结点*p从相应的链表中删去?若可以，其时间复杂度各为多少?
答：我们分别讨论三种链表的情况。
1) 单链表。当我们知道指针p指向某结点时，能够根据该指针找到其直接后继，但是由于不知道其头指针，所以无法访问到p指针指向的结点的直接前趋。因此无法删去该结点。
2) 双链表。由于这样的链表提供双向链接，因此根据已知结点可以查找到其直接前趋和直接后继，从而可以删除该结点。其时间复杂度为O(1)。
3) 单循环链表。根据已知结点位置，我们可以直接得到其后相邻的结点位置(直接后继)，又因为是循环链表，所以我们可以通过查找，得到p结点的直接前趋。因此可以删去p所指结点。其时间复杂度应为O(n)。
6、下述算法的功能是什么?
LinkList Demo(LinkList L){ // L是无头结点单链表
ListNode *Q,*P;
if(L&&L->next){
Q=L;L=L->next;P=L;
while (P->next) P=P->next;
P->next=Q; Q->next=NULL;
}
return L;
}// Demo
答：该算法的功能是：将开始结点摘下链接到终端结点之后成为新的终端结点，而原来的第二个结点成为新的开始结点，返回新链表的头指针。
7、不带头结点的单链表head为空的判定条件是（）。
A、head=NULL
B、head->next=NULL
C、head->next=head
D、head!=NULL
8、在一单链表中，已知q所指的结点是p所指结点的前驱结点，若在q和p之间插入s结点，则执行（）。
A、s->next=p->next;p->next=s;
B、p->next=s->next;s->next=p;
C、q->next=s;s->next=p;
D、p->next=s;s->next=q;
9、在一个单链表中，若p所指的结点不是最后结点，在p之后插入s结点，则执行（）。
A、s->next=p;p->next=s;
B、s->next=p->next;p->next=s;
C、s->next=p->next;p=s;
D、p->next=s;s->next=p;
10、在一个单链表中，若删除p所指结点的后续结点，则执行（）。
A、p->next=p->next->next;
B、p=p->next;p->next=p->next->next;
C、p->next=p->next;
D、p=p->next->next;
11、从一个具有n个结点的单链表中查找其值等于x结点时，在查找成功的情况下，需要平均比较（）个结点？
A、n
B、n/2
C、(n-1)/2
D、(n+1)/2
12、在一个具有n个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度是（）。
A、O(1)
B、O(n)
C、O(n2)
D、O(nlog2n)
13、给定有n个元素的向量，建立一个有序单链表的时间复杂度是（）。
A、O(1)
B、O(n)
C、O(n2)
D、O(nlog2n)
14、带有一个头结点的单链表head为空的条件是.
15、对于一个具有n个结点的单链表，在已知p所指结点之后插入一个新结点的时间复杂度为；在给定值为x的结点后插入一个新结点的时间复杂度是。
16、设顺序表L是一个非递减有序表，试写一算法，将x插入L中，并使L仍是一个有序表。
解：因已知顺序表L是递增有序表，所以只要从头找起找到第一个比它大(或相等)的结点数据，把x插入到这个结点所在的位置就是了。
算法如下：
void InsertIncreaseList(Sqlist *L,Datatype x)
{ int i;
for( i=0;i ListInsert (*L,i,x); // 调用顺序表插入函数 }// InsertIncreaseList 17、设顺序表L是一个递减有序表，试写一算法，将x插入其后仍保持L的有序性。解：与上题相类似，只要从头找到第一个比x小(或相等)的结点数据，在这个位置插入就可以了。 算法如下： void InsertDecreaseList(Sqlist *L,Datatype x) { int i; for (i=0;i ListInsert(*L,i,x); // 调用顺序表插入函数 }// InsertDecreaseList 18、写一算法在单链表上实现线性表的ListLength(L)运算。 解：求单链表长只能用遍历的方法了，从头数到尾。 算法如下： int ListLength( LinkList L ) { int len=0; ListNode *p; p=L; //设该表有头结点 while (p->next) { p=p->next; len++; } return len; }// ListLength 19、已知L1和L2分别指向两个单链表的头结点，且已知其长度分别为m和n。试写一算法将这两个链表连接在一起，请分析你的算法的时间复杂度。 解：算法如下: LinkList Link( LinkList L1 , LinkList L2 ) {//将两个单链表连接在一起 ListNode *p, *q; p=L1; q=L2; while ( p->next ) p=p->next; //查找终端结点 p->next = q->next ; //将L2的开始结点链接在L1之后 return L1 ; }// LinkList Link 分析：本算法的主要操作时间花费在查找L1的终端结点上，与L2的长度无关，所以本算的法时间复杂度为：m+1=O(m) 20、删除带头结点单链表L中的元素x。 解：算法如下: Void delete(LinkList &L,ElemType x) { p=L->next; pre=L; while(p) { if(p->data=x) { pre->next=p->next; free(p); p=pre->next; } else { pre=p; p=p->next; } } }//delete 21、已知：A=(a1,a2,……,a n-1,a n) B=(b1,b2,……,b n-1,b n)均为顺序表，试编写一个比较A、B 大小的算法。 解：算法目标是分析两表的大小，所以不应破坏原表。表的大小指的是“词典顺序”，而非表的长度。 基本操作为：同步比较两个表中相应的数据元素。 假设：int compare(SqList La,SqList Lb) 循环条件：(i<=La.Length)&&( i<=Lb.Length) 主要操作为：if (La.elem[i]==Lb.elem[i]) i++; else if (La.elem[i] else return 1; 循环结束时可能有三种情况： ●(i> La.Length)&&( i>Lb.Length) return 0; ●(i<=La.Length)&&(i>Lb.Length) return 1; ●(i>La.Length)&&(i<=Lb.Length) return -1; 22、删除有序表中所有其值大于minval且小于maxval的数据元素。 解：while(p&&p->data<=minval) { pre=p; p=p->next; } if (p) { while (p&&p->data q=pre->next; pre->next=p; while(q!=p) //q==p时，删除的为一个元素 { s=q; q=q->next; free(s); } //释放中间结点 23、写一算法将单链表中值重复的结点删除，使所得结果表中各结点值均不相同。 解：本题可以这样考虑，先取开始结点中的值，将它与其后的所有结点值一一比较，发现相同的就删除掉，然后再取第二结点的值，重复上述过程直到最后一个结点。 第二种算法是将单链表按值的大小排序，排好后的结点按相同的删除。 具体算法略。 24、试编写在带头结点的单链表中删除（一个）最小值结点的（高效）算法。 void delete（Linklist &L） [题目分析] 本题要求在单链表中删除最小值结点。单链表中删除结点，为使结点删除后不出现“断链”，应知道被删结点的前驱。而“最小值结点”是在遍历整个链表后才能知道。所以算法应首先遍历链表，求得最小值结点及其前驱。遍历结束后再执行删除操作。 LinkList Delete（LinkList L） ∥L是带头结点的单链表，本算法删除其最小值结点。 { p=L->next；∥p为工作指针，指向待处理结点。假定链表非空。 pre=L；∥pre指向最小值结点的前驱。 q=p；∥q指向最小值结点，初始假定第一元素结点是最小值结点。 while（p->next!=null） {if（p->next->data p=p->next；∥指针后移。 } pre->next=q->next；∥从链表上删除最小值结点 free（q）；∥释放最小值结点空间 }∥算法结束 [算法讨论] 算法中函数头是按本教材类C描述语言书写的。原题中void delete （linklist &L），是按C++的“引用”来写的，目的是实现变量的“传址”，克服了C语言函数传递只是“值传递”的缺点。 25、已知非空线性链表由list指出，链结点的构造为（data,link）。请写一算法，将链表中数据域值最小的那个链结点移到链表的最前面。要求：不得额外申请新的链结点。 [题目分析] 本题要求将链表中数据域值最小的结点移到链表的最前面。首先要查找最小值结点。将其移到链表最前面，实质上是将该结点从链表上摘下（不是删除并回收空间），再插入到链表的最前面。 LinkList delinsert（LinkList list） ∥list是非空线性链表，链结点结构是（data，link），data是数据域，link是链域。本算法将链表中数据域值最小的那个结点移到链表的最前面。 {p=list->link；∥p是链表的工作指针 pre=list；∥pre指向链表中数据域最小值结点的前驱 q=p；∥q指向数据域最小值结点，初始假定是第一结点 while （p->link!=null） {if（p->link->data p=p->link； } if (q!=list->link) ∥若最小值是第一元素结点，则不需再操作 {pre->link=q->link；∥将最小值结点从链表上摘下； q->link= list->link；∥将q结点插到链表最前面。 list->link=q； } }∥算法结束 [算法讨论] 算法中假定list带有头结点，否则，插入操作变为q->link=list；list=q。 26、已知递增有序的单链表A,B分别存储了一个集合，请设计算法以求出两个集合A和B 的差集A-B（即仅由在A中出现而不在B中出现的元素所构成的集合），并以同样的形式存储，同时返回该集合的元素个数。 [题目分析] 求两个集合A和B的差集A-B，即在A中删除A和B中共有的元素。由于集合用单链表存储，问题变成删除链表中的结点问题。因此，要记住被删除结点的前驱，以便顺利删除被删结点。两链表均从第一元素结点开始，直到其中一个链表到尾为止。 void Difference（LinkList A，B，*n） ∥A和B均是带头结点的递增有序的单链表，分别存储了一个集合，本算法求两集合的差集，存储于单链表A中，*n是结果集合中元素个数，调用时为0 { p=A->next；∥p和q分别是链表A和B的工作指针 q=B->next；pre=A；∥pre为A中p所指结点的前驱结点的指针 while（p!=null && q!=null） if（p->data else {pre->next=p->next；∥处理A，B中元素值相同的结点，应删除 u=p；p=p->next；free（u）；} ∥删除结点 }∥Difference 27、请写一个算法将顺序存储结构的线性表（a1...a n）逆置为(a n...a1)。 类似本题的另外叙述有： (1) 设有一带头结点的单链表,编程将链表颠倒过来.要求不用另外的数组或结点完成. (2) 设有一个带头结点的单向链表，数据项递减有序。写一算法，重新排列链表，使数据项递增有序，要求算法时间复杂度为O（n）。（注：用程序实现） (3) 试编写求倒排循环链表元素的算法。 (4) 请设计算法将不带头结点的单链表就地逆置。 (5) 试编写算法，将不设表头结点的、不循环的单向链表就地逆转。 (6) 有一个单链表L（至少有1个结点），其头结点指针为head，编写一个过程将L逆置，即最后一个结点变成第一个结点，原来倒数第二个结点变成第二个结点，如此等等。 [题目分析] 顺序存储结构的线性表的逆置，只需一个变量辅助空间。算法核心是选择循环控制变量的初值和终值。 void SeqInvert（ElemType a[ ]，int n） ∥a是具有n个元素用一维数组存储的线性表，本算法将其逆置。 {for（i=0；i<=（n-1）/2；i++） {t=a[i]；a[i]= a[n-1-i]；a[n-1-i]=t；} }∥SeqInvert [算法讨论] 算法中循环控制变量的初值和终值是关键。C中数组从下标0开始，第n 个元素的下标是n-1。因为首尾对称交换，所以控制变量的终值是线性表长度的一半。当n 为偶数，“一半”恰好是线性表长度的二分之一；若n是奇数，“一半”是小于n/2的最大整数，这时取大于1/2的最小整数的位置上的元素，恰是线性表中间位置的元素，不需要逆置。 类似本题的其它题的解答： 这一组选了6个题，都是单链表（包括单循环链表）的逆置。链表逆置的通常作法是：将工作指针指向第一个元素结点，将头结点的指针域置空。然后将链表各结点从第一结点开始直至最后一个结点，依次前插至头结点后，使最后插入的结点成为链表的第一结点，第一个插入的结点成为链表的最后结点。 第2章线性表 一、选择题 1. 链表不具备的特点是（）。 A．可随机访问任意结点 B. 插入删除不需要移动元素 C. 不必事先估计存储空间 D. 所需空间与其长度成正比 2. 不带头结点的单链表head为空的判定条件是（）。 ==NULL B. head->next==NULL >next==head !=NULL 3.带头结点的单链表head为空的判定条件是（）。 ==NULL B. head->next==NULL >next==head !=NULL 4．带头结点的双循环链表L为空表的条件是（）。 A．L==NULL B．L->next->==NULL C．L->prior==NULL >next==L 5.非空的循环链表head的尾结点（由P所指向）满足（）。 A．p->next==NULL B．p==NULL C．p->next==head ==head 6.在循环双链表的p所指结点之前插入s所指结点的操作是（）。 A．p->prior=s;s->next=p;p->prior->next=s;s->prior=p->prior; B．p->prior=s;p->prior->next=s;s->next=p;s->prior=p->prior; C．s->next=p;s->prior=p->prior;p->prior=s;p->right->next=s; D. s->next=p;s->prior=p->prior;p->prior->next=s;p->prior=s; 7.若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一个结点，则采用（）存储方式最节省运算时间。 A．单链表 B．给出表头指针的单循环链表 C．双链表 D. 带头结点的双循环链表 8.某线性表最常用的操作是在最后一个结点之后插入一个节点或删除第一个结点，故采用（）存储方式最节省运算时间。 A．单链表 B．仅有头结点的单循环链表 C．双链表 D. 仅有尾指针的单循环链表 9.需要分配较大空间，插入和删除不需要移动元素的线性表，其存储结构是（）。 A．单链表 B．静态链表 C．线性链表 D. 顺序存储结构 10.如果最常用的操作是取第i个结点及前驱，则采用（）存储方式最节省时间。 A．单链表 B．双链表 C.单循环链表 D.顺序表 11.在一个具有n个结点的有序单链表中插入一个新结点并仍然保持有序的时间复杂度是（）。 A．O(1) B．O(n) C．O(n*n) D. O(nlog2n) 12.在一个长度为n(n>1)的单链表上，设有头和尾两个指针，执行()操作与链表的长度有关。A．删除单链表中的第一个元素 B．删除单链表中的最后一个元素 C. 在单链表第一个元素前插入一个新元素 D.在单链表最后一个元素后插入一个新元素 13.设线性表有n个元素，以下算法中，()在顺序表上实现比在链表上实现效率更高。A．输出第i(0<=i<=n-1)个元素值 B．交换第0个元素与第1个元素的值 C. 顺序输出这n个元素的值 D.输出与给定值x相等的元素在线性表中的序号 14.设线性表有2n个元素，算法()，在单链表上实现比在顺序表上实现效率更高。 A．删除所有值为x的元素 B．在最后一个元素的后面插入一个新元素 C. 顺序输出前k个元素 D.交换第i个元素和第2n-i-1个元素的值(i=0,1,…,n-1) 习题六树和二叉树6.1 单项选择题 (A) (B) (C) (D) 图8.7 4棵二叉树 1. 如图8.7所示的4棵二叉树，_ _不是完全二叉树。 图8.8 4棵二叉树 2. 如图8.8所示的4棵二叉树，__B_是平衡二叉树。 3. 在线索化二叉树中，t所指结点没有左子树的充要条件是B__o A. t —> left二NULL B. t —> ltag=1 C. t —> ltag=1 且t —> left=NULL D. 以上都不对 4. 二叉树按某种顺序线索化后，任一结点均有指向其前驱和后续的线索，这种说 法_B__ o A.正确 B. 错误 5. 二叉树的前序遍历序列中，任意一个结点均处在其子女结点的前面，这种说法 _A__。 A.正确 B. 错误 6. 由于二叉树中每个结点的度最大为2,所以二叉树是一种特殊的树，这种说法 _B_o A.正确 B. 错误 7. 设高度为h的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的结点数至少为—B__o A. 2h B. 2h-1 C. 2h+1 D. h+1 a 8. 如图8.9所示二叉树的中序遍历序列 B o 图8.9 一棵二叉树 A. abcdgef B. dfebagc C. dbaefcg D. defbagc 9. 已知某二叉树的后序遍历序列是d abec，中序遍历序 列是debac，它的前序遍历 序列是D ___ 。 A. acbed B. decab C. deabc D. cedba 10. 设a,b为一棵二叉树上的两个结点，在中序遍历时，a在b前的条件是 B 。 A. a在b的右方 B. a在b的左方 C. a是b的祖先 D. a是b的子孙 11?假定在一棵二叉树中，双分支结点数为15,单分支结点数为30个，则叶子结 点数为个。B A. 15 B. 16 C. 17 D. 47 12. 某二叉树的前序遍历结点访问顺序是abdgcefh，中序遍历的结点访问顺序是 dgbaechf，则其后序遍历的结点访问顺序是D _____ 。 A. bdgcefha B. gdbecfha C. bdgaechf D. gdbehfca 13. 二叉树为二叉排序树的充分必要条件是其任一结点的值均大于其左孩子的值、 小于其右孩子的值。这种说法__B__ o A.正确 B. 错误 14. 按照二叉树的定义，具有3个结点的二叉树有_。__种。 A. 3 B. 4 C. 5 D. 6 15. 一棵二叉树如图8.10所示，其中序遍历的序列为 第二章基本数据结构及其运算 一、单项选择题 1．数据的基本单位是( B ) A．数据B．数据元素C．数据项D．数据结构 2．在数据结构中，构成数据元素的最小单位称为（D）A．字符B．关键字C．数据元素 D．数据项 3．数据在计算机内的存储形式称为数据的（ D ）A．算法描述B．数据类型 C．逻辑结构D．物理结构 4．数据的逻辑结构可分为（C） A．顺序结构和链式结构B．简单结构和复杂结构C．线性结构和非线性结构D．动态结构和静态结构5．顺序表中的每个元素占m个字节，第一个元素的存储地址为LOC(1)，则任意1个元素i的地址为( B ) A．LOC(1)+i*m B．LOC(1)+(i-1)*m C．LCO(1)+(i+1)*m D．(i-1)*m 6．线性表若采用链表存储，其（D） A．所有结点的地址必须是连续的 B．部分结点的地址必须是连续的 C．所有结点的地址一定不连续 D．所有结点的地址连续、不连续都可以 7．线性表在采用链式存储时，其地址（ C ）A．必须是连续的B．一定是不连续的 C．连续不连续都可以D．部分是连续的 8．下列不属于线性结构的是( C )。 A．单链表B．队列 C．二叉树D．数组 9．链表不具有的特点是( A) A．可随机访问任一元素B．插入删除不需要移动元素 C．不必事先估计存储空间D．所需空间与线性表的长度成正比 10．数据结构反映了数据元素之间的结构关系，链表是一种( D)。 A．顺序存储线性表B．非顺序存储非线性表 C．顺序存储非线性表D．非顺序存储线性表 11．在单链表表示的线性表中，可以从( A )。 A．第一个结点访问到所有结点 B．某个结点访问到所有结点 C．某个结点访问到该结点的所有前趋结点 D．最后一个结点访问到所有结点 12．在一个单链表中，已知指针q所指向的结点是指针p所指向的结点的前驱结点，若在指针q和p所指向的两个结点之间插入指针s指向的结点，则执行( C )。 A．s->link=p->link; p->link=s; B．p->link=s->link; s->link=p; C．q->link=s; s->link=p; D．p->link=s; s->link=q; 13．长度为n的顺序存储的线性表，设在任何位置上删除一个元素的概率相等，则删除一个元素时平均要移动的元素 《数据结构》第二章习题参考答案 一、判断题（在正确说法的题后括号中打“√”，错误说法的题后括号中打“×”） 1、顺序存储方式插入和删除时效率太低，因此它不如链式存储方式好。( × ) 2、链表中的头结点仅起到标识的作用。( × ) 3、所谓静态链表就是一直不发生变化的链表。( × ) 4、线性表的特点是每个元素都有一个前驱和一个后继。( × ) 5、在顺序表中，逻辑上相邻的元素在物理位置上不一定相邻。（×） 6、线性表就是顺序存储的表。（×） 7、课本P84 2.4题 （1）√（2）×（3）×（4）×（5）√（6）×（7）×（8）√ （9）×（10）×（11）√（12）√ 二、单项选择题 1、下面关于线性表的叙述中，错误的是哪一个？（ B ） A．线性表采用顺序存储，必须占用一片连续的存储单元。 B．线性表采用顺序存储，便于进行插入和删除操作。 C．线性表采用链接存储，不必占用一片连续的存储单元。 D．线性表采用链接存储，便于插入和删除操作。 2、链表不具有的特点是（ B ） A．插入、删除不需要移动元素B．可随机访问任一元素 C．不必事先估计存储空间D．所需空间与线性长度成正比 3、(1) 静态链表既有顺序存储的优点，又有动态链表的优点。所以，它存取表中第i个元素的时间与i无关。 (2) 静态链表中能容纳的元素个数的最大数在表定义时就确定了，以后不能增加。 (3) 静态链表与动态链表在元素的插入、删除上类似，不需做元素的移动。 以上错误的是（ B ） A．（1），（2）B．（1）C．（1），（2），(3) D.（2） 4、在单链表指针为p的结点之后插入指针为s的结点，正确的操作是（B）A．p->link =s; s-> link =p-> link; B．s-> link =p-> link; p-> link =s; C．p-> link =s; p-> link =s-> link; D．p-> link =s-> link; p-> link =s; 5、若某线性表最常用的操作是取任一指定序号的元素及其前驱，则利用（C）存储方式最节省时间。 A．单链表B．双链表C．顺序表D．带头结点的双循环链表6、对于顺序存储的线性表，访问结点和增加、删除结点的时间复杂度为（ C ）。A．O(n)，O(n) B. O(n)，O(1) C. O(1)，O(n) D. O(1)，O(1) 7、在一个以 h 为头的单循环链中，p 指针指向链尾的条件是（ A ） A. p->next=h B. p->next=NULL C. p->next->next=h D. p->data=-1 三、填空题 第二章线性表 1、描述一下三个概念的区别：头指针，头结点，首元结点。并给予图示。 2、对于有头结点的单链表，分别写出定位成功时，实现下列定位语句序列。(1)定位到第i 个结点a i ； (2)定位到第i 个结点的前驱a i-1； (3)定位到尾结点； (4)定位到尾结点的前驱。 3、已知L 是有表头结点的单链表，且P 结点既不是首元结点，也不是尾结点，试写出实现下列功能的语句序列。 (1)在P 结点后插入S 结点；(2)在P 结点前插入S 结点；(3)在表首插入S 结点；(4)在表尾插入S 结点 . p=head; p=head; j=0; while ( p && jnext; j++;} p=head; j=0; while ( p && j 4、设计算法：在顺序表中删除值为e 的元素，删除成功，返回1；否则，返回0。 5、设计一个算法，将一个带头节点的数据域依次为a 1，a 2，…，a n （n ≥3）的单链表的所有节点逆置，即第一个节点的数据域变为a n ，…，最后一个节点的数据域为a 1。（注意：先用自然语言描述算法基本思想，然后用类C++语言描述） int Sqlist 2.4已知顺序表L递增有序，试写一算法，将X插入到线性表的适当位置上，以保持线性表的有序性。 解： int InsList(SeqList *L,int X) { int i=0,k; if(L->last>=MAXSIZE-1) { printf("表已满无法插入！")； return(ERROR); } while(i<=L->last&&L->elem[i] } } 2.6已知线性表中的元素（整数）以递增有序排列，并以单链表作存储结构。试写一高效算法，删除表中所有大于mink且小于maxk的元素（若表中存在这样的元素），分析你的算法的时间复杂度（注意：mink和maxk是给定的两个变量，他们的值为任意的整数）。 解： int Delete(Linklist,int mink,int maxk) { Node *p,*q; p=L; while(p->next!=NULL) p=p->next; if(mink>=maxk||L->next->data>=maxk||mink+1=maxk) { printf("参数不合法！"); return ERROR; } else { while(p->next->data<=mink) p=p->next; q=p->next; while(q->data 第2章自测卷答案姓名班级 一、填空（每空1分，共13分） 1. 【严题集 2.2①】在顺序表中插入或删除一个元素，需要平均移动表中一半元素，具体移动的元素个数与表长和该元素在表中的位置有关。 2. 线性表中结点的集合是有限的，结点间的关系是一对一的。 3. 向一个长度为n的向量的第i个元素(1≤i≤n+1)之前插入一个元素时，需向后移动n-i+1 个元素。 4. 向一个长度为n的向量中删除第i个元素(1≤i≤n)时，需向前移动n-i 个元素。 5. 在顺序表中访问任意一结点的时间复杂度均为O(1)，因此，顺序表也称为随机存取的数据结构。 6. 【严题集2.2①】顺序表中逻辑上相邻的元素的物理位置必定相邻。单链表中逻辑上相邻的元素的物理位置不一定相邻。 7. 【严题集2.2①】在单链表中，除了首元结点外，任一结点的存储位置由其直接前驱结点的链域的值指示。 8．在n个结点的单链表中要删除已知结点*p，需找到它的前驱结点的地址，其时间复杂度为O（n）。 二、判断正误（在正确的说法后面打勾，反之打叉）（每小题1分，共10分）（×）1. 链表的每个结点中都恰好包含一个指针。 答：错误。链表中的结点可含多个指针域，分别存放多个指针。 例如，双向链表中的结点可以含有两个指针域，分别存放指向其 直接前趋和直接后继结点的指针。 （×）2. 链表的物理存储结构具有同链表一样的顺序。 错，链表的存储结构特点是无序，而链表的示意图有序。 （×）3. 链表的删除算法很简单，因为当删除链中某个结点后，计算机会自动地将后续的各个单元向前移动。 错，链表的结点不会移动，只是指针内容改变。 （×）4. 线性表的每个结点只能是一个简单类型，而链表的每个结点可以是一个复杂类型。 错，混淆了逻辑结构与物理结构，链表也是线性表！且即使是顺序 表，也能存放记录型数据。 （×）5. 顺序表结构适宜于进行顺序存取，而链表适宜于进行随机存取。 第二章习题 一判断题 1．线性表的逻辑顺序与存储顺序总是一致的。× 2．顺序存储的线性表可以按序号随机存取。 3．顺序表的插入和删除操作不需要付出很大的时间代价，因为每次操作平均只有近一半的元素需要移动。× 4．线性表中的元素可以是各种各样的，但同一线性表中的数据元素具有相同的特性，因此是属于同一数据对象。 5．在线性表的顺序存储结构中，逻辑上相邻的两个元素在物理位置上并不一定紧邻。× 6．在线性表的链式存储结构中，逻辑上相邻的元素在物理位置上不一定相邻。 7．线性表的链式存储结构优于顺序存储结构。 8．在线性表的顺序存储结构中，插入和删除时，移动元素的个数与该元素的位置有关。×9．线性表的链式存储结构是用一组任意的存储单元来存储线性表中数据元素的。 10．在单链表中，要取得某个元素，只要知道该元素的指针即可，因此，单链表是随机存取的存储结构。× 11.线性表中每个元素都有一个直接前驱和一个直接后继。（×） 12.线性表中所有元素的排列顺序必须由小到大或由小到小。（×） 13.静态链表的存储空间在可以改变大小。（×） 14.静态链表既有顺序存储结构的优点，又有动态链表的优点。所以它存取表中第i个元素的时间与i无关。（×） 15.静态链表中能容纳元素个数的最大数在定义时就确定了，以后不能增加。（） 16.静态链表与动态链表的插入、删除操作类似，不需要做元素的移动。（） 17.线性表的顺序存储结构优于链式结构。（×） 18.在循环单链表中，从表中任一结点出发都可以通过前后的移动操作扫描整个循环链表。（×） 19.在单链表中，可以从头结点开始查找任何一个结点。（） 20.在双链表中，可以从任何一结点开始沿同一方向查找到任何其他结点。（×） 二单选题 (请从下列A，B，C，D选项中选择一项) 1．线性表是( ) 。 (A) 一个有限序列，可以为空； (B) 一个有限序列，不能为空； (C) 一个无限序列，可以为空； (D) 一个无序序列，不能为空。 ，在任何位置上插入或删除操作都是等概率的。插n．对顺序存储的线性表，设其长度为2． 入一个元素时平均要移动表中的（）个元素。 (A) n/2 (B) n+1/2 (C) （n -1）/2 (D) n 第二章地理信息系统空间数据结构 2.1 地理空间数据及其特征 【学时安排】 1 学时 【目的要求】 1、掌握地理信息系统的数据类型； 2、理解地理信息系统的数据来源； 3、掌握空间数据的特点。 【重点难点】 地理信息系统的数据类型与特征。 【教学方法与手段】 示例式教学方法，多媒体教学手段。 一、GIS空间数据的来源与类型 空间数据是GIS的核心，也有人称它是GIS的血液，因为GIS的操作对象是空间数据，因此设计和使用GIS 的第一步工作就是根据系统的功能，获取所需要的空间数据，并创建空间数据库。 1、地理数据的来源 GIS中的数据来源和数据类型繁多，概括起来主要有以下几种来源： ⑴地图数据。来源于各种类型的普通地图和专题地图，这些地图的内容丰富，图上实体间的空间关系直观，实体的类别或属性清晰，实测地形图还具有很高的精度，是地理信息的主要载体，同时也是地理信息系统最重要的信息源。 ⑵影像数据。主要来源于卫星遥感和航空遥感，包括多平台、多层面、多种传感器、多时相、多光谱、多角度和多种分辨率的遥感影像数据，构成多源海量数据，也是GIS的最有效的数据源之一。 ⑶地形数据。来源于地形等高线图的数字化，已建立的数字高程模型( DEM和其他实 测的地形数据等。 ⑷属性数据。来源于各类调查报告、实测数据、文献资料、解译信息等。 ⑸元数据。来源于由各类纯数据通过调查、推理、分析和总结得到的有关数据的数据，例如数据来源、数据权属、数据产生的时间、数据精度、数据分辨率、源数据比例尺、数据转换方法等。 2、空间数据的类型 空间数据根据表示对象的不同，又具体分为七种类型(图2-1) ，它们各表示的具体内容 如下： (1) 类型数据。例如考古地点、道路线、土壤类型的分布等。 (2) 面域数据。例如随机多边形的中心点，行政区域界线、行政单元等。 (3) 网络数据。例如道路交点、街道、街区等。 (4) 样本数据。例如气象站、航线、野外样方分布区等。 (5) 曲面数据。例如高程点、等高线、等值区域等。 (6) 文本数据。例如地名、河流名称、区域名称等。 (7) 符号数据。例如点状符号、线状符号、面状符号(晕线) 等。 第一章绪论 一、问答题 1. 什么是数据结构？ 2. 叙述四类基本数据结构的名称与含义。 3. 叙述算法的定义与特性。 4. 叙述算法的时间复杂度。 5. 叙述数据类型的概念。 6. 叙述线性结构与非线性结构的差别。 7. 叙述面向对象程序设计语言的特点。 8. 在面向对象程序设计中，类的作用是什么？ 9. 叙述参数传递的主要方式及特点。 10. 叙述抽象数据类型的概念。 二、判断题（在各题后填写“√”或“×”） 1. 线性结构只能用顺序结构来存放，非线性结构只能用非顺序结构来存放。（） 2. 算法就是程序。（） 3. 在高级语言（如C或 PASCAL）中，指针类型是原子类型。（） 三、计算下列程序段中X=X+1的语句频度 for(i=1;i<=n;i++) for(j=1;j<=i;j++) for(k=1;k<=j;k++) x=x+1; 四、试编写算法，求一元多项式Pn(x)=a0+a1x+a2x2+a3x3+…anxn的值Pn(x0)，并确定算法中的每一语句的执行次数和整个算法的时间复杂度，要求时间复杂度尽可能小，规定算法中不能使用求幂函数。注意：本题中的输入ai(i=0,1,…,n),x和n，输出为Pn(x0)。通常算法的输入和输出可采用下列两种方式之一： （1）通过参数表中的参数显式传递。（2）通过全局变量隐式传递。 试讨论这两种方法的优缺点，并在本题算法中以你认为较好的一种方式实现输入和输出。 第二章线性表 2.1 描述以下三个概念的区别：头指针，头结点，首元素结点。 2.2 填空： （1）在顺序表中插入或删除一个元素，需要平均移动＿＿＿＿元素，具体移动的元 素个数与＿＿插入或删除的位置＿＿有关。 （2）在顺序表中，逻辑上相邻的元素，其物理位置＿＿＿＿＿＿相邻。在单链表中，逻辑上相邻的元素，其物理位置＿＿＿＿＿＿相邻。 （3）在带头结点的非空单链表中，头结点的存储位置由＿＿＿＿＿＿指示，首元素结点的存储位置由＿＿＿＿＿＿指示，除首元素结点外，其它任一元素结点的存储位置由＿＿＿＿指示。 2.3 已知L是无表头结点的单链表，且P结点既不是首元素结点，也不是尾元素结点。按要求从下列语句中选择合适的语句序列。 第二章习题 1.描述以下三个概念的区别：头指针，头结点，首元素结点。 2.填空： （1）在顺序表中插入或删除一个元素，需要平均移动元素，具体移动的元素个数与有关。 （2）在顺序表中，逻辑上相邻的元素，其物理位置相邻。在单链表中，逻辑上相邻的元素，其物理位置相邻。 （3）在带头结点的非空单链表中，头结点的存储位置由指示，首元素结点的存储位置由指示，除首元素结点外，其它任一元素结点的存储位置由指示。3．已知L是无表头结点的单链表，且P结点既不是首元素结点，也不是尾元素结点。按要求从下列语句中选择合适的语句序列。 a. 在P结点后插入S结点的语句序列是：。 b. 在P结点前插入S结点的语句序列是：。 c. 在表首插入S结点的语句序列是：。 d. 在表尾插入S结点的语句序列是：。 供选择的语句有： （1）P->next=S; （2）P->next= P->next->next; （3）P->next= S->next; （4）S->next= P->next; （5）S->next= L; （6）S->next= NULL; （7）Q= P; （8）while(P->next!=Q) P=P->next; （9）while(P->next!=NULL) P=P->next; （10）P= Q; （11）P= L; （12）L= S; （13）L= P; 4.设线性表存于a(1:arrsize)的前elenum个分量中且递增有序。试写一算法，将X插入到线性表的适当位置上，以保持线性表的有序性。 5.写一算法，从顺序表中删除自第i个元素开始的k个元素。 6.已知线性表中的元素（整数）以值递增有序排列，并以单链表作存储结构。试写一高效算法，删除表中所有大于mink且小于maxk的元素（若表中存在这样的元素），分析你的算法的时间复杂度（注意：mink和maxk是给定的两个参变量，它们的值为任意的整数）。 7.试分别以不同的存储结构实现线性表的就地逆置算法，即在原表的存储空间将线性表（a1, a2..., an）逆置为（an, an-1,..., a1）。 （1）以一维数组作存储结构，设线性表存于a(1:arrsize)的前elenum个分量中。 （2）以单链表作存储结构。 8.假设两个按元素值递增有序排列的线性表A和B，均以单链表作为存储结构，请编写算法，将A表和B表归并成一个按元素值递减有序排列的线性表C，并要求利用原表（即A 表和B表的）结点空间存放表C。 一、单选题（每题2 分，共20分） 1. 1.对一个算法的评价，不包括如下（B ）方面的内容。 A．健壮性和可读性B．并行性C．正确性D．时空复杂度 2. 2.在带有头结点的单链表HL中，要向表头插入一个由指针p指向的结 点，则执行( A )。 A. p->next=HL->next; HL->next=p; B. p->next=HL; HL=p; C. p->next=HL; p=HL; D. HL=p; p->next=HL; 3. 3.对线性表，在下列哪种情况下应当采用链表表示？(B ) A.经常需要随机地存取元素 B.经常需要进行插入和删除操作 C.表中元素需要占据一片连续的存储空间 D.表中元素的个数不变 4. 4.一个栈的输入序列为1 2 3，则下列序列中不可能是栈的输出序列的是 ( C ) A. 2 3 1 B. 3 2 1 C. 3 1 2 D. 1 2 3 5. 5.AOV网是一种（ D ）。 A．有向图B．无向图C．无向无环图D．有向无环图 6. 6.采用开放定址法处理散列表的冲突时，其平均查找长度（B）。 A．低于链接法处理冲突 B. 高于链接法处理冲突 C．与链接法处理冲突相同D．高于二分查找 7.7.若需要利用形参直接访问实参时，应将形参变量说明为（D ）参数。 A．值B．函数C．指针D．引用 8.8.在稀疏矩阵的带行指针向量的链接存储中，每个单链表中的结点都具 有相同的（A）。 A．行号B．列号C．元素值D．非零元素个数 9.9.快速排序在最坏情况下的时间复杂度为（D ）。 A．O(log2n) B．O(nlog2n) C．0(n) D．0(n2) 10.10.从二叉搜索树中查找一个元素时，其时间复杂度大致为( C )。 A. O(n) B. O(1) C. O(log2n) D. O(n2) 二、二、运算题（每题 6 分，共24分） 1. 1.数据结构是指数据及其相互之间的______________。当结点之间存在M 对N（M：N）的联系时，称这种结构为_____________________。 2. 2.队列的插入操作是在队列的___尾______进行，删除操作是在队列的 ____首______进行。 3. 3.当用长度为N的数组顺序存储一个栈时，假定用top==N表示栈空，则 表示栈满的条件是___top==0___(要超出才为满)_______________。 4. 4.对于一个长度为n的单链存储的线性表，在表头插入元素的时间复杂度 为____O(1)_____，在表尾插入元素的时间复杂度为____O n________。 《数据结构》第二章练习题 1.单项选择题 2.1链表不具备的特点是（） A 可随机访问任一结点 B 插入删除不需要移动元素 C 不必事先估计存储空间 D 所需空间与其长度成正比 2.2 不带头节点的单链表head为空的判定条件是（） A head==NULL B head->next==NULL C head->next==head D head!=NULL 2.3带头节点的单链表head为空的判定条件是（） A head==NULL B head->next==NULL C head->next==head D head!=NULL 2.4 带头结点的双循环链表L为空的条件是（） A L==NULL B l->next->==NULL C L->prior==NULL D L->next==L 2.5 非空的循环单链表head尾结点（由P所指向）满足（) A P->next==NULL B P==NULL C P->next==head D P==head 2.6在双循环链表中的P所指结点之前插入s所指结点的操作是（） A p->prior=s;s->next=p;p->prior>next=s;s->prior=p->prior; B p->prior=s;p->prior>next=s;s->next=p;s->prior=p->prior; C s->next=p;s->prior=p->prior; p->prior=s;p->right->next=s; D s->next=p;s->prior=p->prior;p->prior->next=s;p->prior=s; 2.7若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一个结点，则采用（）存储方式最节省运算时间 A 单链表 B 给出表头指针的单循环链表 C 双链表 D 带头结点的双循环链表 2.8某线性表最常用的操作时在最后一个结点之后插入一个结点或删除第一个结点，故采用（）存储方式最节省运算时间 A 单链表B仅有头结点的单循环链表 数据结构课程作业_A 交卷时间：2017-08-09 10:08:51 一、单选题 1. (7分)设有一个二维数组A[m][n]，假设A[0][0]存放位置在644(10)，A[2][2]存放位置在676(10)，每个元素占一个空间，问A[3][3](10)存放在什么位置脚注(10)表示用10进制表示。 A. 688 B. 678 C. 692 D. 696 纠错 得分： 7 知识点：第五章 展开解析 答案 C 解析第五章第二节综合题目 2. (7分)若有18个元素的有序表存放在一维数组A[19]中，第一个元素放A[1]中，现进行二分查找，则查找A［3］的比较序列的下标依次为( ) A. 1，2，3 B. 9，5，2，3 C. 9，5，3 D. 9，4，2，3 纠错 得分： 0 知识点：第九章 展开解析 答案 D 解析第九章第一节有序表的查找 (7分)设某完全无向图中有n个顶点，则该完全无向图中有（）条边。 A. n(n-1)/2 B. n(n-1) C. n2 D. n2-1 纠错 得分： 7 知识点：第七章 展开解析 答案 A 解析第七章第一节综合题目 4. (7分)若在任意一棵二叉树中，有n0个叶子结点，有n2个度为2的结点，则：n0=_____ A. n2+1 B. n2-1 C. n2+2 D. n2-2 纠错 得分： 7 知识点：第六章 展开解析 答案 A 解析第六章第二节二叉树的性质 5. (7分)栈的插入和删除操作在（）进行。 A. 栈顶 B. 栈底 C. 任意位置 D. 指定位置 得分： 7 知识点：第三章 展开解析 答案 A 解析第三章第一节栈的表示和实现 6. (7分)设有序表中有1000个元素，则用二分查找查找元素X最多需要比较（）次。 A. 25 B. 10 C. 7 D. 1 纠错 得分： 7 知识点：第九章 展开解析 答案 B 解析第九章第一节有序表的查找 7. (7分)设某棵二叉树的高度为10，则该二叉树上叶子结点最多有（）。 A. 20 B. 256 C. 512 D. 1024 纠错 得分： 7 知识点：第六章 展开解析 答案 C 解析第六章第六节二叉树的性质 数据结构（C语言版）（第2版） 课后习题答案 李冬梅 2015.3 目录 第1章绪论 (1) 第2章线性表 (5) 第3章栈和队列 (13) 第4章串、数组和广义表 (26) 第5章树和二叉树 (33) 第6章图 (42) 第7章查找 (54) 第8章排序 (65) 第1章绪论 1．简述下列概念：数据、数据元素、数据项、数据对象、数据结构、逻辑结构、存储结构、抽象数据类型。 答案： 数据：是客观事物的符号表示，指所有能输入到计算机中并被计算机程序处理的符号的总称。如数学计算中用到的整数和实数，文本编辑所用到的字符串，多媒体程序处理的图形、图像、声音、动画等通过特殊编码定义后的数据。 数据元素：是数据的基本单位，在计算机中通常作为一个整体进行考虑和处理。在有些情况下，数据元素也称为元素、结点、记录等。数据元素用于完整地描述一个对象，如一个学生记录，树中棋盘的一个格局（状态）、图中的一个顶点等。 数据项：是组成数据元素的、有独立含义的、不可分割的最小单位。例如，学生基本信息表中的学号、姓名、性别等都是数据项。 数据对象：是性质相同的数据元素的集合，是数据的一个子集。例如：整数数据对象是集合N={0，±1，±2，…}，字母字符数据对象是集合C={‘A’，‘B’，…，‘Z’，‘a’，‘b’，…，‘z’}，学生基本信息表也可是一个数据对象。 数据结构：是相互之间存在一种或多种特定关系的数据元素的集合。换句话说，数据结构是带“结构”的数据元素的集合，“结构”就是指数据元素之间存在的关系。 逻辑结构：从逻辑关系上描述数据，它与数据的存储无关，是独立于计算机的。因此，数据的逻辑结构可以看作是从具体问题抽象出来的数学模型。 存储结构：数据对象在计算机中的存储表示，也称为物理结构。 抽象数据类型：由用户定义的，表示应用问题的数学模型，以及定义在这个模型上的一组操作的总称。具体包括三部分：数据对象、数据对象上关系的集合和对数据对象的基本操作的集合。 2．试举一个数据结构的例子，叙述其逻辑结构和存储结构两方面的含义和相互关系。 答案： 例如有一张学生基本信息表，包括学生的学号、姓名、性别、籍贯、专业等。每个学生基本信息记录对应一个数据元素，学生记录按顺序号排列，形成了学生基本信息记录的线性序列。对于整个表来说，只有一个开始结点(它的前面无记录)和一个终端结点(它的后面无记录)，其他的结点则各有一个也只有一个直接前趋和直接后继。学生记录之间的这种关系就确定了学生表的逻辑结构，即线性结构。 这些学生记录在计算机中的存储表示就是存储结构。如果用连续的存储单元(如用数组表示)来存放这些记录，则称为顺序存储结构；如果存储单元不连续，而是随机存放各个记录，然后用指针进行链接，则称为链式存储结构。 即相同的逻辑结构，可以对应不同的存储结构。 3．简述逻辑结构的四种基本关系并画出它们的关系图。 试卷一 一、单选题（每题 2 分，共20分） 1. 对一个算法的评价，不包括如下（）方面的内容。 A．健壮性和可读性B．并行性C．正确性D．时空复杂度 2. 在带有头结点的单链表HL中，要向表头插入一个由指针p指向的结点，则执行( )。 A. p->next=HL->next; HL->next=p; B. p->next=HL; HL=p; C. p->next=HL; p=HL; D. HL=p; p->next=HL; 3. 对线性表，在下列哪种情况下应当采用链表表示？( ) A.经常需要随机地存取元素 B.经常需要进行插入和删除操作 C.表中元素需要占据一片连续的存储空间 D.表中元素的个数不变 4. 一个栈的输入序列为1 2 3，则下列序列中不可能是栈的输出序列的是( ) A. 2 3 1 B. 3 2 1 C. 3 1 2 D. 1 2 3 5. AOV网是一种（）。 A．有向图B．无向图C．无向无环图D．有向无环图 7. 若需要利用形参直接访问实参时，应将形参变量说明为（）参数。 A．值B．函数C．指针D．引用 8. 在稀疏矩阵的带行指针向量的链接存储中，每个单链表中的结点都具有相同的（）。 A．行号B．列号C．元素值D．非零元素个数 二、填空题（每空1分，共28分） 1. 数据结构是指数据及其相互之间的______________。当结点之间存在M对N（M：N）的联系时，称这种结构为_____________________。 2. 队列的插入操作是在队列的___尾______进行，删除操作是在队列的____首______进行。 3. 当用长度为N的数组顺序存储一个栈时，假定用top==N表示栈空，则表示栈满的条件是___top==0_____________。 4. 对于一个长度为n的单链存储的线性表，在表头插入元素的时间复杂度为_________，在表尾插入元素的时间复杂度为____________。 7. 二叉树是指度为2的____________________树。一棵结点数为N的二叉树，其所有结点的度的总和是_____________。 8. 对一棵二叉搜索树进行中序遍历时，得到的结点序列是一个______________。对一棵由算术表达式组成的二叉语法树进行后序遍历得到的结点序列是该算术表达式的__________________。 9. 对于一棵具有n个结点的二叉树，用二叉链表存储时，其指针总数为_____________个，其中_______________个用于指向孩子，_________________个指针是空闲的。 10. 若对一棵完全二叉树从0开始进行结点的编号，并按此编号把它顺序存储到一维数组A中，即编号为0的结点存储到A[0]中。其余类推，则A[ i ]元素的左孩子元素为________,右孩子元素为 数据结构习题 第一章绪论 1.6 在程序设计中，常用下列三种不同的出错处理方式： 1) 用exit语句终止执行并报告错误； 2) 以函数的返回值区别正确返回或错误返回； 3) 设置一个整形变量的函数参数以区别正确返回或某种错误返回。 试讨论这三种方法各自的优缺点。 1.7 在程序设计中，可采用下列三种方法实现输出和输入： 1) 通过scanf和printf语句； 2) 通过函数的参数显示传递； 3) 通过全局变量隐式传递。 试讨论这三种方法的优缺点。 1.8 设n为正整数。试确定下列各程序段中前置以记号@的语句的频度： 5) for (i = 1; i <= n; i++ ) { for (j = 1; j <= i; j++) { for (k = 1; k <= j; k++) { @ x += delta; } } } 答案：n*(n+1)*(n+2) =1+（1+2）+（1+2+3）+...+(1+2+3+...+n) =∑ =+ n i i i 1 2 / )1 ( * =1/2*∑ =+ n i i i i 1 * =n*(n+1)*(2n+1)/12 +n*(n+1)/4 =n*(n+1)*(n+2)/6 7) x = n; //n是不小于1的常数 y = 0; while (x >= (y + 1) * (y + 1)) { @ y++; } 答案：n向下取整 8) x = 91; y = 100; while (y > 0) { @ if (x > 100) { x -= 10; y--;} else { x++; } } 答案：if 执行次数为1100， if 判断内部执行为100次 1.19 试编写算法，计算i!·2i （i = 0, 1, …, n-1）的值并分别存入数组a[arrsize]的各个分量中。假设计算机中允许的整数最大值为MAXINT ，则当n > arrsize 或对某个k （0 ≤ k ≤ n-1）使k!·2k > MAXINT 时，应按出错处理。注意选择你认为较好的出错处理方法。 1.20 试编写算法求一元多项式∑==n i i i x a x 0n )(P 的值P n (x 0)，并确定算法中每一语句的执行 次数和整个算法的时间复杂度。注意选择你认为较好的输入和输出方法。本题的输入为a i （i=0, 1, …, n ）、x 0和n ，输出为P n (x 0)。数据结构第二章试题
数据结构书面作业练习题
基本数据结构及其运算习题
《数据结构》第二章习题参考答案 殷人昆版
数据结构第二章线性表测试题
数据结构第二章课后习题题解
数据结构 第二章自测题答案
数据结构第2章基础习题 作业
地理信息系统空间数据结构
数据结构(第二版)习题
(完整版)数据结构课后习题及解析第二章
数据结构试题及答案
数据结构第二章练习题 - 副本
数据结构课程作业
数据结构(C语言版)(第2版)课后习题答案
数据结构试题及答案修2
数据结构作业
相关主题
文本预览