欢迎来到天天文库
浏览记录
ID:33751685
大小:55.64 KB
页数:14页
时间:2019-02-28
《西南交大数据结构主观题作业》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库。
1、弘成无锡数字化学习中心批次层次:专升本专业:计算机科学与技术姓名:刘鹏亮学号:1594067314/14第一次作业三、主观题(共3道小题)14. 数据的物理结构包括 的表示和 的表示。参考答案:线性结构 , 非线性结构 15. 数据逻辑结构包括 、 、 和 四种,树结构和图结构统称为 。参考答案: 集合 、 线性结构 、 树 、 图 、非线性结构 16. 数据结构研
2、究的是 和 以及它们之间的相互关系,并对于这种结构定义相应的 ,设计出相应的 。参考答案: 逻辑结构 , 物理结构 , 运算 ,算法第二次作业三、主观题(共22道小题)24. 向一个长度为n的顺序表中的第i个元素之前插入一个元素时,需要向后移动个元素。参考答案:n-i+1 25. 在一个长度为n的顺序表中删除第i个元素时,需要向前移动 元素。参考答案: n-i 26. 在单链表中设置头结点的作用是
3、 。参考答案:简单插入、删除算法 27. 在单链中要删除某一指定结点,必须找到该结点的 结点。参考答案:直接前驱28. 访问单链表中的结点,必须沿着 依次进行。参考答案:指针域29. 在双链表中每个结点有两个指针域,一个指向 ,一个指向 。参考答案:直接前驱结点 ,直接后继结点 30. 在 链表中,删除最后一个结点的算法时间复杂度为O(1)。参考答案: 双向循环 31. 访问一个线性表中具有给定值的时间复杂度的数量级是
4、 。参考答案:O(n)32. 由n个数据元素生成一个顺序表,若每次都调用插入算法把一个元素插入到表头,则整个算法的时间复杂度为 ,若每次都调用插入算法把一个元素插入到表尾,则整个算法的时间复杂度为 。参考答案:O(n) , O(n2) 33. 在 链表中,可以用表尾指针代替表头指针。14/14参考答案: 双向 34. 在 链表中,可以用表尾指针代替表头指针。参考答案: 双向35. 根据n个数据元素建立对应的
5、顺序表和单链表存储结构,其算法的时间复杂度最好的情况是 ,最坏的情况是 。参考答案:O(n) , O(n2) 36. 求线性表的顺序存储和链式存储的长度的算法时间复杂度分别是 和 。参考答案:O(1) , O(n) 37. 在一个带头结点的单链表中,在表头插入或删除与在其他位置插入或删除,其操作过程是否相同? 。参考答案:相同 38. 在一个不带头结点的单链表中,在表头插入或删除与在其他位置插入或删除,其操作过程是否相
6、同? 。参考答案:不相同39. 阐述顺序表和链表存储方式的特点。参考答案:顺序表存储方式为数据分配连续的存储单元,数据元素按逻辑顺序依次存储到相应存储单元中,使得逻辑相邻的数据元素物理也相邻,因此可以实现随即访问线性表的数据元素,即数据访问的时间复杂度为O(1)。链表存储方式分配的存储单元可以不连续,通过每个结点的指针域来表示数据元素之间的逻辑关系,只能顺序访问线性表中的数据元素。40. 若频繁地对一个线性表进行插入和删除操作,则该线性表宜采用何种存储结构,为什么?参考答案:若频繁地对
7、一个线性表进行插入和删除操作,则该线性表宜采用链式存储结构。因此链式存储结构在插入和删除数据元素时不需要移动数据元素,只需要修改结点的指针域就可以改变数据元素之间的逻辑关系。41. 在单链表、双向循环链表和单循环链表中,若仅知道指针p指向某结点,不知道头指针,能否将结点p从相应的链表中删除?若可以,时间复杂度各为多少。参考答案:要实现删除p结点的操作,必须找到其前驱结点,修改其指针域的值使其指向p的后继结点,以实现删除结点p。单链表不行,因此不知道头指针就无法找到结点p的前驱结点。双向循环链表和单循环链表可以
8、可以实现删除p结点。单循环链表删除p结点的时间复杂度为O(n),双循环链表删除P结点的时间复杂度为O(1)。42. 对链表设置头结点的作用是什么?参考答案:对带头结点的链表,在表的任何结点之前插入结点或删除任何位置的结点,所要做的都是修改前一个结点的指针域,因为在带头结点的链表中任何元素结点都有前驱结点。如果没有头结点,在首元结点前插入结点或删除首元结点都要修改头指针,其算法要比不带头结点的算法复杂
此文档下载收益归作者所有