天津大学19秋《数据结构》在线作业一

奥鹏网院作业

天津大学19秋《数据结构》在线作业一

1.任何一棵二叉树的叶结点在先序、中序和后序遍历序列中的相对次序（）。
A.不发生改变
B.发生改变
C.不能确定
D.以上都不对
答案
2.下面程序的时间复杂为（）for（i=1，s=0；i=n；i++）{t=1；for(j=1；j=i；j++)t=t*j；s=s+t；}
A.O(n)
B.O(n2)
C.O(n3)
D.O(n4)
答案
3.二维数组A中，每个元素A的长度为3个字节，行下标i从0到7，列下标j从0到9，从首地址SA开始连续存放在存储器内，该数组按列存放时，元素A[4][7]的起始地址为（）。
A.SA+141
B.SA+180
C.SA+222
D.SA+225
答案
4.对于线性表（7，34，55，25，64，46，20，10）进行散列存储时，若选用H（K）=K%9作为散列函数，则散列地址为1的元素有（）个.
A.1
B.2
C.3
D.4
答案
5.一个队列的数据入列序列是1，2，3，4，则队列的出队时输出序列是（）。
A.4，3，2，1
B.1，2，3，4
C.1，4，3，2
D.3，2，4，1
答案
6.二维数组A中，每个元素A的长度为3个字节，行下标i从0到7，列下标j从0到9，从首地址SA开始连续存放在存储器内，该数组按行存放时，数组元素A[7][4]的起始地址为（）。
A.SA+141
B.SA+144
C.SA+222
D.SA+225
答案
7.以下数据结构中哪一个是非线性结构？()
A.队列
B.栈
C.线性表
D.二叉树
答案
8.设某有向图的邻接表中有n个表头结点和m个表结点，则该图中有（）条有向边。
A.n
B.n1
C.m
D.m1
答案
9.在二叉排序树中插入一个结点的时间复杂度为（）。
A.O(1)
B.O(n)
C.O(log2n)
D.O(n2)
答案
10.设某二叉树中度数为0的结点数为N0，度数为1的结点数为Nl，度数为2的结点数为N2，则下列等式成立的是（）。
A.N0=N1+1
B.N0=Nl+N2
C.N0=N2+1
D.N0=2N1+l
答案
11.对n个记录的文件进行快速排序，所需要的辅助存储空间大致为()
A.O（1）
B.O（n）
C.O（1og2n）
D.O（n2）
答案
12.用链接方式存储的队列，在进行插入运算时().
A.仅修改头指针
B.头、尾指针都要修改
C.仅修改尾指针
D.头、尾指针可能都要修改
答案
13.设一组初始记录关键字序列为(345，253，674，924，627)，则用基数排序需要进行（）趟的分配和回收才能使得初始关键字序列变成有序序列。
A.3
B.4
C.5
D.8
答案
14.哈希表中的冲突可以通过改变哈希函数完全避免。
A.正确
B.错误
答案
15.线性表的顺序存储结构是一种（）的存储结构。
A.随机存取
B.索引存取
C.顺序存取
D.散列存取
答案
16.判定一个循环队列QU（最多元素为m0m0==Maxsize1）为满队列的条件是（）。
A.((rearfront)+Maxsize)%Maxsize==m0
B.rearfront1==m0
C.front==rear
D.front==rear+1
答案
17.设有序顺序表中有n个数据元素，则利用二分查找法查找数据元素X的最多比较次数不超过（）。
A.log2n+1
B.log2n1
C.log2n
D.log2(n+1)
答案
18.设某数据结构的二元组形式表示为A=(D，R)，D={01，02，03，04，05，06，07，08，09}，R={r}，r={01，02，01，03，01，04，02，05，02，06，03，07，03，08，03，09}，则数据结构A是（）。
A.线性结构
B.树型结构
C.物理结构
D.图型结构
答案
19.设一组初始记录关键字序列(5，2，6，3，8)，以第一个记录关键字5为基准进行一趟快速排序的结果为（）。
A.2，3，5，8，6
B.3，2，5，8，6
C.3，2，5，6，8
D.2，3，6，5，8
答案
20.设有n个待排序的记录关键字，则在堆排序中需要（）个辅助记录单元。
A.1
B.n
C.nlog2n
D.n2
答案
21.某二叉树的前序遍历结点访问顺序是abdgcefh，中序遍历的结点访问顺序是dgbaechf，则其后序遍历的结点访问顺序是（）。
A.bdgcefha
B.gdbecfha
C.bdgaechf
D.gdbehfca
答案
22.设高度为h的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的结点数至少为（）。
A.2h
B.2h1
C.2h+1
D.h+1
答案
23.在一个AOE网中，关键路径就是其中路径长度最短的路径。
A.正确
B.错误
答案
24.设无向图的顶点个数为n，则该图最多有（）条边。
A.n1
B.n(n1)/2
C.n(n+1)/2
D.0
答案
25.按照二叉树的定义，具有3个结点的不同形状的二叉树有（）种。
A.3
B.4
C.5
D.6
答案
26.设某有向图中有n个顶点，则该有向图对应的邻接表中有（）个表头结点。
A.n1
B.n
C.n+1
D.2n1
答案
27.在用循环单链表表示的链式队列中，可以不设队头指针，仅在链尾设置队尾指针。
A.正确
B.错误
答案
28.栈结构通常采用的两种存储结构是（）。
A.顺序存储结构和链式存储结构
B.散列方式和索引方式
C.链表存储结构和数组
D.线性存储结构和非线性存储结构
答案
29.在线索化二叉树中，t所指结点没有左子树的充要条件是（）。
A.t—＞left=NULL
B.t—＞ltag=1
C.t—＞ltag=1且t—＞left=NULL
D.以上都不对
答案
30.二维数组A中，每个元素的长度为3个字节，行下标i从0到7，列下标j从0到9，从首地址SA开始连续存放在存储器内，存放该数组至少需要的字节数是（）。
A.80
B.100
C.240
D.270
答案
31.以下叙述中正确的是（）。
A.串是一种特殊的线性表
B.串的长度必须大于零
C.串中无素只能是字母
D.空串就是空白串
答案
32.设无向图G中有n个顶点e条边，则其对应的邻接表中的表头结点和表结点的个数分别为（）。
A.n，e
B.e，n
C.2n，e
D.n，2e
答案
33.设一维数组中有n个数组元素，则读取第i个数组元素的平均时间复杂度为（）。
A.O(n)
B.O(nlog2n)
C.O(1)
D.O(n2)
答案
34.设一组初始关键字记录关键字为(20，15，14，18，21，36，40，10)，则以20为基准记录的一趟快速排序结束后的结果为()。
A.10，15，14，18，20，36，40，21
B.10，15，14，18，20，40，36，21
C.10，15，14，20，18，40，36，2l
D.15，10，14，18，20，36，40，21
答案
35.进行折半搜索的表必须是顺序存储的有序表。
A.正确
B.错误
答案
36.按照二叉树的定义，具有3个不同数据结点的不同的二叉树有（）种。
A.5
B.6
C.30
D.32
答案
37.设有一个二维数组A[m][n]，假设A[0][0]存放位置在644(10)，A[2][2]存放位置在676(10)，每个元素占一个空间，问A[3][3](10)存放在()位置.脚注(10)表示用10进制表示。
A.688
B.678
C.692
D.696
答案
38.实现任意二叉树的后序遍历的非递归算法而不使用栈结构，最佳方案是二叉树采用（）存储结构。
A.二叉链表
B.广义表存储结构
C.三叉链表
D.顺序存储结构
答案
39.从一个具有n个结点的单链表中查找其值等于x结点时，在查找成功的情况下，需平均比较（）个结点。
A.n
B.n/2
C.(n1)/2
D.(n+1)/2
答案
40.串是一中特殊的线性表，其特殊性体现在（）。
A.可以顺序存储
B.数据元素是一个字符
C.可以链接存储
D.数据元素可以是多个字符
答案