中山大学网络教育学院2015上半年数据结构C++作业

数据结构（C++）作业一

一、单选题(每题2分，共20分)

1、串是一___D____

A. 不少于一个字母的序列

B. 任意个字母的序列

C. 不少于一个字符的序列

D. 有限个字符的序列

2、一棵左子树为空的二叉树在先序线索化后（不带头结点的线索化），其中的空链域的个数为___A_____。

A. 2

B. 1

C. 0

D. 不确定

3、用数组A[0..N-1]存放一个循环队列，一元素出队时，其队头指针front的修改方法是____A___：

A. front = (front + 1) mod N;

B. front = (front - 2)mod N;

C. front = front + 1;

D. front = front – 2;

4、已知数据表中的每个元素距其最终位置不远，则采用____B___排序算法最省时间。

A.堆排序

B.插入排序

C.快速排序

D.直接选择排序

5、在有n(>0)个结点且为完全二叉树的二叉排序树中查找一个键值，其平均比较次数的数量级为

_____B_____。

A. O(n)

B. O(log2n)

C. O(nlog2n)

D. O(n2)

6、在具有n个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度是__D____。

A.O(1)

B.O(n2)

C.O(nlogn)

D.O(n)

7、下面程序段的时间复杂度是___D_____。

i=1; while(i<=n) i=i*2;

A. O(n)

B. O(n2)

C. O(2n)

D. O(log2n)

8、设一个栈的输入序列为A，B，C，D，则借助一个栈所得到的输出序列不可能是___D____。

A. A，B，C，D

B. D，C，B，A

C. A，C，D，B

D. D，A，B，C

9、在一个长度为n的线性表中顺序查找值为x的元素时，查找时的平均查找长度（即x同元素的平均比较次数，假定查找每个元素的概率都相等）为 C 。

A.n

B.n/2

C.(n+1)/2

D.(n-1)/2

10、设图的顶点数=n, 边数=e，若用邻接表表示图，那么求最短路径的Dijkstra算法的时间复杂度为

___B_____。

A.O(n*e)

B.O(n2)

C.O(n+e)

D.O(n3)

二、填空作图解答题（第1小题6分，其余每题9分，共60分）

1.假设数组A含有n个元素，函数Random(n)需花费常数时间，sort(A,n)需花费nlog2n步，那么，下

面程序段的时间复杂度T(n)= 0(n2 log2n )

sum=0;

