设待排序的排序码序列为{12, 2, 16, 30, 28, 10, 16*, 20, 6, 18},试写出使用

堆排序方法每趟排序后的结果。并说明做了多少次排序码比较。

设待排序的排序码序列为{12, 2, 16, 30, 28, 10, 16*, 20, 6, 18},试写出使用

基数排序方法每趟排序后的结果。并说明做了多少次排序码比较。

设待排序的排序码序列为{12, 2, 16, 30, 28, 10, 16*, 20, 6, 18},试写出使用

快速排序方法每趟排序后的结果。并说明做了多少次排序码比较。

设待排序的排序码序列为{12, 2, 16, 30, 28, 10, 16*, 20, 6, 18}, 试写出使用

起泡排序方法每趟排序后的结果。并说明做了多少次排序码比较。

设待排序的排序码序列为{12, 2, 16, 30, 28, 10, 16*, 20, 6, 18},试写出使用

希尔排序（增量为5,2,1）方法每趟排序后的结果。并说明做了多少次排序码比较。　

设待排序的排序码序列为{12, 2, 16, 30, 28, 10, 16*, 20, 6, 18}, 试写出使用

直接插入排序方法每趟排序后的结果。并说明做了多少次排序码比较。　

将哨兵放在R[n]中，被排序的记录放在R[0..n-1]中，重新编写直接插入排序算法。

对给定的j(1≤j≤n ),要求在无序的记录区R[1..n]中找到按关键字自小到大排在第j个位置上的记录(即在无序集合中找到第j个最小元)，试利用快速排序的划分思想编写算法实现上述的查找操作。　

写出快速排序的非递归算法。

设计一个算法，实现双向冒泡排序。

奇偶交换排序是另一种交换排序。它的第一趟对序列中的所有奇数项i扫描，第二趟对序列中的所有偶数项i扫描。若A[i] gt; A[i+1]，则交换它们。第三趟有对所有的奇数项，第四趟对所有的偶数项，…，如此反复，直到整个序列全部排好序为止。　

试设计一个算法，使得在O(n)的时间内重排数组，将所有取负值的排序码排在所有取正值(非负值)的排序码之前。

如果某个文件经内排序得到80个初始归并段，试问：　

（1）若使用多路归并执行3趟完成排序，那么应取的归并路数至少应为多少？　

（2）如果操作系统要求一个程序同时可用的输入/输出文件的总数不超过15个，则按多路归并至少需要几趟可以完成排序？如果限定这个趟数，可取的最低路数是多少？　　　

对一个具有7个记录的文件进行快速排序，请问：　

（1）在最好情况下需进行多少次比较？并给出一个最好情况初始排列的实例。　　

（2）在最坏情况下需进行多少次比较？为什么？并给出此时的实例。　

试构造对5个整数元素进行排序，最多只用7次比较的算法思想。

在起泡排序过程中，什么情况下排序码会朝向与排序相反的方向移动，试举例说明。在快速排序过程中有这种现象吗？

冒泡排序算法是否稳定？为什么？　

什么是内排序? 什么是外排序? 什么排序方法是稳定的? 什么排序方法是不稳定的? 　

试编写利用二分查找法确定记录的所在块的分块查找算法。

假设散列函数为H(k)=k % 11，采用链地址法处理冲突。设计算法：　　

（1）输入一组关键字（09,31,26,19,01,13,02,11,27,16,05,21）构造散列表。　　

（2）查找值为x的元素。若查找成功，返回其所在结点的指针，否则返回NULL。　　　

假设二叉排序树采用链表结构存储，设计一个算法，从大到小输出该二叉排序树中所有关键字不小于X的数据元素。

设计一个递归算法，向以BT为树根的二叉排序树上插入值为x的结点。

设计一个算法，以求出给定二叉排序树中值为最大的结点。

设计一个算法，求出指定结点在给定的二叉排序树中所在的层数。　

有递增排序的顺序线性表A[n]，写出利用二分查找算法查找元素K的递归算法。若找到则给出其位置序号，若找不到则其位置号为0。

若线性表中各结点的查找概率不等，则可用如下策略提高顺序查找的效率∶若找到指定的结点，则将该结点和其前驱结点交换，使得经常被查找的结点尽量位于表的前端。试对线性表的链式存储结构写出实现上述策略的顺序查找算法（查找时必须从表头开始向后扫描）。

已知顺序表A长度为n，试写出将监视哨设在高端的顺序查找算法。　

