1.1数算选择题(循环队列、二叉树、查找、堆、顺序表、生成树、哈夫曼树、排序)

2024-01-10 09:02:27

循环队列

front:头指针

rear:尾指针

m:循环队列的长度

元素个数=(rear-front+m)%m

19-11+40=48%40=8

11-19+40=32%40=32

二叉树

入度=出度,n-1=n0+n1+n2-1=n1+2n2,有n2+1=n0,对于完全二叉树,度为1的节点要么只有1个,要么没有,n=n0+n1+n2=2n2+n1+1,由于为偶数,所以N1为奇数,即n1=1,所以n2=15,n0=16?

在先序里确定根节点,然后划分左右子树,A

查找

12个元素,左指针为1,右指针12,1+12>>1=6.5=6,65

左指针为6,右指针12,6+12>>1=9,80

左指针6,右指针9,6+9>>1=7.5=7,70

左指针7,右指针9,8;;经过了4次比较

朴素建堆是加到最后,然后一直往上进行操作,如果比上面大,就和上面交换,直到不能交换为止,即上面比现在的大;

快速建堆是,先输入所有的序列,然后从第一个非叶子节点开始,向下进行操作,维护从下至上一直是大根堆,这样在上面的时候,向下比较,通往下面的路径就都是有序的,递减的,所以交换的时候,就是向下调整,直到不比下面的小,就是最后的位置

如果是要建小根堆,就向下找两个孩子最小的;要建大根堆,就找两个孩子最大的,为了防止选出另一个孩子后,依然不满足要求,就需要再次调整,就很麻烦,所以就直接选最小或最大的,就不用再进行调整了

向下调整,就是找这个节点中最大/最小的孩子,换上来

或者向下调整可以看成是在向下的路径牌堆中找到合适的位置,就是插入排序,插入操作 C

顺序表

如果是要删除的话,删除第一个元素,移动的次数为N-1,删除最后一个元素移动的次数为0,其它平均分布在这之间,所以是(N-1)/2

往顺序表中插入元素时,有N个时,最多移动N次,即放在顺序表的头部,N个元素都要动;最少0次,即插在队尾,其它情况就平均分布在这中间,所以平均就是二分之N

在顺序表中,逻辑上相邻的两个元素物理存储上也一定相邻(对)

某顺序表的第一个元素的存储地址是500,每个元素占4个单元,则第8个元素的起始地址是(D)

A.504?B.508 C.516 D.528

长度为n的非空线性表采用顺序存储结构,在第i个元素前插入一个数据元素,i的合法值应该是(A)

A.1<=i<=n+1 B.0<=i<=n+1 C.i>0 D.1<=i<=n-1

(取n+1就是在队尾插入元素)

在长度为n的顺序表中的第i(1<=i<=n+1)个元素前插入一个元素,需要移动的元素个数为(B)

A.n-i B.n-i+1 C.i D.n-i-1(就是i~n区间里元素的个数,为n-i+1)

在长度为n的顺序表中的第i(1<=i<=n+1)个元素前删除一个元素,需要移动的元素个数为(A)

A…n-i B.n-i+1 C.n-i-1 D.i

假设删除长度为n的顺序表中的每个元素的概率相同,则删除一个元素平均要移动的元素的个数是(D)
A.n/2 B.(n+1)/2 C.n D.(n-1)/2

在长度为n的顺序表中的第i(1<=i<=n+1)个元素前插入一个元素,其算法复杂度为(B)

A.O(1) B.O(n)C.O(n*n) D.O(logn)(以2为底)

在长度为n的顺序表中读取第i(1<=i<=n+1)个元素,其算法复杂度为(A)这道题考察的是getelem,不是定位操作locateelem

A.O(1) B.O(n)C.O(n*n) D.O(logn)(以2为底)

在长度为n的顺序表中删除第i(1<=i<=n+1)个元素,其算法复杂度为(B)
A.O(1) B.O(n)C.O(n*n) D.O(logn)(以2为底)


生成树

所有边权均不相同的无向图最小生成树是唯一的

同一个图不同最小生成树的边权重序列相同。

都可有K算法得出?

哈夫曼树

?

这个路径指的是节点到节点那个棍子的数量,而不是节点和节点间的节点数量?

初始时会入队13个叶子节点,然后每次操作都会减少队列中一个节点,生成一个非叶子节点,直到留下一个根节点,总共操作12次,产生12个非叶子节点,所以一共有25个节点

排序

停止时,左指针指向6,右指针指向3,然后交换,交换后左右指针移动,左指针指向6,右指针指向3,且左指针比右指针大,那么3和5交换,即3,2,5,6,8

文章来源:https://blog.csdn.net/m0_73553411/article/details/135330566
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。