17秋北理工《实用数据结构与算法》在线作业（答案资料）

北理工《实用数据结构与算法》在线作业
一、单选题:【20道,总分:40分】北京理工大学


1.设连通图G中的边集E={(a，b)，(a，e)，(a，c)，(b，e)，(e，d)，(d，f)，(f，c)}，则从顶点a出发可以得到一种深度优先遍历的顶点序列为(    )          (满分:2)
    A. abedfc
    B. acfebd
    C. aebdfc
    D. aedfcb
2.以下说法错误的是(    )          (满分:2)
    A. 求表长、定位这二种运算在采用顺序存储结构时实现的效率不比采用链式存储结构时实现的效率低
    B. 顺序存储的线性表可以随机存取
    C. 由于顺序存储要求连续的存储区域，所以在存储管理上不够灵活
    D. 线性表的链式存储结构优于顺序存储结构
3.设结点A有3个兄弟结点且结点B为结点A的双亲结点，则结点B的度数数为(    )          (满分:2)
    A. 3
    B. 4
    C. 5
    D. 1
4.根据二叉树的定义可知二叉树共有(    )种不同的形态。          (满分:2)
    A. 4
    B. 5
    C. 6
    D. 7
5.设数组Data[0..m]作为循环队列SQ的存储空间，front为队头指针，rear为队尾指针，则执行出队操作的语句为(    )          (满分:2)
    A. front=front+1
    B. front=(front+1)% m
    C. rear=(rear+1)%m
    D. front=(front+1)%(m+1)
6.下列排序方法中效率最高的排序方法是(    )。          (满分:2)
    A. 起泡排序
    B. 堆排序
    C. 快速排序
    D. 直接插入排序
7.用线性链表存储线性表时，要求存储空间(    )          (满分:2)
    A. 必须是连续的
    B. 连续不连续都可以
    C. 部分元素的存储空间必须是连续的
    D. 必须是不连续的
8.栈与一般的线性表的区别在于(    )。          (满分:2)
    A. 数据元素的类型不同
    B. 运算是否受限制
    C. 数据元素的个数不同
    D. 逻辑结构不同
9.以下不稳定的排序方法是(    )          (满分:2)
    A. 直接插入排序
    B. 冒泡排序
    C. 直接选择排序
    D. 二路归并排序
10.长度为256的表,采用分块查找,每块最佳长度为(    )。          (满分:2)
    A. 14
    B. 16
    C. 18
    D. 26
11.任何一个无向连通图的最小生成树(    )。          (满分:2)
    A. 只有一棵
    B. 有一棵或多棵
    C. 一定有多棵
    D. 可能不存在
12.若采用邻接矩阵法存储一个n个顶点的无向图，则该邻接矩阵是一个(    )。          (满分:2)
    A. 上三角矩阵
    B. 稀疏矩阵
    C. 对角矩阵
    D. 对称矩阵
13.设有7000个无序的元素,希望用最快的速度挑选出其中前5个最大的元素,最好选用(    )法。          (满分:2)
    A. 冒泡排序
    B. 快速排序
    C. 堆排序
    D. 基数排序
14.在数据结构中，与所使用的计算机无关的是数据的(    )结构          (满分:2)
    A. 逻辑
    B. 存储
    C. 逻辑和存储
    D. 物理
15.一个栈的入栈序列是abcde，则栈的不可能的输出序列是(    )。          (满分:2)
    A. edcba
    B. decba
    C. dceab
    D. abcde
16.含4个结点（元素值均不相同）的二叉搜索树有(    )种。          (满分:2)
    A. 12
    B. 14
    C. 5
    D. 15
17.下列排序方法中，排序趟数与序列的原始状态有关的方法是(    )。          (满分:2)
    A. 选择排序
    B. 希尔排序
    C. 堆排序
    D. 冒泡排序
18.快速排序属于那种排序类型(    )。          (满分:2)
    A. 选择排序
    B. 插入排序
    C. 交换排序
    D. 基数排序
19.设有一个矩阵A8×6，以行序为主序存储，a11为第一个元素，其存储地址为1，每个元素占一个地址空间，则a56地址为(    )。          (满分:2)
    A. 23
    B. 30
    C. 31
    D. 45
20.若某线性表最常用的操作是在最后一个结点之后插入一个结点或删除最后一个结点，则采用哪一种存储结构算法的时间效率最高?(    )          (满分:2)
    A. 单链表
    B. 给出表头指针的单循环链表
    C. 双向链表
    D. 给出表尾指针的双向循环链表
二、多选题:【10道,总分:20分】

1.下面关于求关键路径的说法正确的是(    )          (满分:2)
    A. 求关键路径是以拓扑排序为基础的
    B. 一个事件的最早开始时间同以该事件为尾的弧的活动最早开始时间相同
    C. 一个事件的最迟开始时间为以该事件为尾的弧的活动最迟开始时间与该活动的持续时间的差
    D. 关键活动一定位于关键路径上
