天大17春《数据结构》在线作业一二满分答案
天大17春《数据结构》在线作业一1.在二叉排序树中插入一个结点的时间复杂度为( )。 (满分:2.5)
A. O(1)
B. O(n)
C. O(log2n)
D. O(n2 )
2.非空的循环单链表head的尾结点（由p所指向）满足( )。 (满分:2.5)
A. p->next= =NULL
B. p= =NULL
C. p->next= =head
D. p= =head
3.二维数组M的成员是6个字符（每个字符占一个存储单元，即一个字节）组成的串，行下标i的范围从0到8，列下标j的范围从0到9，则存放M 至少需要( )个字节。 (满分:2.5)
A. 90
B. 180
C. 240
D. 540
4.线性表的顺序存储结构是一种( )的存储结构。 (满分:2.5)
A. 随机存取
B. 索引存取
C. 顺序存取
D. 散列存取
5.一个栈的入栈序列a，b，c，d，e，则栈的不可能的输出序列是( )。 (满分:2.5)
A. edcba
B. decba
C. dceab
D. abcde
6.设串s1='ABCDEFG'，s2='PQRST'，函数con(x,y)返回x和y串的连接串，subs(s,i,j)返回串s的从序号i的字符开始的j个字符组成的子串，len(s)返回串s的长度，则con(subs(s1,2,len(s2)),subs(s1,len(s2),2))的结果串是( )。 (满分:2.5)
A. BCDEF
B. BCDEFG
C. BCPQRST
D. BCDEFEF
7.设顺序循环队列Q的头指针和尾指针分别为F和R，头指针F总是指向队头元素的前一位置，尾指针R总是指向队尾元素的当前位置，则该循环队列中的元素个数为( )。 (满分:2.5)
A. R-F
B. F-R
C.(R-F+M)％M
D.(F-R+M)％M
8.在一个单链表中，若删除p所指结点的后续结点，则执行( )。 (满分:2.5)
A. p->next=p->next->next;
B. p=p->next;p->next=p->next->next;
C. p->next=p->next;
D. p=p->next->next；
9.设一棵二叉树的深度为k，则该二叉树中最多有( )个结点。 (满分:2.5)
A. 2k-1
B. 2k
C. 2k-1
D. 2k -1
10.如果某二叉树的前根次序遍历结果为stuwv，中序遍历为uwtvs，那么该二叉树的后序为( )。 (满分:2.5)
A. uwvts
B. vwuts
C. wuvts
D. wutsv
11.在数据结构中，从逻辑上可以把数据结构分成( )。 (满分:2.5)
A. 动态结构和静态结构
B. 紧凑结构和非紧凑结构
C. 线性结构和非线性结构
D. 内部结构和外部结构
12.在一棵具有5层的满二叉树中结点数为( ) (满分:2.5)
A. 33
B. 32
C. 31
D. 31
13.在一个单链表中，若p所指结点不是最后结点，在p之后插入s所指结点，则执行( )。 (满分:2.5)
A. s->next=p;p->next=s;
B. s->next=p->next;p->next=s;
C. s->next=p->next;p=s;
D. p->next=s;s->next=p;
14.判定一个循环队列QU（最多元素为m0, m0= =Maxsize-1）为满队列的条件是( )。 (满分:2.5)
A.((rear- front)+ Maxsize)% Maxsize = =m0
B. rear-front-1= =m0
C. front= =rear
D. front= = rear+1
15.实现任意二叉树的后序遍历的非递归算法而不使用栈结构，最佳方案是二叉树采用( )存储结构。 (满分:2.5)
A. 二叉链表
B. 广义表存储结构
C. 三叉链表
D. 顺序存储结构
16.在线索化二叉树中，t所指结点没有左子树的充要条件是( )。 (满分:2.5)
A. t—＞left=NULL
B. t—＞ltag=1
C. t—＞ltag=1且t—＞left=NULL
D. 以上都不对
17.在一非空二叉树的中序遍历序列中，根结点的右边( )。 (满分:2.5)
A. 只有右子树上的所有结点
B. 只有右子树上的部分结点
C. 只有左子树上的部分结点
D. 只有左子树上的所有结点
18.一个队列的数据入列序列是1，2，3，4，则队列的出队时输出序列是( ) 。 (满分:2.5)
A. 4，3，2，1
B. 1，2，3，4
C. 1，4，3，2
D. 3，2，4，1
19.线性表若采用链式存储结构时，要求内存中可用存储单元的地址( )。 (满分:2.5)
A. 必须是连续的
B. 部分地址必须是连续的
C. 一定是不连续的
D. 连续或不连续都可以
20.链式存储在插入和删除时需要保持物理存储空间的顺序分配，不需要保持数据元素之间的逻辑顺序。 (满分:2.5)
A. 正确
B. 错误
21.二维数组A中，每个元素A的长度为3个字节，行下标i从0到7，列下标j从0到9，从首地址SA开始连续存放在存储器内，该数组按行存放时，数组元素A的起始地址为( )。 (满分:2.5)
A. SA+141
B. SA+144
C. SA+222
D. SA+225
22.假定在一棵二叉树中，双分支结点数为15，单分支结点数为30个，则叶子结点数为( )个。 (满分:2.5)
A. 15
B. 16
C. 17
D. 47
23.在一个单链表中，已知q所指结点是p所指结点的前驱结点，若在q和p之间插入s结点，则执行( )。 (满分:2.5)
A. s->next=p->next;p->next=s;
B. p->next=s->next;s->next=p;
C. q->next=s;s->next=p;
D. p->next=s;s->next=q;
24.判定一个顺序栈ST（最多元素为m0）为空的条件是( )。 (满分:2.5)
A. top!=0
B. top= =0
C. top!=m0
D. top= =m0-1
25.设某无向图中有n个顶点e条边，则该无向图中所有顶点的入度之和为( )。 (满分:2.5)
A. n
B. e
C. 2n
D. 2e
26.不带头结点的单链表head为空的判定条件是( )。 (满分:2.5)
A. head= =NULL
B. head->next= =NULL
C. head->next= =head
D. head!=NULL
27.设a,b为一棵二叉树上的两个结点，在中序遍历时，a在b前的条件是( )。 (满分:2.5)
A. a在b的右方
B. a在b的左方
C. a是b的祖先
D. a是b的子孙
28.设某有向图的邻接表中有n个表头结点和m个表结点，则该图中有( )条有向边。 (满分:2.5)
A. n
B. n-1
C. m
D. m-1
29.设一维数组中有n个数组元素，则读取第i个数组元素的平均时间复杂度为( )。 (满分:2.5)
A. O(n)
B. O(nlog2n)
C. O(1)
D. O(n2 )
30.按照二叉树的定义，具有3个不同数据结点的不同的二叉树有( )种。 (满分:2.5)
A. 5
B. 6
C. 30
D. 32
31.若已知一个栈的入栈序列是1，2，3，…，n，其输出序列为p1，p2，p3，…，pn，若p1=n，则pi为( )。 (满分:2.5)
A. i
B. n=i
C. n-i+1
D. 不确定
32.在用循环单链表表示的链式队列中，可以不设队头指针，仅在链尾设置队尾指针。 (满分:2.5)
A. 正确
B. 错误
33.从一个栈顶指针为HS的链栈中删除一个结点时，用x保存被删结点的值，则执行( )。(不带空的头结点) (满分:2.5)
A. x=HS;HS= HS—＞next;
B. x=HS—＞data;
C. HS=HS—＞next;x=HS—＞data;
D. x=HS—＞data;HS= HS—＞next;
34.以下数据结构中哪一个是非线性结构？( ) (满分:2.5)
A. 队列
B. 栈
C. 线性表
D. 二叉树
35.常对数组进行的两种基本操作是( )。 (满分:2.5)
A. 建立与删除
B. 索引和修改
C. 对数据元素的存取和修改
D. 查找与索引
36.设某强连通图中有n个顶点，则该强连通图中至少有( )条边。 (满分:2.5)
A. n(n-1)
B. n+1
C. n
D. n(n+1)
37.栈结构通常采用的两种存储结构是( )。 (满分:2.5)
A. 顺序存储结构和链式存储结构
B. 散列方式和索引方式
C. 链表存储结构和数组
D. 线性存储结构和非线性存储结构
38.设串的长度为n，则它的子串个数为( )。 (满分:2.5)
A. n
B. n(n+1)
C. n(n+1)/2
D. n(n+1)/2+1
39.具有五层结点的二叉平衡树至少有( )个结点。 (满分:2.5)
A. 10
B. 12
C. 15
D. 17
40.设某棵二叉树的中序遍历序列为ABCD，前序遍历序列为CABD，则后序遍历该二叉树得到序列为( )。 (满分:2.5)
A. BADC
B. BCDA
C. CDAB
D. CBDA
《数据结构》在线作业二
一、单选题：
1.设一组权值集合W=(15，3，14，2，6，9，16，17)，要求根据这些权值集合构造一棵哈夫曼树，则这棵哈夫曼树的带权路径长度为( )。 (满分:2.5)
A. 129
B. 219
C. 189
D. 229
2.利用直接插入排序法的思想建立一个有序线性表的时间复杂度为( )。 (满分:2.5)
A. O(n)
B. O(nlog2n)
C. O(n2 )
D. O(1og2n)
3.设顺序线性表的长度为30，分成5块，每块6个元素，如果采用分块查找，则其平均查找长度为( )。 (满分:2.5)
A. 6
B. 11
C. 5
D. 6.5
4.设顺序表的长度为n，则顺序查找的平均比较次数为( )。 (满分:2.5)
A. n
B. n/2
C.(n+1)/2
D.(n-1)/2
5.对于静态表的顺序查找法，若在表头设置岗哨，则正确的查找方式为( )。 (满分:2.5)
A. 从第0个元素往后查找该数据元素
B. 从第1个元素往后查找该数据元素
C. 从第n个元素往开始前查找该数据元素
D. 与查找顺序无关
6.在所有排序方法中，关键字比较的次数与记录的初始排列次序无关的是( )。 (满分:2.5)
A. 希尔排序
B. 起泡排序
C. 插入排序
D. 选择排序
7.有8个结点的无向连通图最少有( )条边。 (满分:2.5)
A. 5
B. 6
C. 7
D. 8
8.一组记录的排序码为（25，48，16，35，79，82，23，40，36，72），其中含有5个长度为2的有序表，按归并排序的方法对该序列进行一趟归并后的结果为( )。 (满分:2.5)
A. 16，25，35，48，23，40，79，82，36，72
B. 16，25，35，48，79，82，23，36，40，72
C. 16，25，48，35，79，82，23，36，40，72
D. 16，25，35，48，79，23，36，40，72，82
9.关键路径是事件结点网络中( )。 (满分:2.5)
A. 从源点到汇点的最长路径
B. 从源点到汇点的最短路径
C. 最长的回路
D. 最短的回路
10.在一个具有n个顶点的无向图中，要连通全部顶点至少需要( )条边。 (满分:2.5)
A. n
B. n+1
C. n-1
D. n/2
11.设带有头结点的单向循环链表的头指针变量为head，则其判空条件是( )。 (满分:2.5)
A. head==0
B. head->next==0
C. head->next==head
D. head!=0
12.排序方法中，从未排序序列中挑选元素，并将其依次放入已排序序列（初始时为空）的一端的方法，称为( )。 (满分:2.5)
A. 希尔排序
B. 归并排序
C. 插入排序
D. 选择排序
13.组成数据的基本单位是( )。 (满分:2.5)
A. 数据项
B. 数据类型
C. 数据元素
D. 数据变量
14.采用邻接表存储的图的宽度优先遍历算法类似于二叉树的( )。 (满分:2.5)
A. 先序遍历
B. 中序遍历
C. 后序遍历
D. 按层遍历
15.下述几种排序方法中，平均查找长度最小的是( )。 (满分:2.5)
A. 插入排序
B. 选择排序
C. 快速排序
D. 归并排序
16.设有一个10阶的下三角矩阵A（包括对角线），按照从上到下、从左到右的顺序存储到连续的55个存储单元中，每个数组元素占1个字节的存储空间，则A地址与A的地址之差为( )。 (满分:2.5)
A. 10
B. 19
C. 28
D. 55
17.有8个结点的无向图最多有( )条边。 (满分:2.5)
A. 14
B. 28
C. 56
D. 112
18.采用线性探测法解决冲突问题，所产生的一系列后继散列地址( )。 (满分:2.5)
A. 必须大于等于原散列地址
B. 必须小于等于原散列地址
C. 可以大于或小于但不能等于原散列地址
D. 地址大小没有具体限制
19.用某种排序方法对线性表（ 25，84，21，47，15，27，68，35，20）进行排序时，元素序列的变化情况如下：⑴ 25，84，21，47，15，27，68，35，20；⑵ 20，15，21，25，47，27，68，35，84；⑶ 15，20，21，25，35，27，47，68，84；⑷ 15，20，21，25，27，35，47，68，84。则所采用的排序方法是( )。 (满分:2.5)
A. 选择排序
B. 希尔排序
C. 归并排序
D. 快速排序
20.用DFS遍历一个无环有向图，并在DFS算法退栈返回时打印出相应的顶点，则输出的顶点序列是( )。 (满分:2.5)
A. 逆拓朴有序的
B. 拓朴有序的
C. 无序的
D. 不确定的
21.设一组初始记录关键字的长度为8，则最多经过( )趟插入排序可以得到有序序列。 (满分:2.5)
A. 6
B. 7
C. 8
D. 9
22.一组记录的排序码为（46，79，56，38，40，84），则利用堆排序的方法建立的初始堆为( )。 (满分:2.5)
A. 79，46，56，38，40，80
B. 38，46
56，79，40，84，
C. 84，79，56，46，40，38
D. 84，56，79，40，46，38
23.采用邻接表存储的图的深度优先遍历算法类似于二叉树的( )。 (满分:2.5)
A. 先序遍历
B. 中序遍历
C. 后序遍历
D. 按层遍历
24.设输入序列为1、2、3、4、5、6，则通过栈的作用后可以得到的输出序列为( )。 (满分:2.5)
A. 5，3，4，6，1，2
B. 3，2，5，6，4，1
C. 3，1，2，5，4，6
D. 1，5，4，6，2，3
25.对于一个具有n个顶点的无向图，若采用邻接矩阵表示，则该矩阵的大小是( )。 (满分:2.5)
A. n
B.(n-1)的平方
C. n-1
D. n的平方
26.树的基本遍历策略可分为先根遍历和后根遍历；二叉树的基本遍历策略可分为先序遍历、中序遍历和后序遍历。这里，我们把由树转化得到的二叉树叫做这棵数对应的二叉树。结论( )是正确的。 (满分:2.5)
A. 树的先根遍历序列与其对应的二叉树的先序遍历序列相同
B. 树的后根遍历序列与其对应的二叉树的后序遍历序列相同
C. 树的先根遍历序列与其对应的二叉树的中序遍历序列相同
D. 以上都不对
27.在待排序的元素序列基本有序的前提下，效率最高的排序方法是( )。 (满分:2.5)
A. 插入排序
B. 选择排序
C. 快速排序
D. 归并排序
28.设一棵完全二叉树中有65个结点，则该完全二叉树的深度为( )。 (满分:2.5)
A. 8
B. 7
C. 6
D. 5
29.( )二叉排序树可以得到一个从小到大的有序序列。 (满分:2.5)
A. 先序遍历
B. 中序遍历
C. 后序遍历
D. 层次遍历
30.在一个图中，所有顶点的度数之和等于所有边数的( )倍。 (满分:2.5)
A. 1/2
B. 1
C. 2
D. 4
31.建立一个长度为n的有序单链表的时间复杂度为( ) (满分:2.5)
A. O(n)
B. O(1)
C. O(n2 )
D. O(log2n)
32.对于一个具有n个顶点和e条边的无向图，若采用邻接表表示，则所有邻接表中的接点总数是( )。 (满分:2.5)
A. e/2
B. e
C. 2e
D. n+e
33.解决散列法中出现的冲突问题常采用的方法是( )。 (满分:2.5)
A. 数字分析法、除余法、平方取中法
B. 数字分析法、除余法、线性探测法
C. 数字分析法、线性探测法、多重散列法
D. 线性探测法、多重散列法、链地址法
34.堆的形状是一棵( )。 (满分:2.5)
A. 二叉排序树
B. 满二叉树
C. 完全二叉树
D. 平衡二叉树
35.设有n个关键字具有相同的Hash函数值，则用线性探测法把这n个关键字映射到HASH表中需要做( )次线性探测。 (满分:2.5)
A. n2
B. n(n+1)
C. n(n+1)/2
D. n(n-1)/2
36.设一组初始记录关键字序列为(60，80，55，40，42，85)，则以第一个关键字45为基准而得到的一趟快速排序结果是( )。 (满分:2.5)
A. 40，42，60，55，80，85
B. 42，45，55，60，85，80
C. 42，40，55，60，80，85
D. 42，40，60，85，55，80
37.设顺序线性表中有n个数据元素，则删除表中第i个元素需要移动( )个元素。 (满分:2.5)
A. n-i
B. n+l -i
C. n-1-i
D. i
38.把一棵树转换为二叉树后，这棵二叉树的形态是( )。 (满分:2.5)
A. 唯一的
B. 有多种
C. 有多种，但根结点都没有左孩子
D. 有多种，但根结点都没有右孩子
39.队列是一种( )的线性表。 (满分:2.5)
A. 先进先出
B. 先进后出
C. 只能插入
D. 只能删除
40.采用顺序查找方法查找长度为n的线性表时，每个元素的平均查找长度为( ). (满分:2.5)
A. n
B. n/2
C.(n+1)/2
D.(n-1)/2
页:
[1]