西南交大大数据结构主观题作业

《西南交大大数据结构主观题作业》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、实用文档弘成无锡数字化学习中心批次层次：专升本专业：计算机科学与技术姓名：刘鹏亮学号：15940673实用文档第一次作业三、主观题(共3道小题)14. 数据的物理结构包括        的表示和            的表示。参考答案：线性结构 , 非线性结构 15. 数据逻辑结构包括         、           、        和         四种，树结构和图结构统称为             。参考答案： 集合   、  线性结构    、  树    、 图 、非线性结构 16. 数据结构研究的是      和          以及它们之间的相互关系，并对于这

2、种结构定义相应的          ，设计出相应的             。参考答案： 逻辑结构 ，   物理结构  ， 运算      ，算法第二次作业三、主观题(共22道小题)24. 向一个长度为n的顺序表中的第i个元素之前插入一个元素时，需要向后移动个元素。参考答案：n-i+1 25. 在一个长度为n的顺序表中删除第i个元素时，需要向前移动        元素。参考答案： n-i 26. 在单链表中设置头结点的作用是            。实用文档参考答案：简单插入、删除算法   27. 在单链中要删除某一指定结点，必须找到该结点的         结点。参考答案：直接前驱2

3、8. 访问单链表中的结点，必须沿着        依次进行。参考答案：指针域29. 在双链表中每个结点有两个指针域，一个指向      ，一个指向      。参考答案：直接前驱结点   ，直接后继结点   30. 在            链表中，删除最后一个结点的算法时间复杂度为O(1)。参考答案： 双向循环 31. 访问一个线性表中具有给定值的时间复杂度的数量级是             。参考答案：O(n)32. 由n个数据元素生成一个顺序表，若每次都调用插入算法把一个元素插入到表头，则整个算法的时间复杂度为            ，若每次都调用插入算法把一个元素插入到表尾，则

4、整个算法的时间复杂度为          。参考答案：O(n)    ， O(n2) 33. 在           链表中，可以用表尾指针代替表头指针。参考答案： 双向 34. 在        链表中，可以用表尾指针代替表头指针。参考答案： 双向35. 根据n个数据元素建立对应的顺序表和单链表存储结构，其算法的时间复杂度最好的情况是     ，最坏的情况是         。参考答案：O(n) ， O(n2)  36. 求线性表的顺序存储和链式存储的长度的算法时间复杂度分别是          和          。参考答案：O(1)  ,    O(n) 实用文档37. 在一个

5、带头结点的单链表中，在表头插入或删除与在其他位置插入或删除，其操作过程是否相同？           。参考答案：相同  38. 在一个不带头结点的单链表中，在表头插入或删除与在其他位置插入或删除，其操作过程是否相同？             。参考答案：不相同39. 阐述顺序表和链表存储方式的特点。参考答案：顺序表存储方式为数据分配连续的存储单元，数据元素按逻辑顺序依次存储到相应存储单元中，使得逻辑相邻的数据元素物理也相邻，因此可以实现随即访问线性表的数据元素，即数据访问的时间复杂度为O(1)。链表存储方式分配的存储单元可以不连续，通过每个结点的指针域来表示数据元素之间的逻辑关系，只

6、能顺序访问线性表中的数据元素。40. 若频繁地对一个线性表进行插入和删除操作，则该线性表宜采用何种存储结构，为什么？参考答案：若频繁地对一个线性表进行插入和删除操作，则该线性表宜采用链式存储结构。因此链式存储结构在插入和删除数据元素时不需要移动数据元素，只需要修改结点的指针域就可以改变数据元素之间的逻辑关系。41. 在单链表、双向循环链表和单循环链表中，若仅知道指针p指向某结点，不知道头指针，能否将结点p从相应的链表中删除？若可以，时间复杂度各为多少。参考答案：要实现删除p结点的操作，必须找到其前驱结点，修改其指针域的值使其指向p的后继结点，以实现删除结点p。单链表不行，因此不知道头指

7、针就无法找到结点p的前驱结点。双向循环链表和单循环链表可以可以实现删除p结点。单循环链表删除p结点的时间复杂度为O(n)，双循环链表删除P结点的时间复杂度为O(1)。42. 对链表设置头结点的作用是什么？参考答案：对带头结点的链表，在表的任何结点之前插入结点或删除任何位置的结点，所要做的都是修改前一个结点的指针域，因为在带头结点的链表中任何元素结点都有前驱结点。如果没有头结点，在首元结点前插入结点或删除首元结点都要修改头指针，其算法要比不带头结