下载文档原格式
一、单项选择题（本大题共71小题，每小题2分，共142分）1、一个对象序列的排序码为{46，79，56，38，40，84}，采用快速排序以位于最左位置的对象为基准而得到的第一次划分结果为（）。
（）A．{38，46，79，56，40，84}B．{38，79，56，46，40，84}C．{40，38，46，56，79，84}D．{38，46，56，79，40，84}标准答案：C2、广义表（（a）,a）的表头是（）。
（）A．aB．bC．(a)D．((a))标准答案：C3、数组A中，每个元素A的长度为3个字节，行下标i从1到8，列下标j从1到10，从首地址SA开始连续存放在存储器内，存放该数组至少需要的单元数是（）。
（）A．80B．100C．240D．270标准答案：C4、在一个单链表HL中，若要向表头插入一个由指针p指向的结点，则执行（）。
（）A．HL=p；p->next=HL；B．p->next=HL；HL=p；C．p->next=HL；p=HL；D．p->next=HL->next；HL->next=p；标准答案：B5、一个具有n个顶点的无向完全图的边数为（）。
（）A．(n+1)/2B．n(n-1)/2C．n(n-1)D．n(n+1)标准答案：B6、如果待排序序列中两个数据元素具有相同的值，在排序后它们的位置发生颠倒，则称该排序是不稳定的。
下列选项中，（）就是不稳定的排序方法。
（）A．起泡排序B．归并排序C．直接插入法排序D．简单选择排序标准答案：D7、按照二叉树的定义，具有3个结点的二叉树有（）种。
（）A．3B．4C．5D．6标准答案：C8、设有1000个元素，用二分法查找时，最大比较次数是（）。
（）A．1B．7C．10D．25标准答案：C9、树适合用来表示（）。
（）A．有序数据元素B．无序数据元素C．元素之间具有分支层次关系的数据D．元素之间无联系的数据标准答案：C10、设有两个串p和q，求p在q中首次出现的位置的运算称作（）。
第一章绪论一、单项选择题1．数据结构是一门研究非数值计算的程序设计问题中计算机的①以及它们之间的②和操作等的学科。
① A.操作对象 B．计算方法 C·逻辑存储 D.数据映象② A.结构 B．关系 C．运算． D.算法2．数据结构被形式地定义为（D，R），其中D是①的有限集合，R是D上的②有限集合。
① A.算法 B.数据元素 C．数据操作 D．逻辑结构② A.操作 B.映象 C、存储 D.关系3．在数据结构中，从逻辑上可以把数据结构分成（）。
A.动态结构和静态结构 B．紧凑结构和非紧凑结构C.线性结构和非线性结构 D．内部结构和外部结构4·算法分析的目的是①，算法分析的两个主要方面是②。
① A. 找出数据结构的合理性 B．研究算法中的输入和输出的关系C. 分析算法的效率以求改进D. 分析算法的易懂性和文档性② A. 空间复杂性和时间复杂性 B．正确性和简明性C．可读性和文档性 D．数据复杂性和程序复杂性5．计算机算法指的是①，它必具备输入、输出和②等五个特性。
① A. 计算方法 B．排序方法 C. 解决问题的有限运算序列 D．调度方法② A. 可行性、可移植性和可扩充性 B. 可行性、确定性和有穷性C. 确定性、有穷性和稳定性 D．易读性、稳定性和安全性6. 线性表的逻辑顺序与存储顺序总是一致的，这种说法（）。
A. 正确 B．不正确7. 线性表若采用链式存储结构时，要求内存中可用存储单元的地址（）。
A. 必须是连续的 B．部分地址必须是连续的C. 一定是不连续的D. 连续或不连续都可以8．数据结构通常是研究数据的（）及它们之间的相互联系。
A．存储和逻辑结构 B．存储和抽象C．理想与抽象 D．理想与逻辑9．数据在计算机存储器内表示时，物理地址与逻辑地址相同并且是连续的，称之为（）。
A．存储结构 B．逻辑结构 C．顺序存储结构 D．链式存储结构11．非线性结构是数据元素之间存在一种（）。
数据结构复习题及答案5篇第一篇：数据结构复习题及答案、数据结构复习题及答案中南大学现代远程教育课程考试（专科）复习题及参考答案数据结构一、判断题：1．数组是一种复杂的数据结构，数组元素之间的关系既不是线性的也不是树形的。
（）2．链式存储在插人和删除时需要保持物理存储空间的顺序分配，不需要保持数据元素之间的逻辑顺序。
（）3．在只有度为0和度为k的结点的k叉树中，设度为0的结点有n0个，度为k的结点有nk个，则有n0=nk+1。
（）4．折半搜索只适用于有序表，包括有序的顺序表和有序的链表。
（）5．如果两个串含有相同的字符，则这两个串相等。
（）6．数组可以看成线性结构的一种推广，因此可以对它进行插入、删除等运算。
（）7．在用循环单链表表示的链式队列中，可以不设队头指针，仅在链尾设置队尾指针。
（）8．通常递归的算法简单、易懂、容易编写，而且执行的效率也高。
（）9．一个广义表的表尾总是一个广义表。
（）10．当从一个小根堆（最小堆）中删除一个元素时，需要把堆尾元素填补到堆顶位置，然后再按条件把它逐层向下调整，直到调整到合适位置为止。
（）11．对于一棵具有n个结点，其高度为h的二叉树，进行任一种次序遍历的时间复杂度为O（h）。
（）12．存储图的邻接矩阵中，邻接矩阵的大小不但与图的顶点个数有关，而且与图的边数也有关。
（）13．直接选择排序是一种稳定的排序方法。
（）14．闭散列法通常比开散列法时间效率更高。
（）15．有n个结点的不同的二叉树有n!棵。
（）16．直接选择排序是一种不稳定的排序方法。
（）17．在2048个互不相同的关键码中选择最小的5个关键码，用堆排序比用锦标赛排序更快。
（）18．当3阶B_树中有255个关键码时,其最大高度(包括失败结点层)不超过8。
（）19．一棵3阶B_树是平衡的3路搜索树,反之,一棵平衡的3路搜索树是3阶非B_树。
（）20．在用散列表存储关键码集合时，可以用双散列法寻找下一个空桶。
《数据结构》复习题一．选择题：1．数据结构是研究数据的( ) 以及它们之间的相互关系A．理想结构，物理结构B．理想结构，抽象结构C．物理结构，逻辑结构D．抽象结构，逻辑结构2. 组成数据的基本单位是（）A.数据项B.数据类型C. 数据元素D. 数据变量3. 如果某数据结构的数据元素的集合为S={A,B,C,D,E,F,G}，元素之间的关系为R={<A,D>,<A,G>,<D,B>,<D,C>,<G,E>,<G,F>},则该数据结构是一种（）A.线性结构B. 树结构C. 图结构D. 链表结构4. 线性表的链接实现有利于( ) 运算A.插入B.读表元C.查找D.定位5. 设一数列的输入顺序为1，2，3，4，5，6通过栈操作不可能排成的输出序列为（）A. 3，2，5，6，4，1B. 1，5，4，6，2，3C. 2，4，3，5，1，6D. 4，5，3，6，2，16. 设字符串S1=‘ABCDEFG’，S2=‘PQRST’则运算S=Concat(Sub(S1,2,Length(S2)),Sub(S1,Length(S2),2))后结果为（）A.‘BCQR’B.‘BCDEF’C.‘BCDEFG’D.‘BCDEFEF’7. 设单链表中指针P指向结点A，若要删除A之后的结点（若存在），则修改指针的操作为（）A. p→next= p→next→nextB. p= p→nextC. p= p→next→nextD. p→next = p8. 线性表采用链式存储时，其地址（）A. 必须是连续的B.部分地址必须是连续的C. 一定是不连续的D.连续与否均可以9. 在内部排序时，排序不稳定的有（）A.插入排序B. 冒泡排序C. 快速排序D.归并排序10. 设有1000个元素，用折半法查找时，最小比较次数为（）A.0B. 1C.10D. 50011. 将一个元素进入队列的时间复杂度是（）n)A. O (1)B. O (n)C. O (n2)D. O (log212. 在一个具有n个结点的单链表中查找其值等x的结点，在查找成功的情况下，需要比较（）个元素结点A. n/2B. nC. (n+1)/2D. (n-1)/213. 从一个长度为n的顺序表中删除第i个元素(1≤i≤n)，需向前移动（）个元素A. n-iB. n-i+1C. n-i-1D. i14. 总共3层的完全二叉树，其结点数至少有（）A.3B. 4C.7D.815. 队列操作的原则是（）A. 先进先出B.后进先出C. 只能进行插入D. 只能进行删除16. 若线性表最常用的操作是存取第i个元素及其前驱元素的值，则采用（）存储方式最节省时间A.单链表B. 双向链表C. 音循环链表D. 顺序表17. 栈和队列都是（）A. 顺序存储的线性结构B. 限制存取点的线性结构C. 链接存储的线性结构D. 限制存取点的非线性结构18. 与线性表的链接存储相符的特性是（）A.插入和删除操作灵活B. 需要连续存储空间C. 便于随机访问D. 存储密度大19.若进队序列为1,2,3,则出队序列是（）A.3，2，1B. 1，3，2C. 1，2，3D. 3，2，120. 在单向循环链表中，若头指针为h，那么p所指结点为尾结点的条件是（）A. p= NULLB. p→next= NULLC. p=hD. p→next= h3. 在双向循环链表中,在指针P所指的结点之后插入指针f所指的结点,其操作为。
（完整版）数据结构复习题（附答案）⼀、算法设计题（每题15分，共60分）答题要求：①⽤⾃然语⾔说明所采⽤算法的思想；②给出每个算法所需的数据结构定义，并做必要说明；③写出对应的算法程序，并做必要的注释。
1、有⼀个带头结点的单链表，每个结点包括两个域，⼀个是整型域info，另⼀个是指向下⼀个结点的指针域next。
假设单链表已建⽴，设计算法删除单链表中所有重复出现的结点，使得info域相等的结点只保留⼀个。
3、约瑟夫环问题（Josephus问题）是指编号为1、2、…，n的n（n>0）个⼈按顺时针⽅向围坐成⼀圈，现从第s个⼈开始按顺时针⽅向报数，数到第m个⼈出列，然后从出列的下⼀个⼈重新开始报数，数到第m的⼈⼜出列，…，如此重复直到所有的⼈全部出列为⽌。
现要求采⽤循环链表结构设计⼀个算法，模拟此过程。
4、编程实现单链表的就地逆置。
23．在数组 A[1..n]中有n个数据，试建⽴⼀个带有头结点的循环链表，头指针为h，要求链中数据从⼩到⼤排列，重复的数据在链中只保存⼀个.5、设计⼀个尽可能的⾼效算法输出单链表的倒数第K个元素。
3、假设以I和O分别表⽰⼊栈和出栈操作。
栈的初态和终态均为空，⼊栈和出栈的操作序列可表⽰为仅由I和O组成的序列，称可以操作的序列为合法序列，否则称为⾮法序列。
（15分）（1）下⾯所⽰的序列中哪些是合法的？A. IOIIOIOOB. IOOIOIIOC. IIIOIOIOD. IIIOOIOO（2）通过对（1）的分析，写出⼀个算法，判定所给的操作序列是否合法。
若合法，返回true，否则返回false（假定被判定的操作序列已存⼊⼀维数组中）。
5、设从键盘输⼊⼀整数的序列：a1, a2, a3，…，an,试编写算法实现：⽤栈结构存储输⼊的整数，当ai≠-1时，将ai进栈；当ai=-1时，输出栈顶整数并出栈。
算法应对异常情况（⼊栈满等）给出相应的信息。
设有⼀个背包可以放⼊的物品重量为S，现有n件物品，重量分别为W1，W2，...，W n。
一单选题 (共20题，总分值60分 )1. 下列叙述中错误的是（）。
（3 分）A. 由树的先序遍历序列和后序遍历序列可以惟一确定一棵树B. 二叉树不同于度为2的有序树C. 深度为k的二叉树上最少有k个结点D. 在结点数目相同的二叉树中，最优二叉树的路径长度最短2. 顺序表中数据元素的存取方式为（）。
（3 分）A. 随机存取B. 顺序存取C. 索引存取D. 连续存取3. 设有向图G中有五个顶点，各顶点的度分别为3、2、2、1、2，则G中弧数为（）。
（3 分）A. 4条B. 5条C. 6条D. 无法确定4. 下列关于文件的说法，错误的是（）。
（3 分）A. 选择文件的组织方式时应考虑外存的性质和容量B. 不定长文件指的是总长度可变的文件C. 对文件的操作主要是维护和检索D. 文件的存储结构指的是文件在外存上的组织方式5. ISAM文件和VSAM文件属于（）。
（3 分）A. 索引非顺序文件B. 索引顺序文件C. 顺序文件D. 散列文件6. 适用于折半查找的表的存储方式及元素排列要求为（）。
（3 分）A. 链接方式存储，元素无序B. 链接方式存储，元素有序C. 顺序方式存储，元素无序D. 顺序方式存储，元素有序7. 在数据结构中，数据的（）结构是独立于计算机的。
（3 分）A. 逻辑B. 存储C. 散列D. 索引8. 设串s1='abcdefg'，s2='ab'，则Concat(s1,s2)的返回值（）。
（3 分）A. abB. cdefgC. abcdefgD. abcdefgab9. 若需在O(nlog2n)的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方法是（）。
（3 分）A. 快速排序B. 堆排序C. 归并排序D. 直接插入排序10. 设在一不带头结点的链队列中，front和rear分别为其队头和队尾指针，则判定该队中只有一个结点的条件是（）。
（3 分）A. front->nextB. rear->nextC. front==rearD. front!=rear11. 具有n个顶点的有向强连通图最少有（）条弧。
一、单项选择题1．评价一个算法时间性能的主要标准是（）A.算法易于调试B. 算法易于理解C.算法的稳定性和正确性D.算法的时间复杂度2．可用带表头结点的链表来表示表，也可用不带表头结点的链表来表示表，前者的主要好处是（）A.可以加快对表的遍历B.使空表和非空表的处理统一C.提高存取结点的速度D.节省存储空间3．稀疏矩阵一般的压缩存储有两种，即（）。
A．一维数组和二维数组B．一维数组和三元组C．二维数组和十字链表D．三元组和十字链表4.链表不具有的特点是（）。
Ａ．可随机访问任一元素Ｂ．插入删除不需要移动元素Ｃ．不必事先估计存储空间Ｄ．所需空间与线性表的长度成正比5.非空的循环单链表head的尾结点p满足（）。
A．P->next==NULL B．p==NULL C．P->next==head D．P==head 6．对稀疏矩阵进行压缩存储是为了（）。
A.便于进行矩阵运算B.便于输入和输出C.节省存储空间D.降低运算的时间复杂度7．数据结构中,与所使用的计算机无关的是数据的（）结构。
A.顺序B.物理C.逻辑D.物理和存储8．在长度为n的顺序表中插入一个元素时,等概率情况下的平均移动元素的次数是（）。
A.（n-1）/2B.n/2C.n*(n-1)/2D.(n+1)/29．对于一个头指针为H的带头结点的单链表，判定该表为空表的条件是（）A. H==NULL B．H!=NULL C.H→next ==H D．H→next==NULL10. 在一个顺序表中，若表的第一个元素的存储地址是210，每一个元素的长度为3，则第5个元素的存储地址是（）。
A．219 B．222 C．225 D．22811. 栈S最多能容纳4个元素,现有6个元素按a,b,c,d,e,f的顺序进栈,下面序列（）是可能的出栈序列。
A．edcbaf B.bcefad C.cbedaf D.adfebc12．循环队列用数组A[M]存放元素，已知其头尾指针分别为front和rear，则当前队列中的元素个数是（）。
数据结构复习题（附答案）1. 快速排序在最坏情况下的时间复杂度为（ D ）。
A．O(log2n) B．O(nlog2n) C．O (n) D. O (n2)2．设⼀棵⼆叉树的深度为k，则该⼆叉树中最多有（ D ）个结点。
A. 2k-1B. 2kC.2k-1D. 2k-13．⼆叉树中第i(i≥1)层上的结点数最多有（ C ）个。
A. 2iB. 2iC. 2i-1D. 2i-1 4．设指针变量p指向单链表结点A，则删除结点A的后继结点B需要的操作为（ A ）。
A. p->next=p->next->nextB. p=p->nextC. p=p->next->nextD. p->next=p5．设栈S和队列Q的初始状态为空，元素E1、E2、E3、E4、E5和E6依次通过栈S，⼀个元素出栈后即进⼊队列Q，若6个元素出列的顺序为E2、E4、E3、E6、E5和E1，则栈S的容量⾄少应该是（ C ）。
A. 6B. 4C. 3D. 26.设有以下四种排序⽅法，则（ B ）的空间复杂度最⼤。
A. 冒泡排序B. 快速排C. 堆排序D. 希尔排序7．设结点A有3个兄弟结点且结点B为结点A的双亲结点，则结点B的度数数为（ B ）。
A. 3B. 4C. 5D. 18．根据⼆叉树的定义可知⼆叉树共有（ B ）种不同的形态。
A. 4B. 5C. 6D. 79．对⼀个算法的评价，不包括如下（ A ）⽅⾯的内容。
A．并⾏性 B．健壮性和可读性 C．正确性 D．时空复杂度10．在⼆叉排序树中插⼊⼀个结点的时间复杂度为（ C ）。
A．O(1) B．O(n) C．O(log2n) D．O(n2)11. 队列是⼀种（ B ）的线性表。
A．先进后出B．先进先出 C．只能插⼊D．只能删除12．采⽤开放定址法处理散列表的冲突时，其平均查找长度（ C ）。
A．低于链接法处理冲突 B. 与链接法处理冲突相同C．⾼于链接法处理冲突 D．⾼于⼆分查找13.设有序顺序表中有n个数据元素，则利⽤⼆分查找法查找数据元素X的最多⽐较次数不超过（ A ）。
数据结构复习题及答案数据结构习题一、名词解释1.数据、数据元素、数据项、数据结构、数据的逻辑结构、数据物理结构、顺序存储、链式存储、算法、时间复杂度、空间复杂度。
2.线性表、顺序表、单链表、双向链表、循环链表、双向循环链表、三个概念的区别：头指针、头结点、首元结点(第1个元素结点)。
3.栈（顺序栈、链栈）、队列（顺序队、链队）、循环队列、递归、稀疏矩阵、三元组。
4.树、叶子结点、结点的度、树的度、树的高(深)度、二叉树、遍历、满二叉树、完全二叉树、哈夫曼树、WPL、哈夫曼编码。
5.图（有向、无向）、网、边、弧、度、入度、出度、完全图（有向、无向）、（强）连通图（分量）、（最小）生成树、邻接矩阵、邻接表、DFS、BFS。
6.查找表、关键字、静态查找、动态查找、ASL、顺序查找、折半查找、分块查找、二叉排序树。
7、排序、内（外）排序、稳定性、插入（直接、希尔），交换（起泡、快速），选择（直接、堆），2路归并。
一、填空题1.数据结构是研究数据的_逻辑结构__和___物理结构__，并在这种结构上定义相关的运算，设计实现这些运算的算法，分析算法的效率。
算法的效率包括时间和空间两个方面，分别称为___时间复杂度____和__空间复杂度___。
2.数据的基本单元是__数据元素__，数据的最小单元是__数据项_。
3.算法是对特定问题求解___步骤___的一种描述，是指令的有限序列。
4.一个算法的时间复杂度为(3n3+2n—7)，其数量级表示为O（n3）_。
5.一个算法具有5个特性：确定性、可行性、有穷性、输入和输出。
6.算法机能的阐发和怀抱，能够从算法的工夫庞大度和空间庞大度来评判算法的好坏。
7.数据的逻辑布局包孕调集布局、线性布局、树形布局和图型布局四品种型。
8.数据布局在计较机中的表示称为数据的物理布局，它能够采用__按次存储___或__链式存储_两种存储方法。
9.线性表有两种存储布局，划分为按次存储和链式存储。
数据结构复习题及标准答案————————————————————————————————作者：————————————————————————————————日期：一、选择题。
(每小题2分，共40分)(1) 计算机识别.存储和加工处理的对象被统称为____A____。
A.数据B.数据元素C.数据结构D.数据类型(2) 数据结构通常是研究数据的____ A _____及它们之间的联系。
A.存储和逻辑结构B.存储和抽象C.理想和抽象D.理想与逻辑(3) 不是数据的逻辑结构是____ A ______。
A.散列结构B.线性结构C.树结构D.图结构(4) 数据结构被形式地定义为<D,R>,其中D是____ B _____的有限集，R是____ C _____的有限集。
A.算法B.数据元素C.数据操作D.逻辑结构(5) 组成数据的基本单位是____ A ______。
A.数据项B.数据类型C.数据元素D.数据变量(6) 设数据结构A=(D，R)，其中D={1，2，3，4}，R={r}，r={<1，2>，<2，3>，<3，4>，<4，1>}，则数据结构A是____ A ______。
A.线性结构B.树型结构C.图型结构D.集合(7) 数据在计算机存储器内表示时，物理地址与逻辑地址相同并且是连续的，称之为___ C ____。
A.存储结构B.逻辑结构C.顺序存储结构D.链式存储结构(8) 在数据结构的讨论中把数据结构从逻辑上分为___ A ____。
A.内部结构与外部结构B.静态结构与动态结构C.线性结构与非线性结构D.紧凑结构与非紧凑结构(9) 对一个算法的评价，不包括如下____ B _____方面的内容。
A.健壮性和可读性B.并行性C.正确性D.时空复杂度(10) 算法分析的两个方面是__ A ____。
A.空间复杂性和时间复杂性B.正确性和简明性C.可读性和文档性D.数据复杂性和程序复杂性(11) 线性表是具有n个___ C _____的有限序列（n≠0)。
一、算法设计题（每题15分，共60分）答题要求：①用自然语言说明所采用算法的思想；②给出每个算法所需的数据结构定义，并做必要说明；③写出对应的算法程序，并做必要的注释。
1、有一个带头结点的单链表，每个结点包括两个域，一个是整型域info，另一个是指向下一个结点的指针域next。
假设单链表已建立，设计算法删除单链表中所有重复出现的结点，使得info域相等的结点只保留一个。
3、约瑟夫环问题（Josephus问题）是指编号为1、2、…，n的n（n>0）个人按顺时针方向围坐成一圈，现从第s个人开始按顺时针方向报数，数到第m个人出列，然后从出列的下一个人重新开始报数，数到第m的人又出列，…，如此重复直到所有的人全部出列为止。
现要求采用循环链表结构设计一个算法，模拟此过程。
4、编程实现单链表的就地逆置。
23．在数组 A[1..n]中有n个数据，试建立一个带有头结点的循环链表，头指针为h，要求链中数据从小到大排列，重复的数据在链中只保存一个.5、设计一个尽可能的高效算法输出单链表的倒数第K个元素。
3、假设以I和O分别表示入栈和出栈操作。
栈的初态和终态均为空，入栈和出栈的操作序列可表示为仅由I和O组成的序列，称可以操作的序列为合法序列，否则称为非法序列。
（15分）（1）下面所示的序列中哪些是合法的？A. IOIIOIOOB. IOOIOIIOC. IIIOIOIOD. IIIOOIOO（2）通过对（1）的分析，写出一个算法，判定所给的操作序列是否合法。
若合法，返回true，否则返回false（假定被判定的操作序列已存入一维数组中）。
5、设从键盘输入一整数的序列：a1, a2, a3，…，an,试编写算法实现：用栈结构存储输入的整数，当ai≠-1时，将ai进栈；当ai=-1时，输出栈顶整数并出栈。
算法应对异常情况（入栈满等）给出相应的信息。
设有一个背包可以放入的物品重量为S，现有n件物品，重量分别为W1，W2，...，W n。
问能否从这n件物品中选择若干件放入背包，使得放入的重量之和正好是S。
设布尔函数Knap(S，n)表示背包问题的解，W i(i=1,2,...，n)均为正整数，并已顺序存储地在数组W中。
请在下列算法的下划线处填空，使其正确求解背包问题。
Knap(S，n)若S=0则Knap←true否则若（S<0）或(S>0且n<1)则Knap←false否则若Knap(1) , _=true则print(W[n])；Knap ←true否则 Knap←Knap(2) _ , _设有一个顺序栈S，元素s1, s2, s3, s4, s5, s6依次进栈，如果6个元素的出栈顺序为s2, s3, s4,s6, s5, s1，则顺序栈的容量至少应为多少？画出具体进栈、出栈过程。
假定采用带头结点的单链表保存单词，当两个单词有相同的后缀时，则可共享相同的后缀存储空间。
例如：设str1和str2是分别指向两个单词的头结点，请设计一个尽可能的高效算法，找出两个单词共同后缀的起始位置，分析算法时间复杂度。
将n(n>1)个整数存放到一维数组R中。
设计一个尽可能高效（时间、空间）的算法，将R中保存的序列循环左移p（0<p<n）个位置，即将R中的数据（x0, x1, x2,…, x n-1），变换为(x p，x p＋1, … , x n-1 ,x0, x1,…, x p-1)。
4．编写一个过程，对一个n×n矩阵，通过行变换，使其每行元素的平均值按递增顺序排列。
7．给定一个整数数组b[0..N-1]，b中连续的相等元素构成的子序列称为平台。
试设计算法，求出b中最长平台的长度。
【8. 给定nxm矩阵A[a..b,c..d],并设A[i,j]≤A[i,j+1](a≤i≤b,c≤j≤d-1)和A[i,j]≤A[i+1,j](a≤i≤b-1,c≤j≤d).设计一算法判定X的值是否在A中,要求时间复杂度为O(m+n)。
【22. 给定有m个整数的递增有序数组a[1..m]和有n个整数的递减有序数组b[1..n]，试写出算法:将数组a和b归并为递增有序数组c[l..m+n]。
(要求：算法的时间复杂度为O(m+n))4、要求二叉树按二叉链表形式存储，（15分）（1）写一个建立二叉树的算法。
（2）写一个判别给定的二叉树是否是完全二叉树的算法。
3、已知一棵二叉树的中序遍历结果为：DBFEAGHCI，后序遍历结果为：DFEBHGICA。
（1）画出这棵二叉树，并写出它的前序遍历结果；（2）将这棵二叉树转换成等价的森林或树。
24.将二叉树bt中每一个结点的左右子树互换的C语言算法如下，其中ADDQ(Q,bt),DELQ(Q),EMPTY(Q)分别为进队，出队和判别队列是否为空的函数，请填写算法中得空白处，完成其功能。
typedef struct node{int data ; struct node *lchild, *rchild; }btnode;void EXCHANGE(btnode *bt){btnode *p, *q;if (bt){ADDQ(Q,bt);while(!EMPTY(Q)){p=DELQ(Q); q=(1)___; p->rchild=(2)___; (3)___=q;if(p->lchild) (4)___; if(p->rchild) (5)___;}} }25.设t是给定的一棵二叉树，下面的递归程序count(t)用于求得:二叉树t中具有非空的左,右两个儿子的结点个数N2;只有非空左儿子的个数NL;只有非空右儿子的结点个数NR和叶子结点个数N0。
N2、NL、NR、N0都是全局量，且在调用count(t)之前都置为0. typedef struct node{int data; struct node *lchild,*rchild;}node;int N2,NL,NR,N0;void count(node *t){if (t->lchild!=NULL) if (1)___ N2++; else NL++;else if (2)___ NR++; else (3)__ ;if(t->lchild!=NULL)(4)____; if (t->rchild!=NULL) (5)____;}26.树的先序非递归算法。
void example(b)btree *b;{ btree *stack[20], *p；int top;if (b!=null){ top=1; stack[top]=b;while (top>0){ p=stack[top]; top--;printf(“%d”,p->data);if (p->rchild!=null){(1)___; (2)___;}if (p->lchild!=null)(3)___; (4)__;}}}}27.由二叉树的前序遍历和中序遍历序列能确定唯一的一棵二叉树，下面程序的作用是实现由已知某二叉树的前序遍历和中序遍历序列，生成一棵用二叉链表表示的二叉树并打印出后序遍历序列，请写出程序所缺的语句。
#define MAX 100typedef struct Node{char info; struct Node *llink, *rlink; }TNODE;char pred[MAX],inod[MAX];main(int argc,int **argv){ TNODE *root;if(argc<3) exit 0;strcpy(pred,argv[1]); strcpy(inod,argv[2]);root=restore(pred,inod,strlen(pred));postorder(root);}TNODE *restore(char *ppos,char *ipos,int n){ TNODE *ptr； char *rpos; int k;if(n<=0) return NULL;ptr->info=(1)_______;for((2)_______ ; rpos<ipos+n;rpos++) if(*rpos==*ppos) break;k=(3)_______;ptr->llink=restore(ppos+1, (4)_______,k );ptr->rlink=restore ((5)_______+k,rpos+1,n-1-k);return ptr;}postorder(TNODE*ptr){ if(ptr=NULL) return;postorder(ptr->llink); postorder(ptr->rlink); printf(“%c”,ptr->info);}28.证明由二叉树的中序序列和后序序列，也可以唯一确定一棵二叉树。
29. ①试找出满足下列条件的二叉树1）先序序列与后序序列相同 2）中序序列与后序序列相同3）先序序列与中序序列相同 4）中序序列与层次遍历序列相同30.设一棵二叉树的结点结构为 (LLINK,INFO,RLINK),ROOT为指向该二叉树根结点的指针，p和q分别为指向该二叉树中任意两个结点的指针，试编写一算法ANCESTOR（ROOT，p,q,r）,该算法找到p和q的最近共同祖先结点r。
31. 设T是一棵满二叉树，编写一个将T的先序遍历序列转换为后序遍历序列的递归算法。
32. 请设计一个算法，要求该算法把二叉树的叶子结点按从左到右的顺序连成一个单链表，表头指针为head。
二叉树按二叉链表方式存储，链接时用叶子结点的右指针域来存放单链表指针。
分析你的算法的时、空复杂度。
33. 设两棵二叉树的的根结点地址分别为p和q，采用二叉链表的形式存储这两棵树上所有的结点。
请编写程序，判断它们是否相似。
34. 一棵二叉树以二叉链表来表示，求其指定的某一层k(k>1)上的叶子结点的个数。
35.二叉树T的中序遍历序列和层次遍历序列分别是BAFDGCE和ABCDEFG，试画出该二叉树，并写出由二叉树的中序遍历序列和层次遍历序列确定二叉树的算法。
36.设二叉树的结点结构是（Lc,data,Rc），其中Lc、Rc分别为指向左、右子树根的指针，data是字符型数据。
试写出算法，求任意二叉树中第一条最长的路径长度，并输出此路径上各结点的值。
2、假设以邻接矩阵作为图的存储结构，编写算法判别在给定的有向图中是否存在一个简单有向回路，若存在，则以顶点序列的方式输出该回路（找到一条即可）。
（注：图中不存在顶点到自己的弧）图1 连通网G5、给定n 个村庄之间的交通图，若村庄i 和j 之间有道路，则将顶点i 和j 用边连接，边上的Wij 表示这条道路的长度，现在要从这n 个村庄中选择一个村庄建一所医院，问这所医院应建在哪个村庄，才能使离医院最远的村庄到医院的路程最短?试设计一个解答上述问题的算法，并应用该算法解答如图所示的实例。
