一、填空

1、數據結構按邏輯結構可分為兩大類，它們分別是線性和非線性

2.1、在長為n的順序存儲的線性表中插入和刪除元素時所需移動元素的平均次數(等概率情況下)為：Ein=n/2，Ede=(n-1)/2

2.2、順序表有5個元素，設在任何位置上插入元素是等概率的，則在該表中插入一個元素時所需移動元素的平均次數為(C)

A．3 B．2 C.2．5 D．5

2.3、設順序表有9個元素，則在第3個元素前插入一個元素所需移動元素的個數為(C)A．9 B．4．5

C．7 D．6

3.1設有指針head指向的帶表頭結點的單鏈表，現將指針p指向的結點插入表中，使之成為第一個結點，其操作是(A)(其中，p->next、head->next分別表示p、head所指結點的鏈域)A．p->next=head->next；head->next=p；

B．p->next=head->next；head=p；

C．p->next=head；head=p；

D．p->next=head；p= head；

3.2、某鏈表如下所示

若要刪除值為C的結點應做操作P—> link=P—>link—>link

3.3 刪除單鏈一中值相同的結點:下列算法將單鏈表中值重復的結點刪除，使所得的結果表中各結點值均不相同，試完成該算法。

void DelSameNode(LinkList L)//L是帶頭結點的單鏈表，刪除其中的值重復的結點// { ListNode * p，*q，*r；

p=L->next；//p初始指向開始結點//

while(p)//處理當前結點p//

{ q=p；r=q->next；

do //刪除與結點*p的值相同的結點//

{ while(r&&r->data!=p->data)

{ q=r；r=r->next；}

if(r)//結點*r的值與*p的值相同，刪除*r//

{q->next=r->next；free(r)；r=q->next；}

}

while(r )；

p=p->next；

}

}

3.4：在值為x的結點前插入一個值為y的新結點，如x不存在，則把新結點插在表尾的算法。

結構形式：struct node {elemtp data；struct node*next }

void inert(struct node *head，elemtp x，elemtp y)

{s=(struct node *)malloc(sizeof(struc node))

s→data=y

if(head→data ==x)