散列表的地址区间为0～15，散列函数为H(key)=key%13。设有一组关键字{19,01,23,14,55,20,84}, 采用线性探测法解决冲突，依次存放在散列表中。问：（1）元素84存放在散列表中的地址是多少？　　　

（2）搜索元素84需要的比较次数是多少？　　

假定一个待散列存储的线性表为(32,75,29,63,48,94,25,46,18,70)，散列地址空间为HT[13]，若采用除留余数法构造散列函数和线性探测法处理冲突，试求出每一元素的初始散列地址和最终散列地址，画出最后得到的散列表，求出平均查找长度。　

设散列函数为H(k)=k % 11，采用拉链法处理冲突，将上例中关键字序列依次存储到散列表中，并求出在等概率情况下的平均查找长度。　

已知散列表的地址区间为0～11，散列函数为H(k)=k % 11，采用线性探测法处理冲突，将关键字序列20,30,70,15,8,12,18,63,19依次存储到散列表中，试构造出该散列表，并求出在等概率情况下的平均查找长度。

直接在二叉排序树中查找关键码K与从中序遍历输出的有序序列中用二分查找法查找关键码K，其数据比较次数是否相同？　

以数据集合{1,2,3,4,5,6}的不同序列为输入，构造4棵高度为4的二叉排序树。　　

构造有12个元素的二分查找的判定树，并求解下列问题：　

（1）各元素的查找长度最大是多少？　

（2）查找长度为1、2、3、4的元素各有多少？具体是哪些元素？　

（3）查找第5个元素依次要比较哪些元素？　

为什么有序的单链表不能进行折半查找?　

设有序表为(a,b,c,d, e,f,g,h, i,j,k,p,q)，请分别画出对给定值a,g和n进行折半查找的过程。

查找成功，即表中有关键字等于给定值K的记录。

对含有n个互不相同元素的集合，同时找最大元和最小元至少需进行多少次比较?

顺序查找时间为O(n)，二分法查找时间为O(log2n)，散列法为O(1)，为什么有高效率的查找方法而低效率的方法不被放弃?　　

设计一个算法，用深度优先遍历法对AOV网进行拓扑排序，检测其中是否存在环。

设计一个算法，输出距离顶点v0的最短路径长度为k的所有顶点，其中路径长度指的是弧或边的数目。　

设计一个深度优先遍历图的非递归算法。（图用邻接矩阵存储） 　

已知某有向图用邻接表表示，设计一个算法，求出给定两顶点间的简单路径。　

设计一个算法，求出分别用邻接矩阵和邻接表表示的有向图中顶点的最大出度值。

设计一个算法，删除无向图的邻接矩阵中给定顶点。

拓扑排序的结果不是唯一的，试写出下图任意2个不同的拓扑序列。　

写出求以下AOE网的关键路径的过程。要求：给出每一个事件和每一个活动的最早开始时间和最晚开始时间。　

对n个顶点的无向图G，采用邻接矩阵表示，如何判别下列有关问题：　　　

（1）图中有多少条边?　

（2）任意两个顶点i和j是否有边相连?　

（3）任意一个顶点的度是多少?　

画出1个顶点、2个顶点、3个顶点、4个顶点和5个顶点的无向完全图。并说明在n个顶点的无向完全图中，边的条数为n(n-1)/2。　

设有一有向图为G=(V，E)。其中，V={ v1, v2, v3, v4, v5}，E={lt;v2, v1gt;, lt;v3, v2gt;, lt;v4, v3gt;, lt;v4, v2gt;, lt;v1, v4gt;, lt;v4, v5gt;, lt;v5, v1gt;}，请画出该有向图并判断是否是强连通图。

设计一个算法，在中序全线索二叉树中，查找给定结点* p在中序序列中的后继（二叉树的根结点指针并未给出），并中序遍历该线索二叉树。

编写递归算法，对于二叉树中每一个元素值为X的结点，删去以它为根的子树，并释放相应的空间。　

已知一棵高度为Ｋ具有ｎ个结点的二叉树，按顺序方式存储。　　　

（1）编写用先根遍历二叉树中每个结点的递归算法； 　

（2）编写将树中最大序号叶子结点的祖先结点全部打印输出的算法。　

设一棵二叉树以二叉链表为存贮结构，设计一个算法将二叉树中所有结点的左，右子树相互交换。

二叉树采用二叉链表存储　　　

（1）编写计算整个二叉树高度的算法（二叉树的高度也叫二叉树的深度）。　　　

（2）编写计算二叉树最大宽度的算法（二叉树的最大宽度是指二叉树所有层中结点个数的最大值）。

