超星尔雅数据结构与算法-k8凯发

k8凯发-凯发官网入口职业技能答案 正文

1.5第1单元测验

1、【单选题】数据结构中,把数据结构从逻辑上分成( )。
    a、动态结构和静态结构
    b、紧凑结构和非紧凑结构
    c、线性结构和非线性结构
    d、内部结构和外部结构

2、【单选题】计算机算法指的是( )。
    a、计算机方法
    b、排序方法
    c、解决问题的有限步骤
    d、调度方法

3、【填空题】数据逻辑结构包括(__)、(__)和(__)。

4、【填空题】线性结构中的元素之间存在(__) 的关系,树型结构的元素之间存在(__) 的关系,图形结构的元素之间存在(__) 的关系。

5、【填空题】算法的设计要求包括:正确性、可读性、健壮性和(__)。

6、【填空题】算法的时间复杂度与空间复杂度相比,通常以(__)作为主要度量指标。

7、【判断题】算法可以没有输入。

8、【判断题】有输出的算法才是有意义的。

9、【简答题】算法的概念是什么?

10、【简答题】算法可读性的含义是什么?

11、【简答题】算法的健壮性是指什么?

12、【简答题】给出下列算法中语句的时间复杂度 i=1;k=0; whle(i<=n-1) { k=k 2*i; i ; }

13、【简答题】给出下列算法中语句的时间复杂度 i=1;k=0; do { k=k 2*i; i ; } while(i!=n)

14、【简答题】给出下列算法中语句的时间复杂度 x=n;y=0; while(x>=(y 1)*(y 1)) y ;

15、【简答题】给出下列算法中语句的时间复杂度 x = 0; y = 0; for (int i = 1; i <= n; i ) for (int j = 1; j <= i; j ) for (int k = 1; k <= j; k ) x=x y;

2.4线性表章节测验

1、【单选题】线性表的第一个元素没有直接前驱,( )元素没有直接后继。
    a、第一个
    b、第二个
    c、最后一个
    d、所有

2、【单选题】假设线性表中有n个元素,如果在第i个位置插入一个新的元素,需向后移动( )个元素。
    a、n-i
    b、n-i 1
    c、n
    d、i

3、【判断题】链表元素的地址可以是不连续的

4、【判断题】顺序表在进行插入和删除元素时比较方便。

3.4堆栈和队列的章节测验

1、【单选题】元素a、b、c、d依次进栈后,则栈顶元素为( )。
    a、a
    b、b
    c、c
    d、d

2、【单选题】一个栈的进栈序列为abcd,则栈的输出序列不可能为( )。
    a、dcba
    b、abcd
    c、cabd
    d、cbad

3、【单选题】判断一个顺序栈s为空的条件是( )。
    a、s.top=-1
    b、s.top=maxsize-1
    c、s.top!=-1
    d、s.top!=maxsize

4、【单选题】判断一个顺序栈s为满的条件是( )。
    a、s.top=-1
    b、s.top=maxsize-1
    c、s.top!=-1
    d、s.top!=maxsize

5、【单选题】一个队列的入队顺序为abcd,则出队顺序为( )。
    a、abcd
    b、dcba
    c、cabd
    d、cbad

6、【单选题】假设循环队列q的队首指示为front,队尾指示为rear,则判断队空的条件为( )。
    a、q.front 1==q.rear
    b、q.rear 1==q.front
    c、q.front==q.rear
    d、q.front==0

7、【单选题】假设循环队列q的队首指示为front,队尾指示为rear,则判断队满的条件为( )。
    a、(q.rear 1)%maxsize==q.front 1
    b、(q.rear)%maxsize==q.front
    c、(q.rear 1)%maxsize==q.front
    d、q.rear==q.front

8、【判断题】堆栈是元素先进后出的线性结构。

9、【判断题】队列是只有一端可以操作的线性结构

4.5字符串的阶段测试

1、【单选题】串是一种特殊的线性表,其特征体现在( )
    a、可以顺序存储
    b、数据元素是一个字符
    c、数据元素可以是多个字符
    d、以上都不对

2、【单选题】有两个串p和q,求p在q中首次出现的位置的运算称为( )。
    a、链接
    b、模式匹配
    c、求串长
    d、求子串

3、【单选题】设字符串s1=“abcdefg”,s2=“pqrst”,则运算:s= concat(substr(s1,1,len(s2)),substr(s1,len(s2),2));后的串值为( )
    a、bcdef
    b、bcdefg
    c、bcdpqrst
    d、bcdeffg

