2022年数据结构考试复习题教案资料.pdf

《2022年数据结构考试复习题教案资料.pdf》由会员分享，可在线阅读，更多相关《2022年数据结构考试复习题教案资料.pdf（22页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数 据 结 构 考 试 复 习 题精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 1 页，共 22 页 - - - - - - - - - - 学习 好资料精品资料复习题集一判断题（） 1. 在决定选取何种存储结构时，一般不考虑各结点的值如何。（） 2. 抽象数据类型与计算机内部表示和实现无关。（）3. 线性表采用链式存储结构时，结点和结点内部的存储空间可以是不连续的。（）4. 链表的每个结点中都恰好包含一个指针。（）5.链表的删除算法很简单，因为当删除链中某个结点后，计算机会自动地将后续的各个单元向前移

2、动。（）6. 线性表的每个结点只能是一个简单类型，而链表的每个结点可以是一个复杂类型。（）7. 顺序表结构适宜于进行顺序存取，而链表适宜于进行随机存取。（）8. 线性表在物理存储空间中也一定是连续的。（）9. 顺序存储方式只能用于存储线性结构。（） 10.栈是一种对所有插入、删除操作限于在表的一端进行的线性表，是一种后进先出型结构。（） 11.对于不同的使用者，一个表结构既可以是栈，也可以是队列，也可以是线性表。（） 12.栈是一种对所有插入、删除操作限于在表的一端进行的线性表，是一种后进先出型结构。（） 13.两个栈共享一片连续内存空间时，为提高内存利用率，减少溢出机会，应把两个栈的栈底分别

3、设在这片内存空间的两端。（）14.二叉树的度为 2。（） 15.若二叉树用二叉链表作存贮结构，则在n个结点的二叉树链表中只有n1个非空指针域。（）16.二叉树中每个结点的两棵子树的高度差等于1。精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 2 页，共 22 页 - - - - - - - - - - 学习 好资料精品资料（） 17.用二叉链表法存储包含n个结点的二叉树，结点的2n个指针区域中有 n+1个为空指针。（） 18.具有 12 个结点的完全二叉树有5个度为 2的结点。（） 19.二叉树的前序遍历

4、序列中，任意一个结点均处在其孩子结点的前面。（）20.在冒泡法排序中，关键值较小的元素总是向前移动，关键值较大的元素总是向后移动。（）21.计算机处理的对象可以分为数据和非数据两大类。计算机处理的对象都是数据 （）22.数据的逻辑结构与各数据元素在计算机中如何存储有关。（）23.算法必须用程序语言来书写。（）24.判断某个算法是否容易阅读是算法分析的任务之一。（）25.顺序表是一种有序的线性表。任何数据结构才用顺序存储都叫顺序表 （） 26.分配给顺序表的内存单元地址必须是连续的。（） 27.栈和队列具有相同的逻辑特性。它们的逻辑结构都是线性表 （） 28.树形结构中每个结点至多有一个前驱。（

5、）29.在树形结构中，处于同一层上的各结点之间都存在兄弟关系。（）30.如果表示图的邻接矩阵是对称矩阵，则该图一定是无向图。（）31.如果表示图的邻接矩阵是对称矩阵，则该图一定是有向图。（）32.顺序查找方法只能在顺序存储结构上进行。（）33.折半查找可以在有序的双向链表上进行。（） 34.满二叉树中不存在度为1的结点。（）35.完全二叉树中的每个结点或者没有孩子或者有两个孩子。（） 36.对 n 个元素执行快速排序，在进行第一次分组时，排序码的比较次数总是n-1次。（） 37.在有向图中，各顶点的入度之和等于各顶点的出度之和。精品资料 - - - 欢迎下载 - - - - - - - - -

6、 - - 欢迎下载 名师归纳 - - - - - - - - - -第 3 页，共 22 页 - - - - - - - - - - 学习 好资料精品资料一、选择题（A）1. 在 n 个结点的顺序表中，算法的时间复杂度是O(1)的操作是：A) 访问第 i 个结点（ 1in）和求第 i 个结点的直接前驱（ 2in） C) 删除第 i 个结点（1in）B) 在第 i 个结点后插入一个新结点（1in） D) 将 n 个结点从小到大排序（C）2. 算法分析的目的是：A) 找出数据结构的合理性 B) 研究算法中的输入和输出的关系C) 分析算法的效率以求改进 D) 分析算法的易懂性和文档性（A）3. 算法

