北航201303学期算法与数据结构答案作业4.doc

作业4 单项选择题 第1题 假设有对角矩阵a[n][n]，我们可以按行序为主将对角矩阵A的非零元素存入一个一维数组B[K]中。给出二维数组的任一元素a[i][j]与一维数组B[K]对应的下标m的关系：（）。 A、k = 2*i + j B、k = 2 * j + i C、k = 3* (i + j ) D、k = i + j 答案：A 第2题 假设有对称矩阵a[n][n]，我们可以按行序为主将对称矩阵Ａ的下三角中的元素存入一个一维数组Ｂ［Ｋ］（Ｋ＝ｎ（ｎ＋１）／２）中。给出二维数组的任一元素a[i][j]与一维数组B[K]对应的下标m的关系：（）。 A、(i-1)*(j+1)=k B、(i+1)*(j+1)=k C、(i-1)*j=k D、i*(j+1)=k 答案：A 第3题 假定M行N列的数组a是行优先存贮的，L是元素a[0][0]的存贮地址，每个元素占K个存贮单元，元素a[I][j]的地址是：（）。 A、L + (I – 1)* N * K +j*K B、L +( I * N +j)*K C、( I * N * K + (J – 1) *K D、L +( I * M +j) * K 答案：B 第4题 对给定的图，Prim方法与Kruskal方法都能给出最小代价生成树，针对最小代价生成树的算法，下面的说法哪一个是正确的：（）。 A、Prim方法与Kruskal方法均不需要进行圈的判断 B、Prim方法与Kruskal方法都需要进行圈的判断 C、Prim方法需要进行圈的判断，Kruskal方法不需要进行圈的判断 D、Prim方法不需要进行圈的判断，Kruskal方法需要进行圈的判断 答案：D 多项选择题 第5题 假定以单向链表方式存贮堆栈，栈顶指针变量为p，表示栈空时，下面的说法哪一个是正确的(): A、p==-1 B、p==0 C、p==NULL D、p != NULL 答案：B|C 第6题 下述陈述中哪一项是正确的(): A、文件中能唯一标识一个记录的数据项称之为主关键字 B、文件中能唯一标识一个记录的数据项组合称之为主关键字 C、文件中能标识一个记录的数据项称之为主关键字 D、文件中能标识一个记录的数据项组合称之为主关键字 答案：A|B 第7题 常用的线性表存贮结构有(): A、顺序存贮结构 B、链表存贮结构 C、队列存贮结构 D、堆栈存贮结构 E、顺序存贮与链表存贮混合结构 答案：A|B|E 第8题 常用的堆栈存贮结构有(): A、顺序存贮结构 B、链表存贮结构 C、顺序存贮与链表存贮混合结构 D、指针存贮结构 答案：A|B 判断题 第9题 空串是打印后不出现任何字符的字符器。 答案：错误 第10题 静态查找就是顺序查找、折半查找和分块查找。 答案：错误 第11题 快速排序是稳定的。 答案：错误 第12题 将左边的树转换为二叉树，右边的结果是否正确。 答案：正确 填空题 第13题 算法的五个重要特性分别是：有穷性，___，可行性，有输入，有输出。 答案：确定性 第14题 数据对象的结构分___和非线性结构二种。 答案：线性结构 第15题 排序分为内部排序和___。 答案：外部排序 第16题 内部排序的效率需要考虑数据的比较与移动次数，外部排序的效率的度量中，除考虑比较和移动次数外，还要考虑___。 答案：内外存之间的交换次数 问答题 第17题 描述堆排序的处理过程。 答案：堆排序的处理过程是：首先建立初始堆，此时根节点为整个序列最大元素（最小元素），然后将根结点与最后一个叶子结点元素交换，再将除交换后的叶子点外的剩余元素所组成的序列重新调整成堆，重复上述过程，直到所有元素都已处理结束。 第18题 描述数据对象物理结构与逻辑结构的概念。 答案：逻辑结构是数据对象固有的、表示数据及其彼此之间的关系，物理结构是数据对象的元素及其关系在计算机内的存贮方法。 第19题 论述堆排序中堆的概念。 答案：在堆排序中，堆是指如果n个关键字序列（r1,r2,…,m），以r1为根将关键字序列构成完全二叉树，且完全二叉树中所有非终端结点的值不大于（或不小于）其左右孩子结点的值，即：ri≤r2i, ri≤r2i+1或ri≥r2i, ri≥r2i+1。由此r1必为序列中的最小值或最大值，分别称满足上诉关系的序列为小根堆或大根堆。 第20题 描述快速排序的处理过程。 答案：快速排序是对昌泡排序的一种改进，其处理过程是：取出某一记录，以该记录所对应的