资源描述
2023数据构造习题集答案 - 数据构造习题集答案 2023年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 &jnext; +j; if(!(p-next)|ji-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|ji?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;idata); /输入元素值 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 next; /q是最后一个不大于mink的元素, /p是第一个大于mink的元素 if(!p) return ERROR; /假如没有比mink更大的元素 while(p & p-data 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-datadata) pc-next=pa;pc=pa;pa=pa-next; elsepc-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 第 5 页 共 5 页
展开阅读全文