湖北工程学院软件工程专业大二数据结构期中小考试文档格式.docx

湖北工程学院软件工程专业大二数据结构期中小考试文档格式.docx

《湖北工程学院软件工程专业大二数据结构期中小考试文档格式.docx》由会员分享，可在线阅读，更多相关《湖北工程学院软件工程专业大二数据结构期中小考试文档格式.docx（15页珍藏版）》请在冰点文库上搜索。

6.某程序的时间复杂度为3n+nlog2n+n^2+8,其数量级表示为（）[单选题]*

A．O（n）

B．O（nlog2n）

C．O（n^2）（正确答案）

D．O（log2n）

7.以下数据结构中哪一个是非线性结构？

（）[单选题]*

A.队列

B.栈

C.线性表

D.二叉树（正确答案）

8.设顺序表有9个元素，则在第3个元素前插入一个元素所需移动元素的个数为（）[单选题]*

A.5

B.6

C.7（正确答案）

D.9

9.线性表采用链式存储结构时，要求内存中可用存储单元的地址（）[单选题]*

A.必须是连续的

B.必须是部分连续的

C.一定是不连续的

D.连续和不连续都可以（正确答案）

10.线性表是具有相同数据类型的n个（）的有限序列[单选题]*

A.数据项

B.数据元素（正确答案）

C.表元素

D.字符

11.在一个具有n个结点的有序单链表中插入一个新结点并仍然保持有序的时间复杂度是（）[单选题]*

A.O

（1）

B.O（n）（正确答案）

C.O（n^2）

D.O（nlog2n）

12.用链接方式存储的队列，在进行插入运算时（）[单选题]*

A.仅修改头指针

B.头、尾指针都要修改

C.仅修改尾指针（正确答案）

D.头、尾指针可能都要修改

13.在长度为n的顺序表中删除第i个元素（1≤i≤n）时，元素移动的次数为（）[单选题]*

A.n-i+1

B.i

C.i+1

D.n-i（正确答案）

14.若带头结点的单链表的头指针为head，则该链表为空的判定条件是（）[单选题]*

A.head==NULL

B.head->

next==NULL（正确答案）

C.head!

=NULL

D.head->

next==head

15.已知栈的最大容量为4。

若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行,则可能出现的出栈序列为（）[单选题]*

A.5，4，3，2，1，6

B.2，3，5，6，1，4

C.3，2，5，4，1，6（正确答案）

D.1，4，6，5，2，3

16.若某线性表中最常用的操作是取第i个元素和找第i个元素的前趋元素，则采用（）存储方式最节省时间[单选题]*

A.单链表

B.双链表

C.单向循环

D.顺序表（正确答案）

17.对一个算法的评价，不包括如下（）方面的内容[单选题]*

A．健壮性和可读性

B．并行性（正确答案）

C．正确性

D．时空复杂度

18.队列的删除操作是在（）进行[单选题]*

A．队首（正确答案）

B．队尾

C．队前

D．对后

19.计算机识别、存储和加工处理的对象被统称为（）[单选题]*

A.数据（正确答案）

B.数据元素

C.数据结构

D.数据类型

20.串是任意有限个（）[单选题]*

A.符号构成的序列

B.符号构成的集合

C.字符构成的序列（正确答案）

D.字符构成的集合

21.如果以链表作为栈的存储结构，则退栈操作时（）[单选题]*

A.必须判别栈是否满

B.对栈不作任何判别

C.必须判别栈是否空（正确答案）

D.判别栈元素的类型

22.队列的插入操作是在（）进行[单选题]*

A．队首

B．队尾（正确答案）

23.一棵具有5层满二叉树中节点总数为（）[单选题]*

A、31（正确答案）

B、32

C、33

D、16

24.广义表是线性表的推广，它们之间的区别在于（）[单选题]*

A．能否使用子表（正确答案）

B．能否使用原子项

C．表的长度

D．是否能为空

25.与线性表相比，串的插入和删除操作的特点是（）[单选题]*

A.通常以串整体作为操作对象（正确答案）

B.需要更多的辅助空间

C.算法的时间复杂度较高

D.涉及移动的元素更多

26.假设带头结点的单向循环链表的头指针为head,则该链表为空的判定条件是（）[单选题]*

A.head==NULL

B.head–>

next==NULL

C.head!

D.head–>

next==head（正确答案）

27.在单链表中，指针p指向值为x的结点，能实现“删除x的后继”的语句是（）[单选题]*

A.p=p->

next;

B.p=p->

next->

C.p->

next=p;

D.p->

next=p->

（正确答案）

28.一个栈的入栈序列是a，b，c，d，e，则栈的输出序列不可能是（）[单选题]*

A.dceab（正确答案）

B.decba

C.edcba

D.abcde

29.若进栈序列为a，b，c，进栈过程中允许出栈，则以下（）是不可能得到的出栈序列[单选题]*

A.a,b,c

B.b,a,c

C.c,a,b（正确答案）

D.c,b,a

30.若进栈序列为1，2，3，4，进栈过程中允许出栈，则可能的出栈序列是（）[单选题]*

A.2，4，1，3

B.3，1，4，2

C.3，4，1，2

D.1，2，3，4（正确答案）

31.设有一个栈，按A、B、C、D的顺序进栈，则可能为出栈序列的是（）[单选题]*

A.DCBA（正确答案）

B.CDAB

C.DBAC

D.DCAB

32.一个最多能容纳m个元素的顺序存储循环队列Q，其头尾指针分别为front和rear，则判定该队列为满的条件是（）[单选题]*

A.（Q.rear+1）%m==Q.front（正确答案）

