2017年大连理工大学电子信息与电气工程学部810数据结构和计算机组成原理之数据结构考研仿真模拟题

目录

2017年大连理工大学电子信息与电气工程学部810数据结构和计算机组成原理之数据结构考研仿真模拟题（一） .................................................................................................................... 2 2017年大连理工大学电子信息与电气工程学部810数据结构和计算机组成原理之数据结构考研仿真模拟题（二） .................................................................................................................. 14 2017年大连理工大学电子信息与电气工程学部810数据结构和计算机组成原理之数据结构考研仿真模拟题（三） .................................................................................................................. 24 2017年大连理工大学电子信息与电气工程学部810数据结构和计算机组成原理之数据结构考研仿真模拟题（四） .................................................................................................................. 35 2017年大连理工大学电子信息与电气工程学部810数据结构和计算机组成原理之数据结构考研仿真模拟题（五） .................................................................................................................. 46

2017年大连理工大学电子信息与电气工程学部810数据结构和计算机组成原理之数

据结构考研仿真模拟题（一）

说明：①本资料为VIP学员内部使用，严格按照2017考研最新题型及历年试题难度出题。

——————————————————————————————————————————

一、选择题

1． 排序过程中，对尚未确定最终位置的所有元素进行一遍处理称为一趟排序。下列排序方法中，每一趟排序结束时都至少能够确定一个元素最终位置的方法是（ ）。

I.简单选择排序II.希尔排序III.快速排序IV.堆排V.二路归并排序 A.仅 I、III、IV B.仅 I、II、III C.仅 II、III、IV D 仅III、IV、V 【答案】A。

【解析】其中简单选择排序、堆排序属于选择类排序，每一趟排序结束时将确定最大（或最小）关键字所在的位置。快速排序每一趟排序结束时将确定基准关键字所在的位置。希尔排序、二路归并排序每一趟排序结束时不一定能确定一个元素的最终位置。

2． 一棵哈夫曼树共有215个结点，对其进行哈夫曼编码，共能得到（ ）个不同的码字。

A.107 B.108 C.214 D.215

【答案】B

【解析】此题可转化为一棵哈夫曼树共有215个结点，共有多少叶子结点。又有以

所

也就是说若对其进行哈夫曼编码，共能得到108个码字。

3． 若用户1与用户2之间发送和接收电子邮件的过程如图所示，则图中①、②、③阶段分别使用的应用层协议可以是（ ）。

图 电子邮件发送接收示意图

A.SMTP、SMTP、SMTP B.POP3、SMTP、POP3 C.POP3、SMTP、SMTP D.SMTP、SMTP、POP3 【答案】D。

【解析】题中电子邮件的工作过程如下：

①用户1调用用户代理来编辑要发送的邮件，用户代理用SMTP将邮件传送给用户1的发送端邮件服务器。

②发送端邮件服务器也就是用户1的邮件服务器将邮件放入邮件缓存队列中，等待发送。 ③运行在发送端邮件服务器的SMTP客户进程，发现在邮件缓存中有待发送的邮件，就向运行在接收端邮件服务器也就是用户2的邮件服务器的SMTP服务器进程发起TCP连接建立。当TCP连接建立后，SMTP客户进程开始向远程的SMTP服务器发送邮件。当所有的待发邮件发完了，SMTP就关闭所建立的TCP连接。

④运行在接收端邮件服务器中的SMTP服务器进程收到邮件后，将邮件放人收信人的用户邮箱中，等待收信人在他方便时进行读取。收信人在打算收信时，调用用户代理，使用POP协议将自己的邮件从接收端邮件服务器的用户邮箱中取回（如果邮箱中有来信的话）。

因此题中1，2, 3阶段分别使用的应用层协议可以是SMTP，SMTP, POP3,因此答案是D。SMTP采用“推”的通信方式，用于用户代理向邮件服务器发送邮件、以及邮件服务器之间发送邮件。POP3采用“拉”的通信方式，用于用户从目的邮件服务器上读取邮件。

4． 下列文件物理结构中，适合随机访问且易于文件扩展的是（ ）。

A.连续结构 B.索引结构

C.链式结构且磁盘块定长 D.链式结构且磁盘块变长 【答案】B

【解析】连续结构的优点是结构简单，缺点是不易于文件扩展，不易随机访问。链式结构的优点是文件易于扩展，缺点是不易随机访问。索引结构的优点是具有链式结构的优点并克服了它的缺点，可随机存取，易于文件扩展。