2.以下说法正确的是(    )          (满分:2)
    A. 二叉树可以是空集
    B. 二叉树的任一结点至多有两棵子树
    C. 二叉树与树具有相同的树形结构
    D. 二叉树的子树有次序之分
3.下列说法正确的是(    )          (满分:2)
    A. 栈是限定在表尾进行插入或删除操作的线性表
    B. 栈是限定在表头进行插入或删除操作的线性表
    C. 对列是先进先出的线性表
    D. 栈是后进先出的线性表
4.下述哪些不是顺序存储结构的优点？(    )          (满分:2)
    A. 存储密度大
    B. 插入运算方便
    C. 删除运算方便
    D. 可方便地用于各种逻辑结构的存储表示
5.对于单链表表示法，以下说法正确的是(    )          (满分:2)
    A. 指向链表的第一个结点的指针，称为头指针
    B. 单链表的每一个结点都被一个指针所指
    C. 任何结点只能通过指向它的指针才能引用
    D. 尾指针变量具标识单链表的作用，故常用尾指针变量来命名单链表
6.下面几个符号串编码集合中，是前缀编码的是(    )          (满分:2)
    A. {0,10,110,1111}
    B. {11,10,001,101,0001}
    C. {00,010,0110,1000}
    D. {b,c,aa,ac,aba,abb,abc}
7.二叉树的遍历方式有(    )          (满分:2)
    A. 先序遍历
    B. 中序遍历
    C. 后序遍历
    D. 线索遍历
8.对线性表，可进行如下基本操作(    )          (满分:2)
    A. 随机存取
    B. 插入
    C. 删除
    D. 查找
9.以下说法正确的是(    )          (满分:2)
    A. 对于线性表来说，定位运算在顺序表和单链表上的量级均为O（n）
    B. 读表元运算在顺序表上只需常数时间O（1）便可实现，因此顺序表是一种随机存取结构
    C. 在链表上实现读表元运算的平均时间复杂性为O（1）
    D. 插入、删除操作在链表上的实现可在O（1）时间内完成
10.以下不稳定的排序方法是(    )          (满分:2)
    A. 快速排序
    B. 冒泡排序
    C. 希尔排序
    D. 堆排序
三、判断题:【20道,总分:40分】

1.队列和栈都是运算受限的线性表。          (满分:2)
    A. 错误
    B. 正确
2.做进栈运算时应先判别,栈是否为空。          (满分:2)
    A. 错误
    B. 正确
3.任何一棵二叉树中至少有一个结点的度为2。          (满分:2)
    A. 错误
    B. 正确
4.深度为6的二叉树最多有64个结点。          (满分:2)
    A. 错误
    B. 正确
5.快速排序的速度在所有排序方法中为最快，而且所需附加空间也最少。          (满分:2)
    A. 错误
    B. 正确
6.层次遍历初始堆可以得到一个有序的序列。          (满分:2)
    A. 错误
    B. 正确
7.完全二叉树中，若一个结点没有左孩子，则它必是树叶。          (满分:2)
    A. 错误
    B. 正确
8.在单链表中，要访问某个结点，只要知道该结点的指针即可；因此，单链表是一种随机存取结构。          (满分:2)
    A. 错误
    B. 正确
9.对于同一组结点，由于建立二叉排序树时插入结点的先后次序不同，所构成的二叉排序树的形态及深度也不同，所以含有n个结点的二叉排序树不唯一。          (满分:2)
    A. 错误
    B. 正确
10.快速排序是排序算法中平均性能最好的一种排序。          (满分:2)
    A. 错误
    B. 正确
11.一个栈的输入序列是12345，则栈的输出序列可以是54312。          (满分:2)
    A. 错误
    B. 正确
12.顺序存储方式只能用于存储线性结构。          (满分:2)
    A. 错误
    B. 正确
13.算法必须具备的5个特征是：有穷性、确定性、可行性、有0或多个输入量，至少有1个输出量。          (满分:2)
    A. 错误
    B. 正确
14.若采用三元组存储稀疏矩阵，只要把每个元素的行下标和列下标互换，就完成了对该矩阵的转置运算。          (满分:2)
    A. 错误
    B. 正确
15.空栈就是所有元素都为0的栈。          (满分:2)
    A. 错误
    B. 正确
16.顺序查找法适用于存储结构为顺序或链接存储的线性表。          (满分:2)
    A. 错误
    B. 正确
17.哈夫曼树又称为最优二叉树。          (满分:2)
    A. 错误
    B. 正确
18.中序遍历二叉排序树可以得到一个有序的序列。          (满分:2)
    A. 错误
    B. 正确
19.散列法存储的基本思想是由关键码的值决定数据的存储地址。          (满分:2)
    A. 错误
    B. 正确
20.空格也是合法字符，它可以出现在较长的字符串中，也可以单独出现 。          (满分:2)
    A. 错误
    B. 正确
更多学习资料请登录www.openhelp100.com