数据结构试卷11.doc

《数据结构试卷11.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、安庆职业技术学院电子信息系2010-2011学年度第一学期期末考试《数据结构》试卷（B卷）命题教师:刘震题号一二三四总分统分人得分分值得分阅卷人一选择题(共10小题，每题2分，共计20分)1．下列时间复杂度中最坏的是____D__。A.O(1)B.O(n)C.O(log2n)D.O(n2)2．算法能正确地实现预定功能的特性称为___A__________。A.正确性B.易读性C.健壮D.高效率在3.数据元素是数据的基本单位，其内______C_______数据项。A.只能包括一个B.不包含C.可以包含多个D.必须包含多个4.在长为n的顺序表中，删除第i个元素(1≤i≤n+1)需要向前移动（

2、A）个元素。A.n-iB.n-i+1C.n-i-1D.i5.一个队的入队顺序是1、2、3、4、5，则此队的出队顺序为（D）。A.5、4、3、2、1B.4、5、3、2、1C.4、3、5、1、2D.1、2、3、4、56.栈是一种特殊的线性表，其特殊性表现在（B）。A.可以顺序存储B.只能从端点进行插入和删除C.可以链式存储D.可以在任何位置进行插入和删除7.一棵二叉树中，第k层上最多有（D）个结点。A.2kB.2k-1C.2kD.2k-18.按照二叉树的定义，具有3个结点的二叉树有（C）种不同形态。A.    3B.4C.5D.69.n个顶点的有向图中最多有（B）条弧。A.n(n-1)/2B.

3、n(n-1)C.n(n+1)D.n(n+1)/210.有向图中，所有顶点入度和是所有顶点出度和的（B）倍。A.0.5B.1C.2D.411.一棵完全二叉树的顺序存储方式中，若编号n的结点有右孩子，则其左孩子的编号为（A）。A.2n+1B.2n-1C.nD.n/212.若某线性表中最常用的操作是随机访问元素，则应采用（D）存储方式。A.单链表B.双链表C.单向循环链表D.顺序表13.连通分量是___A____的极大连通子图。A.无向图B.有向图C.树D.图14.如果从无向图的任一顶点出发进行一次深度优先搜索即可访问所有顶点，则该图一定是__B_____。A.完全图B.连通图C.有回路D.一棵

4、树15.冒泡排序的方法是_______A_________的排序方法。A.稳定B.不稳定C.外部D.选择16.排序是根据________B________的大小重新安排各元素的顺序。A.数组B.关键字C.元素D.结点17.对线性表进行折半查找时，要求线性表必须__B____。A.关键值有序的链表B.关键值有序的顺序表C.链表但关键值不一定有序D.顺序表但关键值不一定有序18．记录中的各个数据项的类型______C_______。A.不能相同B.必须相同C.不必相同D.不确定19.设森林T中有三棵树，第一、二、三棵数的结点个数分别为n1、n2、n3，那么将森林转换成二叉树后，其根结点的右子树

5、上有__B___个结点。A.n1-1B.n2+n3C.n1+n2+n3D.n120.某二叉树的前序遍历结点访问顺序为ABDGCEFH，中序遍历结点访问顺序为DGBAECHF，则其后序遍历结点访问顺序为__D___。A.BDGCEFHAB.GDBECFHAC.BDGAECHFD.GDBEHFCA分值得分阅卷人二、  判断题（共10小题，每题1分，共计10分）（对）1、满二叉树一定是完全二叉树。（错）2、二叉树就是度为2的树。（对）3、存在这样的二叉树，其后序遍历与中序遍历得到的访问序列相同。（错）4、链式存储的线性表可以实现随机存取。（错）5、由空格组成的串叫空串。（对）6、在赋权有向无环图

6、中，可能有多条关键路径。（对）7、栈是一种后进先出的线性结构。（对）8、选择排序是不稳定的。（错）9、在线性结构的顺序存储结构中，逻辑上相邻的两个元素在物理位置上不一定相邻。（错）10、二叉树按某种顺序线索化后，任一结点均有指向其直接前驱和直接后继的线索。分值得分阅卷人三、  填空题（共15空，每空2分，共计30分）1、算法的基本特征为有穷性、确定性、有效性、输入和输出；2、在单链表中，若删除指针p所指结点的直接后继，则需要执行下列三条语句：q=p->next；p->next=q->next或p->next=p->next->next；free（q）；3、在有头结点的单循环链表L中，指针p

7、所指结点是最后一个结点的条件是:p->next==L。4、栈是一种受限制的线性表，也叫FILO结构，FILO的含义是:先进后出。5、对于队列，只能在队尾插入元素，只能在队头删除元素。6、图的遍历方式通常有深度优先遍历和广度优先遍历两种。7、在具有n个结点的按结点数据有序的线性单链中插入一个新结点并使链表依然有序的操作的时间复杂度是Ｏ(n)。8、对于顺序栈，在执行进栈操作之前要先判断栈是否栈满,在执行出栈操作之前要先判断栈