全国自学考试数据结构导论试题及答案.pdf

高等教育自学考试全国统一命题考试数据结构导论试题、答案及评分参考第 1 页全国 2011 年 1 月自学考试 数据结构导论试题课程代码： 02142 一、单项选择题(本大题共15 小题，每小题2 分，共 30 分) 在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内错选、多选或未选均无分1.在顺序表中查找第i 个元素，时间效率最高的算法的时间复杂度为( ) A.O(1) B.O(n ) C.O(log2n) D.O(n) 2.树形结构中，度为0 的结点称为 ( ) A.树根B.叶子C.路径D.二叉树3.已知有向图G=(V,E)， 其中 V=V1,V2,V3,V4,V5,V6,V7， E=， ， ， ， ,，,， ，则图 G 的拓扑序列是( ) A.V1,V3,V4,V6,V2,V5,V7B.V1,V3,V2,V6,V4,V5,V7C.V1,V3,V4,V5,V2,V6,V7D.V1,V2,V5,V3,V4,V6,V74.有关图中路径的定义，表述正确的是( ) A.路径是顶点和相邻顶点偶对构成的边所形成的序列B.路径是不同顶点所形成的序列C.路径是不同边所形成的序列D.路径是不同顶点和不同边所形成的集合5.串的长度是指( ) A.串中所含不同字母的个数B.串中所含字符的个数C.串中所含不同字符的个数D.串中所含非空格字符的个数6.组成数据的基本单位是( ) A.数据项B.数据类型C.数据元素D.数据变量7.程序段i=n；x=0；dox=x+5*i ；i-；while （i0） ；的时间复杂度为( ) A.O（1）B.O（n）C.O（n2）D.O(n3) 8.与串的逻辑结构不同的数据结构是 ( ) A.线性表B.栈C.队列D.树高等教育自学考试全国统一命题考试数据结构导论试题、答案及评分参考第 2 页9.二叉树的第i（i1）层上所拥有的结点个数最多为( ) A.2iB.2i C.2i-1D.2i-1 10.设单链表中指针p 指向结点A，若要删除A 的直接后继，则所需修改指针的操作为( ) A.p-next=p-next-next B.p=p-next C.p=p-next-next D.p-next=p 11.下列排序算法中，某一趟结束后未必能选出一个元素放在其最终位置上的是( ) A.堆排序B.冒泡排序C.直接插入排序D.快速排序12.设字符串S1=ABCDEFG ， S2=PQRST，则运算S=CONCAT(SUBSTR(S1,2,LENGTH(S2),SUBSTR(S1,LENGTH(S2),2) 后 S 的结果为 ( ) A.BCQRB.BCDEF C. BCDEFG D.BCDEFEF 13.在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡结点为A，并且 A 的左孩子的平衡因子为-1，右孩子的平衡因子为0，则使其平衡的调整方法为( ) A.LL 型B.LR 型C.RL 型D.RR 型14.如果结点A 有 3 个兄弟结点，而且B 为 A 的双亲，则B 的度为 ( ) A.1 B.3 C.4 D.5 15.数据表 A 中每个元素距其最终位置较近，则最省时间的排序算法是( ) A.堆排序B.插入排序C.直接选择排序D.快速排序二、填空题 (本大题共 13 小题，每小题2 分，共 26 分) 请在每小题的空格中填上正确答案。

错填、不填均无分16.下列程序段的时间复杂度为_i=1；while（i1)的满二叉树中共有_个结点25.在无向图中，如果从顶点v 到顶点 v有路径，则称v 和 v是 _26.无向完全图G 采用 _存储结构较省空间27.在顺序查找、 二分查找、 索引查找和散列查找四种查找方法中，平均查找长度与元素个数没有关系的查找方法是_28.快速排序最好情况下的时间复杂度为_三、应用题 (本大题共 5 小题，每小题6 分，共 30 分) 29.稀疏矩阵A 如下，写出矩阵A 的三元组表及矩阵A 的转置矩阵的三元组表000003-04000000001-500000010003030.一棵二叉树的前根遍历序列为ABCDEFG ，中根遍历序列为CBDAEGF ，试构造出该二叉树31.下述矩阵表示一个无向连通网，试画出它所表示的连通网及该连通网的最小生成树4210495281298110512132.给定表（ 80，90，50，70，75， 60，40，100） ，试按元素在表中的顺序将它们依次插入一棵初始时为空的二叉排序树，画出插入完成后的二叉排序树33.试写出一组键值（46，58， 15，45，90，18，10，62）应用直接插入排序算法从小到大排序后各趟的结果。

四、算法设计题(本大题共2 小题，每小题7 分，共 14 分) 34.试分别写出二叉树的先根遍历和中根遍历的递归算法35.试编写以单链表为存储结构实现直接选择排序的算法高等教育自学考试全国统一命题考试数据结构导论试题、答案及评分参考第 4 页2011 年 1 月全国自考数据结构导论参考答案高等教育自学考试全国统一命题考试数据结构导论试题、答案及评分参考第 5 页高等教育自学考试全国统一命题考试数据结构导论试题、答案及评分参考第 6 页高等教育自学考试全国统一命题考试数据结构导论试题、答案及评分参考第 7 页全国 2010 年 10 月自学考试 数据结构导论试题课程代码： 02142 一、单项选择题(本大题共15 小题，每小题2 分，共 30 分) 在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内错选、多选或未选均无分1下列描述中正确的是( ) A.数据元素是数据的最小单位B.数据结构是具有结构的数据对象C.数据结构是指相互之间存在一种或多种特定关系的数据元素的集合D.算法和程序原则上没有区别，在讨论数据结构时两者是通用的2归并排序的时间复杂度是( ) AO（n2）B.O（ nlog2n）C.O（n）D.O（log2n）3二分查找的时间复杂度是( ) AO（n2）B.O（ nlog2n）C.O（n）D.O（log2n）4顺序存储的表中有90000 个元素，已按关键字值升序排列，假设对每个元素进行查找的概率相同，且每个元素的关键字值皆不相同，用顺序查找法查找时，需平均比较的次数为( ) A25000 B.30000 C.45000 D.90000 5散列文件是一种( ) A顺序文件B.索引文件C.链接文件D.计算寻址文件6两个矩阵A：mn，B： np 相乘，其时间复杂度为( ) AO(n) B.O(mnp) C.O(n2) D.O（mp）7.常用于函数调用的数据结构是( ) A.栈B.队列C.链表D.数组8二维数组An m以列优先顺序存储，数组A 中每个元素占用1 个字节， A1 1为首元素，其地址为0，则元素Ai j的地址为 ( ) A.（i-1） m+(j-1) B.(j-1) n+(i-1) C.(j-1) n+i D.jn+i 9.图的广度优先搜索使用的数据结构是( ) A队列B.树高等教育自学考试全国统一命题考试数据结构导论试题、答案及评分参考第 8 页C.栈D.集合10序列（ 21,19,37,5,2）经冒泡排序法由小到大排序，在第一次执行交换后所得结果为( ) A(19，21，37，5，2) B.(21，19， 5，37，2) C.(21，19，37，2，5) D.(2，21，19，37，5) 11数据在计算机存储器内表示时，根据结点的关键字直接计算出该结点的存储地址，这种方法称为( ) A索引存储方法B.顺序存储方法C.链式存储方法D.散列存储方法12在单链表中，存储每个结点有两个域，一个是数据域，另一个是指针域，指针域指向该结点的( ) A直接前趋B.直接后继C.开始结点D.终端结点13在已知头指针的单链表中，要在其尾部插入一新结点，其算法所需的时间复杂度为( ) AO（1）B.O（ log2n）C.O（n）D.O（n2）14在链队列中执行入队操作，( ) A需判别队是否空B.需判别队是否满C.限制在链表头p进行D.限制在链表尾p 进行15一整数序列26，59，77，31，51，11，19，42，以二路归并排序从小到大排序，第一阶段的归并结果为( ) A.31 ，51，11，42，26，77，59， 19 B.26，59，31， 77，11，51，19，42 C.11，19，26，31， 42，59，51，77 D.26，11，19， 31，51，59， 77，42 二、填空题 (本大题共 13 小题，每小题2 分，共 26 分) 请在每小题的空格中填上正确答案。

错填、不填均无分16下列程序段的时间复杂度为_i=0；s=0；while（snext=top 和_操作23有 m 个叶结点的哈夫曼树所具有的结点数为_24在一棵具有n个结点的完全二叉树中，从树根起，自上而下、自左至右地给所有结点编号设根结点编号为1若编号为i 的结点有右孩子，那么其右孩子的编号为_25在一棵树中，_结点没有前驱结点高等教育自学考试全国统一命题考试数据结构导论试题、答案及评分参考第 9 页26一个具有n 个顶点的有向完全图的弧数是_27n 个顶点的无向图G 用邻接矩阵An n存储，其中第i 列的所有元素之和等于顶点Vi的_28选择排序的平均时间复杂度为_三、应用题 (本大题共 5 小题，每小题6 分，共 30 分) 29在栈的输入端元素的输入顺序为1，2，3，4，5， 6，进栈过程中可以退栈，则退栈时能否排成序列3，2，5，6，4，1 和 1，5，4，6，2，3，若能， 写出进栈、 退栈过程， 若不能， 简述理由用 push（x）表示 x 进栈， pop(x)表示 x 退栈）30已知一棵二叉树的中根遍历序列为CBEDFAGH ，后根遍历序列为CEFDBHGA ，画出该二叉树。

31给定表（ 15， 11，8，20，14，13） ，试按元素在表中的顺序将它们依次插入一棵初始时为空的二叉排序树，画出插入完成后的二叉排序树，并判断该二叉排序树是否为平衡二叉排序树，若为非平衡二叉排序树，将它调整为平衡二叉排序树32如题 32 图所示无向图， （1）写出其邻接矩阵； （2）写出三种以顶点A 为起点的深度优先搜索顶点序列33用冒泡排序法对数据序列（49，38，65， 97，76，134，27，49）进行排序，写出排序过程并说明冒泡排序是否为稳定排序四、算法设计题(本大题共2 小题，每小题7 分，共 14 分) 34.编写计算二叉树中叶子结点数目的算法35.开散列表的类型定义如下：typedef struct tagnode keytype key; struct tagnode*next; *pointer,node; typedef pointer openhashn; 试写出开散列表上的查找算法高等教育自学考试全国统一命题考试数据结构导论试题、答案及评分参考第 10 页2010 年 10 月自考数据结构导论参考答案高等教育自学考试全国统一命题考试数据结构导论试题、答案及评分参考第 11 页高等教育自学考试全国统一命题考试数据结构导论试题、答案及评分参考第 12 页2005 年 10 月自考试卷数据结构导论高等教育自学考试全国统一命题考试数据结构导论试题、答案及评分参考第 13 页高等教育自学考试全国统一命题考试数据结构导论试题、答案及评分参考第 14 页高等教育自学考试全国统一命题考试数据结构导论试题、答案及评分参考第 15 页高等教育自学考试全国统一命题考试数据结构导论试题、答案及评分参考第 16 页高等教育自学考试全国统一命题考试数据结构导论试题、答案及评分参考第 17 页高等教育自学考试全国统一命题考试数据结构导论试题、答案及评分参考第 18 页高等教育自学考试全国统一命题考试数据结构导论试题、答案及评分参考第 19 页高等教育自学考试全国统一命题考试数据结构导论试题、答案及评分参考第 20 页2005 年 10 月自考数据结构导。