《福师大数据结构在线作业二》由会员分享,可在线阅读,更多相关《福师大数据结构在线作业二(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.da
2、1+(i-1)*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、顺序表相对于链表的优点有_以进行随机存取_和_节省存储_4、链表相对于顺序
3、表的优点有_不需要预分配存储空间_和_插入、删除_操作方便.5、在 n 个结点的顺序表中,删除一个结点需平均移动_(n1)/2_个结点,具体的移动次数取决于_ 表长 n 和删除位置 I _.6、在 n 个结点的顺序表中,插入一个结点需平均移动_ n/2_个结点,具体的移动次数取决于_ 表长 n 和插入位置 i _.福师数据结构练习二7、在顺序表中访问任意一个结点的时间复杂度均为_ O(1)_.因此,顺序表也称为_随机存取_的数据结构.8、在 n 个结点的单链表中要删除已知结点*p,需找到_前驱结点的地址_,其时间复杂度为_ O(n)_.9、在双链中要删除已知结点*p,其时间复杂度为_ O(1)
4、_.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 种