假设以双亲表示法作树的存储结构，写出双亲表示的类型说明，并编写求给定的树的深度的算法。（注：已知树中结点数）　

编写递归算法，在二叉树中求位于先序序列中第k个位置的结点的值。　

有n个结点的完全二叉树存放在一维数组A[1..n]中，试据此建立一棵用二叉链表表示的二叉树，根由tree指向。

要求二叉树按二叉链表形式存储：　　　

（1）写一个建立二叉树的算法。　　

（2）写一个判别给定的二叉树是否是完全二叉树的算法。　

假定用两个一维数组L[N]和R[N]作为有N个结点1，2,…， N的二叉树的存储结构。L[i]和R[i]分别指示结点 i的左子女和右子女；L[i]=0（R[i]=0）表示i的左（右）子女为空。设计一个算法，由L和R建立一个一维数组T[n]，使T[i]存放结点i的父亲；然后再写一个判别结点U是否为结点V的后代的算法。　　

编程求以孩子兄弟表示法存储的森林的叶子结点数，要求描述结构。

已知一棵二叉树按顺序方式存储在数组A[1..n]中。设计算法，求出下标分别为i和j的两个结点的最近的公共祖先结点的值。　　

已知下列字符A、B、C、D、E、F、G的权值分别为3、12、7、4、2、8，11，试填写出其对应哈夫曼树HT的存储结构的初态和终态。

设有正文AADBAACACCDACACAAD，字符集为A，B，C，D，设计一套二进制编码，使得上述正文的编码最短。　

一棵二叉树的先序、中序、后序序列如下，其中一部分未标出，请构造出该二叉树。　　

先序序列 ：_ _ C D E _ G H I _ K 　　　

中序序列 ：C B _ _ F A _ J K I G　

后序序列 ：_ E F D B _ J I H _ A 　

已知一个森林的先序序列和后序序列如下，请构造出该森林。　　　

先序序列：ABCDEFGHIJKLMNO　　

后序序列：CDEBFHIJGAMLONK 　

假设一棵二叉树的层次次序（按层次递增顺序排列，同一层次自左向右）为ABECFGDHI,中序序列为BCDAFEHIG。请画出该二叉树，并将其转换为对应的森林。　

一棵非空二叉树其先序序列和后序序列正好相反，画出二叉树的形状。

已知一棵二叉树的中序序列和后序序列分别为GLDHBEIACJFK和LGHDIEBJKFCA　　

（1）给出这棵二叉树；（2）转换为对应的森林。　

试找出满足下列条件的二叉树：　　

1）先序序列与后序序列相同； 2）中序序列与后序序列相同；　　

3）先序序列与中序序列相同； 4）中序序列与层次序列相同；

试证明，同一棵二叉树的所有叶子结点，在先序序列、中序序列以及后序序列中都按相同的相对位置出现（即先后顺序相同），例如先序abc，后序bca，中序bac。　　

求含有n个结点、采用顺序存储结构的完全二叉树中的序号最小的叶子结点的下标。要求写出简要步骤。　

若在内存中存放一个完全二叉树，在二叉树上只进行下面两个操作：　

（1）寻找某个结点双亲 ； （2）寻找某个结点的子女；　　　

请问应该用何种结构来存储该二叉树？　　

从概念上讲，树，森林和二叉树是三种不同的数据结构，将树，森林转化为二叉树的基本目的是什么，并指出树和二叉树的主要区别。

按层序输出广义表A中的所有元素。　

求广义表深度的递归算法。

假设稀疏矩阵A采用三元组表示，编写一个函数计算其转置矩阵B，要求B也用三元组表示。

给定有m个整数的递增有序数组A[1..m]和有n个整数的递减有序数组B[1..n]。试写出算法：将数组A和B归并为递增有序数组C[1..m+n]。（要求：算法的时间复杂度为O（m+n）。）　

假定数组A[n]的n个元素中有多个零元素，编写算法将A中所有的非零元素依次移到A的前端。　

利用广义表的head和tail操作写出函数表达式，把以下各题中的单元素banana从广义表中分离出来：　

（1） L1（apple, pear, banana, orange）　　

（2） L2（（apple, pear）, （banana, orange））　　　

（3） L3（（（apple）, （pear）, （bananA）, （orange）））　　　

（4） L4（（（（apple）））, （（pear））, （bananA）, orange）　　　

（5） L5（（（（apple）, pear）, bananA）, orange）　

（6） L6（apple, （pear, （bananA）, orange）） 　

