计算机科学与技术专业数据结构试题(4)
2005年上学期已考试卷 计算机科学与技术专业数据结构试题(4) 2003年5月 题号 一 二 三 四 五 六 总分 得分 一、单项选择题,在括号内填写所选择的标号(每小题1分,共12分) 1. 执行下面程序段时,S语句的执行次数为()。 for (int i=l: ilink; 6. 设有一个广义表A (a),其表尾为( A. aB.(()) B. top=top-〉link; x=top-〉data; D. x=top-〉data; )o C. ()D. (a) 7. 在一棵具有n个结点的完全二叉树中,树枝结点的最大编号为()。假定树根结 点的编号为0。 A. (n-l)/2 B. n/2 C. n/2+1 D. n/2-1 8. 若搜索每个元素的概率相等,则在长度为n的顺序表上搜索任一元素的平均搜索长 度为( )o A. nB. n+1 C. (n-l)/2 D. (n+l)/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. 假定对长度n=50的有序表进行折半搜索,则对应的判定树中最下一层的结点数为 个。 9. 用邻接矩阵存储图,占用的存储空间与图中的 数有关。 10. 第i(i=l,2,.,n-1)趟从参加排序的序列中取出第i个元素,把它插入到由第0 个至第i-1个元素组成的有序表中适当的位置,此种排序方法叫做―—排序。 11. 快速排序在平均情况下的时间复杂度和空间复杂度分别为 和 12. 假定对长度n=100的线性表进行索引顺序搜索,并假定每个子表的长度均为 则进行索引顺序搜索的时间复杂度为 。 三、判断题,在每小题前面打对号表示正确或打叉号表示错误(每小题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. 已知图G=(V,E),其中 V= {a, b, c, d, e} , , , } 结点 出度 入度 a b c d e E={〈a, 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,5)6, (4, 6) 6, (5, 6)12}; 试根