201309学期算法与数据结构作业4.doc

201309学期算法与数据结构作业4 单项选择题 第1题 栈和队列的共同特点是： A、只允许在端点处插入和删除元素 B、都是先进后出 C、都是先进先出 D、没有共同点 答案：A 第2题 以下数据结构中哪一个是非线性结构？ A、队列 B、栈 C、线性表 D、二叉树 答案：D 第3题 树最适合用来表示： A、有序数据元素 B、无序数据元素 C、元素之间具有分支层次关系的数据 D、元素之间无联系的数据 答案：C 第4题 若有18个元素的有序表存放在一维数组A[19]中，第一个元素放A[1]中，现进行二分查找，则查找A［3］的比较序列的下标依次为 A、1，2，3 B、9，5，2，3 C、9，5，3 D、9，4，2，3 答案：D 第5题 二叉树的第k层的结点数最多为： A、2k-1 B、2K+1 C、2K-1 D、2k-1 答案：D 第6题 用链接方式存储的队列，在进行插入运算时： A、仅修改头指针 头、尾指针都要修改 B、头、尾指针都要修改 C、仅修改尾指针 D、头、尾指针可能都要修改 答案：D 第7题 1. 设有一个二维数组A[m][n]，假设A[0][0]存放位置在644(10) ，A[2][2]存放位置在676(10) ，每个元素占一个空间，问A[3][3](10)存放在什么位置？脚注(10)表示用10进制表示。 A、688 B、678 C、692 D、696 答案：C 多项选择题 第8题 下列排序算法中哪些是不稳定的(): A、昌泡排序 B、选择排序 C、快速排序 D、堆排序 答案：B|C|D 第9题 图的邻接矩阵存贮结构包括(): A、表示图中顶点间相邻关系的矩阵 B、对称矩阵 C、表示图中顶点元素的数组 D、表示入度的数组 E、表示出度的数组 答案：A|C 第10题 假设有二维数组a[m][n]，如果在内存中以行优先方式存贮。下述计算数据元素a[i][j]地址loc(a[i][j])的公式中哪些是正确的(): A、loc(a[i][j]) = l0 +(m * j + i )*k , 其中k为每个元素所占的存贮单元，l0为a[0][0]的地址，并且假定数组下标的起始值为0 B、loc(a[i][j]) = l0 +(i*n +j )*k , 其中k为每个元素所占的存贮单元，l0为a[0][0]的地址，并且假定数组下标的起始值为0 C、loc(a[i][j]) = l0 +((i-1)*n +j －1)*k , 其中k为每个元素所占的存贮单元，l0为a[0][0]的地址，并且假定数组下标的起始值为1 D、loc(a[i][j]) = l0 +((m-1) *j + i)*k , 其中k为每个元素所占的存贮单元，l0为a[0][0]的地址，并且假定数组下标的起始值为0 答案：B|C 第11题 假设以链表的方式实现堆栈，top为栈顶指针，类型为linkstack结点分别以data和next表示数据域与链域，datatype表示栈内元素的数据类型。下述程序实现出栈操作。判断哪一段程序是错误的(): A、datatype pop( linkstack *top ){ linkstack * p ; if ( top == NULL ) { ERROR(“underflow”); Return NULL; } else { p = top; top = top-next; x = p-data; free(p); return x; } } B、datatype pop( linkstack *top ){ linkstack * p ; p = top; top = top-next; x = p-data; free(p); return x; } C、datatype pop( linkstack *top ){ linkstack * p ; if ( top == NULL ) { ERROR(“underflow”); Return NULL; } else { p = top; top = top-next; return p-data; } D、void pop( linkstack *top ){ linkstack * p ; if ( top == NULL ) { ERROR(“underflow”); Return NULL; } else { p = top; top = top-next; x = p-data; } } 答案：B|C|D