B.Q.front==Q.rear

C.Q.rear+1==Q.front

D.（Q.front+1）%m==Q.rear

33.设数组Data[m]作为循环队列SQ的存储空间，front为队头指针，rear为队尾指针，则执行出队操作的语句为（）[单选题]*

A.front=front+1

B.front=（front+1）%m（正确答案）

C.rear=（rear+1）%m

D.front=（front+1）%（m+1）

34.60.广义表A：

（（），（a），（b，（c，d）））的深度为（）.[填空题]

_________________________________（答案：

undefined）

35.假设以数组A[n]存放循环队列的元素，其头、尾指针分别为front和rear。

若设定尾指针指向队列中的队尾元素，头指针指向队列中队头元素的前一个位置，则当前存于队列中的元素个数为（）[单选题]*

A.（rear-front-1）％n

B.（rear-front）％n

C.（front-rear+1）％n

D.（rear-front+n）％n（正确答案）

36.若用一个大小为6的一维数组来实现循环队列，且当前rear和front的值分别为0和3。

当从队里中删除一个元素，再加入两个元素后，rear和front的值分别是（）[单选题]*

A.1和5

B.5和1

C.2和4

D.4和2（正确答案）

37.两个字符串相等的条件是（）[单选题]*

A.串的长度相等

B.含有相同的字符集

C.都是非空串

D.串的长度相等且对应的字符相同（正确答案）

38.如下陈述中正确的是（）[单选题]*

A．串是一种特殊的线性表（正确答案）

B．串的长度必须大于零

C．串中元素只能是字母

D．空串就是空格串

39.一棵含18个结点的二叉树的高度至少为（）[单选题]*

A.3

B.4

C.5（正确答案）

D.6

40.将一棵有40个结点的完全二叉树从上到下，从左到右依次对结点进行编号，根结点的编号为1，则编号为15的结点的左孩子的编号为（）[单选题]*

A.16

B.30（正确答案）

C.31

D.32

41.在程序的执行过程中，对实现函数的递归调用应该借助于（）结构[单选题]*

A.线性表

B.栈（正确答案）

C.队列

D.树

42.具有100个结点的完全二叉树的深度为（）[单选题]*

A.6

B.7（正确答案）

C.8

43.已知二叉树的先序遍历序列为ABDECF，中序遍历序列为DBEAFC，则后序遍历序列为（）[单选题]*

A．DEBAFC

B．DEFBCA

C．DEBCFA

D．DEBFCA（正确答案）

44.如果在数据结构中每个数据元素只可能有一个直接前驱，但可以有多个直接后继，则该结构是（）[单选题]*

A.栈

B.队列

C.树（正确答案）

D.图

45.已知一棵含50个结点的二叉树中只有一个叶子结点，则该树中度为1的结点个数为（）[单选题]*

A.0

B.1

C.48

D.49（正确答案）

46.具有100个结点的完全二叉树，其中含有（）个度为1的结点[单选题]*

A.1（正确答案）

B.0

C.2

D.不确定

47.已知二叉树的先序遍历序列为ABCD，中序遍历序列为BCDA，则后序遍历序列为（）[单选题]*

A．ABCD

B．BCDA

C．CDBA

D．DCBA（正确答案）

48.对一棵有100个结点的完全二叉树按层序编号，则编号为49的结点，它的左孩子的编号为（）[单选题]*

A.99

B.98（正确答案）

C.97

D.50

49.有m个叶子结点的哈夫曼树，其结点总数是（）[单选题]*

A.2m-1（正确答案）

B.2m

C.2m+1

D.2（m+1）

50.广义表中元素分为（）[单选题]*

A．原子元素

B．表元素

C．原子元素和表元素（正确答案）

D．任意元素

51.广义表A=（（），（a），（b，（c，d）））的长度为（）[单选题]*

A．2

B．3（正确答案）

C．4

D．5

52.一棵深度为6的二叉树至多有（）个结点[单选题]*

A．64

B．32

C．31（正确答案）

D．63

53.将含100个结点的完全二叉树从根第一层开始，每层上从左到右依次对结点编号，根结点的编号为1，编号为49的结点X的双亲编号为（）[单选题]*

A．24（正确答案）

B．25

C．23

D．无法确定

54.链表适用于（）查找[单选题]*

A．顺序（正确答案）

B．二分法

C．顺序,也能二分法

D．随机

55.在顺序表中，只要知道（），就可在相同时间内求出任一结点的存储地址[单选题]*

A．基地址

B．结点大小

C．向量大小

D．基地址和结点大小（正确答案）

56.线性表的顺序存储结构是一种（）的存储结构[单选题]*

A．随机存取（正确答案）

B．顺序存取

C．索引存取

D．散列存取

57.数据结构在计算机内存储器中的表示是指（）[单选题]*

A.数据结构

B.数据元素之间的关系

C.数据的逻辑结构

D.数据的物理存储结构（正确答案）

58.对二叉树的结点从1开始编号，要求每个结点的编号大于其左孩子（如果有的话）的编号，而小于其右（孩子如果有的话）的编号，则可以采用（B）次序的遍历实现二叉树的结点编号[单选题]*

A.先序

B.中序（正确答案）

C.后序

D.层次遍历

59.（）是一棵满二叉树[单选题]*

A．二叉排序树

B．深度为5有31个结点的二叉树（正确答案）

C．有15个结点的完全二叉树

D．哈夫曼（Huffman）树

60.某二叉树结点的中序序列为BDAECF,后序序列为DBEFCA,则该二叉树对应的森林包括（）棵树[单选题]*

A.1

B.2

C.3（正确答案）

D.4