数据结构与算法小测习题

《数据结构与算法小测习题》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、QLLD数据结构与算法小测栈与队列Question1以下循环队列的实现方式中，长度为n的队列，所能容纳的元素个数也为n的有只用front和rear两个指针标记队列的头和尾，front为实指，rear为虚指用front和rear两个指针标记队列的头和尾，并用整型变量len记录队列元素数只用front和rear两个指针标记队列的头和尾，两个指针均为虚指用front和rear两个指针标记队列的头和尾，并用布尔型变量empty记录队列是否为空Question2依次读入数据元素序列{a，b，c，d，e，f，g}进栈，每进一个元素，机器可要求下一个元素进栈或弹栈，如此进行，则栈空时弹出的元素构成

2、的序列可以是以下哪些序列{c，d，a，b，e，f，g}{c，d，b，e，f，a，g}{e，f，d，g，b，c，a}{a，c，e，f，g，d，b}Question3设栈S和队列Q的初始状态为空，元素e1，e2，e3，e4，e5和e6依次通过栈S，一个元素出栈后即进队列Q，若6个元素出队的序列是e2，e4，e3，e6，e5，e1则栈S的容量至少应该是_____________。4638Question4如果用两个栈来模拟一个队列，请问以下哪两个栈最可能高效地模拟了一个队列？（假设元素入队顺序为a,b,c,d,e,f,g,h,i,j，选项表示的是栈的状态）Question5在具有n个单元的

3、顺序存储的循环队列中，假定front和rear分别为队头指针和队尾指针，则判断队满的条件为rear％n+1=frontfront％n-1=rearrear％n-1=frontfront％n+1=rear字符串Question1若字符串s=”algorithm”，则其子串个数为：AnswerforQuestion1Question2设有字符串变量StringA＝“”，B＝“MULE”，C＝“OLD”，D＝“MY”;请计算下列表达式：(1)D+C+B (2)B.substr(3，2)(3)A.strlength()注：答案用空格分隔，答案不要加引号AnswerforQuestion2Qu

4、estion3一个文本串可用事先给定的字母映射表进行加密。例如，设字母映射表为：abcdefghijklmnopqrstuvwxyzngzqtcobmuhelkpdawxfyivrsj比如字符串"encrypt"被加密为"tkzwsdf"。则字符串“algorithm”，被加密为________________（答案不需要加引号）。AnswerforQuestion3Question4S=“S1S2…Sn”是一个长为n的字符串，存放在一个数组中，编程序将S改造之后输出。（1）将S的所有第偶数个字符按照其原来的下标从大到小的次序放在S的后半部分；（2）将S的所有第奇数个字符按照其原来的

5、下标从小到大的次序放在S的前半部分；例如：S=‘ABCDEFGHIJKL’，则改造后的S为‘ACEGIKLJHFDB’。则S=’algorithm’,改造后为____________（答案不需要加引号）。AnswerforQuestion4Question5在字符{A,C,G,T}组成的DNA序列中，A和T、C和G是互补对。判断一个DNA序列中是否存在互补回文串（例如，ATCATGAT的补串是TAGTACTA，与原串形成互补回文串）。下面DNA序列中存在互补回文串的是：TGCAACGTAGCTAGCTAATTAATTCATGGTAC二叉树基础Question1一棵有511个结点的完全

6、二叉树的高度为多少？（独根树高度为1）AnswerforQuestion1Question2在一棵非空二叉树中，若度为0的结点的个数n，度为2的结点个数为m，则有n= __________。AnswerforQuestion2Question3下列关于二叉树遍历的说法正确的有所有结点右子树为空的二叉树的前序和后序遍历顺序恰好一样。所有结点右子树为空的二叉树的中序和后序遍历顺序恰好一样。存在一棵非空二叉树，它的前序、中序和后序遍历都是一样的。所有结点右子树为空的二叉树的前序和中序遍历顺序恰好一样。Question4已知一棵树的中序遍历为DBGEACF，后序遍历为DGEBFCA，求这棵树

7、的前序遍历。（字母和字母之间不要有空格）AnswerforQuestion4Question5请写出下面这棵二叉树的前序遍历（字母和字母之间不要有空格）AnswerforQuestion5二叉树应用Question1下列关于二叉搜索树的说法正确的有二叉搜索树按照中序遍历将各结点打印出将各结点打印出来，将得到按照由小到大的排列。如果结点x的左子树有右子树，则存在某个结点的值介于结点x的值和x左儿子的值之间，并且这个结点在x的左子树之中。二叉搜索树一定是完全二