数据结构栈、队列、树单元测试40题

数据结构栈、队列、树单元测试40题

您的姓名：［填空题］*

L当利用大小为n的数组顺序存储一个队列时，该队列的最大长度为()。［单选题］

*

A、n-2

B、n-1(正确答案)

C、n

D、n+l

2.设链栈中结点的结构为(data,link),且top是指向栈顶的指针。若想在链栈的

栈顶插入一个由指针s所指的结点，则应执行()操作。［单选题］*

A、top->link=s;

B、s->link=top->link;top->link=s;

C、s->link=top;top=s;

D、s->link=top;top=top->link;

3.设循环队列的存储空间为Q(l：m),初始状态为front=rear=m。现经过一系列入队

与退队运算后，front=2(),rear=15,现要在该循环队列中寻找最小值的元素，最坏

情况下需要比较的次数为()o［单选题］*

A、m-6

B、m-5

C、6

D、5

4.设循环队歹Ij的结构是typedefstruct{DataTypedatafMaxSize］;intfront,rear;}

Queue;若有一个Queue类型的队列Q,循环队列少用一个元素空间，试问判断队

列满的条件应为()。［单选题］*

A、Q.front==Q.rear;

B、Q.front-Q.rear==MaxSize;

C、Q.front+Q.rear=MaxSize;

D、Q.front==(Q.rear+1)%MaxSize;假答案)

5.设有一个递归算法如下intfact(intn){if(n<=0)return1;elsereturnn*fact(n-

1);}则计算fact(n)需要函数内部调用的次数为()次。［单选题］*

A、n(正确答案)

B、n+1

C、n+2

D、n-1

6.下列叙述正确的是()。［单选题］*

A、双向链表是二叉树的链式存储结构

B、非线性结构只能采用链式存储结构

C、有的非线性结构也可以采用顺序存储结构

D、循环队列属于队列的链式存储结构

7.按照“后进先出”原则组织数据的数据结构是()。［单选题］*

A、队列

B、栈

C、双向链表

D、二叉树

8.递归调用时系统需要利用一个()来实现数据的传递和控制的转移。［单选题］*

A、队列

B、优先级队列

C、双端队列

D、栈（正确答案）

9.下列对队列的叙述正确的是（）o［单选题］*

A、队列属于非线性表

B、队列按“先进后出”原则组织数据

C、队列在队尾删除数据

D、队列按“先进先出”原则组织数据

1（）.下列关于栈的描述正确的是（）o［单选题］*

A、在栈中只能插入元素而不能删除元素

B、在栈中只能删除元素而不能插入元素

C、栈是特殊的线性表，只能在一端插入或删除元素

D、栈是特殊的线性表，只能在一端插入元素，而在另一端删除元素

11.下列数据结果中，能够按照“先进后出”原则存取数据的是（）。［单选题］*

A、循环队列

B、栈（正确答案）

C、队列

D、二叉树

12.下列叙述中正确的是（）。［单选题］*

A、栈是一种先进先出的线性表

B、队列是一种后进先出的线性表

C、栈和队列都是非线性结构

D、以上三种说法都不对

13.一个栈的初始状态为空。现将元素L2.3.45A.B.C.D.E依次入栈，然后再依次

出栈，则元素出栈的顺序是（）o［单选题］*

A、12345ABCDE

B、EDCBA54321

C、ABCDE12345

D、54321EDCBA

14.当利用大小为n的数组顺序存储一个栈时，假定用top==n表示栈空，则向这个

栈插入一个元素时，首先应执行（）语句修改top指针。［单选题］*

A、top++;

B.top-;

C、top=0;

D、top;

15.假定一个顺序存储的循环队列的队头和队尾指针分别为front和rear,循环队列

少用一个元素空间，则判断队空的条件为（）。［单选题］*

A、front+l==rear

B、rear+1==front

C、front==0

D、front==rear（正确答案）

16.若让元素1,2,3依次进栈，则出栈次序不可能出现（）种情况。［单选题］*

A、3,2,1

B、2,1,3

C、3,1,2

D、1,3,2

17.设循环队歹（J的结构是constintMaxSize=10（）;typedefintDataType;typedefstruct

{DataTypedatafMaxSize］;intfront,rear;}Queue;若有一个Queue类型的队列Q,

循环队列少用一个元素空间，则应用（）表达式计算队列元素的个数。［单选题］*

A、（Q.rear-Q.front+MaxSize）%MaxSize;

