单项选择题(2016年春程序员软考)

对于长度为n的线性表(即n个元素构成的序列),若采用顺序存储结构(数组存储),则在等概率下,删除一个元素平均需要移动的元素数为【 】。

A、n

B、(n-1)/2

C、n/2

D、logn

参考答案

关键词

线性表;顺序;存储;算法;元素;数组;删除;概率;长度;顺序表;

含有n个元素的线性表采用顺序存储,等概率删除其中任一个元素,平均需要移动【 】个元素。

含有n个元素的线性表采用顺序存储方式时,对其运算速度最快的操作是【 】。

函数 Reverselist(LinkList headptr)的功能是将含有头结点的单链表就地逆置。处理思路是将链表中的指针逆转,即将原链表看成由两部分组成,已经完成逆置的部分和未完成逆置的部分,令s指向未逆置部分的第一个结点,并将该结点插入已完成部分的表头(头结点之后),直到全部结点的指针域都修改完成为止。例如,某单链表如图所示,逆置过程中指针s的变化情况如图(a)(b)所示。链表结点类型定义如下:typedef struct Node{ int data, struct Node *next;}Node, *LinkList;void ReverseList (LinkList headptr){//含头结点的单链表就地逆置, headptr为头指针 LinkList p,s; if(__(1)__) return;//空链表(仅有头结点)时无需处理 p=__(2)__;//令p指向第一个元素结点 if (!p->next) return;//链表中仅有一个元素结点时无需处理 s= p->next;//s指向第二个元素结点 __(3)__=NULL;//设置第一个元素结点的指针域为空 while (s){ p=s;//令p指向未处理链表的第一个结点 s=__(4)__; p-> next= headptr-> next;//将p所指结点插入已完成部分的表头 headptr-> next=__(5)__; }}

含有n个元素的线性表用顺序存储方式时,对其运算速度最快的操作是【 】。

线性表采用单链表存储时的特点是【 】。

下列描述中,正确的是【 】

没有提供指针类型的语言,无法构造链式结构,该说法【 】

假设有两个按元素值递增有序排列的线性表A和B,均以带头结点的单链表作为存储结构,编写算法将A表和B表归并成一个按元素值递减有序排列的线性表C,并要求利用原表(A表和B表)的结点空间存放表C。

试写出在双向链表da中的插入操作算法,算法中插入位置的获取可直接引入getnodep(da,i),其中参数da为双向链表,i是要插入的数据,要求算法中含有双向链表da的结点结构描述。

已知结点指针p、q分别表示双向链表中任意两个相邻结点(即p->rlink=q且q->llink=p),请写出删除q所指结点的程序段。