5． 在一个采用CSMA/CD协议的网络中，传输介质是一根完整的电缆，传输速率为1Gbps,电缆中的信号传播速度是200000km/s。若最小数据帧长度减少800bit，则最远的两个站点之间的距离至少需要（ ）。

A.增加160m B.增加80m C.减少160m D.减少80m 【答案】D

【解析】以太网采用CSMA/CD访问协议，在发送的同时要进行冲突检测，这就要求在能检测出冲突的最大时间内数据包不能够发送完毕，否则冲突检测不能有效地工作。所以，当发送的数据包太短时必须进行填充。最小帧长度=碰撞窗口大小x报文发送速率，本题最小数据帧长度减

少800b，那么碰撞的窗口也要减少，因此距离也要减少，从而（800×2×）/（l×）=160m，

由于时间延时存在两倍的关系，因此减少的距离为80m。

6． 若元素a，b, c, d, e，f依次进栈，允许进栈、退栈操作交替进行，但不允许连续三次进行退栈操作，则不可能得到的出栈序列是（ ）。

A.d，c，e，b，f，a B.c，b，d，a，e，f C.b，c，a，e，f，d D.a，f，e，d，c，b

【答案】D

【解析】4个选项所给序列的进、出栈操作序列分别为：

选项A.Push,Push,Push，Push, Pop, Pop, Push，Pop, Pop,Push,Pop，Pop 选项B.Push,Push,Push,Pop,Pop, Push, Pop, Pop, Push,Pop, Push,Pop 选项C.Push,Push,Pop,Push,Pop, Pop, Push, Push, Pop,Push,Pop,Pop 选项D.Push,Pop, Push,Push,Push, Push, Push, Pop, Pop，Pop,Pop,Pop

按照题目要求，不允许连续三次进行退栈操作，所以选项D所给序列为不可能得到的出栈顺序。

7． 二叉树在线索化后，仍不能有效求解的问题是（ ）。

A.前序线索二叉树中求前序后继 B.中序线索二叉树中求中序后继 C.中序线索二叉树中求中序前驱 D.后序线索二叉树中求后序后继 【答案】D

【解析】后序线索二叉树求后序后继要分3种情况，比较复杂，不是仅仅线索化后就能求解的，算法上还要要分情况讨论。

8． 对于一个线性表既要求能够进行较快速地的插入和删除，又要求存储结构能反映数据之间的逻辑关系，则应该用（ ）。

A.顺序存储方式 B.链式存储方式 C.散列存储方式 D.以上均可以 【答案】B

9． 某计算机存储器按字节编址，采用小端方式存放数据。假定编译器规定int和short型长度分别为32位和16位，并且数据按边界对齐存储。某C语言程序段如下：

若record变量的首地址为A. B. C. D. 【答案】D。

则地址

中内容及record.c的地址分别为（ ）。

【解析】32位整数a需要占4个字节，16位整数c需要占2个字节，而字符数据b占一个字节。a=273,转换成十六进制是111H,采用小端方式存放数据，地址0xC008中的内容为11H。由于数据按边界对齐存储，地址

中存放a,地址

中存放b, 地址

中空闲，

地址中存放c。

10．某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（ ）存储方式最节省运算时间。

A.单链表

B.仅有头指针的单循环链表 C.双链表

D.仅有尾指针的单循环链表 【答案】D

【解析】仅有尾指针的单循环链表，在最后插入元素和删除第一个元素都会用到这个尾指针。

11．一个C语言程序在一台32位机器上运行。程序中定义了3个变量x、Y和z，其中x和z为int型，Y为short型。当x=127，Y=-9时，执行赋值语句z=x+Y后，x、Y和z的值分别是（ ）。

A.x=0000007FH,Y=FFF9H,z=00000076H B.x=0000007FH,Y=FFF9H,z=FFFF0076H C.x=0000007FH,Y=FFF7H,z=FFFF0076H D.x=0000007FH,Y=FFF7H,z=00000076H

【答案】D

【解析】当两个不同长度的数据，要想通过算术运算得到正确的结果，必须将短字长数据转换成长字长数据，这被称为“符号扩展”。例如，x和z为int型，数据长32位，Y为short型，数据长16位，因此首先应将y转换成32位的数据，然后再进行加法运算。运算采用补码的形式，而x的补码是0000007FH,Y的补码是FFFFFFF7H,所以x+Y=00000076H。

12．已知关键字序列5,8,12,19，28，20，15，22是小根堆（最小堆），插入关键字3，调整后的小根堆是（ ）。

