西南交大18秋《数据结构》在线作业二资料

西南交《数据结构》在线作业二

奥鹏作业答案
奥鹏西南交通大学

一、单选题：
1.[单选题]树的后根遍历序列等同于该树对应的二叉树的().          (满分:)
    A. 先序序列
    B. 中序序列
    C. 后序序列
    D. 都不正确
    正确答案:——B——
2.[单选题]链表不具有的特点是（）          (满分:)
    A. 插入、删除不需要移动元素
    B. 可随机访问任一元素
    C. 不必事先估计存储空间
    D. 所需空间与线性长度成正比
    正确答案:——B——
3.[单选题]采用折半查找法查找长度为n的查找表时,每个元素查找的平均查找长度为()。          (满分:)
    A. O(n2)
    B. O(nlog2n)
    C. O(n)
    D. O(log2n)
    正确答案:——D——
4.[单选题]如果对n个元素进行直接选择排序,则进行一趟排序过程中,为寻找最小值元素所需要的时间复杂度为()。          (满分:)
    A. O(1)
    B. O(log2n)
    C. O(n2)
    D. O(n)
    正确答案:————
5.[单选题]下列排序算法中，占用辅助空间最多的是：()          (满分:)    奥鹏答案

    A. 归并排序
    B. 快速排序
    C. 希尔排序
    D. 堆排序
    正确答案:————
6.[单选题]已知串S=‘aaab’,其Next数组值为（）。          (满分:)
    A. 0123
    B. 1123
    C. 1231
    D. 1211
    正确答案:————
7.[单选题]设有两个串p和q，其中q是p的子串，求q在p中首次出现的位置的算法称为（）          (满分:)
    A. 求子串
    B. 联接
    C. 匹配
    D. 求串长
    正确答案:————
8.[单选题]设计一个判别表达式中左，右括号是否配对出现的算法，采用（）数据结构最佳。          (满分:)
    A. 线性表的顺序存储结构
    B. 队列
    C. 线性表的链式存储结构
    D. 栈
    正确答案:————
9.[单选题]设有一个n*n的对称矩阵,采用压缩存储,则存入内存的元素个数为()。          (满分:)
    A. n*n
    B. n*n/2
    C. n*(n+1)/2
    D. (n+1)2/2
    正确答案:————
10.[单选题]稀疏矩阵一般的压缩方法有两种,即()。          (满分:)
    A. 二维数组和三维数组
    B. 三元组和散列
    C. 三元组和十字链表
    D. 散列和十字链表
    正确答案:————
11.[单选题]要连通具有n个顶点的有向图，至少需要（）条边。          (满分:)
    A. n-l
    B. n
    C. n+l
    D. 2n
    正确答案:————
12.[单选题]设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储，a11为第一元素，其存储地址为1，每个元素占一个地址空间，则a85的地址为（）。          (满分:)
    A. 13
    B. 33
    C. 18
    D. 40
    正确答案:————
13.[单选题]输入序列为ABC，可以变为CBA时，经过的栈操作为（）          (满分:)
    A. push,pop,push,pop,push,pop
    B. push,push,push,pop,pop,pop
    C. push,push,pop,pop,push,pop
    D. push,pop,push,push,pop,pop
    正确答案:————
14.[单选题]与顺序栈相比较,链栈有一个比较明显的优势是()。          (满分:)
    A. 通常不会出现栈满的情况
    B. 插入操作更容易实现
    C. 通常不会出现栈空的情况
    D. 删除操作更容易实现
    正确答案:————
15.[单选题]队列存放在A[0..M-1]中,则入队时的操作为()。          (满分:)
    A. rear=rear+1
    B. rear=(rear+1)%M
    C. rear=rear+1)%(M+1)
    D. rear=(rear+1)%(M-1)
    正确答案:————
三、判断题：
16.[判断题]排序的稳定性是指排序算法中的比较次数保持不变，且算法能够终止          (满分:)
    A. 错误
    B. 正确
    正确答案:————
17.[判断题]顺序队列中的元素个数可以根据队首指针和队尾指针的值计算出来。()          (满分:)
    A. 错误
    B. 正确
    正确答案:————
18.[判断题]折半查找法的查找速度一定比顺序查找法快          (满分:)
    A. 错误
    B. 正确
    正确答案:————
19.[判断题]哈希冲突是指同一个关键字对应多个不同的哈希地址。()          (满分:)
    A. 错误
    B. 正确
    正确答案:————
20.[判断题]在顺序存储结构中，有时也存储数据结构中元素之间的关系。          (满分:)
    A. 错误
    B. 正确
    正确答案:————
21.[判断题]完全二叉树中,若一个没有左孩子,则它必定是叶结点。()          (满分:)
    A. 错误
    B. 正确
    正确答案:————
22.[判断题]如果表示有向图的邻接矩阵是对称的,则该有向图一定是完全有向图。()          (满分:)
    A. 错误
    B. 正确
    正确答案:————
23.[判断题]哈希存储法只能存储数据元素的值,不能存储数据元素之间的关系。()          (满分:)
    A. 错误
    B. 正确
    正确答案:————
24.[判断题]二维以上的数组其实是一种特殊的广义表。          (满分:)
    A. 错误
    B. 正确
    正确答案:————
25.[判断题]即使对不含相同元素的同一输入序列进行两组不同的合法的入栈和出栈操作,所得的输出序列一定相同。()          (满分:)
    A. 错误
    B. 正确
    正确答案:————
奥鹏作业答案