数据结构概论1-3在线作业.doc

一、单选:1.数据结构通常是研究数据的( )及它们之间的相互关系.A.存储和逻辑结构B.存储和抽象C.理想与抽象D.理想与逻辑2.数据在计算机存储器内表示时,物理地址与逻辑地址相同并且是连续的,称为( )A.存储结构B.逻辑结构5C.顺序存储结构D.链式存储结构3.非线性结构是数据元素之间是存在的一种( )A.一对多关系B.多对多关系C.多对一关系D.一对一关系4.非线性结构中,每个结点( )A.无直接前趋.B.只有一个直接前驱和后继C.只有一个直接前驱和个数不受限制的直接后继D.有个数不受限制的直接前驱和后继.5.除了考虑存储数据结构本身所占用的空间外,实现算法所用辅助空间的多少称为算法的: A.时间效率B.空间效率C.硬件效率D.软件效率二、填空1、数据结构包括数据的_逻辑结构_,数据的_存储结构_,数据的_运算_,这三个方面的内容 .2、数据结构按逻辑结构可分为两大类,分别是_线性结构和非线性结构 _.3、数据的存储结构可用四种基本的存储方法表示,分别是_顺序、链式、索引、散列_.4、线性结构反映结点间的逻辑关系是_一对一关系_.非线性结构反映结点间的逻辑关系是多对多关系.5、一个算法的效率可分为时间效率和_空间效率_.三、简答：分别写出下列两个算法的时间复杂度.1、x=0;for(i=1;in;i+)for(j=i+1;j=n;j+)x+;答：2、x=0;for(i=1;in;i+)for(j=1;j=front时，队列长度为_rear-front_；当rearFRONT时，队列长度是_rear+m-front_。7、在队列中存取数据应遵从的原则是：_先进后出8、在队列结构中，允许插入的一端称为_队尾_，允许删除的一端称为：_队头_9、s1=abcd,s2=cd，则s2在s1中的位置是_310、_不含任何字符的串_称为空串，_仅含空格字符的串_称为空白串。二、简答：1、设长度为n的链队列用单循环链表表示，若只设头指针，则入队，出队操作的时间是什么？如果只设尾指针呢？2、设T0.n-1=abaabaabcaabaa P0.m-1=aab,当用模式串P匹配目标串T时，请给出所有的有效位移。朴素匹配返回的位移是哪 一个？3、如果目标串一共有10个字符，模式串共有2个字符，问，当匹配不成功的时候，最多比较了多少个字符？举例说明。4、如果目标串一共有10个字符，模式串共有2个字符，问，当匹配成功的时候，最多比较了多少个字符？举例说明。作业标题 练习二严晓明 2011-04-29 20:56:58.0 一、选择1、用单链表方式存储的线性表,存储每个结点需要两个域,一个是数据域,另一个是()A.当前结点所在地址域.B.指针域.C.空指针域.D.空闲域.2、在具有n个结点的单链表中,实现()的操作,其算法的时间复杂度是o(n).A.遍历链表和求链表的第i个结点.B.在地址为p的结点之后插入一个结点.C.删除开始结点D.删除地址为p的结点的后继结点.3、单链表的存储密度().A.大于1 B.等于1 C.小于1 D.不确定4、已知一个顺序存储的线性表,设每个结点需占m个存储单元,若第一个结点的地址为da1,则第i个结点的地址为()A.da1+(i-1)*m B.da1+i*mC.da1-i*mD.da1+(i+1)*m5、在n个结点的顺序表中,算法的时间复杂度是O(1)的操作是: ()A.访问第i个结点(1=i=n)和求第i个结点的直接前趋(2=i=n)B.在第i个结点后插入一个新的结点(1=i=n)C.删除第i个结点(1=i=2)叉树的K叉链表表示中，有多少个空指针。n个结点的K叉树共有n*k个指针域，已使用的指针域为n-1,所以空指针的个数为：n(k-1)+12、已知一棵二叉树的前序序列和中序序列分别为abdghcefi和gdhbaecif,给出这棵二叉树的后序遍历序列。一、选择1、在一个图中，所有顶点的度数之和等于图的边数的 ( )倍.A. 1/2 B.1 C.2 D.42、在一个有向图中,所有顶点的入度之和等于所有顶点的出度之和的( )倍.A. 1/2 B.1 C.2 D.43、有8个结点的无向图最多有( )条边.A.14 B.28 C.56 D.1124、有8个结点的无向连通图最少有( )条边.A.5 B.6 C.7 D.85、有8个结点的有向完全图有( )条边.A.14 B.28 C.56 D.1126、用邻接表表示图进行广度优先遍历时,通常采用( )来实现算法.A. 栈 B. 队列 C.树 D.图7、用邻接表表示图进行深度优先遍历时,通常采用( )来实现算法.A. 栈 B. 队列 C.树 D.图8、深度优先遍历类似于二叉树的( )A.先序遍历 B.中序遍历 C.后序遍历 D.层次遍历9、广度优先遍历类似于二叉树的( )A.先序遍历 B.中序遍历 C.后序遍历 D.层次遍历10、任何一个无向连通图的最小生成树( )A.只有一棵 B.一棵或多棵 C.一定有多棵 D.可能不存在二、简答无向图G有6个结点和9条边,并依次输入这9条边为(0,1),(0,2),(0,4),(0,5),(1,2),(2,3),(2,4),(3,4),(4,5),试从顶点0出发,分别写出按深度优先搜索法和广度优先搜索法进行遍历的结点序列.深度优先搜索法:0-2-3-4-5-1广度优先搜索法:0-1-2-4-5-3一、填空1、下列关键字序列中( )是堆A.16,72,31,23,94,53B.94,23,31,72,16,53C.16,53,23,94,31,72D.16,23,53,31,94,722、堆是一种( )排序A.插入 B.选择 C.交换 D.归并3、堆的形状是一棵( ).A.二叉排序树 B.满二叉树 C.完全二叉树 D.平衡二叉树4、若一组记录的排序码为(46,79,56,38,40,84),则利用堆的方法建立的初始堆为( )A. 79,46,56,38,60,86B.84,79,56,38,40,46C.84,79,56,46,40,38D.84,56,79,40,46,385、若一组记录的关键码为(46,79,56,38,40,84),则利用快速排序的方法,以第一个记录为基准得到的一次划分结果为( )A.38,40,46,56,79,84B.40,38,46,79,56,84C.40,38,46,56,79,84D.40,38,46,84,56,796、设有100个元素,用折半查找法进行查找的时候,最大比较的次数是( )A.15 B.50 C.10 D.77、对线性表进行二分查找的时候,要求线性表必须( )A.以顺序方式B.以链接方式存储C.以顺序方式存储,且结点按斗争字有序排列D.以链接方