7、分析的两个主要方面是：A) 空间复杂性和时间复杂性 B) 正确性和简明性C) 可读性和文档性 D) 数据复杂性和程序复杂性（C）4. 计算机算法指的是：A) 计算方法 B) 排序方法 C) 解决问题的有限运算序列 D) 调度方法（B）5. 计算机算法必须具备输入、输出和等 5个特性。A) 可行性、可移植性和可扩充性 B) 可行性、确定性和有穷性C) 确定性、有穷性和稳定性 D) 易读性、稳定性和安全性（B）6. 一个向量第一个元素的存储地址是100，每个元素的长度为2，则第 5 个元素的地址是: （A）110 （B）108 （C）100 （D）120 （D）下列选项中与数据存储结构无关的术语是

8、：A.顺序表 B.链表 C.链队列 D.栈（A）7. 链接存储的存储结构所占存储空间：（A）分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 4 页，共 22 页 - - - - - - - - - - 学习 好资料精品资料（B）只有一部分，存放结点值（C） 只有一部分，存储表示结点间关系的指针（D） 分两部分，一部分存放结点值，另一部分存放结点所占单元数（B）8. 带头结点的单链表head，链表为空的判定条件是(A)head = NULL (B)

9、 head-next =NULL ( C) head-next =head (D) head!=NULL （B）9. 一个栈的输入序列为1，2，3，n，若输出序列的第一个元素是n，输出第 i（1 i n）个元素是。A) 不确定 B) ni1 C) i D) ni（B）10. 最大容量为 n 的循环队列，队尾指针是rear，队头是 front ，则队空的条件是（）。 A) (rear1)% n=front B) rear=front C) rear1=front D) (rearl) % n=front （A）11. 循环队列 A0.m 1存放其元素值，用front 和 rear 分别表示队头和

10、队尾，则当前队列中的元素数是 : (A) (rearfrontm)%m (B) rearfront1 (C) rearfront1 (D) rearfront （B）12. 若用一个大小为 6 的数值来实现循环队列，且当前rear 和 front 的值分别为 0和 3，当从队列中删除一个元素，再加入两个元素后，rear 和 front 的值分别为 : (A) 1 和 5 (B) 2和 4 (C) 4和 2 ( D) 5和 1 （C）13. 按照二叉树的定义，具有3 个结点的二叉树有（）种。A) 3 B) 4 C) 5 D) 6 利用排列组合知识来做 （B）14. 若一棵二叉树中度为l 的结点个

11、数是 3，度为 2 的结点个数是 4，则该二叉树叶子结点的个数是 : (A) 4 (B) 5 (C) 7 (D) 8 （B）15. 具有 n(n0)个结点的完全二叉树的深度为: () log2(n) () log2(n) () log2(n) +1 () log2(n)+1精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 5 页，共 22 页 - - - - - - - - - - 学习 好资料精品资料（D）16. 对一个满二叉树， m 个叶子， n 个结点，深度为h，则: (A) n = h+m (B)

12、h+m = 2n (C) m = h-1 (D) n = 2h-1 （C）17在高度为 h 的完全二叉树中，表述正确的是（）A.度为 0 的结点都在第 h层上 B.第 i(1 ih)层上的结点都是度为2的结点C.第 i(1 ih)层上有 2i-1个结点 D.不存在度为 1的结点（B）18. 深度为 5 的二叉树至多有（）个结点。A) 32 B) 31 C) 16 D) 10 （A）19. 用邻接表表示图进行深度优先遍历时，通常采用( )结构来时实现算法。A) 栈 B) 队列 C) 树 D) 图（D）20. 对 N 个记录作顺序查找时，当查找成功时，平均查找长度是（）。A) N2 B) N2/2

13、 C) N D)（N1)/2 （B）21. 当一个有 n 个顶点的图用邻接矩阵A 表示时，顶点 Vi的度是（）。(A)nijiA1, B) njjiA1, C)niijA1, D)nijiA1,+njijA1,（C）22某算法的时间复杂度为O(2n)，表明该算法的（）A.问题规模是 2n B.执行时间等于 2nC.执行时间近似与2n成正比 D.问题的规模近似与2n成正比（D）23“二叉树为空”意味着二叉树（ ）A.由一些没有赋值的空结点构成 B.根结点没有子树 C.不存在 D.没有结点（D）24数据结构的研究内容不涉及（）A.数据如何组织 B.数据如何存储 C.数据的运算如何实现 D.算法用什