设有一个n′n的对称矩阵A，为了节约存储，可以只存对角线及对角线以上的元素，或者只存对角线或对角线以下的元素。前者称为上三角矩阵，后者称为下三角矩阵。我们把它们按行存放于一个一维数组B中，称之为对称矩阵A的压缩存储方式。试问：　　　

（1） 存放对称矩阵A上三角部分或下三角部分的一维数组B有多少元素？　　　

（2） 若在一维数组B中从0号位置开始存放，则对称矩阵中的任一元素a_ij在只存下三角部分的情形下应存于一维数组的什么下标位置？给出计算公式。　　　

设有一个二维数组A[m][n]，假设A[0][0]存放位置在644，A[2][2]存放位置在676，每个元素占一个空间，问A[3][3]存放在什么位置？

编写一个实现串通配符匹配的函数，其中的通配符只有#39;?#39;，它可以和任何一个字符匹配成功。　

设计一个算法，将字符串s的全部字符复制到字符串t中，不能利用strcpy函数。

一个仅由字母组成的字符串s，长度为n，其结构为单链表，每个结点的data字段只存放一个字母。试设计一个函数，去掉字符串中所有的X字母，并将串中的一个最小字母排列到串尾。　

输入一个由若干单词组成的文本行，每个单词之间用若干个空格隔开，统计其中的单词数。　

采用顺序存储结构存储的串，编写一个程序，将两个字符串进行比较，若sgt;t时返回1，s=t时返回0，slt;t时返回-1。不能用strcmp库函数。

如果一个字符串的一个子串（其长度大于1）的各个字符均相同，则称之为等值子串。试设计一个算法，输入字符串s，以“！”作为结束标志。如果串s中不存在等值子串，则输出信息“无等值子串”，否则求出（输出）一个长度最大的等值子串。

若S和T是用结点大小为1的单链表存储的两个串，试设计一个算法找出S中第一个不在T中出现的字符。　

设计一个算法，统计在输入字符串中各个不同字符出现的频度。（字符串中的合法字符为#39;A#39;-#39;Z#39;这26个字母和#39;0#39;-#39;9#39;这10个数字）。

函数void insert(char*s,char*t,int pos)将字符串t插入到字符串s中，插入位置为pos。请用c语言实现该函数。假设分配给字符串s的空间足够让字符串t插入。（说明：不得使用任何库函数）

设s、t为两个字符串，分别放在两个一维数组中，m、n分别为其长度，判断t是否为s的子串。如果是，输出子串所在位置（第一个字符），否则输出0。　

