2008年10月自考数据结构导论试题真题1.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.先在所有的记录中选出键值最