2010-2011上期末试卷数据结构

《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，则该二叉树的前序遍历序列为___________，中序遍历序列为___________，后序遍历序列为________