08计算机班--数据结构期末试题

导读:安徽美卡学院2009-2010学年第一学期08级计算机信息管理班数据结构导论,期末试题班级__________姓名__________分数__________,1.数据的不可分割的最小标识单位是()A.数据项B.数据记录C.数据元素D.数据,2.关于存储相同数据元素的说法中正确的是()A.顺序存储比链式存储少占空间B.顺,某数据元素的地址为LOC+50L,16.在数据结构中,数据的存储结构有顺

08计算机班--数据结构期末试题

安徽美卡学院2009-2010学年第一学期08级计算机信息管理班数据结构导论

期 末 试 题 班级__________ 姓名__________ 分数______________ 一、单项选择题(本大题共15小题,每小题2分,共30分) 在每小题列出的四个备选项中只有一个是符合题目要求的,请将其代码填写在题后的括号内。错选、多选或未选均无分。 1.数据的不可分割的最小标识单位是( ) A.数据项 B.数据记录 C.数据元素 D.数据变量

2 .关于存储相同数据元素的说法中正确的是( ) A .顺序存储比链式存储少占空间 B. 顺序存储比链式存储多占空间

C. 顺序存储和链式存储都要求占用整块存储空间 D. 链式存储比顺序存储难于扩充空间

3.若线性表最常用的操作是存取第i个元素及其前趋的值,那么最节省操作时间的存储方式是( ) A.单链表 B.双链表 C.单循环链表 D.顺序表

4.设单链表中指针p指向结点A,要删除A之后的结点(若存在),则修改指针的操作为( ) A.p—>next=p—>next—>next B.p=p—>next C.p=p—>next—>next D.p—>next=p

5.向一个栈顶指针为hs的链栈中插入一个*s结点时,应执行的操作为( ) A.hs—>next=s; B.s—>next=hs;hs=s;

C.s—>next=hs—>next;hs—>next=s; D.s—>next=hs;hs=hs—>next;

1

安徽美卡学院2009-2010学年第一学期08级计算机信息管理班数据结构导论

6.设循环队列的元素存放在一维数组Q[0‥30]中,队列非空时,9.对一棵有100个结点的完全二叉树按层序编号,则编号为49的front指示队头元素的前一个位置,rear指示队尾元素。如果队列中元素的个数为11,front的值为25,则rear应指向的元素是( ) A.Q[4] B.Q[5] C.Q[14] D.Q[15]

7.定义二维数组A[1‥8,0‥10],起始地址为LOC,每个元素占2L个存储单元,在以行序为主序的存储方式下,某数据元素的地址为LOC+50L,则在以列序为主序的存储方式下,该元素的存储地址为( ) A.LOC+28L B.LOC+36L C.LOC+50L D.LOC+52L

8.具有n个结点的二叉树,拥有指向孩子结点的分支数目是( ) A.n-1 B.n C.n+1 D.2n

结点,它的左孩子的编号为( ) A.99 B.98 C.97 D.50

