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

一、单选:
1.数据结构通常是研究数据的(  )及它们之间的相互关系.
A.存储和逻辑结构
B.存储和抽象
C.理想与抽象
D.理想与逻辑
2.数据在计算机存储器内表示时,物理地址与逻辑地址相同并且是连续的,称为(  )
A.存储结构
B.逻辑结构5
C.顺序存储结构
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;i<n;i++)
 for(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指向队头元素，队尾无名指是针指向队尾元素后的一个空闲元素。
.在循环队列中，队空标志为_front==rear__队满标志为__front==(rear+1)%m_
.当rear>=front时，队列长度为_rear-front_；当rear<FRONT时，队列长度是_rear+m-front__。
7、在队列中存取数据应遵从的原则是：__先进后出
8、在队列结构中，允许插入的一端称为____队尾___，允许删除的一端称为：___队头_
9、s1="abcd",s2="cd"，则s2在s1中的位置是__3
10、__不含任何字符的串___称为空串，_仅含空格字符的串__称为空白串。
二、简答：
1、设长度为n的链队列用单循环链表表示，若只设头指针，则入队，出队操作的时间是什么？如果只设尾指针呢？
2、设T[0..n-1]="abaabaabcaabaa" P[0..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*m
C.da1-i*m
D.da1+(i+1)*m
5、在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、链表相对于顺序表的优点有_不需要预分配存储空间___和_插入、删除_____操作方便
5、在n个结点的顺序表中,删除一个结点需平均移动__（n－1）/2______个结点,具体的移动次数取决于__表长n和删除位置I___________
6、在n个结点的顺序表中,插入一个结点需平均移动__ n/2______个结点,具体的移动次数取决于___表长n和插入位置i_________.
7、在顺序表中访问任意一个结点的时间复杂度均为__ O(1)_____.因此,顺序表也称为_随机存取________的数据结构.
8、在n个结点的单链表中要删除已知结点*p,需找到_前驱结点的地址______,其时间复杂度为_ O(n)_____.
9、在双链中要删除已知结点*p,其时间复杂度为_ O(1)
10、在单链表中,要在已知结点*p之前插入一个新结点,仍需找到_节点p的前一个节点___,其时间复杂度为__ 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、设二维数组A[0..m-1][0..n-1]按行优先顺序存储在内存中，每个元素aij占d个字节，则aij的地址为_LOC(a00)+(i*n+j)*d _
2、已知二维数组A8*10中，每个元素占两个字节，元素a12的地址为1000，则元素a00的地址为_976_
3、若数组A定义为A[2..m][2..n]，则元素aij的地址为：__LOC(a00)+j*m=i________
4、对于任何一棵二叉树T，如果其终端结点数为n0，度为2的结点数为n2，则有什么样的关系式。n0=n2+1
5、设x是一棵树，x''''''''是对应于x的二叉树，则x的先根遍历和x''''''''的__先序______遍历相同。
6、深度为K的二叉树至多有___6.2^k-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，那么当把森林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、已知二叉树有50个叶子结点，且仅有一个孩子的结点数为30，则总结点数为__129___。
二、简答：
1、在具有n个结点的K（k>=2)叉树的K叉链表表示中，有多少个空指针。
n个结点的K叉树共有n*k个指针域，已使用的指针域为n-1,所以空指针的个数为：n(k-1)+1
2、已知一棵二叉树的前序序列和中序序列分别为abdghcefi和gdhbaecif,给出这棵二叉树的后序遍历序列。

一、选择
1、在一个图中，所有顶点的度数之和等于图的边数的 (  )倍.
A. 1/2  B.1  C.2  D.4
2、在一个有向图中,所有顶点的入度之和等于所有顶点的出度之和的(   )倍.
A. 1/2  B.1  C.2  D.4
3、有8个结点的无向图最多有(   )条边.
A.14   B.28   C.56  D.112
4、有8个结点的无向连通图最少有( )条边.
A.5  B.6   C.7   D.8

5、有8个结点的有向完全图有(  )条边.
A.14    B.28   C.56  D.112
6、用邻接表表示图进行广度优先遍历时,通常采用(    )来实现算法.
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,53
B.94,23,31,72,16,53
C.16,53,23,94,31,72
D.16,23,53,31,94,72
2、堆是一种(    )排序
A.插入  B.选择  C.交换    D.归并
3、堆的形状是一棵(   ).
A.二叉排序树    B.满二叉树   C.完全二叉树  D.平衡二叉树
4、若一组记录的排序码为(46,79,56,38,40,84),则利用堆的方法建立的初始堆为(   )
A. 79,46,56,38,60,86
B.84,79,56,38,40,46
C.84,79,56,46,40,38
D.84,56,79,40,46,38
5、若一组记录的关键码为(46,79,56,38,40,84),则利用快速排序的方法,以第一个记录为基准得到的一次划分结果为(   )
A.38,40,46,56,79,84
B.40,38,46,79,56,84
C.40,38,46,56,79,84
D.40,38,46,84,56,79
6、设有100个元素,用折半查找法进行查找的时候,最大比较的次数是(   )
A.15   B.50  C.10   D.7
7、对线性表进行二分查找的时候,要求线性表必须(   )
A.以顺序方式
B.以链接方式存储
C.以顺序方式存储,且结点按斗争字有序排列
D.以链接方式存储,且结点按关键字有序排列
8、稠密索引是指(   )
A.索引密度大的文件
B.索引量大的文件
C.为每个主记录建立一个索引项的文件
D.为每个页块建立一个索引项的文件
9、稀疏索引是指(   )
A.索引密度小的文件
B.索引量小的文件
C.为每个主记录建立一个索引项的文件
D.为每个页块建立一个索引项的文件