填空⑴ 在顺序表[1]中,等概率情况下,插入和删除一个元素平均需移动( )个元素,具体移动元素的个数与( )和( )有关。[解答]表长的一半,表长,该元素在表中的位置⑵ 顺序表中第一个元素的存储地址是100,每个元素的长度为2,则第5个元素的存储地址是( )。[解答]108[分析]第5个元素的存储地址=第1个元素的存储地址+(5-1)×2=108⑶ 设单链表[2]中指针p 指向结点[3]A,若要删除A的后继结点(假设A存在后继结点),则需修改指针的操作为( )。[解答]p->next=(p->next)->next⑷ 单链表中设置头结点的作用是( )。[解答]为了运算方便[分析]例如在插入和删除操作时不必对表头的情况进行特殊处理。⑸ 非空的单循环链表[4]由头指针head指示,则其尾结点(由指针p所指)满足( )。[解答]p->next=head[分析]如图2-8所示。a1 a2 an p-|||-ead-|||-图 2-8 尾结点p与头指针head的关系示意图⑹ 在由尾指针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所示:a1 a2 an p-|||-ead-|||-图 2-8 尾结点p与头指针head的关系示意图⑺ 一个具有n个结点的单链表,在指针p所指结点后插入一个新结点的时间复杂度为( );在给定值为x的结点后插入一个新结点的时间复杂度为( )。[解答]Ο(1),Ο(n)[分析]在p所指结点后插入一个新结点只需修改指针,所以时间复杂度为Ο(1)(是表示常数计算时间);而在给定值为x的结点后插入一个新结点需要先查找值为x的结点,所以时间复杂度为Ο(n)。⑻ 设数组S[n]作为两个栈S1和S2的存储空间,对任何一个栈只有当S[n]全满时才不能进行进栈操作。为这两个栈分配空间的最佳方案是( )。A. S1的栈底位置为0,S2的栈底位置为n-1 B. S1的栈底位置为0,S2的栈底位置为n/2 C. S1的栈底位置为0,S2的栈底位置为n D. S1的栈底位置为0,S2的栈底位置为1 E. [解答]A F. [分析]两栈共享空间首先两个栈是相向增长的,栈底应该分别指向两个栈中的第一个元素的位置,并注意C++中的数组下标是从0开始的。 G. ⑼ 设有两个串p和q,求q在p中首次出现的位置的运算称作( )。 连接 模式匹配 求子串 求串长 [解答]B