选择题 2.  下列数据结构中,同时具有较高的查找和删除性能的是______。
【正确答案】 C、D
【答案解析】 首先介绍常见的数据结构的操作性能:
   1)有序数组:查找的时候可以采用二分查找法,因此,查找的时间复杂度为O(logn),其中,n表示数组序列的长度。由于数组中的元素在内存中是顺序存放的,因此,删除数组中的一个元素后,数组中后面的元素就需要向前移动。在最坏的情况下,如果删除数组中的第一个元素,那么数组中后面的n-1个元素都需要向前移动,移动操作的次数为n-1,因此,此时的时间复杂度为O(n)。插入操作与删除操作类似,都需要数组中元素的移动,因此,其时间复杂度也为O(n)。
   2)有序链表:链表(以单链表为例)的存储特点为:每个结点的地址存储在它的前驱结点的指针域中,对链表的遍历只能从链表的首结点开始遍历,因此,此时查找的时间复杂度为O(n),其中,n表示链表的长度。对于删除和插入操作,虽然删除和插入操作的时间复杂度都为O(1)(因为不需要结点的移动操作),但是在删除前首先需要找到待删除结点的地址,这个操作的时间复杂度为O(n),在插入结点前首先也要找到结点应该被插入的地方,这个操作的时间复杂度也为O(n),因此,插入与删除的时间复杂度都为O(n)。
   3)AVL树(平衡二叉树):AVL树是一棵空树或它的左右两个子树的高度差的绝对值不超过1,并且左右两个子树都是一棵平衡二叉树。由于树的高度为logn,其中,n表示树中结点的个数,因此,查找的时间复杂度为O(logn),显然,删除与插入的时间复杂度也为O(logn)。
   4)Hash表:Hash表通过Hash值就可以定位到元素的位置,因此,查找、插入与删除的时间复杂度都为O(1)。
   5)普通数组:查找的时候只能顺序地遍历数组,在最坏的情况下需要对数组中所有的元素遍历一遍,因此,此时的时间复杂度为O(n),其中,n表示数组序列的长度。插入的时候只需要把元素插入到数组的最后一个元素的后面即可,因此,时间复杂度为O(1),删除操作也需要移动这个元素后面的所有的元素,因此,此时的时间复杂度也为O(n)。
   6)普通二叉树:在最坏的情况下,有n个结点的树的高度为n,因此,查找、插入与删除的时间复杂度都为O(n)。
   从上面的分析可以发现,平衡二叉树的查找和删除的时间复杂度都是O(logn),Hash表的查找、插入的时间复杂度都是O(1)。因此,这两个数据结构有较好的查找和删除的性能。所以,选项C、选项D正确。