4、【判断题】字符串的长度不能为0。

5、【判断题】字符串是数据元素类型都为字符的一种线性表

5.6数组与矩阵的阶段测试

1、【单选题】稀疏矩阵一般的压缩存储方法有两种,即()
    a、二维数组和三维数组
    b、三元组和散列
    c、三元组和十字链表
    d、散列和十字链表

2、【单选题】数组的基本操作主要包括()。
    a、建立与删除
    b、索引与修改
    c、访问和修改
    d、访问与索引

3、【单选题】设矩阵a是一个对称矩阵,为了节省空间,将其下三角矩阵按行存储存放在一个一维数组b[1,n(n 1)/2]中,对下三角部分中任一元素 (ij),在以为数组b中下标k的值是( )
    a、i(i-1)/2 j-1
    b、i(i-1)/2 j
    c、i(i 1)/2 j-1
    d、i(i 1)/2 j

4、【判断题】数组元素的个数不能小于等于1。

5、【判断题】数组元素的地址可以是不连续的。

6.5树的章节测试

1、【单选题】树型结构最适合用来描述( )。
    a、有序的数据元素
    b、无序的数据元素
    c、数据元素之间的具有层次关系的数据
    d、数据元素之间没有关系的数据

2、【单选题】在非空二叉树的中根遍历序列中,二叉树的根结点的左边应该( )。
    a、只有左子树上的所有结点
    b、只有左子树上的部分结点
    c、只有右子树上的所有结点
    d、只有右子树上的部分结点

3、【单选题】下面关于哈夫曼树的说法,不正确的是( )。
    a、对应于一组权值构造出的哈夫曼树一般不是惟一的
    b、哈夫曼树具有最小带权路径长度
    c、哈夫曼树中没有度为1的结点
    d、哈夫曼树中除了度为1的结点外,还有度为2的结点和叶子结点

4、【判断题】树结构中的父节点对子节点的关系是一对多的关系。

5、【判断题】树结构中的元素个数n必须大于0

7.5图的章节测试

1、【单选题】具有n个顶点的无向完全图的弧数为( )。
    a、n(n-1)/2
    b、n(n-1)
    c、n(n 1)/2
    d、n/2

2、【单选题】下列有关图遍历的说法中不正确的是( )。
    a、连通图的深度优先搜索是一个递归过程
    b、图的广度优先搜索中邻接点的寻找具有“先进先出”特征
    c、非连通图不能用深度优先搜索法
    d、图的遍历要求每一顶点仅被访问一次

3、【判断题】图结构可用邻接矩阵和邻接表两种方式存储

4、【判断题】图的广度优先搜索可用堆栈的先进后出特性存储拜访过的结点,以记录下一层要拜访的结点。

8.5查找的章节测试

1、【单选题】顺序查找法适合于存储结构为____的线性表。
    a、散列存储
    b、顺序存储或链接存储
    c、压缩存储
    d、索引存储

2、【单选题】对线性表进行二分查找时,要求线性表必须____。
    a、以顺序方式存储
    b、以链接方式存储
    c、以顺序方式存储,且结点按关键字有序排序
    d、以链接方式存储,且结点按关键字有序排序

3、【单选题】采用顺序查找方法查找长度为n的线性表时,每个元素的平均查找长度为____.
    a、n
    b、n/2
    c、(n 1)/2
    d、(n-1)/2

4、【单选题】采用二分查找方法查找长度为n的线性表时,每个元素的平均查找长度为____。
    a、o(n2)
    b、o(nlog2n)
    c、o(n)
    d、o(log2n)

5、【单选题】二分查找和二叉排序树的时间性能____。
    a、相同
    b、不相同

6、【单选题】有一个有序表为{1,3,9,12,32,41,45,62,75,77,82,95,100},当二分查找值82为的结点时,____次比较后查找成功。
    a、1
    b、2
    c、4
    d、8

7、【单选题】设哈希表长m=14,哈希函数h(key)=key。表中已有4个结点: addr (15)=4; addr (38)=5; addr (61)=6; addr (84)=7 如用二次探测再散列处理冲突,关键字为49的结点的地址是____。
    a、8
    b、3
    c、5
    d、9

