东北大学17秋《数据结构Ⅱ》在线作业123标准答案参考
17秋学期《数据结构Ⅱ》在线作业1一、单选题:【20道,总分:100分】
1. 若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行，则不可能出现的出栈序列是 (满分:5)
A. 2，4，3，1，5，6 B. 3，2，4，1，6，5
C. 4，3，2，1，5，6 D. 2，3，5，1，6，4
2.已知广义表LS=((a，b，c)，(d，e，f))，运算head和tail函数取出元素e的运算是 (满分:5)
A.head(tail(LS))
B. tail(head(LS))
C. head(tail(head(tail(LS))))
D. head(tail(tail(head(LS))))
3. 有关二叉树下列说法正确的是 (满分:5)
A. 二叉树的度为2
B. 一棵二叉树的度可以小于2
C. 二叉树中至少有一个结点的度为2
D. 二叉树中任何一个结点的度都为2
4. 假设以数组A存放循环队列的元素。已知队列的长度为length，指针rear指向队尾元素的下一个存储位置，则队头元素所在的存储位置为 (满分:5)
A.(rear-length+m+1)％m
B.(rear-length+m)％m
C.(rear-length+m-1)％m
D.(rear-length)％m
5. 若在9阶B-树中插入关键字引起结点分裂，则该结点在插入前含有的关键字个数为 (满分:5)
A. 4
B. 5
C. 8
D. 9
6. 已知一个有向图如右所示，则从顶点a出发进行深度优先偏历，不可能得到的DFS序列为 (满分:5)
A. a d b e f c
B. a d c e f b
C. a d c b f e
D. a d e f c b
7. 假设以数组A存放循环队列的元素，其头、尾指针分别为front和rear。若设定尾指针指向队列中的队尾元素，头指针指向队列中队头元素的前一个位置，则当前存于队列中的元素个数为 (满分:5)
A. (rear-front-1)％n
B.(rear-front)％n
C. (front-rear+1)％n
D. (rear-front+n)％n
8. 一个具有1025个结点的二叉树的高h为 (满分:5)
A. 11
B. 10
C. 11至1025之间
D. 10至1024之间
9. 在单链表中，指针p指向元素为x的结点，实现“删除x的后继”的语句是 (满分:5)
A. p=p->next;
B. p->next=p->next->next;
C. p->next=p;
D. p=p->next->next;
10. 下面的叙述不正确的是 (满分:5)
A. 线性表在链式存储时，查找第i个元素的时间同i的值成正比
B. 线性表在链式存储时，查找第i个元素的时间同i的值无关
C. 线性表在顺序存储时，查找第i个元素的时间同i 的值成反比
D.线性表在顺序存储时，查找第i个元素的时间同i的值无关
11. 如果某图的邻接矩阵是对角线元素均为零的上三角矩阵，则此图是 (满分:5)
A. 有向完全图
B. 连通图
C. 强连通图
D. 有向无环图
12. 在VSAM文件的控制区间中，记录的存储方式为 (满分:5)
A. 无序顺序
B. 有序顺序
C. 无序链接
D. 有序链接
13. 对关键字序列（5，1，4，3，7，2，8，6）进行快速排序时，以第一个元素5为基准的一次划分的结果为 (满分:5)
A. （1，2，3，4，5，6，7，8）
B. （1，4，3，2，5，7，8，6）
C. （2，1，4，3，5，7，8，6）
D. （8，7，6，5，4，3，2，1）
14. 深度为h的满m叉树的第k层的结点(1=数有 (满分:5)
A. mk-1
B. mk-1
C. mh-1
D. mh-1
15. 多维数组之所以有行优先顺序和列优先顺序两种存储方式是因为 (满分:5)
A. 数组的元素处在行和列两个关系中
B. 数组的元素必须从左到右顺序排列
C. 数组的元素之间存在次序关系
D. 数组是多维结构，内存是一维结构
16. 用二叉链表表示具有n个结点的二叉树时，值为空的指针域的个数为 (满分:5)
A. n-1
B. n
C. n+l
D. 2n
17. 已知一棵含50个结点的二叉树中只有一个叶子结点，则该树中度为1的结点个数为 (满分:5)
A. 0
B. 1
C. 48
D. 49
18. 若采用孩子兄弟链表作为树的存储结构，则树的后序遍历应采用二叉树的 (满分:5)
A. 层次遍历算法
B. 前序遍历算法
C. 中序遍历算法
D. 后序遍历算法
19. 在头指针为head且表长大于1的单循环链表中，指针p指向表中某个结点，若p->next->next= head,则 (满分:5)
A.p指向头结点
B.p指向尾结点
C.p的直接后继是头结点
D. P的直接后继是尾结点
20. 若度为m的哈夫曼树中，其叶结点个数为n，则非叶结点的个数为 (满分:5)
A.n-1
B. ën/mû-1
C. é(n-1)/(m-1)ù
D.én/(m-1)ù-1
17秋学期《数据结构Ⅱ》在线作业2
一、单选题:【20道,总分:100分】
1. 在线性表的下列运算中，不改变数据元素之间结构关系的运算是 (满分:5)
A. 插入
B. 删除
C. 排序
D. 查找
2. 已知一组关键字为{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}
3. 已知广义表的表头为a，表尾为(b,c)，则此广义表为 (满分:5)
A. .(a,(b,c))
B. .(a,b,c)
C. .((a),b,c)
D. .((a,b,c))
4. 若允许表达式内多种括号混合嵌套，则为检查表达式中括号是否正确配对的算法，通常选用的辅助结构是 (满分:5)
A. 栈
B. 线性表
C. 队列
D. 二叉排序树
5. 采用ISAM或VSAM组织的文件是 (满分:5)
A.索引非顺序文件
B. 顺序文件
C. 索引顺序文件
D.散列文件
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. 在一棵高度为k的满二叉树中，结点总数为 (满分:5)
A. 2k-1
B. 2k
C. 2k-1
D. ëlog2kû+1
10. 一棵左子树为空的二叉树在先序线索化后，其中空的链域的个数是 (满分:5)
A. 不确定
B. 0
C. 1
D. 2
11. 三维数组A按行优先存储方法存储在内存中，若每个元素占2个存储单元，且数组中第一个元素的存 储地址为120，则元素A［３］的存储地址为 (满分:5)
A. 356
B. 358
C. 360
D. 362
12. 对于哈希函数H(key)=key%13,被称为同义词的关键字是 (满分:5)
A.35和41
B.23和39
C. 15和44
D.25和51
13. 算法的时间复杂度主要取决于 (满分:5)
A. 问题的规模
B. 待处理数据的初态
C. 难度
D. A和B
14. 栈的两种常用存储结构分别为 (满分:5)
A. 顺序存储结构和链式存储结构
B. 顺序存储结构和散列存储结构
C. 链式存储结构和索引存储结构
D. 链式存储结构和散列存储结构
15. 已知函数Sub(s,i,j)的功能是返回串s中从第i个字符起长度为j的子串，函数Scopy(s,t)的功能为复制串t 到s。若字符串S=″SCIENCESTUDY″，则调用函数Scopy(P,Sub(S,1,7))后得到 (满分:5)
A. P=″SCIENCE″
B. P=″STUDY″
C. S=″SCIENCE″
D. S=″STUDY″
16. 树有先根遍历和后根遍历，树可以转化为对应的二叉树。下面的说法正确的是 (满分:5)
A. 树的后根遍历与其对应的二叉树的后根遍历相同
B. 树的后根遍历与其对应的二叉树的中根遍历相同
C. 树的先根遍历与其对应的二叉树的中根遍历相同
D. 以上都不对
17. 在对n个关键字进行直接选择排序的过程中，每一趟都要从无序区选出最小关键字元素，则在进行第i趟排序之前，无序区中关键字元素的个数为 (满分:5)
A. i
B. i+1
C. n-i
D. n-i+1
18. 设树T的度为4，其中度为1，2，3和4的结点个数分别为4，2，1，1 则T中的叶子数为 (满分:5)
A. 5
B. 6
C. 7
D. 8
19. 设有一个顺序栈，6个元素1、2 、3、4、5、6依次入栈，如果6个元素出栈的顺序是2、3、4、6、5、1，则栈的容量至少应该是 (满分:5)
A. 2
B. 3
C. 5
D. 6
20. 用二叉链表表示具有n个结点的二叉树时，值为空的指针域的个数为 (满分:5)
A. n-1
B. n
C. n+l
D. 2n
17秋学期《数据结构Ⅱ》在线作业3
一、单选题:【20道,总分:100分】
1. 树有先根遍历和后根遍历，树可以转化为对应的二叉树。下面的说法正确的是 (满分:5)
A. 树的后根遍历与其对应的二叉树的后根遍历相同
B. 树的后根遍历与其对应的二叉树的中根遍历相同
C. 树的先根遍历与其对应的二叉树的中根遍历相同
D. 以上都不对
2. 若度为m的哈夫曼树中，其叶结点个数为n，则非叶结点的个数为 (满分:5)
A.n-1
B. ën/mû-1
C. é(n-1)/(m-1)ù
D.én/(m-1)ù-1
3. 已知一个散列表如图所示，其散列函数为H(key)=key％11，采用二次探查法处理冲突，则下一个插入的关键字49的地址为 (满分:5)
A. 2
B. 3
C. 8
D. 9
4. 设有一个顺序栈的入栈序列是a、b、c，则3个元素都出栈的可能不同排列个数为 (满分:5)
A. 4
B. 5
C. 6
D. 7
5. 采用ISAM或VSAM组织的文件是 (满分:5)
A.索引非顺序文件
B. 顺序文件
C. 索引顺序文件
D.散列文件
6. 通常将链串的结点大小设置为大于1是为了 (满分:5)
A. 提高串匹配效率
B. 提高存储密度
C. 便于插入操作
D. 便于删除操作
7. 如果将矩阵An×n的每一列看成一个子表，整个矩阵看成是一个广义表L，即L=((a11,a21,…,an1),( a12,a22,…,an2),…，（a1n,a2n,…,ann）),并且可以通过求表头head和求表尾tail的运算求取矩阵中的每一个元素，则求得a21的运算是 (满分:5)
A. head(tail(head(L)))
B. head(head(head(L)))
C. tail(head(tail(L)))
D. head(head(tail(L)))
8. 下列编码中属于前缀编码的是 (满分:5)
A. {1,01,000,001}
B.{1,01,011,010}
C. {0,10,110,11}
D.{0,1,00,11}
9. 希尔排序的增量序列必须是 (满分:5)
A. 递增的
B. 随机的
C. 递减的
D. 非递减的
10. 高度为5的完全二叉树中含有的结点数至少为 (满分:5)
A. 16
B. 17
C. 31
D. 32
11. 一棵二叉树高度为h,所有结点的度或为0，或为2，则这棵二叉树最少的结点数有 (满分:5)
A. 2h
B. 2h-1
C. 2h+1
D. h+1
12. 某带头结点的单链表的头指针为head，判定该链表为非空的条件是 (满分:5)
A.head==NULL
B.head->next==NULL
C. head!=NULL
D. head->next!=NULL
13. 二维数组A的每个元素是由6个字符组成的串，其行下标i=0，l，…，8，列下标为j=1，2．…．10。设每个字符占一个字节,若按行先存储，元素A的起始地址与A按列存储时起始地址相同的元素是 (满分:5)
A. A
B. A
C. A
D. A
14. 适宜进行批量处理的文件类型是 (满分:5)
A.顺序文件
B. 索引顺序文件
C. 散列文件
D. 多关键字文件
15. 一个有向无环图的拓扑排序序列是 (满分:5)
A. 一定唯一的
B. 一定不唯一的
C. 不一定唯一的
D. 都不对
16. 队列和栈的主要区别是 (满分:5)
A.逻辑结构不同
B.存储结构不同
C. 所包含的运算个数不同
D.限定插入和删除的位置不同
17. 已知一棵树的前序序列为ABCDEF，后序序列为CEDFBA，则对该树进行层次遍历得到的序列为 (满分:5)
A. ABCDEF
B. ABCEFD
C. ABFCDE
D. ABCDFE
18. 下列程序段 for(i=1;i的时间复杂度是 (满分:5)
A. O(1)
B. O(0)
C. O(1+n)
D. O(n)
19. 含n个关键字的二叉排序树的平均查找长度主要取决于 (满分:5)
A. 关键字的个数
B. 树的形态
C. 关键字的取值范围
D. 关键字的数据类型
20. 当采用分快查找时，数据的组织方式为 (满分:5)
A. 数据分成若干块，每块内数据有序
B. 数据分成若干块，每块内数据不必有序，但块间必须有序，每块内最大（或最小）的数据组成索引块
C. 数据分成若干块，每块内数据有序，每块内最大（或最小）的数据组成索引块
D. 数据分成若干块，每块（除最后一块外）中数据个数需相同
页:
[1]