《浙江省2002年1月高等教育自学考试数据结构试题课程代码02331》由会员分享，可在线阅读，更多相关《浙江省2002年1月高等教育自学考试数据结构试题课程代码02331（5页珍藏版）》请在金锄头文库上搜索。
1、02331 数据结构 第 1 页 共 5 页浙江省 2002 年 1 月高等教育自学考试数据结构试题课程代码：02331一、单项选择题(在每小题的四个备选答案中，选出一个正确答案，并将正确答案的序号填在题干的括号内。每小题 2 分，共 38 分)1.某二叉树的先序序列和后序序列正好相同，则该二叉树一定是( )的二叉树。A.空或只有一个结点 B.高度等于其结点数C.任一结点无左孩子 D.任一结点无右孩子2.下列排序算法中，时间复杂度不受数据初始状态影响，恒为 O(log2n)的是( )A.堆排序 B.冒泡排序C.直接选择排序 D.快速排序3.下列排序算法中，( )算法可能会出现下面情况：初始数据
2、有序时，花费的时间反而最多。A.堆排序 B.冒泡排序C.快速排序 D.SHELL 排序4.一个栈的输入序列为 1 2 3 4 5，则下列序列中不可能是栈的输出序列的是( )A. 2 3 4 1 5 B. 5 4 1 3 2C. 2 3 1 4 5 D. 1 5 4 3 25.设循环队列中数组的下标范围是 1n，其头尾指针分别为 f 和 r，则其元素个数为( )A. r-f B. r-f+1C. (r-f) mod n+1 D. (r-f+n) mod n6.若某链表最常用的操作是在最后一个结点之后插入一个结点和删除最后一个结点，则采用( )存储方式最节省时间。A.单链表 B.双链表C.带头结点
3、的双循环链表 D.单循环链表7.在有 n 个结点的二叉链表中，值为非空的链域的个数为( )A. n-1 B. 2n-1C. n+1 D. 2n+18.一棵左右子树均不空的二叉树在先序线索化后，其空指针域数为( )A. 0 B. 1C. 2 D.不确定9.数组 A 的每个元素占 5 个单元，将其按行优先次序存储在起始地址为 1000 的连续的内存单元中，则元素 A，的地址为( )A. 1140 B. 1145C. 1120 D. 112510.求最短路径的 DIJKSTRA 算法的时间复杂度为( )A. O(n) B. O(n+e)C. O(n2) D. O(ne)11.对有 18 个元素的有序
4、表作二分查找，则查找 A3的比较序列的下标依次为( )A. 1，2，3 B. 9，5，2，3C. 9，5，3 D. 9，4，2，312.快速排序算法在最好情况下的时间复杂度为( )A. O(n) B. O(nlog2n)C. O(n2) D. O(log2n)02331 数据结构 第 2 页 共 5 页13.下列排序算法中，某一趟结束后未必能选出一个元素放在其最终位置上的是( )A.堆排序 B.冒泡排序C.快速排序 D.直接插入排序14.二叉树在线索化后，仍不能有效求解的问题是( )A.先序线索二叉树中求先序后继B.中序线索二叉树中求中序后继C.中序线索二叉树中求中序前趋D.后序线索二叉树中求
5、后序后继15.DFS 算法的时间复杂度为( )A. O(n) B. O(n3)C. O(n2) D. O(n+e)16.队列操作的原则是( )A.先进先出 B.后进先出C.只能进行插入 D.只能进行删除17.有 64 个结点的完全二叉树的深度为( )(根的层次为 1)。A. 8 B. 7C. 6 D. 518.在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡结点为 A，并已知 A 的左孩子的平衡因子为-1，右孩子的平衡因子为 0，则应作 ( )型调整以使其平衡。A. LL B. LRC. RL D. RR19.数据表 A 中有 10000 个元素，如果仅要求求出其中最大的 10 个元素
6、，则采用( )排序算法最节省时间。A.堆排序 B.希尔排序C.快速排序 D.直接选择排序二、判断题(判断下列各题，正确的在题后括号内打 “” ，错的打“” 。每小题 1 分，共10 分)1.给出不同的输入序列建造二叉排序树，一定得到不同的二叉排序树。( )2.由于希尔排序的最后一趟与直接插入排序过程相同，因此前者一定比后者花费的时间多。( )3.在对链队列作出队操作时，不会改变 front 指针的值。( )4.若一个栈的输入序列为 123n，其输出序列的第一个元素为 n，则其输出序列的每个元素ai 一定满足 ai=n-i+1(i=1,2.,n)( )5.二叉树中的叶子结点就是二叉树中没有左右子
7、树的结点。( )6.一棵树中的叶子结点数一定等于与其对应的二叉树中的叶子结点数。( )7.有向图用邻接矩阵表示后，顶点 i 的人度等于邻接矩阵中第 i 列的元素个数。( )8.有向图的邻接表和逆邻接表中的结点数一定相同。( )9.删除二叉排序树中一个结点，再重新插入上去，一定能得到原来的二叉排序树。( )10.图 G 的拓扑序列唯一，则其弧数必为 n-1(其中 n 为 G 的顶点数)。( )三、填空题(每空 2 分，共 20 分)1.在有 n 个叶子结点的哈夫曼树中，总结点数是_。2.一棵树 T 采用二叉链表存储，如果树 T 中某结点为叶子结点，则在二叉链表 BT 中所对应的结点一定_。3.已
8、知数组 A 为对称矩阵，其中每个元素占 5 个单元。现将其下三角部分02331 数据结构 第 3 页 共 5 页按行优先次序存储在起始地址为 1000 的连续的内存单元中，则元素 A，对应的地址是_。4.在有 n 个结点的无向图中，其边数最多为_。5.取出广义表 A=(x,(a,b,c,d)中原子 x 的函数是_。6.对矩阵采用压缩存储是为了_。7.带头结点的双循环链表 L 为空表的条件是_。8.在双链表中，在指针 P 所指结点前面插入一个结点 S时的语句序列是：S-next=P;S-prior=P-prior;P-prior=S;_；9.对广义表 A=(x,(a,b),c,d)的运算 hea
9、d (head (tail (A)的结果是 _。10.判断线索二叉树中某结点指针 P 所指结点有左孩子的条件是_。四、简答题(每小题 5 分，共 15 分)1.求出下图的一棵最小生成树。2.将下面顺序表建成一个小头堆。(70，12，20，31，1，5，44 ，66，61，200，30，80，150，4，28)3.已知一棵二叉树的先序序列是 ABCDEFGHIJK，中序序列是 CDBGFEAHJIK，请构造出该二叉树。五、综合应用题(共 17 分)1.已知一树的双亲表示法如下，其中各兄弟结点是依次出现的，画出该树及对应的二叉树。(满分 7 分) 。1 2 3 4 5 6 7 8 9 10 11
10、12 13 14 15data A B C D E F G H I J K L M N Oparent 0 1 1 1 2 2 3 3 4 4 5 6 6 7 82.计算二叉树的深度的算法。(10 分)02331 数据结构 第 4 页 共 5 页浙江省 2002 年 1 月高等教育自学考试数据结构试题参考答案课程代码：02331一、单项选择题(每小题 2 分，共 38 分)1.A 2.B 3.C 4.B 5.D6.C 7.A 8.B 9.A 10.C11.D 12.B 13.D 14.D 15.C16.A 17.B 18.A 19.C二、判断题(每小题 1 分，共 10 分)1. 2. 3 4
11、. 5.6. 7. 8. 9. 10.三、填空题(每空 2 分，共 20 分)1. n-12. 左右子树空3. 12254. n(n-1)/25. head(A)6. 节省空间7. L-next=L-prior 或 L-next=L8. S-prior-next=S9. (a)10. P-ltag=1四、简答题(每小题 5 分，共 15 分)1.最小生成树：2.小头堆：1 12 4 31 30 5 20 66 61 200 70 80 150 44 283.二叉树：02331 数据结构 第 5 页 共 5 页五、综合应用题(共 17 分)1.从森林转换为二叉树：(7 分 )2.计算二叉树的深度的算法：(10 分)int depth(tree *T)if(!T)return 0;elsereturn 1+max(depth(T-Lchild),depth(-Rchild);
