《数据结构概论作业2》由会员分享，可在线阅读，更多相关《数据结构概论作业2（2页珍藏版）》请在金锄头文库上搜索。
1、一、选择1、用单链表方式存储的线性表,存储每个结点需要两个域,一个是数据域,另一个是(B)A.当前结点所在地址域.B.指针域.C.空指针域.D.空闲域.2、在具有n个结点的单链表中,实现(A)的操作,其算法的时间复杂度是o(n). A.遍历链表和求链表的第i个结点.B.在地址为p的结点之后插入一个结点.C.删除开始结点D.删除地址为p的结点的后继结点.3、单链表的存储密度(C).A.大于1 B.等于1 C.小于1 D.不确定4、已知一个顺序存储的线性表,设每个结点需占m个存储单元,若第一个结点的地址为da1,则第i个结点的地址为(A)A.da1+(i-1)*m B.da1+i*mC.da1-i
2、*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、顺序表相对于链表的优点有_以进行随机存取_和_节省存储_4、链表相对于顺序表的优点有_不需要预分配存储空间_和_插入、删除_操作方便.5、在n个结点的顺序表中
3、,删除一个结点需平均移动_（n1）/2_个结点,具体的移动次数取决于_表长n和删除位置I _.6、在n个结点的顺序表中,插入一个结点需平均移动_ n/2_个结点,具体的移动次数取决于_表长n和插入位置i _.7、在顺序表中访问任意一个结点的时间复杂度均为_ O(1)_.因此,顺序表也称为_随机存取_的数据结构.8、在n个结点的单链表中要删除已知结点*p,需找到_前驱结点的地址_,其时间复杂度为_ O(n)_.9、在双链中要删除已知结点*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出栈，然后4进栈，最后4，1按顺序出栈依次类推，有2的4次方=16种
