搜索
第2章线性表1．假设有两个按元素值递增次序排列的线性表，均以单链表形式存储。请编写算法将这两个单链表归并为一个按元素值递减次序排列的单链表，并要求利用原来两个单链表的结点存放归并后的单链表。【北京大学1998三、1（5分）】2.带头结点且头指针为ha和hb的两线性表A和B分别表示两个集合。两表中的元素皆为递增有序。请写一算法求A和B的并集AUB。要求该并集中的元素仍保持递增有序。且要利用A和B的原有结点空间。【北京邮电大学1992二（15分）】3.已知L1、L2分别为两循环单链表的头结点指针，m,n分别为L1、L2表中数据结点个数。要求设计一算法，用最快速度将两表合并成一个带头结点的循环单链表。【东北大学1996二(12分)】4.顺序结构线性表LA与LB的结点关键字为整数。LA与LB的元素按非递减有序，线性表空间足够大。试用类PASCAL语言给出一种高效算法，将LB中元素合到LA中，使新的LA的元素仍保持非递减有序。高效指最大限度的避免移动元素。【北京工业大学1997一、2(12分)】5.已知不带头结点的线性链表list，链表中结点构造为（data、link），其中data为数据域，link为指针域。请写一算法，将该链表按结点数据域的值的大小从小到大重新链接。要求链接过程中不得使用除该链表以外的任何链结点空间。【北京航空航天大学1998五（15分）】6.设L为单链表的头结点地址，其数据结点的数据都是正整数且无相同的，试设计利用直接插入的原则把该链表整理成数据递增的有序单链表的算法。【东北大学1996六(14分)】7.设Listhead为一单链表的头指针，单链表的每个结点由一个整数域DATA和指针域NEXT组成，整数在单链表中是无序的。编一PASCAL过程，将Listhead链中结点分成一个奇数链和一个偶数链，分别由P,Q指向，每个链中的数据按由小到大排列。程序中不得使用NEW过程申请空间。【山东大学1993六(15分)】12.线性表(a1,a2,a3,…,an)中元素递增有序且按顺序存储于计算机内。要求设计一算法完成：【东北大学1996三(12分)】（1）用最少时间在表中查找数值为x的元素。（2）若找到将其与后继元素位置相交换。（3）若找不到将其插入表中并使表中元素仍递增有序。14.已知两个单链表A和B,其头指针分别为heada和headb，编写一个过程从单链表A中删除自第i个元素起的共len个元素，然后将单链表A插入到单链表B的第j个元素之前。【中国矿业大学2000三（10分）】15.设线性表存于A[1..size]的前num个分量中，且递增有序。请设计一个算法，将x插入到线性表的适当位置上，以保持线性表的有序性，并在设计前说明设计思想，最后说明所设计算法的时间复杂度。【西安电子科技大学1999计应用1997二（10分）】18.已知一个单链表中每个结点存放一个整数，并且结点数不少于2，请设计算法以判断该链表中第二项起的每个元素值是否等于其序号的平方减去其前驱的值，若满足则返回ture，否则返回false.【西安电子科技大学2000软件1997二（10分）】19．两个整数序列A=a1,a2,a3,…,am和B=b1,b2,b3,…,bn已经存入两个单链表中，设计一个算法，判断序列B是否是序列A的子序列。【东北大学1999二(10分)】20．L1与L2分别为两单链表头结点地址指针，且两表中数据结点的数据域均为一个字母。设计把L1中与L2中数据相同的连续结点顺序完全倒置的算法。【东北大学1997四(15分)】21.请写一个算法将顺序（或链接）存储结构的线性表（a1...an）逆置为(an...a1)。【大连海事大学1996八(６分)】22．设有一个由正整数组成的无序（向后）单链表，编写完成下列功能的算法：（1）找出最小值结点，且打印该数值；（2）若该数值是奇数，则将其与直接后继结点的数值交换；（3）若该数值是偶数，则将其直接后继结点删除。【东北大学2000二(15分)】27.编写一个算法来交换单链表中指针P所指结点与其后继结点，HEAD是该链表的头指针，P指向该链表中某一结点。【吉林大学2001二、1(7分)】第3-4章栈、队列1.、利用栈可以检查表达式中括号是否配对，试编写算法实现之。（教材P483-9）2、编程实现利用队列将栈中元素逆置的算法。（教材P483-10）9.假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾结点，但不设头指针，如图所示（编者略），请写出相应的入队列和出队列算法。【西安电子科技大学1999计应用六（10分）】17．线性表中元素存放在向量A（1,…,n）中，元素是整型数。试写出递归算法求出A中的最大和最小元素。【北京邮电大学1994八（10分）】第4章数组1、给定nm矩阵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)。【东南大学2001六(13分)】第5章树和二叉树5．假定用两个一维数组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的后代的算法。【哈尔滨工业大学1999七(14分)】6．要求二叉树按二叉链表形式存储，（1）写一个建立二叉树的算法。（2）写一个判别给定的二叉树是否是完全二叉树的算法。完全二叉树定义为：深度为K，具有N个结点的二叉树的每个结点都与深度为K的满二叉树中编号从1至N的结点一一对应。此题以此定义为准。【西北大学2000六(12分)】13．二叉树采用二叉链表存储：【西北大学2001四】（1）编写计算整个二叉树高度的算法（二叉树的高度也叫二叉树的深度）。（2）编写计算二叉树最大宽度的算法（二叉树的最大宽度是指二叉树所有层中结点个数的最大值）。18．在二叉树中查找值为x的结点，试编写算法打印值为x的结点的所有祖先，假设值为x的结点不多于一个，最后试分析该算法的时间复杂度。【上海交通大学1998五】24．对于二叉树的链接实现,完成非递归的中序遍历过程。【中山大学1999五、(15分)】27．在一棵以二叉链表表示的二叉树上，试写出用按层次顺序遍历二叉树的方法，统计树中具有度为1的结点数目的算法。【同济大学2000三、2（12分）】28．设一棵二叉树以二叉链表为存贮结构，结点结构为(lchild,data,rchild)，设计一个算法将二叉树中所有结点的左，右子树相互交换。【福州大学1998四、2(10分)】39．试写出复制一棵二叉树的算法。【山东大学2000二(10分)】。41．请设计一个算法，要求该算法把二叉树的叶子结点按从左到右的顺序连成一个单链表，表头指针为head。二叉树按二叉链表方式存储，链接时用叶子结点的右指针域来存放单链表指针。分析你的算法的时、空复杂度。【华南师范大学1999六、2（13分）】46．设两棵二叉树的的根结点地址分别为p和q，采用二叉链表的形式存储这两棵树上所有的结点。请编写程序，判断它们是否相似。【上海交通大学2000十二(8分)】48．已知二叉树以二叉链表存储，编写算法完成：对于树中每一个元素值为x的结点，删去以它为根的子树，并释放相应的空间。【北京轻工业学院1998二(14分)】52．设计算法：统计一棵二叉树中所有叶结点的数目及非叶结点的数目。【南开大学2000三、1】53．编写一非递归算法，求二叉树上叶子结点的数量。二叉树用二叉链表存贮，左指针定义为lchild,右指针定义为rchild。【燕山大学2000七、2（8分）】56．设一棵二叉树中各结点的值互不相同，其前序序列和中序序列分别存于两个一维数组pre[1..n]和mid[1..n]中，试遍写算法建立该二叉树的二叉链表。【南京航空航天大学1999十(10分)】必须掌握的基础算法：1、删除一棵二叉树2、计算二叉树的结点个数3、二叉树复制4、交换二叉树中每个结点的左右子树5、求二叉树中度为1的结点个数6、求二叉树的高度7、二叉树中第k层结点的个数8、二叉树根到指定结点x的路径第6-8章集合、二叉树、散列表4.写出在二叉排序树中删除一个结点的算法，使删除后仍为二叉排序树。设删除结点由指针p所指，其双亲结点由指针f所指，并假设被删除结点是其双亲结点的右孩子。【南开大学1998七(16分)】5.已知二叉树排序树中某结点指针p,其双亲结点指针为fp,p为fp的左孩子，试编写算法，删除p所指结点。【北京轻工业学院1998五（12分）】6．二叉排序树采用二叉链表存储。写一个算法，删除结点值是X的结点。要求删除该结点后,此树仍然是一棵二叉排序树，并且高度没有增长（注：可不考虑被删除的结点是根的情况）。【中科院软件所1999七、1（8分）】10．给出折半查找的递归算法，并给出算法时间复杂度性分析。【河南大学1998五（5分）】15．设排序二叉树中结点的结构为下述三个域构成:data:给出结点数据的值；left:给出本结点的左儿子结点的地址；right:给出本结点的右儿子结点的地址设data域为正整数，该二叉树树根结点地址为T。现给出一个正整数x。请编写非递归程序，实现将data域的值小于等于x的结点全部删除掉。【上海交通大学2000十一(12分)】16．已知二叉树T的结点形式为(llink,data,count,rlink,),在树中查找值为X的结点，若找到，则记数（count）加1；否则，作为一个新结点插入树中，插入后仍为二叉排序树，写出其非递归算法。【中山大学1999数三(10分)】18．设二叉排序树的各元素值均不相同，采用二叉链表作为存储结构，试分别设计递归和非递归算法按递减序打印所有左子树为空，右子树非空的结点的数据域的值。【北方交通大学1998七（20分）】19．22.在二叉排序树的结构中，有些数据元素值可能是相同的，设计一个算法实现按递增有序打印结点的数据域，要求相同的数据元素仅输出一个，算法还应能报出最后被滤掉，而未输出的数据元素个数。【北京工业大学1995六(18分)】28.设给定关键字输入序列为（100，90，120，60，78，35，42，31，15）用散列法散列0-10的地址区间。要求设计一合理的散列函数；冲突时用链表法解决，写出散列算法，并构造出散列表，在等概率查找情况下查找成功的平均查找长度是多少？【东北大学1996四(12分)】29、利用二叉树遍历的思想编写一个判断二叉树是否是平衡二叉树的算法。30、设计一个算法，求出给定二叉排序树中最小和最大的元素。第9章图6．写出从图的邻接表表示转换成邻接矩阵表示的算法。【南开大学1998四(16分)】7．编写算法，将图的邻接矩阵存储改为邻接表的存储。【中山大学1998五、2（10分）】9．已知无向图采用邻接表存储方式，试写出删除边（i，j）的算法。【东南大学1999三（10分）】10．假设有向图以邻接表存储，试编写算法删除弧Vi，Vj的算法。【北京轻工业学院1997五（10分）】12．设有向图用邻接表表示,图有n个顶点,表示为1至n,试写一个算法求顶点k的入度(1kn)。【南京理工大学1997四、2（10分）】13．假设以邻接矩阵作为图的存储结构，编写算法判别在给定的有向图中是否存在一个简单有向回路，若存在，则以顶点序列的方式输出该回路（找到一条即可）。（注：图中不存在顶点到自己的弧）【清华大学1994六（15分）】17．试编写求无向图G的连通分量的算法。要求输出每一连通分量的顶点值。(设图G已用邻接表存储)【南京航空航天大学1995十一（10分）】18．设无向图G已用邻接表结构存储，顶点表为GL[n](n为图中顶点数)，试用“广度优先搜索”方法，写出求图G中各连通分量的C语言描述算法。（注：算法中可调用队列操作的基本算法。