数据结构与算法小测习题

QLLD数据结构与算法小测栈与队列Question1以下循环队列的实现方式中，长度为n的队列，所能容纳的元素个数也为n的有只用front和rear两个指针标记队列的头和尾，front为实指，rear为虚指用front和rear两个指针标记队列的头和尾，并用整型变量len记录队列元素数只用front和rear两个指针标记队列的头和尾，两个指针均为虚指用front和rear两个指针标记队列的头和尾，并用布尔型变量empty记录队列是否为空Question2依次读入数据元素序列{a，b，c，d，e，f，g}进栈，每进一个元素，机器可要求下一个元素进栈或弹栈，如此进行，则栈空时弹出的元素构成的序列可以是以下哪些序列{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个单元的顺序存储的循环队列中，假定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()注：答案用空格分隔，答案不要加引号AnswerforQuestion2Question3一个文本串可用事先给定的字母映射表进行加密。例如，设字母映射表为：abcdefghijklmnopqrstuvwxyzngzqtcobmuhelkpdawxfyivrsj比如字符串encrypt被加密为tkzwsdf。则字符串“algorithm”，被加密为________________（答案不需要加引号）。AnswerforQuestion3Question4S=“S1S2…Sn”是一个长为n的字符串，存放在一个数组中，编程序将S改造之后输出。（1）将S的所有第偶数个字符按照其原来的下标从大到小的次序放在S的后半部分；（2）将S的所有第奇数个字符按照其原来的下标从小到大的次序放在S的前半部分；例如：S=‘ABCDEFGHIJKL’，则改造后的S为‘ACEGIKLJHFDB’。则S=’algorithm’,改造后为____________（答案不需要加引号）。AnswerforQuestion4Question5在字符{A,C,G,T}组成的DNA序列中，A和T、C和G是互补对。判断一个DNA序列中是否存在互补回文串（例如，ATCATGAT的补串是TAGTACTA，与原串形成互补回文串）。下面DNA序列中存在互补回文串的是：TGCAACGTAGCTAGCTAATTAATTCATGGTAC二叉树基础Question1一棵有511个结点的完全二叉树的高度为多少？（独根树高度为1）AnswerforQuestion1Question2在一棵非空二叉树中，若度为0的结点的个数n，度为2的结点个数为m，则有n=__________。AnswerforQuestion2Question3下列关于二叉树遍历的说法正确的有所有结点右子树为空的二叉树的前序和后序遍历顺序恰好一样。所有结点右子树为空的二叉树的中序和后序遍历顺序恰好一样。存在一棵非空二叉树，它的前序、中序和后序遍历都是一样的。所有结点右子树为空的二叉树的前序和中序遍历顺序恰好一样。Question4已知一棵树的中序遍历为DBGEACF，后序遍历为DGEBFCA，求这棵树的前序遍历。（字母和字母之间不要有空格）AnswerforQuestion4Question5请写出下面这棵二叉树的前序遍历（字母和字母之间不要有空格）AnswerforQuestion5二叉树应用Question1下列关于二叉搜索树的说法正确的有二叉搜索树按照中序遍历将各结点打印出将各结点打印出来，将得到按照由小到大的排列。如果结点x的左子树有右子树，则存在某个结点的值介于结点x的值和x左儿子的值之间，并且这个结点在x的左子树之中。二叉搜索树一定是完全二叉树。二叉搜索树一定是满二叉树。Question2从空二叉树开始，严格按照二叉搜索树的插入算法（不进行旋转平衡），逐个插入关键码{18,73,10,5,68,99,27,41,51,32,25}构造出一棵二叉搜索树，对该二叉搜索树按照前序遍历得到的序列为（每两个元素之间用一个空格隔开）AnswerforQuestion2Question3下列关于堆的说法正确的有堆一定是满二叉树。堆一定是完全二叉树。最小堆中，最下面一层最靠右的结点一定是权值最大的结点。最小堆中，某个结点左子树中最大的结点可能比右子树中最小的结点小。Question4对于如下图所示的最大堆，删除掉最大的元素后，堆的后序遍历结果是AnswerforQuestion4Question5一组包含不同权的字母已经对应好Huffman编码，如果某一个字母对应编码001，下面说法正确的有建好的Huffman树至少包含4个叶结点。以000开头的代码不可能对应任何字母。以001开头的编码不可能对应其他字母。编码0和00可能对应于其他字母。Question6请阅读下面一段代码while(!aStack.empty()||pointer){?while(pointer!=NULL){//1号访问点element.pointer=pointer;element.tag=Left;aStack.push(element);pointer=pointer-leftchild();}element=aStack.top();aStack.pop();pointer=element.pointer;if(element.tag==Left){//2号访问点element.tag=Right;aStack.push(element);pointer=pointer-rightchild();}else{//3号访问点pointer=NULL;}}若此段代码的作用是用来进行中序遍历，那么应该在几号访问点进行访问？（只需要填写数字）AnswerforQuestion6