全国2010年1月自考数据结构导论考试试题,答案,笔记

《全国2010年1月自考数据结构导论考试试题,答案,笔记》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、全国2010年1月高等教育自学考试数据结构导论试题课程代码：02142一、单项选择题(本大题共15小题，每小题2分，共30分)在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。1.下述文件中适合于磁带存储的是（A）A.顺序文件B.索引文件C.散列文件D.多关键字文件2.某二叉树的后根遍历序列为dabec，中根遍历序列为debac，则先根遍历序列为（D）A.acbedB.becabC.deabcD.cedba3.含有n个结点的二叉树用二叉链表表示时，空指针域个数为(C)A.n-1B.nC.n+1

2、D.n+2注：子域为2n个，有n-1个孩子。4.在一个图中，所有顶点的度数之和与图的边数的比是(C)A.1∶2B.1∶1C.2∶1D.4∶15.长度为n的链队列用单循环链表表示，若只设头指针，则出队操作的时间复杂度为(A)A.O(1)B.O(1og2n)二分法注：若只有尾指针，那么入和出都为O(1)C.O(n)（入队）D.O(n2)-冒泡6.下述几种排序方法中，要求内存量最大的是(C)A.插入排序B.快速排序C.归并排序D.选择排序7.对n个不同值进行冒泡排序，在元素无序的情况下比较的次数为(D)A.n-1B.nC.n+1D.n(n-1)／28.对

3、线性表进行二分查找时，要求线性表必须(C)A.以顺序方式存储B.以链式方式存储C.以顺序方式存储，且结点按关键字有序排列D.以链接方式存储，且结点按关键字有序排列9.在表长为n的顺序表上做删除运算，其平均时间复杂度为(B)A.O(1)B.O(n)注：在双向循环链表中，删除最后一个结点C.O(nlog2n)D.O(n2)的时间复杂度为O(1)10.当利用大小为n的数组顺序存储一个队列时，该队列的最大容量为(B)A.n-2B.n-1C.nD.n+111.有关插入排序的叙述，错误的是(C)A.插入排序在最坏情况下需要O(n2)时间B.插入排序在最佳情况可

4、在O(n)时间内完成C.插入排序平均需要O(nlog2n)时间-----快速排序需要o（nlog2n）树：是n各节点的有限集合。1.当n=0时，称为空树。2.当n>0时，有且仅有一个根的结点。D.插入排序的空间复杂度为O(1)12.有关树的叙述正确的是(C)A.每一个内部结点至少有一个兄弟B.每一个叶结点均有父结点C.有的树没有子树D.每个树至少有一个根结点与一个叶结点。(有且仅有一个结点)13.循环队列存储在数组元素A[0]至A[m]中，则入队时的操作为(D)A.rear=rear+1B.rear=(rear+1)％(m-1)C.rear=(re

5、ar+1)％mD.rear=(rear+1)％(m+1)14.关于串的的叙述，不正确的是(B)A.串是字符的有限序列B.空串是由空格构成的串注：空格串是只包括空格的串，空格串是有长度的，，而空串没有长度。C.替换是串的一种重要运算D.串既可以采用顺序存储，也可以采用链式存储15.对称矩阵A[N][N]，A[1][1]为首元素，将下三角(包括对角线)元素以行优先顺序存储到一维数组元素T[1]至T[N(N+1)／2]中，则任一上三角元素A[i][j]存于T[k]中，下标k为(B)A.i(i-1)／2+jB.j(j-1)／2+iC.i(j-i)／2+1D

6、.j(i-1)／2+l二、填空题(本大题共13小题，每小题2分，共26分)请在每小题的空格中填上正确答案。错填、不填均无分。16.下列程序段的时间复杂度为____O(n3)________。for(i=1；i<=n；i++)for(j=1；j<=n；j++)for(k=1；k<=n；k++)s=i+j+k；17.在数据结构中，各个结点按逻辑关系互相缠绕，任意两个结点可以邻接的结构称为__图状结构__________。18.在单链表中，存储每个结点有两个域，一个是数据域，另一个是指针域，指针域指向该结点___直接后继_____的。注：数据域---前接

7、前趋，指针域—直接后继19.在栈结构中，允许插入的一端称为__栈顶__________。注：队列允许插入的一端叫队尾。20.从一个长度为n的顺序表中删除第i个元素(1≤i≤n)时，需向前移动n-i__个元素。注：向后移动n-i+1个元素。21.一个栈的输入序列是1，2，3，…，n，输出序列的第一个元素是n，则第i个输出元素为__n-i+1________。22.循环队列被定义为结构类型，含有三个域：data、front和rear，则循环队列sq为空的条件是__sq.rear=sq.front__________。注：1，使用下列公式必要前提是，矩阵

8、式n*n的，也就是方矩阵。上三角情况：当i≤J时（前小于等于后）所求地址=首元素所占地址+i(20n-i+1)/2+j-i