21秋福师《数据结构概论》在线作业一[答案]

21秋福师《数据结构概论》在线作业一[答案]答案

福师《数据结构概论》在线作业一-0002

试卷总分:100 得分:100

一、单选题 (共 25 道试题,共 50 分)

1.下列排序算法中（ ）算法可能会出现下面情况：在最后一趟开始之前，所有元素都不在其最终的位置上。

A.堆排序

B.冒泡排序

C.快速排序

D.插入排序

正确答案:-----

2.n个结点的线索二叉树上含有的线索数为（ ）

A.2n

B.n－l

C.n＋l

D.n

正确答案:-----

3.输入序列为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

正确答案:-----

4.数组A[0..4,-1..-3,5..7]中含有元素的个数（ ）

A.55

B.45

C.36

D.16

正确答案:-----

5.栈和队都是（ ）

A.顺序存储的

B.线性结构

C.链式存储的

D.非线性结构

正确答案:-----

6.设给定权值总数有n 个，其哈夫曼树的结点总数为( )

A.不确定

B.2n

C.2n+1

D.2n-1

正确答案:-----

正确答案:-----

7.以下属于 非容器类控件 的是?

A.Form

B.Label

C.page

D.Container

正确答案:-----

8.广义表运算式Tail(((a,b),(c,d)))的操作结果是（ ）。

正确答案:-----

A.(c,d)

正确答案:-----

B.c,d

C.((c,d))

正确答案:-----

D.d

正确答案:-----

9.假设以行序为主序存储二维数组A=array[1..100，1..100]，设每个数据元素占2个存储单元，基地址为10，则LOC[5，5]=（ ）。

A.808

B.821

C.1010

D.1020

正确答案:-----

10.为了使索引键的值在基本表中唯一，在建立索引语句中应使用下面哪个保留字？

A.UNIQUE

B.COUNT

C.DISDINCT

正确答案:-----

D.UNION

正确答案:-----

11.以下数据结构中（ ）是非线性数据结构

A.树

B.字符串

C.队

D.栈

正确答案:-----

12.若二叉树采用二叉链表存储结构，要交换其所有分支结点左、右子树的位置，利用( )遍历方法最合适。

A.前序

B.中序

C.后序

D.按层次

正确答案:-----

13.适用于折半查找的表的存储方式及元素排列要求为( )

A.链接方式存储，元素无序

B.链接方式存储，元素有序

C.顺序方式存储，元素无序

D.顺序方式存储，元素有序

正确答案:-----

14.下面的程序段中，对x的赋值语句的频度为（ ）FOR i:=1 TO n DOFOR j:=1 TO n DO x:=x+1;

正确答案:-----

A.O(2n)

B.O(n)

C.O(n^2)

D.O(log2n)

正确答案:-----

15.关键路径是事件结点网络中（ ）

A.从源点到汇点的最长路径

B.从源点到汇点的最短路径

C.最长回路

D.最短回路

正确答案:-----

16.下列排序算法中，在待排序数据已有序时，花费时间反而最多的是( )排序

A.冒泡

B.希尔

C.快速

D.堆

正确答案:-----

17.设有两个串p和q，其中q是p的子串，求q在p中首次出现的位置的算法称为（ ）

A.求子串

B.联接

C.匹配

D.求串长

正确答案:-----

21.下面有关算法说法错误的是（ ）

A.算法最终必须由计算机程序实现

B.为解决某问题的算法同为该问题编写的程序含义是相同的

C.算法的可行性是指指令不能有二义性

D.以上几个都是错误的

正确答案:-----

19.串的长度是指（ ）

A.串中所含不同字母的个数

B.串中所含字符的个数

C.串中所含不同字符的个数

D.串中所含非空格字符的个数

正确答案:-----

20.下面叙述正确的是（ ）

A.算法的执行效率与数据的存储结构无关

B.算法的空间复杂度是指算法程序中指令(或语句)的条数

C.算法的有穷性是指算法必须能在执行有限个步骤之后终止

D.以上三种描述都不对

正确答案:-----

21.设有部门和职员两个实体，每个职员只能属于一个部门，一个部门可以有多名职员，则部门与职员实体之间的联系类型是

A.m:n

B.1:m

C.m:k

D.1:1

正确答案:-----

22.有n个叶子的哈夫曼树的结点总数为（ ）。

A.不确定

B.2n

C.2n+1

D.2n-1

23.下面关于关系数据模型的说法，正确的是哪一项？

A.只能表示实体间的1：1联系

B.只能表示实体间的l：n联系

C.只能表示实体间的m：n联系

D.可以表示实体间的上述三种联系

正确答案:-----

24.若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为（ ）(1<=i<=n+1)。

A.O(0)

B.O(1)

C.O(n)

D.O(n2)

正确答案:-----

25.线索二叉树是一种（ ）构。

A.逻辑

B.逻辑和存储

C.物理

D.线性

正确答案:-----

21秋福师《数据结构概论》在线作业一[答案]多选题答案

二、判断题 (共 20 道试题,共 40 分)

26.当待排序记录已经从小到大排序或者已经从大到小排序时，快速排序的执行时间最省。

27.通常使用队列来处理函数或过程的调用（ ）

28.对于有N个结点的二叉树，其高度为log2n。

29.在待排数据基本有序的情况下，快速排序效果最好（ ）

30.SQL语言的事务管理主要通过‘事务提交COMMIT’和‘事务撤消ROLLBACK（回滚）’两个命令来实现的。

31.对一棵二叉树进行层次遍历时，应借助于一个栈

32.直接选择排序算法在最好情况下的时间复杂度为O（N）（ ）

33.一条没有指明去向的SQL SELECT语句执行之后，会把查询结果显示在屏幕上，要退出这个查询窗口，应按 ESC。

34.线性表采用链表存储时，结点和结点内部的存储空间可以是不连续的（ ）

35.在查找树（二叉树排序树）中插入一个新结点，总是插入到叶结点下面（ ）

36.对无序表用二分法查找比顺序查找快

37.两分法插入排序所需比较次数与待排序记录的初始排列状态相关。

38.循环链表不是线性表（ ）