教材第2章部分习题参考解答.docVIP

教材第二章部分习题参考解答 一、单选题 1. B 2. A 3. C 4. B 5. D 6. C 二、填空题 1．值 指针 2．(38,56,25,60,42,74) 3. O(n) O(1) 4. O(1) O(n) 5. i-1 i+1 6. p-next a[p].next 7. 表头 8．前驱 后继 9．表尾 表头 10．HL-next==NULL HL-next==HL 11. a[i].next=a[1].next; a[1].next=i; 12. i=a[1].next; a[1].next=a[i].next; 13. p=a[i].next; a[i].next=a[p].next; i=p; 14. a[j].next=a[i].next; a[i].next=j; 三、普通题 第1小题 1. (79, 62, 34, 57, 26, 48) 2. (26, 34, 48, 57, 62, 79) 3. (48, 56, 57, 62, 79, 34) 4. (56, 57, 79, 34) 5. (26, 34, 39, 48, 57, 62) 第2小题 分析：为了排版方便，假定采用以下输出格式表示单链表示意图：每个括号内的数据表示一个元素结点，其中第一个数据为元素值，第二个数据为后继结点的指针，第一个元素结点前的数值为表头指针。 1. (7(79,6), (62,5), (34,4), (57,3), (26,2), (48,0)) 2. (3(26,5), (34,2), (48,4), (57,6), (62,7), (79,0)) 3. (2(48,8), (56,4), (57,6), (62,7), (79,5), (34,0)) 4. (8(56,4), (57,7), (79,5), (34,0)) 第3小题 1. ElemType DMValue(List L) //从线性表中删除具有最小值的元素并由函数返回，空出的位置 //由最后一个元素填补，若线性表为空则显示出错信息并退出运行。 { if(ListEmpty(L)) { cerrList is Empty!endl; exit(1); } ElemType x; x=L.list[0]; int k=0; for(int i=1; iL.size; i++) { ElemType y=L.list[i]; if (yx) {x=y; k=i; } } L.list[k]=L.list[L.size-1]; L.size--; return x; } 2. int Delete1(List L, int i) //从线性表中删除第i个元素并由函数返回。 { if(i1 || iL.size) { cerrIndex is out range!endl; exit(1); } ElemType x; x=L.list[i-1]; for(int j=i-1; jL.size-1; j++) L.list[j]=L.list[j+1]; L.size--; return x; 3. void Insert1(List L, int i, ElemType x) //向线性表中第i个元素位置插入一个元素。 { if(i1 ||iL.size+1) { cerrIndex is out range!endl; exit(1); }