小工具知识网

当前位置: 首页 > 行业知识 > 数据结构算法第三套大题

行业知识

数据结构算法第三套大题

2026-11-17 07:45:57 来源:互联网转载

1.二叉树的绘制

��程:

1.最简单的,先锁定根节点,然后分析前序和中序易得左子树——>2.分析右子树时,先看前序遍历(根左右),再看中序遍历(左根右),会发现位置是交换的,如果在存在交换(比如:BG,GB),说明根节点B左边是有左子树的

2.线索二叉树的画法

3.散列算法:

1.第一问:

当冲突的时候,就会往后进行搜索

第二问:

(注意查的时候也算一次,然后往后冲突,线性寻找时+1)

1+1+2+3+1/5=1.6

1.6

3.2散列哈希,拉链法(线性寻址法)解决哈希冲突

平均查找长度:元素移动次数之和/元素个数

4.希尔排序:

因为之前的排序复杂度都是n^2,对于数据量很大时候并不适用。因此,希尔提出了一种叫希尔排序的方法。具体实现方法书上有,这里举一个栗子:

**1.**首先将元素个数n/2=4->作为增量序列——>**2.**然后对每个序列进行排序(增量为4,代表空格为4)

**3.**然后进行排序(对比相同颜色的元素——>增量为4代表对应元素与空格为4的元素进行比较),如果大小顺序为顺序,则不变,否则交换位置

4.然后分量/2

此时,间隔为2,对应元素与距离为2的元素进行比较

排序后为: 2.0.5.3.7.6.8.9

5.然后再除2为分量为1

此时仅有1组,直接插入排序得到有序数组即可

总结: 分量为n,则有n组,那么在每一组内都为有序序列

5.堆排序:

1.堆排序的过程:

思路: 1.首先是按照线性表的次序建造一个二叉树——>2.然后从下到上进行调整(每次的时间复杂度为0(logn)),从下到上按大根堆的形式进行调整(根节点最大)——>3.左右子树选出最大的节点为他们的根节点,然后再将根节点87与最小的节点9进行交换,然后把87移出来

2.

1.此时9为根节点,然后按照大根堆的形式构造出一个新的大根堆——>2.此时78为新的大根堆,根节点,而9为叶子节点,进行交换,将78移除——>3,9为新根节点——>依次往复,9为最后移除的节点

6.链表中删除多余节点

//1.定义链表typedef struct node{   ElemType data;   struct node* next;}list;//2.删除链表多余节点void deleteOthers(list* l){   list*p,*q,*t; //q为每次的探索节点,寻找是否有相同值   p=l;   while(p!=NULL){     q=p;     while(q->next!=NULL){ //寻找与当前p相等的节点        if(p->data==q->next->data){          t=q->next; //t保存与p相等的节点           q=t->next; //q指向新的节点          p->next=q; //更新p的指向          free(t); //删除t节点        }else{          q=q->next;        }     }     p=p->next;   }}

7.查节点双亲算法:

void parent(BiTree *bt,char x){   if(bt!=NULL){      //1.判断当前节点的左子树的data是否等于x     if(bt->lchild&&bt->child->data==x){       printf("存在双亲节点为%c\n",bt->data);       return;       }     //2.判断当前节点的右子树的data是否等于x     if(bt->rchild&&bt->rchild->data==x){       printf("存在双亲节点为%c\n",bt->data);       return;     }     //3.递归当前节点的左右子树     parent(bt->lchild,x);     parent(bt->rchild,x);   }   }

上一篇:电脑主机启动屏幕黑屏怎么办恢复正常

下一篇:揭秘Q9500处理器性能实力,深度解析展现技术魅力!