UC知道数据结构算法设计题和2个计算题（重分）
来源：百度知道 编辑：UC知道 时间：2024/06/17 12:35:14
算法设计题
1 设带表头结点的双向链表的定义为
typedef int ElemTyp*:
typedef struct dnode｛file://双向链表结点定义
ElemType data: file://数据
struct dnode*lLink*rLink:file://结点前驱与后继指针
DblNode
typedef DblNode*DblList:_____________
试设计一个算法，改造一个带表头结点的双向链表，所有结点的原有次序保持在各个结点的右链域rLink中，并利用左链域lLink吧所有结点按照其值从小到大的顺序连接起来。
计算题
1设有一个顺序贱S,元素s1,s2.s3.s4.s5.s6依次进贱，如果6个单元的出贱顺序为s2,s3,s4,s6,s5,s1,则顺序贱的容量至少应为多少？
2一颗具有n个结点的理想平衡二叉树（即除离根最远的最底层外其他各层都是满的，最底层有若干结点）有多少层？若设根结点在第0层，则树的高度h如何用n来表示（注意n可能为0）?
1 设带表头结点的双向链表的定义为
typedef int ElemTyp*:
typedef struct dnode｛file://双向链表结点定义
ElemType data: file://数据
struct dnode*lLink*rLink:file://结点前驱与后继指针
DblNode
typedef DblNode*DblList:_____________
试设计一个算法，改造一个带表头结点的双向链表，所有结点的原有次序保持在各个结点的右链域rLink中，并利用左链域lLink吧所有结点按照其值从小到大的顺序连接起来。
计算题
1设有一个顺序贱S,元素s1,s2.s3.s4.s5.s6依次进贱，如果6个单元的出贱顺序为s2,s3,s4,s6,s5,s1,则顺序贱的容量至少应为多少？
2一颗具有n个结点的理想平衡二叉树（即除离根最远的最底层外其他各层都是满的，最底层有若干结点）有多少层？若设根结点在第0层，则树的高度h如何用n来表示（注意n可能为0）?
1：
至少为3
进栈：s1,s2, s3, s4, s5,s6
出栈： s2, s3, s4, s6,s5,s1
栈内
元素
个数：1，2，1，2，1，2，1，2，3，2，1，0
2：
2^0+2+2^2+2^3+……+2^(h-1)=2^h-1
》》[2^h-1]<n<[2^(h+1)-1]
所以h=[log2 (n+1)]向下取整
算法设计题好久没看了，很伤脑筋
希望对你有用
噢，看不懂