资源描述：
《数据结构概论作业2.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、一、选择1、用单链表方式存储的线性表,存储每个结点需要两个域,一个是数据域,另一个是(B)A.当前结点所在地址域.B.指针域.C.空指针域.D.空闲域.2、在具有n个结点的单链表中,实现(A)的操作,其算法的时间复杂度是o(n).A.遍历链表和求链表的第i个结点.B.在地址为p的结点之后插入一个结点.C.删除开始结点D.删除地址为p的结点的后继结点.3、单链表的存储密度(C).A.大于1B.等于1C.小于1D.不确定4、已知一个顺序存储的线性表,设每个结点需占m个存储单元,若第一个结点的地址为da1,则第i个结点的地址为(A)A.da1+(i-1)
2、*m B.da1+i*mC.da1-i*mD.da1+(i+1)*m5、在n个结点的顺序表中,算法的时间复杂度是O(1)的操作是:(B)A.访问第i个结点(1<=i<=n)和求第i个结点的直接前趋(2<=i<=n)B.在第i个结点后插入一个新的结点(1<=i<=n)C.删除第i个结点(1<=i<=n)D.将n个结点从小到大排序.二、填空：1、按顺序存储方法存储的线性表称为_顺序表__,按链式存储方法存储的线性表称为_链表__.2、线性表中结点的集合是_有限的_,结点间的关系是__1对1的__.3、顺序表相对于链表的优点有_以进行随机存取_和__节省
3、存储__4、链表相对于顺序表的优点有_不需要预分配存储空间_和__插入、删除__操作方便.5、在n个结点的顺序表中,删除一个结点需平均移动__（n－1）/2__个结点,具体的移动次数取决于_表长n和删除位置I__.6、在n个结点的顺序表中,插入一个结点需平均移动___n/2___个结点,具体的移动次数取决于___表长n和插入位置i___.7、在顺序表中访问任意一个结点的时间复杂度均为_O(1)_.因此,顺序表也称为_随机存取__的数据结构.8、在n个结点的单链表中要删除已知结点*p,需找到__前驱结点的地址___,其时间复杂度为_O(n)_.9、在
4、双链中要删除已知结点*p,其时间复杂度为_O(1)_.10、在单链表中,要在已知结点*p之前插入一个新结点,仍需找到_节点p_,其时间复杂度为__O(n)__.而在双链表中,完成同样的操作,其时间复杂度为__O(1)___11、在循环链表中,可根据在一结点的地址遍历整个链表,而单链表中需要知道__头指针__才能遍历整个链表.三、简答题：1,2,3,4四个数字按顺序进栈,问退栈的顺序有几种?答:4,3,2,1即全部进栈，然后顺序出栈！3，4，2，1即1，2，3先进栈，然后3出栈，然后1，2按顺序出栈3，2，4，1即1，2，3先进栈，然后3出栈，然后2
5、出栈，然后4进栈，最后4，1按顺序出栈依次类推，有2的4次方=16种
