《东大18春学期《数据结构Ⅱ》在线作业123满分答案》由会员分享，可在线阅读，更多相关《东大18春学期《数据结构Ⅱ》在线作业123满分答案（36页珍藏版）》请在金锄头文库上搜索。
1、18 春学期数据结构在线作业 1 试卷总分:100 得分:100 第 1 题, 连通网的最小生成 树是其所有生成树中 A、 顶 点集最小的生成树 B、 边集最小的生成树 C、顶点权值之和最小的生成树D、 边的权值之和最小的生成树 正确答案:D第 2 题, 通常将链串的结点大小设置为大 于1是为了 A、提高串匹配效率 B、提高存储密度 C、便于插入操作D、便于删除操作 正确答案:B第 3 题, 设一个栈的输入序 列为A，B，C，D，则借助一个栈所得到的输出序列不可能是A、A，B，C，D B、D，C，B，A C、A，C，D，B D、D，A，B，C 正确答案:D第 4 题, 已知一组关键字为25,4
2、8,36,72,79,82,23,40,16,35，其中每相邻两个为有序子序列。对 这些子序列进行一趟两两归并的结果是 A、.25,36,48,72,23,40,79,82,16,35 B、.25,36,48,72,16,23,40,79,82,35 C、.25,36,48,72,16,23,35,40,79,82 D、.16,23,25,35,36,40,48,72,79,82 正确答案:D第 5 题, 在下列对顺序表进行的操作中，算法时间复杂度为O(1) 的是 A、访问第i个元素的前驱 B、在第i个元素之后插入一个新元素 C、删除第i个元素 D、对顺序表中元素进行排序 正确答案:A第 6
3、题, 下列编码中属于前缀编码的是 A、1,01,000,001 B、 1,01,011,010 C、0,10,110,11 D、 0,1,00,11 正确答案:A第 7 题, 按排序过程中依据的原则分类， 快速排序属于 A、插入类的排序方法 B、选择类的排序方法 C、交换类的排序方法 D、归并类的排序方法 正确答案:C第 8 题, ISAM文件和VSAM文件的区别之一是 A、前者是索引顺序 文件，后者是索引非顺序文件 B、 前者只能进行顺序存取，后者只能进行随机存取 C、前 者建立静态索引结构，后者建立动态索引结构 D、前者的存储介质是磁盘，后者的存储介质不是磁盘正确答案:C第 9 题, 设给
4、定权值总数 有n 个，其哈夫曼树的结点总数为 A、不确定 B、2n C、2n+1D、2n- 1 正确答案:D第 10 题, 设树T的度为4，其中度为 1，2，3和4的结点个数分别为4，2，1，1 则T中的叶子数为 A、5 B、6 C、7 D、8 正确答案:D第 11 题, 若有序表的关键字序列为（b,c,d,e,f,g,q,r,s,t） ，则在二 分查找关键字b的过程中，先后进行比较的关键字依次为 A、f,c,b B、f,d,b C、g,c,b D、g,d,b 正确答案:A第 12 题, 二叉树中第5层上的结点个数最多为 A、8 B、15 C、16 D、32 正确答案:C第 13 题, 若X是
5、二叉中序线索树中一个有左孩子的结点，且X不为根，则x的前驱为 A、X的双亲 B、X的右子树中 最左的结点 C、X的左子树中最右结点 D、X的 左子树中最右叶结点 正确答案:C第 14 题, 链栈与顺序栈相比，比较明显的优 点是 A、插入操作更加方便B、删除操作更加方便 C、不会出现下溢 的情况 D、不会出现上溢 的情况 正确答案:D第 15 题, 一棵完全二叉树上有1001个结点，其中叶子结点的个数是 A、250B、500 C、254D、以上答案都不对 正确答案:D第 16 题, 若数组s0.n-1为两个栈s1和 s2的共用存储空间，且仅当s0.n-1 全满时，各栈才不能进行进栈操作， 则为这
6、两个栈分配空间的最佳方案是：s1和s2的栈顶指针的初值分别为 A、1和n+1 B、1和n/2 C、1和n D、1和n+1 正确答案:C第 17 题, 二维数组A按行优先顺序存储，其中每个元素占1个存储单 元。若A1 1的存储地址为420，A3 3的存储 地址为446，则A5 5的存储地址为 A、470 B、471 C、472 D、473 正确答案:C第 18 题, 某带头结点的单链表的头 指针为head，判定该链表为非空的条件是 A、 head=NULL B、 head-next=NULL C、head!=NULL D、head-next!=NULL 正确答案:B第 19 题, 在头指针为he
7、ad且表长大于1的单循环链表中，指 针p指向表中某个结点，若p-next- next= head,则 A、 p指向头结点 B、 p指向尾结点 C、 p的直接后继是头结点 D、P的直接后继是尾结点 正确答案:D第 20 题, ISAM文件的周期性整理是为了空出 A、磁道索引 B、柱面索引 C、 柱面基本区 D、 柱面溢出区 正确答案:D【奥鹏】东北大学18 春学期数据结构在线作业 2 试卷总分:100 得分:100 第 1 题, 对有18个元素的有序表作二分查找，则查找A3 的比较序列的下标为 A、 1，2，3 B、 9，5，2，3 C、9，5，3 D、 9，4，2，3 正确答案:D第 2 题,
8、 算法分析的目的是 A、辨别数据结构的合理性B、评价算法的效率 C、研究算法中输入与输出 的关系D、鉴别算法的可读 性 正确答案:B第 3 题, 在任意一棵二叉树的前序序列和后序序列中，各叶子之间的相对次序关系 A、不一定相同 B、都相同 C、都不相同 D、互为逆序 正确答案:B第 4 题, 用有向无环图描述表达式(A+B)*(A+B)/A)，至少需要 顶点的数目为 A、5 B、6 C、8 D、9 正确答案:A第 5 题, 在关键字序列(12，23，34，45，56，67，78，89，91)中二分 查找关键字为45、89和12的结点时，所需进行的比较次数分别为 A、4，4，3 B、4，3，3
9、C、3，4，4 D、3，3，4 正确答案:B第 6 题, 在目标串T0.n-1=xwxxyxy中，对模式串P0.m-1=xy进行子串定位操作的结果是A、1B、2 C、3 D、5 正确答案:C第 7 题, 抽象数据类型的三个组成部分分别为 A、数据对象、数据关系和 基本操作 B、数据元素、逻辑结构和 存储结构 C、数据项、数据元素和数 据类型 D、数据元素、数据结构和 数据类型 正确答案:A第 8 题, 用二叉链表表示具有n个结点的二叉树时，值为空的指针域的个数为 A、n-1 B、n C、n+l D、2n 正确答案:C第 9 题, BFS算法可用来解决单源最短路径问题的条件是当各边上的权值 A、
10、均相等B、均互不相等 C、不一定相等 D、任意值 正确答案:A第 10 题, 一个具有1025个结点的二叉树的高h为A、11 B、10C、11至 1025之间 D、10至1024之间 正确答案:C第 11 题, 以下数据结构中，属于线性结构的是 A、广义表B、二叉树C、稀疏矩 阵 D、串 正确答案:A第 12 题, 下列排序算法中， 时间复杂度不受数据初始状态影响，恒为0(nlog2n)的 是 A、堆排序B、冒泡排序 C、直接选择排序 D、快速排序 正确答案:A第 13 题, 树有先根遍历和后 根遍历，树可以转化为对应的二叉树。下面的说法正确的是 A、树的后根 遍历与其对应的二叉树的后根遍历相
11、同 B、树的后根 遍历与其对应的二叉树的中根遍历相同 C、树的先根 遍历与其对应的二叉树的中根遍历相同 D、以上都不对 正确答案:B第 14 题, 数据元素及其关系在计算 机存储器内的表示，称为数据的 A、逻 辑结构 B、存 储结构 C、线性结构 D、非线性结构 正确答案:B第 15 题, 下面关于数据结构正确的说法是 A、一种数据类型B、数据的存储结构 C、一组性质相同的数据元 素的集合 D、相互之间存在一 种或多种特定关系的数据元素的集合 正确答案:D第 16 题, 在按层次遍历二叉树的算法中，需要借助的辅助数据结构是 A、队列 B、栈 C、线性表 D、有序表 正确答案:A第 17 题,
12、若以1234作为双端队列的输入序列，则既不能由 输入受限的双端队列得到，也不能由输出受限的双端队列得到的输出序列是A、1234 B、4132 C、4231 D、4213 正确答案:C第 18 题, 已知函数Sub(s,i,j) 的功能是返回串s中从第i 个字符起长度为j的子串，函数Scopy(s,t) 的功能为复制串t 到s。若字符串S=SCIENCESTUDY， 则调用函数Scopy(P,Sub(S,1,7)后得到 A、P=SCIENCE B、P=STUDY C、S=SCIENCE D、S=STUDY 正确答案:A第 19 题, 若vi, vj是有向图的一 条边，则称 A、 vi邻接于vj
13、B、 vj邻接于vi C、 vi和vj相互邻接 D、vi与vj不相邻接正确答案:B第 20 题, 算法的时间复杂度主要取决于 A、问题的规模 B、待处理数据的初态 C、难度 D、A和B 正确答案:A【奥鹏】东北大学18 春学期数据结构在线作业 3 试卷总分:100 得分:100 第 1 题, 已知一个散列表如图所示，其散列函数为H(key)=key11，采用二次探查法处理 冲突，则下一个插入的关键字49的地址为 A、2 B、3 C、8 D、9 正确答案:C第 2 题, 已知在一棵度为3的树中，度为2的结点数为4，度为 3的结点数为3，则该树中的叶子 结点数为 A、5 B、8 C、11 D、18
14、 正确答案:C第 3 题, 队列和栈的主要区别是 A、 逻辑结构不同 B、 存储结构不同 C、所包含的运算个数不同 D、 限定插入和删除的位置不同 正确答案:D第 4 题, 将两个各有n个元素的有序表归并成一个有序表，其最少的比较次数是A、nB、2n-1 C、2n D、n-1 正确答案:A第 5 题, 在一个单链表中，若删除*p结点的后继结点，则执行操作 A、 q=p-next;p-next=q-next;free(q); B、 p=p-next;p-next=p-next- next;free(p); C、p-next=q-next;free(p-next); D、 p=p-next-nex
15、t;free(p-next); 正确答案:A第 6 题, 引起循环队列队头位置发生变化的操作是 A、出队 B、入队 C、 取队头元素 D、 取队尾元素 正确答案:A第 7 题, 在分块索引的在顺序表中查找，算 法中采用的最佳技术是 A、穷举法 B、贪心法 C、分治法 D、分支限界法 正确答案:A第 8 题, 一棵树高为K的完全二叉树至少的结点是A、2k 1 B、2k-1 1 C、2k-1D、2k 正确答案:C第 9 题, ALV树是一种平衡的二叉排序树，树中任一结点 的 A、 左、右子树的高度均相同 B、左、右子树高 度差的绝对值不超过1 C、 左子树的高度均大于右子树的高度 D、 左子树的高
16、度均小于右子树的高度 正确答案:B第 10 题, 若以1234作为双端队列的输入序列，则既不能由输入受限的双端队列得到，也不能由输出受限的双端队列得到的输出序列是 A、1234 B、4132 C、4231 D、4213 正确答案:C第 11 题, 判断两个串大小的基本准则是A、两个串长度的大小 B、两个串中首字符的大小 C、两个串中大写字母的多少 D、对应的第一个不等字符的大小 正确答案:D第 12 题, 设p指向单链表中的一个结点，s指向待插入的结点，则下述程序段的功能是 s - next = p - next; p - next = s; t = p - data; p - data = s - data; s -data = t; A、结点p与结点s的数据域互换 B、在p所指结点的元素之前插入元素 C、在p所指结点的元素之后插入
