全国2012年10月自考数据结构试题(课程代码:02331)

全国2012年10月高等教育自学考试

数据结构试题

课程代码:02331

请考生按规定用笔将所有试题的答案涂、写在答题纸上。

选择题部分

注意事项:

1. 答题前,考生务必将自己的考试课程名称、姓名、准考证号用黑色字迹的签字笔或钢笔填写在答题纸规定的位置上。

2. 每小题选出答案后,用2B铅笔把答题纸上对应题目的答案标号涂黑。如需改动,用橡皮擦干净后,再选涂其他答案标号。不能答在试题卷上。

一、单项选择题(本大题共l5小题,每小题2分,共30分)

在每小题列出的四个备选项中只有一个是符合题目要求的,请将其选出并将“答题 纸”的相应代码涂黑。错涂、多涂或未涂均无分。 1.一个算法的时间耗费的数量级称为该算法的 A.效率 C.可实现性 2.顺序表便于 A.插入结点 C.按值查找结点

B.删除结点 D.按序号查找结点 B.难度 D.时间复杂度

3.设带头结点的单循环链表的头指针为head,指针变量P指向尾结点的条件是 A.p->next->next==head C.p->next->next==NULL

B.p->next==head D.p->next==NULL

4.设以数组A[0..m-1]存放循环队列,front指向队头元素,rear指向队尾元素的下一个位置,则当前队列中的元素个数为

A.(rear-front+m)%m C.(front-rear+m)%m

5.下列关于顺序栈的叙述中,正确的是

A.入栈操作需要判断栈满,出栈操作需要判断栈空 B.入栈操作不需要判断栈满,出栈操作需要判断栈空 C.入栈操作需要判断栈满,出栈操作不需要判断栈空 D.入栈操作不需要判断栈满,出栈操作不需要判断栈空

- 本套试题共分10页,当前页是第1页-

B.rear-front+1 D.(rear-front)%m

6.A是一个10×10的对称矩阵,若采用行优先的下三角压缩存储,第一个元素a0,0的存储地址为1,每个元素占一个存储单元,则a7,5的地址为 A.25 C.33

7.树的后序遍历等价于该树对应二叉树的 A.层次遍历 C.中序遍历

8.使用二叉线索树的目的是便于 A.二叉树中结点的插入与删除 C.确定二叉树的高度

B.在二叉树中查找双亲 D.查找一个结点的前趋和后继 B.前序遍历 D.后序遍历 B.26 D.34

9.设无向图的顶点个数为n,则该图边的数目最多为 A.n-l C.n(n+1)/2

10.可进行拓扑排序的图只能是 A.有向图 C.有向无环图 11.下列排序方法中稳定的是 A.直接插入排序 C.堆排序 12.下列序列不为堆的是 .. A.75,45,65,30,15,25 C.75,65,30,l5,25,45

B.75,65,45,30,25,15 D.75,45,65,25,30,15 B.直接选择排序 D.快速排序 B.无向图 D.无向连通图 B.n(n-1)/2 D.n2

13.对线性表进行二分查找时,要求线性表必须是 A.顺序存储

C.顺序存储且按关键字有序

B.链式存储

D.链式存储且按关键字有序

14.分别用以下序列生成二叉排序树,其中三个序列生成的二叉排序树是相同的,不同 .. 的序列是 A.(4,1,2,3,5) C.(4,5,2,1,3)

B.(4,2,3,l,5) D.(4,2,1,5,3)

15.下列关于m阶B树的叙述中,错误的是 .. A.每个结点至多有m个关键字 B.每个结点至多有m棵子树

C.插入关键字时,通过结点分裂使树高增加 D.删除关键字时通过结点合并使树高降低

非选择题部分

- 本套试题共分10页,当前页是第2页-

注意事项:

用黑色字迹的签字笔或钢笔将答案写在答题纸上,不能答在试题卷上。

二、填空题(本大题共10小题,每小题2分,共20分) 16.数据元素之间的逻辑关系称为数据的______结构。 17.在线性表中,表的长度定义为______。

18.用S表示入栈操作,X表示出栈操作,若元素入栈的顺序为1、2、3、4,为了得到 1、3、4、2的出栈顺序,相应的S和X的操作序列为______。 19.在二叉树中,带权路径长度最短的树称为______。

20.已知广义表G,head(G)与tail(G)的深度分别为4和6,则G的深度是______。

21.一组字符(a,b,c,d)在文中出现的次数分别为(7,6,3,5),字符'd'的哈夫曼编码的长度为______。 22.在一个具有n个顶点的无向图中,要连通全部顶点至少需要______条边。 23.直接选择排序算法的时间复杂度是______。

24.对于长度为81的表,若采用分块查找,每块的最佳长度为______。 25.用二叉链表保存有n个结点的二叉树,则结点中有______个空指针域。 三、解答题(本大题共4小题,每小题5分,共20分)

26.假设Q是一个具有11个元素存储空间的循环队列(队尾指针指向队尾元素的下一 个位置,队头指针指向队头元素),初始状态Q.front=Q.rear=0;写出依次执行 下列操作后头、尾指针的当前值。

a,b,c,d,e,f入队,a,b,c,d出队; (1) Q.front=______;Q.rear=______。 g,h,i,j,k,l入队,e,f,g,h出队; (2) Q.front=______;Q.rear=______。 M,n,o,P入队, i,j,k,l,m出队; (3) Q.front=______;Q.rear=______。

27.已知一个无向图如题27图所示,以①为起点,用普里姆(Prim)算法求其最小生成树,画出最小生成树的构

造过程。

28.用归并排序法对序列 (98,36,-9,0,47,23,1,8)进行排序,问: (1)一共需要几趟归并可完成排序。 (2)写出第一趟归并后数据的排列次序。

- 本套试题共分10页,当前页是第3页-

联系客服:779662525#qq.com(#替换为@) 苏ICP备20003344号-4