A.3,5，12，8,28，20,15，22，19 B.3,5,12,19,20,15,22,8,28

C.3,8,12,5,20,15,22,28,19 D.3,12,5,8,28,20,15,22,19 【答案】A

【解析】在堆中插入或删除一个元素后，将不再满足堆的性质。为了使其成为新堆，在输出堆顶元素后，需要调整剩余元素。具体过程如图（1） （5）所示，（1）为原堆，（2）为插入3后，（3）、（4）为调整过程，（5）为调整后的小根堆。

二、判断题

13．循环队列也存在空间溢出问题。（ ）

【答案】

【解析】循环队列的存储空间也是有限的，因此也存在空间溢出问题。

14．对于有n个结点的二叉树，其高度为（ ）

【答案】×

【解析】例如n结点的单枝树，高度就为n。

15．树中的结点和图中的顶点就是指数据结构中的数据元素。（ ）

【答案】√

【解析】树中的结点和图中的顶点就是指数据结构中的数据元素，而它们的边指的是元素之间的关系。

16．若一个有向图无环，则它一定有唯一的拓扑序列。（ ）

【答案】×

【解析】有向图无环说明它一定有拓扑序列，但这个拓扑序列不唯一。如果在一个线性有序的序列中，每个顶点有唯一的前驱后继关系，在做拓扑排序时，则排序的结果是唯一的，即它有唯一的拓扑序列。

17．KMP算法的特点是在模式匹配时指示主串的指针不会变小。（ ）

【答案】

函数，函

【解析】KMP算法是一种字符串匹配的算法，KMP算法的关键是利用匹配失败后的信息，尽量减少模式串与主串的匹配次数以达到快速匹配的目的。具体实现就是实现一个数本身包含了模式串的局部匹配信息。

18．m阶B树的任何一个结点的左右子树的高度都相等。（ ）

【答案】√

【解析】由B树的性质得知，叶子结点都处于同一层。因此，m阶B树的任何一个结点的左右子树的高度都相等。

19．树形结构中元素之间存在一对多的关系。（ ）

【答案】√

【解析】树形结构是非线性结构，存在一对多的关系。

20．基数分类只适用于以数字为关键字的情况，不适用于以字符串为关键字的情况。（ ）

【答案】×

【解析】如果用字符串为关键字，可以将其中的字符串的每一位用Ascn码进行比较。

21．若一个有向图的邻接矩阵对角线以下元素均为零，则该图的拓扑有序序列必定存在。 （ ）

【答案】√

【解析】因为一个有向图的邻接矩阵对角线以下元素均为零，则该图是一个有向无环图，所以该图的拓扑有序序列必定存在。

22．两个长度不相同的串有可能相等。（ ）

【答案】

【解析】两个字符串相等，只有当两个字符串的长度相等，并且各个对应位置的字符相等才相等。

23．在执行某个排序算法过程中，出现了排序码朝着最终排序序列位置相反方向移动，则该算法是不稳定的。（ ）

【答案】×

【解析】例如起泡排序是稳定排序，将4，3，2，1按起泡排序排成升序序列，第一趟变成3，2，1，4，此时3就朝向最终位置的相反方向移动。

24．线性表采用链表存储时，结点和结点内部的存储空间可以是不连续的。（ ）

【答案】

【解析】对于链式存储，数据元素之间的存储地址不一定是相邻的，即结点的存储空间可以是不连续的。而结点内部的存储空间需要是连续的，因为它是一个完整的数据。

25．通常使用队列来处理函数或过程的调用。（ ）

【答案】

【解析】经常使用栈来处理函数或过程的调用。

26．二叉树中序线索化后，不存在空指针域。（ ）

【答案】×

【解析】非空二叉树中序遍历第一个结点无前驱，最后一个结点无后继，这两个结点的前驱线索和后继线索为空指针。

27．在链队列中，即使不设置尾指针也能进行入队操作。（ ）

【答案】

【解析】因为存在头指针，根据链表的性质，根据头指针可以找到为指针。

三、算法设计题

28．按图的宽度优先搜索法写一算法判别以邻接矩阵存储的有向图中是否存在由顶点的路径

//设有向图有n个顶点

到顶点

【答案】算法如下：

//判断以邻接矩阵方式存储的有向图中是否存在由顶点Vi到顶点Vj的路径

是队列，容量足够大，元素是顶点编

号

）

//Vi人队

到顶点

29．设有一个数组中存放了一个无序的关键序列

【答案】算法如下：

