数据结构第二节习题.doc

第2章 线性表 一、单项选择题 1．线性表是具有n个_________的有限序列。 A．表元素 B．字符 C．数据元素 D．数据项 2．线性表是_________。 A．一个有限序列，可以为空 B．一个有限序列，不可以为空 C．一个无限序列，可以为空 D．一个无限序列，不可以为空 3．线性表采用链表存储时，其地址_________。 A．必须是连续的 B．一定是不连续的 C．部分地址必须是连续的 D．连续与否均可以 4．链表不具备的特点是_________。 A．可随机访问任一结点 B．插入删除不需要移动元素 C．不必事先估计存储空间 D．所需空间与其长度成正比 5．设线性表有n个元素，以下操作中，_________在顺序表上实现比在链表上实现效率更高。 A．输出第i(1≤i≤n)个元素值 B．交换第1个元素与第2个元素的值 C．顺序输出这n个元素的值 D．输出与给定值x相等的元素在线性表中的序号 ．设线性表中有2n个元素，以下操作中，_________在单链表上实现要比在顺序表上实现效率更高。 A．删除指定的元素 B．在最后一个元素的后面插入一个新元素 C．顺序输出前k个元素 D．交换第i个元素和第2n-i-1个元素的值(i=0,1…,n-1) ．如果最常用的操作是取第i个结点及其前驱，则采用_________存储方式最节省时间。 A．单链表 B．双链表 C．单循环链表 D．顺序表 ．与单链表相比，双链表的优点之一是_________。 A．插入删除操作更简单 B．可以进行随机访问 C．可以省略表头指针或表尾指针 D．访问前后相邻结点更灵活 ．的单链表L为空的判定条件是_________。 A．L= =NULL B．L-next= =NULL C．L-next= =L D．L!=NULL 1．在一个具有n 个结点的有序单链表中插入一个新结点并仍然保持有序的时间复杂度是_________。 A．O(1) B．O(n) C．O(n2) D．O(nlog2n) 1．在一个长度为n(n1)的带头结点的单链表h上，另设有尾指针r（指向尾结点），执行_________操作与链表的长度有关。 A．删除单链表中的第一个元素 B．删除单链表中的最后一个元素 C．在单逻表第一个元素前插入一个新元素 D．在单链表最后一个元素后插入一个新元素 1．对于一个具有n个元素的线性表，建立其单链表的时间复杂度_________。 A．O(log2n) B．O(1) C．O(n2) D．O(n) 二填空题 1．在线性表的顺序存储中，元素之间的逻辑关系是通过_________决定的；在线性表的链式存储中，元素之间的逻辑关系是通过_________决定的。 2．向一个长度为n的顺序表中的第i个元素(1≤i≤n)之前插入一个元素时，需向后移动_________个元素。 3．在一个长度为n的顺序表中删除第i个元素(1≤i≤n)时，需向前移动________个元素。 4．为了设置一个空的顺序表L，采用的操作是_________。 5．删除顺序表的_________元素，不需要移动任何元素。 6．删除顺序表的_________元素，需要移动的元素最多。 7．在顺序表_________元素后面插入一个元素，不需要移动任何元素。 8．顺序表的_________元素插入元素，需要移动的元素最多。 9． 在长度为n的顺序L中查找指定元素值的元素，其时间复杂度为_________。 10．在单链表中设置头结点的作用是_________。 11．在单链表中，要删除某一指定的结点，必须找到该结点的_________结点。 12．访问单链表中的结点，必须沿着_________依次进行。 13．求单链表长度的时间复杂度为_________。 14．删除单链表L中某结点*p之后的一个结点，其时间复杂度