17春北航《算法与数据结构》在线作业二标准答案

openhelp100

北航《算法与数据结构》在线作业二
答案

一、单选题：
1.设有向图有n个顶点和e条边，采用领接表作为其存储表示，在进行拓扑排序时，总的计算时间为(    )。          (满分:4)
    A. O（nloge）
    B. O（n+e）
    C. O(n*e)
    D. O(n的平方)
2.以下二叉树说法错误的是          (满分:4)
    A. 完全二叉树上结点之间的父子关系可由它们编号之间的关系来表达
    B. 在三叉链表上，二叉树的求双亲运算很容易实现
    C. 在二叉链表上，求根，求左、右孩子等很容易实现
    D. 在二叉链表上，求双亲运算的时间性能很好
3.下述几种排序方法中,平均查找长度最小的是(    )          (满分:4)
    A. 插入排序
    B. 选择排序
    C. 快速排序
    D. 归并排序
4.对于顺序表，以下说法错误的是(    )          (满分:4)
    A. 顺序表是用一维数组实现的线性表，数组的下标可以看成是元素的绝对地址
    B. 顺序表的所有存储结点按相应数据元素间的逻辑关系决定的次序依次排列
    C. 顺序表的特点是:逻辑结构中相邻的结点在存储结构中仍相邻
    D. 顺序表的特点是:逻辑上相邻的元素，存储在物理位置也相邻的单元中
5.队列的插入操作是在(    )进行。          (满分:4)
    A. 队首
    B. 队尾
    C. 队前
    D. 队后
6.设有两个串（S1和S2），求S1在S2中首次出现的位置的运算称为(    )。          (满分:4)
    A. 连接
    B. 模式匹配
    C. 求子串
    D. 求串长
7.一般地，一个存储结构包括以下三个主要部分。以下说法错误的是          (满分:4)
    A. 存储结点每个存储结点可以存放一个或一个以上的数据元素
    B. 数据元素之间关联方式的表示 也就是逻辑结构的机内表示
    C. 附加设施，如为便于运算实现而设置的“哑结点”等等
    D. 一种存储结构可以在两个级别上讨论。其一是机器级，其二是语言级
8.串的逻辑结构与(    )的逻辑结构不同。          (满分:4)
    A. 线性表
    B. 栈
    C. 队列
    D. 树
9.将含100个结点的完全二叉树从根这一层开始，每层上从左到右依次对结点编号，根结点的编号为1。编号为49的结点X的双亲编号为(    )          (满分:4)
    A. 24
    B. 25
    C. 23
    D. 无法确定
10.向顺序栈中压入新元素时，应当(    )。          (满分:4)
    A. 先移动栈顶指针，再存入元素
    B. 先存入元素，再移动栈顶指针
    C. 先后次序无关紧要
    D. 同时进行
11.由两个栈共享一个向量空间的好处是(    )。          (满分:4)
    A. 减少存取时间，降低下溢发生的机率
    B. 节省存储空间，降低上溢发生的机率
    C. 减少存取时间，降低上溢发生的机率
    D. 节省存储空间，降低下溢发生的机率
12.下述几种排序方法中,要求内存量最大的是(    )。          (满分:4)
    A. 插入排序
    B. 选择排序
    C. 快速排序
    D. 归并排序
13.二分查找要求被查找的表是(    )          (满分:4)
    A. 键值有序的链接表
    B. 链接表但键值不一定有序
    C. 键值有序的顺序表
    D. 顺序表但键值不一定有序
14.在一个具有n个顶点的无向图中，要连通所有顶点则至少需要(    )条边。          (满分:4)
    A. n
    B. 2n
    C. n-1
    D. n+1
15.在有n个叶子结点的哈夫曼树中，其结点总数为(    )。          (满分:4)
    A. 不确定
    B. 2n
    C. 2n+1
    D. 2n-1
16.设无向图的顶点个数为n，则该图最多有(    )条边。          (满分:4)
    A. n-1
    B. n(n-1)/2
    C. n(n+1)/2
    D. 0
17.一个加权的无向连通图的最小生成树(    )。          (满分:4)
    A. 有一棵或多棵
    B. 只有一棵
    C. 一定有多棵
    D. 可能不存在
18.带头节点的单链表  head 为空的判定条件(    )。          (满分:4)
    A. head=NULL
    B. head->next=NULL
    C. head->next=head
    D. head!=head
19.通常从正确性、易读性、健壮性、高效性等四个方面评价算法(包括程序)的质量。以下解释错误的是          (满分:4)
    A. 正确性 算法应能正确地实现预定的功能(即处理要求)
    B. 易读性 算法应易于阅读和理解 以便于调试 修改和扩充
    C. 健壮性 当环境发生变化时，算法能适当地做出反应或进行处理，不会产生不需要的运行结果
    D. 高效性 即达到所需要的时间性能
20.在一个单链表HL中，若要向表头插入一个由指针p指向的结点，则执行(    )。          (满分:4)
    A. HL=p;p->next=HL;
    B. p->next=HL;HL=p;
    C. p->next=HL;p=HL;
    D. p->next=HL->next;HL->next=p;
21.一组记录的排序码为(46,79,56,38,40,84),则利用堆排序的方法建立的初始堆为(    )。          (满分:4)
    A. 79,46,56,38,40,80
    B. 84,79,46,38,40,56
    C. 84,79,56,46,40,38
    D. 84,56,79,40,46,38
22.以下说法错误的是  (    )          (满分:4)
    A. 线性表的元素可以是各种各样的，逻辑上相邻的元素在物理位置上不一定相邻
    B. 在线性表的顺序存储结构中，逻辑上相邻的两个元素在物理位置上不一定相邻
    C. 在线性表的链式存储结构中，逻辑上相邻的元素在物理位置上不一定相邻
    D. 线性表的链式存储结构的特点是用一组任意的存储单元存储线性表的数据元素
23.当利用大小为N 的数组顺序存储一个栈时，假定用top = = N表示栈空，则退栈时，用(    )语句修改top指针。          (满分:4)
    A. top++
    B. top=0
    C. top--
    D. top=N
24.在线性表的散列存储中，若用m表示散列表的长度，n表示待散列存储的元素的个数，则装填因子a等于(    )。          (满分:4)
    A. n/m
    B. m/n
    C. n/(n+m)
    D. m/(n+m)
25.对于数据结构课程的主要内容，以下解释正确的是          (满分:4)
    A. 数据结构的定义，包括逻辑结构、存储结构和基本运算集
    B. 数据结构的实现，包括存储实现、运算实现和基本运算集
    C. 数据结构的评价和选择，包括逻辑结构的选择、基本运算集的选择和存储选择
    D. 以上说法均不正确
转载请注明易百网