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

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的容量至少应该是

_____________。

4

6

3

8

Question4

如果用两个栈来模拟一个队列，请问以下哪两个栈最可能高效地模拟了一个队列？（假设元素入

队顺序为a,b,c,d,e,f,g,h,i,j，选项表示的是栈的状态）

Question5

在具有n个单元的顺序存储的循环队列中，假定front和rear分别为队头指针和队尾指针，则判

断队满的条件为

rear％n+1=front

front％n-1=rear

rear％n-1=front

front％n+1=rear

字符串

Question1

若字符串s=”algorithm”，则其子串个数为：

AnswerforQuestion1

Question2

设有字符串变量StringA＝“”，B＝“MULE”，C＝“OLD”，D＝“MY”;请计算下列表达式：

(1)D+C+B

(2)B.substr(3，2)

(3)A.strlength()

注：答案用空格分隔，答案不要加引号

AnswerforQuestion2

Question3

一个文本串可用事先给定的字母映射表进行加密。例如，设字母映射表为：

abcdefghijklmnopqrstuvwxyz

ngzqtcobmuhelkpdawxfyivrsj

比如字符串比如字符串被加密为被加密为。

则字符串“algorithm”，被加密为________________（答案不需要加引号）。

AnswerforQuestion3

Question4

S=“S1S2…Sn”是一个长为n的字符串，存放在一个数组中，编程序将S改造之后输出。

（1）将S的所有第偶数个字符按照其原来的下标从大到小的次序放在S的后半部分；

（2）将S的所有第奇数个字符按照其原来的下标从小到大的次序放在S的前半部分；

例如：S=‘ABCDEFGHIJKL’，则改造后的S为‘ACEGIKLJHFDB’。

则S=’algorithm’,改造后为____________（答案不需要加引号）。

AnswerforQuestion4

Question5

在字符{A,C,G,T}组成的DNA序列中，A和T、C和G是互补对。判断一个DNA序列中是否存在

互补回文串（例如，ATCATGAT的补串是TAGTACTA，与原串形成互补回文串）。

下面DNA序列中存在互补回文串的是：

TGCAACGT

AGCTAGCT

AATTAATT

CATGGTAC

二叉树基础

Question1

一棵有511个结点的完全二叉树的高度为多少？（独根树高度为1）

AnswerforQuestion1

Question2

在一棵非空二叉树中，若度为0的结点的个