福师大数据结构在线作业2.doc

一、选择 1、用单链表方式存储的线性表,存储每个结点需要两个域,一个是数据域,另一个是()A.当前结点所在地址域.B.指针域.C.空指针域.D.空闲域. 2、在具有n个结点的单链表中,实现()的操作,其算法的时间复杂度是o(n). A.遍历链表和求链表的第i个结点.B.在地址为p的结点之后插入一个结点.C.删除开始结点D.删除地址为p的结点的后继结点. 3、单链表的存储密度().A.大于1 B.等于1 C.小于1 D.不确定 4、已知一个顺序存储的线性表,设每个结点需占m个存储单元,若第一个结点的地址为da1,则第i个结点的地址为()A.da1+(i-1)*m? B.da1+i*mC.da1-i*mD.da1+(i+1)*m 5、在n个结点的顺序表中,算法的时间复杂度是O(1)的操作是: ()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个结点的顺序表中,删除一个结点需平均移动__（n－1）/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种