设S1，S2为串，请给出使S1/*S2=S2/*S1成立的所有可能的条件（/*为连接符）。

描述以下概念的区别：空格串与空串。

用标志位方式设计出在循环队列中进行插入和删除运算的算法。

回文是指正读反读均相同的字符序列，如quot;abbaquot;和quot;abdbaquot;均是回文，但quot;goodquot;不是回文。设计一个算法判定给定的字符向量是否为回文。(提示：将一半字符入栈) 　

一个双向栈S是在同一向量空间内实现的两个栈，它们的栈底分别设在向量空间的两端。 试为此双向栈设计初始化InitStack ( S ) 、入栈Push( S , i , x) 和出栈Pop( S , i )等算法， 其中i为0 或1， 用以表示栈号。

假设循环队列中只设rear和length来分别指示队尾元素的位置和队中元素的个数，试给出判别此循环队列的队满条件，并写出相应的入队和出队算法，要求出队时需返回队头元素。　　

编写一个算法，利用栈的基本运算将指定栈中的内容进行逆转。

试将下列递归函数改写为非递归函数。　　　

void test(int *sum)　　

{　

int x;　

scanf(quot;%dquot;,amp;x);　

if(x==0) *sum=0 ;　

else {test(amp;sum); (*sum)+=x;}　

printf(quot;%5dquot;,*sum);　

} 　　　

设整数序列a₁，a₂，…，a_n，给出求解最大值的递归程序。

假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾结点，但不设头指针，请写出相应的入队列和出队列算法。　

1．设表达式以字符形式已存入数组E[n]中，‘#’为表达式的结束符，试写出判断表达式中括号（‘（’和‘）’）是否配对的C语言描述算法：EXYX(E); (注：算法中可调用栈操作的基本算法。) 　

若以1、2、3、4作为双端队列的输入序列，试分别求出以下条件的输出序列：　　

（1）能由输入受限的双端队列得到，但不能由输出受限的双端队列得到的输出序列；　　　

（2）能由输出受限的双端队列得到，但不能由输入受限的双端队列得到的输出序列；　　　

（3）既不能由输入受限双端队列得到，也不能由输出受限双端队列得到的输出序列。

简述顺序存储队列的假溢出的避免方法及队列满和空的条件。

如果输入序列为123456，试问能否通过栈结构得到以下两个序列：435612和13542 6，请说明为什么不能或如何才能得到。

假设以S和X分别表示入栈和出栈操作，则对初态和终态均为空的栈操作可由S和X组成的序列表示（如SXSX）。　

（1）试指出判别给定序列是否合法的一般规则。　

（2）两个不同合法序列（对同一输入序列）能否得到相同的输出元素序列？如能得到，请举列说明。

名词解释：栈和队列

设 head为一单链表的头指针，单链表的每个结点由一个整数域data和指针域next组成，整数在单链表中是无序的。编一函数，将 head链中结点分成一个奇数链和一个偶数链，分别由p，q指向，每个链中的数据按由小到大排列。程序中不得使用malloc申请空间。

已知三个带头结点的线性链表A、B和C中的结点均依元素值自小至大非递减排列（可能存在两个以上值相同的结点），编写算法对A表进行如下操作：使操作后的链表A中仅留下三个表中均包含的数据元素的结点，且没有值相同的结点，并释放所有无用结点。限定算法的时间复杂度为O（m+n+p），其中m、n和p分别为三个表的长度。　　

设有一个双向循环链表，每个结点中除有 prior，data和 next三个域外，还增设了一个访问频度域freq。在链表被起用之前，频度域freq的值均初始化为零，而每当对链表进行一次LOCATE（L，X）的操作后，被访问的结点（元素值等于X的结点）中的频度域freq的值便增1，同时调整链表中结点之间的次序，使其按访问频度非递增的次序顺序排列，以便始终保持被频繁访问的结点总是靠近表头结点。试编写符合上述要求的 LOCATE操作的算法。

设L为单链表的头结点地址，其数据结点的数据都是正整数且无相同的，试设计利用直接插入的原则把该链表整理成数据递增的有序单链表的算法。

已知A，B和C为三个递增有序的线性表，现要求对A表作如下操作：删去那些既在B表中出现又在C表中出现的元素。试对顺序表编写实现上述操作的算法，并分析你的算法的时间复杂度（注意：题中没有特别指明同一表中的元素值各不相同）。

假设有两个按元素值递增有序排列的线性表A和B，均以单链表作存储结构，请设计一个算法将A表和B表归并成一个按元素值递减有序（即非递增有序，允许表中含有值相同的元素）排列的线性表C，并要求利用原表（即 A表和B表）的结点空间构造C表。

设线性表A=（a₁，a₂，…，a_m） 和 B=（b₁，b₂，…，b_n），试设计一个按下列规则合并A，B为线性表C的算法，即使得　

C=（a₁，b₁，…，a_m，b_m，b_m+1，…，b_n）当 m≤n时；　　　

或者 　

C=（a₁，b₁，…，a_n，b_n，a_n+1，…，a_m）当m＞n时。　　　

线性表A，B和C均以单链表作存储结构，且C表利用A表和B表中的结点空间构成。注意：单链表的长度值m和n均未显式存储。

试设计一个算法，对带头结点的单链表实现就地逆置。

已知线性表中的元素以值递增有序排列，并以单链表作存储结构。试设计一个高效的算法，删除表中所有值相同的多余元素（使得操作后的线性表中所有元素的值均不相同），同时释放被删结点空间。　

已知线性表中的元素以值递增有序排列，并以单链表作存储结构。试设计一个高效的算法，删除表中所有值大于 mink且小于 maxk的元素（若表中存在这样的元素），同时释放被删结点空间（注意：mink和maxk是给定的两个参变量。它们的值可以和表中的元素相同，也可以不同）。

试设计一个算法，在无头结点的动态单链表上实现线性表操作INSERT（L，i，b），并和在带头结点的动态单链表上实现相同操作的算法进行比较。

已知指针 ha和 hb分别指向两个单链表的头结点，并且已知两个链表的长度分别为m和n。试设计一个算法将这两个链表连接在一起（即令其中一个表的首元结点连在另一个表的最后一个结点之后），假设指针hc指向连接后的链表的头结点，并要求算法以尽可能短的时间完成连接运算。

设 A=（a₁，a₂，…，a_m） 和 B=（b₁，b₂，…，b_n）均为顺序表，试设计一个比较A，B大小的算法（请注意：在算法中，不要破坏原表A和B）。

设顺序表va中的数据元素递增有序。试设计一个算法，将x插入到顺序表的适当位置上，以保持该表的有序性。