现要求将

放在将元素排序后的

不存在路径

正确位置上，试编写实现该功能的算法，要求比较关键字的次数不超过n（注：用程序实现）。

30．设表达式以字符形式已存入数组E中，

【答案】算法如下：

为表达式的结束符，试写出判断表达式中括号

是否配对的C语言描述算法：EXYX（E）（注：算法中可调用栈操作的基本算法）。

31．请运用快速排序思想，设计递归算法实现求n（n>l）个不同元素集合中的第

【答案】算法如下：

小元素。

32．请用流程图或高级语言表示算法。已知有向图有n个顶点，请写算法，根据用户输入的数对，对于每条这样建立该有向 图的邻接表。即接受用户输入的<vi，yj>（以其中之一为0标志结束）的边，申请一个结点，并插 入到的单链表中，如此反复，直到将图中所有边处理完毕。

提示：先产生邻接表的n个头结点（其结点数值域从1到n）。 【答案】算法如下：

//建立有向图的邻接表存储结构

//输入顶点信息

//题目要求两顶点之一为0表示结束

33．编写算法，将自然数按“蛇形”填矩阵中。例如图所示（用程序实现）。

图

【答案】算法如下：

//

34．设记录

的关键字为

树结点

的败者树，要求除

指向败者记录，

和

为全胜记以外，只用

录下标。写一算法产生对应上述

辅助空间。 【答案】算法如下：

35．设A和B均为下三角矩阵，每一个都有n行n列。因此在下三角区域中各有无素。另设有一个二维数组C，它有n行

个

列。试设计一个方案，将两个矩阵A和B中的下三

和B的矩

角区域元素存放于同一个C中。要求将A的下三角区域中的元素存放于C的下三角区域中，B的下三角区域中的元素转置后存放于C的上三角区域中。并给出计算A的矩阵元素阵元素在C中的存放位置下标的公式。

【答案】算法如下：

36．编写算法打印出由指针Hm指向总表头的以十字链表形式存储的稀疏矩阵中每一行的非零元的个数。注意：行、列及总表头结点的形式为：

它们已用

域链接成循环链表。非零元的结点形式也同上，每一行（列）的非零元由

域把它们链接成循环链表，该行（列）的表头结点即为该行（列）循环链表的表头。

【答案】算法如下：

37．写出一趟快速排序算法。

【答案】算法如下：

2017年大连理工大学电子信息与电气工程学部810数据结构和计算机组成原理之数

据结构考研仿真模拟题（二）

说明：①本资料为VIP学员内部使用，严格按照2017考研最新题型及历年试题难度出题。

——————————————————————————————————————————

一、选择题

1． 循环队列元素数是（ ）。

【答案】A

【解析】对于循环队列，需要深刻理解队头在队尾进行进队操作。

和队尾

的概念，在队头进行出队操作，

如果为负则元

可能为正也可能为负，为正时元素个数=

存放其元素值，用front和rear分别表示队头和队尾，则当前队列中的

素的个数=所以统一的公式就是

2． 和顺序栈相比，链栈有一个比较明显的优势是（ ）。

A.通常不会出现找满的情况 B.通常不会出现栈空的情况 C.插入操作更容易实现 D.删除操作更容易实现 【答案】A

3． 单处理机系统中，可并行的是（ ）。

I.进程与进程 II.处理机与设备 III.处理机与通道 IV.设备与设备 A.I、II和III B.I、II和IV C.I、III和IV D.II、III和IV 【答案】D

【解析】注意区分并发和并行。在单处理机系统中，进程只能并发。微观上同一时刻占用处理机的进程只有一个，因此，进程之间不是并行的。通道是独立于CPU控制的输入/输出的设备，处理机与通道两者是可以并行。显然，设备和设备之间也是可以并行的。

4． 在一棵三元树中度为3的结点数为2个，度为2的结点数为1个，度为1的结点数为2个，则度为0的结点数为（ ）个。

A.4 B.5 C.6 D.7

【答案】C

【解析】设度为0的结点数为x则度为3的树总结点数n=度为0的结点数+度为1的结点数+度为2的结点数+度为3的结点数为3

的树总结点数 5． 广义表

【答案】D

head操作就是得到广义表中第一个的原子。【解析】

操作就是得到除第一个原子外剩下元

素构成的表。也就是toil得到的元素需要在外层再加一个（ ）。

6． 要连通具有n个顶点的有向图，至少需要（ ）条边。

A.n-1 B.n C.n+1 D.2n

【答案】B

