《天大18秋《数据结构》在线作业一标准答案》由会员分享，可在线阅读，更多相关《天大18秋《数据结构》在线作业一标准答案（18页珍藏版）》请在金锄头文库上搜索。
1、数据结构在线作业一-0002 试卷总分:100 得分:100 一、 单选题 (共 40 道试题,共 100 分)1.数据结构是一门研究非数值计算的程序设计问题中,数据元素的（） 、数据信息在计算机中 的存储结构以及一组相关的运算等的课程。A.操作对象B.计算方法C.逻辑结构D.数据映象正确答案:C2.设一维数组中有 n 个数组元素，则读取第 i 个数组元素的平均时间复杂度为（ ） 。A.O(n)B.O(nlog2n)C.O(1)D.O(n2 )正确答案:C3.设一组初始记录关键字序列为(345，253，674，924，627)，则用基数排序需要进行（ ） 趟的分配和回收才能使得初始关键字序列变
2、成有序序列。A.3B.4C.5D.8正确答案:A4.如果只想得到 1024 个元素组成的序列中第 5 个最小元素之前的部分排序的序列，用（ ） 方法最快。A.起泡排序B.快速排序C.简单选择排序D.堆排序正确答案:D5.下面程序的时间复杂为（ ） for（i=1，s=0； inext=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;正确答案:B7.已知某二叉树的后序遍历序列是 dabec，中序遍历序列是 debac，它的前序遍历序列是（） 。A.acbedB.decabC.deabcD.ce
3、dba正确答案:D8.二维数组 A 中，每个元素的长度为 3 个字节，行下标 i 从 0 到 7，列下标 j 从 0 到 9，从 首地址 SA 开始连续存放在存储器内，存放该数组至少需要的字节数是（） 。A.80B.100C.240D.270正确答案:C9.若已知一个栈的入栈序列是 1，2，3，n，其输出序列为 p1，p2，p3，pn，若 p1=n，则 pi 为（） 。A.iB.n=iC.n-i+1D.不确定正确答案:C10.判定一个顺序栈 ST（最多元素为 m0）为栈满的条件是（） 。A.top！=0B.top= =0C.top！=m0D.top= =m0-1正确答案:D11.在二叉排序树中
4、插入一个结点的时间复杂度为（ ） 。A.O(1)B.O(n)C.O(log2n)D.O(n2 )正确答案:B12.设串 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.BCDEFB.BCDEFGC.BCPQRSTD.BCDEFEF正确答案:D13.在用循环单链表表示的链式队列中，可以不设队头指针，仅在链尾设置队尾指针。A.正确B.
5、错误正确答案:A14.非空的循环单链表 head 的尾结点（由 p 所指向）满足（） 。A.p-next= =NULLB.p= =NULLC.p-next= =headD.p= =head正确答案:C15.某二叉树的前序遍历结点访问顺序是 abdgcefh，中序遍历的结点访问顺序是 dgbaechf， 则其后序遍历的结点访问顺序是（） 。A.bdgcefhaB.gdbecfhaC.bdgaechfD.gdbehfca正确答案:D16.带头结点的单链表 head 为空的判定条件是（） 。A.head= =NULLB.head-next= =NULLC.head-next= =headD.head
6、!=NULL正确答案:B17.进行折半搜索的表必须是顺序存储的有序表。A.正确B.错误正确答案:A18.设串的长度为 n，则它的子串个数为（） 。A.nB.n(n+1)C.n(n+1)/2D.n(n+1)/2+1正确答案:C19.常对数组进行的两种基本操作是（） 。A.建立与删除B.索引和修改C.对数据元素的存取和修改D.查找与索引正确答案:C20.设某无向图中有 n 个顶点 e 条边，则该无向图中所有顶点的入度之和为（ ） 。A.nB.eC.2nD.2e正确答案:D21.向一个栈顶指针为 HS 的链栈中插入一个 s 所指结点时，则执行（） 。(不带空的头结点)A.HSnext=s;B.sne
7、xt= HSnext;HSnext=s;C.snext= HS;HS=s;D.snext= HS;HS= HSnext;正确答案:C22.深度为 5 的二叉树至多有（）个结点。A.16B.32C.31D.10正确答案:C23.设有 6 个结点的无向图，该图至少应有( )条边才能确保是一个连通图。A.5B.6C.7D.8正确答案:A24.设顺序循环队列 Q0：M-1的头指针和尾指针分别为 F 和 R，头指针 F 总是指向队头元素 的前一位置，尾指针 R 总是指向队尾元素的当前位置，则该循环队列中的元素个数为（ ） 。A.R-FB.F-RC.(R-F+M)MD.(F-R+M)M正确答案:C25.在
8、一个单链表中，已知 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;正确答案:B26.设无向图 G 中有 n 个顶点，则该无向图的最小生成树上有（ ）条边。A.nB.n-1C.2nD.2n-1正确答案:B27.链式存储在插入和删除时需要保持物理存储空间的顺序分配，不需要保持数据元素之间 的逻辑顺序。A.正确B.错误正确答案:B28.对于线性表（7，34，55，25，64，
9、46，20，10）进行散列存储时，若选用 H（K）=K %9 作为散列函数，则散列地址为 1 的元素有（ ）个.A.1B.2C.3D.4正确答案:D29.设某棵二叉树中有 2000 个结点，则该二叉树的最小高度为（ ） 。A.9B.10C.11D.12正确答案:C30.设某完全无向图中有 n 个顶点，则该完全无向图中有（ ）条边。A.n(n-1)/2B.n(n-1)C.n2D.n2 -1正确答案:A31.在以下的叙述中，正确的是（） 。A.线性表的顺序存储结构优于链表存储结构B.线性表的顺序存储结构适用于频繁插入/删除数据元素的情况C.线性表的链表存储结构适用于频繁插入/删除数据元素的情况D.
10、线性表的链表存储结构优于顺序存储结构正确答案:C32.在线索化二叉树中，t 所指结点没有左子树的充要条件是（） 。A.tleft=NULLB.tltag=1C.tltag=1 且 tleft=NULLD.以上都不对正确答案:B33.二维数组 A 中，每个元素 A 的长度为 3 个字节，行下标 i 从 0 到 7，列下标 j 从 0 到 9， 从首地址 SA 开始连续存放在存储器内，该数组按行存放时，数组元素 A74的起始地址 为（） 。A.SA+141B.SA+144C.SA+222D.SA+225正确答案:C34.从一个栈顶指针为 HS 的链栈中删除一个结点时，用 x 保存被删结点的值，则执
11、行（） 。 (不带空的头结点)A.x=HS;HS= HSnext;B.x=HSdata;C.HS=HSnext;x=HSdata;D.x=HSdata;HS= HSnext;正确答案:D35.设二叉排序树中有 n 个结点，则在二叉排序树的平均平均查找长度为（ ） 。A.O(1)B.O(log2n)C.O(n4)D.O(n2 )正确答案:B36.按照二叉树的定义，具有 3 个结点的不同形状的二叉树有（）种。A.3B.4C.5D.6正确答案:C37.具有五层结点的二叉平衡树至少有（）个结点。A.10B.12C.15D.17正确答案:B38.串是一中特殊的线性表，其特殊性体现在（） 。A.可以顺序存储B.数据元素是一个字符C.可以链接存储D.数据元素可以是多个字符正确答案:B39.下面关于线性表的叙述错误的是（ ） 。A.线性表采用顺序存储必须占用一片连续的存储空间B.线性表采用链式存储不必占用一片连续的存储空间C.线性表采用链式存储便于插入和删除操作的实现D.线性表采用顺序存储便于插入和删除操作的实现正确答案:D40.数据结构 DS(Data Struct)可以被形式地定义为 DS=（D，R） ，其中 D 是（）有限集合， R 是 D 上的关系有限集合。A.算法B.数据元素C.数据操作D.数据对象正确答案:B
