华师2016春《数据结构》作业

1、第1题 (2) 分 以下叙述错误的是( )。A、数据的三个层次是数据、数据元素、数据项B、数据类型是指相同性质的计算机数据的集合C、每种逻辑结构都有一个运算的集合D、储存结构中不仅要储存数据的内容，还要把数据间的关系表示出来。第2题 (2) 分 多维数组之所以有行优先顺序和列优先顺序两种存储方式是因为( )。A、数组的元素处在行和列两个关系中B、数组的元素必须从左到右顺序排列C、数组的元素之间存在次序关系D、数组是多维结构，内存是一维结构第3题 (2) 分 线性表采用链式存储时，其地址( )。A、必须连续B、部分地址必须连续C、一定不连续D、连续与否均可第4题 (2) 分 线索二叉树中某结点为

2、叶子的条件是( )。A、p- lchild!=NULL | p- rchild!=NULLB、p- ltag=0 | p- rtag=0C、p- lchild!=NULL & & p- rchild!=NULLD、p- ltag=1 & & p- rtag=1第5题 (2) 分 设有向图n个顶点和e条边，进行拓扑排序时，总的计算时间为( )。A)O(nlog2n)B)O(en)C)O(elog2n)D)O(n+e)A、AB、BC、CD、D第6题 (2) 分 最好和最坏时间复杂度均为O(nlog2n)且稳定的排序方法是( )。A、快速排序B、堆排序C、归并排序D、基数排序第7题 (2) 分 假定

3、有k个关键字互为同义词，若用线性探测法把这k个关键字存入散列表中，至少要进行( )次探侧。A、k-1B、kC、k+1D、k(k+1)/2第8题 (2) 分 n个记录直接选择排序时所需的记录最多交换次数是( )。A、n-1B、nC、n(n-1)/2D、n(n+1)/2第9题 (2) 分 若进栈序列为a,b,c，则通过入出栈操作能得到的a,b,c的不同排列个数为( )。A、4B、5C、6D、7第10题 (2) 分 若某线性表中最常用的操作是取第i个元素和找第i个元素的前趋元素，则采用( )存储方式最节省运算时间( )。A、单链表B、顺序表C、双链表D、单循环链表第11题 (2) 分 在C语言中，串

4、的存储方式是( )。A、顺序存储B、散列存储C、索引存储D、链式存储第12题 (2) 分 对包含n个关键字的散列表进行检索，平均检索长度是( )。A)O(log2n)B)O(n)C)不直接依赖于nD)O(nlog2n)A、AB、BC、CD、D第13题 (2) 分 对于有向图，其邻接矩阵表示相比邻接表表示更易于进行的操作为( )。A、求顶点的邻接点B、求顶点的度C、深度优先遍历D、广度优先遍历第14题 (2) 分 高度为n、结点数也为n的二叉树，共有( )棵。A）nB）2n-1C）n-1D）2n-1A、AB、BC、CD、D第15题 (2) 分 排序趟数与序列的原始状态有关的排序方法是( )排序法

5、。A、插入B、选择C、希尔D、快速第16题 (2) 分 以下叙述错误的是( )。A、树的先根遍历需要借助栈来实现。B、树的层次遍历需要借助队列来实现。C、树的后根遍历与对应二叉树的后根遍历相同。D、树的先根序列与对应二叉树的先根序列相同。第17题 (2) 分 希尔排序的增量序列必须是( )。A、递增的B、随机的C、递减的D、任意的第18题 (2) 分 ( )存储方式适用于折半查找。A、键值有序的单链表B、键值有序的顺序表C、键值有序的双链表D、键值无序的顺序表第19题 (2) 分 在n个顶点和e条边的无向图的邻接矩阵中，表示边存在的元素个数为( )。A、nB、n*eC、eD、2*e第20题 (

6、2) 分 若下图表示某广义表，则它是一种( )。A、线性表B、纯表C、再入表D、递归表第21题 (2) 分 树结构最适合用来表示( )。A、有序数据B、无序数据C、元素间具有分支层次关系的数据D、元素间无关联的数据第22题 (2) 分 设p指向单链表中的一个结点，s指向待插入的结点，则下述程序段的功能是( )。s-next=p-next;p-next=s;t=p-data;p-data=s-data;s-data=t;A、结点*p与结点*s的数据域互换B、在p所指结点的元素之前插入元素C、在p所指结点的元素之后插入元素D、在结点*p之前插入结点*s第23题 (2) 分 下列各式中，按增长率由小

7、至大的顺序正确排列的是( )。An1/2，n!，2n ，n3/2Bn3/2，2n，nlogn，2100C2n，logn，nlogn，n3/2D2100，logn, 2n, nnA、AB、BC、CD、D第24题 (2) 分 下列查找方法中，不属于动态的查找方法是( )。A、二叉排序树法B、平衡树法C、散列法D、二分查找法第25题 (2) 分 连通图是指图中任意两个顶点之间( )。A、都连通的无向图B、都不连通的无向图C、都连通的有向图D、都不连通的有向图判断题第26题 (2) 分 缩短关键路径上活动的工期一定能够缩短整个工程的工期。正确错误第27题 (2) 分 线性结构可以顺序存储，也可以链接存

8、储。非线性结构只能链接存储。正确错误第28题 (2) 分 单链表中取第i个元素的时间与i成正比。正确错误第29题 (2) 分 二分查找所对应的判定树，是一棵理想平衡的二叉排序树。正确错误第30题 (2) 分 堆排序是一种巧妙的树型选择排序。正确错误第31题 (2) 分 拓扑排序可以分析某工程能否顺利进行。正确错误第32题 (2) 分 利用栈可将递归程序转化成非递归程序。正确错误第33题 (2) 分 设串的长度为n，则其子串个数为n(n+1)/2。正确错误第34题 (2) 分 线性表、树、图等都可以用广义表表示。正确错误第35题 (2) 分 在开散列表中不会出现堆积现象。正确错误第36题 (2)

9、 分 计算机的速度越快，算法的时间复杂性就越低。正确错误第37题 (2) 分 顺序表不需存放指针，链表要存放指针，故链表的存储空间要求总是比顺序表大。正确错误第38题 (2) 分 如果某种排序算法是不稳定的，则该方法没有实际的应用价值。正确错误第39题 (2) 分 对任何图，执行一次深度优先或广度优先遍历后，就可访问到图中所有节点。正确错误第40题 (2) 分 二叉树中不可能有两个结点在先根、中根和后根序列中的相对次序都不变。正确错误第41题 (2) 分 链栈一般不需要头结点，因为无头结点的链栈运算也很方便。正确错误第42题 (2) 分 数组的基本运算有读、写、插入、删除等。正确错误第43题 (2) 分 树的度是指树中结点的最大度数，所以二叉树的度为2。正确错误第44题 (2) 分 在顺序表中按值查找运算的复杂性为O(1)。正确错误第45题 (2) 分 n个结点的有向图，若它有n(n1)条边，则它一定是强连通的。正确错误第46题 (2) 分 基数排序不需进行关键字间的比较，故执行时间比基于比较的排序方法要快。正确错误第47题 (2) 分 用线性探测法解