神马作文网数据结构算法设计题和2个计算题（重分）
来源：学生作业帮 编辑：神马作文网作业帮 分类：综合作业 时间：2024/11/12 07:11:56
数据结构算法设计题和2个计算题（重分）
算法设计题
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]
至少为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]