东北大学17春学期《数据结构Ⅰ》在线作业123答案
17春学期《数据结构Ⅰ》在线作业1一、单选题：
1. 已知一组关键字为{25,48,36,72,79,82,23,40,16,35}，其中每相邻两个为有序子序列。对这些子序列进行一趟两两归并的结果是 (满分:5)
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}
2. 为便于判别有向图中是否存在回路，可借助于 (满分:5)
A.广度优先搜索算法
B.最小生成树算法
C. 最短路径算法
D. 拓扑排序算法
3. 假设在构建散列表时，采用线性探测解决冲突。若连续插入的n个关键字都是同义词，则查找其中最后插入的关键字时，所需进行的比较次数为 (满分:5)
A. n-1
B. n
C. n+1
D. n+2
4. 一个含n个顶点和e条弧的有向图以邻接矩阵表示法为存储结构，则计算该有向图中某个顶点出度的时间复杂度为 (满分:5)
A. O(n)
B.O(e)
C. O(n+e)
D. O(n2)
5. 下列数据结构中，属于非线性数据结构的是 (满分:5)
A. 栈
B.队列
C.完全二叉树
D. 堆
6. 已知含10个结点的二叉排序树是一棵完全二叉树，则该二叉排序树在等概率情况下查找成功的平均查找长度等于 (满分:5)
A. 1.0
B. 2.9
C. 3.4
D. 5.5
7. 在长度为n的顺序表中删除第i个元素(1≤i≤n)时，元素移动的次数为 (满分:5)
A. n-i+1
B.i
C.i+1
D.n-i
8. 假设以数组A存放循环队列的元素，其头、尾指针分别为front和rear。若设定尾指针指向队列中的队尾 元素，头指针指向队列中队头元素的前一个位置，则当前存于队列中的元素个数为 (满分:5)
A. (rear-front-1)％n
B. (rear-front)％n
C. (front-rear+1)％n
D. (rear-front+n)％n
9. 从逻辑上可以把数据结构分为两大类，即 (满分:5)
A. 动态结构、静态结构
B. 顺序结构、链式结构
C. 线性结构、非线性结构
D. 初等结构、构造型结构
10. 设数组A为循环队列Q的存储空间，front为队头指针，rear为队尾指针，则判定Q为空队列的条件是 (满分:5)
A. (rear-front)%m= =1
B.front= =rear
C.(rear-front)%m= =m-1
D. front= =(rear+1)%m
11. 稠密索引是在索引表中 (满分:5)
A. 为每个记录建立一个索引项
B. 为每个页块建立一个索引项
C. 为每组记录建立一个索引项
D. 为每个字段建立一个索引项
12. 索引非顺序文件的特点是 (满分:5)
A.主文件无序，索引表有序
B.主文件有序，索引表无序
C.主文件有序，索引表有序
D. 主文件无序，索引表无序
13. 已知在一棵度为3的树中，度为2的结点数为4，度为3的结点数为3，则该树中的叶子结点数为 (满分:5)
A. 5
B. 8
C. 11
D. 18
14. 抽象数据类型的三个组成部分分别为 (满分:5)
A. 数据对象、数据关系和基本操作
B. 数据元素、逻辑结构和存储结构
C. 数据项、数据元素和数据类型
D. 数据元素、数据结构和数据类型
15. 一棵左右子树均不空的二叉树在先序线索化后，其中空的链域的个数是 (满分:5)
A. 0
B. 1
C. 2
D. 不确定
16. 除第一层外，满二叉树中每一层结点个数是上一层结点个数的 (满分:5)
A. 1/2倍
B.1倍
C. 2倍
D. 3倍
17. 下列说法正确的是 (1)二又树按某种方式线索化后，任一节点均有指向前趋和后继的线索 (2)二叉树的前序遍历序列中，任意一个节点均处于在子孙节点前 (3)二叉排序树中任一节点的值大于其左孩子的值，小于右孩子的值 (满分:5)
A.(1)(2)(3)
B.(1)(2)
C.(1)(3)
D. 前面的可选答案都不对
18. 在下列对顺序表进行的操作中，算法时间复杂度为O(1)的是 (满分:5)
A. 访问第i个元素的前驱
B. 在第i个元素之后插入一个新元素
C. 删除第i个元素
D.对顺序表中元素进行排序
19. 二叉树中第5层上的结点个数最多为 (满分:5)
A. 8
B. 15
C. 16
D. 32
20. 二维数组A的每个元素是由6个字符组成的串，其行下标i=0，l，…，8，列下标为j=1，2．…．10。设每个字符占一个字节,若按行先存储，元素A的起始地址与A按列存储时起始地址相同的元素是 (满分:5)
A. A
B. A
C. A
D. A
17春学期《数据结构Ⅰ》在线作业2
一、单选题：
1. 索引非顺序文件的特点是 (满分:5)
A.主文件无序，索引表有序
B.主文件有序，索引表无序
C.主文件有序，索引表有序
D. 主文件无序，索引表无序
2. 在计算机内实现递归算法时所需的辅助数据结构是 (满分:5)
A. 栈
B. 队列
C. 树
D. 图
3. 在一棵高度为k的满二叉树中，结点总数为 (满分:5)
A.2k-1
B. 2k
C. 2k-1
D. log2kû+1
4. ISAM文件和VSAM文件的区别之一是 (满分:5)
A.前者是索引顺序文件，后者是索引非顺序文件
B.前者只能进行顺序存取，后者只能进行随机存取
C.前者建立静态索引结构，后者建立动态索引结构
D.前者的存储介质是磁盘，后者的存储介质不是磁盘
5. 在VSAM文件的控制区间中，记录的存储方式为 (满分:5)
A.无序顺序
B.有序顺序
C.无序链接
D. 有序链接
6. 下列查找算法中，平均查找长度与元素个数n不直接相关的查找方法是 (满分:5)
A.分块查找
B.顺序查找
C.二分查找
D. 散列查找
7. 设p指向单链表中的一个结点，s指向待插入的结点，则下述程序段的功能是 s -> next = p -> next; p -> next = s; t = p -> data; p -> data = s -> data; s ->data = t; (满分:5)
A.结点p与结点s的数据域互换
B. 在p所指结点的元素之前插入元素
C.在p所指结点的元素之后插入元素
D. 在结点p之前插入结点s
8. 用有向无环图描述表达式(A+B)*((A+B)/A)，至少需要顶点的数目为 (满分:5)
A. 5
B. 6
C. 8
D. 9
9. 在图采用邻接表存储时，求最小生成树的 Prim 算法的时间复杂度为 (满分:5)
A. O(n)
B.O(n+e)
C. O(n2)
D. O(n3)
10. 一个含n个顶点和e条弧的有向图以邻接矩阵表示法为存储结构，则计算该有向图中某个顶点出度的时间复杂度为 (满分:5)
A. O(n)
B.O(e)
C. O(n+e)
D. O(n2)
11. 除第一层外，满二叉树中每一层结点个数是上一层结点个数的 (满分:5)
A. 1/2倍
B.1倍
C. 2倍
D. 3倍
12. 若数组s为两个栈s1和s2的共用存储空间，且仅当s全满时，各栈才不能进行进栈操作， 则为这两个栈分配空间的最佳方案是：s1和s2的栈顶指针的初值分别为 (满分:5)
A.1和n+1
B. 1和n/2
C. －1和n
D. －1和n+1
13. 设哈希表长为14，哈希函数H(key)=key％11，表中已有数据的关键字为15，38，61，84，四个，现将关键字为49的结点加到表中，用二次探测再散列法解决冲突，则放入的位置是 (满分:5)
A. 8
B. 3
C. 5
D. 9
14. 若i, vj>是有向图的一条边，则称 (满分:5)
A. vi邻接于vj
B. vj邻接于vi
C. vi和vj相互邻接
D. vi与vj­不相邻接
15. 在一个单链表中，已知q结点是p结点的前驱结点，若在q 和p之间插入结点s，则执行操作 (满分:5)
A.s->next=p->next;p->next=s;
B.s->next=p; q->next=s
C.q->next=s;s->next=p; D. p->next=s;s->next=q;
D.q->next=s;s->next=p; D. p->next=s;s->next=q;
16. 若度为m的哈夫曼树中，其叶结点个数为n，则非叶结点的个数为 (满分:5)
A. n-1
B. ën/mû-1
C.é(n-1)/(m-1)ù
D.én/(m-1)ù-1
17. 可有效提高次关键字查找效率的文件是 (满分:5)
A. 顺序文件
B.倒排文件
C. 散列文件
D. VSAM文件
18. 若一个有向图的邻接距阵中,主对角线以下的元素均为零,则该图的拓扑有序序列 (满分:5)
A. 一定存在
B. 一定不存在
C. 不一定存在
D. 不确定
19. 如果某图的邻接矩阵是对角线元素均为零的上三角矩阵，则此图是 (满分:5)
A. 有向完全图
B. 连通图
C. 强连通图
D.有向无环图
20. n个顶点的强连通图中至少含有 (满分:5)
A.n-1条有向边
B.n条有向边
C.n(n-1)/2条有向边
D. n(n-1)条有向边
17春学期《数据结构Ⅰ》在线作业3
一、单选题：转载请注明无忧答案网
1. 设哈希表长为14，哈希函数H(key)=key％11，表中已有数据的关键字为15，38，61，84，四个，现将关键字为49的结点加到表中，用二次探测再散列法解决冲突，则放入的位置是 (满分:5)
A. 8
B. 3
C. 5
D. 9
2. 根据数据元素的关键字直接计算出该元素存储地址的存储方法是 (满分:5)
A.顺序存储方法
B. 链式存储方法
C.索引存储方法
D. 散列存储方法
3. 一个含n个顶点和e条弧的有向图以邻接矩阵表示法为存储结构，则计算该有向图中某个顶点出度的时间复杂度为 (满分:5)
A. O(n)
B.O(e)
C. O(n+e)
D. O(n2)
4. 下面的叙述不正确的是 (满分:5)
A. 线性表在链式存储时，查找第i个元素的时间同i的值成正比
B.线性表在链式存储时，查找第i个元素的时间同i的值无关
C. 线性表在顺序存储时，查找第i个元素的时间同i 的值成反比
D. 线性表在顺序存储时，查找第i个元素的时间同i的值无关
5. 已知在一棵度为3的树中，度为2的结点数为4，度为3的结点数为3，则该树中的叶子结点数为 (满分:5)
A. 5
B. 8
C. 11
D. 18
6. 下面哪一方法可以判断出一个有向图是否有回路 (满分:5)
A. 深度优先遍历
B.求关键路径
C. 求最短路径
D.A和C
7. 顺序存储设计时，存储单元的地址 (满分:5)
A. 一定连续
B. 一定不连续
C. 不一定连续
D. 部分连续，部分不连续
8. 队列和栈的主要区别是 (满分:5)
A. 逻辑结构不同
B. 存储结构不同
C.所包含的运算个数不同
D.限定插入和删除的位置不同
9. 若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3，当从队列中删除一个元素， 再加入两个元素后，rear和front的值分别为 (满分:5)
A. 1和 5
B. 2和4
C.4和2
D.5和1
10. 高度为5的完全二叉树中含有的结点数至少为 (满分:5)
A. 16
B. 17
C. 31
D. 32
11. 若允许表达式内多种括号混合嵌套，则为检查表达式中括号是否正确配对的算法，通常选用的辅助结构是 (满分:5)
A. 栈
B. 线性表
C. 队列
D. 二叉排序树
12. 一棵完全二叉树上有1001个结点，其中叶子结点的个数是 (满分:5)
A. 250
B. 500
C. 254
D. 以上答案都不对
13. 设一个栈的输入序列为A，B，C，D，则借助一个栈所得到的输出序列不可能是 (满分:5)
A. A，B，C，D
B. D，C，B，A
C.A，C，D，B
D.D，A，B，C
14.数据结构中所定义的数据元素，是用于表示数据的 (满分:5)
A. 最小单位
B.最大单位
C.基本单位
D.不可分割的单位
15. 设数组A为循环队列Q的存储空间，front为队头指针，rear为队尾指针，则判定Q为空队列的条件是 (满分:5)
A. (rear-front)%m= =1
B.front= =rear
C.(rear-front)%m= =m-1
D. front= =(rear+1)%m
16. 计算机识别、存储和加工处理的对象被统称为 (满分:5)
A. 数据
B. 数据元素
C. 数据结构
D. 数据类型
17. 算法的时间复杂度主要取决于 (满分:5)
A. 问题的规模
B. 待处理数据的初态
C. 难度
D. A和B
18. 树的先根序列等同于与该树对应的二叉树的 (满分:5)
A.先序序列
B. 中序序列
C.后序序列
D. 层序序列
19. 在关键字序列(12，23，34，45，56，67，78，89，91)中二分查找关键字为45、89和12的结点时，所需进行的比较次数分别为 (满分:5)
A. 4，4，3
B. 4，3，3
C. 3，4，4
D. 3，3，4
20. 当在二叉排序树中插入一个新结点时，若树中不存在与待插入结点的关键字相同的结点，且新结点的关键字小于根结点的关键字，则新结点将成为 (满分:5)
A. A．左子树的叶子结点
B. B．左子树的分支结点
C. C．右子树的叶子结点
D. D．右子树的分支结点
页:
[1]