发布时间 : 星期三 文章数据结构习题1更新完毕开始阅读0c9897303968011ca30091a9
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] } 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