14、么语言描述（C）25在存储数据时，通常不仅要存储各数据元素的值，而且还要存储A.数据的处理方法 B.数据元素的类型 C.数据元素之间的关系 D.数据的存储方法精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 6 页，共 22 页 - - - - - - - - - - 学习 好资料精品资料（D）26数据采用顺序存储，要求（）A.存储的是属于线性结构的数据 B.根据结点值的大小，有序存放各结点C.按存储单元地址由低到高的顺序存放各结点 D.各结点存放方法有规律，能隐含表示结点间的逻辑关系（D）27一个顺序表所

15、占存储空间大的大小与（）无关A.顺序表长度 B.结点类型 C.结点中各字段的类型 D.结点存放顺序（A）28数据采用链接存储，要求（）A.每个结点占用一片连续的存储区域 B.所有结点占用一片连续的存储区域C.结点的最后一个字段是指针型的字段 C.每个结点有多少个后继，就设多少个指针字段（A）29算法的时间复杂度与（）有关A.问题规模 B.计算机硬件性能 C.编译程序质量 D.程序设计语言（C）30在程序中，为了设置一个空的顺序表，必须（）A.给各数组元素赋空值 B.给各顺序表元素赋空值C.给表示顺序表长度的变量赋初始值 D.给数组变量名赋初始值（D）31若变量 H 是某个带表头结点循环单向链表

16、的表头指针，则在该链表最后的一个结点的后继指针域中存放的是（）A.H 的地址 B.H 的值 C.表头结点的值 D.首元结点的地址（A）32栈和队列的共同点在于（）A.逻辑特性 B.存储结构 C.运算方法 D.元素类型（C）33栈和队列的共同点在于（）A.都对存储方法作了限制 B.都是只能进行插入、删除运算C.都对插入、删除的位置作了限制 D.都对插入、删除两中操作的先后顺序作了限制（C）34若 5 个元素的进栈序列是1,2,3,4,5，则不可能得到出栈序列（）精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第

17、 7 页，共 22 页 - - - - - - - - - - 学习 好资料精品资料A.1，2，3，4，5 B.3，4，2，5，1 C.4，2，1，3，5 D.5，4，3，2，1 （A）35顺序循环队列中是否可以插入下一个元素，（）A.与队首指针和队尾指针的值有关 B.只与队尾指针的值有关，与队首指针的值无关C.只与数组大小有关，与队首指针和队尾指针的值无关 D.与曾经进行过多少次插入操作有关（A）36在顺序队列中，元素的排列顺序（）A.由元素插入队列的先后顺序决定 B.与元素值的大小有关C.与队首指针和队尾指针的取值有关 D.与数组大小有关（C）37在高度为 h 的完全二叉树中，（）A.度为

18、 0 的结点都在第 h层上 B.第 i(1 ih)层上的结点都是度为2的结点C.第 i(1ih) 层上有 2i-1个结点 D.不存在度为 1的结点（B）38一颗二叉树如图所示，其中序遍历的序列为：A. ABDGCEFH B. DGBAECHF C. GDBEHFCA D. ABCDEFGH （A）39采用邻接表存储的图的深度优先遍历算法类似于二叉树的A先序遍历 B中序遍历 C后序遍历 D按层遍历（D）40采用邻接表存储的图的广度优先遍历算法类似于二叉树的A先序遍历 B中序遍历 C后序遍历 D按层遍历（D）41.已知关键字序列为 (51，22，83，46，75，18，68，30)，对其进行快速排

19、序，第一趟划分完成后的关键字序列是A.(18,22,30,46,51,68,75,83) B.(30,18,22,46,51,75,83,68) C.(46,30,22,18,51,75,68,83) D.(30,22,18,46,51,75,68,83) A C E B F G D H 精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 8 页，共 22 页 - - - - - - - - - - 学习 好资料精品资料二、填空题1数据结构包括数据的逻辑结构、数据的 存储结构和数据的运算 这三个方面的内容。2

