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

数据结构试题

课程代码：02331

一、单项选择题(本大题共15小题，每小题2分，共30分)在每小题列出的四个选项中只有一个选项是符合题目要求的，请将正确选项前的字母填在题后的括号内。

1.若结点的存储地址与其关键字之间存在某种映射关系，则称这种存储结构为(   )

  A.顺序存储结构        B.链式存储结构

  C.索引存储结构        D.散列存储结构

2.在长度为n的顺序表的第i(1≤i≤n+1)个位置上插入一个元素，元素的移动次数为(   )

  A.n-i+1        B.n-i

  C.i            D.i-1

3.对于只在表的首、尾两端进行插入操作的线性表，宜采用的存储结构为(   )

   A.顺序表        B.用头指针表示的单循环链表

   C.用尾指针表示的单循环链表        D.单链表

4.若进栈序列为a,b,c，则通过入出栈操作可能得到的a,b,c的不同排列个数为(   )

  A.4        B.5        C.6        D.7

5.为查找某一特定单词在文本中出现的位置，可应用的串运算是(   )

  A.插入        B.删除        C.串联接        D.子串定位

6.已知函数Sub(s,i,j)的功能是返回串s中从第i个字符起长度为j的子串，函数Scopy(s,t)的功能为复制串t到s。若字符串S=″SCIENCESTUDY″，则调用函数Scopy(P,Sub(S,1,7))后得到(   )

  A.P=″SCIENCE″        B.P=″STUDY″

  C.S=″SCIENCE″        D.S=″STUDY″

7.三维数组A[4][5][6]按行优先存储方法存储在内存中，若每个元素占2个存储单元，且数组中第一个元素的存储地址为120，则元素A［３］[4][5]的存储地址为(   )

  A.356        B.358        C.360        D.362

8.如右图所示广义表是一种(   )

  A.线性表

  B.纯表

  C.结点共享表

  D.递归表

9.下列陈述中正确的是(   )

  A.二叉树是度为2的有序树

  B.二叉树中结点只有一个孩子时无左右之分

  C.二叉树中必有度为2的结点

  D.二叉树中最多只有两棵子树，并且有左右之分

10.n个顶点的有向完全图中含有向边的数目最多为(   )

  A.n-1                B.n           C.n(n-1)/2           D.n(n-1)

11.已知一个有向图如右所示，则从顶点a出发进行深度优先偏历，不可能得到的DFS序列为(   )

  A.a d b e f c

  B.a d c e f b

  C.a d c b f e

  D.a d e f c b

12.在最好和最坏情况下的时间复杂度均为O(nlogn)且稳定的排序方法是(   )

  A.快速排序        B.堆排序        C.归并排序        D.基数排序

13.不可能生成右图所示二叉排序树的关键字序列是(   )

  A.4 5 3 1 2

  B.4 2 5 3 1

  C.4 5 2 1 3

  D.4 2 3 1 5

14.ALV树是一种平衡的二叉排序树，树中任一结点的(   )

  A.左、右子树的高度均相同          B.左、右子树高度差的绝对值不超过1

  C.左子树的高度均大于右子树的高度  D.左子树的高度均小于右子树的高度

15.在VSAM文件的控制区间中，记录的存储方式为(   )

  A.无序顺序        B.有序顺序

  C.无序链接        D.有序链接

二、填空题(本大题共