西工大16秋《数据结构》在线作业资料

admin

一、单选题（共 40 道试题，共 80 分。）

1.  已知广义表ls=(,(,,),)，运用h和til函数取出ls中原子的运算是（ ）。
. h(h(ls))
. til(h(ls))
. h(h(til(ls)))
. h(til(ls))
    标准资料：
2.  在双向循环链表中，在p指针所指向的结点前插入一个指针q所指向的新结点其修改指针的操作是（ ）。（双向链表的结点结构是llink，t，rlink）
. p->llink=q;q->rlink=p;p->llink->rlink=q;q->llink=q;
. p->llink=q; p->llink->rlink=q; q ->rlink=p;q->llink= p->llink;
. p->llink=q; q->llink= p->llink; p->llink->rlink=q;p->llink=q;
. q->llink= p->llink;q->rlink=p; p->llink =q;p->llink=q;
    标准资料：
3.  树形结构最适合用来描述（ ）。
. 有序的数据元素
. 无序的数据元素
. 数据元素之间的具有层次关系的数据
. 数据元素之间没有关系的数据
    标准资料：
4.  下列程序段的时间复杂度是（ ）。 or(i=0;i<="" [i][j]="0;" or(j="1;j<m;j++)">
. O(n)
. O(m+n+1)
. O(m+n)
. O(m*n)
    标准资料：
5.  如果T2是由有序树T转换而来的二叉树，那么T中结点的后序就是T2结点的（ ）。
. 先序
. 中序
. 后序
. 层序
    标准资料：
6.  折半查找法的时间复杂度是（ ）。
. O(n*n)
. O(n)
. O(nlogn)
. O(logn)
    标准资料：
7.  有一个10阶的对称矩阵，采用压缩存储方式，以行序为主序，11为第一个元素，其存储地址为1，每个元素占1个地址空间，则85的地址为（ ）。
. 13
. 33
. 18
. 40
    标准资料：
8.  表达式INX(‘TSTRUTUR’,’STR’)的运算结果是（ ）。
. 5
. 4
. 6
. 3
    标准资料：
9.  若结点的存储地址与其关键字之间存在某种映射关系，则称这种存储结构为（ ）。
. 顺序存储结构
. 链式存储结构
. 索引存储结构
. 散列存储结构
    标准资料：
10.  算法指的是（ ）。
. 计算机程序
. 解决问题的计算方法
. 排序算法
. 解决问题的有限运算序列
    标准资料：
11.  数据表中有10000个元素，如果仅要求求出其中最大的10个元素，则采用（ ）排序算法最节省时间。
. 堆排序
. 希尔排序
. 快速排序
. 直接选择排序
    标准资料：
12.  已知广义表=((,,)，(,,))，从中取出原子的运算是（ ）。
. til(h())
. h(til())
. h(til(til(h())))
. h(til(til()))
    标准资料：
13.  广义表运算式til[((,),(,))]的结果为（ ）。
. ,
. (,)
. ((,))
. ,
    标准资料：
14.  希尔排序的增量序列必须是（ ）。
. 递增的
. 随机的
. 递减的
. 非递减的
    标准资料：
15.  设有两个串p和q，其中q是p的字串，求q在p中首次出现的位置的算法称为（ ）。
. 求子串
. 联接
. 匹配
. 求串长
    标准资料：
16.  若串S=’syntx’，其字串的数目是（ ）。
. 6
. 21
. 22
. 7
    标准资料：
17.  深度为5的二叉树至多有结点数为（ ）。
. 16
. 30
. 31
. 32
    标准资料：
18.  n个顶点的强连通图至少有（ ）条边。
. n-1
. n
. 2n
. n(n-1)
    标准资料：
19.  具有65个结点的完全二叉树的高度为（ ）。（根的层次号为0）
. 8
. 7
. 6
. 5
    标准资料：
20.  在数据结构中，数据的逻辑结构可以分为（ ）。
. 内部结构和外部结构
. 线性结构和非线性结构
. 紧凑结构和非紧凑结构
. 动态结构和静态结构
    标准资料：
21.  在n个顶点的有向完全图中，边的总数为（ ）条。
. n(n-1)/2
. n(n-1)
. n(n-2)
. 2n
    标准资料：
22.  适于对动态查找表进行高效率查找的组织结构是（ ）。
. 有序表
. 分块有序表
. 三叉排序树
. 线性链表
    标准资料：
23.  对于一个具有n个顶点和条边的无向图，若采用邻接表表示，则所有顶点邻接表中的结点总数为（ ）。
. 2*n
. 2*
. n
.
    标准资料：
24.  线索二叉树是一种（ ）结构。
. 逻辑
. 逻辑和存储
. 物理
. 线性
    标准资料：
25.  计算机识别、存储和加工处理的对象被统称为（ ）。
. 数据
. 数据元素
. 数据结构
. 数据类型
    标准资料：
26.  若待排序列已基本有序，要使它们完全有序，从关键码比较次数和移动次数考虑，应当使用的排序方法是（ ）。
. 归并排序
. 直接插入排序
. 直接选择排序
. 快速排序
    标准资料：
27.  在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡结点为，并已知的左孩子的平衡因子为-1，右孩子的平衡因子为0，则应作（ ）型调整以使其平衡。
. LL
. LR
. RL
. RR
    标准资料：
28.  一个广义表为(,(,),,,((i,j),k))，则该广义表的长度和深度分别为（ ）。
. 5和3
. 5和4
. 4和3
. 4和4
    标准资料：
29.  设无向图G中顶点数为n，图G最多（ ）有条边。
. n
. n-1
. n*(n-1)/2
. n*(n-1)
    标准资料：
30.  一个n*n的对称矩阵，如果以行或列为主序存入内存，则其容量为（ ）。
. n*n
. n*(n+1)/2
. (n+1)*(n+1)/2
. (n-1)*n/2
    标准资料：
31.  为了方便的在线性结构的数据中插入一个数据元素，则其数据结构宜采用（ ）。
. 顺序存储
. 链式存储
. 索引存储
. 散列存储
    标准资料：
32.  二维数组的每个元素是由6个字符组成的串，行下标i的范围从0～8，列下标j的范围从1～10。若按行存放，元素[8,5]的起始地址与当按列存放时的元素（ ）的起始地址一致（每个字符占一个字节）。
. [8,5]
. [3,10]
. [5,8]
. [0,9]
    标准资料：
33.  对表长为n的顺序表进行顺序查找，在查找概率相等的情况下，查找成功的平均查找长度为（ ）。
. （n-1）/2
. n/2
. (n+1)/2
. n
    标准资料：
34.  如果某图的邻接矩阵时对角线元素均为零的上三角矩阵，则此图是（ ）。
. 有向完全图
. 连通图
. 强连通图
. 有向无环图
    标准资料：
35.  对于哈希函数H（ky）=ky%13，被称为同义词的关键字是（ ）。
. 35和41
. 23和39
. 15和44
. 25和51
    标准资料：
36.  下述排序算法中，稳定的是（ ）。
. 直接选择排序
. 表插入排序
. 快速排序
. 堆排序
    标准资料：
37.  对于单链表形式的队列，队空的条件是（ ）。
. =R=null
. =R
. ≠null且R=null
. R-=1
    标准资料：
38.  设有5000个元素，希望用最快速度挑选出其中前10个最大的元素，在以下的排序方法中，采用那一种最好（ ）。
. 快速排序
. 堆排序
. 归并排序
. 基数排序和shll排序
    标准资料：
39.  向顺序栈中压入新元素时，习惯上应当（ ）。
. 先移动栈顶指针，再存入元素
. 先存入元素，再移动栈顶指针
. 先后次序无关紧要
. 同时进行
    标准资料：
40.  数组[1..10，-2..6，2..8]以行优先的顺序存储，设第一个元素的首址是100，每个元素的长度为3。元素[5,0,7]的存储首址为（ ）。
. 900
. 912
. 910
. 913
    标准资料：


二、判断题（共 10 道试题，共 20 分。）

1.  在链表中存储线性表中的第一个数据元素的结点是首元结点。（ ）
. 错误
. 正确
    标准资料：
2.  根据线性表的链式存储结构，每个结点所含指针的个数，链表分为循环链表和普通链表。（ ）
. 错误
. 正确
    标准资料：
3.  若一个栈的输出序列是1,2,3，...，n，输出序列的第一个元素是n，则第i个输出元素是n-i+1。（ ）
. 错误
. 正确
    标准资料：
4.  POP（PUSH（S，））的运算步骤是首先将元素压入栈中，若栈S满，出现上溢现象，否则将元素压入栈顶，且元素个数加1，然后做POP（S）运算，将栈顶元素弹出，且元素个数减一。（ ）
. 错误
. 正确
    标准资料：
5.  图的生成树是不唯一的，一个连通图的生成树是一个最小连通子图，n个顶点的生成树有n-1条边，最小代价生成树是唯一的。（ ）
. 错误
. 正确
    标准资料：
6.  算法的计算量的大小称为计算的复杂性。（ ）
. 错误
. 正确
    标准资料：
7.  模式串P=’’的nxt函数值序列为01122313。（ ）
. 错误
. 正确
    标准资料：
8.  线性表中元素数量基本稳定，且很少进行插入和删除，要求以最快的速度存取线性表中的元素，此线性表宜采用链式存储结构。（ ）
. 错误
. 正确
    标准资料：
9.  被计算机加工的数据元素不是孤立无关的，它们彼此之间一般存在着某种联系通常将数据元素间的这种联系关系称为结构。（ ）
. 错误
. 正确
    标准资料：
10.  在顺序表中插入或删除一个元素，需要平均移动n/2个元素，具体移动的元素个数与插入或删除元素的位置有关。（ ）
. 错误
. 正确
    标准资料：