全国自考2013年01月《数据结构导论》试题.doc

全国2013年1月 课程代码：02142 一、单项选择题(本大题共15小题，每小题2分，共30分) 在每小题列出的四个备选项中只有一个是符合题目要求的，请将其选出并将“答题纸”的相应代码涂黑。错涂、多涂或未涂均无分。 1.数据的基本单位是A.数据元素B.数据项C.字段D.域 2.算法的空间复杂度是指 　　A.算法中输入数据所占用的存储空间的大小 B.算法本身所占用的存储空间的大小 C.算法中所占用的所有存储空间的大小 D.算法中需要的辅助变量所占用存储空间的大小 3.从一个长度为100的顺序表中删除第30个元素,需向前移动的元素个数为 　　A.29　　 B.30　　C.70 　　D.71 4.若线性表最常用的操作是存取第i个元素及其后继的值,则最节省操作时间的存储结构是 　　A.单链表 B.双链表C.单循环链表 D.顺序表 5.判断链栈LS是否为空的条件是 　　A.LS-next= =LS　　B.LS-next= =NULL　　C.LS! =NULL 　　D.LS= =NULL 6.关于链队列的运算说法正确的是 　　A.入队列需要判断队列是否满B.出队列需要判断队列是否空 C.入队列需要判断队列是否空D.出队列需要判断队列是否满 7.元素的进栈次序为A,B,C,D,E,则出栈中不可能的序列是 　　A.A,B,C,D,E　　B.B,C,D,E,A　　C.E,A,B,C,D　　D.E,D,C,B,A 8.具有63个结点的完全二叉树是 　　A.满二叉树B.二叉排序树C.哈夫曼树D.空树 9.将含有80个结点的完全二叉树从根这一层开始,每层从左到右依次对结点编号,根结点的编号为1。则关于编号40的结点的左右孩子的说法正确的是 　　A.左孩子编号为79，右孩子编号为80 B.左孩子不存在，右孩子编号为80 C.左孩子编号为80，右孩子不存在 D.左孩子不存在，右孩子不存在 10.将题10图所示的一棵树转换为二叉树，结点D是 　　A.A的右孩子B.B的右孩子 C.C的右孩子D.E的右孩子 11.无向图的邻接矩阵是 题10图 A.对称矩阵B.稀疏矩阵C.对角矩阵D.上三角矩阵 12.图的广度优先有哪些信誉好的足球投注网站遍历的过程类似于树的 　　A.前序遍历B.中序遍历C.后序遍历D.按层次遍历 13.要解决散列引起的冲突问题，最常用的方法是 　　A.数字分析法、除留余数法、平方取中法 B.除留余数法、线性探测法、平方取中法 C.线性探测法、二次探测法、链地址法D.除留余数法、线性探测法、二次探测法 14.下列表述中，正确的是 　　A.序列（102，81，55，62，50，40，58，35，20）是堆 B.序列（102，81，55，62，50，40，35，58，20）是堆 C.序列（102，81，55，58，50，40，35，62，20）是堆 D.序列（102，71，55，40，50，62，35，58，20）是堆 15.下列算法中，不稳定的排序算法是 　　A.冒泡排序B.快速排序C.直接插入排序D.二路归并排序 二、填空题(本大题共13小题，每小题2分，共26分) 16.下面算法程序段的时间复杂度为__________。 for(i=1;i=n;i++) for(j=1;j=i;j++) {x=a[i][j]; a[i][j]=a[j][i]; a[j][i]=x;} 17.设p指向单链表的最后一个结点，要在最后一个结点之后插入q所指的结点，需执行的语句序列是①p-next=q;②__________;③p-next=NULL。 18.向一个长度为100的顺序表中第50个元素之前插入一个元素时，需向后移动的元素个数为__________。 19.一个带头结点的链栈LS，现将一个新结点入栈，指向该结点的指针为p，入栈操作为p-next=LS-next和__________。 20.队列操作的原则是__________。 21.含有n个顶点的连通图中的任意一条简单路径，其最大长度为__________。 22.在一棵度为3的树中，度为3的结点数为1个，度为2的结点数为2个，度为1的结点数为3个，则度为0的结点数为__________个。 23.某二叉树的中序遍历序列为BACDEFGH，后序遍历序列为BCAEDGHF，则根结点F的左子树上共有__________个结点。 24.设有向图G的邻接矩阵为A,如果Vi,Vj是图中的一条弧,则A［i］［j］的值为。 25.一个有序表A含有15个数据元素，且第一个元素的下标为1，按二分查找算法查找元素A［14］，所比较的元素下标依次是__________。 26.用n个值构造一棵二叉排序树，它的最大深度为__________。 27