20、下面程序段的时间复杂度是 O(log3n) 。i 0；while（inext ; (2) P-next = P; (3) P-next = P-next-next (4) P-next = P-next-next; (5) while(P!=NULL) P = P-next ; (6) while(Q-next != NULL) P = Q; Q=Q-next; (7) while(P-next != Q) P = P-next; (8) while(P-next-next != Q) P = P-next; (9) while(P-next-next != NULL) P = P-next;

21、 (10) Q = P; (11) Q = P-next; (12) P = L ; (13) L = L-next; (14) free(Q); 7栈是一种特殊的线性表，允许插入和删除运算的一端称为栈顶。不允许插入和删除运算的一端称为栈底。精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 9 页，共 22 页 - - - - - - - - - - 学习 好资料精品资料8设栈 S的初始状态为空，若元素a、b、c、d、e、f 依次进栈，得到的出栈序列是b、d、c、f、e、a，则栈 S的容量至少是 3 。9用

22、 S表示入栈操作， X表示出栈操作，若元素入栈的顺序为1234，为了得到 1342 出栈顺序，相应的 S和 X的操作串为 SXSSXSXX 。10数据的逻辑结构可以分为线性 和 非线性 两大类。11数据的运算用算法 表示。12逻辑上相邻的结点在存储器中也相邻，这是顺序存储结构的特点。13在长度为 n 的顺序表上实现定位操作，其算法的时间复杂度为 O(n) 。14为了实现随机访问，线性结构应该采用顺序存储。15在长度为 n 的顺序表中插入一个元素，最多要移动 n 个元素。16栈的存储结构主要有顺序和 链式 两种。17在编写程序的时候，如果栈的最大长度难以预先估计，则最好使用链式栈。18在树形结构

23、中，如果某结点没有前驱（双亲），则称该结点为根结点；如果某结点没有后继（孩子），则称该结点为叶子。19在树形结构中，每个结点最多只有一个前驱（双亲）。20 由 3 个结点所构成的二叉树有 5 种形态。21二叉树的前序遍历按如下三个步骤进行：访问根结点； 前序遍历左子树； 前序遍历右子树。【注意：中一定要加“前序”两字！】22二叉树的中序遍历按如下三个步骤进行：中序遍历左子树； 访问根结点；中序遍历左子树。【注意：中一定要加“中序”两字！】23在 n 个顶点的无向图中，至少有 0 条边，至多有 n(n-1)/2 条边。24在 n 个顶点的有向图中，至少有 0 条边，至多有 n(n-1) 条边。2

24、5如果排序不改变关键字相同的记录之间的相对次序，则称该排序方法是稳定的。精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 10 页，共 22 页 - - - - - - - - - - 学习 好资料精品资料26如果排序改变了关键字相同的记录之间的相对次序，则称该排序方法是不稳定的。27当待排关键字序列基本有序时，快速排序、简单选择排序和直接插入排序三种排序方法中，运行效率最高的是直接插入排序 。28在一个图中，所有顶点的度数之和是所有边数的 2 倍。29无向图中边的数目等于邻接矩阵中非零元素个数的 0.5

25、倍。30折半查找有序表（ 4，6，12，20，28，38，50，70，88，100），若查找表中元素20，它将依次与表中元素 28，6，12，20 比较大小。31在有序表（ 2，4，6，8，10，12，14，16，18）上用折半查找法查找元素9，其中第二次被比较的元素是 4 。32在有序表（ 2，4，6，8，10，12，14，16，18）上用折半查找法查找元素9，其中第三次被比较的元素是 6 。三、简答题1对链表设置头结点的作用是什么？（至少说出两条好处）答：其好处有：（ 1）对带头结点的链表，在表的任何结点之前插入结点或删除表中任何结点，所要做的都是修改前一个结点的指针域，因为任何元素结点都

26、有前驱结点（若链表没有头结点，则首元素结点没有前驱结点，在其前插入结点和删除该结点时操作复杂些）。（2）对带头结点的链表，表头指针是指向头结点的非空指针，因此空表与非空表的处理是一样的。2. 写出下列程序段的输出结果（队列中的元素类型QElem Type为 char）。void main( ) Queue Q; Init Queue (Q); Char x= e; y= c;EnQueue (Q, h); EnQueue (Q, r ); EnQueue (Q, y); DeQueue (Q,x); EnQueue (Q,x); DeQueue (Q,x); EnQ ueue (Q, a);

