数据结构1-5章习题参考答案

《数据结构1-5章习题参考答案》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、第1章绪论—、填空题01、【操作对象】【关系和运算】02、【数据元索】【关系】03、【逻辑结构】【存储结构】【运算】04、【线性结构】【非线性结构】05、【一对一】【一对多】【多对多】06、【没有】【没有】07、【前驱】【1】【后续】【任意多个】08、【任意多个】09、【顺序】【链式】【索引】【散列】10、【集合】【线性结构】【树形结构】【阁状结构】11、【插入】【删除】【修改】【齊找】【排序】12、【时间】【空间】13、【吋间复杂度】【空间复杂度】14、【映射】15、【冇穷性】【确定性】【可行性】16、[n+1][n][n(n+3)/2

2、][n(n+l)/2]17、【n(n+l)(n+2)/6】【O(n3)】18、【0(1Og2)】19、【⑽沁么)】20、【0(10§2)】21、【(n+3)(n-2)/2】22、【n(n-l)/2】二、判断题01-05.XXX7X06-10、XVXXX11_12、7X三、单项选择题B01BD02A03C04C05八06C07B08A09C10B11A12C13D14A15C16四、分析下面各程序段的时间复杂度01、o(mxn)z202、0(A2)03、答：o(n2)(M、答：0(log/)五、设有数据逻辑结构S-(D，R)，试按各小题所给

3、条件画出这些逻辑结构的阁示，并确定相对丁•关系R，哪些结点足开始结点，哪些结点是终端结点？01、此图为线性结构dl—d2—d3—d4dl—无直接前驱，是首结点d4-无直接后继是尾结点02、此图为树形结构dl—无直接前驱，是根结点d2,d5,d7,d9—无直接后继是叶子结点03、此图为图形结构dl，d2—无直接前驱，是开始结点d6,d7—无直接后继是终端结点六、简述题01、什么是数据结构？答：数据结构是一门研究非数值讣算的程序设讣问题中计算机的操作对象以及它们之间的关系和运算等的学科。02、顺序存储结构和链式存储结构的特点是什么？答：顺序存

4、储结构足指数据索的逻辑存储顺序和计算机中的物理存储顺序一致，即数据占用一段连续的存储甲.元，该存储结构便于实现在查找数裾元素吋的地址定位，但缺点是在插入和删除操作吋需要移动大S的数据元素。链式存储结构是指数据元素在计算机屮A用不连续的存储单元，通过指针指向表示其先)5顺序，该存储结构缺点是在杳找数据元素时耍通过指针的链接关系冰能找到所要的数据素，优点在于插入和删除操作时，不需要移动人量数据元素，只需要改变其指向关系即可。第2章线性表一、填空题01、【顺序】02、【(n-l)/2】03、【n/2】【表长】【该元素在表屮的位置】04、【有限】

5、【一对一】05、【n-i+1】06、【n-i】07、【0⑴】【随机存取】08、【必定相邻】【未必相邻】09、【W直接前驱结点的链域值】10、【前驱结点的地址】【O(n)】11、[py->next=px->next;px->next=py;]12、【在第一个元素之前插入％素和删除第一个结点】13、【0⑴】【0(n)】14、[f->ncxt=p->ncxt;f-〉prior=p;p->next->prior=f;p->ncxt=f;]15、【p-〉prior】【s-〉prior-〉next】16、【指针】17、【1】【2】18、【从任一结点H

6、i发都可访问到链表中每一个元素】19、[u=p-〉next;p->next=u~>next;free(u);】20、【l，〉next-〉next==L】21、[p->next!=null】22、[L->next==L&&L-〉prior==L】23、[s->next=p->next;p->next=s;]二、判断题01-05、XXXXX06-10、XXXXX1卜15、X77XX16-20、XXXX7三、单项选择题C01B02A03B04A05A061)07BOSC09D10DllA12B13C14C15A16A17B18D19B20C21

7、A22C23A24B25C26C27C28B29B30A311)32A33四、简述题1、按课本定义，写出顺序表的存储结构。typedefstructnode{ElemType*elem;intlength;}SqList2、按课笨定义，写出链表的存储结构。typedefstructNode{ElemTypedata;structNode氺next;}Node,*LinkList;五、代码填空题01、【s-〉data=e】【s-〉next=p-〉next】【p-〉next=s】02、【q=p—〉next】【p-〉next=q-〉next】【

8、free(q)】03、【L—〉next=NL:LL】【p-〉next=L—〉next】【L—〉next=p】04、【q-〉next=p】【q=p】【p-〉next=NULL】05、【L==NU