10.有m个叶子结点的哈夫曼树,其结点总数是( A.2m-1 B.2m C.2m+1 D.2(m+1)

11.有n个结点的无向图的边数最多为( ) A.n+1 B.n(n-1)/2 C.n(n+1) D.2n(n+1)

12.设图的邻接矩阵为,则该图为( )A.有向图 B.无向图 C.强连通图 D.完全图

2

安徽美卡学院2009-2010学年第一学期08级计算机信息管理班数据结构导论

13.二分查找算法的时间复杂度是( ) A. O(n2

) B. O(nlog2n) C. O(n) D. O(log2n)

14.已知8个元素(34,76,45,18,26,54,92,65),按照依次

插入结点的方法生成一棵二叉排序树,则该树的深度为( ) A.4 B.5 C.6 D.7

15 .设有一组初始关键字值序列为(49,81,55,36,44,88)则利用快速排序的方法,以第一个关键字值为基准得到的一次划分为( )

A .36 , 44 , 49 , 55 , 81 , 88 B. 44 , 36 , 49 , 55 , 81 , 88 C. 44 , 36 , 49 , 81 , 55 ,88 D. 44 , 36 , 49 , 55 , 88 , 81

二、填空题(本大题共13小题,每小题2分,共26分) 请在每小题的空格中填上正确答案。错填、不填均无分。

16.在数据结构中,数据的存储结构有顺序存储方式、链式存储方式、_________和散列存储方式等四种。

17.对一棵深度为10的满二叉树按层编号,则编号为51的结点,它的双亲结点编号为________。

18.在双链表中,存储一个结点有三个域,一个是数据域,另两个

是指针域,分别指向_________和_________。 19.在有n个元素的链队列中,入队和出队操作的时间复杂度分别为_________和_________。

20.在栈结构中,允许插入的一端称为_________;在队列结构中,允许插入的一端称为_________。

21.在循环队列中,存储空间为0~n-1。设队头指针front指向队头元素前一个空闲元素,队尾指针指向队尾元素,那么其队空标志为rear=front,队满标志为_________。

22.深度为k的二叉树至多有_________个结点,最少有_________个结点。

23.在无向图G的邻接矩阵A中,若A[i][j]等于0,则A[j][i]等于________。

3

安徽美卡学院2009-2010学年第一学期08级计算机信息管理班数据结构导论

24.在一个具有n个结点的单链表中查找其值等于x的结点时,在查找成功的情况下,需平均比较_________个元素结点。 25.假定对线性表R[0…59]进行分块检索,共分为10块,每块长度等于6。若检索索引表和块均用顺序检索的方法,则检索每一个元素的平均检索长度为_________。 26 .二分查找的时间复杂度为 _______ 。

27.在插入排序、冒泡排序、快速排序、归并排序等排序算法中,占用辅助空间最多的是_________。

28.对n个元素进行冒泡排序时,最少的比较次数为________。 三、应用题(本大题共5小题,每小题6分,共30分) 29.已知一棵二叉树的前序序列是ABCDEFG,中序序列是CBDAEGF。请构造出该二叉树,并给出该二叉树的后序序列。

30.将题30图所示的由三棵树组成的森林转化为一棵二叉树。 题30图

4

安徽美卡学院2009-2010学年第一学期08级计算机信息管理班数据结构导论

31.已知某图的邻接表存储结构如题31图所示:

题31图

(1)画出该图。

(2)根据该邻接表从顶点A出发,分别写出按深度优先搜索法和广度优先搜索法进行遍历的结点序列。

32.假定采用H(k)=kmod7计算散列地址,引用线性探测的开放定址法解决冲突,试在0~6的散列地址空间中,对关键字序列(38,25,74,63,52,48)构造散列表,并求出等概率情况下查找成功的平均查找长度。

33.用快速排序法对数据序列(49,38,65,97,16,53,134,27,39)进行排序,写出其第一趟排序的全过程。

5

安徽美卡学院2009-2010学年第一学期08级计算机信息管理班数据结构导论

四、算法设计题(本大题共2小题,每小题7分,共14分) 34.完善下列折半插入排序算法。

Voidbinasort(structnoder[MAXSIZE],int n) {for(i=2;i<=n;i++){

_________; else{

level++;

while(root—>key != p—>key) r[0]=r[i];low=1;high=i-1; while(low <= high){ mid=_________;

if(r[0].key_______ )

high=_________; else

low=_________;

}

for(j=i-1;j>=low;j--) _________;

r[low]=r[0];

}

}

35.下列算法的功能是求出指定结点在给定的二叉排序树中所在的层次。请完善该算法。 Voidlevel(BSTreeroot,p) { intlevel=0; if(!root)

{

if(root—>key_____) _________; else

_________; level++; }

_________; }

}

6

五星文库wxphp.com包含总结汇报、IT计算机、党团工作、工作范文、计划方案、文档下载、教学研究以及08计算机班--数据结构期末试题等内容。

本文共2页12