数据结构期末复习习题(含答案).docVIP

第一章习题 一、求下列程序段的时间复杂度。 1. x=0; for(i=1;in;i++) for(j=i+1;j=n;j++) x++; 2. x=0; for(i=1;in;i++) for(j=1;j=n-i;j++) x++; 3. int i,j,k; for(i=0;in;i++) for(j=0;j=n;j++) { c[i][j]=0; for(k=0;kn;k++) c[i][j]=a[i][k]*b[k][j] } 4. i=n-1; while((i=0)A[i]!=k)) j--; return (i); 5. fact(n) { if(n=1) return (1); else return (n*fact(n-1)); } 二、写一个算法，返回一个数组中所有元素被第一个元素除的结果 一、 O() 2. O() 3. O(n) 4. O(n) 5. O(n) 二、void DivArray(int * pArray ,int size) { if (size = 0) return ; if (pArray[0] == 0) return; for (int i=size-1;i=0;i--) { pArray[i] /=pArray[0]; } } 线性表习题 一、单项选择题 1. 线性表是________。 A．一个有限序列，可以为空 B．一个有限序列，不可以为空 C．一个无限序列，可以为空 D．一个无限序列，不可以为空 2. 在一个长度为n的顺序表中删除第i个元素(0=i=n)时，需向前移动 个元素。 A．n-i B．n-i+l C．n-i-1 D．i 3. 线性表采用链式存储时，其地址________。 A．必须是连续的 B．一定是不连续的 C．部分地址必须是连续的 D．连续与否均可以 4. 从一个具有n个结点的单链表中查找其值等于x的结点时，在查找成功的情况下，需平均比较________个元素结点。 A．n/2 B．n C．（n+1）/2 D．（n-1）/2 5. 在双向循环链表中，在p所指的结点之后插入s指针所指的结点，其操作是____。 A． p-next=s; s-prior=p; p-next-prior=s; s-next=p-next; B． s-prior=p; s-next=p-next; p-next=s; p-next-prior=s; C． p-next=s; p-next-prior=s; s-prior=p; s-next=p-next; D． s-prior=p; s-next=p-next; p-next-prior=s; p-next=s; 6. 设单链表中指针p指向结点m，若要删除m之后的结点（若存在），则需修改指针的操作为________。 A．p-next=p-next-next; B．p=p-next; C．p=p-next-next; D．p-next=p; 7. 在一个长度为n的顺序表中向第i个元素(0 in+l )之前插入一个新元素时，需向后移动______个元素。 A．n-i B．n-i+l C．n-i-1 D．i 8. 在一个单链表中，已知q结点是p结点的前趋结点，若在q和p之间插入s结点，则须执行 A．s-next=p-next; p-next=s B．q-next=s; s-next=p C．p-next=s-next; s-next=p D．p-next=s; s-next=q 9. 以下关于线性表的说法不正确的是______。 ? 线性表中的数据元素可以是数字、字符、记录等不同类型。线性表中包含的数据元素个数不是任意的。线性表中的每个结点都有且只有一个直接前趋和直接后继。存在这样的线性表：表中各结点都没有直接前趋和直接后继。1. 线性表是一种典型的_________结构。 2在一个长度为n的顺序表第i个元素前插入一个元素，要后移____个元素。顺序表中逻辑上相邻的元素的物理位置________。4. 要从一个顺序表删除一个元素时，被删除元素之后的所有元素均需_______一个位置，移动过程是从_______向_______依次移动每一个元素。 5. 在线性表的顺序存储中，元素之间的逻辑关系是通过_______决定的；在线性表的链接存储中，元素之间的逻辑关系是通