东师数据结构18秋在线作业1答案答案
数据结构18秋在线作业1-0001
试卷总分:100 得分:0
一、 单选题 (共 20 道试题,共 60 分)
1.静态链表中的指针表示的是()。
A.内存地址
B.数组下标
C.下一元素地址
D.左、右子女地址
2.一个栈的入栈序列是a、b、c，则栈的不可能的输出序列是 ( )。
A.acb
B.abc
C.bca
D.cab
3.设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储，a11为第一个元素，其存储地址为100，每个元素占一个地址空间，则a 85的地址为 ()。
A.112
B.132
C.118
D.140
4.在下列排序算法中，哪一个算法的时间复杂度与记录初始排列无关 ()。
A.直接插入排序
B.冒泡排序
C.快速排序
D.直接选择排序
5.有n个顶点的有向图的边数最多为 ()。
A.n
B.n(n-1)
C.n(n-1)/2
D.2n
6.下述文件中适合于磁带存储的是 ()。
A.顺序文件
B.索引文件
C.散列文件
D.多关键字文件
7.采用邻接表存储的图的广度优先遍历类似于二叉树的 ()。
A.前序遍历
B.中序遍历
C.后序遍历
D.层次遍历
8.快速排序算法在下述哪种情况下效率最高 ()。
A.被排序的数据已完全有序
B.被排序的数据中含有多个相同的排序码
C.被排序的数据已基本有序
D.被排序的数据完全无序
9.算法的计算量的大小称为计算的（）。
A.效率
B.复杂性
C.现实性
D.难度
10.折半查找要求结点 ()。
A.无序、顺序存储
B.无序、链接存储
C.有序、顺序存储
D.有序、链接存储
11.head指向的非空的单循环链表的尾结点(由p所指向)满足 ( )。
A.p->next = = NULL
B.p = = NULL
C.p->next = = head
D.p = = head
12.就排序算法所用的辅助空间而言，堆排序、快速排序、归并排序的关系是 () 。
A.堆排序＜快速排序＜归并排序
B.堆排序＜归并排序＜快速排序
C.堆排序＞归并排序＞快速排序
D.堆排序＞快速排序＞归并排序
13.散列函数有一个共同的性质，即函数值应当以下面的哪一项来取其值域的每个值 ()。
A.同等概率
B.最大概率
C.最小概率
D.平均概率
14.一个顺序栈一旦被说明，其占用空间的大小 ( )。
A.可以改变
B.不能固定
C.已固定
D.动态变化
15.下列排序算法中，其中 () 是稳定的。
A.堆排序，起泡排序
B.快速排序，堆排序
C.归并排序，起泡排序
D.直接选择排序，归并排序
16.若设根结点的层数为0，则高(或深)度为4的二叉树至多含有的结点数为 ( )。
A.10
B.16
C.31
D.32
17.在查找过程中，仅进行查找操作，没有引起表本身的改动，这种查找则称为 ()。
A.静态查找
B.动态查找
C.内查找
D.外查找
18.树最适合用来表示 ( )。
A.有序数据元素
B.无序数据元素
C.元素之间具有分支层次关系的数据
D.元素之间无联系的数据
19.设广义表L = ( ( a , b , c ) )，则L的长度和深度分别为 ()。
A.1和1
B.1和3
C.1和2
D.2和3
20.广义表A=(a, b, ( c, d ) , (e，( f , g ) ) )，则式子head ( tail ( head ( tail ( tail ( A ) ) ) ) )的值为 ()。
A.( g )
B.( d )
C.c
D.d
东师数据结构18秋在线作业1答案多选题
二、 判断题 (共 20 道试题,共 40 分)
1.二叉树的中序遍历序列中，任意一个结点均处在其右子女结点( 若存在 )的前面。
A.错误
B.正确
2.哈希表(散列表)的平均查找长度与处理冲突的方法无关。
A.错误
B.正确
3.有向图中顶点Vi的度等于其邻接矩阵里第i行中的 l 的个数。
A.错误
B.正确
4.对于任何数据结构，链接存储结构一定优于顺序存储结构。
A.错误
B.正确
5.完全二叉树的存储结构通常采用顺序存储结构。
A.错误
B.正确
6.快速排序和归并排序在最坏情况下的比较次数都是O(nlog2n )。
A.错误
B.正确
7.顺序存储方式只能用于存储线性结构。
A.错误
B.正确
8.一个有向图的邻接表和逆邻接表中结点的个数可能不等。
A.错误
B.正确
9.栈和队列都是限制存取点的线性结构。
A.错误
B.正确
10.广义表的取表尾运算，其结果通常是一个表，但有时也可是一个单元素值。
A.错误
B.正确
11.文件系统采用索引结构是为了节省存储空间。
A.错误
B.正确
12.循环队列通常用指针来实现队列的头尾相接。
A.错误
B.正确
13.对无序表用折半查找比顺序查找快。
A.错误
B.正确
14.线性表的特点是每个元素都有一个前驱和一个后继。
A.错误
B.正确
15.折半插入排序所需比较次数与待排序记录的初始排列状态无关。
A.错误
B.正确
16.当一棵具有m个叶结点的二叉树的 WPL值为最小时，称其树为Huffman树，且其二叉树的形状必是唯一的。
A.错误
B.正确
17.消除递归不一定需要使用栈。
A.错误
B.正确
18.链表中的表头指针与表头结点起到相同的作用。
A.错误
B.正确
19.取顺序表的第i个元素的时间与i的大小无关。
A.错误
B.正确
东师数据结构18秋在线作业1答案历年真题如下：
