201309201309 学期算法与数据结构作业学期算法与数据结构作业 4 4单项选择题单项选择题 第 1 题 栈和队列的共同特点是： A、只允许在端点处插入和删除元素 B、都是先进后出 C、都是先进先出 D、没有共同点 答案：A 第 2 题 以下数据结构中哪一个是非线性结构？ A、队列 B、栈 C、线性表 D、二叉树 答案：D 第 3 题 树最适合用来表示： A、有序数据元素 B、无序数据元素 C、元素之间具有分支层次关系的数据 D、元素之间无联系的数据 答案：C 第 4 题 若有 18 个元素的有序表存放在一维数组 A19中，第一个元素放 A1中，现进行二 分查找，则查找 A3的比较序列的下标依次为 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. 设有一个二维数组 Amn，假设 A00存放位置在 644(10) ，A22存放位置 在 676(10) ，每个元素占一个空间，问 A33(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 题 假设有二维数组 amn，如果在内存中以行优先方式存贮。下述计算数据元素 aij地址 loc(aij)的公式中哪些是正确的(): A、loc(aij) = l0 +(m * j + i )*k , 其中 k 为每个元素所占的存贮单元，l0 为 a00的地址， 并且假定数组下标的起始值为 0 B、loc(aij) = l0 +(i*n +j )*k , 其中 k 为每个元素所占的存贮单元，l0 为 a00的地址，并 且假定数组下标的起始值为 0 C、loc(aij) = l0 +(i-1)*n +j 1)*k , 其中 k 为每个元素所占的存贮单元，l0 为 a00的地 址，并且假定数组下标的起始值为 1 D、loc(aij) = l0 +(m-1) *j + i)*k , 其中 k 为每个元素所占的存贮单元，l0 为 a00的地址， 并且假定数组下标的起始值为 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 第 12 题 假设以链表的方式实现堆栈，top 为栈顶指针，类型为 linkstack 的结点分别以 data 和 next 表示数据域与链域，datatype 表示栈内元素的数据类型。下述程序实现查看栈 顶元素的操作。判断哪一段程序是错误的(): A、datatype GetTop(linkstack * top) if ( EMPTYSTACK(top) error(“stack is empty!”); else return top-data; B、datatype GetTop(linkstack * top) return top-data; C、datatype GetTop(linkstack * top) if ( EMPTYSTACK(top) error(“stack is empty!”); else p = top; top = top-next; x = p-data; free(p); return x; D、datatype GetTop(linkstack * top) if ( ！EMPTYSTACK(top) return top-data; 答案：B|C 第 13 题 常用的线性表存贮结构有(): A、顺序存贮结构 B、链表存贮结构 C、队列存贮结构 D、堆栈存贮结构 E、顺序存贮与链表存贮混合结构 答案：A|B|E 第 14 题 下述陈述中哪一项是正确的(): A、文件中能唯一标识一个记录的数据项称之为主关键字 B、文件中能唯一标识一个记录的数据项组合称之为主关键字 C、文件中能标识一个记录的数据项称之为主关键字 D、文件中能标识一个记录的数据项组合称之为主关键字 答案：A|B 第 15 题 稀疏矩阵的存贮结构要满足哪些条件？() A、每个非零元素存贮其行号、列号以及值 B、存贮矩阵的行数和列数 C、所有的非零元素以行优先的排列规则存贮 D、只存贮上三角的元素 E、只存贮下三角的元素 答案：A|B|C 第 16 题 假设有三角矩阵 ann，对角线及对角线以上的元素非零，对角线以下的元素为 0。如果采用压缩存贮，即只存贮矩阵中的上三角元素和既存贮上三角元素又存贮 0 两种情 况下，所需要的存贮空间的分别容量为()和()。 A、n*(n+1)/2, n*(n+1)/2 + 1 B、n*(n+1)/2, n*n C、(n+1)n/2, (n+1)n/2 + 1 D、n(n-1)/2, n*(n-1)/2 + 1 答案：A|C 第 17 题 假设以链表的方式实现堆栈，top 为栈顶指针，指向类型为 linkstack 类型，下述 程序实现将堆栈初始化为空栈的操作。判断哪一段程序是正确的(): A、void INITSTACK( linkstack *top ) top = NULL; B、void INITSTACK(linkstack * top ) top = 1; C、void INITSTACK(linkstack * top ) top = 0; D、void INITSTACK(linkstack * top ) top = 空; 答案：A|C 第 18 题 假设以链表的方式实现堆栈，top 为栈顶指针，类型为 linkstack 的结点分别以 data 和 next 表示数据域与链域，其中 datatype 为栈内元素的数据类型， 。下述程序实现将 元素 x 压入链顶的操作。判断哪一段程序是正确的(): A、void push( linkstack *top, datatype x ) linkstack * p ; p = malloc(sizeof(linkstack); p-data = x; p-next = top; top = p; B、void pushstack( linkstack *top, datatype x ) linkstack * p ; p = malloc(sizeof(linkstack); p- data = x; p-next = top; top = p; C、void push( linkstack *top, datatype x ) p-data = x; p-next = top; top = p; D、void push( linkstack *top, datatype x ) top-data = x; top-next = top; 答案：A|B 第 19 题 假定以单向链表方式存贮堆栈，栈顶指针变量为 p，表示栈空时，下面的说法哪 一个是正确的(): A、p=-1 B、p=0 C、p=NULL D、p != NULL 答案：B|C 第 20 题 常用的堆栈存贮结构有(): A、顺序存贮结构 B、链表存贮结构 C、顺序存贮与链表存贮混合结构 D、指针存贮结构 答案：A|B