数据结构习题1

2 在一个长度为n的顺序表中，向第iI个元素（1≤i≤n+1）位置插入一个新元素时，需要从后向前依次后移（B）个元素。

A n-i B n-i+1 C n-i-1 D i

3 在一个顺序表的表尾插入一个元素的时间复度的量级为（B）。

A O(n) B O(1) C O(n) D O(log n) 4 表长为n的顺序存储的线性表，当在任意位置上插入或删除一个元素的概率相等时，插入一个元素所需移动元素的平均个数为（C），删除一个元素需要移动元素的平均个数为（D） A (n-1)/2 B n C (n+1)/2 D n/2

5 设单链表中指针p指向结点a，若要删除p之后的结点（若存在），则需修改指针的操作为（A）。

A p->next=p->next->next B p=p->next

C p=p->next->next D next=p

6 单链表的存储密度为（C）。

A 大于1 B 等于5 C 小于1 D 不能确定

7 在一个单链表中，若要在p所指向的结点之后插入一个新结点，则需要相继修改（B）个指针域的值。

A 1 B 2 C 3 D 4

8 在一个单链表中，若要在p所指向的结点之前插入一个新结点，则此算法的时间复杂度的量级为（A）。 A O(n) B O(n/2) C O(1) D O(n1/2)

9 在一个带头结点的双向循环链表中，若要在p所指向的结点之前插入一个新结点，则需要相继修改（C）个指针域的值。

A 2 B 3 C 4 D 6

2

二、简答题

1 什么叫线性表？它有哪些特点？

2 在链表的设计中，为什么通常采用带头结点的链表结构？

3 对比顺序表与单链表，说明顺序表与单链表的主要优点和主要缺点。

4 试编写算法实现顺序表的逆置，即把顺序表A中的数据元素（a1,a2, ?,an）逆置为（an,an-1, ?,a1）。

5 已知A和B为两个非递减的线性表，现要求实现如下操作：从A中删除在B中出现的元素。试编写在顺序表中实现上述操作的算法。

6 试编写算法实现链表的就地逆置(不增加存储空间)，即把链表A中的数据元素（a1,a2, ?,an）逆置为（an,an-1, ?,a1）。 7 假设有两个非递减的线性表A 和B，均采用链式存储结构，试编写算法将A和B 归并成一个按元素非递减的线性表C。

4

8 试编写算法求单循环链表的表长。

1. A 2. B 3. B 4. D A5. A 6. C 7. B 8. A 9. C 二、简答题

1. 答：线性表是具有n个数据元素的一个有限序列。线性表的特点是：数据元素之间是一对一的关系。除第一个元素外，每个元素有且只有一个直接前驱；除最后一个元素外，每个元素有且只有一个直接后继。

2. 答：头指针是链表的一个标识，它用来指向带头结点的链表中的头结点。头结点是在链表的第一个数据元素之前附加的一个结点，它的作用是使对第一个结点的操作和其它结点一致，表空与非空时处理一致，不需要特殊处理，简化了操作。

3. 答：顺序表的特点是逻辑位置相邻的数据元素其物理位置也相邻，因此可以进行随机存储， 是一种随机存储结构。其插入和删除操作的时间复杂度均为O(n)。链表中的数据元素使用一组任意的存储单元存储，不要求逻辑位置相邻的数据元素物理位置也相邻，而是采用附加的指针表示元素之间的逻辑关系。链表的插入和删除结点均不需要移动其他结点，但是，其查找运算必须从头指针开始顺序查找，其时间复杂度为O(n)。 4. 答：算法如下

void Convert(SqList &L){

int i,j,temp; j=L.length-1; i=0; while(i

temp=L.elem[i]; L.elem[i]=L.elem[j]; L.elem[j]=temp; i++; j--;

} }

5. 答：算法如下

void Delete(SqList &La,SqList Lb){ int i,j,k;

i=0;j=0;

while(i

if(La.elem[i]Lb.elem[j]) j++; else ListDelete_Sq(La, i+1, k);

}

6. 答：算法如下

void InvertList(LinkList &L){

LinkList p,q,r; p = L->next; q = p->next; p->next=NULL; while(q!=NULL){

5

}

r=q->next; q->next=p; p=q; q=r;

L->next=p;

}

7. 答：算法如下

void MergeOrder(LinkList La,LinkList Lb){

LinkList pa,pb,Lc,pc; pa=La->next; pb=Lb->next; Lc=pc=La;

while (pa&&pb){ if(pa->data <=pb->data ){ pc->next=pa; pc=pa; pa=pa->next; }else{ pc->next=pb;

pc=pb;

pb=pb->next; } }

if (!pa) pc->next=pb;

else pc->next=pa; }

8. 答：算法如下

int Length(LinkList L){ int i=0; LinkList p; p=L->next; while(p){ p=p->next; i++;

}

return i;

}

习

一、选择题

题36

1在栈顶一端可进行的全部操作是（ ）。

A 插入 B 删除 C插入和删除 D进栈

2 栈的特点是（ ）。

A 先进先出 B 后进先出 C后进后出 D不进不出

3 顺序栈是空栈的条件是（ ）。

A top==0 B top==1 C top==-1 D top==m

4 假定利用数组A[N]顺序存储一个栈，top表示栈顶指针，已知栈未满，则x入栈时所执行的操作是（ ）。

A a[--top]=x; B a[top--]=x C a[++top]=x D a[top++]=x

5 一个栈的入栈序列是a,b,c,d,e，则不可能的出栈序列是（ ）。 A edcda B dceab C decba D abcde

6 经过下列栈的运算后EmptyStack(s)的值是（ ）。 InitStack(s);Push(s,a);Push(s,b);Pop(s,x);Pop(s,x) ;

A a B b C 1 D 0

7 若已知一个栈的入栈序列是1,2,3, ?,n，其输出序列为p1,p2,p3,?,pn，若p1=n,则pi为（ ）。 A i B n-i C n-i+1 D 不确定

8 队列的特点是（）。

A 先进先出 B 后进先出 C先进后出 D 不进不出 9 循环队列S为满的条件是（）。 A S->rear==S->front

B S->rear+1)%maxsiae==s->front C S->rear==0 D s->front==0

10 经过下列运算后GetHead(Q)的值是（）。

InitQueue(Q); EnQueue(Q,a); EnQueue(Q,b); DeQueue(Q,x); A a B b C 1 D 2

二、简答题

1 简述栈与队列的相同点与不同点。

2 在顺序队列中，什么叫真溢出？什么叫假溢出？为什么顺序队列常都采用循环队列结构？ 3 设以带头结点的循环链表表示队列，并且只设一个指针指向队尾元素结点（不设头指针），试编写相应的入队列、出队列算法。

4 设计一个输出如下形式数值的递归算法。

4 4 4 4 3 3 3

7