么影响?
三. 算法设计题(共25分)
1. (10分)设有一个带头结点的单链表hc,设计一个算法:
void split(LinkList *hc, LinkList *&ha, LinkList *&hb,ElemType x,ElemType y) 将hc拆分成两个带头结点的单链表ha和hb,其中ha的所有结点值均大于等于x且小于等于y,hb为其他结点。
2.(15分)假设一棵二叉树采用二叉链存储结构进行存储,每个结点的类型如下(每个结点值均为正整数且大小均不同):
typedef struct node
{ int data;
struct node *lchild,*rchild; /*左、右孩子结点指针*/
} BSTNode; (1)(10分)设计一个算法int isBST(BSTNode *bt),判断二叉树bt是否是一棵二叉排序树;
(2)(5分)说明你的算法的正确性。
数据结构部分参考答案
一. 单项选择题(2×10分,共20分)
1.D
2.C
3.C
4.B
5.D 6.A 7.D
8.C
9.D
10.B
二. 问答题(共30分)
1. 算法中的基本操作为while语句,设while循环语句执行T(n)次,有: s=1+2+3+…+T(n)<n 即
(1+T(n))*T(n)
<n,显然T(n) (1 T(n))*T(n)
2
2n O(n)
所以算法时间复杂度为O(n)。
评分标准:只有正确结果给2分,推导过程为3分。 2. 答:
对应的递归模型如下: f(b)=0 b=NULL
f(b)=f(b->lchild)+f(b->rchild)+1 若*b为双分支结点 f(b)=f(b->lchild)+f(b->rchild) 其他情况 该算法用于计算b二叉树中双分支结点的个数。 评分标准:递归模型占3分,功能占2分。
3. 构造相应的判定树如图2所示(图中结点的值对应元素的序号),第一层1个结点,
武汉大学2007计算机考研复试试卷_工学_高等教育_教育专区。武汉大学2007计算机考研... 武大计算机考研数据结构... 6页 1下载券 武汉大学计算机与信息处... 4页 ...
计算机考研 数据结构真题及其答案_计算机软件及应用_IT/计算机_专业资料。计算机科学与技术专业考研 数据结构真题极其答案。好好复习,加油加油啊...
武汉大学数据结构2007试题(A)_研究生入学考试_高等教育_教育专区。武汉大学...武汉大学计算机学院 2006 年-2007 学年第二学期“数据结构”考试试题(A)姓名 ...
2007年中山大学数据结构A考研真题详解_研究生入学考试_高等教育_教育专区。考研经验分享,考研笔记,考研辅导班,考研辅导视频,考研重点分析,出题老师介绍,导师推荐,...
数据结构复习题 一、单项选择题 1.不带头结点的单链表 head 为空的判断条件是( )。 A.head==NULL B.head->next==NULL C.head->next==head D.head!=...
2007年中山大学数据结构A考研真题答案精解_研究生入学考试_高等教育_教育专区。考研经验分享,考研笔记,考研辅导班,考研辅导视频,考研重点分析,出题老师介绍,导师推荐...
2007年中山大学数据结构A考研真题答案_研究生入学考试_高等教育_教育专区。考研经验分享,考研笔记,考研辅导班,考研辅导视频,考研重点分析,出题老师介绍,导师推荐,...
2007年中山大学数据结构A考研真题解析_研究生入学考试_高等教育_教育专区。考研...(非法学)、408计算机学科专业基础综合、414-植物生理学与生物化学、497-法硕联考...
武汉科技学院 2007 年招收硕士学位研究生试卷 科目代码 考试时间 406 2007 年 1 月 21 日下午 科目名称 报考专业 数据结构(A 卷) 计算机应用技术 1、试题内容...
2007年中山大学数据结构A考研真题状元讲解_研究生入学考试_高等教育_教育专区。考研经验分享,考研笔记,考研辅导班,考研辅导视频,考研重点分析,出题老师介绍,导师推荐...
热门文档