50分求关于数据结构3个题目:【1】:6、9、3、1、8、9、5、11画出二叉树,写出前中后三序的结果.
来源:学生作业帮 编辑:搜搜做题作业网作业帮 分类:数学作业 时间:2024/08/09 00:38:35
50分求关于数据结构3个题目:【1】:6、9、3、1、8、9、5、11画出二叉树,写出前中后三序的结果.
【2】:24、15、6、9、72、5、3写出它的快速排序,希尔排序及二分查找的相应算法.
【3】:写出单链表、栈队列的相关指针及判断空满的必要条件.
【2】:24、15、6、9、72、5、3写出它的快速排序,希尔排序及二分查找的相应算法.
【3】:写出单链表、栈队列的相关指针及判断空满的必要条件.
1】
二叉树:6、9、3、1、8、9、5、11
\x09\x096
\x09 /\x09 \
\x099\x09\x093
/ \ / \
1\x09 8 9 5
/
11
1,前序:6、9,1,11,8,3,9,5
2,中序:11、1,9,8,6,9,3,5
3,后序:11、1,8,9,9,5,3,6
2】,
\x091,快速排序算法:
它的基本思想是:通过一躺排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一不部分的所有数据都要小,然后再按次方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列.
假设要排序的数组是A[1]……A[N],首先任意选取一个数据(通常选用第一个数据)作为关键数据,然后将所有比它的数都放到它前面,所有比它大的数都放到它后面,这个过程称为一躺快速排序.一躺快速排序的算法是:
1)、设置两个变量I、J,排序开始的时候I:=1,J:=N;
2)以第一个数组元素作为关键数据,赋值给X,即X:=A[1];
3)、从J开始向前搜索,即由后开始向前搜索(J:=J-1),找到第一个小于X的值,两者交换;
4)、从I开始向后搜索,即由前开始向后搜索(I:=I+1),找到第一个大于X的值,两者交换;
5)、重复第3、4步,直到I=J;
算法实现:
int sort_t(int a[],int top,int tall)
{
\x09int temp=a[top];
\x09while(top= temp && top < tall)
\x09\x09\x09--tall;
\x09\x09a[top]=a[tall];
\x09\x09while(a[top]top)
\x09\x09\x09++top;
\x09\x09a[tall]=a[top];
\x09}
\x09a[top]=temp;
\x09return top;
}
void sort(int a[],int top,int tall)
{
\x09if(top>=tall)
\x09\x09return;
\x09int middle=sort_t(a,top,tall);
\x09sort(a,top,middle-1);
\x09sort(a,middle+1,tall);
}
\x092,希尔排序
基本思想:
先取一个小于n的整数d1作为第一个增量,把文件的全部记录分成d1个组.所有距离为dl的倍数的记录放在同一个组中.先在各组内进行直接插人排序;然后,取第二个增量d2
再问: 单链表、栈队列的相关指针及判断空满的必要条件?
再答: 3】 单链表、栈队列的相关指针及判断空满的必要条件: 设最大长度为: N 链表数为:i 队列入队位置、出队位置:j,k 栈指针位置:p 1,为满的条件 单链表:每增加一结点,i++;当链表结点不为空,并且结点计数i=N 队列:入队列j++,;入队列指针数j>k=N-1,(j>k);或者(j+N)>k=N-1,(j
二叉树:6、9、3、1、8、9、5、11
\x09\x096
\x09 /\x09 \
\x099\x09\x093
/ \ / \
1\x09 8 9 5
/
11
1,前序:6、9,1,11,8,3,9,5
2,中序:11、1,9,8,6,9,3,5
3,后序:11、1,8,9,9,5,3,6
2】,
\x091,快速排序算法:
它的基本思想是:通过一躺排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一不部分的所有数据都要小,然后再按次方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列.
假设要排序的数组是A[1]……A[N],首先任意选取一个数据(通常选用第一个数据)作为关键数据,然后将所有比它的数都放到它前面,所有比它大的数都放到它后面,这个过程称为一躺快速排序.一躺快速排序的算法是:
1)、设置两个变量I、J,排序开始的时候I:=1,J:=N;
2)以第一个数组元素作为关键数据,赋值给X,即X:=A[1];
3)、从J开始向前搜索,即由后开始向前搜索(J:=J-1),找到第一个小于X的值,两者交换;
4)、从I开始向后搜索,即由前开始向后搜索(I:=I+1),找到第一个大于X的值,两者交换;
5)、重复第3、4步,直到I=J;
算法实现:
int sort_t(int a[],int top,int tall)
{
\x09int temp=a[top];
\x09while(top= temp && top < tall)
\x09\x09\x09--tall;
\x09\x09a[top]=a[tall];
\x09\x09while(a[top]top)
\x09\x09\x09++top;
\x09\x09a[tall]=a[top];
\x09}
\x09a[top]=temp;
\x09return top;
}
void sort(int a[],int top,int tall)
{
\x09if(top>=tall)
\x09\x09return;
\x09int middle=sort_t(a,top,tall);
\x09sort(a,top,middle-1);
\x09sort(a,middle+1,tall);
}
\x092,希尔排序
基本思想:
先取一个小于n的整数d1作为第一个增量,把文件的全部记录分成d1个组.所有距离为dl的倍数的记录放在同一个组中.先在各组内进行直接插人排序;然后,取第二个增量d2
再问: 单链表、栈队列的相关指针及判断空满的必要条件?
再答: 3】 单链表、栈队列的相关指针及判断空满的必要条件: 设最大长度为: N 链表数为:i 队列入队位置、出队位置:j,k 栈指针位置:p 1,为满的条件 单链表:每增加一结点,i++;当链表结点不为空,并且结点计数i=N 队列:入队列j++,;入队列指针数j>k=N-1,(j>k);或者(j+N)>k=N-1,(j
数据结构二叉树题已知DLR:ABCDEFG LDR:CBEDAFG求(1)LRD (2)画出该二叉树 (3)判定该二叉树
数据结构试题,某二叉树的节点数据采用顺序存储表示如下:0 1 2 3 4 5 6 7 8 9 10 11 12 13 1
数据结构的线索二叉树,为什么在有n个结点的二叉链表中必定存在n+1个空链域
已知二叉树的前序扩充序列如下:1 2 * 4 5 * * * 3 * * 请画出对应的二叉树
数据结构,关于线索二叉树
求最优二叉树 求带权值为1,3,5,5,8,12,14,19的最优二叉树.只要结果 不求中间过程,.为什么没人回答呢?汗
数据结构 一棵完全二叉树,第8层含有5个结点,则这棵二叉树的叶子结点个数为?
数据结构题目:在有n个叶子结点的完全二叉树中,最多有多少个结点?
数据结构的二叉树求深度的问题.
求叶子带权为1 4 9 16 25 36 49 64 81 100的最优二叉树,写出该二叉树对应的前缀码
给定权3,4,5,6,7,8,9,试用算法构造一棵最优二叉树,画出这棵树并计算出它的权.(离散数学)
在计算机程序中,二叉树是一种表示数据结构的方法,-层二叉树的结点总数为1;二层二叉树的结点的数