1 / 7 2010 年 10 月全国自考数据结构试题 课程代码：02331 一、单项选择题（本大题共15小题，每小题2分，共30分） 1．数据的四种存储结构是(A) A.顺序存储结构、链接存储结构、索引存储结构和散列存储结构 B.线性存储结构、非线性存储结构、树型存储结构和图型存储结构 C.集合存储结构、一对一存储结构、一对多存储结构和多对多存储结构 D.顺序存储结构、树型存储结构、图型存储结构和散列存储结构 2．若对某线性表最常用的操作是在最后一个结点之后插入一个新结点或删除最后一个结点，要使操作时间最少，下列选项中，应选择的存储结构是(C) A.无头结点的单向链表 B.带头结点的单向链表 C.带头结点的双循环链表 D.带头结点的单循环链表 3．若带头结点的单链表的头指针为head，则判断链表是否为空的条件是(B) A.head=NULL B.head->nex t=NULL C.head!=NULL D.head->nex t!=head 4．若元素的入栈顺序为1， 2， 3....， n，如果第2个出栈的元素是n，则输出的第i(1<=i<=n)个元素是(D) A.n-i B.n-i+l C.n-i+2 D.无法确定 5．串匹配算法的本质是(C) A.串复制 B.串比较 C.子串定位 D.子串链接 6．设有一个10阶的对称矩阵A，采用行优先压缩存储方式，a11为第一个元素，其存储地址为 1，每个元素占一个字节空间，则a85的地址为(C) A.13 B.18 C.33 D.40 7．若一棵二叉树的前序遍历序列与后序遍历序列相同，则该二叉树可能的形状是(B) A.树中没有度为2的结点 B.树中只有一个根结点 C.树中非叶结点均只有左子树 D.树中非叶结点均只有右子树 8．若根结点的层数为1，则具有n个结点的二叉树的最大高度是(A) A.n B.2log n C.2log n +1 D.n/2 9．在图G中求两个结点之间的最短路径可以采用的算法是(A) 2 / 7 A.迪杰斯特拉（Dijkstra）算法 B.克鲁斯卡尔（Kru skal）算法 C.普里姆(Prim)算法 D.广度优先遍历(BFS)算法 10．下图G=(V,E)是一个带权连通图，G的最小生成树的权为(D) A.15 B.16 C.17 D.18 11．在下图中，从顶点1出发进行深度优先遍历可得到的序列是(B) A.1 2 3 4 5 6 7 B.1 4 2 6 3 7 5 C.1 4 2 5 3 6 7 D.1 2 4 6 5 3 7 12．如果在排序过程中不改变关键字相同元素的相对位置，则认为该排序方法是(B) A.不稳定的 B.稳定的 C.基于交换的 D.基于选择的 13．设有一组关键字(19, 14, 23, 1，6，20, 4，27, 5，11, 10, 9)，...
