18秋[天津大学]《数据结构》在线作业一（100分）

admin

【奥鹏】[天津大学]《数据结构》在线作业一
试卷总分:100    得分:100
第1题,数据结构是一门研究非数值计算的程序设计问题中,数据元素的（）、数据信息在计算机中的存储结构以及一组相关的运算等的课程。
A、操作对象
B、计算方法
C、逻辑结构
D、数据映象
正确资料:


第2题,设一维数组中有n个数组元素，则读取第i个数组元素的平均时间复杂度为（  ）。
A、O(n)
B、O(nlog2n)
C、O(1)
D、O(n2 )
正确资料:


第3题,设一组初始记录关键字序列为(345，253，674，924，627)，则用基数排序需要进行（  ）趟的分配和回收才能使得初始关键字序列变成有序序列。
A、3
B、4
C、5
D、8
正确资料:


第4题,如果只想得到1024个元素组成的序列中第5个最小元素之前的部分排序的序列，用（   ）方法最快。
A、起泡排序
B、快速排序
C、简单选择排序
D、堆排序
正确资料:


第5题,下面程序的时间复杂为（  ）  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 )
正确资料:


第6题,在一个单链表中，若p所指结点不是最后结点，在p之后插入s所指结点，则执行（）。
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;
正确资料:


第7题,已知某二叉树的后序遍历序列是dabec，中序遍历序列是debac，它的前序遍历序列是（）。
A、acbed
B、decab
C、deabc
D、cedba
正确资料:


第8题,二维数组A中，每个元素的长度为3个字节，行下标i从0到7，列下标j从0到9，从首地址SA开始连续存放在存储器内，存放该数组至少需要的字节数是（）。
A、80
B、100
C、240
D、270
正确资料:


第9题,若已知一个栈的入栈序列是1，2，3，...，n，其输出序列为p1，p2，p3，...，pn，若p1=n，则pi为（）。
A、i
B、n=i
C、n-i+1
D、不确定
正确资料:


第10题,判定一个顺序栈ST（最多元素为m0）为栈满的条件是（）。
A、top！=0
B、top= =0
C、top！=m0
D、top= =m0-1
正确资料:


第11题,在二叉排序树中插入一个结点的时间复杂度为（  ）。
A、O(1)
B、O(n)
C、O(log2n)
D、O(n2 )
正确资料:


第12题,设串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))的结果串是（）。
A、BCDEF
B、BCDEFG
C、BCPQRST
D、BCDEFEF
正确资料:


第13题,在用循环单链表表示的链式队列中，可以不设队头指针，仅在链尾设置队尾指针。
A、正确
B、错误
正确资料:


第14题,非空的循环单链表head的尾结点（由p所指向）满足（）。
A、p-next= =NULL
B、p= =NULL
C、p-next= =head
D、p= =head
正确资料:


第15题,某二叉树的前序遍历结点访问顺序是abdgcefh，中序遍历的结点访问顺序是dgbaechf，则其后序遍历的结点访问顺序是（）。
A、bdgcefha
B、gdbecfha
C、bdgaechf
D、gdbehfca
正确资料:


第16题,带头结点的单链表head为空的判定条件是（）。
A、head= =NULL
B、head-next= =NULL
C、head-next= =head
D、head!=NULL
正确资料:


第17题,进行折半搜索的表必须是顺序存储的有序表。
A、正确
B、错误
正确资料:


第18题,设串的长度为n，则它的子串个数为（）。
A、n
B、n(n+1)
C、n(n+1)/2
D、n(n+1)/2+1
正确资料:


第19题,常对数组进行的两种基本操作是（）。
A、建立与删除
B、索引和修改
C、对数据元素的存取和修改
D、查找与索引
正确资料:


第20题,设某无向图中有n个顶点e条边，则该无向图中所有顶点的入度之和为（  ）。
A、n
B、e
C、2n
D、2e
正确资料:


