东北大学17春学期《数据结构Ⅱ》在线作业123答案
17春学期《数据结构Ⅱ》在线作业1转载请注明无忧答案网
一、单选题：
1. 若以1234作为双端队列的输入序列，则既不能由输入受限的双端队列得到，也不能由输出受限的双端队列得到的输出序列是 (满分:5)
A. 1234
B. 4132
C. 4231
D. 4213
2. 在计算机内实现递归算法时所需的辅助数据结构是 (满分:5)
A. 栈
B. 队列
C. 树
D. 图
3. 设有一个顺序栈，6个元素1、2 、3、4、5、6依次入栈，如果6个元素出栈的顺序是2、3、4、6、5、1，则栈的容量至少应该是 (满分:5)
A. 2
B. 3
C. 5
D. 6
4. 在以单链表为存储结构的线性表中，数据元素之间的逻辑关系用 (满分:5)
A. 数据元素的相邻地址表示
B. 数据元素在表中的序号表示
C. 指向后继元素的指针表示
D. 数据元素的值表示
5. 一棵左右子树均不空的二叉树在先序线索化后，其中空的链域的个数是 (满分:5)
A. 0
B. 1
C. 2
D. 3
6. 多维数组之所以有行优先顺序和列优先顺序两种存储方式是因为 (满分:5)
A. 数组的元素处在行和列两个关系中
B. 数组的元素必须从左到右顺序排列
C. 数组的元素之间存在次序关系
D. 数组是多维结构，内存是一维结构
7. 在单链表中，指针p指向元素为x的结点，实现“删除x的后继”的语句是 (满分:5)
A. p=p->next;
B. p->next=p->next->next;
C. p->next=p;
D. p=p->next->next;
8. 适宜进行批量处理的文件类型是 (满分:5)
A.顺序文件
B. 索引顺序文件
C. 散列文件
D. 多关键字文件
9. 稠密索引是在索引表中 (满分:5)
A.为每个记录建立一个索引项
B.为每个页块建立一个索引项
C.为每组记录建立一个索引项
D. 为每个字段建立一个索引项
10. 一棵具有 n个结点的完全二叉树的树高度（深度）是 (满分:5)
A. ëlognû+1
B. logn+1
C. ëlognû
D. logn-1
11. 如果求一个连通图中以某个顶点为根的高度最小的生成树，应采用 (满分:5)
A. 深度优先搜索算法
B. 广度优先搜索算法
C. 求最小生成树的prim算法
D. 拓扑排序算法
12. 采用ISAM或VSAM组织的文件是 (满分:5)
A.索引非顺序文件
B. 顺序文件
C. 索引顺序文件
D.散列文件
13. 三维数组A按行优先存储方法存储在内存中，若每个元素占2个存储单元，且数组中第一个元素的存 储地址为120，则元素A［３］的存储地址为 (满分:5)
A. 356
B. 358
C. 360
D. 362
14. 索引非顺序文件的特点是 (满分:5)
A. 主文件无序，索引表有序
B. 主文件有序，索引表无序
C. 主文件有序，索引表有序
D. 主文件无序，索引表无序
15. 如果在数据结构中每个数据元素只可能有一个直接前驱，但可以有多个直接后继，则该结构是 (满分:5)
A. 栈
B. 队列
C. 树
D. 图
16. 对长度为15的有序顺序表进行二分查找，在各记录的查找概率均相等的情况下，查找成功时所需进行的关键字比较次数的平均值为 (满分:5)
A. 39/15
B. 49/15
C. 51/15
D. 55/15
17. 队列和栈的主要区别是 (满分:5)
A.逻辑结构不同
B.存储结构不同
C. 所包含的运算个数不同
D.限定插入和删除的位置不同
18. 若允许表达式内多种括号混合嵌套，则为检查表达式中括号是否正确配对的算法，通常选用的辅助结构是 (满分:5)
A. 栈
B. 线性表
C. 队列
D. 二叉排序树
19. 设顺序存储的线性表共有123个元素，按分块查找的要求等分成3块。若对索引表采用顺序查找来确定块，并在确定的块中进行顺序查找，则在查找概率相等的情况下，分块查找成功时的平均查找长度为 (满分:5)
A. 21
B. 23
C. 41
D. 62
20. 设一个栈的输入序列为12345，则借助一个栈所得到的输出序列不可能是 (满分:5)
A. 23415
B. 54132
C. 23145
D. 15432
17春学期《数据结构Ⅱ》在线作业2
一、单选题：
1. 对有18个元素的有序表作二分查找，则查找A的比较序列的下标为 (满分:5)
A.1，2，3
B.9，5，2，3
C. 9，5，3
D.9，4，2，3
2. 引起循环队列队头位置发生变化的操作是 (满分:5)
A. 出队
B. 入队
C. 取队头元素
D. 取队尾元素
3. 若要在O(1)的时间复杂度上实现两个循环链表头尾相接，则应对两个循环链表各设置一个指针，分别指向 (满分:5)
A. 各自的头结点
B. 各自的尾结点
C. 各自的第一个元素结点
D. 一个表的头结点，另一个表的尾结点
4. for（i=0；i；i++） for（j=0；j；j++）c［i］［j］=0；for（i=0；i；i++）for（j=0；j；j++）for（k=0；k；k++）c［i］［j］=c［i］［j］+a［i］［k］*b［k］［j］； 上列程序的时间复杂度为 (满分:5)
A.O（m+n×t）
B.O（m+n+t）
C.O（m×n×t）
D.O（m×t+n）
5. 希尔排序的增量序列必须是 (满分:5)
A. 递增的
B. 随机的
C. 递减的
D. 非递减的
6. 一棵左子树为空的二叉树在先序线索化后，其中空的链域的个数是 (满分:5)
A. 不确定
B. 0
C. 1
D. 2
7. 下列关键字序列中，构成小根堆的是 (满分:5)
A. {84，46，62，41，28，58，15，37}
B. {84，62，58，46，41，37，28，15}
C. {15，28，46，37，84，41，58，62}
D. {15，28，46，37，84，58，62，41}
8. 从广义表LS＝（(p, q), r, s）中分解出原子q的运算是 (满分:5)
A. tail(head(LS))
B. head(tail(head(LS)))
C. head(tail(LS))
D. tail(tail(head(LS)))
9. 假设以数组A存放循环队列的元素，其头、尾指针分别为front和rear。若设定尾指针指向队列中的队尾元素，头指针指向队列中队头元素的前一个位置，则当前存于队列中的元素个数为 (满分:5)
A. (rear-front-1)％n
B.(rear-front)％n
C. (front-rear+1)％n
D. (rear-front+n)％n
10. 一个含n个顶点和e条弧的有向图以邻接矩阵表示法为存储结构，则计算该有向图中某个顶点出度的时间复杂度为 (满分:5)
A. O(n)
B. O(e)
C. O(n+e)
D. O(n2)
11. 从逻辑上可以把数据结构分为两大类，即 (满分:5)
A. 动态结构、静态结构
B. 顺序结构、链式结构
C. 线性结构、非线性结构
D. 初等结构、构造型结构
12. 带行表的三元组表是稀疏矩阵的一种 (满分:5)
A.顺序存储结构
B. 链式存储结构
C. 索引存储结构
D. 散列存储结构
13. 采用ISAM或VSAM组织的文件是 (满分:5)
A.索引非顺序文件
B. 顺序文件
C. 索引顺序文件
D.散列文件
14. 执行下列程序段后，串X的值为 S=〞abcdefgh〞; T=〞xyzw〞; substr(X,S,2,strlen(T)); substr(Y,S, stelen(T),2); strcat(X,Y); (满分:5)
A. 〞cdefgh〞
B. 〞cdxyzw〞
C. "defxy〞
D. 〞cdefef〞
15. 判断两个串大小的基本准则是 (满分:5)
A. 两个串长度的大小
B. 两个串中首字符的大小
C. 两个串中大写字母的多少
D. 对应的第一个不等字符的大小
16. 已知输入序列为abcd 经过输出受限的双向队列后能得到的输出序列有 (满分:5)
A.dacb
B. cadb
C. bdac
D. 以上答案都不对
17. 若在9阶B-树中插入关键字引起结点分裂，则该结点在插入前含有的关键字个数为 (满分:5)
A. 4
B. 5
C. 8
D. 9
18. 在平衡二叉树中插入一个结点后引起了不平衡，设最低(最接近于叶子)的不平衡点是A，并已知A的左、右孩子的平衡因子分别为-1和0，则应进行的平衡旋转是 (满分:5)
A. LL型
B. LR型
C. RL型
D. RR型
19. 对于顺序存储的线性表，访问结点和增加、删除结点的时间复杂度为 (满分:5)
A. O(n) O(n)
B. O(n) O(1)
C. O(1) O(n)
D. O(1) O(1)
20. 下列程序段 for(i=1;i的时间复杂度是 (满分:5)
A. O(1)
B. O(0)
C. O(1+n)
D. O(n)
17春学期《数据结构Ⅱ》在线作业3
一、单选题：
1. n个顶点的强连通图中至少含有 (满分:5)
A.n-1条有向边
B. n条有向边
C. n(n-1)/2条有向边
D. n(n-1)条有向边
2. 在线性表的下列运算中，不改变数据元素之间结构关系的运算是 (满分:5)
A. 插入
B. 删除
C. 排序
D. 查找
3. 如果求一个连通图中以某个顶点为根的高度最小的生成树，应采用 (满分:5)
A. 深度优先搜索算法
B. 广度优先搜索算法
C. 求最小生成树的prim算法
D. 拓扑排序算法
4. 已知含10个结点的二叉排序树是一棵完全二叉树，则该二叉排序树在等概率情况下查找成功的平均查找长度等于 (满分:5)
A. 1.0
B. 2.9
C. 3.4
D. 5.5
5. 下列查找算法中，平均查找长度与元素个数n不直接相关的查找方法是 (满分:5)
A. 分块查找
B. 顺序查找
C. 二分查找
D. 散列查找
6. 若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则节省时间的存储方式是 (满分:5)
A. 顺序表
B. 双链表
C. 带头结点的双循环链表
D. 单循环链表
7. 栈的两种常用存储结构分别为 (满分:5)
A. 顺序存储结构和链式存储结构
B. 顺序存储结构和散列存储结构
C. 链式存储结构和索引存储结构
D. 链式存储结构和散列存储结构
8. 连通图是指图中任意两个顶点之间 (满分:5)
A.都连通的无向图
B.都不连通的无向图
C.都连通的有向图
D.都不连通的有向图
9. 一个有向无环图的拓扑排序序列是 (满分:5)
A. 一定唯一的
B. 一定不唯一的
C. 不一定唯一的
D. 都不对
10. 下面哪一方法可以判断出一个有向图是否有回路 (满分:5)
A. 深度优先遍历
B. 求关键路径
C. 求最短路径
D. A和C
11. 可有效提高次关键字查找效率的文件是 (满分:5)
A. 顺序文件
B. 倒排文件
C. 散列文件
D. VSAM文件
12. 通常将链串的结点大小设置为大于1是为了 (满分:5)
A. 提高串匹配效率
B. 提高存储密度
C. 便于插入操作
D. 便于删除操作
13. 在单链表中，指针p指向元素为x的结点，实现“删除x的后继”的语句是 (满分:5)
A. p=p->next;
B. p->next=p->next->next;
C. p->next=p;
D. p=p->next->next;
14. 已知一棵含50个结点的二叉树中只有一个叶子结点，则该树中度为1的结点个数为 (满分:5)
A. 0
B. 1
C. 48
D. 49
15. ISAM文件和VSAM文件的区别之一是 (满分:5)
A. 前者是索引顺序文件，后者是索引非顺序文件
B. 前者只能进行顺序存取，后者只能进行随机存取
C. 前者建立静态索引结构，后者建立动态索引结构
D. 前者的存储介质是磁盘，后者的存储介质不是磁盘
16. 对关键字序列(56，23，78，92，88，67，19，34)进行增量为3的一趟希尔排序的结果为 (满分:5)
A. (19，23，56，34，78，67，88，92)
B. (23，56，78，66，88，92，19，34)
C.(19，23，34，56，67，78，88，92)
D. (19，23，67，56，34，78，92，88)
17. 无向图中一个顶点的度是指图中 (满分:5)
A.通过该顶点的简单路径数
B.与该顶点相邻接的顶点数
C.通过该顶点的回路数
D.与该顶点连通的顶点数
18. 下列说法正确的是 (1)二又树按某种方式线索化后，任一节点均有指向前趋和后继的线索 (2)二叉树的前序遍历序列中，任意一个节点均处于在子孙节点前 (3)二叉排序树中任一节点的值大于其左孩子的值，小于右孩子的值 (满分:5)
A.(1)(2)(3)
B.(1)(2)
C.(1)(3)
D. 前面的可选答案都不对
19. 对二叉树从1开始进行连续编号，要求每个结点的编号大于其左右孩子的编号，同一个结点的左右孩子中，其左孩子的编号小于其右孩子的编号，则可采用遍历方式是 (满分:5)
A. 先序
B. 中序
C. 后序
D. 从根开始的层次遍历
20. 在一个单链表中，已知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;
页:
[1]