数据结构期末及.doc

E 卷一、单项选择题 1、线性表若采用链式结构时，要求内存中可用存储单元的地址( )。 A. 必须是连续的 B. 部分地址必须是连续的 C. 一定是不连续的 D. 连续不连续都可以 2、判定一个栈ST(最多元素为m0)为空的条件是( )。 A. ST-top!=0 B. ST-top==0 C. ST-top!=m0 D. ST-top==m0 3、数组A中，每个元素A的长度为3个字节，行下标i从1到8，列j下标从1到10，从首地址SA开始连续存放在存储器内，该数组按行存放时，元素A[8][5]的起始地址为( )。 A. SA+141 B. SA+144 C. SA+222 D. SA+225 4、设哈希表长m=14，哈希函数H(key)=key%11。表中已有4个结点： addr(15)=4 addr(38)=5 addr(61)=6 addr(84)=7 其余地址为空 如用二次探测再散列处理冲突，关键字为49的结点的地址是( )。 A. 8 B. 3 C. 5 D. 9 5、在线索化二叉树中，t所指结点没有左子树的充要条件是( )。 A. t-left==NULL B. t-ltag==1 C. t-ltag==1且t-left==NULL D. 以上都不对 6、将递归算法转换成对应的非递归算法时，通常需要使用( )。 A. 栈 B. 队列 C. 链表 D. 树 7、有一个有序表为{1,3,9,12,32,41,45,62,75,77,82,95,100},当二分查找值为82的结点时，( )次比较后查找成功。 A. 1 B. 2 C. 4 D. 8 8、对一个满二叉树，m个树叶，n个结点，深度为h，则( )。 A. n=h+m B. h+m=2n C. m=h-1 D. n=2h-1 9、如果要求一个线性表既能较快地查找，又能适应动态变化的要求，可以采用_____查找方法。 A. 分块 B. 顺序 C. 二分 D. 散列 10、快速排序方法在( )情况下最不利于发挥其长处。 A. 要排序的数据量太大 B. 要排序的数据中含有多个相同值 C. 要排序的数据已基本有序 D. 要排序的数据个数为奇数 11、在含有n个顶点和e条边的无向图的邻接矩阵中，零元素的个数为________. A.e B.2e C.-e D. -2e 12.假设一个有n个顶点和e条弧的有向图用邻接表表示，则删除与某个顶点相关的所有弧的时间复杂度是_________. A.O(n) B.O(e) C.O(n+e) D.O(n*e) 13. 用某种排序方法对关键字序列（25，84，21，47，15，27，68，35，20）进行排序时，序列的变化情况： 20，15，21，25，47，27，68，35，84 15，20，21，25，35，27，47，68，84 15，20，21，25，27，35，47，68，84 则所采用的排序方法是_________. A. 选择排序 B. 希尔排序 C. 归并排序 D. 快速排序 14. 适宜于对动态查找表进行高效率查找的组织结构是_____. A.有序表 B. 分块有序表 C. 三叉排序表 D.线性链表 15. 不定长文件是指__________. A. 文件的长度不固定 B.记录的长度不固定 C. 字段的长度不固定 D.关键字项的长度不固定 二、填空题 16、对数据间关系的描述是数据的逻辑结构，形式地可以用一个二元组 B=（D，R）来表示，其中D表示______