11206045 杨明芳土木与水利学院结构工程。
作业5. 查找、排序。
非编程作业：
1． 对下标为1～9的有序表进行折半查找，画出折半查找的判定树；并计算在等概率情况下查找成功的平均查找长度asl。
asl=(1+2*2+4*3+2*4)/9=25/9
2． 设有关键字序列，散列表长12，散列函数为h(key)=key%11，用线性探查再散列、链地址法处理冲突，请分别画出散列表，并计算。
1) 线性探查再散列。
asl=(1+1+1+2+1+3+1+1+3+6+5+9)/12=34/12=17/6
2) 链地址法。
asl=(1*7+2*3+3*2)/12=19/12
3． 已知待排序序列为，请写出按下列排序方法进行升序排序时的第一趟排序结果：
1 直接插入排序；50，86，72，41，45，93，57，46
2 冒泡排序；50,72,41,45,86,57,46,93
3 简单选择排序；41，86，72，50，45，93，57，46
4 堆排序初建堆序列。大顶堆：93,86,72,46,45,50,57,41
小顶堆：41,45,57,46,50,93,72,86
4． 设计一种方法，以少于2n-3次的比较在顺序存储的n(n>=2)个数中同时找出最大和最小值。
答：有n个元素，将两个分成一组，一共为n/2组，每组的两个元素相互比较，把每组中最大和最小的比较出来，每组需要比较一次，经过第一轮共进行n/2次比较，之后将每组中最大的元素单独拿出来作为一个整体记为a，则其中共有n/2个元素，并且整个数列中最大的数字一定在这里面产生，同理把每组中最小的n/2个元素拿出来记为b，最小的数字一定在b中产生。
a中的n/2个元素相互比较，选出最大，共需要n/2-1次，同理b中需要n/2-1次比较选出最小，此时共需要2*（n/2-1）+ n/2=3n/2-2次比较。在n>=2时该数值小于2n-3。
数据结构作业
数据结构作业 下周三交。题目描述 二叉排序树，也称为二叉查找树。可以是一颗空树，也可以是一颗具有如下特性的非空二叉树 1.若左子树非空，则左子树上所有节点关键字值均不大于根节点的关键字值 2.若右子树非空，则右子树上所有节点关键字值均不小于根节点的关键字值 3.左 右子树本身也是一颗二叉排序树。现在...
数据结构作业
数据结构 作业一。1 1什么是数据？它与信息是什么关系？1 2什么是数据结构？有关数据结构的讨论涉及哪三个方面？1 3数据的逻辑结构分为线性结构和非线性结构两大类。线性结构包括数组 链表 栈 队列 优先级队列等 非线性结构包括树 图等 数据结构 作业一。1 1什么是数据？它与信息是什么关系？1 2什...
数据结构作业
c线性表。1.初始化线性表l initlist l 2.销毁线性表l destorylist l 3.清空线性表l clearlist l 4.求线性表l的长度 listlength l 5.判断线性表l是否为空 isempty l 6.获取线性表l中的某个数据元素内容 getelem l,i,e ...