文档介绍：第1章绪论 ⑴在顺序表中,等概率情况下,插入和删除一个元素平均需移动()个元素,具体移动元素的个数与() 和( )有关。【解答】表长的一半,表长,该元素在表中的位置⑵顺序表中第一个元素的存储地址是 100 ,每个元素的长度为 2,则第 5个元素的存储地址是( )。【解答】 108 【分析】第 5个元素的存储地址=第1个元素的存储地址+ (5- 1)× 2=108 ⑶设单链表中指针 p 指向结点 A ,若要删除 A 的后继结点(假设 A 存在后继结点) ,则需修改指针的操作为( )。【解答】 p->next=(p->next)->next ⑷单链表中设置头结点的作用是( )。【解答】为了运算方便【分析】例如在插入和删除操作时不必对表头的情况进行特殊处理。⑸非空的单循环链表由头指针 head 指示,则其尾结点(由指针 p所指)满足( )。【解答】 p->next=head 【分析】如图 2-8 所示。⑹在由尾指针 rear 指示的单循环链表中,在表尾插入一个结点 s的操作序列是();删除开始结点的操作序列为( )。【解答】 s->next =rear->next; rear->next =s; rear =s; (将S 的指针域先弄成表尾指针域,而表尾指针域是代表下个结点的地址信息,所以要将指针域要用 S替代,最后把表尾给 S) q=rear->next->next; rear->next->next=q->next; delete q; 【分析】操作示意图如图 2-9 所示: ⑺一个具有 n个结点的单链表,在指针 p所指结点后插入一个新结点的时间复杂度为();在给定值为 x 的结点后插入一个新结点的时间复杂度为( )。【解答】Ο(1) ,Ο(n) 【分析】在 p 所指结点后插入一个新结点只需修改指针,所以时间复杂度为Ο(1) (是表示常数计算时间); 而在给定值为 x的结点后插入一个新结点需要先查找值为 x的结点,所以时间复杂度为Ο(n) 。⑻可由一个尾指针唯一确定的链表有( )、()、()。【解答】循环链表,循环双链表,双链表 ⑴线性表的顺序存储结构是一种( )的存储结构,线性表的链接存储结构是一种( )的存储结构。 A随机存取 B顺序存取 C索引存取 D散列存取【解答】 A, B【分析】参见 。⑵线性表采用链接存储时,其地址( )。 A必须是连续的 B部分地址必须是连续的 C一定是不连续的 D连续与否均可以【解答】 D 【分析】线性表的链接存储是用一组任意的存储单元存储线性表的数据元素,这组存储单元可以连续,也可以不连续,甚至可以零散分布在内存中任意位置。⑶单循环链表的主要优点是( )。 A不再需要头指针了 B从表中任一结点出发都能扫描到整个链表; C已知某个结点的位置后,能够容易找到它的直接前驱; D在进行插入、删除操作时,能更好地保证链表不断开。【解答】 B⑷链表不具有的特点是( )。 A可随机访问任一元素 B插入、删除不需要移动元素 C不必事先估计存储空间 D所需空间与线性表长度成正比【解答】 A⑸若某线性表中最常用的操作是取第 i个元素和找第 i个元素的前驱,则采用()存储方法最节省时间。 A顺序表 B单链表 C双链表 D单循环链表【解答】 A 【分析】线性表中最常用的操作是取第 i 个元素,所以,应选择随机存取结构即顺序表,同时在顺序表中查找第 i个元素的前驱也很方便。单链表和单循环链表既不能实现随机存取,查找第 i个元素的前驱也不方便,双链表虽然能快速查找第 i个元素的前驱,但不能实现随机存取。⑹若链表中最常用的操作是在最后一个结点之后插入一个结点和删除第一个结点,则采用( )存储方法最节省时间。 A单链表 B带头指针的单循环链表 C双链表 D带尾指针的单循环链表【解答】 D 【分析】在链表中的最后一个结点之后插入一个结点需要知道终端结点的地址,所以,单链表、带头指针的单循环链表、双链表都不合适,考虑在带尾指针的单循环链表中删除第一个结点,其时间性能是 O(1) , 所以,答案是 D。⑺若链表中最常用的操作是在最后一个结点之后插入一个结点和删除最后一个结点,则采用( )存储方法最节省运算时间。 A单链表 B循环双链表 C单循环链表 D带尾指针的单循环链表【解答】 B 【分析】在链表中的最后一个结点之后插入一个结点需要知道终端结点的地址,所以,单链表、单循环链表都不合适,删除最后一个结点需要知道终端结点的前驱结点的地址,所以,带尾指针的单循环链表不合适,而循环双链表满足条件。⑻在具有 n个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度是( )。 A O(1) B O(n) C O(n2) D O(nlog2n) 【解答】 B【分析】首先应顺序查找新结点在单链表中的位置。⑼对于