《数据结构》习题集答案
2014年8月
第一章-第五章 参考答案
一.单选与填空
1. n(n-1)/2 2.O(n) 3.常数阶 O(n) 4. C 5.A 6.C 7.D 8.A 9. O(n) 10.B 11.C 12.A 13.A 14.B 15.C 16.L->next==NULL 17. P->prior->next=P->next P-> next -> prior =P->prior 18.B 19.C 20.3 21.C 22.A 23.A 24.C 25. D 26.D
27. I have a dream , ave 28. 6 29.A 30.D 31.(a,b) (c,( )) 32.B 33.C 二、算法题
1. 程序的功能: 对长度大于等于2的单链表,将首元结点插入到表尾。
2. (1) 栈中的数据元素逆置 (2) 如果栈中存在元素e,将其
从栈中清除。
3. 程序的运行结果:(1) chris (2) card 4.-10 题答案:. #define OK 1 #define ERROR 0 typedef int Status; typedef struct LNode{ int data;
struct LNode *next; }LNode,*LinkList; 4. 题答案
int Length(LinkList L)//求链表的长度 { k=0; p=L;
while (p->next) { p=p->next; k++;} return k; }//Length
5. 题答案
LNode* Locate(LinkList L, Elemtype x)//链表上的元素查找,返回指针
{ p=L->next;
while (p&&p->data!=x) p=p->next; return p; }//Locate 6. 题答案
Status ListDelete_L(LinkList &L,int i,ElemType &e){
//将线性表L中第i个数
据元素删除
p=L;j=0;
while(p->next &&j p=p->next; ++j; } if(!(p->next)||j>i-1) return ERROR; //删除位置不合理 q=p->next; //临时保存被删结点的地址以备释放 p->next=q->next; //改变删除结点前驱结点的指针域 e=q->data; //保存删除结点的数据域 free(q); //释放删除结点的空间 return OK; }//ListDelete_L 7. 题答案 Status ListInsert_L(LinkList &L,int i,ElemType e){ //在第i个元素之前插入数 据元素e p=L;j=0; while(p&&jnext;++j;} //寻找第i?1个结点 if(!p||j>i?1)return ERROR; //i大于表长 + 1或者小于1 s= (LinkList) malloc ( sizeof (LNode)); //生成新结点s s->data=e; //将结点s的数据域置为e s->next=p->next; //将结点s插入L中 p->next=s; return OK; }//ListInsert_L 8. 题答案 void CreateList_L(LinkList &L,int n){ //正位序输入n个元素的值,建立带表头结点的单链表L L=(LinkList) malloc (sizeof (LNode)); L->next=NULL; r=L; //尾指针r指向头结点 for(i=0;i p = (LinkList) malloc (sizeof (LNode)); //生成新结点 scanf(&p->data); //输入元素值 p->next=NULL; r->next=p; //插入到表尾 r=p; //r指向新的尾结点 } }//CreateList_L 9. 题答案 Status Delete_Between(Linklist &L,int mink,int maxk)//删除元素递增排列的链表L中值大于mink且小于maxk的所有元素 { q=L; p =L->next; while(p && p->data <= mink ){ q=p;p = p->next;} //q是最后一个 不大于mink的元素, //p是第一个大于mink的元素 if(!p) return ERROR; //如果没有比mink更大的元素 while(p && p->data < maxk) { q->next = p->next; free(p); p =q->next;} return OK; }//Delete_Between 10. 题答案 void MergeList_L(LinkList &La,LinkList &Lb,LinkList &Lc){ pa=La->next; pb=Lb->next; pc=Lc=La; //用La的头结点作为Lc的头结点 while(pa && pb){ if(pa->data<=pb->data){ pc->next=pa;pc=pa;pa=pa->next;} else{pc->next=pb; pc=pb; pb=pb->next;} pc->next=pa?pa:pb; //插入剩余段 free(Lb); //释放Lb的头结点 } 第六章 参考答案: 一.单选与填空 1.C 2. 150 3.C 4. A 5. D 6. D 7. B 8. A 9. B 10. 1.95 11. B 二.解答题 1. (1)先序遍历:GADEFBC;二叉树的形态见左下图; (2)对应的树见右下图 2.(1)画出该二叉树; (2)画出对应的二叉树 aa A A bkbc bA bA clef d A A A A edhg A gA A f hi A A g i j