计算机科学与技术专业数据结构试题（4）

2005年上学期已考试卷 计算机科学与技术专业数据结构试题4 2003年5月 题号 一 二 三 四 五 六 总分 得分 一、单项选择题，在括号内填写所选择的标号每小题1分，共12分 1. 执行下面程序段时，S语句的执行次数为。 for int il in; i forint jl; j〈i; j S; A. n2 B. n2/2 C. n n1 D. nnl /2 2. 多维数组实际上是由嵌套的实现的。 A. 一维数组B.多项式 C,三元组表 D.简单变量 3. 不带头结点的单链表first为空的判定条件是。 A. firstNULL;B. first-〉］inkNULL; C. first-〉linkfirst;D. firstNULL; 4. 若让元素1,2,3依次进栈，则出栈次序不可能出现种情况。 A. 3, 2, 1B. 2, 1, 3 C. 3, 1, 2 D. 1, 3, 2 5, 设链式栈中结点的结构为data, link,且top是指向栈顶的指针。若想摘除链式 栈的栈顶结点，并将被摘除结点的值保存到x中，则应执行操作。 A. xtop-〉data; toptop-〉link; C. xtop; toptop-link; 6. 设有一个广义表A a,其表尾为 A. aB. B. toptop-〉link; xtop-〉data; D. xtop-〉data; o C. D. a 7. 在一棵具有n个结点的完全二叉树中，树枝结点的最大编号为。假定树根结 点的编号为0。 A. n-l/2 B. n/2 C. n/21 D. n/2-1 8. 若搜索每个元素的概率相等，则在长度为n的顺序表上搜索任一元素的平均搜索长 度为 o A. nB. n1 C. n-l/2 D. nl/2 向一棵AVL树插入元素时，可能引起对最小不平衡子树的调整过程，此调整分为 种旋转类型。 A. 2 B. 3 C. 4 D. 5 9. 为了实现图的广度优先搜索遍历，BFS算法使用的一个辅助数据结构是（）。 A.栈 B,队列 C.二叉树 D.树 11. 若待排序序列在排序前已基本递增有序, A.直接插入排序B.快速排序 12. 5阶B树中，每个结点最多允许有（ A. 2B. 3 则采用（）方法比较次数最少。 C.归并排序 D.直接选择排序 ）个关键码。 C. 4D. 5 二、填空题，在横线处填写合适内容（每空1分，共16分） 1. 数据结构包括、和数据的运算三个方面。 2. 一维数组所占用的空间是连续的。但数组元素不一定顺序存取，通常是按元素的 存取的。 3. 将一个n阶对称矩阵的上三角部分或下三角部分压缩存放于一个一维数组中，则该 一维数组需要至少具有 个元素。 4. 链接表与顺序表、一表、一表等一样都是数据逻辑结构的存储表示。 5. 在一个链式队列中，若队头指针与队尾指针的值则表示该队列可能为空, 也可能只包含有1个结点。 6. 对于一棵具有n个结点的树，该树中所有结点的度数之和为 7. 在一棵高度为3的理想平衡二叉树中，最少含有个结点，最多含有 个结点。假定树根结点的高度为0。 8. 假定对长度n50的有序表进行折半搜索，则对应的判定树中最下一层的结点数为 个。 9. 用邻接矩阵存储图，占用的存储空间与图中的 数有关。 10. 第i（il,2,...,n-1）趟从参加排序的序列中取出第i个元素，把它插入到由第0 个至第i-1个元素组成的有序表中适当的位置，此种排序方法叫做排序。 11. 快速排序在平均情况下的时间复杂度和空间复杂度分别为 和 12. 假定对长度n100的线性表进行索引顺序搜索，并假定每个子表的长度均为 则进行索引顺序搜索的时间复杂度为 。 三、判断题，在每小题前面打对号表示正确或打叉号表示错误（每小题1分，共12分） 1. 数据的逻辑结构与数据元素本身的内容和形式无关。 2. 使用三元组表示稀疏矩阵中的非零元素能节省存储空间。 3. 在使用后缀表示实现表达式求值时用到一个栈的实例，它的作用是暂存运算对象和 中间计算结果。 4. 一个广义表的表头总是一个广义表。 5. 在一棵二叉树中，假定每个结点只有左子女，没有右子女，对它分别进行前序遍历 和按层遍历，则具有相同的结果。 6. 能够在链接存储的有序表上进行折半搜索，其时间复杂度与在顺序存储的有序表上 相同。 7. 邻接表只能用于有向图的存储，邻接矩阵对于有向图和无向图的存储都适用。 8. 在AOE网络中，可能同时存在几条关键路径，把所有关键路径都需通过的有向边称 为桥。如果加速这样的桥上的关键活动就能使整个工程提前完成。 9. 当输入序列已经基本有序时，起泡排序需要比较关键码的次数，比快速排序还要少。 10. 在索引顺序结构上实施分块搜索，在等概率情况下，其平均搜索长度不仅与子表个 数有关，而且与每一个子表中的对象个数有关。 11. 若有m个初始归并段参加k路平衡归并排序，则归并趟数应为「logdn]。 12. 向一棵B树插入关键码的过程中，若最终引起树根结点的分裂，则新树比原树的高 度减少1。 四、运算题（每小题6分，共30分） 1. 设有一个10 x10的矩阵A,将其下三角部分按行存放在一个一维数组B中，A[0] [0] 存放于B[0]中，那么A[8] [5]存放于B中什么位置。 A[8][5]在B中的存放位置 2. 已知棵树的静态双亲表示如下，其中用-1表示空指针，树根结点存于0号单元, 分别求出该树的叶子结点数、单分支结点数、两分支结点数和三分支结点数。 序号 012345678910 a b c d e f g h i J k -1 0 1 1 3 0 5 6 6 0 9 data parent 单分支结点数 叶子结点数 两分支结点数三分支结点数 3. 已知图GV,E,其中 V {a, b, c, d, e} c, d, d, e, e, a, e, c} 结点 出度 入度 a b c d e E{〈a, b〉，b, a, c, b, 请写出各结点的出度和入度。 4. 已知一个带权图的顶点集V和辿集G分别为 V{0, 1,2, 3, 4, 5, 6}; E {0, 1 19, 0, 2 10, 0, 3 14, 1, 2 6, 1, 5 5, 2, 3 26, 2, 4 15, 3, 4 18, 4,56, 4, 6 6, 5, 612}; 试根