兰州大学-数据结构-命题作业-二叉树

兰州大学-数据结构-命题作业-二叉树（完整答案）

第一题

//二叉树结点

typedef struct BiTNode{

//数据

char data;

//左右孩子指针

struct BiTNode *lchild,*rchild;

}BiTNode,*BiTree;

//按前序遍历创建二叉树

int CreateBiTree(BiTree &T){

char data;

//按先序次序输入二叉树中结点的值（一个字符），‘#’表示空树scanf("%c",&data);

if(data == '#'){

T = NULL;

}

else{

T = (BiTree)malloc(sizeof(BiTNode)); //生成根结点

T->data = data;

//构造左子树

CreateBiTree(T->lchild);

//构造右子树

CreateBiTree(T->rchild);

}

return 0;

}

//输出

void Visit(BiTree T){

if(T->data != '#'){

printf("%c ",T->data);

}

}

//前序遍历

void PreOrder(BiTree T){

if(T != NULL){

//访问根节点

Visit(T);

//访问左子结点

PreOrder(T->lchild);

//访问右子结点

PreOrder(T->rchild);

数据结构考试试题及答案

数据结构 一、单选题 1. 计算机算法指的是（b ）。 A．程序B．问题求解步骤的描述C．调度方法D．排序方法 2. 以下数据结构中，（a ）个是非线性数据结构。 A．树B．字符串C．队D．栈 3. 对于顺序存储的线性表，访问元素和插入元素的时间复杂度分别为：（c ）。 A．O(n) O(n) B．O(n) O(1) C．O(1) O(n) D．O(1) O(1) 4. 在单链表指针为p的结点之后插入指针为s的结点，正确的操作是（b ）。 A.p->next=s;s->next=p->next B.s->next=p->next; p->next=s C.p->next=s;p->next=s->next D.p->next=s->next; p->next=s 5. n个顶点的有向图中,含有向边的数目最多为( d ) A．n-1 B．n C．n(n-1)/2 D．n(n-1) 6. 循环队列存储在数组A[0..m]中，则入队时的操作为（ d ） A．rear=rear+1 B．rear=(rear+1)mod(m-1) C．rear=(rear+1)mod m D．rear=(rear+1)mod(m+1) 7. 字符串?ababaabab?的next函数为（d ） A.011232232 B.012341234 C.011122334 D. 011234234 8. 若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数为（ b ）A．9 B．11 C．15 D．不确定 9. 设有数组A[i,j]，数组的每个元素长度为3字节，i的值为1到8，j的值为1到10，数组从内存首地址BA开始顺序存放，当以列为主序存放时，元素A[5,8]的首地址为（ b ）。A．BA+141 B．BA+180 C．BA+222 D．BA+225 10. n个顶点的带权无向连通图的最小生成树包含(b )个顶点 A．n-1 B．n C．n/2 D．n+1 11．有关二叉树的下列说法正确的是（ b ） A．二叉树的度为2 B．一棵二叉树的度可以小于2 C．二叉树中至少有一个结点的度为2 D．二叉树中任何一个结点的度都为2 12．关键路径是AOE网中（ a ）。 A．从源点到汇点的最长路径B．从源点到汇点的最短路径 C．最长回路 D．最短路径（从源点到汇点的所有路径中，经过弧的数目最多的路径） 13．若查找每个记录的概率相等，则在具有n个记录的连续文件中采用顺序查找查找一个记录，其平均查找长度ASL为（c）。 A．(n-1)/2 B．n/2 C．(n+1)/2 D．n 14．就平均性能而言，目前最好的内部排序方法是（d ） A．冒泡排序B．希尔排序C．堆排序D．快速排序 15．已知广义表LS=((a,b,c),(d,e,f))，运用head和tail函数取出LS中原子e的运算是（d ）A．head(tail(LS)) B．tail (head (LS) C．head(tail(head(tail(LS)))) D．head(tail(tail (head (LS)))) 17．在n个结点的顺序表中，算法的时间复杂度是O（1）的操作是：( a ) A. 访问第i个结点（1≤i≤n）和求第i个结点的直接前驱（2≤i≤n） B. 在第i个结点后插入一个新结点（1≤i≤n）

数据结构树和二叉树实验报告

《数据结构》课程实验报告 实验名称树和二叉树实验序号 5 实验日期 姓名院系班级学号 专业指导教师成绩 教师评语 一、实验目的和要求 (1)掌握树的相关概念，包括树、结点的度、树的度、分支结点、叶子结点、儿子结点、双亲结点、树 的深度、森林等定义。 (2)掌握树的表示，包括树形表示法、文氏图表示法、凹入表示法和括号表示法等。 (3)掌握二叉树的概念，包括二叉树、满二叉树和完全二叉树的定义。 (4)掌握二叉树的性质。 (5)重点掌握二叉树的存储结构，包括二叉树顺序存储结构和链式存储结构。 (6)重点掌握二叉树的基本运算和各种遍历算法的实现。 (7)掌握线索二叉树的概念和相关算法的实现。 (8)掌握哈夫曼树的定义、哈夫曼树的构造过程和哈夫曼编码产生方法。 (9)掌握并查集的相关概念和算法。 (10)灵活掌握运用二叉树这种数据结构解决一些综合应用问题。 二、实验项目摘要 1．编写一程序，实现二叉树的各种基本运算，并在此基础上设计一个主程序完成如下功能： （1）输出二叉树b; （2）输出H结点的左、右孩子结点值； （3）输出二叉树b的深度； （4）输出二叉树b的宽度； （5）输出二叉树b的结点个数； （6）输出二叉树b的叶子结点个数。 2．编写一程序，实现二叉树的先序遍历、中序遍历和后序遍历的各种递归和非递归算法，以及层次遍历的算法。 三、实验预习内容 二叉树存储结构，二叉树基本运算（创建二叉树、寻找结点、找孩子结点、求高度、输出二叉树）

三、实验结果与分析 7-1 #include #include #define MaxSize 100 typedef char ElemType; typedef struct node { ElemType data; struct node *lchild; struct node *rchild; } BTNode; void CreateBTNode(BTNode *&b,char *str) { BTNode *St[MaxSize],*p=NULL; int top=-1,k,j=0; char ch; b=NULL; ch=str[j]; while (ch!='\0') { switch(ch) { case '(':top++;St[top]=p;k=1; break; case ')':top--;break; case ',':k=2; break; default:p=(BTNode *)malloc(sizeof(BTNode)); p->data=ch;p->lchild=p->rchild=NULL; if (b==NULL) b=p; else { switch(k) { case 1:St[top]->lchild=p;break; case 2:St[top]->rchild=p;break; } } } j++; ch=str[j]; }

兰州大学02-05人文地理考研试题

兰州大学 1999年 1. 论述加入世贸组织对中国空间经济格局和区域发展的影响 2.论述知识经济对经济地理学的影响 3. 论述数字信息革命浪潮对经济地理学的影响 2002年 一、名词 1.农业生态系统 2.干扰机会 3.回路径道 4.补偿贸易 5.机会成本 二、简答题 1.商业区位指向原则 2.第三产业增长的动力分析 3.制造工业布局特点 4.产业空心化及其原因 三、论述题 1.城市聚集障碍类型及聚集障碍的影响效应 2.西北开发的模式和重点 2003年 一、名词 1. 区位理论 2. 空间结构理论 3. 经济地理信息系统 4. 旅游环境容量 5. 城市首位律 6. 佩蒂---克拉克定理 7. 区域规划 二、简答 1. 影响国际服务贸易布局的主要因素 2. 主导产业的判断标准 3. 罗斯托的经济增长理论 4. 城镇体系的基本特征 5. 旅游地生命周期理论 三、论述 1.经济活动全球化对西北地区产业发展的影响 2.高技术圆区的空间布局特征 2004年 一、名词 1. 城市经济区 2. 空间要素替代理论 3. 区位指向 4. 梯度推移理论 5. 点轴式空间结构 6. 霍夫曼比例 7. 城镇生态规划 8. 旅游者空间行为 二、简答 1. 区域电信规划的内容和主要问题 2. 简述旅游规划的组成要素 3. 简述克鲁格曼的经济地理观点 4. 简述城市规模分布的位序规模法则 三、论述

经济活动全球化对中国西北地区产业发展的影响分析 2005年 一、名词 1. 干扰机会 2. 门槛人口 3. 点轴式空间结构 4. 虚拟经济 5. 城市空心化 6. 运费指向论 7. 旅游地空间竞争 8. 城市金子塔 二、简答 1. 迪肯的全球转移模式及其在中国的应用 2. 克里斯塔勒中央地理论的意义和存在的问题 3. 影响公司与投资地关系的特点及主要因素 4. 加纳的商业中心空间模式 三、论述 论西北地区可持续发展目标下的能源结构战略及其实现途径 兰州大学 兰州大学2000年硕士研究生入学考试试题 自然地理学 一. 解释下列概念(30分) 日的距离及其意义 臭氧层及其意义 成冰作用 夷平面 腐殖质及其作用 生态位 二. 论述地球自转和公转个有那些意义(20分) 三. 简介垂直地带性(15分) 四. 试论西部大开发(35分)

《数据结构》习题集：_树和叉树

第6章树和二叉树 一、选择题 1.有一“遗传”关系，设x是y的父亲，则x可以把它的属性遗传给y，表示该遗传关系最适合的数据结构是（ B ） A、向量 B、树 C、图 D、二叉树 2.树最适合用来表示（ B ） A、有序数据元素 B、元素之间具有分支层次关系的数据 C、无序数据元素 D、元素之间无联系的数据 3.树B 的层号表示为1a,2b,3d,3e,2c，对应于下面选择的（ C ） A、1a(2b(3d,3e),2c) B、a(b(D,e),c) C、a(b(d,e),c) D、a(b,d(e),c) 4.对二叉树的结点从1 开始连续编号，要求每个结点的编号大于其左、右孩子的编号，同一结点的左右孩子中， 其左孩子的编号小于其右孩子的编号，则可采用（ C ）次序的遍历实现二叉树的结点编号。 A、先序 B、中序 C、后序 D、从根开始按层次遍历 5.按照二叉树的定义，具有3 个结点的二叉树有（C ）种。 A、3 B、4 C、5 D、6 6.在一棵有n个结点的二叉树中，若度为2的结点数为n2，度为1的结点数为n1，度为0的结点数为n0，则树的最大高 度为（ E ），其叶结点数为（ H ）；树的最小高度为（ B ），其叶结点数为（ G ）；若采用链表存储结构，则有（ I ）个空链域。 log+1 C、log2n D、n A、n/2 B、??n2 E、n0+n1+n2 F、n1+n2 G、n2+1 H、1 I、n+1 J、n1K、n2L、n1+1 7.对一棵满二叉树，m 个树叶，n 个结点，深度为h，则（ D ） A、n=m+h B、h+m=2n C、m=h-1 D、n=2h-1 8.设高度为h 的二叉树中只有度为0 和度为2 的结点，则此类二叉树中所包含的结点数至少为（ B ），至多 为（D ）。 A、2h B、2h-1 C、2h-1 D、2h-1 9.在一棵二叉树上第5 层的结点数最多为（B）（假设根结点的层数为1） A、8 B、16 C、15 D、32 10.深度为5 的二叉树至多有（ C ）个结点。 A、16 B、32 C、31 D、10 11.一棵有124 个叶结点的完全二叉树，最多有（B ）个结点 A、247 B、248 C、249 D、250 12.含有129 个叶子结点的完全二叉树，最少有（ D ）个结点 A、254 B、255 C、256 D、257 13.假定有一棵二叉树，双分支结点数为15，单分支结点数为30，则叶子结点数为（ B ）个。 A、15 B、16 C、17 D、47 14.用顺序存储的方法将完全二叉树中所有结点逐层存放在数组R[1…n]中，结点R[i]若有左子树，则左子树是结 点（ B ）。 A、R[2i+1] B、R[2i] C、R[i/2] D、R[2i-1]

第六章树和二叉树习题数据结构

习题六树和二叉树 一、单项选择题 1．以下说法错误的是 ( ) A．树形结构的特点是一个结点可以有多个直接前趋 B．线性结构中的一个结点至多只有一个直接后继 C．树形结构可以表达(组织)更复杂的数据 D．树(及一切树形结构)是一种"分支层次"结构 E．任何只含一个结点的集合是一棵树 2．下列说法中正确的是 ( ) A．任何一棵二叉树中至少有一个结点的度为2 B．任何一棵二叉树中每个结点的度都为2 C．任何一棵二叉树中的度肯定等于2 D．任何一棵二叉树中的度可以小于2 3．讨论树、森林和二叉树的关系，目的是为了（） A．借助二叉树上的运算方法去实现对树的一些运算 B．将树、森林按二叉树的存储方式进行存储 C．将树、森林转换成二叉树 D．体现一种技巧，没有什么实际意义 4．树最适合用来表示 ( ) A．有序数据元素 B．无序数据元素 C．元素之间具有分支层次关系的数据 D．元素之间无联系的数据 5．若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（）A．9 B．11 C．15 D．不确定 6．设森林F中有三棵树，第一，第二，第三棵树的结点个数分别为M1，M2和M3。与森林F对应的二叉树根结点的右子树上的结点个数是（）。 A．M1 B．M1+M2 C．M3 D．M2+M3 7．一棵完全二叉树上有1001个结点，其中叶子结点的个数是（） A． 250 B． 500 C．254 D．505 E．以上答案都不对 8. 设给定权值总数有n 个，其哈夫曼树的结点总数为( ) A．不确定 B．2n C．2n+1 D．2n-1 9．二叉树的第I层上最多含有结点数为（） A．2I B． 2I-1-1 C． 2I-1 D．2I -1 10．一棵二叉树高度为h,所有结点的度或为0，或为2，则这棵二叉树最少有( )结点A．2h B．2h-1 C．2h+1 D．h+1 11. 利用二叉链表存储树，则根结点的右指针是（）。 A．指向最左孩子 B．指向最右孩子 C．空 D．非空 14．在二叉树结点的先序序列，中序序列和后序序列中，所有叶子结点的先后顺序（）A．都不相同 B．完全相同 C．先序和中序相同，而与后序不同 D．中序和后序相同，而与先序不同 15．在完全二叉树中，若一个结点是叶结点，则它没（）。 A．左子结点 B．右子结点 C．左子结点和右子结点 D．左子结点，右子结点和兄弟结点 16．在下列情况中，可称为二叉树的是（）

兰州大学考研真题(已有10试题)

兰州大学 管理学院 管理学2000——2006 西方经济学2000——2007，2010（2010为回忆版） 文学院 古代汉语和现代汉语2006 古代汉语2002——2005 文学概论2000——2002，2004——2005 现代汉语2002 现代汉语和语言学概论2003——2005 语言学概论2000——2002 中国文学2008 中国文学史2000——2007（注：2002，2003年试卷名称为“中国古代文学史”）中国现代文学史2002——2003 文学理论和外国文学2008 文学概论和外国文学2006 比较文学与世界文学2002——2003 汉语言文字学2000——2001 新闻与传播学院 传播学原理1999——2005（1999——2004有答案） 新闻理论(含中国新闻事业史) 1999——2005，2007（1999——2004有答案） 新闻写作1999——2002 历史文化学院 民族学概论2003——2005 民族学原理2000——2001 世界近现代史1995——2005 中国古代史2000——2005 中国近现代史1994——2005 中国历史文选2002——2005 中国少数民族史2003——2005 经济学院 高级微观与宏观经济学2006 西方经济学2000——2007，2010（2010为回忆版） 发展经济学2000——2005 金融学综合（含货币银行学、国际金融学）2005 政治经济学（资、社）2000——2005 中国近现代经济史(含中国近代经济史、中华人民共和国经济史)2005

法学院 法理学2003——2005 法理学（复试）2004 国际公法（复试）2004——2005 国际经济法2005 环境与资源保护法2002——2005 经济法2001——2005 民法2001——2002 民法（复试）2004——2005 民商法2003——2005 民事诉讼法（复试）2004——2005 宪法与行政法学2008 宪法（复试）2004 刑法2004——2005 刑事诉讼法（复试）2004——2005 行政法2002 行政法与行政诉讼法2004——2005 外国语学院 二外德语2002——2005 二外法语2002——2005 二外日语2001，2003（2001有答案） 翻译与写作2004——2005 英美文学2001——2005 英语语言学2002——2005 哲学社会学院 科学思想史2004——2005 马克思主义哲学2004——2005 西方哲学史2000——2005 中国哲学史2000——2005 社会调查方法2002——2005（注：2004年试卷共2页，缺第2页）社会学理论2007 社会学概论2002——2005 社会学专业2004年复试（笔试）试题 政治与行政学院 国际政治学2002——2006，2008（注：2008年试卷为回忆版） 马克思主义发展史2002——2006 政治学原理2002——2006，2008 科学社会主义原理2004 教育学院 高等教育学2002

目前最完整的数据结构1800题包括完整答案树和二叉树答案

第6章树和二叉树 部分答案解释如下。 12. 由二叉树结点的公式：n=n0+n1+n2=n0+n1+(n0-1)=2n0+n1-1，因为n=1001,所以1002=2n0+n1,在完全二叉树树中，n1只能取0或1,在本题中只能取0，故n=501，因此选E。 42.前序序列是“根左右”，后序序列是“左右根”，若要这两个序列相反，只有单支树，所以本题的A和B均对，单支树的特点是只有一个叶子结点，故C是最合适的，选C。A或B 都不全。由本题可解答44题。 47. 左子树为空的二叉树的根结点的左线索为空（无前驱），先序序列的最后结点的右线索为空（无后继），共2个空链域。 52．线索二叉树是利用二叉树的空链域加上线索，n个结点的二叉树有n+1个空链域。 部分答案解释如下。 6．只有在确定何序（前序、中序、后序或层次）遍历后，遍历结果才唯一。 19．任何结点至多只有左子树的二叉树的遍历就不需要栈。 24. 只对完全二叉树适用，编号为i的结点的左儿子的编号为2i(2i<=n)，右儿子是2i+1（2i+1<=n） 37. 其中序前驱是其左子树上按中序遍历的最右边的结点（叶子或无右子女），该结点无右孩子。 38 . 新插入的结点都是叶子结点。 42. 在二叉树上，对有左右子女的结点，其中序前驱是其左子树上按中序遍历的最右边的结点（该结点的后继指针指向祖先），中序后继是其右子树上按中序遍历的最左边的结点（该结点的前驱指针指向祖先）。 44．非空二叉树中序遍历第一个结点无前驱，最后一个结点无后继，这两个结点的前驱线索和后继线索为空指针。 三.填空题

1.(1)根结点(2)左子树(3)右子树 2.(1)双亲链表表示法(2)孩子链表表示法(3)孩 子兄弟表示法 3．p->lchild==null && p->rchlid==null 4.(1) ++a*b3*4-cd (2)18 5.平衡 因子 6. 9 7. 12 8.(1)2k-1 (2)2k-1 9.(1)2H-1 (2)2H-1 (3)H=?log2N?+1 10. 用顺序存储二叉树时，要按完全二叉树的形式存储，非完全二叉树存储时，要加“虚结 点”。设编号为i和j的结点在顺序存储中的下标为s 和t ,则结点i和j在同一层上的条 件是?log2s?=?log2t?。 11. ?log2i?=?log2j?12.(1)0 (2)(n-1)/2 (3)(n+1)/2 (4) ?log2n?+1 13.n 14. N2+1 15.(1) 2K+1-1 (2) k+1 16. ?N/2? 17. 2k-2 18. 64 19. 99 20. 11 21.(1) n1-1 (2)n2+n3 22.(1)2k-2+1（第k层1个结点，总结点个数是2H-1，其双亲是2H-1/2=2k-2）(2) ?log2i?+1 23.69 24. 4 25.3h-1 26. ?n/2? 27. ?log2k?+1 28.(1)完全二叉树 (2)单枝树，树中任一结点（除最后一个结点是叶子外）,只有左子女或 只有右子女。 29.N+1 30.(1) 128(第七层满，加第八层１个) (2) 7 31. 0至多个。任意二叉树，度为１的结点个数没限制。只有完全二叉树，度为１的结点个 数才至多为1。 32．21 33.(1)2 (2) n-1 (3) 1 (4) n (5) 1 (6) n-1 34.(1) FEGHDCB (2)BEF（该二叉树转换成森林，含三棵树，其第一棵树的先根次序是 BEF） 35.(1)先序（2）中序 36. (1)EACBDGF （2）2 37.任何结点至多只有右子女 的二叉树。 38.(1)a (2) dbe (3) hfcg 39.(1) . (2) ...GD.B...HE..FCA 40.DGEBFCA 41．(1)5 （2）略 42.二叉排序树 43.二叉树 44. 前序 45.(1)先根次序（2）中根次序46.双亲的右子树中最左下的叶子结点47.2 48.(n+1)/2 49.31（x的后继是经x的双亲y的右子树中最左下的叶结点） 50.(1)前驱 (2)后 继 51.(1)1 (2)y^.lchild (3)0 (4)x (5)1 (6) y (7)x(编者注：本题按 中序线索化) 52.带权路径长度最小的二叉树，又称最优二叉树 53.69 54.(1)6 (2)261 55.(1)80 (2)001（不唯一）56.2n0-1 57.本题①是表达式求值，②是在二叉排序树中删除值为x的结点。首先查找x，若没有x， 则结束。否则分成四种情况讨论：x结点有左右子树；只有左子树；只有右子树和本身是叶 子。 (1)Postoder_eval(t^.Lchild) (2) Postorder_eval(t^.Rchild) (3)ERROR(无此运 算符)(4)A (5)tempA^.Lchild (6)tempA=NULL(7)q^.Rchild (8)q (9)tempA^.Rchild (10)tempA^.Item

高等数学A卷(兰大版张志强)试题

兰州大学2012～2013学年第 一 学期 考试试卷（卷） 课程名称： 高等数学（物理类） 任课教师： 学院： 专业： 年级： 姓名： 校园卡号： 一 计算题（共50分）： 1. 计算极限0 lim 2sin x x x →+3/（1） （5分） 2．计算极限0tan sin lim sin x x x x x →-- （5分） 3．计算极限2 112 lim x x x x →++-- （5分） 4．计算sin ()(cos )x f x x =的导数 （5分） 5．设sin 3ρθ=，计算导数 dy dx （6分） 6．设0sin cos sin t x x t y e dx =?? ?=???，计算导数dy dx （6分） 7．计算积分sin x dx x ? （6分） 8．计算积分3tan sec x xdx ? （6分） 9．计算积分sin ln x dx ? （6分） 二（10分）求由方程1sin 02x y y -+=所确定的二阶导数22d y dx 三（10分）求圆环体，即圆片222()(0)x a y R R a -+≤<<绕y 轴旋转所得旋转体的体积. 四（10分）一圆柱形贮水桶高为H 米，底半径为r 米，桶内盛满水。如果把桶内水全 部吸出，问至少需要作多少功？ 五（10分）求幂级数21 n n nx ∞ =∑的和. 六（5分）证明当02 x π << 时，tan 2sin 3x x x +> 七（5分）证明极坐标曲线()r r θ=的曲率公式为22223/2|2| ()r r rr K r r '''+-='+。据此证明双纽 线2cos 2r θ=的曲率半径与r 成反比. 题 号 一 二 三 四 五 六 七 八 总分 分 数 阅卷教师 --------------------------------------------------------装-------------------------------订---------------------------------线-------------------------------------------------------- 第2页

数据结构树和二叉树习题

树与二叉树 一.选择题 1.假定在一棵二叉树中，双分支结点数为15，单分支结点数为30个，则叶子结 点数为（）个。 A．15B．16C．17D．47 2.按照二叉树的定义，具有3个结点的不同形状的二叉树有（）种。 A. 3 B. 4 C. 5 D. 6 3.按照二叉树的定义，具有3个不同数据结点的不同的二叉树有（）种。 A. 5 B. 6 C. 30 D. 32 4.深度为5的二叉树至多有（）个结点。1 A. 16 B. 32 C. 31 D. 10 5.设高度为h的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的 结点数至少为（）。 A. 2h B. 2h-1 C. 2h+1 D. h+1 6.对一个满二叉树2，m个树叶，n个结点，深度为h，则（）。 A. n=h+m3 B. h+m=2n C. m=h-1 D. n=2 h-1 1深度为n的二叉树结点至多有2n-1 2满二叉树是除最后一层无任何子节点外，每一层上的所有结点都有两个子结点的二叉树7.任何一棵二叉树的叶结点在先序.中序和后序遍历序列中的相对次序（）。 A.不发生改变 B.发生改变 C.不能确定 D.以上都不对 8.如果某二叉树的前根次序遍历结果为stuwv，中序遍历为uwtvs，那么该二叉 树的后序为（）。 A. uwvts B. vwuts C. wuvts D. wutsv 9.某二叉树的前序遍历结点访问顺序是abdgcefh，中序遍历的结点访问顺序是 dgbaechf，则其后序遍历的结点访问顺序是（）。 A. bdgcefha B. gdbecfha C. bdgaechf D. gdbehfca 10.在一非空二叉树的中序遍历序列中，根结点的右边（）。 A. 只有右子树上的所有结点 B. 只有右子树上的部分结点 C. 只有左子树上的部分结点 D. 只有左子树上的所有结点 11.树的基本遍历策略可分为先根遍历和后根遍历；二叉树的基本遍历策略可分为 先序遍历.中序遍历和后序遍历。这里，我们把由树转化得到的二叉树4叫做这棵数对应的二叉树。结论（）是正确的。 A.树的先根遍历序列与其对应的二叉树的先序遍历序列相同 B.树的后根遍历序列与其对应的二叉树的后序遍历序列相同 3对于深度为h的满二叉树，n=20+21+…+2h-1=2h-1，m=2h-1。故而n=h+m。 4树转化为二叉树的基本方法是把所有兄弟结点都用线连起来，然后去掉双亲到子女的连线，只留下双亲到第一个子女的连线。因此原来的兄弟关系就变为双亲与右孩子的关系。 1/ 9

2017年数据结构期末考试题及答案A

2017年数据结构期末考试题及答案 一、选择题（共计50分，每题2分，共25题） 1 ?在数据结构中，从逻辑上可以把数据结构分为 C 。 A. 动态结构和静态结构B?紧凑结构和非紧凑结构 C.线性结构和非线性结构 D .内部结构和外部结构 2?数据结构在计算机内存中的表示是指 A ° A. 数据的存储结构 B.数据结构 C.数据的逻辑结构 D .数据元 素之间的关系 3.在数据结构中，与所使用的计算机无关的是数据的 A 结构。 A. 逻辑B?存储 C.逻辑和存储 D.物理 4 .在存储数据时，通常不仅要存储各数据元素的值，而且还要存储 C ° A.数据的处理方法B?数据元素的类型 C.数据元素之间的关系 D.数据的存储方法 5. 在决定选取何种存储结构时，一般不考虑 A ° A.各结点的值如何B?结点个数的多少 C?对数据有哪些运算 D.所用的编程语言实现这种结构是否方便。 6. 以下说法正确的是D ° A. 数据项是数据的基本单位 B. 数据元素是数据的最小单位 C. 数据结构是带结构的数据项的集合 D. —些表面上很不相同的数据可以有相同的逻辑结构 7. 在以下的叙述中，正确的是B ° A. 线性表的顺序存储结构优于链表存储结构 B. 二维数组是其数据元素为线性表的线性表 C?栈的操作方式是先进先出 D.队列的操作方式是先进后出

8. 通常要求同一逻辑结构中的所有数据元素具有相同的特性，这意味着 A. 数据元素具有同一特点 B. 不仅数据元素所包含的数据项的个数要相同，而且对应的数据项的类型要一致 C. 每个数据元素都一样 D. 数据元素所包含的数据项的个数要相等 9 ?链表不具备的特点是 A 。 A.可随机访问任一结点 B.插入删除不需要移动元素 C?不必事先估计存储空间 D.所需空间与其长度成正比 10. 若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一 个结点，则采用 D 存储方式最节省运算时间。 A.单链表B ?给出表头指针的单循环链表 C.双链表D ?带头结点 的双循环链表 11. 需要分配较大空间，插入和删除不需要移动元素的线性表，其存储结构是 B 。 A.单链表B .静态链表 C.线性链表 D .顺序存储结构 12 .非空的循环单链表head的尾结点（由p所指向）满足C 。 A. p—>next 一NULL B. p — NULL C. p—>next == head D. p = = head 13 .在循环双链表的p所指的结点之前插入s所指结点的操作是 D 。 A .p—> prior-> prior=s B .p—> prior-> n ext=s C.s —> prior—> n ext = s D.s —> prior—> prior = s 14 .栈和队列的共同点是C 。 A.都是先进后出 B .都是先进先出 C.只允许在端点处插入和删除元素 D .没有共同点

兰州大学内科学试题及答案

内科学理论综合考试试卷 (A卷) A1型题（最佳答案题――肯定型，每题1分，共23分） 每一道题有A、B、C、D、E五个备选答案，问题表述形式为表定陈述，在答题时只需从5个备选答案中选择一个最合适的作为正 确答案。 1.在治疗肝硬化腹水时，如利尿过猛，尿量过多，最易诱发： A.上消化道出血 B.自发性腹膜炎 C.肝性脑病 D.急性肾功能不全 E.代谢性酸中毒 2.肝硬化失代偿期患者，经卧床、限盐及利尿剂治疗仍有中等量腹水，下肢浮肿，血浆白蛋白20g/L，血钾 3.56mmol/L，血钠138mmol/L，目前最重要的治疗措施是： A.继续利尿 B.导泻 C.腹腔穿刺放腹水 D.静脉输注白蛋白 E.腹腔-颈静脉分流术 3.十二指肠球部溃疡患者，三天来上腹痛加重，反复呕吐，为胃内容物及咖啡样物，共三次约500ml，无宿食，吐后疼痛缓解，最可能合并 A.幽门硬阻 B.上消化道出血 C.穿孔 D.癌变 E.弥漫性腹膜炎 4.患者，男，50岁，因胸痛两小时来急诊，心电图检查示V1，V2导联呈QS波形，V3，V4呈Qr波形，ST段均呈弓背向上抬高，并有室性期前收缩，本例处理，除吸氧、镇痛外，应首先尽快应用 A.毛花苷丙 B.硝酸异山梨酯 C.普萘洛尔 D.利多卡因 E.极化液 5.阻塞性肺气肿的肺功能检查最有价值的是 A.潮气量 B.肺活量 C.流量-容积（V－V）曲线测定 D.残气量（RV）及/肺总量（RV/TLC）百分比测定 E.最大通气量 6.男性，42岁，有高血压史。4小时前因劳累而感头痛，烦躁，心悸，多汗，恶心，面色苍白，视力模糊，收缩压33.8Kpa(260mmHg)，舒张压18.6Kpa(140mmHg)采用以下哪一项治疗最适宜？ A.氢氯噻嗪口服 B.心得安口服 C.静脉输液 D.硝普钠静滴 E.安定肌注 7.急性白血病经化疗获得完全缓解后，下一步骤最应是 A.停止化疗 B.维持化疗 C.强化巩固治疗 D.干扰素治疗 E.免疫治疗 8.X线胸片显示肺透过度增加，肺纹理增粗，横膈降低，肋间隙增宽，肺功能：FEV1和最大通气量均降低，RV/TLC%增加，以上检查结果最常见于下列哪种疾病？ A.肺间质纤维化 B.双侧自发性气胸 C.慢性支气管炎合并阻塞性肺气肿 D.支气管哮喘缓解期 E.先天性肺囊肿 9.男，56岁，因胸骨后压榨样疼痛1小时，急诊来院，体检：血压13.3/8Kpa （100/60mmHg），心率194次/分，心音低钝，心电图显示P波辨不出，QRS波宽大畸形连续，节律基本规则，下列哪一种药物为急用首选？ A.普罗帕酮 B.乙胺碘呋酮 C.利多卡因 D.普萘洛尔 E.溴苄胺 10.男性，30岁，畏寒、高热二周，咳嗽、咯大量脓臭痰一周，静置分层，痰培养出厌氧菌，抗生素治疗停药的指征是哪一项？ A.临床症状完全消失 B.临床症状完全消失，X线示炎症及脓腔完全消散 C.临床症状完全消失，X线仍有病变 D.体温下降至正常后2周 E.体温下降至正常后4-6周 11.男性，23岁，突然寒战、高热、咳嗽，咯少量铁锈色痰，口周有疱疹，

数据结构期末考试题及标准答案

数据结构期末考试题及标准答案

————————————————————————————————作者：————————————————————————————————日期：

2012年数据结构期末考试题及答案 一、选择题 1．在数据结构中，从逻辑上可以把数据结构分为C。 A．动态结构和静态结构B．紧凑结构和非紧凑结构 C．线性结构和非线性结构D．内部结构和外部结构 2．数据结构在计算机内存中的表示是指A。 A．数据的存储结构B．数据结构C．数据的逻辑结构D．数据元素之间的关系 3．在数据结构中，与所使用的计算机无关的是数据的A结构。 A．逻辑B．存储C．逻辑和存储D．物理 4．在存储数据时，通常不仅要存储各数据元素的值，而且还要存储C。 A．数据的处理方法B．数据元素的类型 C．数据元素之间的关系D．数据的存储方法 5．在决定选取何种存储结构时，一般不考虑A。 A．各结点的值如何B．结点个数的多少 C．对数据有哪些运算D．所用的编程语言实现这种结构是否方便。 6．以下说法正确的是D。 A．数据项是数据的基本单位 B．数据元素是数据的最小单位 C．数据结构是带结构的数据项的集合 D．一些表面上很不相同的数据可以有相同的逻辑结构 7．算法分析的目的是C，算法分析的两个主要方面是A。 （1）A．找出数据结构的合理性B．研究算法中的输入和输出的关系 C．分析算法的效率以求改进C．分析算法的易读性和文档性 （2）A．空间复杂度和时间复杂度B．正确性和简明性 C．可读性和文档性D．数据复杂性和程序复杂性 8．下面程序段的时间复杂度是O（n2）。

s ＝0； for（I ＝0；i＜n；i＋＋） for（j＝0；j＜n；j＋＋） s ＋＝B[i][j]； sum ＝s ； 9．下面程序段的时间复杂度是O（n*m）。 for（i ＝0；i＜n；i＋＋） for（j＝0；j＜m；j＋＋） A[i][j] ＝0； 10．下面程序段的时间复杂度是O（log3n）。 i ＝0； while（i＜＝n） i ＝i * 3； 11．在以下的叙述中，正确的是B。 A．线性表的顺序存储结构优于链表存储结构 B．二维数组是其数据元素为线性表的线性表 C．栈的操作方式是先进先出 D．队列的操作方式是先进后出 12．通常要求同一逻辑结构中的所有数据元素具有相同的特性，这意味着B 。 A．数据元素具有同一特点 B．不仅数据元素所包含的数据项的个数要相同，而且对应的数据项的类型要一致 C．每个数据元素都一样 D．数据元素所包含的数据项的个数要相等 13．链表不具备的特点是A。 A．可随机访问任一结点B．插入删除不需要移动元素 C．不必事先估计存储空间D．所需空间与其长度成正比 14．不带头结点的单链表head为空的判定条件是A。

兰州大学考研试题汇编

兰州大学中文系2004年中国文学史( 2004-5-8 18:38 ) 招生专业：中国古代文学、中国现当代文学、文艺学、比较文学与世界文学 一、填空（每空2分，共40分） 1、我国现存最早最完整的文人七言诗是——。 2、鲁迅评《世说新语》的艺术特点是：记言——，记行——。 3、——、——在文学史上的地位，就在于他们完成了“回忌声病，约句准篇”的律诗定型任务。 4、宋初诗坛三派指的是“白体”、“晚唐体”和——。 5、江西诗派的“一祖三宗”指的是杜甫、黄庭坚、陈师道和——。 6、“落木千山无远大，——”。 7、“绿肥红瘦”出自李清照的《》。 8、南戏四大传奇指的是《荆钗记》、《白兔记》、《拜月亭》、和《》 9、中国现代文学史上第一部新诗集作者是——的《》。 10、中国现代文学第一个十年中，最大的两个文学社团是——和——，并形成了新文学的两大流派。 11、在中国现代文学发展的第二个十年里，矛盾开创了——小说流派。 12、20世纪20年代末30年代初，上海一批用现代派手法表现都市生活的小说家，被人们称为——派。 13、更能代表20世纪40年代文学主潮的，是——区的文学创作。 14、“七月诗派”是在诗人——的影响下，以理论家兼诗人——为中心，形成的一个青年人群。 15、作家——是20世纪40年代中国出现的一位学者型讽刺小说家。 二、论述题（共110分） 1、试述楚辞的来源。（30分） 2、试述中国古代章回小说的产生和发展。（30分） 3、结合作品论述郭沫若《女神》的思想内容特色及其具体表现。（25分） 4、论述赵树理小说创作的艺术的成就。（25分） 兰州大学中文系2004年文学概论 招生专业：文艺学、中国古代文学、中国现当代文学、世界文学与比较文学 一、填空题（每小题2分，共30分） 1、文学理论以——为研究对象，是文艺学或文学学的五个分支之一。 2、以——、——、——等人为主要代表的德国古典美学文艺学是马克思文学理论的主要来源。 3、小说的基本特征主要是——、完整复杂的情节叙述和具体充分的环境描写。 4、“叙事”一词通常包括三个方面涵义，即——、——和——。 5、按照恩格斯的说法。“历史的必然要求和这个要求的实际上不可能实现之间”的矛盾冲突即使——。 6、17世纪欧洲古典主义戏剧创作所遵循的“三一律”法则是——、——、和——、的“三个一律”。

《数据结构》期末考试题及答案

2011-2012学年第一学期期末考查 《数据结构》试卷 （答案一律写在答题纸上，在本试卷上做答无效） 一、选择（每题1分，共10分） 1.长度为n的线性表采用顺序存储结构，一个在其第i个位置插入新元素的算法时间复杂度为（D） A.O(0) B.O(1) C.O(n) D.O(n2) 2.六个元素按照6，5，4，3，2，1的顺序入栈，下列哪一个是合法的出栈序列？（D） A.543612 B.453126 C.346512 D.234156 3.设树的度为4，其中度为1、2、3、4的结点个数分别是4、2、1、2，则树中叶子个数为（B ） A.8 B.9 C.10 D.11 4.设森林F对应的二叉树B有m个结点，B的右子树结点个数为n，森林F中第一棵树的结点个数是（ B ） A. m-n B.m-n-1 C.n+1 D.m+n 5.若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（B） A.9 B.11 C.15 D.不确定 6.下列哪一个方法可以判断出一个有向图是否有环。（A） A.深度优先遍历 B.拓扑排序 C.求最短路径 D.求关键路径 7.第7层有10个叶子结点的完全二叉树不可能有（B ）个结点。 A.73 B.234 C.235 D.236 8.分别用以下序列构造二叉排序树，与用其他三个序列构造的结果不同的是（B） A.（100,80,90,60,120,110,130） B.（100, 120, 110,130,80, 60,90） C.（100,60,80,90,120,110,130） D.（100,80, 60,90, 120, 130,110） 9.对一组数据（84，47，25，15，21）排序，数据的排列次序在排序过程中变化如下：（1）84 47 25 15 21 （2）15 47 25 84 21 （3）15 21 25 84 47（4）15 21 25 47 84则采用的排序方法是（B ） A.选择排序 B.起泡排序 C.快速排序 D.插入排序 10.对线性表进行折半查找时，要求线性表必须（D） A.以顺序方式存储 B.以顺序方式存储，且数据元素有序

2015年数据结构期末考试题及答案

2012年数据结构期末考试题及答案 一、选择题 1．在数据结构中，从逻辑上可以把数据结构分为C。 A．动态结构和静态结构B．紧凑结构和非紧凑结构 C．线性结构和非线性结构D．内部结构和外部结构 2．数据结构在计算机内存中的表示是指A。 A．数据的存储结构B．数据结构C．数据的逻辑结构D．数据元素之间的关系 3．在数据结构中，与所使用的计算机无关的是数据的A结构。 A．逻辑B．存储C．逻辑和存储D．物理 4．在存储数据时，通常不仅要存储各数据元素的值，而且还要存储C。 A．数据的处理方法B．数据元素的类型 C．数据元素之间的关系D．数据的存储方法 5．在决定选取何种存储结构时，一般不考虑A。 A．各结点的值如何B．结点个数的多少 C．对数据有哪些运算D．所用的编程语言实现这种结构是否方便。 6．以下说法正确的是D。 A．数据项是数据的基本单位 B．数据元素是数据的最小单位 C．数据结构是带结构的数据项的集合 D．一些表面上很不相同的数据可以有相同的逻辑结构 7．算法分析的目的是C，算法分析的两个主要方面是A。 （1）A．找出数据结构的合理性B．研究算法中的输入和输出的关系 C．分析算法的效率以求改进C．分析算法的易读性和文档性 （2）A．空间复杂度和时间复杂度B．正确性和简明性 C．可读性和文档性D．数据复杂性和程序复杂性 8．下面程序段的时间复杂度是O（n2）。

s ＝0； for（I ＝0；i＜n；i＋＋） for（j＝0；j＜n；j＋＋） s ＋＝B[i][j]； sum ＝s ； 9．下面程序段的时间复杂度是O（n*m）。 for（i ＝0；i＜n；i＋＋） for（j＝0；j＜m；j＋＋） A[i][j] ＝0； 10．下面程序段的时间复杂度是O（log3n）。 i ＝0； while（i＜＝n） i ＝i * 3； 11．在以下的叙述中，正确的是B。 A．线性表的顺序存储结构优于链表存储结构 B．二维数组是其数据元素为线性表的线性表 C．栈的操作方式是先进先出 D．队列的操作方式是先进后出 12．通常要求同一逻辑结构中的所有数据元素具有相同的特性，这意味着B 。 A．数据元素具有同一特点 B．不仅数据元素所包含的数据项的个数要相同，而且对应的数据项的类型要一致 C．每个数据元素都一样 D．数据元素所包含的数据项的个数要相等 13．链表不具备的特点是A。 A．可随机访问任一结点B．插入删除不需要移动元素 C．不必事先估计存储空间D．所需空间与其长度成正比 14．不带头结点的单链表head为空的判定条件是A。

数据结构—— 树和二叉树知识点归纳

第6章树和二叉树 6.1 知识点概述 树（Tree）形结构是一种很重要的非线性结构，它反映了数据元素之间的层次关系和分支关系。在计算机科学中具有广泛的应用。 1、树的定义 树（Tree）是n（n≥0）个数据元素的有限集合。当n＝0时，称这棵树为空树。在一棵非空树T中： （1）有一个特殊的数据元素称为树的根结点，根结点没有前驱结点。 （2）若n>1，除根结点之外的其余数据元素被分成m（m>0）个互不相交的集合T1，T2，…，Tm，其中每一个集合Ti（1≤i≤m）本身又是一棵树。树T1，T2，…，Tm称为这个根结点的子树。 2、树的基本存储结构 （1）双亲表示法 由于树中的每一个结点都有一个唯一确定的双亲结点，所以我们可用一组连续的 存储空间（即一维数组）存储树中的结点。每个结点有两个域：一个是data域，存放结点信息，另一个是parent域，用来存放双亲的位置(指针)。 （2）孩子表示法 将一个结点所有孩子链接成一个单链表形，而树中有若干个结点，故有若干个单 链表，每个单链表有一个表头结点，所有表头结点用一个数组来描述这种方法通常是把每个结点的孩子结点排列起来，构成一个单链表，称为孩子链表。 （3）双亲孩子表示法 双亲表示法是将双亲表示法和孩子表示法相结合的结果。其仍将各结点的孩子结点分别组成单链表，同时用一维数组顺序存储树中的各结点，数组元素除了包括结点本身的信息和该结点的孩子结点链表的头指针之外，还增设一个域，存储该结点双亲结点在数组中的序号。 （4）孩子兄弟表示法 这种表示法又称为树的二叉表示法，或者二叉链表表示法，即以二叉链表作为树的存储结构。链表中每个结点设有两个链域，分别指向该结点的第一个孩子结点和下一个兄弟（右兄弟）结点。 3、二叉树的定义 二叉树（Binary Tree）是个有限元素的集合，该集合或者为空、或者由一个称为根(root)的元素及两个不相交的、被分别称为左子树和右子树的二叉树组成。当集合为空时，称该二叉树为空二叉树。在二叉树中，一个元素也称作一个结点。 4、满二叉树 定义：在一棵二叉树中，如果所有分支结点都存在左子树和右子树，并且所有叶子结点都在同一层上，这样的一棵二叉树称作满二叉树。 5、完全二叉树 定义：一棵深度为k的有n个结点的二叉树，对树中的结点按从上至下、从左到右的顺序进行编号，如果编号为i（1≤i≤n）的结点与满二叉树中编号为i的结点在二叉树中的位置相同，则这棵二叉树称为完全二叉树。完全二叉树的特点是：叶子结点只能出现在最下层和次下层，且最下层的叶子结点集中在树的左部。 6、二叉树的性质