B、Q.rear-Q.front+1;

C、Q.rear-Q.front-1;

D、Q.rear-Qfront;

18.设栈的顺序存储空间为S（0:49）,栈底指针bottom=49,栈顶指针top=3（）（指向

栈顶元素），则栈中的元素个数是（）。［单选题］*

A、30

B、19

C、20

D、29

19.下列叙述正确的是（）o［单选题］*

A、带链队列的存储空间可以不连续，且队头指针可以大于也可以小于队尾指针

（正确答案）

B、带链队列的存储空间可以不连续，但队头指针必须小于队尾指针

C、带链队列的存储空间可以不连续，但队头指针必须大于队尾指针

20.下列叙述中正确的是（）。［单选题］*

A、循环队列有队头和队尾两个指针，因此，循环队列是非线性结构

B、在循环队列中，只需要队头指针就能反映队列中元素的动态变化情况

C、在循环队列中，只需要队尾指针就能反映队列中元素的动态变化情况

D、循环队列中元素的个数是由队头指针和队尾指针共同决定

21.下列叙述中正确的是（）o［单选题］*

A、循环链表是循环队列的链式存储结构

B、栈与队列都只能顺序存储

C、循环队列是队列的顺序存储结构

22.利用3,6,8,12这四个值作为叶子结点的权，生成一棵哈夫曼树，该树的带权路

径长度为（）。［单选题］*

A、55（正确答案）

B、29

C、58

D、38

23.某二叉树的前序序列为ABCDEFG,中序序歹为DCBAEFG,该二叉树的深度

（根结点在第1层）为（）o［单选题］*

A、4（正确答案）

B、2

C、3

D、5

24.某二叉树共有7个结点，其中叶子结点只有1个，则该二叉树的深度为（）

（假设根结点在第1层）。［单选题］*

A、3

B、4

C、6

D、7

25.一棵二叉树中共有70个叶子结点与8（）个度为1的结点，则该二叉树中的总结

点数为0o［单选题］*

A、219角答案）

B、221

C、229

D、231

26.在一棵高度为h+1的完全二叉树中，所含结点个数不小于（）。［单选题］*

A、2的h-1次方

B、2的h+1次方

C、2的h次方-1

D、2的h次方

27.树中所有结点的度之和等于所有结点数加（）。［单选题］*

A、0

B、1

C、

D、2

28.在一棵具有n个结点的二叉树的第i层上（假定根结点为第1层），最多具有（）个

结点。［单选题］*

A、2的i次方

B、2的i+1次方

C、2的i-l次方

D、2的n次方

29.在一棵树中，（）没有前驱结点。［单选题］*

A、树枝结点

B、叶子结点

c、树根结点正确答案）

D、空结点

30.在一棵完全二叉树中，若编号为i的结点存在左孩子,则左孩子结点的编号为

（）。假定树根结点的编号为1。［单选题］*

A、2i（正确答案）

B、2i-l

C、2i+l

D、2i+2

w

31.对如下二叉树进行后序遍历的结果为（）o回LUL±J［单选题］

*

A、ABCDEF

B、DBEAFC

C、ABDECF

D、DEBFCA（正确答案）

F"

一

0

—Vn

S［

32.对下列二叉树进行中序遍历的结果是（）。［单选题］

*

A、ACBDFEG：正今

B、ACBDFGE

C、ABDCGEF

D、FCADBEG

33.某二叉树有5个度为2的结点，则该二叉树中的叶子结点数是（）o［单选题］

*

A、10

B、8

C、6

D、4

34.某二叉树中有n个叶子结点，则该二叉树中度为2的结点数为（）。［单选题］

*

A、n/2

B、n+1

C、2n

D、n-1E确答案）

35.设某二叉树的前序序列为ABC,中序序列为CBA,则该二叉树的后序序列为

（）o［单选题］*

A、CAB

B、CBA

C、ABC

D、BCA

36.下列关于二叉树的叙述中，正确的是（）。［单选题］*

A、叶子结点总是比度为2的结点少一个

B、叶子结点总是比度为2的结点多一个

c、叶子结点数是度为2的结点数的两倍

D、度为2的结点数是度为1的结点数的两倍

37.一棵具有35个结点的完全二叉树的高度为（）。假定空树的高度为-lo［单选题］

A、5

B、6

C、7

D、8

38.在一棵具有n个结点的二叉树中，所有结点的空子树个数等于（）。［单选题］*

A、n

B、n