数据结构概论13在线作业

1、一、单选:1.数据结构通常是研究数据的(  )及它们之间的相互关系.A.存储和逻辑结构B.存储和抽象C.理想与抽象D.理想与逻辑2.数据在计算机存储器内表示时,物理地址与逻辑地址相同并且是连续的,称为(  )A.存储结构B.逻辑结构5C.顺序存储结构D.链式存储结构3.非线性结构是数据元素之间是存在的一种( )A.一对多关系B.多对多关系C.多对一关系D.一对一关系4.非线性结构中,每个结点( )A.无直接前趋.B.只有一个直接前驱和后继C.只有一个直接前驱和个数不受限制的直接后继D.有个数不受限制的直接前驱和后继. 5.除了考虑存储数据结构本身所占用的空间外,实

2、现算法所用辅助空间的多少称为算法的: A.时间效率B.空间效率C.硬件效率D.软件效率二、填空 1、数据结构包括数据的_逻辑结构_,数据的_存储结构_,数据的_运算_,这三个方面的内容 .2、数据结构按逻辑结构可分为两大类,分别是_线性结构和非线性结构 _.3、数据的存储结构可用四种基本的存储方法表示,分别是_顺序、链式、索引、散列_.4、线性结构反映结点间的逻辑关系是_一对一关系_.非线性结构反映结点间的逻辑关系是多对多关系.5、一个算法的效率可分为时间效率和_空间效率_.三、简答：分别写出下列两个算法的时间复杂度.1、x=0;for(i=1;i<n;i+) for

3、(j=i+1;j<=n;j+) x+; 答：2、x=0;for(i=1;i<n;i+) for(j=1;j<=n-i;j+) x+; 答： 欧一、填空1、在栈中存取数据的原则是：_先进后出_2、在栈中，出栈操作的时间复杂度为：_ 0(1)3、栈与一般线性表的区别主要在于_栈只允许在表尾进行插入和删除操作_4、顺序栈是空栈的条件是：_ s.top=0_5、插入和删除只能在一端进行的线性表，称为：_受限线性表_6、设循环向量有m个元素，循环向量中有一个循环队列，在循环队列中设队头指针front指向队头元素，队尾无名指是针指向队尾元

4、素后的一个空闲元素。.在循环队列中，队空标志为_front=rear_队满标志为_front=(rear+1)%m_.当rear>=front时，队列长度为_rear-front_；当rear<FRONT时，队列长度是_rear+m-front_。7、在队列中存取数据应遵从的原则是：_先进后出8、在队列结构中，允许插入的一端称为_队尾_，允许删除的一端称为：_队头_9、s1="abcd",s2="cd"，则s2在s1中的位置是_310、_不含任何字符的串_称为空串，_仅含空格字符的串_称为空白串。二、简答：1、设长度为n的链队列用单循环链表表

5、示，若只设头指针，则入队，出队操作的时间是什么？如果只设尾指针呢？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、用

6、单链表方式存储的线性表,存储每个结点需要两个域,一个是数据域,另一个是()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.da

7、1+(i+1)*m5、在n个结点的顺序表中,算法的时间复杂度是O(1)的操作是: ()A.访问第i个结点(1<=i<=n)和求第i个结点的直接前趋(2<=i<=n)B.在第i个结点后插入一个新的结点(1<=i<=n)C.删除第i个结点(1<=i<=n)D.将n个结点从小到大排序.二、填空：1、按顺序存储方法存储的线性表称为_顺序表_,按链式存储方法存储的线性表称为 链表_.2、线性表中结点的结点是_有限的_,结点间的关系是_1对1的_.3、顺序表相对于链表的优点有_以进行随机存取_和_节省存储_4、链表相对于顺序表的优点有_不需要预分配存储空间_

8、和_插入、删除_操作方便5、在n个结点的顺序表中,删除一个结点需平均移动_（n1）/2_个结点,具体的移动次数取决于_表长n和删除位置I_6、在n个结点的顺序表中,插入一个结点需平均移动_ n/2_个结点,具体的移动次数取决于_表长n和插入位置i_.7、在顺序表中访问任意一个结点的时间复杂度均为_ O(1)_.因此,顺序表也称为_随机存取_的数据结构.8、在n个结点的单链表中要删除已知结点*p,需找到_前驱结点的地址_,其时间复杂度为_ O(n)_.9、在双链中要删除已知结点*p,其时间复杂度为_ O(1)10、在单链表中,要在已知结点*p之前插入一个新结点,仍需找到_节点p的前一个节点_,其

