天津大学18春《数据结构》在线作业12资料
《数据结构》在线作业一一、单选题：
1.（单选题）用链接方式存储的队列，在进行插入运算时(). (满分:)
A仅修改头指针
B头、尾指针都要修改
C仅修改尾指针
D头、尾指针可能都要修改
正确答案:——D——
2.（单选题）设一维数组中有n个数组元素，则读取第i个数组元素的平均时间复杂度为（）。 (满分:)
AO(n)
BO(nlog2n)
CO(1)
DO(n2)
正确答案:——C——
3.（单选题）设指针变量p指向单链表中结点A，若删除单链表中结点A，则需要修改指针的操作序列为（）。 (满分:)
Aq=p->next；p->data=q->data；p->next=q->next；free(q)；
Bq=p->next；q->data=p->data；p->next=q->next；free(q)；
Cq=p->next；p->next=q->next；free(q)；
Dq=p->next；p->data=q->data；free(q)
正确答案:——A——
4.（单选题）设二叉排序树中有n个结点，则在二叉排序树的平均平均查找长度为（）。 (满分:)
AO(1)
BO(log2n)
CO(n4)
DO(n2)
正确答案:————
5.（单选题）非空的循环单链表head的尾结点（由p所指向）满足（）。 (满分:)
Ap->next==NULL
Bp==NULL
Cp->next==head
Dp==head
正确答案:————
6.（单选题）若有18个元素的有序表存放在一维数组A中，第一个元素放A中，现进行二分查找，则查找A［3］的比较序列的下标依次为(cd) (满分:)
A1，2，3
B9，5，2，3
C9，5，3
D9，4，2，3
正确答案:————
7.（单选题）设某棵二叉树的中序遍历序列为ABCD，前序遍历序列为CABD，则后序遍历该二叉树得到序列为（）。 (满分:)
ABADC
BBCDA
CCDAB
DCBDA
正确答案:————
8.（单选题）在一非空二叉树的中序遍历序列中，根结点的右边（）。 (满分:)
A只有右子树上的所有结点
B只有右子树上的部分结点
C只有左子树上的部分结点
D只有左子树上的所有结点
正确答案:————
9.（单选题）下面程序的时间复杂为（）for（i=1，s=0；i<=n；i++）{t=1；for(j=1；j<=i；j++)t=t*j；s=s+t；} (满分:)
AO(n)
BO(n2)
CO(n3)
DO(n4)
正确答案:————
10.（单选题）一个向量（即一批地址连续的存储单元）第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是（）。 (满分:)
A110
B108
C100
D120
正确答案:————
11.（单选题）设高度为h的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的结点数至少为（）。 (满分:)
A2h
B2h-1
C2h+1
Dh+1
正确答案:————
12.（单选题）线性表是一个具有n个（）的有限序列 (满分:)
A表元素
B字符
C数据元素
D数据项
正确答案:————
13.（单选题）设某无向图有n个顶点，则该无向图的邻接表中有（）个表头结点。 (满分:)
A2n
Bn
Cn/2
Dn(n-1)
正确答案:————
14.（单选题）判定一个循环队列QU（最多元素为m0,m0==Maxsize-1）为满队列的条件是（）。 (满分:)
A((rear-front)+Maxsize)%Maxsize==m0
Brear-front-1==m0
Cfront==rear
Dfront==rear+1
正确答案:————
15.（单选题）判定一个循环队列QU（最多元素为m0）为空的条件是（）。 (满分:)
Arear-front==m0
Brear-front-1==m0
Cfront==rear
Dfront==rear+1
正确答案:————
16.（单选题）数据结构DS(DataStruct)可以被形式地定义为DS=（D，R），其中D是（）有限集合，R是D上的关系有限集合。 (满分:)
A算法
B数据元素
C数据操作
D数据对象
正确答案:————
17.（单选题）设a,b为一棵二叉树上的两个结点，在中序遍历时，a在b前的条件是（）。 (满分:)
Aa在b的右方
Ba在b的左方
Ca是b的祖先
Da是b的子孙
正确答案:————
18.（单选题）设某二叉树中度数为0的结点数为N0，度数为1的结点数为Nl，度数为2的结点数为N2，则下列等式成立的是（）。 (满分:)
AN0=N1+1
BN0=Nl+N2
CN0=N2+1
DN0=2N1+l
正确答案:————
19.（单选题）设无向图的顶点个数为n，则该图最多有（）条边。 (满分:)
An-1
Bn(n-1)/2
Cn(n+1)/2
D0
正确答案:————
20.（单选题）一个栈的入栈序列a，b，c，d，e，则栈的不可能的输出序列是（）。 (满分:)
Aedcba
Bdecba
Cdceab
Dabcde
正确答案:————
21.（单选题）设串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))的结果串是（）。 (满分:)
ABCDEF
BBCDEFG
CBCPQRST
DBCDEFEF
正确答案:————
22.（单选题）设有一个二维数组A，假设A存放位置在644(10)，A存放位置在676(10)，每个元素占一个空间，问A(10)存放在()位置.脚注(10)表示用10进制表示。 (满分:)
A688
B678
C692
D696
正确答案:————
23.（单选题）向一个栈顶指针为HS的链栈中插入一个s所指结点时，则执行（）。(不带空的头结点) (满分:)
AHS—＞next=s;
Bs—＞next=HS—＞next;HS—＞next=s;
Cs—＞next=HS;HS=s;
Ds—＞next=HS;HS=HS—＞next;
正确答案:————
24.（单选题）线性表的顺序存储结构是一种（）的存储结构。 (满分:)
A随机存取
B索引存取
C顺序存取
D散列存取
正确答案:————
25.（单选题）二维数组A中，每个元素A的长度为3个字节，行下标i从0到7，列下标j从0到9，从首地址SA开始连续存放在存储器内，该数组按行存放时，数组元素A的起始地址为（）。 (满分:)
ASA+141
BSA+144
CSA+222
DSA+225
正确答案:————
26.（单选题）若已知一个栈的入栈序列是1，2，3，…，n，其输出序列为p1，p2，p3，…，pn，若p1=n，则pi为（）。 (满分:)
Ai
Bn=i
Cn-i+1
D不确定
正确答案:————
27.（单选题）在一个单链表中，已知q所指结点是p所指结点的前驱结点，若在q和p之间插入s结点，则执行（）。 (满分:)
As->next=p->next;p->next=s;
Bp->next=s->next;s->next=p;
Cq->next=s;s->next=p;
Dp->next=s;s->next=q;
正确答案:————
28.（单选题）设一组初始记录关键字序列为(345，253，674，924，627)，则用基数排序需要进行（）趟的分配和回收才能使得初始关键字序列变成有序序列。 (满分:)
A3
B4
C5
D8
正确答案:————
29.（单选题）设一组初始关键字记录关键字为(20，15，14，18，21，36，40，10)，则以20为基准记录的一趟快速排序结束后的结果为()。 (满分:)
A10，15，14，18，20，36，40，21
B10，15，14，18，20，40，36，21
C10，15，14，20，18，40，36，2l
D15，10，14，18，20，36，40，21
正确答案:————
30.（单选题）判定一个顺序栈ST（最多元素为m0）为栈满的条件是（）。 (满分:)
Atop！=0
Btop==0
Ctop！=m0
Dtop==m0-1
正确答案:————
31.（单选题）栈和队列的共同特点是()。 (满分:)
A只允许在端点处插入和删除元素
B都是先进后出
C都是先进先出
D没有共同点
正确答案:————
32.（单选题）按照二叉树的定义，具有3个不同数据结点的不同的二叉树有（）种。 (满分:)
A5
B6
C30
D32
正确答案:————
33.（单选题）在一个单链表中，若删除p所指结点的后续结点，则执行（）。 (满分:)
Ap->next=p->next->next;
Bp=p->next;p->next=p->next->next;
Cp->next=p->next;
Dp=p->next->next；
正确答案:————
34.（单选题）深度为5的二叉树至多有（）个结点。 (满分:)
A16
B32
C31
D10
正确答案:————
35.（单选题）二维数组A中，每个元素的长度为3个字节，行下标i从0到7，列下标j从0到9，从首地址SA开始连续存放在存储器内，存放该数组至少需要的字节数是（）。 (满分:)
A80
B100
C240
D270
正确答案:————
36.（单选题）在数据结构中，从逻辑上可以把数据结构分成（）。 (满分:)
A动态结构和静态结构
B紧凑结构和非紧凑结构
C线性结构和非线性结构
D内部结构和外部结构
正确答案:————
37.（单选题）串是一中特殊的线性表，其特殊性体现在（）。 (满分:)
A可以顺序存储
B数据元素是一个字符
C可以链接存储
D数据元素可以是多个字符
正确答案:————
38.（单选题）设某有向图中有n个顶点，则该有向图对应的邻接表中有（）个表头结点。 (满分:)
An-1
Bn
Cn+1
D2n-1
正确答案:————
39.（单选题）已知某二叉树的后序遍历序列是dabec，中序遍历序列是debac，它的前序遍历序列是（）。 (满分:)
Aacbed
Bdecab
Cdeabc
Dcedba
正确答案:————
40.（单选题）进行折半搜索的表必须是顺序存储的有序表。 (满分:)
A正确
B错误
正确答案:————
《数据结构》在线作业二
一、单选题：
1.（单选题）设哈希表长m=14，哈希函数H(key)=key%11。表中已有4个结点：addr(15)=4;addr(38)=5;addr(61)=6;addr(84)=7，如用二次探测再散列处理冲突，关键字为49的结点的地址是（）。 (满分:)
A8
B3
C5
D9
正确答案:——D——
2.（单选题）设有一组初始记录关键字序列为(34，76，45，18，26，54，92)，则由这组记录关键字生成的二叉排序树的深度为（）。 (满分:)
A4
B5
C6
D7
正确答案:——A——
3.（单选题）对线性表进行二分查找时，要求线性表必须（）。 (满分:)
A以顺序方式存储
B以链接方式存储
C以顺序方式存储，且结点按关键字有序排序
D以链接方式存储，且结点按关键字有序排序
正确答案:——C——
4.（单选题）设一组初始记录关键字的长度为8，则最多经过（）趟插入排序可以得到有序序列。 (满分:)
A6
B7
C8
D9
正确答案:————
5.（单选题）快速排序方法在（）情况下最不利于发挥其长处。 (满分:)
A要排序的数据量太大
B要排序的数据中含有多个相同值
C要排序的数据已基本有序
D要排序的数据个数为奇数
正确答案:————
6.（单选题）设有向无环图G中的有向边集合E={<1，2>，<2，3>，<3，4>，<1，4>}，则下列属于该有向图G的一种拓扑排序序列的是（）。 (满分:)
A1，2，3，4
B2，3，4，1
C1，4，2，3
D1，2，4，3
正确答案:————
7.（单选题）任何一个无向连通图的最小生成树（）。 (满分:)
A只有一棵
B有一棵或多棵
C一定有多棵
D可能不存在
正确答案:————
8.（单选题）程序段s=i=0；do{i=i+1；s=s+i；}while(i<=n)；的时间复杂度为（）。 (满分:)
AO(n)
BO(nlog2n)
CO(n2)
DO(n3/2)
正确答案:————
9.（单选题）设在一棵度数为3的树中，度数为3的结点数有2个，度数为2的结点数有1个，度数为1的结点数有2个，那么度数为0的结点数有（）个。 (满分:)
A4
B5
C6
D7
正确答案:————
10.（单选题）设一组初始记录关键字序列为(13，18，24，35，47，50，62，83，90，115，134),则利用二分法查找关键字90需要比较的关键字个数为（）。 (满分:)
A1
B2
C3
D4
正确答案:————
11.（单选题）有一个长度为12的有序表，按二分查找法对该表进行查找，在表内各元素等概率情况下查找成功所需的平均比较次数为（）。 (满分:)
A35/12
B37/12
C39/12
D43/12
正确答案:————
12.（单选题）二叉树是非线性数据结构，所以（）。 (满分:)
A它不能用顺序存储结构存储
B它不能用链式存储结构存储
C顺序存储结构和链式存储结构都能存储
D顺序存储结构和链式存储结构都不能使用
正确答案:————
13.（单选题）下列程序段的时间复杂度为（）。for(i=0；i<m；i++)for(j=0；j<t；j++)c=0；for(i=0；i<m；i++)for(j=0；j<t；j++)for(k=0；k<n；k++)c=c+a*b； (满分:)
AO(m*n*t)
BO(m+n+t)
CO(m+n*t)
DO(m*t+n)
正确答案:————
14.（单选题）设指针q指向单链表中结点A，指针p指向单链表中结点A的后继结点B，指针s指向被插入的结点X，则在结点A和结点B插入结点X的操作序列为（）。 (满分:)
As->next=p->next；p->next=-s；
Bq->next=s；s->next=p；
Cp->next=s->next；s->next=p；
Dp->next=s；s->next=q；
正确答案:————
15.（单选题）有一个有序表为{1，3，9，12，32，41，45，62，75，77，82，95，100}，当二分查找值82为的结点时，（）次比较后查找成功。 (满分:)
A1
B2
C4
D8
正确答案:————
16.（单选题）对于一个有向图，若一个顶点的入度为k1,、出度为k2，则对应逆邻接表中该顶点单链表中的结点数为（）。 (满分:)
Ak1
Bk2
Ck1-k2
Dk1+k2
正确答案:————
17.（单选题）有8个结点的无向连通图最少有（）条边。 (满分:)
A5
B6
C7
D8
正确答案:————
18.（单选题）具有4个顶点的无向完全图有（）条边。 (满分:)
A6
B12
C16
D20
正确答案:————
19.（单选题）字符串的长度是指（）。 (满分:)
A串中不同字符的个数
B串中不同字母的个数
C串中所含字符的个数
D串中不同数字的个数
正确答案:————
20.（单选题）判定一个有向图是否存在回路除了可以利用拓扑排序方法外，还可以利用（）。 (满分:)
A求关键路径的方法
B求最短路径的Dijkstra方法
C宽度优先遍历算法
D深度优先遍历算法
正确答案:————
21.（单选题）在所有排序方法中，关键字比较的次数与记录的初始排列次序无关的是（）。 (满分:)
A希尔排序
B起泡排序
C插入排序
D选择排序
正确答案:————
22.（单选题）在一个具有n个顶点的无向图中，要连通全部顶点至少需要（）条边。 (满分:)
An
Bn+1
Cn-1
Dn/2
正确答案:————
23.（单选题）对于一个具有n个顶点的无向图，若采用邻接矩阵表示，则该矩阵的大小是（）。 (满分:)
An
B(n-1)的平方
Cn-1
Dn的平方
正确答案:————
24.（单选题）一个有n个顶点的无向图最多有（）条边。 (满分:)
An
Bn(n-1)
Cn(n-1)/2
D2n
正确答案:————
25.（单选题）设散列表中有m个存储单元，散列函数H(key)=key%p，则p最好选择（）。 (满分:)
A小于等于m的最大奇数
B小于等于m的最大素数
C小于等于m的最大偶数
D小于等于m的最大合数
正确答案:————
26.（单选题）用DFS遍历一个无环有向图，并在DFS算法退栈返回时打印出相应的顶点，则输出的顶点序列是（）。 (满分:)
A逆拓朴有序的
B拓朴有序的
C无序的
D不确定的
正确答案:————
27.（单选题）设顺序表的长度为n，则顺序查找的平均比较次数为（）。 (满分:)
An
Bn/2
C(n+1)/2
D(n-1)/2
正确答案:————
28.（单选题）不含任何结点的空树（）。 (满分:)
A是一棵树
B是一棵二叉树
C是一棵树也是一棵二叉树
D既不是树也不是二叉树
正确答案:————
29.（单选题）采用二分查找方法查找长度为n的线性表时，每个元素的平均查找长度为（）。 (满分:)
AO（n2）
BO(nlog2n)
CO(n)
DO(log2n)
正确答案:————
30.（单选题）设某链表中最常用的操作是在链表的尾部插入或删除元素，则选用下列（）存储方式最节省运算时间。 (满分:)
A单向链表
B单向循环链表
C双向链表
D双向循环链表
正确答案:————
31.（单选题）设指针变量p指向双向链表中结点A，指针变量s指向被插入的结点X，则在结点A的后面插入结点X的操作序列为（）。 (满分:)
Ap->right=s；s->left=p；p->right->left=s；s->right=p->right；
Bs->left=p；s->right=p->right；p->right=s；p->right->left=s；
Cp->right=s；p->right->left=s；s->left=p；s->right=p->right；
Ds->left=p；s->right=p->right；p->right->left=s；p->right=s；
正确答案:————
32.（单选题）树的基本遍历策略可分为先根遍历和后根遍历；二叉树的基本遍历策略可分为先序遍历、中序遍历和后序遍历。这里，我们把由树转化得到的二叉树叫做这棵数对应的二叉树。结论（）是正确的。 (满分:)
A树的先根遍历序列与其对应的二叉树的先序遍历序列相同
B树的后根遍历序列与其对应的二叉树的后序遍历序列相同
C树的先根遍历序列与其对应的二叉树的中序遍历序列相同
D以上都不对
正确答案:————
33.（单选题）对于查找表的查找过程中，若被查找的数据元素不存在，则把该数据元素插入到集合中。这种方式主要适合于（）。 (满分:)
A静态查找表
B动态查找表
C静态查找表与动态查找表
D两种表都不适合
正确答案:————
34.（单选题）设顺序线性表中有n个数据元素，则删除表中第i个元素需要移动（）个元素。 (满分:)
An-i
Bn+l-i
Cn-1-i
Di
正确答案:————
35.（单选题）排序方法中，从未排序序列中依次取出元素与已排序序列（初始时为空）中的元素进行比较，将其放入已排序序列的正确位置上的方法，称为（）。 (满分:)
A希尔排序
B起泡排序
C插入排序
D选择排序
正确答案:————
36.（单选题）一组记录的关键码为（46，79，56，38，40，84），则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为（）。 (满分:)
A38，40，46，56，79，84
B40，38，46，79，56，84
C40，38，46，56，79，84
D40，38，46，84，56，79
正确答案:————
37.（单选题）有8个结点的无向图最多有（）条边。 (满分:)
A14
B28
C56
D112
正确答案:————
38.（单选题）设一组初始记录关键字序列为(Q，H，C，Y，P，A，M，S，R，D，F，X)，则按字母升序的第一趟冒泡排序结束后的结果是（）。 (满分:)
AF，H，C，D，P，A，M，Q，R，S，Y，X
BP，A，C，S，Q，D，F，X，R，H，M，Y
CA，D，C，R，F，Q，M，S，Y，P，H，X
DH，C，Q，P，A，M，S，R，D，F，X，Y
正确答案:————
39.（单选题）采用邻接表存储的图的深度优先遍历算法类似于二叉树的（）。 (满分:)
A先序遍历
B中序遍历
C后序遍历
D按层遍历
正确答案:————
40.（单选题）下述几种排序方法中，要求内存量最大的是（）。 (满分:)
A插入排序
B选择排序
C快速排序
D归并排序
正确答案:————
转载请注明：www.ap5u.com
页:
[1]