数据结构算法题

前五章习题算法

2.2

算法设计题

1.设计一个算法从一给定的有序顺序表L中删除元素值在X到Y(X<=Y)之间的所有元素,要求以较高的效率实现,要求算法的空间复杂度为O(1) void delete(SqList &L,ElemType x,ElemType y) {

int i=0,k=0;

while(i=x &&L.elem[i]<=y) k++; //记录被删记录的个数 else L.elem[i-k]=L.elem[i]; //前移k个位置 i++; }

L.length=L.length-k; }

2设一个有序表L,含有2n个整数,其中n个位负数,n个为正数,设计一个算法将L中所有元素按正负相间排列. 要求算法的空间复杂度为O(1),时间复杂度为O(n) void move(SqList &L) {

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

while(i0)i++; while(i

while(i

} }

3.假设一两个元素依之=值递增有序排列的线性表A和B分别表示两个集合(同一 元素值各不相同),要求分别设计求A和B交并差集的算法,要求结果线形表中的元素依值递增有序排列,试对顺序表实现上述操作. 交集:

void intersection(SqList A,SqList B ,SqList &C) {

int i=0,j=0,k=0;

while(iB.elem[j]) j++; else { C.elem[k]=A.elem[i]; k++;i++;j++;} //共同的元素 }

C.length=k; } 并集:

void Union(SqList A,SqList B ,SqList &C) {

int i=0,j=0,k=0;

while(iB.elem[j]) {C.elem[k]=B.elem[j];k++;j++;} else {C.elem[k]=A.elem[i]; k++;i++;j++;} //共同的元素只放一个 }

while(i

void differnce(SqList A,SqList B ,SqList &C) {

int i=0,j=0,k=0;

while(iB.elem[j]) {j++;} else {i++;j++;} //共同的元素只放一个 }

while(i

2.3线性表的链式存储结构 简答题:

1. 描述以下三个概念的区别:头结点,头指针,首元结点(第一个元素结点).在单链表中设置头

结点的作用是什么?

答：首元结点是指链表中存储线性表中第一个数据元素a1的结点。为了操作方便，通常在链表的首元结点之前附设一个结点，称为头结点，该结点的数据域中不存储线性表的数据元素，其作用是为了对链表进行操作时，可以对空表.非空表的情况以及对首元结点进行统一处理。头指针是指向链表中第一个结点（或为头结点或为首元结点）的指针。若链表中附设头结点，则不管线性表是否为空表，头指针均不为空。否则表示空表的链表的头指针为空。这三个概念对单链表.双向链表和循环链表均适用。是否设置头结点，是不同的存储结构表示同一逻辑结构的问题。 头结点 head à

data link 头指针 首元结点 简而言之，

头指针是指向链表中第一个结点（或为头结点或为首元结点）的指针； 头结点是在链表的首元结点之前附设的一个结点；数据域内只放空表标志和表长等信息（内放头指针？那还得另配一个头指针！！！）

首元素结点是指链表中存储线性表中第一个数据元素a1的结点。

2. 试比较线性表的两种存储结构的优缺点,在什么情况下用顺序表比链表好?

① 顺序存储时，相邻数据元素的存放地址也相邻（逻辑与物理统一）；要求内存中可用存储单元的地址必须是连续的。

优点：存储密度大，存储空间利用率高。缺点：插入或删除元素时不方便。

②链式存储时，相邻数据元素可随意存放，但所占存储空间分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针

优点：插入或删除元素时很方便，使用灵活。缺点：存储密度小（<1），存储空间利用率低。 顺序表适宜于做查找这样的静态操作；链表宜于做插入.删除这样的动态操作。 若线性表的长度变化不大，且其主要操作是查找，则采用顺序表；

若线性表的长度变化较大，且其主要操作是插入.删除操作，则采用链表。

算法设计题

1试写一算法,对单链表的实现就地逆置 Status ListOppose_L(LinkList &L) { LinkList p,q; p=L->next; //p指向单链表第一个结点 L->next=NULL; //形成空的单链表 while(p){ //采用头插入法将p结点插入到头结点的后面实现逆置 q=p; p=p->next; q->next=L->next; L->next=q;

} return OK; }

2试设计一个算法,求A和Bl两个单链表表示的集合的交集并集和差集,单链表中的数据递增有序排列

并集：LinkList Bingji(LinkList &Head1,LinkList &Head2,LinkList &Head3) {

LNode *p1=Head1->next; LNode *p2=Head2->next; LNode *p3=Head3=Head1;

while(p1 && p2) {

if(p1->data < p2->data) {

p3->next =p1; p3=p3->next ; p1=p1->next ; } else {

if(p1->data > p2->data) {

p3->next =p2; p3=p3->next ; p2=p2->next ; } else {

p3->next = p1; p3=p3->next ; p1=p1->next ; q=p2; free(q);

p2=p2->next ; }

} }

p3->next =(p1)?p1:p2; free(Head2);

return Head3; }

交集：LinkList Jiaoji(LinkList &Head1,LinkList &Head2,LinkList &Head3) {

LinkList pa,pb,r,p; pa=Head1->next; pb=Head2->next; r=Head3=Head1; while(pa&&pb){ if(pa->datadata) {

r->next =pa->next ; free(pa); pa=r->next ; } else if(pa->data>pb->data) pb=pb->next; else {r->next=pa; r=pa;pa=pa->next;} } while(pa){

r->next =pa->next ; free(pa); pa=r->next ; } while (Head2->next) //释放Head2链表所有的结点空间 { p=Head2->next; Head2->next=p->next; free(p); } return Head3; }

差集：LinkList Chaji(LinkList &Head1,LinkList &Head2,LinkList &Head3) {

LinkList pa,pb,r,p; pa=Head1->next; pb=Head2->next; r=Head3=Head1; while(pa&&pb){ if(pa->datadata) {

while(!QueueEmpty(Q)) { DeQueue(Q,p); visit(p);

if(p->lchild) EnQueue(Q,p->lchild); if(p->rchild) EnQueue(Q,p->rchild); } }//LayerOrder

6.2.4假定二叉树采用二叉链表存储结构存储,设计一个算法计算一棵给定二叉树的结点总数.

int Nodes(BTNode *T) {

int num1,num2;

if (T==NULL) return 0;

else if(T->lchild==NULL&&T->rchild==NULL)return 1; else { num1=Nodes(T->lchild); num2=Nodes(T->rchild); return num1+num2+1; } }

本文来源：https://www.bwwdw.com/article/274t.html