文档介绍：中央电大计算机科学与技术专业
数据结构(本科)试卷7
2003年7月已考
一、选择题(每小题1分,共10分)
在一个长度为n的顺序表的任一位置插入一个新元素的渐进时间复杂度为( )。
A. O(n) B. O(n/2) C. O(1) D. O(n2)
带头结点的单链表first为空的判定条件是:
A. first == NULL; B. first->link == NULL;
C. first->link == first; D. first != NULL;
当利用大小为n的数组顺序存储一个队列时,该队列的最大长度为( )。
A. n-2 B. n-1 C. n D. n+1
在系统实现递归调用时需利用递归工作记录保存实际参数的值。在传值参数情形,需为对应形式参数分配空间,以存放实际参数的副本;在引用参数情形,需保存实际参数的( ),在被调用程序中可直接操纵实际参数。
A. 空间 B. 副本 C. 返回地址 D. 地址
在一棵树中,( )没有前驱结点。
A. 分支结点 B. 叶结点 C. 树根结点 D. 空结点
在一棵二叉树的二叉链表中,空指针域数等于非空指针域数加( )。
A. 2 B. 1 C. 0 D. –1
对于长度为9的有序顺序表,若采用折半搜索,在等概率情况下搜索成功的平均搜索长度为( )的值除以9。
A. 20 B. 18 C. 25 D. 22
在有向图中每个顶点的度等于该顶点的( )。
A. 入度 B. 出度
C. 入度与出度之和 D. 入度与出度之差
在基于排序码比较的排序算法中,( )算法的最坏情况下的时间复杂度不高于O(nlog2n)。
A. 起泡排序 B. 希尔排序 C. 归并排序 D. 快速排序
当α的值较小时,散列存储通常比其他存储方式具有( )的查找速度。
A. 较慢 B. 较快 C. 相同
填空题(每小题1分,共10分)
二维数组是一种非线性结构,其中的每一个数组元素最多有_________个直接前驱(或直接后继)。
将一个n阶三对角矩阵A的三条对角线上的元素按行压缩存放于一个一维数组B中,A[0][0]存放于B[0]中。对于任意给定数组元素B[K],它应是A中第_________行的元素。
链表对于数据元素的插入和删除不需移动结点,只需改变相关结点的________域的值。
在一个链式栈中,若栈顶指针等于NULL则为________。
主程序第一次调用递归函数被称为外部调用,递归函数自己调用自己被称为内部调用,它们都需要利用栈保存调用后的_________地址。
在一棵树中,______结点没有后继结点。
一棵树的广义表表示为a (b (c, d (e, f), g (h) ), i (j, k (x, y) ) ),结点f的层数为______。假定根结点的层数为0。
在一棵AVL树(高度平衡的二叉搜索树)中,每个结点的左子树高度与右子树高度之差的绝对值不超过________。
n (n﹥0) 个顶点的无向图最多有________条边,最少有________条边。
在索引存储中,若一个索引项对应数据对象表中的一个表项(记录),则称此索引为________索引,若对应数据对象表中的若干个表项,则称此索引为________索引。