9、时间复杂度为_ O(n)_.而在双链表中,完成同样的操作,其时间复杂度为_ O(1)_11、在循环链表中,可根据在一结点的地址遍历整个链表,而单链表中需要知道_头指针_才能遍历整个链表.三、简答题：1,2,3,4四个数字按顺序进栈,问退栈的顺序有几种?答: 4,3,2,1即全部进栈，然后顺序出栈！3，4，2，1即1，2，3先进栈，然后3出栈，然后1，2按顺序出栈3，2，4，1即1，2，3先进栈，然后3出栈，然后2出栈，然后4进栈，最后4，1按顺序出栈依次类推，有2的4次方=16种一、填空：1、设二维数组A0.m-10.n-1按行优先顺序存储在内存中，每个元素aij占d个字节，则aij的地址为_

10、LOC(a00)+(i*n+j)*d _2、已知二维数组A8*10中，每个元素占两个字节，元素a12的地址为1000，则元素a00的地址为_976_3、若数组A定义为A2.m2.n，则元素aij的地址为：_LOC(a00)+j*m=i_4、对于任何一棵二叉树T，如果其终端结点数为n0，度为2的结点数为n2，则有什么样的关系式。n0=n2+15、设x是一棵树，x''''''''是对应于x的二叉树，则x的先根遍历和x''''''''的_先序_遍历相同。6、深度为

11、K的二叉树至多有_6.2k-1_个结点。7、对于二叉树来说，第i层上至多有_2(k-1)_个结点。8、某二叉树的前序遍历序列为ijklmno,中序遍历序列为jlkinmo,则后序遍历序列为：_lkjnomi_9._9、将一棵有100个结点的完全二叉树从上到下，从左到右依次对结点进行编号，根结点的编号为1，则编号为49的结点的孩子编号为：_10、某二叉树的前序和后序正好相反，则该二叉树一定是_高度等于其结点数_二叉树。11、设高度为h的二叉树上只有度为0和度为2的结点，则此二叉树中所包含的结点数至少为：_12、设森林T中有4棵树，第一，二，三，四棵树的结点个数分别是n1,n2,n3,n4，那么当

12、把森林T转换成一棵二叉树后，其根结点的右子树上有_ n2+ n3+ n3_个结点。13、树中结点的最大层次称为树的_深度或高度_14、由一棵二叉树的前序序列和_中序遍历、由中序和后序遍历序列_，能唯一确定这棵二叉树。15、高度为5的完全二叉树至少有_ 2(h-1) _个结点。16、将一棵树转换成一棵二叉树后，二叉树根结点没有_左_子树。17、森林的后根遍历序列正是相应二叉树_的遍历序列。森林的先根遍历正是相应二叉树的_遍历序列。18、哈夫曼树是带权路径长度_最小的二叉树。19、具有m个叶结点的哈夫曼树共有_2m-1_结点。20、前序为a,b,c且后序为c,b,a的二叉树共_4_棵。21、已知二

13、叉树有50个叶子结点，且仅有一个孩子的结点数为30，则总结点数为_129_。二、简答：1、在具有n个结点的K（k>=2)叉树的K叉链表表示中，有多少个空指针。n个结点的K叉树共有n*k个指针域，已使用的指针域为n-1,所以空指针的个数为：n(k-1)+12、已知一棵二叉树的前序序列和中序序列分别为abdghcefi和gdhbaecif,给出这棵二叉树的后序遍历序列。 一、选择1、在一个图中，所有顶点的度数之和等于图的边数的 (  )倍.A. 1/2  B.1  C.2  D.42、在一个有向图中,所有顶点的入度之和等于所有顶点的出度之和的

14、(   )倍.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.8 5、有8个结点的有向完全图有(  )条边.A.14    B.28   C.56  D.1126、用邻接表表示图进

15、行广度优先遍历时,通常采用(    )来实现算法.A. 栈   B. 队列   C.树   D.图7、用邻接表表示图进行深度优先遍历时,通常采用(   )来实现算法.A. 栈   B. 队列   C.树   D.图8、深度优先遍历类似于二叉树的(   )A.先序遍历   B.中序遍历   C.后序遍历   D.层次遍历9、广度优先遍历类似于二叉树的

16、(   )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出发,分别写出按深度优先

17、搜索法和广度优先搜索法进行遍历的结点序列. 深度优先搜索法: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、堆的形状是一棵(

18、   ).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