27、while(!QueueEmpty(Q) DeQueue (Q,y); printf(y); ; 精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 11 页，共 22 页 - - - - - - - - - - 学习 好资料精品资料Printf(x); 解：char 3. 简述以下算法的功能（栈和队列的元素类型均为int）。void algo3(Queue &Q) Stack S; int d; InitStack(S); while(!QueueEmpty(Q) DeQueue (Q,d); Push(S

28、,d); ; while(!StackEmpty(S) Pop(S,d); EnQueue (Q,d); 解：利用栈 S作为缓存空间，将队列Q 中的元素进行逆置（即相对于原顺序进行倒排）。4. 描述以下三个概念的区别：头指针、头结点、首元结点（第一个元素结点）。在单链表中设置头结点的作用是什么？答：首元结点是指链表中存储线性表中第一个数据元素a1的结点。为了操作方便，通常在链表的首元结点之前附设一个结点，称为头结点，该结点的数据域中不存储线性表的数据元素，其作用是为了对链表进行操作时，可以对空表、非空表的情况以及对首元结点进行统一处理。头指针是指向链表中第一个结点（或为头结点或为首元结点）的指

29、针。若链表中附设头结点，则不管线性表是否为空表，头指针均不为空。否则表示空表的链表的头指针为空。这三个概念对单链表、双向链表和循环链表均适用。是否设置头结点，是不同的存储结构表示同一逻辑结构的问题。头结点head data link 头指针首元结点简而言之，精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 12 页，共 22 页 - - - - - - - - - - 学习 好资料精品资料头指针是指向链表中第一个结点（或为头结点或为首元结点）的指针；头结点是在链表的首元结点之前附设的一个结点；数据域内只放空

30、表标志和表长等信息（内放头指针？那还得另配一个头指针！）首元素结点是指链表中存储线性表中第一个数据元素a1的结点。5. 对以下单链表执行下列语句，简述代码的功能，并画出单链表结果示意图。T = L; while(T-next != NULL) T-data = 2 * T-data; T = T-next; 解：代码功能：除最后一个结点之外，每个结点的数值部分改变为原值的2 倍。单链表结果示意图如下：6. 请画出下图的邻接矩阵和邻接表【本题较简单，不提供答案】7假设二叉树采用顺序存储结构，如图所示。（1） 画出二叉树表示；（2） 写出先序遍历、中序遍历和后序遍历的结果；（3） 写出结点值 c

31、的双亲结点，其左、右孩子；1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 e a f d g c j h i b 8. 树和二叉树之间有什么样的区别与联系？2 5 7 3 8 L 4 10 14 6 8 L 精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 13 页，共 22 页 - - - - - - - - - - 学习 好资料精品资料解：联系：（ 1）二叉树是树的一种，是一种特殊的树；（2）对树适用的操作或规律都可应用到二叉树上。区别：（ 1）二叉

32、树是一种特殊的树，特殊在，第一是有序树，第二结点的度数不超过2；（2）普通二叉树有 3 个性质，完全二叉树有5 个性质，普通树是没有这些性质的。9. 一棵二叉树中的结点的度或为0 或为 2，则二叉树的枝数为2(n0-1) ，其中 n0是度为 0 的结点的个数。证明：设总结点数为 n，度数为 2 的结点数为 n2，依题意，该二叉树没有度数为1 的结点。那么 n= n0+ n2假定分枝数为 B，每个结点通过一个分枝跟其双亲相连，除根结点外；这意味着除根结点外，每个结点对应一个分枝，即B=n-1 , 根据二叉树的性质3，n2=n0+1 , 于是 B=n-1= n0+ n2-1= n0+ n0-1-1

33、=2(n0-1) 10. 一个深度为L 的满 K 叉树有以下性质：第L 层上的结点都是叶子结点，其余各层上每个结点都有K 棵非空子树，如果按层次顺序从1 开始对全部结点进行编号，求：（1）各层的结点的数目是多少？（2）编号为 n 的结点的双亲结点（若存在）的编号是多少？（3）编号为 n 的结点的第i 个孩子结点（若存在）的编号是多少？（4）编号为 n 的结点有右兄弟的条件是什么？如果有，其右兄弟的编号是多少？请给出计算和推导过程。11. 如果用一个循环数组q0.m-1表示队列时，该队列只有一个队列头指针front ，不设队列尾指针 rear ，而改置计数器 count 用以记录队列中结点的个数

34、。（1）编写实现队列的三个基本运算：判空、入队、出队（2）队列中能容纳元素的最多个数是多少？【此题超出教学范围，不作解答。】精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 14 页，共 22 页 - - - - - - - - - - 学习 好资料精品资料12. 已知一棵二叉树的前序遍历结果为ABCDEF，中序遍历结果为CBAEDF，画出此二叉树。并给出其后序遍历的结果。解：根据已知的前序和中序遍历结果，建立二叉树如图所示。此二叉树的后序遍历结果为：CBEFDA 13假设以二叉链表表示二叉树，其类型定义如

35、下：typedef struct node char data; struct node*lchild, *rchild; 左右孩子指针 *BinTree ；阅读下列程序。void f13(BinTree T) InitStack(S); 初始化一个堆栈 S while(T | !StackEmpty(S) while(T) Push(S,T); T=T-lchild; if(!StackEmpty(S) T=Pop(S); printf(“ %c” ,T-data); T=T-rchild; 回答下列问题：(1)已知以 T 为根指针的二叉树如图所示，请写出执行 f13(T)的输出结果：A B

36、 C D E F 精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 15 页，共 22 页 - - - - - - - - - - 学习 好资料精品资料(2)简述算法 f13 的功能。14设如下图所示的二叉树B 的存储结构为二叉链表， root 为根指针，结点结构为：（lchild,data,rchild）。其中 lchild，rchild 分别为指向左右孩子的指针，data为字符型， root 为根指针，试回答下列问题：（1）对下列二叉树 B，执行下列算法traversal(root)，试指出其输出结果；

37、（2）假定二叉树 B 共有 n 个结点，试分析算法traversal(root)的时间复杂度。二叉树 B 解：（1）输出结果：ABCCEEBDFFGG （2）时间复杂度：15.已知有向图的邻接表如图所示，请回答下面问题：(1)给出该图的邻接矩阵；(2)从结点 A 出发，写出该图的深度优先遍历序列。16. 设要将序列 Q, H, C, Y, P, A, M, S, R, D, F, X 中的关键码按字母序的升序重新排列。简述快速排序的思路，并以第一个元素为轴中心，给出用快速排序对序列一趟扫描的结果。A B D C F G E C的结点类型定义如下：struct node char data; s

38、truct node *lchild, rchild; ; C算法如下：void traversal(struct node *root) if (root) printf(“%c ”, root-data); traversal(root-lchild); printf(“%c ”, root-data); traversal(root-rchild); 精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 16 页，共 22 页 - - - - - - - - - - 学习 好资料精品资料解：快速排序的思路

39、：（ 1）从序列中任意选取一个元素作为枢轴，以枢轴为标准将序列划分成三部分。第一部分的所有元素比枢轴小，第二部分是枢轴自己，第三部分的所有元素比枢轴大。这样处理以后，枢轴的位置已经排好。（2）对上述划分的第一部分序列和第三部分序列循环执行第（1）步的操作，直到划分的序列中只有一个元素为止。针对题目给定的序列，快速排序一趟扫描的结果是：F, H, C, D, P, A, M, Q, R, S, Y, X. 四、算法填空1假设线性表用不带头结点的单向链表表示，结点数据类型如下：struct node int s; node * next; 下面的算法用于求线性表的长度。请在方框中填入适当的内容，将

40、算法补充完整。int GetLinkLen(node *h) int s; s=0; while(h) s=s+1; h=h-next ; return(s); 2设有 n 个顺序表元素存放在数组v1vn 中，数组 v 的最大下标为 n0，元素类型为 TElem. 下面的算法用于删除顺序表中第一个值为x 的元素。请在方框中填入适当内容，将算法补充完整。void DeleValue (TElem x) int i, j; i=1; 精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 17 页，共 22 页 -

41、- - - - - - - - - 学习 好资料精品资料 While( vi!=x & i=n ) i=i+1; if(ii;j-) vj-1=vj; n- ; 五、算法设计题1.从顺序表中删除值为x 的元素。答：假定顺序表为a，有效元素个数为n，下标从 0 开始。int DeleteReapeatValue(datatype * a, int * pNum, datatype x) int i, k, n; n=*pNum; k=0; for(i=0;in;i+) If(ai=x) k+; Else ai-k=ai; *pNum=n-1; return k; 2.将顺序存储结构线性表（ v1

42、, v2, , vn）改变成（ vk+1,vk+2, , vn,v1,v2, vk）。答：void ChangeSequence(datatype * v) datatype aSIZE; for(int i=1;in;i+) ai=vi; for(i=1;i=n;i+) v(k+i)%n=ai; 3.将顺序存储的线性表（ v1, v2, , vn）改变成（ v1, v3, v5,）。答：void ChangeSequence(datatype * v) for(int i=3;i=n;i+=2) vi-i/2=vi 4.从顺序表中删除重复的元素，并使剩余元素间的相对次序保持不变。精品资料 -

43、 - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 18 页，共 22 页 - - - - - - - - - - 学习 好资料精品资料答：int DeleteAllReapeatValue(datatype * a, int * pNum) int n=*pNum; int i , j ; for(i=0;in;i+) for(j=i+1; jn;j+) if(ai!= INFINITY & ai=aj) aj= INFINITY; return DeleteReapeatValue(a,pNum, INFINITY)

44、; 5.从键盘输入一系列整数，建立一个长度为n 的、不含重复元素的顺序表。答：int CreateSequence() int aSIZE; int i=0, j, k; while(in) scanf( “%d ”, &k); for(j=0; ji) a+i=k; 6.从键盘输入 n 个整数，建立带表头结点的单向链表。答：LinkList CreateList() int i=0 , j , k; LinkList head=(Node*)malloc(sizeof(Node); Node* r=head,*p=NULL; While(inext; while(p) if(p-data=k

45、) break; p=p-next; if(p=NULL) s=(Node*)malloc(sizeof(Node); s-data=k; r-next=s; r=s i+; 精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 19 页，共 22 页 - - - - - - - - - - 学习 好资料精品资料 return head; 7.设 H 是带表头结点的单向链表的表头指针，将链表中数值重复的结点删除。答：LinkList DleReapeatValue(LinkList H) Node *p=H-n

46、ext,*q,*s; While(p) s= p; q=s-next; while(q) if(p-data=q-data) s-next=q-next; free(q); q=s-next; s=s-next; q=q-next; p=p-next; 8. 设有一带头结点的单链表，编程将链表颠倒过来。要求不用另外的数组或结点完成。解：设链表结点的数据类型为：typedef struct Node ElemType data; / 自定义类型 struct Node *next; Node; 假定链表的头指针为H，如下的函数实现链表的倒置：void RevLinkList(Node* H) N

47、ode *p=H-next; Node * q=NULL; H-next=NULL; while(p) q=p-next; /保存下一个节点的指针精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 20 页，共 22 页 - - - - - - - - - - 学习 好资料精品资料 p-next=H-next; H-next=p; /把取出的节点插入到头节点的后面 p=q; 9. 统计出单链表 HL 中结点的值等于给定值X 的结点数。解：设链表结点的数据类型为：typedef struct Node Elem

48、Type data; / 自定义类型 struct Node *next; Node; 假定链表的头指针为HL，如下的函数统计链表中接点值为X的结点数目：Int CountNodeX(Node * HL, ElemType x ) Int n; Node* p=HL-next; While(p) If(p-data=x) n+; P=p-next; Return p; 11已知非空线性链表的第一个结点的指针为head，请写一个算法，将该链表中数据域值最小的结点移动到链表的最前端。编写的函数具有如下原型：void func(TLinkNode *head), 其中链结点的结构如下： struct

49、 TLinkNode int data; TLinkNode *next; 请完成该算法。12. 编写递归算法，计算二叉树中叶子结点的数目。解：假定二叉树用二叉链表存储，并假定二叉树的结点类型定义如下struct node char data; struct node *lchild, rchild; node, BiTree*; 再假定 n 是一个全局整型变量，用来存放二叉树中叶子结点的数目。如下的函数统计出二叉树t（为指向给定二叉树根的指针）中叶子结点的数目：Int CountLeafNum(BiTree t) 精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 21 页，共 22 页 - - - - - - - - - - 学习 好资料精品资料If(t) CountLeafNum(t-lchild); CountLeafNum(t-lchild); If(!t-lchild & !t-rchild) n+; 精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 22 页，共 22 页 - - - - - - - - - -