数据结构与算法小测习题.docx

QLLD数据结构与算法小测栈与队列Question 1以下循环队列的实现方式中，长度为n的队列，所能容纳的元素个数也为n的有只用front和rear两个指针标记队列的头和尾，front为实指，rear为虚指用front和rear两个指针标记队列的头和尾，并用整型变量len记录队列元素数只用front和rear两个指针标记队列的头和尾，两个指针均为虚指用front和rear两个指针标记队列的头和尾，并用布尔型变量empty记录队列是否为空Question 2依次读入数据元素序列a，b，c，d，e，f，g 进栈，每进一个元素，机器可要求下一个元素进栈或弹栈，如此进行，则栈空时弹出的元素构成的序列可以是以下哪些序列c，d，a，b，e，f，gc，d，b，e，f，a，ge，f，d，g，b，c，aa，c，e，f，g，d，bQuestion 3设栈S 和队列Q 的初始状态为空，元素e1，e2，e3，e4，e5和e6依次通过栈S，一个元素出栈后即进队列Q，若6 个元素出队的序列是e2，e4，e3，e6，e5，e1则栈S的容量至少应该是_。4638Question 4如果用两个栈来模拟一个队列，请问以下哪两个栈最可能高效地模拟了一个队列？（假设元素入队顺序为a,b,c,d,e,f,g,h,i,j，选项表示的是栈的状态）Question 5在具有n个单元的顺序存储的循环队列中，假定front和rear分别为队头指针和队尾指针，则判断队满的条件为rearn+1=frontfrontn-1=rearrearn-1=frontfrontn+1=rear字符串Question 1若字符串s=”algorithm”，则其子串个数为：Answer for Question 1Question 2设有字符串变量String A “”，B“MULE”，C“OLD”，D“MY” ; 请计算下列表达式：(1) D+C+B(2) B.substr(3，2)(3) A.strlength()注：答案用空格分隔，答案不要加引号Answer for Question 2Question 3一个文本串可用事先给定的字母映射表进行加密。例如，设字母映射表为：abcdefghijklmnopqrstuvwxyzngzqtcobmuhelkpdawxfyivrsj比如字符串encrypt被加密为tkzwsdf。则字符串 “algorithm”，被加密为_（答案不需要加引号）。Answer for Question 3Question 4S=“S1S2Sn”是一个长为n的字符串，存放在一个数组中，编程序将S改造之后输出。（1）将S的所有第偶数个字符按照其原来的下标从大到小的次序放在S的后半部分；（2）将S的所有第奇数个字符按照其原来的下标从小到大的次序放在S的前半部分；例如：S=ABCDEFGHIJKL，则改造后的S为ACEGIKLJHFDB。则 S=algorithm, 改造后为_（答案不需要加引号）。Answer for Question 4Question 5在字符A, C, G, T组成的DNA序列中，A和T、C和G是互补对。判断一个DNA序列中是否存在互补回文串（例如，ATCATGAT的补串是TAGTACTA，与原串形成互补回文串）。下面DNA序列中存在互补回文串的是：TGCAACGTAGCTAGCTAATTAATTCATGGTAC二叉树基础Question 1一棵有511个结点的完全二叉树的高度为多少？（独根树高度为1）Answer for Question 1Question 2在一棵非空二叉树中，若度为0的结点的个数n，度为2的结点个数为m，则有n=_。Answer for Question 2Question 3下列关于二叉树遍历的说法正确的有所有结点右子树为空的二叉树的前序和后序遍历顺序恰好一样。所有结点右子树为空的二叉树的中序和后序遍历顺序恰好一样。存在一棵非空二叉树，它的前序、中序和后序遍历都是一样的。所有结点右子树为空的二叉树的前序和中序遍历顺序恰好一样。Question 4已知一棵树的中序遍历为DBGEACF，后序遍历为DGEBFCA，求这棵树的前序遍历。（字母和字母之间不要有空格）Answer for Question 4Question 5请写出下面这棵二叉树的前序遍历（字母和字母之间不要有空格）Answer for Question 5二叉树应用Question 1下列关于二叉搜索树的说法正确的有二叉搜索树按照中序遍历将各结点打印出将各结点打印出来，将得到按照由小到大的排列。如果结点x的左子树有右子树，则存在某个结点的值介于结点x的值和x左儿子的值之间，并且这个结点在x的左子树之中。二叉搜索树一定是完全二叉树。二叉搜索树一定是满二叉树。Question 2从空二叉树开始，严格按照二叉搜索树的插入算法（不进行旋转平衡），逐个插入关键码18,73,10,5,68,99,27,41,51,32,25构造出一棵二叉搜索树，对该二叉搜索树按照前序遍历得到的序列为（每两个元素之间用一个空格隔开）Answer for Question 2Question 3下列关于堆的说法正确的有堆一定是满二叉树。堆一定是完全二叉树。最小堆中，最下面一层最靠右的结点一定是权值最大的结点。最小堆中，某个结点左子树中最大的结点可能比右子树中最小的结点小。Question 4对于如下图所示的最大堆，删除掉最大的元素后，堆的后序遍历结果是Answer for Question 4Question 5一组包含不同权的字母已经对应好Huffman编码，如果某一个字母对应编码001，下面说法正确的有建好的Huffman树至少包含4个叶结点。以000开头的代码不可能对应任何字母。以001开头的编码不可能对应其他字母。编码0和00可能对应于其他字母。Question 6请阅读下面一段代码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; aS