东北大学17秋《数据结构Ⅰ》在线作业123答案100分参考
17秋学期《数据结构Ⅰ》在线作业1一、单选题:【20道,总分:100分】
1. 已知含10个结点的二叉排序树是一棵完全二叉树，则该二叉排序树在等概率情况下查找成功的平均查找长度等于 (满分:5)
A. 1.0 B. 2.9 C. 3.4
D. 5.52. 能进行二分查找的线性表,必须以 (满分:5)
A. 顺序方式存储,且元素按关键字有序
B. 链式方式存储,且元素按关键字有序
C. 顺序方式存储,且元素按关键字分块有序
D. 链式方式存储,且元素按关键字分块有序
3. 已知输入序列为abcd 经过输出受限的双向队列后能得到的输出序列有 (满分:5)
A.dacb
B.cadb
C. bdac
D. 以上答案都不对
4. 对n个关键字的序列进行快速排序，平均情况下的空间复杂度为 (满分:5)
A. O(1)
B.O(logn)
C. O(n)
D. O(n logn)
5. 设一个栈的输入序列为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
6. 连通图是指图中任意两个顶点之间 (满分:5)
A.都连通的无向图
B.都不连通的无向图
C. 都连通的有向图
D. 都不连通的有向图
7. 队列和栈的主要区别是 (满分:5)
A. 逻辑结构不同
B. 存储结构不同
C.所包含的运算个数不同
D.限定插入和删除的位置不同
8. 一棵树高为K的完全二叉树至少的结点是 (满分:5)
A. 2k –1
B.2k-1 –1
C.2k-1
D.2k
9. n个顶点的有向完全图中含有向边的数目最多为 (满分:5)
A. n-1
B.n
C. n(n-1)/2
D. n(n-1)
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. 0
B. 1
C. 2
D. 不确定
13. 在关键字序列(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
14. 下列关键字序列中，构成小根堆的是 (满分: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}
15. 若以1234作为双端队列的输入序列，则既不能由输入受限的双端队列得到，也不能由输出受限的双端队列得 到的输出序列是 (满分:5)
A. 1234
B. 4132
C. 4231
D. 4213
16. 设有一个顺序栈，6个元素1、2 、3、4、5、6依次入栈，如果6个元素出栈的顺序是2、3、4、6、5、1，则栈的容量至少应该是 (满分:5)
A. 2
B. 3
C. 5
D. 6
17. 下列查找算法中，平均查找长度与元素个数n不直接相关的查找方法是 (满分:5)
A.分块查找
B.顺序查找
C.二分查找
D. 散列查找
18. 抽象数据类型的三个组成部分分别为 (满分:5)
A. 数据对象、数据关系和基本操作
B. 数据元素、逻辑结构和存储结构
C. 数据项、数据元素和数据类型
D. 数据元素、数据结构和数据类型
19. 可有效提高次关键字查找效率的文件是 (满分:5)
A. 顺序文件
B.倒排文件
C. 散列文件
D. VSAM文件
20. 设给定权值总数有n 个，其哈夫曼树的结点总数为 (满分:5)
A. 不确定
B. 2n
C. 2n+1
D. 2n-1
17秋学期《数据结构Ⅰ》在线作业2
一、单选题:【20道,总分:100分】
1. 假设以数组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
2. 队列和栈的主要区别是 (满分:5)
A. 逻辑结构不同
B. 存储结构不同
C.所包含的运算个数不同
D.限定插入和删除的位置不同
3. 在单链表中，指针p指向元素为x的结点，实现“删除x的后继”的语句是 (满分:5)
A. p=p->next;
B.p->next=p->next->next;
C. p->next=p;
D. p=p->next->next;
4. 已知在一棵度为3的树中，度为2的结点数为4，度为3的结点数为3，则该树中的叶子结点数为 (满分:5)
A. 5
B. 8
C. 11
D. 18
5. 顺序存储设计时，存储单元的地址 (满分: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. 求最小生成树的prim算法
D. 拓扑排序算法
11. 带行表的三元组表是稀疏矩阵的一种 (满分:5)
A. 顺序存储结构
B.链式存储结构
C. 索引存储结构
D. 散列存储结构
12. 多维数组之所以有行优先顺序和列优先顺序两种存储方式是因为 (满分:5)
A. 数组的元素处在行和列两个关系中
B. 数组的元素必须从左到右顺序排列
C. 数组的元素之间存在次序关系
D. 数组是多维结构，内存是一维结构
13. 在下列对顺序表进行的操作中，算法时间复杂度为O(1)的是 (满分:5)
A. 访问第i个元素的前驱
B. 在第i个元素之后插入一个新元素
C. 删除第i个元素
D.对顺序表中元素进行排序
14. . 在用邻接表表示图时，拓扑排序算法时间复杂度为 (满分:5)
A.O(n)
B.O(n＋e)
C.O(n*n)
D. O(n*n*n)
15. 在长度为n的顺序表的第i(1≤i≤n+1)个位置上插入一个元素，元素的移动次数为 (满分:5)
A. n-i+1
B. n-i
C. i
D. i-1
16. 当在二叉排序树中插入一个新结点时，若树中不存在与待插入结点的关键字相同的结点，且新结点的关键字小于根结点的关键字，则新结点将成为 (满分:5)
A. A．左子树的叶子结点
B. B．左子树的分支结点
C. C．右子树的叶子结点
D. D．右子树的分支结点
17. 已知一组关键字为{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}
18. 设一个栈的输入序列为12345，则借助一个栈所得到的输出序列不可能是 (满分:5)
A. 23415
B. 54132
C. 23145
D. 15432
19. 对于哈希函数H(key)=key%13,被称为同义词的关键字是 (满分:5)
A. 35和41
B.23和39
C. 15和44
D.25和51
20. 一个有向无环图的拓扑排序序列是 (满分:5)
A. 一定唯一的
B. 一定不唯一的
C. 不一定唯一的
D. 都不对
17秋学期《数据结构Ⅰ》在线作业3
一、单选题:【20道,总分:100分】
1. 在待排关键字序列基本有序的前提下，效率最高的排序方法是 (满分:5)
A. 直接插入排序
B.快速排序
C. 直接选择排序
D.归并排序
2. 下面的说法中正确的是 (1)任何一棵二叉树的叶子节点在三种遍历中的相对次序不变。 (2)按二叉树定义，具有三个节点的二叉树共有6种。 (满分:5)
A.(1)，(2)
B. (1)
C.(2)
D. (1)，(2)都错
3. 在单链表中，指针p指向元素为x的结点，实现“删除x的后继”的语句是 (满分:5)
A. p=p->next;
B.p->next=p->next->next;
C. p->next=p;
D. p=p->next->next;
4. 一棵左右子树均不空的二叉树在先序线索化后，其中空的链域的个数是 (满分:5)
A. 0
B. 1
C. 2
D. 不确定
5. 对关键字序列(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)
6. 一个含n个顶点和e条弧的有向图以邻接矩阵表示法为存储结构，则计算该有向图中某个顶点出度的时间复杂度为 (满分:5)
A. O(n)
B.O(e)
C. O(n+e)
D. O(n2)
7. 对关键字序列（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）
8. 上溢现象通常出现在 (满分:5)
A. 顺序栈的入栈操作过程中
B. 顺序栈的出栈操作过程中
C. 链栈的入栈操作过程中
D. 链栈的出栈操作过程中
9. 假设一棵完全二叉树按层次遍历的顺序依次存放在数组BT中，其中根结点存放在BT，若BT中的结点有左孩子，则左孩子存放在 (满分:5)
A. BT
B.BT
C.BT
D.BT
10. 某二叉树的先序序列和后序序列正好相反，则该二叉树的特点一定是 (满分:5)
A. 空或只有一个结点
B. 高度等于其结点数
C.任一结点无左孩子
D.任一结点无右孩子
11. 若要在O(1)的时间复杂度上实现两个循环链表头尾相接，则应对两个循环链表各设置一个指针，分别指向 (满分:5)
A.各自的头结点
B. 各自的尾结点
C. 各自的第一个元素结点
D. 一个表的头结点，另一个表的尾结点
12. n个顶点的强连通图中至少含有 (满分:5)
A.n-1条有向边
B.n条有向边
C.n(n-1)/2条有向边
D. n(n-1)条有向边
13. 在头指针为head且表长大于1的单循环链表中，指针p指向表中某个结点，若p->next->next= head,则 (满分:5)
A. p指向头结点
B. p指向尾结点
C. p的直接后继是头结点
D. P的直接后继是尾结点
14. 设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
15. 在一棵高度为k的满二叉树中，结点总数为 (满分:5)
A.2k-1
B. 2k
C. 2k-1
D. log2kû+1
16. 倒排文件的主要优点是 (满分:5)
A.便于进行插入和删除运算
B. 便于进行文件的恢复
C.便于进行多关键字查询
D.节省存储空间
17. 对n个关键字的序列进行快速排序，平均情况下的空间复杂度为 (满分:5)
A. O(1)
B.O(logn)
C. O(n)
D. O(n logn)
18. 若要在单链表中的结点p之后插入一个结点s，则应执行的语句是 (满分:5)
A. s->next=p->next; p->next=s;
B.p->next=s; s->next=p->next;
C. p->next=s->next; s->next=p;
D. s->next=p; p->next=s->next;
19. 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）
20. 算法的时间复杂度主要取决于 (满分:5)
A. 问题的规模
B. 待处理数据的初态
C. 难度
D. A和B
页:
[1]