2009年1月自考全国统一命题考试 数据结构试题与答案

2018-12-19
来源:

20091月高等教育自学考试全国统一命题考试

数据结构试题

课程代码:02331

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

在每小题列出的四个备选项中只有一个是符合题目要求的,请将其代码填写在题后的括号内。错选、多选或未选均无分

1.下列程序段的时间复杂度为(       )

 s=0

 for(i=1i<ni++)

   for(j=1j<nj++)

      s+=i*j

A.O(1)B.O(n)

C.O(2n)D.O(n2)

2.假设某个带头结点的单链表的头指针为head,则判定该表为空表的条件是(       )

A.head==NULLB.head->next==NULL

C.head!=NULLD.head->next==head

3.栈是一种操作受限的线性结构,其操作的主要特征是(       )

A.先进先出B.后进先出

C.进优于出D.出优于进  

4.假设以数组A[n]存放循环队列的元素,其头、尾指针分别为frontrear。若设定尾指针指向队列中的队尾元素,头指针指向队列中队头元素的前一个位置,则当前存于队列中的元素个数为(       )

A.(rear-front-1)nB.(rear-front)n

C.(front-rear+1)nD.(rear-front+n)n

5.判断两个串大小的基本准则是(       )

A.两个串长度的大小B.两个串中首字符的大小

C.两个串中大写字母的多少D.对应的第一个不等字符的大小

6.二维数组A[4][5]按行优先顺序存储,若每个元素占2个存储单元,且第一个元素A[0][0]的存储地址为1000,则数组元素A[3][2]的存储地址为(       )

A.1012B.1017

C.1034D.1036

7.高度为5的完全二叉树中含有的结点数至少为(       )

A.16B.17

C.31D.32

8.已知在一棵度为3的树中,度为2的结点数为4,度为3的结点数为3,则该树中的叶子结点数为(       )

A.5B.8

C.11D.18

9.下列所示各图中是中序线索化二叉树的是(       )

题9.png

10.已知含6个顶点(v0v1v2v3v4v5)的无向图的邻接矩阵如图所示,则从顶点v0出发进行深度优先遍历可能得到的顶点访问序列为(       )

题10.pngA.(v0v1v2v5v4v3)

B.(v0v1v2v3v4v5)

C.(v0v1v5v2v3v4)

D.(v0v1v4v5v2v3)

11.如图所示有向图的一个拓扑序列是(       )

题11.pngA.ABCDEF

B.FCBEAD

C.FEDCBA

D.DAEBCF

12.下列关键字序列中,构成大根堆的是(       )

A.58139627B.981756233

C.98635l27D.98675123

13.对长度为15的有序顺序表进行二分查找,在各记录的查找概率均相等的情况下,查找成功时所需进行的关键字比较次数的平均值为(       )


14.已知一个散列表如图所示,其散列函数为H(key)=key11,采用二次探查法处理冲突,则下一个插入的关键字49的地址为(       )

题14.png

15.数据库文件是由大量带有结构的(       )

A.记录组成的集合B.字符组成的集合

C.数据项组成的集合D.数据结构组成的集合

二、填空题(本大题共10小题,每小题2分,共20)

请在每小题的空格中填上正确答案。错填、不填均无分

16.估算算法时间复杂度时考虑的问题规模通常是指算法求解问题的_________

17.在双向循环链表中插入一个新的结点时,应修改_________指针域的值。

18.若进栈序列为abc,且进栈和出栈可以穿插进行,则可能出现_________个不同的出栈序列。

19.链串的结点大小定义为结点的_________中存放的字符个数。

20.广义表(a(d(c)))的深度为_________

21.在含有3个结点abc的二叉树中,前序序列为abc且后序序列为cba的二叉树有_________棵。

22.若用邻接矩阵表示有向图,则顶点i度等于矩阵中_________

23.对关键字序列(1518111319161217108)进行增量为5的一趟希尔排序的结果为_________

24.索引顺序查找的索引表由各分块中的最大关键字及各分块的_________构成。

25.VSAM文件的实现依赖于操作系统中的_________存取方法的功能。