数据结构习题与实验C++.docx

数据结构习题与实验-C+浙江万里学院内容简介数据结构是计算机专业的核心课，是重要的专业基础课。实践是学习本课程的 一个重要的环节。目前各种“数据结构”教材较为注重理论的叙述与介绍，算法描 述不拘泥某种语言的语法细节，默认读者已具备扎实的程序设计基础，可以在课下 独立完成数据结构实验。实际上在读者群中程序设计的基础并不一致，相当一部分 人基础较为薄弱。多数学生反映数据结构的上机实验存在一定的困难，希望有合适 的实验参考书指导学习。数据结构的理论学习也有一定的深度，存在一定的难度。 学生必须完成一定数量的思考题、练习题、书面作业题，一方面巩固基本知识、一 方面提高联系实际分析解决问题的能力。正是基于以上的原因编写了这本“数据结 构实验与习题”。本资料的前期版本（用C语言描述算法，用C/C+描述算法）已经使用数届， 现在是第三次修订，主要是使用C+面向对象技术描述算法和实现程序。本参考书包括C+语言基础、书面作业练习题和上机实验习题三部分。在C+语言基础知识部分，这里针对数据结构上机实验所必须的C+基本知识 （结构体、类等等）做补充介绍。这部分内容非常重要，掌握的是否熟练会直接影 响''数据结构”的学习。在习题部分，既有选择题、判断题，也有用图表解答的练习题、算法设计题或 综合解答分析题。并且配有部分练习题的答案供学生自学、练习、参考。在实验部分，包括有完整的C+语言源程序例题，介绍了一些设计数据结构题 目所需的C+语言常用的知识和技巧。在实验题中，既有简单容易的验证题，即验 证已经给出的源程序，或者扩充已经给出的源程序，也有需独立思考设计的综合实 验题。第1部分、第2部分的习题1、习题2、习题5、习题6和第3部分的上机实验 要求及规范、实验1、实验2、实验5、实验6由杨秀金改写。第2部分的习题3、 习题9和第3部分的实验3、实验9由汪沁改写。第2部分的习题4、习题7、习题 8和第3部分的实验4、实验7、实验8由邓芳改写。由于时间仓足、水平有限，书 中难免存在错误和不妥之处，敬请读者指正。计算机与信息学院杨秀金汪沁邓芳2005年2月修订 于浙江万里学院钱湖校区第1部分C+语言基本知识一、C+源程序结构1二、结构体及运用1三、类的基本概念及运用3四、结构体在类中的使用4第2部分书面作业练习题习题1绪论6习题2线性表8习题3栈和队列11习题4串13习题5数组15习题6树与二叉树17习题7图24习题8查找31习题9排序34第3部分上机实验习题上机实验要求及规范37实验1复数ADT及其实现 39实验2线性表40实验3栈和队列-47实验4串53实验5数组57实验6树与二叉树60实验7图64实验8查找68实验9排序71第1部分C+基本知识各种数据结构以及相应算法的描述总是要选用一种语言工具。在计算机科学发 展过程中，早期数据结构教材大都采用PASCAL语言为描述工具，后来出现了采用C 语言为描述工具的教材版本、至今又出现了采用C+语言为描述工具的多种教材版 本。本教实验指导书是为已经学习过C+语言的学生而编写。编写实验指导书目的 为了配合理论教学。程序要求在C+ Builder开发环境之下调试运行，采用面向对 象方法进行设计。典型的数据结构被设计成为类(class),典型算法设计成为类的 函数成员，然后在主函数中声明创建类对象，根据实际需要调用重要的算法。由于C+的使用具有一定的难度，为了同学更好的学习数据结构自身的知识内 容，减轻描述工具所带来的困难，这里针对数据结构上机实验所必须的C+基本知 识(结构体、类等等)做补充介绍。一、源程序组成#include . 编译预处理class A ")；/类成员函数定义；int main()编译预处理等类的相关程序编码主函数程序代码这部分内容详细参见本指导书的第3部分的程序实例。二、结构体及运用数据结构课程所研究的问题均运用到“结构体”和“类”。在C+语言中结构体 和函数又是理解和掌握“类”的语法基础。定义结构体的一般格式：struct 结构体类型名类型名1 变量名1; 数据子域类型名2变量名2；类型名n变量名n；其中struct是保留字。结构体类型名由用户自己命名。在使用时必须声明一个 具体的结构体类型的变量，声明创建一个结构体变量的方法是：结构体类型名结构体变量名；一个结构体中可以包含多个数据子域。数据子域的类型名一般指基本数据类型 (int char等)，也可是已经定义的另一结构体名。数据子域变量名可以是简单变 量，也可以是数组。它们也可以称为结构体的数据成员，它们的访问控制具有公 有'属性。1.通过“结构体变量名.数据子域”可以访问数据子域。/设计Student结构体，在主程序中运用。#include <iostream.h>#include <conio.h>#include <string.h>struct Student定义结构体 Studentlongnum;/学号intx;/成绩charname10;/姓名)int main()声明创建一个结构体变量si或者使用键盘输入cin » si.num;cin » sl.x;cin » si.name; Student si;为si的数据子域提供数据sl.num=1001 ;si. x=83;strcpy( si.name, * 李 明”)；输出结构体变量si的内容cout« " 姓名：”vv si.name «endl;cout«44 学号：M« sl.num«endl: cout« ” 成绩：M« sl.x «ednl;_getch(); return 0;)2.设计-维数组，每个数组元素是Student结构体类型，通过以下语句段可以 说明结构体数组的一般用法：通过“结构体数组名下标.数据子域”访问数据域。Student a5;声明创建一个结构体数组输出数组元素ai的学号域 输出数组元素ai的姓名域 输出数组元素ai的成绩域for(int i=0, i<5, i+)cout« "学号："；cin»ai.num;cout« "姓名："；cin>> ai.name；cout« "成绩:"cin»ai.x;以上是关于结构体的基本概念和简单运用。三、类的基本概念及运用类的是面向对象程序的基本单位。类是山数据成员和相关的函数成员组成。从 面向对象的角度考虑“学生”这个类，它不仅包括“学生”的一般属性：学号、姓 名、成绩等等，还应包括对于这些属性的操作：输入/输出、听课、实验、等等。类定义的一般格式：class类名若干数据成员；若干函数成员；类的数据成员和函数成员均存在访问控制权限问题。访问控制分为三种：公有(public )> 私有(private)和受护(protected)。数据成员的定义和结构体中的数据域定义是相似的。不同的是它们必须明确访 问控制。而公有数据成员，可以认为与结构体的数据域的访问权限相同。成员函数的定义又和一般函数的定义基本相同。不同的是类中成员函数也必须 明确访问控制权限。如果在类之中定义成员函数带函数体，并未有什么特殊之处。 如果在类之中仅有成员函数的原型声明，当在类定义之外定义函数体时，需要加上类的定义：定义类结构体Students私有成员/学号/ 成绩/姓名公有成员类限定标识“类名：:下面是“学生 class Students private:long num;int x;char name 10;public:Students();Students。 ;void SetDat( long n, int xO, char *na0 ) num=n; x=x0; strcpy( name,na0);)；void Students: :PrintOut() cout« " 姓名：void PrintOut();输出函数的原型声明/输出函数前加Students:“« name «endl;cout«学号："vv num«endl: cout«44 成绩：*« x «ednl; 在主程序中运用类Students, int main() Students s;声明创建一个类对象s,调用构造函数s.PrintOut();输出s的内容long m; int y; char xname10; coutvv”输入学号，成绩，姓名：”； cin»m»y»xname; s. SetDat( m, y, xname );修改对象 s 数据5. PrintOut();输出改变后s的内容_getch(); return 0; ) 运行结果： 姓名：O 学号：0 成绩:0 输入学号，成绩，姓名：1001 90 WangMing 姓名：WangMing 学号：1001 成绩：90这个例题中数据成员全部定义为私有(private),以便保证数据安全性。而函数成员全部定义为公有(public)成员函数，可以作为类对外部的的接口。 通过s. SetDat( m, y, xname );直接访公有函数成员SetDat(),将实参(主函数的 局部变量m, y, xname)的数据赋给私有数据成员num, x, name。 通过 s.PrintOut();直接访公有函数成员PrintOut(),间接访问输出私有成员num, x, name。四、结构体在类中的使用/数组的容量/数据元素的类型1 .结构体数组做类的数据成员const int MAXSIZE=100; struct ElemType int numb;char name20;long tel;）；class Sqlist private:ElemType elemMAXSIZE; 结构体 ElemType 类型的数组 elem做数据成员int length;public:Sqlist( void);Sqlist() );其他函数；2.结构体指针变量做类的数据成员 struct NodeType int data;NodeType *next;/结点的结构定义数据域指针域)；class Link private:NodeType *Head;类声明指向结构构体N odeT ype的指针变61Head做数据成员public:Link () Head=new NodeType; 间Head->next=Head; 空环);-Link() ;void creat();void outs();)；/为头结点申请空/头结点Head形成Head第2部分书面练习题习题1 绪论1.1单项选择题1 .数据结构是一门研究非数值计算的程序设计问题中,数据元素的、数据信 息在计算机中的以及一组相关的运算等的课程。A.操作对象B .计算方法C.逻辑结构D.数据映象A.存储结构B.关系C.运算D.算法2 .数据结构DS(Data Struct)可以被形式地定义为DS=(D,R),其中D是的 有限集合，R是D上的有限集合。A.算法B.数据元素C.数据操作D .数据对象A.操作B.映象C.存储D.关系3 .在数据结构中，从逻辑上可以把数据结构分成 oA.动态结构和静态结构B .紧凑结构和非紧凑结构C.线性结构和非线性结构D.内部结构和外部结构4 .算法分析的目的是，算法分析的两个主要方面是。A.找出数据结构的合理性C.分析算法的效率以求改进A.空间爱杂性和时间爱杂性C.可读性和文档性B.研究算法中的输入和输出的关系D.分析算法的易懂性和文档性B,正确性和简明性D.数据复杂性和程序复杂性5.计算机算法指的是.A.计算方法,它必具备输入、输出和等五个特性。B.排序方法D.调度方法B,可行性、确定性和有穷性 D.易读性、稳定性和安全性C.解决问题的有限运算序列A.可行性、可移植性和可扩充性C.确定性、有穷性和稳定性1.2填空题(将正确的答案填在相应的空中)1 .数据逻辑结构包括、和 三种类型，树形结构和图形结构合称为。2 .在线性结构中，第一个结点 前驱结点，其余每个结点有且只有个前驱结点；最后个结点 后续结点，其余每个结点有且只有 个后续结点。3 .在树形结构中，树根结点没有 结点，其余每个结点有且只有 个直接前驱结点，叶子结点没有 结点，其余每个结点的直接后续结点可以。4 .在图形结构中，每个结点的前驱结点数和后续结点数可以。5 .线性结构中元素之间存在 关系，树形结构中元素之间存在关系，图形结构中元素之间存在关系。6 .算法的五个重要特性是。7 .分析下面算法(程序段)，给出最大语句频度，该算法的时间复杂度是for (i=0;i<n;i+)for (j=O;j<n; j+)Aij=0;8 .分析下面算法(程序段)，给出最大语句频度一，该算法的时间复杂度是for (i=0;i<n;i+)for (j=0; j<i; j+)AiJUJ=O；9 .分析下面算法(程序段)，给出最大语句频度一，该算法的时间复杂度是s=0;for (i=0;i<n;i+)for (j=O;j<n;j+)for (k=0;k<n;k+) s=s+Bmjk;sum=s;10 .分析下面算法(程序段)给出最大语句频度，该算法的时间复杂度是i=s=0;while (s<n) i+；s+=i;/s=s+i11 .分析下面算法(程序段)给出最大语句频度,该算法的时间复杂度是i=l；while (i<=n)i=i*2;1.3算法设计题1 .试写一算法，自大到小依次输出顺序读入的三个数x, 丫和z的值.2 .试写一算法，求出n个数据中的最大值。写出最大语句频度，该算法的时间 复杂度。习题答案1.1 1.C.A2. B.D 3.C4. C,A 5. C,B1.2 1.线性结构、树形结构、图形结构，非线性结构2 .没有、1、没有、13 .前驱、1、后续、任意多个4 .任意多个5 , 一对一、一对多、多对多6 .有穷性、确定性、可行性、输入、输出7 .最大语句频度：I?,时间复杂度：.0(1?)8 .最大语句频度：n(n+l)/2 ,时间复杂度：.0(/)9 .最大语句频度：n3 ,时间复杂度：.0(/)£ £10 .最大语句频度：n?,时间复杂度：.0(1?)11 .最大语句频度：log2n,时间复杂度:.O (log2n )习题2线性表2.1单项选择题1 .一个向量（即一批地址连续的存储单元）第一个元素的存储地址是100,每 个元素的长度为2,则第5个元素的地址是<,A. 110 B. 108 C. 100 D. 1202 .线性表的顺序存储结构是一种一的存储结构，而链式存储结构是一种 的存储结构。A.随机存取B.索引存取 C.顺序存取 D.散列存取3 .线性表的逻辑顺序与存储顺序总是一致的，这种说法。A.正确B.不正确4 .线性表若采用链式存储结构时，要求内存中可用存储单元的地址。A.必须是连续的B.部分地址必须是连续的C.一定是不连续的D.连续或不连续都可以5 .在以下的叙述中，正确的是.A.线性表的顺序存储结构优于链表存储结构B.线性表的顺序存储结构适用于频繁插入/删除数据元素的情况C.线性表的链表存储结构适用于频繁插入/删除数据元素的情况D.线性表的链表存储结构优于顺序存储结构6 .每种数据结构都具备三个基本运算：插入、删除和查找，这种说法。A.正确B.不正确7 .不带头结点的单链表head为空的判定条件是一oA. head= =NULLB. head->next= =NULLC. head->next= =headD. head!=NULL8 .带头结点的单链表head为空的判定条件是一oA. head= =NULLB. head->next= =NULLC. head->next= =headD. head!=NULL9 .非空的循环单链表head的尾结点（由p所指向）满足一。A. p->next= =NULLB. p= =NULLC. p->next= =headD. p= =head10 .在双向循环链表的p所指结点之后插入s所指结点的操作是oA. p->right=s; s->left=p; p->right->left=s; s->right=p->right;B. p->right=s; p->right->left=s; s->left=p; s->right=p->right;C. s->left=p; s->right=p->right; p->right=s; p->right->left=s;D. s->left=p; s->right=p->right; p->right->left=s; p->right=s;11 .在一个单链表中，已知q所指结点是p所指结点的前驱结点，若在q和p 之间插入s结点，则执行.A. s->next=p->next; p->next=s; B. p->next=s->next; s->next=p;B. q->next=s; s->next=p;C. p->next=s; s->next=q;12.在一个单链表中，若p所指结点不是最后结点，在p之后插入s所指结点， 则执行。A. s->next=p; p->next=s;B. s->next=p->next; p->next=s;C. s->next=p->next; p=s;C. p->next=s; s->next=p;13 .在一个单链表中，若删除p所指结点的后续结点，则执行一oA. p->next= p->next->next；B. p= p->next; p->next= p->next->next；C. p->next= p->next;D. p= p->next->next；14 .从一个具有n个结点的单链表中查找其值等于x结点时，在查找成功的情 况下，需平均比较一个结点。A. n B. n/2 C. (n-l)/2D. (n+l)/215 .在一个具有n个结点的有序单链表中插入一个新结点并仍然有序的时间复 杂度是。A.O(l) B. O(n) C. 0 (n2)D. O (nlog2n)16 .给定有n个元素的向量，建立一个有序单链表的时间复杂度是.A. 0(1)B. O(n) C. O (n2)D, O (n*log2n)2.2 填空题（将正确的答案填在相应的空中）1 .单链表可以做 的链接存储表示。2 .在双链表中，每个结点有两个指针域,一个指向,另一个指向.3 .在一个单链表中p所指结点之前插入一个s （值为e）所指结点时，可执行如下 操作：q=head;while （q->next!=p） q=q->next;s= new Node; s->data=e;q->next=; 填空s->next=; 填空4 .在一个单链表中删除p所指结点的后继结点时，应执行以下操作：q= p->next;p->next=; 填空delete ; 填空5 .在一个单链表中p所指结点之后插入一个s所指结点时，应执行s->next=_ _和p->next=的操作。6 .对于一个具有n个结点的单链表，在已知p所指结点后插入一个新结点的时 间复杂度是;在给定值为x的结点后插入一个新结点的时间复杂度是_2.3 算法设计题：1 .设顺序表va中的数据元数递增有序。试写一算法，将x插入到顺序表的适当 位置上，以保持该表的有序性。2 .试写一算法，实现顺序表的就地逆置，即利用原表的存储空间将线性表（即 32. a“）逆置（a“. a“-i.ai） °3 .已知线性表中的元素以值递增有序排列，并以单链表作存储结构。试写一算 法，删除表中所有大于x且小于y的元素（若表中存在这样的元素）同时释放被删 除结点空间。4 .试写一算法，实现单链表的就地逆置（要求在原链表上进行）。习题答案2.11.B2. A,C 3. B9.C10. D11.B2.21.线性结表3. s, p5. p->next, s4. D 5.C6. A 7. A 8. B16.C12.B13.A14.D15.B2.前驱结点、后继结点4. q->next, q6. 0(1) ,O(n)习题3栈和队列6.1 单项选择题1. 一个栈的入栈序列a, b, c, d, e,则栈的不可能的输出序列是.A. edcba B. decba C. dceab D. abcde2 .若已知一个栈的入栈序列是1, 2, 3,，n,其输出序列为pl, p2, p3,， pn,若 pl=n> 则 pi 为 oA. i B. n=i C. n-i+1 D.不确定3 .栈结构通常采用的两种存储结构是一。A.顺序存储结构和链式存储结构B.散列方式和索引方式C.链表存储结构和数组D.线性存储结构和非线性存储结构4 .判定一个顺序栈ST （最多元素为mO）为空的条件是一。A. top !=0 B. top= =0 C. top !=m0 D. top= =m0-l5 .判定一个顺序栈ST （最多元素为mO）为栈满的条件是oA. top! =0 B. top= =0 C. top! =m0 D. top= =m0-16 .栈的特点是一,队列的特点是oA.先进先出 B.先进后出7 .向一个栈顶指针为HS的链栈中插入一个s所指结点时，则执行 o（不带空的头结点）A. HS>next=s;B. s>next= HS>next; HS>next=s;C. s>next= HS; HS=s;D. s>next= HS; HS= HS>next;8 .从一个栈顶指针为HS的链栈中删除一个结点时，用x保存被删结点的值， 则执行 o （不带空的头结点）A. x=HS; HS= HS>next;B. x=HS>data;C. HS= HS>next; x=HS>data;D. x=HS>data; HS= HS>next;9 . 一个队列的数据入列序列是1, 2, 3, 4,则队列的出队时输出序列是oA. 4, 3, 2, 1B. 1, 2, 3, 4C. 1, 4, 3, 2D. 3, 2, 4, 110 .判定一个循环队列QU （最多元素为mO）为空的条件是oA. rear - front= =m0 B. rear-front-1 = =m0C. front= = rearD. front= = rear+111 .判定一个循环队列QU （最多元素为mO,mO=Maxsize-l）为满队列的条件 是 OA. （rear- front）+ Maxsize）% Maxsize = =m0B. rear-front-1= =m0 C. front= =rear D. front= = rear+112.循环队列用数组A0, m-l存放其元素值，Li知其头尾指针分别是front和 rear,则当前队列中的元素个数是.A. (rear-front+m)%mB. rear-front+1C. rear-front-1D. rear-front13.栈和队列的共同点是一。A.都是先进后出B.都是先进先出C.只允许在端点处插入和删除元素D,没有共同点3.2 填空题（将正确的答案填在相应的空中）1 .向量、栈和队列都是一结构，可以在向量的一位置插入和删除元素；对 于栈只能在一插入和删除元素；对于队列只能在一插入元素和一删除元素。2 .向一个长度为n的向量的第i个元素（IWiWn+l）之前插入一个元素时，需 向后移动 个元素。3 .向一个长度为n的向量中删除第i个元素（IWiWn）时，需向前移动一个 元素。4 .向栈中压入元素的操作是一.5 .对栈进行退栈时的操作是一。6 .在一个循环队列中，队首指针指向队首元素的一»7 .从循环队列中删除一个元素时，其操作是一。8 .在具有n个单元的循环队列中，队满时共有一个元素。9 . 一个栈的输入序列是12345,则栈的输出序列43512是。10 . 一个栈的输入序列是12345,则栈的输出序列12345是3.3 算法设计题:1 .输入一个任意的非负十进制整数,输出与其等值的八进值数。2 .按照四则运算加、减、乘、除和嘉运算（t ）优先关系的惯例，并仿照教科 书3. 2节例3-1的格式，画出对下列算术表达式求值时操作数栈和运算符栈的变化 过程：A-B*C/D+E t F3 .假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾元素结点 （注意不设头指针），试编写相应的队列初始化、入队列和出队列的算法。习题答案3.11. C 2, C 3. A 4. B 5,D6. BA 7,C8. B 9. C 10.11. A 12. A 13.C1.线性、任何、栈顶、队尾、队首4.先移动栈顶指针，后存入元素6.前一个位置8. n-19.不可能的2. n-i+13. n-i5.先取出元素，后移动栈顶指针7.先移动队首元素，后取出元素10.可能的习题4 串4.1 单项选择题1 .以下叙述中正确的是。A.串是一种特殊的线性表B.串的长度必须大于零C.串中无素只能是字母D.空串就是空白串2 .空串与空格串是相同的，这种说法 oA.正确B.不正确3 .串是一中特殊的线性表，其特殊性体现在一oA.可以顺序存储B.数据元素是一个字符C.可以链接存储D.数据元素可以是多个字符4 .设有两个串p和q,求q在p中首次出现的位置的运算称作一。A.连接B.模式匹配C.求子串D.求串长5 .设串sl='ABCDEFG', s2='PQRSTL函数con (x,y)返回x和y串的连接串， subs(s,i,j)返回串s的从序号i的字符开始的j个字符组成的子串，len(s)返回串 s 的长度,则 con (subs (sl,2,len (s2), subs (sl,len (s2),2)的结果串是。A. BCDEFB. BCDEFGC. BCPQRSTD. BCDEFEF6 .设串的长度为n,则它的子串个数为 oA.nB.n(n+1)C.n(n+1 )/2D.n(n+1 )/2+14.2 填空题(将正确的答案填在相应的空中)1 .串的两种最基本的存储方式是一O2 .两个串相等的充分必要条件是一o3 .空串是一，其长度等于一。4 .空格串是一，其长度等于一。5 .设 s='LAMA TEACHER',其长度是。4.3 判断题1 .串是由有限个字符构成的连续序列，串长度为串中字符的个数，子串是主串 中符构成的有限序列。()2 .子串定位函数的时间复杂度在最坏情况下为O (n*m),因此子串定位函数 没有实际使用的价值。()3 . KMP算法的最大特点是指主串的指针不需要回溯。4 .设模式串的长度为m,目标串的长度为n；当nm且处理只匹配一次的模 式时，朴素的匹配(即子串定位函数)算法所花的时间代价也可能会更为节省。()5 .如果一个串中的所有字符均在另一串中出现，则说前者是后者的子串。 ()4.3算法设计题1 .编写算法，从串S中删除所有和串t相同的子串。2 .编写算法,实现串的基本操作Replace(&S,T,V)。3 .写一个递归算法来实现字符串逆序存储，要求不另设存储空间。习题答案4 .11. A 2. B 3. B 4. B 5. D 6. C4.21 .顺序存储方式和链接存储方式2 .两个串的长度相等且对应位置的字符相同3 .零个字符的串、零4 .山一个或多个空格字符组成的串、其包含的空格个数5 . 144.3 X X V V X4.43. void reverse(char arr)char ch;int i=l;docin»ch;reverse(arr);arri=ch;i+；while(ch!=,#,&&i<n)习题5 数组和广义表5.1 单项选择题i .常对数组进行的两种基本操作是一。A.建立与删除B.索引和修改C,对数据元素的存取和修改 D.查找与索引2 .二维数组M的成员是6个字符(每个字符占一个存储单元，即一个字节)组 成的串，行下标i的范围从0到8,列下标j的范围从0到9,则存放M至少需要 一个字节；M数组的第8列和第5行共占一个字节。 A. 90B, 180C. 240D. 540 A. 108B. 114C. 54D. 603 .二维数组A中，每个元素的长度为3个字节，行下标i从。到7,列下标j 从。到9,从首地址SA开始连续存放在存储器内，存放该数组至少需要的字节数是A. 80B. 100C.240D. 2704 .二维数组A中，每个元素A的长度为3个字节，行下标i从。到7,列下标 j从0到9,从首地址SA开始连续存放在存储器内，该数组按行存放时，数组元素 A74的起始地址为.A. SA+141 B. SA+144 C. SA+222 D. SA+2255 .二维数组A中，每个元素A的长度为3个字节，行下标i从0到7,列下标 j从0到9,从苜地址SA开始连续存放在存储器内，该数组按列存放时，元素A47 的起始地址为 0A. SA+141 B, SA+180 C. SA+222 D. SA+2255.2填空题(将正确的答案填在相应的空中)1 .已知二维数组AmHn采用行序为主方式存储，每个元素占k个存储单元， 并且第一个元素的存储地址是LOC(A00),则的地址是 o2 .二维数组A1020采用列序为主方式存储，每个元素占一个存储单元并且 AOHO的存储地址是200,则A612的地址是.3 .二维数组A10.205.10采用行序为主方式存储，每个元素占4个存储单元, 并且A105的存储地址是1000,则A18H9的地址是.4 .求下列广义表操作的结果：(1) GetTailGetHead(a,b),(c,d);(2) GetTailGetHeadGetTail(a,b),(c,d)5.利用广义表的GetHead和GetTail操作写出如上题的函数表达式,把原子 banana分别从下列广义表中分离出来.(1) Li=(apple),(pear),(banana),orange);(2) L2=(apple,(pear,(banana),orange);5.3算法设计题：1 .假设稀疏矩阵A和B均以三元组顺序表作为存储结构。试写出矩阵相加的算 法，另设三元组表C存放结果矩阵。2 .假设系数矩阵A和B均以三元组顺序表作为存储结构。试写出满足以下条件 的矩阵相加的算法：假设三元组顺序表A的空间足够大，将矩阵B加到矩阵A上， 不增加A, B之外的附加空间，你的算法能否达到0 (m+n)的时间复杂度？其中m 和n分别为A, B矩阵中非零元的数目。3 .试编写一个以三元组形式输出用十字链表表示的稀疏矩阵中非零元素及其下 标的算法。习题答案5.1 1.C2. D,A 3,C4.C5. B5.2 1. LOC (AOO)+(n*i+j)*k2. 200+ (6*20+12) =3263. 1000+(18-10)*6+(9-5)*4= 12084. (l).(b)(2). (d)5. (l)GetHead GetHeadGetTailGetTailL|;(2) GetHead GelHead GetHeadGetTailL2 ;习题6树和二叉树6.1单项选择题1 .由于二叉树中每个结点的度最大为2,所以二叉树是一种特殊的树，这种说A.正确B.错误2 .假定在一棵二叉树中，双分支结点数为15,单分支结点数为30个，则叶子 结点数为 个。 A. 15 B. 16 C. 17 D. 473 .按照二叉树的定义，具有3个结点的不同形状的二叉树有一种。A. 3B.4 C. 5 D. 64 .按照二叉树的定义，具有3个不同数据结点的不同的二叉树有 种。A. 5 B. 6 C. 30 D. 325 .深度为5的二叉树至多有一个结点。A. 16 B. 32 C. 31 D. 106 .设高度为h的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含 的结点数至少为 oA. 2hB. 2h-l C. 2h+l D. h+l7 .对一个满二叉树，m个树叶，n个结点，深度为h,则。A. n=h+m B. h+m=2n C. m=h-lD. n=2 h-18 .任何一棵二叉树的叶结点在先序、中序和后序遍历序列中的相对次序。 A.不发生改变B.发生改变C.不能确定D.以上都不对9 .如果某二叉树的前根次序遍历结果为stuwv,中序遍历为uwtvs,那么该二叉 树的后序为 oA. uwvts B. vwuts C. wuvts D.wutsv10 .二叉树的前序遍历序列中，任意一个结点均处在其子女结点的前面，这种 说法. A.正确B.错误11 .某二叉树的前序遍历结点访问顺序是abdgcefh,中序遍历的结点访问顺序是 dgbaechf,则其后序遍历的结点访