河南电大数据结构期末复习题3

1．输出一个二维数组b[m][n]中所有元素的时间复杂度为( D )。 A．( ) (n) B．C．( ) (n2) D．( ) (m*n)( ) (m十n)2．在一个长度为n的顺序存储的有序表中搜索值为x元素时, 其时间效率最高的算法的时间复杂度为( C )。 A. ( )( 1 ) B. ( )( ) C. ( )() D. ( )( n )3．当利用大小为n的数组顺序存储一个栈时, 假定用top= =n表示栈空, 则向这个栈插入一个元素时, 首先应执行( B )语句修改top指针。 A．top++; B. top--; C．top=0; D．top; 4．在一棵树中, ( C )没有前驱结点。 A．树枝结点 B. 叶子结点 C. 树根结点 D．空结点5．已知一棵树的边集表示为{, , , , , , }, 则该树的深度为( B )。假定树根结点的深度为0。 A. 2 B. 3 C．4D．56．n个顶点的连通图中至少含有( A )条边。 A．n一1 B．n C．n(n-1)／2D. n(n一1)7．设无向图的顶点个数为n．则该图最多有( B )条边。 A．n一1 B．n(n一1)／2C．n(n+1)／2 D．n(n一1)8．在采纳开散列法解决冲突时, 每一个散列地址所链接的同义词子表中各个表项的( C)的值相同。 A. 关键码 B．非关键码 C. 散列函数 D．某个域9．散列函敷应该有这样的性质, 即函数值应当以( D )概率取其值域范围内的每--个值。 A．最大 B. 最小 C. 平均D．同等二、 填空题 1．面对对象的特征应包括对象、 类、 继承、 多态、 消息通信等。 2．在单链表中设置表头附加结点的作用是在插入和删除表中任一个元素时的操作都相同 3．若设顺序栈的最大容量为MaxSize, top==-l表示栈空, 则推断栈满的条件是top== MaxSixe一1 4．在一棵高度为5的完全二叉树中, 最多包含有 63 个结点。假定树根结点的高度为0。 5. 在一个最大堆中, 堆顶结点的值是所有结点中的最大值。 6．具有n个顶点的连通无向图的-棵生成树中含有 n - 1 条边。 7．在一棵5阶B树中, 每个结点最多含有 4 个关键码。三、 推断题 ( √ )1. 线性表若采纳链式存储表示, 在删除时不需要移动元素。 ( × )2．若让元素1, 2, 3依次进栈, 任何时候都允许元素出栈, 则出栈次序1, 3, 2是不可能出现的情况。 ( √ )3．一个广义表((a), ((h), c), (((d))))的长度为3, 深度为4。 ( × )4．二叉树是一棵无序树。 ( √ )5．对于关键码互不相同的一组记录, 若生成二叉搜索...