02142数据结构导论2008年10月份真题及答案.doc

全国2008年10月高等教育自学考试 数据结构导论试题 课程代码：02142 一、单项选择题(本大题共15小题，每小题2分，共30分) 在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。 1.从逻辑上可以把数据结构分为(　　　) A.动态结构、静态结构 B.顺序结构、链式结构 C.线性结构、非线性结构 D.初等结构、构造型结构 2.关于算法的描述，不正确的是(　　　) A.算法最终必须由计算机程序实现 B.所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界 C.健壮的算法不会因非法的输入数据而出现莫名其妙的状态 D.算法的优劣与算法描述语言无关 3.在单链表中，存储每个结点需要有两个域，一个是数据域，另一个是指针域，指针域指向该结点的(　　　) A.直接前趋 B.直接后继 C.开始结点 D.终端结点 4.将两个各有n个元素的有序表合并成一个有序表，其最少的比较次数为(　　　) A.n B.2n-1 C.2n D.n2 5.栈和队列共同具有的特点是(　　　) A.都是先进后出 B.都是先进先出 C.只允许在端点进行操作运算 D.既能先进先出，也能先进后出 6.若用一个有6个单元的数组来实现循环队列，rear和front的初值分别为0和3。则从队列中删除一个元素，再添加两个元素后，rear和front的值分别为(　　　) A.1和5 B.2和4 C.4和2 D.5和1 7.数组A［0..5］［0..5］的每个元素占5个字节，将其以列为主序存储在起始地址为1000的内存单元中，则元素A［5］［5］的地址是(　　　) A.1175 B.1180 C.1205 D.1210 8.含有n个结点的二叉树采用二叉链表存储时，空指针域的个数为(　　　) A.n-1 B.n C.n+1 D.n+2 9.在一棵深度为H的完全二叉树中，所含结点的个数不少于(　　　) A.2H-1-1 B.2H-1 C.2H-1 D.2H 10.一个具有n个顶点的无向连通图，它所包含的连通分量数为(　　　) A.0 B.1 C.n D.不确定 11.下列说法中不正确的是(　　　) A.无向图的极大连通子图称为连通分量 B.连通图的广度优先搜索中一般要采用队列来暂存刚访问过的顶点 C.连通图的深度优先搜索中一般要采用栈来暂存刚访问过的顶点 D.有向图的遍历不可采用广度优先搜索算法 12.对一棵二叉排序树采用中根遍历进行输出的数据一定是(　　　) A.递增或递减序列 B.递减序列 C.无序序列 D.递增序列 13.一个有序表为{1，3，9，12，32，41，45，62，75，77，82，95，100}，当二分查找值为82的结点时，查找成功时的比较次数为(　　　) A.1 B.2 C.4 D.8 14.一组记录的关键字为{45，80，55，40，42，85}，则利用堆排序的方法建立的初始堆为 (　　　) A.80，45，55，40，42，85 B.85，80，55，40，42，45 C.85，80，55，45，42，40 D.85，55，80，42，45，40 15.关于VSAM文件存取操作的说法，正确的是(　　　) A.不能顺序存取，只能按关键字随机存取 B.不能顺序存取，不能按关键字随机存取 C.只能顺序存取，不能按关键字随机存取 D.既能顺序存取，也能按关键字随机存取 二、填空题(本大题共13小题，每小题2分，共26分) 请在每小题的空格中填上正确答案。错填、不填均无分。 16.在任何问题中，数据元素都不是孤立的，它们之间总存在某种关系，通常称这种关系为 ________。 17.存储结点之间通常有四种基本存储方式，即顺序存储方式、索引存储方式、________和散列存储方式。 18.在一个长度为n的顺序表中第i个元素（1≤i≤n）之前插入一个元素时，需向后移动________个元素。 19.对一棵深度为10的满二叉树按层编号，则编号为51的结点，它的双亲结点编号为________。 20.用S表示入栈操作，X表示出栈操作，若元素入栈顺序为1234，为了得到1342的出栈顺序，相应的S和X操作串为________。 21.具有n个叶子结点的哈夫曼树，其结点总数为________。 22.一棵具有n个结点的树，所有非终端结点的度均为k，则该树中叶子结点个数为________。 23.在无向图G的邻接矩阵A中，若A［i］［j］等于0，则A［j］［i］等于________。 24.两个串是相等的，当且仅当两个串的长度相等且________的字符都相同。 25.某二叉树的后根遍历序列为abd，中根遍历序列为adb，则它的先根遍历序列为________。 26.先在所有的记录中选出键值最