出自:河南理工大学数据结构

回文是指正读反读均相同的字符序列,如“abba”和“abdba”均是回文,但“good”不是回文。试写一个算法判定给定的字符向量是否为回文。(提示:将一半字符入栈)
设从键盘输入一整数的序列:a1, a2, a3,…,an,试编写算法实现:用栈结构存储输入的整数,当ai≠-1时,将ai进栈;当ai=-1时,输出栈顶整数并出栈。算法应对异常情况(入栈满等)给出相应的信息。
从键盘上输入一个后缀表达式,试编写算法计算表达式的值。规定:逆波兰表达式的长度不超过一行,以$符作为输入结束,操作数之间用空格分隔,操作符只可能有+、-、*、/四种运算。例如:234 34+2*$。
假设以I和O分别表示入栈和出栈操作。栈的初态和终态均为空,入栈和出栈的操作序列可表示为仅由I和O组成的序列,称可以操作的序列为合法序列,否则称为非法序列。①下面所示的序列中哪些是合法的? A. IOIIOIOO B. IOOIOIIO C. IIIOIOIO D. IIIOOIOO ②通过对①的分析,写出一个算法,判定所给的操作序列是否合法。若合法,返回true,否则返回false(假定被判定的操作序列已存入一维数组中)。
假设以带头结点的循环链表表示队列,并且只设一个指针指向队尾元素站点(注意不设头指针) ,试编写相应的置空队、判队空 、入队和出队等算法。
假设以数组Q[m]存放循环队列中的元素, 同时设置一个标志tag,以tag == 0和tag == 1来区别在队头指针(front)和队尾指针(rear)相等时,队列状态为“空”还是“满”。试编写与此结构相应的插入(enqueue)和删除(dlqueue)算法。
如果允许在循环队列的两端都可以进行插入和删除操作。要求: ① 写出循环队列的类型定义; ② 写出“从队尾删除”和“从队头插入”的算法。
已知f为单链表的表头指针, 链表中存储的都是整型数据,试写出实现下列运算的递归算法: ① 求链表中的最大整数; ② 求链表的结点个数; ③ 求所有整数的平均值。
最大容量为n的循环队列,队尾指针是rear,队头是front,若牺牲一个空间不用,则队列满的条件是____________________。
已知模式串t=‘abcaabbabcab’写出用KMP法求得的每个字符对应的next和nextval函数值。
设目标为t=“abcaabbabcabaacbacba”,模式为p=“abcabaa” ① 计算模式p的naxtval函数值; ② 不写出算法,只画出利用KMP算法进行模式匹配时每一趟的匹配过程。
数组A中,每个元素A[i,j]的长度均为32个二进位,行下标从-1到9,列下标从1到11,从首地址S开始连续存放主存储器中,主存储器字长为16位。求: ① 存放该数组所需多少单元? ② 存放数组第4列所有元素至少需多少单元? ③ 数组按行存放时,元素A[7,4]的起始地址是多少? ④ 数组按列存放时,元素A[4,7]的起始地址是多少?
请将香蕉banana用工具 H( )—Head( ),T( )—Tail( )从L中取出。 L=(apple,(orange,(strawberry,(banana)),peach),pear)
写一个算法统计在输入字符串中各个不同字符出现的频度并将结果存入文件(字符串中的合法字符为A-Z这26个字母和0-9这10个数字)。
写一个递归算法来实现字符串逆序存储,要求不另设串存储空间。
编写算法,实现下面函数的功能。函数void insert(char*s,char*t,int pos)将字符串t插入到字符串s中,插入位置为pos。假设分配给字符串s的空间足够让字符串t插入。(说明:不得使用任何库函数)
已知字符串S1中存放一段英文,写出算法format(s1,s2,s3,n),将其按给定的长度n格式化成两端对齐的字符串S2, 其多余的字符送S3。
设二维数组a[1..m, 1..n] 含有m*n 个整数。 ① 写一个算法判断a中所有元素是否互不相同?输出相关信息(yes/no); ② 试分析算法的时间复杂度。
设任意n个整数存放于数组A(1:n)中,试编写算法,将所有正数排在所有负数前面(要求算法复杂度为0(n))。
串是元素类型为字符型的线性表。
A.正确
B.错误
二维数组S,行下标i从0到7,列下标j从0 到9,每个元素占3个字节,若从首地址S开始以列序为主序将元素连续存放在存储器内,则元素S [4][7]的起始地址为 。
试找出满足下列条件的二叉树 ① 先序序列与后序序列相同 ②中序序列与后序序列相同 ③ 先序序列与中序序列相同 ④中序序列与层次遍历序列相同
以二叉链表作为二叉树的存储结构,编写以下算法: (1)统计二叉树的叶结点个数。
判别两棵树是否相等。
交换二叉树每个结点的左孩子和右孩子。
设计二叉树的双序遍历算法(双序遍历是指对于二叉树的每一个结点来说,先访问这个结点,再按双序遍历它的左子树,然后再一次访问这个结点,接下来按双序遍历它的右子树)。
计算二叉树最大的宽度(二叉树的最大宽度是指二叉树所有层中结点个数的最大值)。
用按层次顺序遍历二叉树的方法,统计树中具有度为1的结点数目。
求任意二叉树中第一条最长的路径长度,并输出此路径上各结点的值。
输出二叉树中从每个叶子结点到根结点的路径。
由树转化成二叉树,该二叉树的右子树不一定为空。
A.正确
B.错误
设一棵二叉树的中序遍历序列为BDCA,后序遍历序列为DBAC,则这棵二叉树的先序遍历序列为____________________。
分别以邻接矩阵和邻接表作为存储结构,实现以下图的基本操作: ① 增加一个新顶点v,InsertVex(G, v); ② 删除顶点v及其相关的边,DeleteVex(G, v); ③ 增加一条边,InsertArc(G, v, w); ④ 删除一条边,DeleteArc(G, v, w)。
一个连通图采用邻接表作为存储结构,设计一个算法,实现从顶点v出发的深度优先遍历的非递归过程。
设计一个算法,求图G中距离顶点v的最短路径长度最大的一个顶点,设v可达其余各个顶点。
试基于图的深度优先搜索策略写一算法,判别以邻接表方式存储的有向图中是否存在由顶点vi到顶点vj的路径(i≠j)。
采用邻接表存储结构,编写一个算法,判别无向图中任意给定的两个顶点之间是否存在一条长度为为k的简单路径。
对连通图进行深度优先遍历可以访问到该图中的所有顶点。
A.正确
B.错误
设无向图G中有n个顶点e条边,所有顶点的度数之和为m,则e和m有______关系。
试写出折半查找的递归算法。
试写一个判别给定二叉树是否为二叉排序树的算法。
已知二叉排序树采用二叉链表存储结构,根结点的指针为T,链结点的结构为(lchild,data,rchild),其中lchild,rchild分别指向该结点左、右孩子的指针,data域存放结点的数据信息。请写出递归算法,从小到大输出二叉排序树中所有数据值>=x的结点的数据。要求先找到第一个满足条件的结点后,再依次输出其他满足条件的结点。
已知二叉树T的结点形式为(lling,data,count,rlink),在树中查找值为X的结点,若找到,则记数(count)加1,否则,作为一个新结点插入树中,插入后仍为二叉排序树,写出其非递归算法。
假设一棵平衡二叉树的每个结点都表明了平衡因子b,试设计一个算法,求平衡二叉树的高度。
分别写出在散列表中插入和删除关键字为K的一个记录的算法,设散列函数为H,解决冲突的方法为链地址法。
m阶B-树的非叶结点至少有m/2 (m为偶数)或m/2+1(m为奇数)棵子树。
A.正确
B.错误
对22个记录的有序表作折半查找,查找失败时,至少需要比较___个关键字。
试以单链表为存储结构,实现简单选择排序算法
有n个记录存储在带头结点的双向链表中,现用双向冒泡排序法对其按上升序进行排序,请写出这种排序的算法。(注:双向冒泡排序即相邻两趟排序向相反方向冒泡)。
设有顺序放置的n个桶,每个桶中装有一粒砾石,每粒砾石的颜色是红,白,蓝之一。要求重新安排这些砾石,使得所有红色砾石在前,所有白色砾石居中,所有蓝色砾石居后,重新安排时对每粒砾石的颜色只能看一次,并且只允许交换操作来调整砾石的位置。