第2章测试题.docVIP

选择题 1．从一个具有n个结点的单链表中查找值为x的结点，在查找成功情况下，需平均比较（ d）n个节点，单链表。 如果x等于第一个元素的值。则要比较1次 x等于第二个元素的值，则要比较2次 … 最不巧：x值刚好等于第n个元素，则要比较x次 所以总次数是1+2+3+……+n-1+n=(n+1)*n/2 所以平均需要：(n+1)/2次。 顺序数组可以用折半查找，需要 log2…为低…N 次个结点。 A．n B．n/2 C．（n-1）/2 D．（n+1）/2 2．（a ）插入、删除速度快，但查找速度慢。 链表只需要修改前驱或者前驱与后继的指针就可以，查找时链表需要顺序查找，并且由于读取指针耗费时间 A．链表 B．顺序表 C．有序顺序表 D．上述三项无法比较 3．若希望从链表中快速确定一个结点的前驱，则链表最好采用（ c）方式。 双链表在结点前驱后继查找上的时间复杂度是O(1) A．单链表 B．循环单链表 C．双向链表 D．任意 4．在一个单链表中，若删除p所指结点的后继结点，则执行（d）。 p-next指向p指针的后继结点，p-next-next指向后继结点的后继结点。 A．p-next=p-next B．p=p-next-next C．p=p-next;p-next=p-next-next; D．p-next=p-next-next 5．带头结点的单链表head为空的判定条件是（b ）。 A．head==NULL B．head-next==NULL C．head-next==head D．head!=NULL 6．在循环双向链表的p所指结点之后插入s所指结点的操作是（ d）。 A．p-next=s;s-prior=p;p-next-prior=s;s-next=p-next; B．p-next=s;p-next-prior=s;s-prior=p;s-next=p-next; C．s-prior=p;s-next=p-next;p-next=s;p-next-prior=s; D．s-prior=p;s-next=p-next;p-next-prior=s;p-next=s; 7．若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（ a）存储方式最节省时间。 想要存取任一指定序号的元素，链表实现这个功能的代价很大 本来顺序表的弱点在于插入和删除元素，但是题目要求只最后进行插入和删除运算，所有顺序表是最好的选择！ A．顺序表 B．双向链表 C．带头结点的双循环链表 D．单循环链表 填空题 1．对于采用顺序存储结构的线性表，当随机插入或删除一个数据元素时，平均约需移动表中 一半 元素。 2．当对一个线性表经常进行的是插入和删除操作时，采用 链式 存储结构为宜。 因为采用链式结构存储线性表，插入和删除操作需要从头结点起查找被插入或删除结点的前驱结点，并修改这些结点的指针域，查找过程平均移动指针域为表长的一半 3．当对一个线性表经常进行的是存取操作，而很少进行插入和删除操作时，最好采用 顺序 存储结构。 它的特点是逻辑关系上相邻的两个元素在物理位置上也相邻，因此可以随机存取表中任一元素，它的存储位置可用一个简单，直观的公式来表示 4．在一个长度为n的顺序存储结构的线性表中，向第i个元素（1≦i≦n+1）之前插入一个新元素时，需向后移动 n-i+1 个元素。 这道题，可以进行举例来验证，比如要是在第一个元素前插入元素，需要移动n个元素。 i=1时，需要移动n个，进行验证 5．从长度是n的采用顺序存储结构的线性表中删除第i个元素（1≦i≦n），需向前移动 n-i 个元素。 6．对于长度是n的顺序存储结构的线性表，插入或删除元素的时间复杂度为 0（n） 。 7．在具有n个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度是 0（n） 。 因为单链表保存的信息只有表头 如果要在特定位置插入一个节点 需要先从表头一路找到那个节点 这个过程是O(n)的 8．在双向链表中，每个结点共有两个指针域，一个指向 前驱 结点，另一个则指向 后继 结点。 判断题 1．链表中的头结点仅起到标识的作用。 （ f） 头结点的数据域还可以存储一些必要的数据，如表长。 2．顺序存储结构的主要缺点是不利于插入和删除操作。 （ t） 3．线性表采用链表存储时，结点和结点内部的存储空间可以是不连续的。 （ f） 结点内部空间是连续的。 4．顺序存储方式插入和删除时效率太低，因此它不如链式存储方式好。 （ f） 还有其他比较参数。如空间利用率，难易程度，存取快捷等。 5．