for(int i=0; i

sum++;

for (i=0; i

for(j=0; j

A[i]=Random(n);

sort(A, n);

}

2. 有一组关键码序列{40，20，60，15，50，45，95，10，75}，采用Shell 排序方法从小到大进行排序，

假设其间隔序列为5，3，1，请写出每趟的结果。

答案：

第1趟： 40,20,10,15,50,45,95,60,75

第2趟： 15,20,10,40,50,45,95,60,75

第3趟： 10,15,20,40,45,50,60,75,95

3. 对下面的3阶B 树依次插入关键码60，14，6，画出插入三个关键码后并删除关键码20后的结果。

4. 假设某森林的先根遍历序列为EBADCFHGIKJ 和中根遍历序列为ABCDEFGHIJK 。请画出该森林的带双

亲的孩子链表示。

5. 如果采用一运算数栈和一运算符栈来计算由键盘输入的中缀表达式

1+((2+3)*4+5)*9/(5-(6+7)*8)#的值,这里运算数栈用来存放计算过程中使用或产生的运算数，运算符栈用来存放尚未用于计算的运算符，那么按照算法，请将当运算数栈第一次在栈顶出现13时各栈中存放的数据情况填入下表。

运算

数栈

6. 用堆排序算法(“最大堆”排序算法)对关键字{70，33，79，67，46，24，30，40}进行排序，请先

建“最大堆”，然后输出一个堆顶元素, 并调整成堆：初始状态 { 40 ， 33 ， 24 ， 67 ， 46 ， 79 ， 30 ，70 } 所建大顶堆 {79，70，40，67，46，24，30，33} 或 {79，70，67，46，40，24，30，33}

输出一个堆顶元素后调整的结果 {70，67，40，33，46，24，30，79} 或{70，40，67，33，40，24，30，79}

7. 求出下图中顶点A 到其余个顶点的最短路径和最短路径长度。

运算符栈

解：AE=10; AF=17; AB=19; AG=25; AC=26; AD=27; AH=28

三、程序填空题（每空2分，共20分）

1.下面是起泡排序算法的实现。试在程序的每一划线部分填入一条语句或表达式，以使该算法在发现

数据有序时能及时停止。

void BubbleSort(int datalist[], int size) //要排序的数据存放在数组datalist[]中，元素个数=size

{

int exchange,i,j,temp;

i=1;

exchange=1;

while(i

{

_②exchange =0________

for(j=size-1;j>=i; j--)

if(datalist[j-1]>datalist[j])

{

temp=datalist[j-1];

datalist[j-1]=datalist[j];

datalist[j]=temp;

__③exchange =1_________;

}

i++;

}

}

2.下面是仅给出了部分操作某线性表类的定义和实现。试在程序的每一划线部分填入一条语句或表达

式，完成相应的操作。

typedef node {

int elem;

struct node *next;

}node,*LinkListPtr;

typedef struct {

LinkListPtr head,tail;

LinkListPtr curr;

} LinkList;

void InitLinkList(LinkList &L) //初始化线性表

{

L.head = (node *)malloc(sizeof(node));

if(L.head == NULL){cout<<"Insufficient memory available\n" ;exit(0);};

L.tail = L.head; L.curr = L.head;

}

void insert(LinkList &L,int & item) //在表L的当前位置处插入元素item

{

if(L.curr == NULL){cout<<"Current position is not a legal position\n";exit(0); }; node * newnode = (node *)malloc(sizeof(node));

if(newnode == NULL){cout<<"Insufficient memory available\n" ;exit(0);};

new node->elem=item;

④ newnode->next=L.curr->next ;

⑤ L.curr->next= newnode ;

if (L.tail == L.curr) L.tail = L.curr->next;

}

void setFirst(LinkList &L) //将表的当前位置定位于第1个元素

{

⑥ L.curr= L.head ;

}

int currValue(LinkList &L) //将表的当前位置的元素值返回

{

if(!isInList(L))

{

cout<<"Current position is not a legal position\n";exit(0);

}

return ⑦ L.curr->next->elem ;

}

bool isEmpty(LinkList &L) //判断线性表是否为空

{

⑧ return L.head->next->elem==NULL ;

}

bool isInList(LinkList &L) //判断curr是否在表中

{

return (L.curr != NULL) && (L.curr->next != NULL) && (!isEmpty(L));

}

bool find(LinkList &L ,const int & eval) //从表的当前位置开始查找元素eval

{

while (isInList(L))

if ( ⑨ (L.curr->next->elem)==eval ) return TRUE;

else ⑩ L.curr= L.curr->next

return FALSE;

}

147020390 许鸿平

数据结构期末考试复习笔记

判断： 1.线性表的链式存储结构优于顺序存储错误 2.单链表的每个节点都恰好包含一个指针域错误 3.线性表中的元素都可以是各种各样的，但同一线性表中的数据元素具有相同的特性，因 此属于同一数据对象正确 4.在线性表的顺序存储结构中，逻辑上相邻的两个元素在屋里位置上并不一定紧邻。错 误 5.在线性表的数据结构中，插入和删除元素时，移动元素的个数和该元素的位置有关。正 确 6.顺序存储的线性表可以实现随机存取正确 7.栈一定是顺序存储的线性结构错误 8.一个栈的输入序列为A，B,C,D，可以得到输入序列为C,A,B,D 错误 9.队列是一种后进先出的线性表错误 10.树结构中每个节点最多只有一个直接前驱正确 11.二叉树的前序遍历中，任意一个节点均处于其子树节点的前面正确 12.在栈空的情况下，不能做出出栈操作，否则产生溢出正确 13.在前序遍历二叉树的序列中，任何节点的子树的所有节点都是直接跟在该节点之后正 确 填空： 1.在N个节点的顺序表中删除一个节点平均需要移动（（N-1）/2）个节点，具体的移 动次数取决于（表长N和删除位置） 2.在单链表中除首节点外，任意节点的存储位置都由（直接前驱）节点中的指针指示 3.树中节点的最大层次称为树的（度） 4.由一颗二叉树的前序序列和（中）序列可唯一确定这棵二叉树 5.哈弗曼树的带权路径长度（最小）的二叉树 6.二插排序树任意节点的关键字值（大于）其左子树中各节点的关键字值（小于）其 右子树中的各节点关键字值 7.二分查找法，表中元素必须按（关键字有序）存放 选择： 1.用单链表方式存储的线性表，储存每个节点需要两个域，一个数据域，另一个是（B 指针域） 2.设A1，A2，A3为三个节点；P，10，,2代表地址，则如下的链表存储结构称为（B 单链表） 3.单链表的存储密度（C 小于1） 4.在线性表中（B 中间元素）只有一个直接前驱和一个直接后续 5.两个指针P和Q，分别指向单链表的两个元素P所指元素时Q所指元素前驱的条 件是（D P==Q） 6.在栈中存取数据的原则是（B 后进先出） 7.顺序栈判空的条件是（C top==-1） 8.串是一种特殊的线性表，其特殊性体现在（B 数据元素是一个字符） 9.求字符串T和字符串S中首次出现的位置的操作为（C 串的模式匹配） 10.深度为H的二叉树至多有（B 2H-1）个节点

2021北京科技大学计算机科学与技术考研真题经验参考书

我本科在燕山大学，作为河北省的一个旅游城市，旅游季节超级多以外，真的没有开拓我太多眼界，但是鉴于老师负责而且很专业，教会了我很多知识。但是我们专业，在一二线城市，机会多，企业多，就业及科研合作机会也多，所以，选择学校，一定要先看城市，再选学校。对我而言，研究生考进北科大，也是一项很大的挑战和提升。下面是我整理的一些考研经验与心得，希望能助你一臂之力，早日考进自己理想的学校。 数学： 对于计算机科技而言，数学很重要。我们专业是以数学逻辑为基础的，数据结构是建立在数学基础之上的一门学科。可以说，数学是我们的工具书。数学真的很重要。要从3月份就开始复习，这样后面会比较轻松。建议先从基础教材着手，看完教材，要做课后练习题，测试自己是否掌握了本章节的知识。这样，高数和线性代数的课本过一遍，需要2-3个月的时间。第二阶段就要做大量的练习了，研数盒子，这个公众号的特点是习题为主，数学一定要多加练习，这个公众号就是以练习各种习题为主，每周都会发各种作业和讲解，研数盒子有一套教材叫做研数800题非常好。做的过程中，对错题要着重注意并记录一下，建立一个错题本，然后针对没做对的题，分析归纳，然后回归到课本上，查到对应章节，重新温习。这套练习要刷个3遍左右，每一遍你都会有新的认识和体会，个人觉得效果会比做3套不同的题更有效。3遍下来，精读的效果就很明显了，这就是“温故知新”的道理。10月开始，真题要开始做起来了，向上面一样，建立错题本，这个本会是你考研备考后期独一无二的宝典。总之，数学真的很重要，要自始至终坚持到底，除了反复多加练习，还要多思考。 英语： 阅读理解很重要，备考需要坚持每天2篇阅读，开始的时候要精度，好好分析一下句式，掌握好主谓宾从，整段意思也就很容易理解了。学会分析句式以后，后续就会容易很多。再就是单词部分，买一本基础的单词书<<一本单词>>，早晨背完，晚上回忆，过电影一样的，重要的单词，要熟悉到知道在哪个位置，上面的解释是什么。没事看看，不想看书的时候看看，随手看看，遍数多了，自然会记住了，或者每个考生都有自己独特的单词记忆方法，请大家用尽十八般武艺，只有一个目的——背好单词，大家也可以关注蛋核英语公众号。再说说作文，作文呢，一定要积累名言警句，有华丽的辞藻才能表达出自己的观点对不对？作文

数据结构习题及参考答案

习题1 一、单项选择题 A1.数据结构是指（）。 A.数据元素的组织形式 B.数据类型 C.数据存储结构 D.数据定义 C2.数据在计算机存储器内表示时，物理地址与逻辑地址不相同的，称之为（）。 A.存储结构 B.逻辑结构 C.链式存储结构 D.顺序存储结构 D3.树形结构是数据元素之间存在一种（）。 A.一对一关系 B.多对多关系 C.多对一关系 D.一对多关系 B4.设语句x++的时间是单位时间，则以下语句的时间复杂度为（）。 for(i=1; i<=n; i++) for(j=i; j<=n; j++) x++; A.O(1) B.O(2n) C.O(n) D.O(3n) CA5.算法分析的目的是（1），算法分析的两个主要方面是（2）。 （1） A.找出数据结构的合理性 B.研究算法中的输入和输出关系 C.分析算法的效率以求改进 D.分析算法的易懂性和文档性 （2） A.空间复杂度和时间复杂度 B.正确性和简明性 C.可读性和文档性 D.数据复杂性和程序复杂性 6.计算机算法指的是（1），它具备输入，输出和（2）等五个特性。 （1） A.计算方法 B.排序方法 C.解决问题的有限运算序列 D.调度方法 （2） A.可行性，可移植性和可扩充性 B.可行性，确定性和有穷性 C.确定性，有穷性和稳定性 D.易读性，稳定性和安全性 7.数据在计算机内有链式和顺序两种存储方式，在存储空间使用的灵活性上，链式存储比顺序存储要（）。 A.低 B.高 C.相同 D.不好说 8.数据结构作为一门独立的课程出现是在（）年。 A.1946 B.1953 C.1964 D.1968 9.数据结构只是研究数据的逻辑结构和物理结构，这种观点（）。 A.正确 B.错误 C.前半句对，后半句错 D.前半句错，后半句对

川农16《房屋建筑学(本科)》在线作业满分答案

《房屋建筑学(本科)》16年9月 单选题（共20 道试题，共100 分。）得分：100 1. 下列哪种做法属于抹灰类饰面（） A. 瓷锦砖面 B. 塑料壁纸面 C. 水磨石面 D. 石面 正确答案：C 满分：5 分得分：5 2. 现浇肋梁楼板由（）现浇而成。 A. 混凝土、砂浆、钢筋 B. 柱、次梁、主梁 C. 板、次梁、主梁 D. 砂浆、次梁、主梁 正确答案：C 满分：5 分得分：5 3. 下列不属于三阶段设计的是：（） A. 建筑设计 B. 初步设计 C. 技术设计 D. 施工图设计 正确答案：A 满分：5 分得分：5 4. 一般单股人流通行最小宽度取（） A. 450mm B. 500mm C. 550mm D. 600mm 正确答案：B 满分：5 分得分：5 5. 梯井宽度以（）为宜 A. 60～150mm

B. 100～200mm C. 60～200mm D. 60～150mm 正确答案：C 满分：5 分得分：5 6. 预制板在墙上的搁置长度不少于：） A. 90毫米 B. 180毫米 C. 60毫米 D. 120毫米 正确答案：A 满分：5 分得分：5 7. 卧室净高常取（） A. 2.2~2.4 B. 2.8~3.0 C. 3.0~3.6 D. 4.2~6. 正确答案：B 满分：5 分得分：5 8. 木地面按其构造做法有：（） A. 空铺、实铺、砌筑 B. 实铺、空铺、拼接 C. 粘贴、空铺、实铺 D. 砌筑、拼接、实铺 正确答案：C 满分：5 分得分：5 9. 教室第一排座位距黑板的距离必须大于等于（）m，以保证垂直视角大于（）度。 A. 2；15 B. 1.5；45 C. 2；45

郝斌数据结构自学笔记--知识点+程序源代码

郝斌数据结构自学笔记 --知识点+程序源代码 By-HZM 1_什么叫做数据结构 数据结构概述 定义 我们如何把现实中大量而复杂的问题以特定的数据类型和特定的存储结构保存到主存储器（内存）中，以及在此基础上为实现某个功能（比如查找某个元素，删除某个元素，对所有元素进行排序）而执行的相应操作，这个相应的操作也叫算法。 ~ 数据结构=个体的存储+个体的关系存储 算法=对存储数据的操作 2_衡量算法的标准 算法 解题的方法和步骤 ~ 衡量算法的标准 1）时间复杂度：大概程序执行的次数，而非执行的时间 2）空间复杂度：算法执行过程中大概所占用的最大内存 3）难易程度 4）健壮性 3_数据结构的特点 【 数据结构的地位 数据结构是软件中最核心的课程 程序=数据的存储+数据的操作+可以被计算机执行的语言 4_预备知识_指针_1 5_预备知识_指针_2 * 指针的重要性： 指针是C语言的灵魂 定义：

地址： 地址是内存单元的编号,从0开始的非负整数，范围：0-FFFFFFFF【0-4G-1】 CPU=====地址线，控制线，数据线=====内存 指针： … 指针就是地址，地址就是指针。 指针变量是存放内存单元地址的变量。 指针的本质是一个操作受限的非负整数。 分类： 1.基本类型的指针 2.指针和数组的关系 ? 变量并不一定连续分配，随机分配内存。 内存： 内存是多字节组成的线性一维存储空间。 内存的基本划分单位是字节。 每个字节含有8位，每一位存放1个0或1个1. 内存和编号是一一对应的。 （ 软件在运行前需要向操作系统申请存储空间。在软件运行期间，该软件所占空间不再分配给其他软件。当软件运行完毕后，操作系统将回收该内存空间（操作系统并不清空该内存空间中遗留下来的数据）。 NOTE：1）指针变量也是变量，普通变量前不能加*，常亮和表达式前不能加&。 2）局部变量只在本函数内部使用。 如何通过被调函数修改主调函数中普通变量的值。 1）实参为相关变量的地址； < 2）形参为以该变量的类型为类型的指针变量； 3）在被调函数中通过 *形参变量名的形式的形式就可以修改主函数。 CASE 1 #include<> int main(void) { |

2015数据结构与算法在线作业答案

单选题 1.【第1章第2节】数据结构课程主要研究以下三方面的内容，它们是______。 ? A 数据、数据元素、数据类型 ? B 数据元素、数据类型、算法实现 ? C 数据元素、数据的逻辑结构、数据的存储结构 ? D 数据的逻辑结构、数据的存储结构、数据的运算 ? 单选题 2.【第1章第2节】在数据结构中，与所使用的计算机无关的是数据的____结 构。 ? A 存储 ? B 物理 ? C 逻辑 ? D 物理与存储

? 判断题 3.【第1章第2节】逻辑结构相同时物理结构也应该相同。 ?正确错误 ? 单选题 4.【第1章第3节】设某二维数组A［1..n，1..n］，则在该数组中用顺序查找 法查找一个元素的时间复杂性的量级为______。 ? A O（log2n） ? B O(n) ? C O(nlog2n) ? D O(n^2) ? 单选题 5.【第1章第3节】计算机算法是指______。

? A 计算方法 ? B 排序方法 ? C 调度方法 ? D 解决问题的有限运算序列 ? 判断题 6.【第1章第3节】所谓时间复杂度是指最坏情况下，估算算法执行时间的一 个上界 ?正确错误 ? 单选题 7.【第3章第2节】在长度为n 的双链表中某结点（已知其地址）之前，插入 一个新结点的时间复杂度是_____ 。 ? A O(n) ? B O(log2n)

? C O(1) ? D O(n^2) ? 单选题 8.【第3章第2节】线性表按链式方式存储时，每个结点的存储包括_____两部 分。 ? A 数据值与符号 ? B 数据与指针 ? C 数据与表名 ? D 数据项与符号 ? 单选题 9.【第3章第2节】链表不具有的特点是_____。 ? A 可随机访问任一元素

数据结构复习笔记

数据结构复习笔记 作者: 网络转载发布日期: 无 数据就是指能够被计算机识别、存储和加工处理的信息的载体。 数据元素是数据的基本单位，有时一个数据元素可以由若干个数据项组成。数据项是具有独立含义的最小标识单位。如整数这个集合中，10这个数就可称是一个数据元素.又比如在一个数据库(关系式数据库)中，一个记录可称为一个数据元素，而这个元素中的某一字段就是一个数据项。 数据结构的定义虽然没有标准，但是它包括以下三方面内容：逻辑结构、存储结构、和对数据的操作。这一段比较重要，我用自己的语言来说明一下，大家看看是不是这样。 比如一个表(数据库)，我们就称它为一个数据结构，它由很多记录(数据元素)组成，每个元素又包括很多字段(数据项)组成。那么这张表的逻辑结构是怎么样的呢? 我们分析数据结构都是从结点(其实也就是元素、记录、顶点，虽然在各种情况下所用名字不同，但说的是同一个东东)之间的关系来分析的，对于这个表中的任一个记录(结点)，它只有一个直接前趋，只有一个直接后继(前趋后继就是前相邻后相邻的意思)，整个表只有一个开始结点和一个终端结点，那我们知道了这些关系就能明白这个表的逻辑结构了。 而存储结构则是指用计算机语言如何表示结点之间的这种关系。如上面的表，在计算机语言中描述为连续存放在一片内存单元中，还是随机的存放在内存中再用指针把它们链接在一起，这两种表示法就成为两种不同的存储结构。(注意，在本课程里，我们只在高级语言的层次上讨论存储结构。) 第三个概念就是对数据的运算，比如一张表格，我们需要进行查找，增加，修改，删除记录等工作，而怎么样才能进行这样的操作呢? 这也就是数据的运算，它不仅仅是加减乘除这些算术运算了，在数据结构中，这些运算常常涉及算法问题。 弄清了以上三个问题，就可以弄清数据结构这个概念。 -------------------------------------------------------------------------------- 通常我们就将数据的逻辑结构简称为数据结构，数据的逻辑结构分两大类：线性结构和非线性结构(这两个很容易理解) 数据的存储方法有四种：顺序存储方法、链接存储方法、索引存储方法和散列存储方法。-------------------------------------------------------------------------------- 下一个是难点问题，就是算法的描述和分析，主要是算法复杂度的分析方法及其运用。首先了解一下几个概念。一个是时间复杂度，一个是渐近时间复杂度。前者是某个算法的时间耗费，它是该算法所求解问题规模n的函数，而后者是指当问题规模趋向无穷大时，该算法时间复杂度的数量级。 当我们评价一个算法的时间性能时，主要标准就是算法的渐近时间复杂度，因此，在算法分析时，往往对两者不予区分，经常是将渐近时间复杂度T(n)=O(f(n)简称为时间复杂度，其中的f(n)一般是算法中频度最大的语句频度。 此外，算法中语句的频度不仅与问题规模有关，还与输入实例中各元素的取值相关。但是我们总是考虑在最坏的情况下的时间复杂度。以保证算法的运行时间不会比它更长。 常见的时间复杂度，按数量级递增排列依次为：常数阶O(1)、对数阶O(log2n)、线性阶O(n)、线性对数阶O(nlog2n)、平方阶O(n^2)、立方阶O(n^3)、k次方阶O(n^k)、指数阶O(2^n)。 时间复杂度的分析计算请看书本上的例子，然后我们通过做练习加以领会和巩固。 数据结构习题一 --------------------------------------------------------------------------------

中山大学研究生入学考试数据结构1997真题

中山大学九七年数据结构考研 一、（10分）解释下列名词： （1）二叉排序树（binary sort tree）; （2）关键路径（critical path）; （3）trie树。 二、（10分）简答题： （1）已知二叉树先序遍历结果为ABGFHCEIKDJ,中序遍历结果为GBHFAEKICDJ,求它的后序遍历结果。 （2）下表中A、B、C、D、E、F代表6个城市，表中数字是各城市间各公路的造价，构造这个交通网络的最小生成树。 A B C D E F A B C D E F 27 16 15 4 30 10 8 26 6 3 24 18 20 17 28 （3）给定权集合（5、4、10、1、6、8）构造相应的哈夫曼树。 （4）什么是二分查找法（Binary Search）？这种查找法有什么优、缺点？ 三、（10分）什么是归并排序？实现二路归并排序总的时间复杂度为多少？给出一组关键字序 列：（16、2、36、99、88、12、65、88、30），对它进行二路归路并排序，试写出排序过程示意图。并且统计第一遍和第二遍排序所进行的关键字比较次数。 四、（10分）已知计算多项式值的归并算法如下： FUNCTION (x: real; n: integer; ): real; BEGIN IF n=0 THEN p:=1 ELSE IF n=1 THEN p:=x ELSE p:=((2*n-1)*x*p(x,n-1)-(n-1)*p*(x,n-2))/n END; 写出计算该多项式值的非递归算法。 五、（10分）按图的宽度优先搜索法写一算法判别以邻接矩阵存储的有向图中是否存在由顶点 Vi到顶点Vj的路径（i≠j）.

2012版《数据结构高分笔记》更新补丁之外部排序

※特别章外部排序（2012版《数据结构高分笔记》更新补丁） ·外部排序简介 所谓外部排序，即对外存中的数据进行排序（相对于内部排序而言），也可以说是对文件中的数据进行排序。有了内部排序算法，为什么还要外部排序？因为文件太大，内存放不下。外排做法可以概括为一句话：将内存作为工作空间来调整外存中数据的位置。 具体可以分成以下三个要点： ①文件在外存中的组织； ②文件在内存中的排序； ③文件在内外存之间的交换。 说明：本补丁是2012年数据结构考研大纲新增内容，虽然知识点不多，但由于第一年被列入考试范围，所以大家要重视。 ·归并排序法 归并排序法是外排序中最常用的方法，分为两个执行阶段。第一阶段：将文件中的数据分段输入到内存中，在内存中用内排序方法对其分类，这样排序完的文件段称作归并段，然后将其写回外存中而在外存中形成了许多初始归并段。第二阶段：对这些初始归并段采用某种归并方法，进行多遍归并，最后在外存上形成整个文件的单一归并段，也就完成了这个文件的外排序。 说明：外排序中的归并排序法和内排序中的归并法是类似的，都是由小单元逐渐归并成单元的过程，注意对比，加深理解。 归并排序算法分两个阶段： 1.初始归并段的形成 其过程是根据缓冲区大小，由文件输入（由外存读入内存）记录，当记录充满缓冲区后，选择最小的（以递增排序为例）记录输出（由内存写出到外存），其空缺位置由下一个输入记录来取代，输出的记录成为当前初始归并段的一部分。如果新输入的记录不能成为当前生成的归并段的一部分，即它比生成的当前部分归并段最大的记录要小（如例1中的关键字11，比15要小，不可能出现在当前归并段中），它将等待生成下一个归并段时提供选择。反复进行上述操作，直到所有新输入的记录关键字都小于最后输出记录的关键字时（如步骤9中的所有关键字都比83小，则以83为结尾的归并段生成完毕），就生成了一个初始归并段。接着继续生成下一个归并段，直到全部记录都处理完毕为止。 下面通过例题来具体说明一下。 例1.设输入文件的各个记录的关键字为： 15,19,04,83,12,27,11,25,16,34,26,07,10,90,06, ... ... 假设内存缓冲区可容纳4个记录，成初始归并段。如下表所示，给出了生成初始归并段过程中各步的缓冲区内容和输出结果。

数据结构习题及参考答案 .

习题1 一、单项选择题 1.数据结构是指（）。 A.数据元素的组织形式 B.数据类型 C.数据存储结构 D.数据定义 2.数据在计算机存储器内表示时，物理地址与逻辑地址不相同的，称之为（）。 A.存储结构 B.逻辑结构 C.链式存储结构 D.顺序存储结构 3.树形结构是数据元素之间存在一种（）。 A.一对一关系 B.多对多关系 C.多对一关系 D.一对多关系 4.设语句x++的时间是单位时间，则以下语句的时间复杂度为（）。 for(i=1; i<=n; i++) for(j=i; j<=n; j++) x++; A.O(1) B.O(2n) C.O(n) D.O(3n) 5.算法分析的目的是（1），算法分析的两个主要方面是（2）。 （1） A.找出数据结构的合理性 B.研究算法中的输入和输出关系 C.分析算法的效率以求改进 D.分析算法的易懂性和文档性 （2） A.空间复杂度和时间复杂度 B.正确性和简明性 C.可读性和文档性 D.数据复杂性和程序复杂性 6.计算机算法指的是（1），它具备输入，输出和（2）等五个特性。 （1） A.计算方法 B.排序方法 C.解决问题的有限运算序列 D.调度方法 （2） A.可行性，可移植性和可扩充性 B.可行性，确定性和有穷性 C.确定性，有穷性和稳定性 D.易读性，稳定性和安全性 7.数据在计算机内有链式和顺序两种存储方式，在存储空间使用的灵活性上，链式存储比顺序存储要（）。 A.低 B.高 C.相同 D.不好说 8.数据结构作为一门独立的课程出现是在（）年。 A.1946 B.1953 C.1964 D.1968 9.数据结构只是研究数据的逻辑结构和物理结构，这种观点（）。 A.正确 B.错误 C.前半句对，后半句错 D.前半句错，后半句对

数据结构学习总结

数据结构学习总结 经过一学期的学习，我对数据结构有了我自己的认识。一开始，我以为它和C语言和C++一样，都是讲一门语言。但学习之后，发现事实并不是这样，在数据结构的学习中，有线性表，有队，有栈，有树，有图等等。这些看起来没有关系，其实之间有着千丝万缕的联系。线性表是其中最简单的，所以在前几章学习，后面依次逐章变难，学起来也很吃力。 《数据结构与算法》以基本数据结构和算法设计策略为知识单元，系统地介绍了数据结构的知识与应用、计算机算法的设计与分析方法，主要内容包括线性表、树、图和广义表、算法设计策略以及查找与排序算法等。 线性表是最基本、最简单、也是最常用的一种数据结构。线性表中数据元素之间的关系是一对一的关系，即除了第一个和最后一个数据元素之外，其它数据元素都是首尾相接的。线性表的逻辑结构简单，便于实现和操作。因此，线性表这种数据结构在实际应用中是广泛采用的一种数据结构。线性表具有如下的结构特点：均匀性：虽然不同数据表的数据元素可以是各种各样的，但对于同一线性表的各数据元素必定具有相同的数据类型和长度。有序性：各数据元素在线性表中的位置只取决于它们的序号，数据元素之前的相对位置是线性的，即存在唯一的“第一个“和“最后一个”的数据元素，除了第一个和最后一个外，其它元素前面均只有一个数据元素直接前驱和后面均只有一个数据元素（直接后继）。在实现线性表数据元素的存储方面，一般可用顺序存储结构和链式存储结构两种方法。链式存储结构将在本网站线性链表中介绍，本章主要介绍用数组实现线性表数据元素的顺序存储及其应用。另外栈、队列和串也是线性表的特殊情况，又称为受限的线性结构。 链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生

广工数据结构复习题目及答案说课讲解

广工2015数据结构复习题目及答案

《数据结构-C语言版》 第一章绪论 单项选择题 1．在数据结构中，数据的基本单位是_____ ____。 A. 数据项 B. 数据类型 C. 数据元素 D. 数据变量 2．数据结构中数据元素之间的逻辑关系被称为__ ____。 A. 数据的存储结构 B. 数据的基本操作 C. 程序的算法 D. 数据的逻辑结构3．在数据结构中，与所使用计算机无关的是数据的____ ___。 A. 存储结构 B. 逻辑和物理结构 C. 逻辑结构 D. 物理结构 4．在链式存储结构中，数据之间的关系是通过____ ____体现的。 A. 数据在内存的相对位置 B. 指示数据元素的指针 C. 数据的存储地址 D. 指针 5．计算算法的时间复杂度是属于一种____ ___。 A. 事前统计的方法 B. 事前分析估算的方法 C. 事后统计的方法 D. 事后分析估算的方法 6．在对算法的时间复杂度进行估计的时候，下列最佳的时间复杂度是____ __。 A. n2 B. nlogn C. n D. logn 7．设使用某算法对n个元素进行处理，所需的时间是 T(n)=100nlog2n+200n+2000，则该算法的渐近时间复杂度为____ ___。 A. O(1) B. O(n) C. O(200n) D. O(nlog2n)

CDCBBDD 第二章线性表 单项选择题 1．链表不具有的特点是____ ____。 A. 可随机访问任一元素 B. 插入和删除时不需要移动元素 C. 不必事先估计存储空间 D. 所需空间与线性表的长度正比 2．设顺序表的每个元素占8个存储单元。第1个单元的存储地址是100，则第6个元素占用的最后一个存储单元的地址为。 A. 139 B. 140 C. 147 D. 148 3．在线性链表存储结构下，插入操作算法。 A. 需要判断是否表满 B. 需要判断是否表空 C. 不需要判断表满 D. 需要判断是否表空和表满 4．在一个单链表中，若删除p所指结点的后继结点，则执行。 A. p->next = p->next->next; B. p->next = p->next; C. p = p->next->next; D. p = p->next; p->next = p->next->next; 5．将长度为n的单链表接在长度为m的单链表之后的算法时间复杂度 为。 A. O(n) B. O(1) C. O(m) D. O(m+n) 6．需要预分较大空间，插入和删除不需要移动元素的线性表，其存储结构是。 A. 单链表 B. 静态链表 C. 线性链表 D. 顺序存储方式 ACCABB 填空题 1．在带表头结点的单链表中，当删除某一指定结点时，必须找到该结点的 _____结点。 2．在单链表中，指针p所指结点为最后一个结点的条件是。 3．将两个各有n个元素的有序表归并成一个有序表，其最少的比较次数 是。 4．在一个长度为n的顺序表中第i个元素（1≤i≤n）之前插入一个元素时，需向后移动元素的个数是。 5．在长度为n的顺序表中插入一个元素的时间复杂度为。

操作系统可用来进行考研复习资料(1)

第八章死锁习题及答案 一、填空题 1．进程的“同步”和“互斥”反映了进程间① 和② 的关系。 【答案】①直接制约、②间接制约 【解析】进程的同步是指在异步环境下的并发进程因直接制约而互相发送消息，进行相互合作、相互等待，使得各进程按一定的速度执行的过程；而进程的互斥是由并发进程同时共享公有资源而造成的对并发进程执行速度的间接制约。 2．死锁产生的原因是① 和② 。 【答案】①系统资源不足、②进程推进路径非法 【解析】死锁产生的根本原因是系统的资源不足而引发了并发进程之间的资源竞争。由于资源总是有限的，我们不可能为所有要求资源的进程无限地提供资源。而另一个原因是操作系统应用的动态分配系统各种资源的策略不当，造成并发进程联合推进的路径进入进程相互封锁的危险区。所以，采用适当的资源分配算法，来达到消除死锁的目的是操作系统主要研究的课题之一。 3．产生死锁的四个必要条件是① 、② 、③ 、 ④ 。 【答案】①互斥条件、②非抢占条件、③占有且等待资源条件、④循环等待条件 【解析】 互斥条件：进程对它所需的资源进行排它性控制，即在一段时间内，某资源为一进程所独占。 非抢占条件：进程所获得的资源在未使用完毕之前，不能被其它进程强行夺走，即只能由获得资源的进程自己释放。 占有且等待资源条件：进程每次申请它所需的一部分资源，在等待新资源的同时，继续占有已分配到的资源， 循环等待条件：存在一进程循环链，链中每一个进程已获得的资源同时被下一个进程所请求。 4．在操作系统中，信号量是表示① 的物理实体，它是一个与② 有关的整型变量，其值仅能由③ 原语来改变。 【答案】①资源，②队列，③P-V 【解析】信号量的概念和 P-V原语是荷兰科学家 E．W．Dijkstra提出来的。信号量是一个特殊的整型量，它与一个初始状态为空的队列相联系。信号量代表了资源的实体，操作系统利用它的状态对并发进程共享资源进行管理。信号量的值只能由P-V原语来改变。 5．每执行一次P原语，信号量的数值S减1。如果S>=0，该进程① ；若S<0，则② 该进程，并把它插入该③ 对应的④ 队列中。 【答案】①继续执行，②阻塞（等待），③信号量，④阻塞（等待） 【解析】从物理概念上讲，S＞0时的数值表示某类资源可用的数量。执行 一次P原语，意味着请求分配一个单位的资源，因此描述为S=S－1。当S<0时，表示已无资源，这时请求资源的进程将被阻塞，把它排在信号量S的等待队列中。此时，S的绝对值等于信号量队列上的阻塞的进程数目。

广工2015数据结构复习题目及答案课案

《数据结构-C语言版》 第一章绪论 单项选择题 1．在数据结构中，数据的基本单位是_____ ____。 A. 数据项 B. 数据类型 C. 数据元素 D. 数据变量 2．数据结构中数据元素之间的逻辑关系被称为__ ____。 A. 数据的存储结构 B. 数据的基本操作 C. 程序的算法 D. 数据的逻辑结构3．在数据结构中，与所使用计算机无关的是数据的____ ___。 A. 存储结构 B. 逻辑和物理结构 C. 逻辑结构 D. 物理结构4．在链式存储结构中，数据之间的关系是通过____ ____体现的。 A. 数据在内存的相对位置 B. 指示数据元素的指针 C. 数据的存储地址 D. 指针 5．计算算法的时间复杂度是属于一种____ ___。 A. 事前统计的方法 B. 事前分析估算的方法 C. 事后统计的方法 D. 事后分析估算的方法 6．在对算法的时间复杂度进行估计的时候，下列最佳的时间复杂度是____ __。 A. n2 B. nlogn C. n D. logn 7．设使用某算法对n个元素进行处理，所需的时间是T(n)=100nlog2n+200n+2000，则该算法的渐近时间复杂度为____ ___。 A. O(1) B. O(n) C. O(200n) D. O(nlog2n)

CDCBBDD 第二章线性表 单项选择题 1．链表不具有的特点是____ ____。 A. 可随机访问任一元素 B. 插入和删除时不需要移动元素 C. 不必事先估计存储空间 D. 所需空间与线性表的长度正比 2．设顺序表的每个元素占8个存储单元。第1个单元的存储地址是100，则第6个元素占用的最后一个存储单元的地址为。 A. 139 B. 140 C. 147 D. 148 3．在线性链表存储结构下，插入操作算法。 A. 需要判断是否表满 B. 需要判断是否表空 C. 不需要判断表满 D. 需要判断是否表空和表满 4．在一个单链表中，若删除p所指结点的后继结点，则执行。 A. p->next = p->next->next; B. p->next = p->next; C. p = p->next->next; D. p = p->next; p->next = p->next->next; 5．将长度为n的单链表接在长度为m的单链表之后的算法时间复杂度为。A. O(n) B. O(1) C. O(m) D. O(m+n) 6．需要预分较大空间，插入和删除不需要移动元素的线性表，其存储结构是。 A. 单链表 B. 静态链表 C. 线性链表 D. 顺序存储方式ACCABB 填空题 1．在带表头结点的单链表中，当删除某一指定结点时，必须找到该结点的_____结点。2．在单链表中，指针p所指结点为最后一个结点的条件是。 3．将两个各有n个元素的有序表归并成一个有序表，其最少的比较次数是。4．在一个长度为n的顺序表中第i个元素（1≤i≤n）之前插入一个元素时，需向后移动元素的个数是。 5．在长度为n的顺序表中插入一个元素的时间复杂度为。 1前驱 2 p->next==NULL

川农2015结构作业满分

一、单选题（共 20 道试题，共 70 分。） V 1. 11.混凝土强度等级由（）确定 A. f B. uk C. f D. k E. f F. m G. f tk 满分：3.5 分 2. 21.下列钢筋混凝土构件破坏中属于脆性破坏的是 A. 钢筋混凝土板正截面适筋破坏 B. 钢筋混凝土柱大偏心受压破坏 C. 钢筋混凝土柱小心受压破坏 D. 钢筋混凝土受扭构件部分超筋破 满分：3.5 分 3. 10.在其他条件相同时，与素混凝土梁相比，钢筋混凝土梁承载能力 A. 相同 B. 提高许多

C. 有所提高 D. 降低 满分：3.5 分 4. 16.计算混凝土纯扭构件开裂扭矩的公式是 A. 根据弹性理论导出 B. 假定截面各点剪应力都达到ft C. 经验公式 D. 在弹性理论基础上考虑塑性影响 满分：3.5 分 5. 23.某两端固定对称配筋的钢筋砼构件，在受荷前砼发生收缩，这时砼与钢筋中的应力情况为 A. 砼中产生压应力，钢筋中产生拉应力 B. 砼中产生拉应力，钢筋中产生拉应力 C. 砼中产生拉应力，钢筋中应力为0 D. 砼及钢筋中应力均为0 满分：3.5 分 6. 18.混凝土各种强度指标之间的关系是 A. f B. k>f C. u,k>ftk D. ftk>f

E. u,k>f F. k G. f H. u,k>ftk>f I. k J. f K. u,k>f L. k>ftk 满分：3.5 分 7. 3.当钢筋混凝土梁的抵抗弯矩图不切入设计弯矩图时，可保证 A. 斜截面抗剪能力 B. 正截面抗弯和斜截面抗剪能力 C. 正截面抗弯能力 D. 斜截面抗弯能力 满分：3.5 分 8. 5.钢筋混凝土偏心受压构件发生受拉破坏的条件是： A. 偏心距较大且受拉一侧钢筋过多 B. 偏心距较大且受拉一侧钢筋偏少 C. 偏心距较小且受拉一侧钢筋过多

2018北大计算机考研经验分享

2018北大计算机考研经验分享 我本科毕业于北京科技大学计算机科学与技术专业，研究生将就读于北京大学计算机技术专业。初试考研总分接近370+分，计算机基础综合135分，在专业课上算是有些心得吧。 写这篇经验贴的初衷一是看过很多经验贴，都是比较散乱的回顾+感受，没有系统的复习方法；二是我在新祥旭考研一对一做专业课辅导老师，算是给自己打个广告吧，多说一句，我主要是针对考北大计算机专业的学生。当然，虽然打了一下广告，但是这篇帖子的经验还是希望大家认真看，我觉得还是能够对学弟学妹们有所裨益的。 ，下面主要和大家聊一聊北大计算机考研的情况，政治、英语、数学这些课我就不多说了，这几门课程的资料、老师都是比较成熟且成功的，大家在网上多看看就知道怎么回事了。今天，主要是说专业课以及北大计算机的招录情况。 【北大招录情况】 2018年北大软微计算机技术复试线：复试线为300分，单科线也是50+80。具体的招录比现在基本是没有相关数据的，但是招生人数还是可查的，根据软微学院官网数据：整个软件与微电子学院招收全日制654人，非全日制156人。其中计算机技术专业全日制招生310人，

包含推免生接近70人，留给其他考生的名额为240左右。 总之，现在是大数据时代，北大计算机技术的关注度也越来越高，所以以后考研竞争难度也会越来越大。 【参考书目】 822计算机基础综合 专业课教材 《数据结构》（C语言版）严蔚敏清华大学出版社 《计算机操作系统》汤子瀛西安电子科技大学出版社 《计算机网络》谢希仁电子工业出版社 《计算机组成原理》唐朔飞高等教育出版社 专业辅导书： 王道系列 《数据结构考研复习指导》 《计算机组成原理考研复习指导》 《操作系统考研复习指导》 《计算机网络考研复习指导》 《计算机专业基础综合考试指导全书》 《计算机专业基础综合考试名校真题精析》 《计算机专业基础综合考试最后8套模拟题》

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。

数据结构复习笔记

第一章概论 1.数据：信息的载体,能被计算机识别、存储和加工处理。 2.数据元素：数据的基本单位，可由若干个数据项组成，数据项是具有独立含义的最小标识单位。 3.数据结构：数据之间的相互关系，即数据的组织形式。 它包括：1）数据的逻辑结构，从逻辑关系上描述数据，与数据存储无关，独立于计算机； 2）数据的存储结构，是逻辑结构用计算机语言的实现，依赖于计算机语言。 3）数据的运算，定义在逻辑结构上，每种逻辑结构都有一个运算集合。常用的运算：检索/插入/删除/更新/排序。 4.数据的逻辑结构可以看作是从具体问题抽象出来的数学模型。数据的存储结构是逻辑结构用计算机语言的实现。 5.数据类型：一个值的集合及在值上定义的一组操作的总称。分为：原子类型和结构类型。 6.抽象数据类型：抽象数据的组织和与之相关的操作。优点：将数据和操作封装在一起实现了信息隐藏。 7. 抽象数据类型ADT：是在概念层上描述问题；类：是在实现层上描述问题；在应用层上操作对象（类的实例）解决问题。 8.数据的逻辑结构，简称为数据结构，有： （1）线性结构，若结构是非空集则仅有一个开始和终端结点，并且所有结点最多只有一个直接前趋和后继。 （2）非线性结构，一个结点可能有多个直接前趋和后继。 9.数据的存储结构有： 1）顺序存储，把逻辑相邻的结点存储在物理上相邻的存储单元内。 2）链接存储，结点间的逻辑关系由附加指针字段表示。 3）索引存储，存储结点信息的同时，建立附加索引表，有稠密索引和稀疏索引。 4）散列存储，按结点的关键字直接计算出存储地址。 10.评价算法的好坏是：算法是正确的；执行算法所耗的时间；执行算法的存储空间（辅助存储空间）；易于理解、编码、调试。

数据结构1

习题练习第一章绪论 1、void maxtrixmult (int n,int a[][100],int b[][100],intc[][100]) { int j,k,r; int x; for(r=0;r<=n;r++) 1) n+2 { for (j=0;j<=n;j++) 2) (n+1)*(n+2) { x=0; 3) (n+1)2 for(k=1；k<=n;k++) 4) (n+1)3 x+=a[r][k]*[k][j]; 5) n* (n+1)2 c[r][j]=x; 6) (n+1)2 } } } 计算时间每条语句的频度和该算法的时间复杂度 2．一个算法应该是（ B ）。【中山大学 1998 二、1（2分）】 A．程序 B．问题求解步骤的描述 C．要满足五个基本特性 D．A和C. 4．从逻辑上可以把数据结构分为（ C ）两大类。【武汉交通科技大学 1996 一、4（2分）】 A．动态结构、静态结构 B．顺序结构、链式结构 C．线性结构、非线性结构 D．初等结构、构造型结构 5．以下与数据的存储结构无关的术语是（ D ）。【北方交通大学 2000 二、1 （2分）】 A．循环队列 B. 链表 C. 哈希表 D. 栈 6．连续存储设计时，存储单元的地址（ A ）。【中山大学 1999 一、1（1分）】A．一定连续 B．一定不连续 C．不一定连续 D．部分连续，部分不连续 7. 数据元素是数据的最小单位。( F ) 【北京邮电大学 1998 一、1（2分）】【青岛大学 2000 一、1 （1分）】 【上海交通大学 1998 一、1】【山东师范大学 2001 一、1 （2分）】 第二章线性表 1．线性表是具有n个（ C ）的有限序列（n>0）。【清华大学 1998 一、 4（2分）】 A．表元素 B．字符 C．数据元素 D．数据项 E．信 息项

