2013年1月自学考试数据结构导论试题

　　课程代码：02142请考生按规定用笔将所有试题的答案涂、写在答题纸上。

　　选择题部门

　　留意事项：

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

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

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

　　在每小题列出的四个备选项中只要一个是符合标题问题要求的，请将其选出并将“答题纸”的相应代码涂黑。错涂、多涂或未涂均无分。

　　1.数据的基本单元是

　　A.数据元素B.数据项

　　C.字段D.域

　　2.算法的空间复杂度是指

　　A.算法中输入数据所占用的存储空间的大小

　　B.算法本身所占用的存储空间的大小

　　C.算法中所占用的所有存储空间的大小

　　D.算法中需要的辅助变量所占用存储空间的大小

　　3.从一个长度为100的挨次表中删除第30个元素,需向前挪动的元素个数为

　　A.29B.30

　　C.70D.71

　　4.若线性表最常用的操作是存取第i个元素及其后继的值,则最节省操作时间的存储布局是

　　A.单链表B.双链表

　　C.单循环链表D.挨次表

　　5.判断链栈LS能否为空的条件是

　　A.LS->next==LSB.LS->next==NULL

　　C.LS!=NULLD.LS==NULL

　　6.关于链队列的运算说法准确的是

　　A.入队列需要判断队列能否满B.出队列需要判断队列能否空

　　C.入队列需要判断队列能否空D.出队列需要判断队列能否满

　　7.元素的进栈次序为A,B,C,D,E,则出栈中不成能的序列是

　　A.A,B,C,D,EB.B,C,D,E,A

　　C.E,A,B,C,DD.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,如果

　　25.一个有序表A含有15个数据元素，且第一个元素的下标为1，按二分查找算法查找元素A[14]，所比力的元素下标顺次是__________。

　　26.用n个值构造一棵二叉排序树，它的最大深度为__________。

　　27.设记录数为n，则冒泡排序算法在最好情况下所作的比力次数为__________。

　　28.二路归并排序算法的时间复杂度为__________。

　　三、使用题(本大题共5小题，每小题6分，共30分)

　　29.设有编号为A，B，C，D的四辆列车，挨次进入一个栈式布局的站台，试写出这四辆列车开出站台的所有可能的挨次。

　　30.已知一棵二叉树的先序遍历序列为ABCDEFGHK，中序遍历序列为CBEDFAGKH，试成立该二叉树并写出它的后序遍历序列。

　　31.操纵克鲁斯卡尔(Kruskal)算法构造题31图的最小生成树，画出它的构造过程。

　　题31图

　　32.给定表(27，19，50，1，75，12，40，90，66，32，22)，试按元素在表中的次序将它们顺次插入一棵初始时为空的二叉排序树，画出插入完成后的二叉排序树。

　　33.对初始关键字序列48，39，，68，95，88，12，27，48的记录进行冒泡排序(升序)，给出排序过程。

　　四、算法设想题(本大题共2小题，每小题7分，共14分)

　　34.试写出判断带头结点的单链表head中的元素值能否是递减的算法。

　　35.试写出在有序表T顶用二分查找法查找键值为key的元素的算法。