14秋北航《算法与数据结构》在线作业资料三辅导资料

谋学网

谋学网(www.mouxue.com)是国内最专业的奥鹏作业资料，奥鹏离线作业资料及奥鹏毕业论文辅导型网站，主要提供奥鹏中医大、大工、东财、北语、北航、川大、南开等奥鹏作业资料辅导，致力打造中国最专业的远程教育辅导社区。

一、单选题（共 25 道试题，共 100 分。）V 1.  下列图的说法中正确的是（ ） 。
A. 一个具有 n 个顶点的无向完全图的边数为 n(n-1)
B. 连通图的生成树是该图的一个极大连通子图
C. 图的广度优先搜索是一个递归过程
D. 在非连通图的遍历过程中，每调用一次深度优先搜索算法都得到该图的一个连通分量
      满分：4  分
2.  一组记录的关键码为(46,79,56,38,40,84),则利用快速排序的方法,以第一个记录为基准得到的一次划分结果为（）。
A. 38,40,46,56,79,84
B. 40,38,46,79,56,84
C. 40,38,46,56,79,84
D. 40,38,46,84,56,79
      满分：4  分
3.  对有n个记录的有序表采用二分查找，其平均查找长度的量级为（　）
A. O(log2n)
B. O(nlog2n)
C. O(n)
D. O(n2)
      满分：4  分
4.  在线性表的散列存储中，若用m表示散列表的长度，n表示待散列存储的元素的个数，则装填因子a等于（）。
A. n/m
B. m/n
C. n/(n+m)
D. m/(n+m)
      满分：4  分
5.  设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主的存储，a11为第一个元素，其存储地址为1，每个元素占1个地址空间，则a85的地址为（）。
A. 13
B. 18
C. 33
D. 40
      满分：4  分
6.  顺序表的一个存储结点仅仅存储线性表的一个
A. 数据元素
B. 数据项
C. 数据
D. 数据结构
      满分：4  分
7.  顺序查找法适合于存储结构为（）的线性表。
A. 散列表
B. 顺序存储或连接存储
C. 压缩存储
D. 索引存储
      满分：4  分
8.  若线性表最常用的操作是存取第i个元素及其前趋的值，则采用（ ）存储方式节省时间。
A. 单链表
B. 双链表
C. 单循环链表
D. 顺序表
      满分：4  分
9.  如果要求一个线性表既能较快地查找,又能适应动态变化的要求,可以采用（）查找方法。
A. 分块
B. 顺序
C. 二分
D. 散列
      满分：4  分
10.  设二叉树有n个结点，则其深度为
A. n-1
B. n
C. 5floor(log2n)
D. 无法确定
      满分：4  分
11.  循环队列的人队操作应为 ( )
A. sq.rear=sq.rear+1 sq.data[sq.rear]=x
B. sq.data[sq.rear]=x sq.rear=sq.rear+1
C. sq.rear=(sq.rear+1)% maxsize sq.data[sq.rear]=x
D. sq.data[sq.rear]=x sq.rear=(sq.rear+1)% maxsize
      满分：4  分
12.  在待排序的元素序列基本有序的前提下,效率最高的排序方法是（）
A. 插入排序
B. 选择排序
C. 快速排序
D. 归并排序
      满分：4  分
13.  3个结点可构成（ 　）个不同形态的二叉树。
A. 2
B. 3
C. 4
D. 5
      满分：4  分
14.  在以下队列的基本运算中，不是加工型运算的是 （ ）
A. InitQueue(Q)
B. EnQueue(Q,X)
C. OutQueu(Q,X)
D. GetHead(Q,x)
      满分：4  分
15.  用某种排序方法队线性表（25，84，21，47，15，27，68，35，20）进行排序，元素序列变化如下：（1）25，84，21，47，15，27，68，35，20 （2）20，15，21，25，47，27，68，35，84 （3）15，20，21，25，35，27，47，68，84 （4）15，20，21，25，27，35，47，68，84 所采用的排序方法是（ ）。
A. 选择排序
B. Shell排序
C. 归并排序
D. 快速排序
      满分：4  分
16.  队列的删除操作是在（ ）进行。
A. 队首
B. 队尾
C. 队前
D. 队后
      满分：4  分
17.  以下说法正确的是
A. 所谓数据的逻辑结构指的是数据元素之间的逻辑关系。
B. 逻辑结构与数据元素本身的内容和形式无关
C. 顺序文件只适合于存放在磁带上，索引文件只能存放在磁盘上
D. 基于某种逻辑结构之上的运算，其实现是惟一的
      满分：4  分
18.  若某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除最后一个元素，则采用（ 　）存储方式最节省运算时间。
A. 单链表
B. 双链表
C. 带头结点的双循环链表
D. 容量足够大的顺序表
      满分：4  分
19.  设有1000个元素，用二分法查找时，最大比较次数是（ ）。
A. 1
B. 7
C. 10
D. 25
      满分：4  分
20.  顺序表是线性表的
A. 链式存储结构
B. 顺序存储结构
C. 索引存储结构
D. 散列存储结构
      满分：4  分
21.  以下关于树和森林说法错误的是
A. 一般在哈夫曼树中，权值越大的叶子离根结点越近
B. 哈夫曼树中没有度数为1的分支结点
C. 若初始森林中共有n裸二叉树，最终求得的哈夫曼树共有2n-1个结点
D. 若初始森林中共有n裸二叉树，进行2n-1次合并后才能剩下一棵最终的哈夫曼树
      满分：4  分
22.  算法分析的两个主要方面是（ ）。
A. 空间复杂度和时间复杂度
B. 正确性和简明性
C. 可读性和文档性
D. 数据复杂性和程序复杂性
      满分：4  分
23.  下述几种排序方法中,平均查找长度最小的是（）
A. 插入排序
B. 选择排序
C. 快速排序
D. 归并排序
      满分：4  分
24.  设有向图有n个顶点和e条边，采用领接表作为其存储表示，在进行拓扑排序时，总的计算时间为（）。
A. O（nloge）
B. O（n+e）
C. O(n*e)
D. O(n的平方)
      满分：4  分
25.  快速排序的记录移动次数（　 ）比较次数，其总执行时间为O(nlog2n)。
A. 大于
B. 大于等于
C. 小于等于
D. 小于
      满分：4  分

谋学网(www.mouxue.com)是国内最专业的奥鹏作业资料，奥鹏离线作业资料及奥鹏毕业论文辅导型网站，主要提供奥鹏中医大、大工、东财、北语、北航、川大、南开等奥鹏作业资料辅导，致力打造中国最专业的远程教育辅导社区。