【解析】对于有向图来说，两个顶点之间的边是具有方向的。如果是构成连通的无向图，需要n-1条边，而对于有向图来说，只需要再加上第一个顶点和最后一个顶点加上一条边，让其构成环状的图即可，因此最少需要n条边。

7． 一棵3阶B-树中含有2047个关键字，包括叶结点层，该树的最大深度为（ ）。

A.11 B.12 C.13 D.14

【答案】B

8． 有一个的稀疏矩阵，非0元素有10个，设每个整型数占2字节，则用三元组表示该矩阵时，所需的字节数是（ ）。

A.60 B.66 C.18000 D.33

【答案】B

【解析】如果是全部，

则是需要

个字节；但是用三元组表示的话，只需要记录非零

从每个结点所指向的结点数的和的角度来计算度两种方法所计算出来的n相等，所以则式子

的值为（ ）。

数据的X坐标，Y坐标，数值即可，就是每个非零数字需要占用三个整数的空间，即10个非零整数则是

字节，

字节；如果问有效元素占的空间大小，则选A项，但是如果从整体

来看，应该多一个用来记录矩阵宽（100）、高（90）、默认值（0）的元素，所以还应该多算6个字节。所以全部为66字节，选B项。

9． 假定一台计算机的显示存储器用DRAM芯片实现，若要求显示分辨率为1600x1200,颜色深度为24位，帧频为85Hz,显存总带宽的50%用来刷新屏幕，则需要的显存总带宽至少约为（ ）。

A.245Mbps B.979Mbps C. D. 【答案】D

【解析】显存的容量=分辨率×色深，带宽=分辨率×色深×帧频，考虑到

的时间用来刷新

1600×1200×24×85×2＝7834Mbps 屏幕，故显存总带宽应加倍。所以需要的显存总带宽至少约为：

10．假定用若干个2Kx4位的芯片组成一个8Kx8位的存储器，则地址0B1FH所在芯片的最小地址是（ ）。

A.0000H B.0600H C.0700H D.0800H 【答案】D

【解析】由若干芯片构成存储器，采用字和位同时扩展方法。8片2Kx4位的芯片分成4组，每组2个芯片，各组芯片的地址分配分别为：第1组，0000H 07FFH;第2组，0800H 0FFFH;第3组，1000H 17FFH;第4组，1800H 1FFFH。地址0BIFH处于第2组内，其芯片的最小地址为0800H。

11．使用浏览器访问某大学Web网站主页时，不可能使用的协议是（ ）

A.PPP B.ARP C.UDP D.SMTP 【答案】D

【解析】SMTP是简单邮件传输协议，访问主页时并不涉及邮件相关协议。

12．最大容量为n的循环队列，队尾指针是rear，队头：front,则队空的条件是（ ）。

A. B. C. D. 【答案】B

【解析】循环队列队空的条件是：rear=front。循环队列队满的条件，通常采

用

来判定队满，其中

表示队列的长度。

二、判断题

13．无环有向图才能进行拓扑排序。（ ）

【答案】√

【解析】在图论中，由一个有向无环图的顶点组成的序列，才能进行拓扑排序。

14．倒排文件的目的是为了多关键字查找。（ ）

【答案】√

【解析】多关键字文件的特点是，在对文件进行检索操作时，不仅对主关键字进行简单询问，还经常需要对次关键字进行其它类型的询问检索。常见的多关键字文件为：多重表文件和倒排文件。

15．队列是一种插入与删除操作分别在表的两端进行的线性表，是一种先进后出型结构。 （ ）

【答案】

【解析】队列是一种先入先出型结构，而栈才是先进后出的线性结构。

16．静态链表就是一直不发生变化的链表。（ ）

【答案】

【解析】用数组描述的链表，即称为静态链表。仍具有链式存储结构的主要优点。不是指不发生变化的的链表。

17．如果数据元素保持有序，则查找时就可以采用折半查找方法。（ ）

【答案】×

【解析】采用折半查找的条件是数据元素有序且存储方式为顺序存储，对于常见的链式存储，在进行查找时主要依靠指针来操作。

18．用一维数组存储二叉树时，总是以前序遍历顺序存储结点。（ ）

【答案】×

【解析】后序遍历、中序遍历也可以遍历一维数组存储的二叉树。

19．内排序要求数据一定要以顺序方式存储。（ ）

【答案】×

【解析】由于待排序的记录数量不同，使得排序过程中涉及的存储器不同，可将排序方法分为两大类：一类是内部排序；另一类是外部排序。因此，内部排序没有要求数据一定是以顺序方式存储。

