欢迎来到天天文库
浏览记录
ID:17097377
大小:96.50 KB
页数:13页
时间:2018-08-27
《2010-2011上期末试卷数据结构》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库。
1、装订线学院:专业:学号:姓名:教学班号:线封密云南农业大学2010—2011学年上学期期末考试数据结构试卷(A卷)(课程代码3111003)本试题满分100分,考试时间120分钟。题号一二三四五六七八总分得分阅卷人一.选择题。(每小题2分,共40分)1.组成数据的基本单位是()。(A)数据项(B)数据类型(C)数据元素(D)数据变量2.设数据结构A=(D,R),其中D={1,2,3,4},R={r},r={<1,2>,<2,3>,<3,4>,<4,1>},则数据结构A是()。(A)线性结构(B)树型结构(C)图型结构(D)集合3.数组
2、的逻辑结构不同于下列()的逻辑结构。(A)线性表(B)栈(C)队列(D)树4.二叉树中第i(i≥1)层上的结点数最多有()个。(A)2i(B)2i(C)2i-1(D)2i-15.设指针变量p指向单链表结点A,则删除结点A的后继结点B需要的操作为()。(A)p->next=p->next->next(B)p=p->next(C)p=p->next->next(D)p->next=p6.设栈S和队列Q的初始状态为空,元素E1、E2、E3、E4、E5和E6依次通过栈S,一个元素出栈后即进入队列Q,若6个元素出列的顺序为E2、E4、E3、E6
3、、E5和E1,则栈S的容量至少应该是()。(A)6(B)4(C)3(D)2第1页(共7页)7.将10阶对称矩阵压缩存储到一维数组A中,则数组A的长度最少为()。(A)100(B)40(C)55(D)808.设结点A有3个兄弟结点且结点B为结点A的双亲结点,则结点B的度数数为()。(A)3(B)4(C)5(D)19.根据二叉树的定义可知二叉树共有()种不同的形态。(A)4(B)5(C)6(D)710.设有以下四种排序方法,则()的空间复杂度最大。(A)冒泡排序(B)快速排序(C)堆排序(D)希尔排序11.下面关于线性表的叙述错误的是()
4、。(A)线性表采用顺序存储必须占用一片连续的存储空间(B)线性表采用链式存储不必占用一片连续的存储空间(C)线性表采用链式存储便于插入和删除操作的实现(D)线性表采用顺序存储便于插入和删除操作的实现12.设哈夫曼树中的叶子结点总数为m,若用二叉链表作为存储结构,则该哈夫曼树中总共有()个空指针域。(A)2m-1(B)2m(C)2m+1(D)4m13.设顺序循环队列Q[0:M-1]的头指针和尾指针分别为F和R,头指针F总是指向队头元素的前一位置,尾指针R总是指向队尾元素的当前位置,则该循环队列中的元素个数为()。(A)R-F(B)F-R
5、(C)(R-F+M)%M(D)(F-R+M)%M14.设某棵二叉树的中序遍历序列为ABCD,前序遍历序列为CABD,则后序遍历该二叉树得到序列为()。(A)BADC(B)BCDA(C)CDAB(D)CBDA15.设某完全无向图中有n个顶点,则该完全无向图中有()条边。(A)n(n-1)/2(B)n(n-1)(C)n2(D)n2-116.设某棵二叉树中有2000个结点,则该二叉树的最小高度为()。(A)9(B)10(C)11(D)12第2页(共7页)17.设某有向图中有n个顶点,则该有向图对应的邻接表中有()个表头结点。(A)n-1(B
6、)n(C)n+1(D)2n-118.设一组初始记录关键字序列(5,2,6,3,8),以第一个记录关键字5为基准进行一趟快速排序的结果为()。(A)2,3,5,8,6(B)3,2,5,8,6(C)3,2,5,6,8(D)2,3,6,5,819.设一组初始记录关键字序列为(25,50,15,35,80,85,20,40,36,70),其中含有5个长度为2的有序子表,则用归并排序的方法对该记录关键字序列进行一趟归并后的结果为()。(A)15,25,35,50,20,40,80,85,36,70(B)15,25,35,50,80,20,85,
7、40,70,36(C)15,25,35,50,80,85,20,36,40,70(D)15,25,35,50,80,20,36,40,70,8520.下面程序的时间复杂为()for(i=1,s=0;i<=n;i++){t=1;for(j=1;j<=i;j++)t=t*j;s=s+t;}(A)O(n)(B)O(n2)(C)O(n3)(D)O(n4)二.填空题。(每空1分,共15分)。1.通常从四个方面评价算法的质量:_________、_________、_________和_________。2.中序遍历二叉排序树所得到的序列是___
8、________序列(填有序或无序)3. 设一棵完全二叉树的顺序存储结构中存储数据元素为ABCDEF,则该二叉树的前序遍历序列为___________,中序遍历序列为___________,后序遍历序列为________
此文档下载收益归作者所有