8、【单选题】有一个长度为12的有序表,按二分查找法对该表进行查找,在表内各元素等概率情况下查找成功所需的平均比较次数为____。
    a、35/12
    b、37/12
    c、39/12
    d、43/12

9、【单选题】对于静态表的顺序查找法,若在表头设置岗哨,则正确的查找方式为 ()。
    a、从第0个元素往后查找该数据元素
    b、从第1个元素往后查找该数据元素
    c、从第n个元素往开始前查找该数据元素
    d、与查找顺序无关

10、【单选题】解决散列法中出现的冲突问题常采用的方法是()。
    a、数字分析法、除余法、平方取中法
    b、数字分析法、除余法、线性探测法
    c、数字分析法、线性探测法、多重散列法
    d、线性探测法、多重散列法、链地址法

11、【单选题】采用线性探测法解决冲突问题,所产生的一系列后继散列地址( )。
    a、必须大于等于原散列地址
    b、必须小于等于原散列地址
    c、可以大于或小于但不能等于原散列地址
    d、地址大小没有具体限制

12、【单选题】散列表的平均查找长度( )。
    a、与处理冲突方法有关而与表的长度无关
    b、与处理冲突方法无关而与表的长度有关
    c、与处理冲突方法有关而与表的长度有关
    d、与处理冲突方法无关而与表的长度无关

13、【判断题】分块查找属于静态查找

14、【判断题】哈希查找算法的时间复杂度是o(1)

9.5排序的章节测试

1、【单选题】从未排序序列中依次取出一个元素与已排序序列中的元素依次进行比较,然后将其放在已排序序列的合适位置,该排序方法称为()排序法。
    a、直接插入
    b、简单选择
    c、希尔
    d、二路归并

2、【单选题】直接插入排序在最好情况下的时间复杂度为()。
    a、o(logn)
    b、o(n)
    c、o(nlogn)
    d、o(n2)

3、【单选题】设有一组关键字值(46,79,56,38,40,84),则用堆排序的方法建立的初始堆为()。
    a、79,46,56,38,40,80
    b、84,79,56,38,40,46
    c、84,79,56,46,40,38
    d、84,56,79,40,46,38