2016最新广工anyview数据结构答案

【题目】若两棵二叉树T1和T2皆为空，或者皆不空且T1的左、右子树和T2的左、右子树分别相似，则称二叉树T1和T2相似。试编写算法，判别给定两棵二叉树是否相似。 二叉链表类型定义： typedef struct BiTNode { TElemType data; struct BiTNode *lchild, *rchild; } BiTNode, *BiTree; **********/ Status Similar(BiTree T1, BiTree T2) /* 判断两棵二叉树是否相似的递归算法*/ { if(!T1&&!T2)//同为空时，两树相似 return TRUE;

else if(T1&&T1){ if(Similar(T1 -> lchild,T2 -> lchild) && Similar(T1 -> rchild,T2 -> rchild)) //两树都不为空时，判断左右子树是否相似 return TRUE; else return FALSE; }else//以上两种情况都不符合，就直接返回FALSE return FALSE; } /********** 【题目】编写递归算法，求对二叉树T先序遍历时 第k个访问的结点的值。 二叉链表类型定义： typedef struct BiTNode {

TElemType data; struct BiTNode *lchild, *rchild; } BiTNode, *BiTree; **********/ TElemType PreOrder(BiTree T, int &k) { TElemType x='#'; if(T==NULL)return '#'; if(k==1)return T->data; if(T->lchild!=NULL) { k--; x=PreOrder(T->lchild,k); } if(T->rchild!=NULL&&x=='#')