20．程序一定是算法。（ ）

【答案】

【解析】一个程序不一定满足有穷性。而算法是对问题的解，用程序设计语言来实现来描述，这时算法就是一个程序。

21．为了很方便的插入和删除数据，可以使用双向链表存放数据。（ ）

【答案】

【解析】链式存储结构便于数据的插入和删除，但只能顺序访问表中的元素。

22．—个排序算法是否稳定，是指该算法在各种情况下的时间效率是否相差不大。（ ）

【答案】×

【解析】排序的稳定性指：假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，

且ri在rj之前，而在排序后的

序列中，ri仍在rj之前，则称这种排序算法是稳定的；否则称为不稳定的。

23．就平均查找长度而言，分块查找最小，折半查找次之，顺序查找最大。（ ）

【答案】×

【解析】折半查找最小，分块查找次之，顺序查找最大。分块查找的速度虽然不如折半查找算法，但比顺序查找算法快得多，同时又不需要对全部节点进行排序。当结点很多且块数很大时，对索引表可以采用折半查找，这样能够进一步提高查找的速度。

24．3阶的B-树是平衡的3路搜索树。反之，一棵平衡的3路搜索树是3阶B-树。（ ）

【答案】×

【解析】3路搜索树并不具有3阶B-树的性质。因此一棵平衡的3路搜索树不一定是3阶B-树。

25．在用堆排序算法排序时，如果要进行增序排序，则需要采用“大根堆”。（ ）

【答案】√

，使其n个元素的最大（小）【解析】堆排序：基本思想先将原始序列构造成一个堆（初始堆）

值处于序列的第一个位置；然后交换序列第一个元素与最后一个元素的位置。

26．对处理大量数据的外存介质而言，索引顺序存取方法是一种方便的文件组织方法。（ ）

【答案】×

【解析】索引顺序存取方法插入操作比较麻烦，对于处理大量数据，会有大量的记录进入溢出区，而基本区中又浪费很多空间。

27．在初始数据表已经有序时，快速排序算法的时间复杂度为

【答案】×

（ ）

【解析】当初始数据表有序，此时快速排序所需要比较的次数最多，快速排序算法的时间复杂度为〇（n2）。

三、算法设计题

28．已知顺序表中有m个记录，表中记录不依关键字有序排列，编写算法为该顺序表建立一个有序的索引表，索引表中的每一项含记录的关键字和该记录在顺序表中的序号，要求算法的时间复

杂度在最好的情况下能达到

【答案】算法如下：

29．设T是一棵满二叉树，写一个把T的后序遍历序列转换为前序遍历序列的递归算法。

【答案】算法如下：

//将满二叉树的后序序列转为前序序列，11、hl、12、h2是序列初始和最后结点的下标。

//根结点

//左子树或右子树的结点数

//将左子树前序序列转为

后序序列

后序序列

30．设二叉树用二指针结构存储（可以是动态存储结构），元素值为整数，且元素值无重复，请编写子程序，求出以元素值等于某个给定的整数的结点为根的子树中的各个叶结点。

【答案】算法如下：

//将右子树前序序列转为

//在二叉树t中査找结点值等于x的结点

//结束

//统计以t为根结点的子树的叶结点数

nO

//叶结点

}//结束 Count

31．已知P是指向单向循环链表最后一个结点的指针，试编写只包含一个循环的算法，

将线性表

改造为

【答案】算法如下：

32．若x和y是两个采用顺序结构存储的串，编写一个比较两个串是否相等的函数。

【答案】算法如下：

//输出并计数

33．写出按后序序列遍历中序线索树的算法。

【答案】算法如下：

//求结点

//求结点

//若t是father的右孩子，返回1,否则返回0

//后序遍历中序线索二叉树bt

//沿左分支向下

//左孩子为线索，右孩子为链，相当从左返回

//P为叶子，相当从右返回

//访问结点

//修改P指向双亲

//P是左子女，用最右子孙的右线索找双亲

//转向当前结点右分支

} }//结束PostOrderInThr

34．假设串的存储结构如下所示，编写算法实现串的置换操作。

【答案】算法如下：

和t是用一维数组存储的串，本算法将s串第i个字符开始连续j个字符用t串置换，操作

成功返回1,否则返回0表示失败

t最左子孙的左线索

//沿左分支向下

t最右子孙的右线索

//沿右分支向下

本文来源：https://www.bwwdw.com/article/zcpj.html