第21题,向一个栈顶指针为HS的链栈中插入一个s所指结点时，则执行（）。(不带空的头结点)
A、HS-＞next=s;
B、s-＞next= HS-＞next;HS-＞next=s;
C、s-＞next= HS;HS=s;
D、s-＞next= HS;HS= HS-＞next;
正确资料:


第22题,深度为5的二叉树至多有（）个结点。
A、16
B、32
C、31
D、10
正确资料:


第23题,设有6个结点的无向图，该图至少应有(   )条边才能确保是一个连通图。
A、5
B、6
C、7
D、8
正确资料:


第24题,设顺序循环队列Q[0：M-1]的头指针和尾指针分别为F和R，头指针F总是指向队头元素的前一位置，尾指针R总是指向队尾元素的当前位置，则该循环队列中的元素个数为（  ）。
A、R-F
B、F-R
C、(R-F+M)％M
D、(F-R+M)％M
正确资料:


第25题,在一个单链表中，已知q所指结点是p所指结点的前驱结点，若在q和p之间插入s结点，则执行（）。
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;
正确资料:


第26题,设无向图G中有n个顶点，则该无向图的最小生成树上有（  ）条边。
A、n
B、n-1
C、2n
D、2n-1
正确资料:


第27题,链式存储在插入和删除时需要保持物理存储空间的顺序分配，不需要保持数据元素之间的逻辑顺序。
A、正确
B、错误
正确资料:


第28题,对于线性表（7，34，55，25，64，46，20，10）进行散列存储时，若选用H（K）=K %9作为散列函数，则散列地址为1的元素有（  ）个.
A、1
B、2
C、3
D、4
正确资料:


第29题,设某棵二叉树中有2000个结点，则该二叉树的最小高度为（  ）。
A、9
B、10
C、11
D、12
正确资料:


第30题,设某完全无向图中有n个顶点，则该完全无向图中有（  ）条边。
A、n(n-1)/2
B、n(n-1)
C、n2
D、n2 -1
正确资料:


第31题,在以下的叙述中，正确的是（）。
A、线性表的顺序存储结构优于链表存储结构
B、线性表的顺序存储结构适用于频繁插入/删除数据元素的情况
C、线性表的链表存储结构适用于频繁插入/删除数据元素的情况
D、线性表的链表存储结构优于顺序存储结构
正确资料:


第32题,在线索化二叉树中，t所指结点没有左子树的充要条件是（）。
A、t-＞left=NULL
B、t-＞ltag=1
C、t-＞ltag=1且t-＞left=NULL
D、以上都不对
正确资料:


第33题,二维数组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
正确资料:


第34题,从一个栈顶指针为HS的链栈中删除一个结点时，用x保存被删结点的值，则执行（）。(不带空的头结点)
A、x=HS;HS= HS-＞next;
B、x=HS-＞data;
C、HS=HS-＞next;x=HS-＞data;
D、x=HS-＞data;HS= HS-＞next;
正确资料:


第35题,设二叉排序树中有n个结点，则在二叉排序树的平均平均查找长度为（  ）。
A、O(1)
B、O(log2n)
C、O(n4)
D、O(n2 )
正确资料:


第36题,按照二叉树的定义，具有3个结点的不同形状的二叉树有（）种。
A、3
B、4
C、5
D、6
正确资料:


第37题,具有五层结点的二叉平衡树至少有（）个结点。
A、10
B、12
C、15
D、17
正确资料:


第38题,串是一中特殊的线性表，其特殊性体现在（）。
A、可以顺序存储
B、数据元素是一个字符
C、可以链接存储
D、数据元素可以是多个字符
正确资料:


第39题,下面关于线性表的叙述错误的是（   ）。
A、线性表采用顺序存储必须占用一片连续的存储空间
B、线性表采用链式存储不必占用一片连续的存储空间
C、线性表采用链式存储便于插入和删除操作的实现
D、线性表采用顺序存储便于插入和删除操作的实现
正确资料:


第40题,数据结构DS(Data Struct)可以被形式地定义为DS=（D，R），其中D是（）有限集合，R是D上的关系有限集合。
A、算法
B、数据元素
C、数据操作
D、数据对象
正确资料: