数据结构复习题(4)

…………….……………..装……………………订………………..线…………….…………….. 课程 共 20 页，第16页，共印刷 份, — 年 月 日 考试，任课教师

27.已知世界6 大城市：北京(B)、纽约(N) 、巴黎（p）、伦敦(L) 、东京(T)、墨西哥城（M)。第五部分 算法设计题

1. 试编写在带头结点的单链表中删除（一个）最小值结点的（高效）算法。 试在下表给出的交通网中确定最小生成树，并说明所使用的方法和时间复杂度。 表：世界6 大城市交通里程网络表(单位：1OOkm) B N P L T M

28.已知数据序列为(36，74，8，50，18，6，40，30)，给出建立二叉排序树的过程示意图，再给出删除74，8后的二叉排序树。

29.对下面的有向图。

1) 给出每个顶点的入度和出度 2) 画出邻接链表 3) 求所有可能的拓扑序

5 6 2 3 4 1 B 109 82 81 21 124 N 109 58 55 108 32 P 82 58 3 97 92 L 81 55 3 95 89 T 21 108 91 95 113 M 124 32 92 89 113 void delete（Linklist &L）

计算机与信息 学院 信息工程、计科 专业 数据结构 LinkedList Delete（LinkedList L）

∥L是带头结点的单链表，本算法删除其最小值结点。

{p=L->next； ∥p为工作指针。指向待处理的结点。假定链表非空。 pre=L； ∥pre指向最小值结点的前驱。

q=p； ∥q指向最小值结点，初始假定第一元素结点是最小值结点。 while（p->next!=null）

{if（p->next->datadata）{pre=p；q=p->next；} ∥查最小值结点 p=p->next； ∥指针后移。 } pre->next=q->next；∥从链表上删除最小值结点 free（q）； ∥释放最小值结点空间 }∥结束算法delete。

2. 将两个递增的有序链表合并为一个递增的有序链表。要求结果链表仍使用原来两个链表的存

储空间, 不另外占用其它的存储空间。表中不允许有重复的数据。 void MergeList_L(LinkList &La,LinkList &Lb,LinkList &Lc)

void MergeList_L(LinkList &La,LinkList &Lb,LinkList &Lc){ pa=La->next; pb=Lb->next;

Lc=pc=La; //用La的头结点作为Lc的头结点 while(pa && pb){

if(pa->datadata){ pc->next=pa;pc=pa;pa=pa->next;}

else if(pa->data>pb->data) {pc->next=pb; pc=pb; pb=pb->next;} else {// 相等时取La的元素，删除Lb的元素 pc->next=pa;pc=pa;pa=pa->next; q=pb->next;delete pb ;pb =q;} } pc->next=pa?pa:pb; //插入剩余段 delete Lb; //释放Lb的头结点}

3. 已知长度为n的线性表A采用顺序存储结构，请写一时间复杂度为O(n)、空间复杂度为O(1)

的算法，该算法删除线性表中所有值为item的数据元素。 void Delete_Sq(SqList &A)

计算机与信息 学院 信息工程、计科 专业 数据结构 link 课程 共 20 页，第 17 页，共印刷 份, 年 月 日 考试，任课教师 …………….……………..装……………………订………………..线…………….…………….. 4. 已知一个带有表头结点的单链表，结点结构为： data 7. 已知一个带有表头结点的单链表，头指针为L，请用一个尽可能高效的算法实现，在非头结

点p所指元素前，插入元素e,并分析算法的时间复杂度。

假设该链表只给出了头指针list，在不改变链表的前提下，请设计一个尽可能高效的算法，查找链表中倒数第K位置的结点（K为正整数），若查找成功，算法输出该结点 data域的值，并返回1，时间复杂度O(n) 否则只返回0；要求：

（1）简述算法的基本设计思想；

（2）描述算法的详细实现步骤（使用C，或C++实现 ），关键之处给出详细解释。 int LocateElement(linklist list,int k)

{ P1=list->link; P=list; i=1; while(P1) { P1=P1->link; i++;

if(i>k) P=P->next; //如果i>k,则p也往后移 }

if(P==list) return 0; //说明链表没有k个结点 else { printf(“%d\\n“,P->data); return 1; } }

5. 已知非空线性链表第一个结点的指针为list，请写一个算法，将该链表中数据域值最大的那

个结点移到链表的最后面。 void REMOVE(LinkList & list){ LinkList s,r,p,q; q=list; p=list->link; r=list; While(p!=NULL){ if(p->data->q->data) then

Delete(Node *L, Node *p)

{ Node *s, *t s = L->next; t = L; while (s != NULL && s != p){ t = s; s = s->next; }

if (s != NULL){ t->next = s->next; free(s);} }

8. 已知一个带有表头结点的单链表，头指针为L，请用一个尽可能高效的算法实现，删除非头

结点p所指元素,并分析算法的时间复杂度。

9. 试设计实现在单链表中删去值相同的多余结点的算法。

typedef int datatype;

{ s=r; q=p; } r=p;p=p->link;} typedef struct node {datatype data; struct node *next;}lklist;

void delredundant(lklist *&head) if(q!=r) then { if (q==list) then list=q->link;

{ lklist *p,*q,*s;

else s->link=q->link; r->link=q; q->link=NULL; } } for(p=head;p!=0;p=p->next)

{ for(q=p->next,s=q;q!=0; )

6. 若已知非空线性链表第一个结点的指针为list，请 写一个算法，将该链表中数据域值最小的

if (q->data==p->data) {s->next=q->next; free(q);q=s->next;}

那个结点移到链表的最前端。

else {s=q,q=q->next;}

void REMOVE(LinkList & list){ } }

LinkList q=list, s ,r; p=list->link ;

While(p!=NULL){ if(p->data->q->data) then { s=r; q=p; } r=p;p=p->link;}

if(q!=list) then s->link=q->link; q->link=list; list=q; } }

10. 编写算法，判断带头结点的双向循环链表L是否对称。对称是指：设各元素值a1,a2,...,an,

则有ai=an-i+1 ，即指：a1= an，a2= an-1 。。 。。。。。

结点结构为：

prior data next int judge(DLinkList L) {

p=L->next; q=L->prior; while(p!=q) {

if(p->data!=q->data) return 0; if(p->next==q) return 1; p=p->next; q=q->prior; } return 1; }

计算机与信息 学院 信息工程、计科 专业 数据结构 课程 共 20 页，第 18 页，共印刷 份, 年 月 日 — 考试，任课教师 …………….……………..装……………………订………………..线…………….…………….. 11. 已知带头结点的动态单链表L中的结点是按整数值递增排列，试写一算法将值为X的结点插

入链表L中，使L仍然有序。

分析：本题算法的思想是先建立一个待插入的结点，然后依次与链表中的各结点的数据域比较大小，找到插入该结点的位置，最后插入该结点。实现本题功能的函数如下： void insertorder(Linklist &L， Elemtype x) { Linklist p,q,s; s=(Linklist)malloc(sizeof(Lnode));

s->data=x; s->next=NULL; //产生一个待插入的结点s q=L; p=q->next; while( p && x>p->data)

{ q=p; …… 此处隐藏：5260字，全部文档内容请下载后查看。喜欢就下载吧 ……