4、【单选题】设有一组关键字值(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

5、【单选题】将两个各有n个元素的有序表归并成一个有序表,最少进行( )次比较.
    a、n
    b、2n-1
    c、2n
    d、n-1

6、【单选题】下列排序方法中,排序趟数与待排序列的初始状态有关的是( )。
    a、直接插入
    b、简单选择
    c、冒泡
    d、堆

7、【单选题】下列排序方法中,不稳定的是( )。
    a、直接插入
    b、冒泡
    c、二路归并
    d、堆

8、【单选题】若要在o(nlog2n)的时间复杂度上完成排序,且要求排序是稳定的,则可选择下列排序方法中的( )。
    a、快速
    b、堆
    c、二路归并
    d、直接插入

9、【单选题】设有1000个无序的数据元素,希望用最快的速度挑选出关键字最大的前10个元素,最好选用( )排序法。
    a、冒泡
    b、快速
    c、堆
    d、基数

10、【单选题】若待排元素已按关键字值基本有序,则下列排序方法中效率最高的是( )。
    a、直接插入
    b、简单选择
    c、快速
    d、二路归并

11、【单选题】数据序列(8,9,10,4,5,6,20,1,2)只能是下列排序算法中的( )的两趟排序后的结果。
    a、选择排序
    b、冒泡排序
    c、插入排序
    d、堆排序

12、【单选题】占用额外空间的空间复杂性为o(1)的排序算法是下列的()。
    a、堆排序算法
    b、归并排序算法
    c、快速排序算法
    d、以上答案都不对

13、【单选题】对一组数据(84,47,25,15,21)排序,数据的排列次序在排序的过程中的变化为 (a)84 47 25 15 21 (b)15 47 25 84 21 (c)15 21 25 84 47 (d)15 21 25 47 84 则采用的排序是( )。
    a、选择
    b、冒泡
    c、快速
    d、插入

14、【单选题】一个排序算法的时间复杂度与( )有关。
    a、排序算法的稳定性
    b、所需比较关键字的次数
    c、所采用的存储结构
    d、所需辅助存储空间的大小

15、【单选题】适合并行处理的排序算法是()。
    a、选择排序
    b、快速排序
    c、希尔排序
    d、基数排序

16、【单选题】下列排序算法中,( )算法可能会出现下面的情况:初始数据有序时,花费的时间反而最多。
    a、快速排序
    b、堆排序
    c、希尔排序
    d、冒泡排序

17、【单选题】有些排序算法在每趟排序过程中,都会有一个元素被放置在其最终的位置上,下列算法不会出现此情况的是( )。
    a、希尔排序
    b、堆排序
    c、冒泡排序
    d、快速排序

18、【单选题】在文件“局部有序”或文件长度较小的情况下,最佳内部排序的方法是( )
    a、直接插入排序
    b、冒泡排序
    c、简单选择排序
    d、快速排序

19、【单选题】下列排序算法中,( )算法可能会出现下面情况:在最后一趟开始之前,所有元素都不在其最终的位置上。
    a、堆排序排序
    b、冒泡排序
    c、快速排序
    d、插入排序

20、【单选题】下列排序算法中,占用辅助空间最多的是( )。
    a、归并排序
    b、快速排序
    c、希尔排序
    d、堆排序

21、【单选题】从未排序序列中依次取出一个元素与已排序序列中的元素依次进行比较,然后将其放在已排序序列的合适位置,该排序方法称为( )排序法。
    a、插入
    b、选择
    c、希尔
    d、二路归并

22、【单选题】用直接插入排序方法对下面四个序列进行排序(由小到大),元素比较次数最少的是( )。
    a、94,32,40,90,80,46,21,69
    b、32,40,21,46,69,94,90,80
    c、21,32,46,40,80,69,90,94
    d、90,69,80,46,21,32,94,40

23、【单选题】对序列{15,9,7,8,20,-1,4}用希尔排序方法排序,经一趟后序列变为{15,-l,4,8,20,9,7}则该次采用的增量是()。
    a、1
    b、4
    c、3
    d、2

24、【单选题】从堆中删除一个元素的时间复杂度为( )。
    a、o(1)
    b、o(log2n)
    c、o(n)
    d、(nlog2n)

25、【单选题】在对n个记录的线性表进行快速排序为减少算法的递归深度,以下叙述正确的是( )。
    a、每次分区后,先处理较短的部分
    b、每次分区后,先处理较长的部分
    c、与算法每次分区后的处理顺序无关
    d、以上三者都不对

26、【判断题】快速排序是不稳定的排序。

27、【判断题】希尔排序是不稳定的排序。

9.6阶段测试

1、【单选题】计算机算法指的是( )。
    a、计算机方法
    b、排序方法
    c、解决问题的有限步骤
    d、调度方法

2、【单选题】数据结构中,把数据结构从逻辑上分成( )。
    a、动态结构和静态结构
    b、紧凑结构和非紧凑结构
    c、线性结构和非线性结构
    d、内部结构和外部结构

3、【单选题】线性表是一个( )。
    a、有限序列,不能为空
    b、有限序列,可以为空
    c、无限序列,不能为空
    d、无限序列,可以为空

4、【单选题】线性表的第一个元素没有直接前驱,( )元素没有直接后继。
    a、第一个
    b、第二个
    c、最后一个
    d、所有

5、【单选题】假设线性表中有n个元素,如果在第i个位置插入一个新的元素,需向后移动( )个元素。
    a、n-i
    b、n-i 1
    c、n
    d、i

6、【单选题】元素a、b、c、d依次进栈后,则栈顶元素为( )。
    a、a
    b、b
    c、c
    d、d

7、【单选题】一个栈的进栈序列为abcd,则栈的输出序列不可能为( )。
    a、dcba
    b、abcd
    c、cabd
    d、cbad

8、【单选题】判断一个顺序栈s为空的条件是( )。
    a、s.top=-1
    b、s.top=maxsize-1
    c、s.top!=-1
    d、s.top!=maxsize

9、【单选题】判断一个顺序栈s为满的条件是( )。
    a、s.top=-1
    b、s.top=maxsize-1
    c、s.top!=-1
    d、s.top!=maxsize

10、【单选题】一个队列的入队顺序为abcd,则出队顺序为( )。
    a、abcd
    b、dcba
    c、cabd
    d、cbad

11、【单选题】假设循环队列q的队首指示为front,队尾指示为rear,则判断队空的条件为( )。
    a、q.front 1==q.rear
    b、q.rear 1==q.front
    c、q.front==q.rear
    d、q.front==0

12、【单选题】假设循环队列q的队首指示为front,队尾指示为rear,则判断队满的条件为( )。
    a、(q.rear 1)%maxsize==q.front 1
    b、(q.rear)%maxsize==q.front
    c、(q.rear 1)%maxsize==q.front
    d、q.rear==q.front

13、【单选题】树型结构最适合用来描述( )。
    a、有序的数据元素
    b、无序的数据元素
    c、数据元素之间的具有层次关系的数据
    d、数据元素之间没有关系的数据

14、【单选题】在非空二叉树的中根遍历序列中,二叉树的根结点的左边应该( )。
    a、只有左子树上的所有结点
    b、只有左子树上的部分结点
    c、只有右子树上的所有结点
    d、只有右子树上的部分结点

15、【单选题】下面关于哈夫曼树的说法,不正确的是( )。
    a、对应于一组权值构造出的哈夫曼树一般不是惟一的
    b、哈夫曼树具有最小带权路径长度
    c、哈夫曼树中没有度为1的结点
    d、哈夫曼树中除了度为1的结点外,还有度为2的结点和叶子结点

16、【单选题】具有n个顶点的无向完全图的弧数为( )。
    a、n(n-1)/2
    b、n(n-1)
    c、n(n 1)/2
    d、n/2

17、【单选题】下列有关图遍历的说法中不正确的是( )。
    a、连通图的深度优先搜索是一个递归过程
    b、图的广度优先搜索中邻接点的寻找具有“先进先出”特征
    c、非连通图不能用深度优先搜索法
    d、图的遍历要求每一顶点仅被访问一次

18、【单选题】设有一组关键字值(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

19、【判断题】算法可以没有输入。

20、【判断题】有输出的算法才是有意义的。

21、【判断题】链表元素的地址可以是不连续的

22、【判断题】顺序表在进行插入和删除元素时比较方便。

23、【判断题】堆栈是元素先进后出的线性结构。

24、【判断题】队列是只有一端可以操作的线性结构

25、【判断题】树结构中的父节点对子节点的关系是一对多的关系。

26、【判断题】树结构中的元素个数n必须大于0

27、【判断题】图结构可用邻接矩阵和邻接表两种方式存储

28、【判断题】图的广度优先搜索可用堆栈的先进后出特性存储拜访过的结点,以记录下一层要拜访的结点。

11.11期末考试

1、【单选题】线性表是一个( )。
    a、有限序列,不能为空
    b、有限序列,可以为空
    c、无限序列,不能为空
    d、无限序列,可以为空

2、【单选题】线性表的第一个元素没有直接前驱,( )元素没有直接后继。
    a、第一个
    b、第二个
    c、最后一个
    d、所有

3、【单选题】假设线性表中有n个元素,如果在第i个位置插入一个新的元素,需向后移动( )个元素。
    a、n-i
    b、n-i 1
    c、n
    d、i

4、【单选题】元素a、b、c、d依次进栈后,则栈顶元素为( )。
    a、a
    b、b
    c、c
    d、d

5、【单选题】一个栈的进栈序列为abcd,则栈的输出序列不可能为( )。
    a、dcba
    b、abcd
    c、cabd
    d、cbad

6、【单选题】判断一个顺序栈s为空的条件是( )。
    a、s.top=-1
    b、s.top=maxsize-1
    c、s.top!=-1
    d、s.top!=maxsize

7、【单选题】判断一个顺序栈s为满的条件是( )。
    a、s.top=-1
    b、s.top=maxsize-1
    c、s.top!=-1
    d、s.top!=maxsize

8、【单选题】一个队列的入队顺序为abcd,则出队顺序为( )。
    a、abcd
    b、dcba
    c、cabd
    d、cbad

9、【单选题】假设循环队列q的队首指示为front,队尾指示为rear,则判断队空的条件为( )。
    a、q.front 1==q.rear
    b、q.rear 1==q.front
    c、q.front==q.rear
    d、q.front==0

10、【单选题】假设循环队列q的队首指示为front,队尾指示为rear,则判断队满的条件为( )。
    a、(q.rear 1)%maxsize==q.front 1
    b、(q.rear)%maxsize==q.front
    c、(q.rear 1)%maxsize==q.front
    d、q.rear==q.front

11、【判断题】链表元素的地址可以是不连续的

12、【判断题】顺序表在进行插入和删除元素时比较方便。

13、【判断题】堆栈是元素先进后出的线性结构。

14、【判断题】队列是只有一端可以操作的线性结构