数据结构练习题

数据结构练习题 《数据结构》练习题 一、选择题 1(一个数组元素a[i]与( A )的表示等价。 A(*(a+i) B(a+i C(*a+i D(&a+i a是存储的是数组首地址，*a指向的就是数组第一个元素a[0],所以*(a+i)的地址和a[i]的地址一样。数组和指针在一定程度上本质是一样的。 2(当利用大小为N的数组顺序存储一个栈时，假定用top==N表示栈空，则退栈时，修改top指针的语句是( A )。 A(top++; B(top=0; C(top--; D(top=N; 3(队列的删除操作是在( A )进行。 A(队首 B(队尾 C(队前 D(队后 队列删除元素是在队首进行，队列是进先先出，相对来说，队首元素是最先进入队列的，因此出队应该是在队首进行。队列其实就和我们平时排队一样的 4(二叉树上叶子结点数等于( C )。 A(分支结点数加1 B(单分支结点数加1 C(双分支结点数加1 D(双分支结点数减1 5(哈希冲突是指( D )。 A(两个元素具有相同的序号 B(两个元素的键值不同，而其他属性相同 C(数据元素太多 D(不同键值的元素对应于相同的存储地址 6(由权值分别为3，6，7，2，5的叶子结点生成一棵哈夫曼树，它的带权路径长度为( A )。 A(51 B(23 C(53 D(74 23 10 13 5 5 6 7 2 3 (2+3)*3+5*2+(6+7)*2=51 7(某程序的时间复杂度为，其数量级表示为(3n，100，logn，nlogn)22 1 数据结构练习题 ( B )。 A(O(n) B( C(O(100) D( O(nlogn)O(logn)228(从二叉搜索树中查找一个元素时，其时间复杂度大致为( C )。 2A(O(n) B(O(1) C( D( O(n)O(logn)2 9(在线性表的散列存储中，若用m表示散列表的长度，n表示待散列存储的元素的个数，则装填因子α等于( A )。 n/mm/nA( B( C( D( n/(n，m)m/(n，m)10(在一棵二叉搜索树中，每个分支结点的左子树上所有结点的值一定( A )该结点的值。 A(小于 B(大于 C(不小于 D(大于等于 11(队列的插入操作是在( B )进行。 A(队首 B(队尾 C(队前 D(队后 12(在稀疏矩阵的带行指针向量的链接存储中，每个行单链表中的结点都具有相同的( A )。 A(行号 B(列号 C(元素值 D(地址 13(对于一棵具有n个结点的树，该树中所有结点的度数之和为( A )。 A(n-1 B(n C(n+1 D(2n 每个节点都有且只有一个入度。除去根节点没有入度 所以一共是N-1。 14(每次从无序表中取出一个元素，把它插入到有序表中的适当位置，此种排序方法叫做( A )排序。 A(插入 B(交换 C(选择 D(归并 15(在一个图中，所有顶点的度数之和等于所有边数的( A )倍 A(2 B(1 C(3 D(4 如果是无向图，顶点的度数之和是边数的两倍，这是没问题的，无向图中不讲入度和出度这两个概念。 有向图中，任意一条边AB(A->B)都会给A提供一个出度，给B提供一个入度，所以 顶点的度之和 = 2 * 顶点入度之和 = 2*顶点出度之和 = 顶点入度之和+顶点出度之和=边数的两倍. 16(在一个单链表中，若q所指结点是p所指结点的前驱结点，若在q与p之间插入一个s所指的结点，则执行( D )。 A(s,link=p,link; p,link=s; B(p,link=s; s,link=q; C(p,link=s,link; s,link=p; 2 数据结构练习题 D(q,link=s; s,link=p; 17(在一棵二叉树中，第4层上的结点数最多为( B ) A(31 B(8 C(15 D(16 第1层1个 2^0 第2层2个 2^1 第3层4个 2^2 第n层 2^(n-1) 18(在一个带权连通图G中，权值最小的边一定包含在G的( A )。 A(最小生成树 B(深度优先生成树中 C(广度优先生成树中 D(深度优先生成森林中 19(根据n个元素建立一棵二叉搜索树时，其时间复杂度大致为( D )。 2A(O(n) B( C( D( O(n)O(logn)O(nlogn)2220(以下数据结构中哪一个是线性结构,( B ) A(有向图 B(栈 C(二叉树 D(树 21(若某链表最常用的操作是在最后一个结点之后插入一个结点和删除最后一个结点，则最节省时间的存储方式是( C )。 A(单链表 B(双链表 C(带首结点的双循环链表 D(单循环链表 22(以下哪一个不是队列的基本运算,( A ) A(在队列第i个元素之后插入一个元素 B(从队头删除一个元素 C(判断一个队列是否为空 D(读取队头元素的值 23(字符A、B、C、D依次进入一个栈，按出栈的先后顺序组成不同的字符串，至多可以组成( B )个不同的字符串。 A(15 B(14 C(16 D(21 24(下面的二叉树中，不是完全二叉树的是( C )。 25(由权值分别为4，7，6，2的叶子生成一棵哈夫曼树，它的带权路径长度为( B )。 A(11 B(37 C(19 D(53 3 数据结构练习题 26(设有关键码序列(q,g,m,z,a)，下面哪一个序列是从上述序列出发建的小根堆的结果,( B ) A(a,g,m,q,z B(a,g,m,z,q C(g,m,q,a,z D(g,m,a,q,z 27(组成数据的基本单位是( C )。 A(数据项 B(数据类型 C(数据元素 D(数据变量 28(线性表的链接实现有利于( A )运算。 A(插入 B(读表元素 C(查找 D(定位 29(中序遍历一棵二叉排序树所得到的结点访问序列是键值的( C )序列。 A(递增或递减 B(递减 C(递增 D(无序 1.二叉排序树的概念: 二叉排序树是一种动态树表。 二叉排序树的定义:二叉排序树或者是一棵空树， 或者是一棵具有如下性质的二叉树: ? 若它的左子树非空，则左子树上所有结点的值均小于根结点的值; ? 若它的右子树非空，则右子树上所有结点的值均大于根结点的值; ? 左、右子树本身又各是一棵二叉排序树。二叉排序树的性质: 按中序遍历二叉排序树，所得到的中序遍历序列是一个递增有序序列。 30(SubStr(„DATA STRUCTURE?，5，9)=( A )。 A(‘STRUCTURE’ B(‘DATA’ C(‘ASTRUCTURE’ D(‘DATA STRUCTURE’ 从第5位开始截取9个字符 31(下列哪一种形态不为树,( A ) 32(下列哪种排序需要的附加存储开销最大,( C ) A(快速排序 B(堆排序 C(归并排序 D(插入排序 33(对下图的度为( B )。 v4 4 数据结构练习题 A(1 B(2 C(3 D(4 34(在内部排序中，排序时不稳定的有( A )。 A(快速排序 B(冒泡排序 C(归并排序 D(直接插入排序 35(设有1000个元素，用折半查找时，最大比较次数为( B )，最小比较次数为( D ) A(25 B(10 C(7 D(1 36(在一个单链表HL中，若要向表头插入一个由指针p指向的结点，则执行( B )。 A(HL=p; p,next=HL; B(p,next=HL; HL=p; C(p,next=HL; p=HL; D(p,next=HL,next; HL,next=p; 37(n个顶点的强连通图中至少含有( B )。 A(n-1条有向边 B(n条有向边 C(n(n-1)/2条有向边 D(n(n-1)条有向边 38(从一棵二叉搜索树中查找一个元素时，其时间复杂度大致为( C )。 2A( B( C( D( O(n)O(logn)O(1)O(n)2 39(对稀疏矩阵进行压缩存储的目的是( C )。 A(便于进行矩阵运算 B(便于输入和输出 C(节省存储空间 D(降低运算的时间复杂度 40(当一个作为实际传递的对象占用的存储空间较大并可能需要修改时，应最好把它说明为( B )参数，以节省参数的传输时间和存储参数的空间。 A(整型 B(引用型 C(指针型 D常值引用型 41(向一个长度为n的顺序表中插入一个新元素的平均时间复杂度为( A ) 2A( B( C( D( O(n)O(logn)O(n)O(1)2 42(采用链结构存储线性表时，其地址( C )。 A(必须是连续的 B(连续不连续都可以 C(部分地址必须是连续的 D(必须是不连续的 线性表有顺序表和链表两种存储结构。 顺序表:线性表的结点按逻辑次序依次存放在一组地址连续的存储单元里的方法。 5 数据结构练习题 链表:用一组任意的存储单元来存放线性表的结点，这组存储单元既可以是连续的，也可以是不连续的 43(具有2000个结点的二叉树，其高度至少为( B )。 A(9 B(10 C(11 D(12 44(按字母顺序，下图中的二叉排序树是( C )。 45(设单链表中指针p指着结点A，若要删除A之后的结点(若存在)，则需要修改指针的操作为( A )。 A(p,next=p,next,next; B(p=p,next; C(p=p,next,next; D(p,next=p; 46(在一个长度为n的顺序表的任一位置插入一个新元素的渐进时间复杂度为( A )。 2A( B( C( D( O(n)O(n)O(n/2)O(1) 47(带头结点的单链表first为空的判定条件是:( B )。 A(first==NULL B(first,link==NULL C(first,link==first; D(first!=NULL 48(当利用大小为n的数组顺序存储一个队列时，该队列的最大长度为( B )。 A(n-2 B(n-1 C(n D(n+1 为N-1, 因为队列需要设置成循环队列，所以必须有一个空格来区分队列的头和尾的分界线。 举个例子:一个长度为4的数组做循环队列，现在插入1，2，3，4四个数字: 作为队列，需要两个指针:队头指针head和队尾指针tail。初始的时 6 数据结构练习题 候(队空)，这两个指针是重合的，假设都指向a[1]位置。如下 a[0] = null a[1] = null<-- head(tail) a[2] = null a[3] = null 每插入一个值，tail指针向后移一个，每删除一个值，队头指针向“前”移动一个。那么插入1，2，3三个数以后，队列的情况如下: a[0] = null <-- tail a[1] = 1 <-- head a[2] = 2 a[3] = 3 如果现在插入4会出现什么情况, a[0] = 4 a[1] = 1 <--head(tail) a[2] = 2 a[3] = 3 队头指针和队尾指针再次重合～但是从第一步我们可以知道，队空的标志正是head和tail两个指针重合(事实上这也正是我们判断队列是否为空的标准)。这样的话，队满和队空的标志是一样的，这时不可接受的。 因此一个长度为N的数组来作为循环队列的话，队列的长度最长只能为N-1, 队空标志是head和tail重合，队满标志是tail在head“前”一位。 49(在系统实现递归调用时需利用递归工作记录保护实际参数的值。在传值参数情形，需为对应形式参数分配空间，以存放实际参数的副本;在引用参数情形，需保存实际参数的( D )，在被调用程序中可直接操作纵实际参数。 A(空间 B(副本 C(返回地址 D(地址 50(在一棵树中，没有前驱结点的结点是( C )。 A(分支结点 B(叶结点 C(树根结点 D(空结点 51(在一棵二叉树的二叉链表中，空指针域数等于非空指针域数加( A ) A(2 B(1 C(0 D(-1 一颗二叉树中，假设有N个点，则有N+1个空指针域，N-1个非空域 52(对于长度为9的有序表，若采用折半搜索，在等概率情况下搜索成功的平均搜索长度为( C )的值除以9。 A(20 B(18 C(25 D(22 7 数据结构练习题 链表中的位置 :1 2 3 4 5 6 7 8 9 搜索成功的长度:3 2 3 4 1 3 2 3 4 所以平均长度是 (3+2+3...+3+4) / 9 答案是: C 第五个查找1次 第二个和第七个查找两次 第一，第三和第六，第八要查找三次 第四和第九要查找四次 一共25次 53(在有向图中每个顶点的度等于该顶点的( C ) A(入度 B(出度 C(入度与出度之和 D(入度与出度之差 54(在基于排序码比较的排序算法中，( C )算法的最坏情况下的时间复杂度不高于 O(nlogn)2 A(起泡排序 B(希尔排序 C(归并排序 D(快速排序 排序方法 最坏时间复杂度 最好时间复杂度 平均时间复杂度 直接插入 O(n2) O(n) O(n2) 简单选择 O(n2) O(n2) O(n2) 起泡排序 O(n2) O(n) O(n2) 快速排序 O(n2) O(nlog2n) O(nlog2n) 堆排序 O(nlog2n) O(nlog2n) O(nlog2n) 归并排序 O(nlog2n) O(nlog2n) O(nlog2n) 55(当的值较小时，散列存储通常比其他存储方式具有( B ), 的查找速度。 A(较慢 B(较快 C(相同 D(不确定 56(设单链表中结点的结构为:struct node{int data;struct node *link;};，非空单链表first的尾结点(由p所指向)满足( C )。 A. p->link==NULL B. p==NULL C. p->link==NULL D. p->link==NULL 57(设有一个顺序栈S，元素A、B、C、D、E、F依次进栈。如果6个元素的出栈顺序为B、D、C、E、F、A，顺序栈的容量至少应为( A )。 A(3 B(4 C(5 D(6 58(在含n个顶点和e条边弧的有向图的邻接矩阵中，零元素的个数为( C )。 22A(e B(2e C( D( n,en,2e 59(下面关于串的叙述中，不正确的是( B )。 A(串是字符的有限序列 8 数据结构练习题 B(空串是由空格构成的串 C(模式匹配是串的一种重要运算 D(串既可以采用顺序存储，也可以采用链式存储 60(用数组data[0…m-1]作为循环队列SQ的存储空间，from为队头指针，rear为队尾指针，则执行入队操作后其尾指针rear值为( D )。 A(rear=rear+1 B(rear=(rear+1)%(m-1) C(rear=(rear-1)%m D(rear=(rear+1)%m 61(设有100个元素，用折半查找法进行查找时，在查找成功的情况下，最大比较次数是( D )。 A(100 B(50 C(99 D(7 62(下列排序方法中，哪一个是稳定的排序方法( B )。 A(直接选择排序 B(二分法插入排序 C(希尔排序 D(快速排序 63(广义表(a，(b，c)，d，e)的表头为( A )。 A(a B(a(b，c) C((a，(b，c)) D((a) 求下列广义表运算的结果: (1)head ((p,h,w)); (2)tail((b,k,p,h)); (3) head (((a,b),(c,d))); (4)tail(((a,b),(c,d))); (5)head(tail(((a,b),(c,d)))); (6)tail(head((((a,b),(c,d)))). 答: (1)head ((p,h,w))=p; (2)tail((b,k,p,h))=(k,p,h); (3)head (((a,b),(c,d)))=(a,b); (4)tail(((a,b),(c,d)))=((c,d));好像有问题这个 -----------------注意三和四返回结果的 区别 (取表尾运算符得到的结果一定为一个子表) (5)head(tail(((a,b),(c,d))))=(c,d); (6)tail(head(((a,b),(c,d))))=(b). 64(已知一棵二叉树的先序遍历序列为ABCDEF，中序遍历序列为CBAEDF，则后序遍历序列为( A )。 A(CBEFDA B(FEDCBA C(CBEDFA D(不确定 65(图的广度优先遍历类似于二叉树的( D ) A(先序遍历 B(中序遍历 C(后序遍历 D(层次遍历 66(顺序存储结构的特点是( A ) A(逻辑上相邻的数据元素在存储地址上也一定相邻 B(逻辑上相邻的数据元素在存储地址上不一定相邻 9 数据结构练习题 C(只能实现顺序存取元素的操作 D(只能实现随机存取元素的操作 67(从任一结点出发均可访问链表中的每一个结点，则该链表应为( B )。 A(单链表 B(双链表 C(链栈 D(链队列 68(设输入序列为6、3、5、9、2，则借助于栈可能得到的输出序列为( B )。 A(2、6、5、9、3 B(5、3、6、2、9 C(6、9、2、3、5 D(9、6、5、3、2 69(已知数组A[-2:5，4:8]按列存储，其中元素A[0][6]的起始地址为100，每个元素占4个字节，则元素A[4][7]的起始地址为( C )。 A(184 B(180 C(148 D(144 70(广义表的存储结构为( B )。 A(顺序存储结构 B(链式存储结构 C(单链表存储结构 D(十字链表存储结构 71(设abcdef以所给的次序进栈，若在进栈操作时，允许退栈操作，则下面得不到的序列为( D )。 A(fedcba B(bcafed C(dcefba D(cabdef 72(简单路径就是在路径中( A )。 A(顶点不重复出现 B(边不重复出现 C(起始点不重合 D(起始点重合 是指除了起点和终点有可能相同外，其余顶点均不相同的路径 73(邻接表和逆邻接表都是表示有向图的存储结构，下列叙述正确的是( B )。 A(邻接表中的结点数大于逆邻表中的结点数 B(邻接表中的结点数等于逆邻表中的结点数 C(邻接表中的结点数小于逆邻表中的结点数 D(邻接表中的结点数目与逆邻表中的结点数目无法比较多少 74(在哈希表中，常用的构造哈希函数的方法为( B )。 A(开放地址法 B(直接定址法 C(链地址法 D(线性探测再散列法 75(时间复杂度在最好情况下可以达到的排序方法有( A )。 O(n) A(起泡排序 B(简单选择排序 C(堆排序 D(折半插入排序 76(以下与数据的存储结构无关的术语是( B )。 A(栈 B(哈希表 C(线索树 D(队列 77(在双向链表存储结构中，删除p所指的结点指针的操作是 10 数据结构练习题 ( A )。 A(p,prior,next=p,next; p,next,prior=p,prior; B(p,prior=p,prior,prior; p,proir,next=p; C(p,next,proir=p; p,next=p,next,next; D(p,next=p,proir,prior; p,prior=p,next,next; 78(稳定的排序方法是( C )。 A(直接插入排序和快速排序 B(折半插入排序和堆排序 C(简单选择排序和冒泡排序 D(树形选择排序和希尔排序 排序法 平均时间 最差情形 稳定度 额外空间 备注 冒泡 O(n2) O(n2) 稳定 O(1) n小时较好 交换 O(n2) O(n2) 不稳定 O(1) n小时较好 选择 O(n2) O(n2) 不稳定 O(1) n小时较好 插入 O(n2) O(n2) 稳定 O(1) 大部分已排序时较好 基数 O(logRB) O(logRB) 稳定 O(n) B是真数(0-9)， R是基数(个十百) Shell O(nlogn) O(ns) 1next=p->next;p->next->prior=f;f->prior=p;p->next=f_________。 5(下面为简单的模式匹配算法，请在算法的下划线处填上正确的子句。 int index(s,t) { i=j=0; while(ikey==k)__return (t);_______________; if(t->key>k)___return(bstsearch(t,lchild,k))_____; 13 数据结构练习题 else_return(bstsearch(t,rchild),k)____________________________ __; } } 17(对于一个以顺序实现的共享栈[1…n]，栈顶指针分别为top1和top2，top1由小到大，top2由大到小，其判断下溢的条件是___top1=0或top2=n+1___;判断上溢的条件是____top1+1=top2_________。 18(双向循环链表的主要优点是_____既可以方便地找到一个结点的后继，又可以方便地找到一个结点的前驱______________。 19(上三角矩阵压缩存储的下标对应关系 i(2n,i，1)k=______________。 ，j,i(i,j) 2 20(设有一个空栈，现输入序列为1，2，3，4，5，经过Push，Push，Pop，Push，Pop，Push，Pop，Push，后，输出序列为 __2、3、4____________。 21(后序序列和中序序列相同的二叉树为_____单左子树二叉树或孤立结点__。 22(具有128个结点的完全二叉树的深度为__8_________。 23(有向图G用邻接矩阵A[1…m,1…m]存储，其第i行的所有元素 v值之和等于顶点的____出度_______。 i 24(设键值序列为建堆和排序全过程共需进行{k,k,？,k}12nn,,，n,1_______次堆调整。 ,,2，，25(在下面冒泡排序算法中填入适当的内容，使该算法在发现有序时能及时停止。 bubble(Rectype R[n]) { int i,j,exchang; Rectype temp; i=1; do{ exchang=False; for(j=n;j>=___i+1___;j--) if(R[j]prior___=p; f,next=p,next; _p->next->prior____=f; p,next=f。 27(一个具有n个顶点的有向安全图的弧数为______n(n-1)__________。 28(设一棵二叉树共用50个叶子结点(终端结点)，则它共有___49____个度为2的结点。 29(高度为h(?0)的二叉树，至少有____h___个结点，最多有 h2,1________个结点。 30(二维数组是一种非线性结构，其中的每一个数组元素最多有___2_____个直接前驱(或直接后继)。 31(将一个n阶三对角矩阵A的三条对角线上的元素按行压缩存放于一个一维数组B中，A[0][0]存放于B[0]中。对于任意给定数组元 (k，1),,素B[k]，它应是A中第_________行的元素。 ,,3，，32(链表对于数据元素的插入和删除不需移动结点，只需改变相关结点的____指针_______域的值。 33(在一个链式栈中，若栈顶指针等于NULL，则为____空栈_____________。 34(主程序第一次调用递归函数被称为外部调用，递归函数自己调用自己被称为内部调用，它们都需要利用栈保存调用后的____返回_________地址。 35(在一棵树中，______叶子_____结点没有后继结点。 36(一棵树的广义表表示为a(b(c，d(e，f)，g(h)，i(j，k(x，y)))，结点f的层数为_____3_______。假定根结点的层数为0。 n(n,1)37(n(n>0)个顶点的无向图最多有________条边，最少有2____0______条边。 38(在索引存储中，若一个索引项对应的数据对象表中的一个表项(记录)，则称此索引为_____稠密_________索引，若对应数据对象表中的若干个表项，则称此索引为______稀疏___________索引。 39(一个算法，如果不论问题规模大小，运行所需时间都一样，则该算法的时间复杂度是___________。 O(1) 40(在求最小生成树的两种算法中，_____Kruskal______算法适合于稀疏图。 三、应用题: 1(已知一个图的顶点集V和边集G分别为: 15 数据结构练习题 V={0，1，2，3，4，5，6，7} E={(0，1)8，(0，2)5，(0，3)2，(1，5)6，(2，3)25，(2，4)13，(3，5)9，(3，6)10，(4，6)4，(5，7)20} 按照普里姆算法从顶点O出发得到最小生成树，试写出在最小生成树中依次得到的各条边:_(0，3)2__，_(0，2)5__，_(0，1)8__，_(1，5)6_，__(3，6)10，__(6，4)4_，__(5，7)20_。 2(假定一组记录的排序码为(46，79，56，38，40，80，25，34)，则对其进行快速排序的第一次划分的结果为__[34 25 40 38] 46 [80 56 79]__。 3(有七个带权结点，其权值分别为3,7,8,2,6,10,14，试以它们为叶子结点构造一棵哈夫曼树，并计算出带权路径长度WPL。 WPL=131 4(假定一个待散列存储的线性表为(37，65，25，73，42，91，45，36，18，75)，散列地址空间为HT[12]，若采用除留余数法构造散列函数和拉链法处理冲突，试求出每一元素的散列地址，画出最后得到的散列表，求出平均查找长度。 平均查找长度ASL=(7*1+2*2+3*1)/10=1.4 5(设哈希表的地址空间为0—16，开始时哈希表为空，用线性探测 16 数据结构练习题 开放地址法处理冲突，对于数据元素Jan，Feb，Mar，Jun，Aug，Sep，Oct，Nov，Dec，试构造其对应的哈希表，，其中i为关H(key),i/2，， 键码中第一个字母在字母表中的序号。 地0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 址 关Aug Dec Feb Jan Mar Jun Oct Sep Nov 键 字 比1 1 1 1 1 3 2 1 4 较 次 数 6(设有5000个无序的元素，希望用最快的速度挑选出其中前10个最大的元素，在快速排序、堆排序和基数排序方法中，采用哪种方法最好,为什么, 在5000个无序的元素中，希望用最快的速度挑选出其中前10个最大的元素，在快速排序、堆排序和基数排序方法中，采用基数排序方法最好。因为快速排序未完成排序过程是找不到前10个最大元素的;堆排序在筛选和调整堆时比较费时间;而基数排序可以采用最高位优先进行分配和收集。 7(简述堆排序的基本思想，对关键值集合{72，73，71，23，94，16，50，68}对应的二叉树进行建堆，并写出具体步骤。 基本思想 堆的定义: n个关键字序列Kl，K2，…，Kn称为堆，当且仅当该序列满足如下性质(简称堆性质): (1) ki?K2i且ki?K2i+1 或(2)Ki?K2i且ki?K2i+1(1?i?FLOOR(n/2)) 若将此序列所存储的向量R[1..n]看做是一棵完全二叉树的存储结构，则堆实质上是满 足如下性质的完全二叉树:树中任一非叶结点的关键字均不大于(或不小于)其左右孩子(若 存在)结点的关键字。根结点(亦称为堆顶)的关键字是堆里所有结点关键字中最小者的堆称为小根堆。根结点(亦称为堆顶)的关键字是堆里所有结点关键字中最大者，称为大根堆。 17 数据结构练习题 用大根堆排序的基本思想: (1) 先将初始文件R[1..n]建成一个大根堆，此堆为初始的无序区; (2) 再将关键字最大的记录R[1](即堆顶)和无序区的最后一个记录R[n]交换，由此得 到新的无序区R[1..n-1]和有序区R[n]，且满足R[1..n-1].keys?R[n].key; (3) 由于交换后新的根R[1]可能违反堆性质，故应将当前无序区R[1..n-1]调整为堆。 然后再次将R[1..n-1]中关键字最大的记录R[1]和该区间的最后一个记录R[n-1]交换，由 此得到新的无序区R[1..n-2]和有序区R[n-1..n]，且仍满足关系 R[1..n-2].keys?R[n-1..n].keys，同样要将R[1..n-2]调整为堆。 8(假定一个大根堆为(56，38，42，30，25，40，35，20)，则依次从中删除两个元素后得到的堆为____40，38，35，30，25，20___________________。 9(已知一个图的顶点集V和边集E分别为: V={0，1，2，3，4，5，6，7} E={(0,4)8，(0,2)5，(0,3)2，(1,5)6，(2,3)25，(2,4)13，(3,5)9，(3,6)10，(4,6)4，(5,7)20 } 按照克鲁斯卡尔算法得到最小生成树，试写出在最小生成树中依次得到的各条边。__(0，3)2__，__(4，6)4___，_(0，2)5___，_(1，5)6__，_(0，1)8_，_(3，6)10_，_(5，7)20_。 10(假定一组数据的初始堆为(84，79，56，42，40，46，50，38)，请写出在堆排序阶段进行前三次对换和筛选运算后数据的排列情况。 数据排序情况:____(50，42，46，38，40，56，79，84)_。 11(假定一组记录的排序码为(46，79，56，38，40，80，36，40，75，66，84，24)，对其进行归并排序的过程中，第三趟归并后的结果为: [36 38 40 40 46 56 79 80] [24 66 75 84]__。 12(依次输入集合{20，13，22，5，16，3，48，24}中的键值，得到一棵二叉排序树，试画出该二叉树并求出在等概率下成功查找的平均查找长度。 1，1，2，2，3，3，2，4 ASL,,2.7520 a8 13 22 5 16 48 18 3 24 数据结构练习题 13(设下图所示的二叉树是由森林转换而成的，试将它还原成森林。 A H I B C D J K E F G 14(树与二叉树之间有何区别? 15(已知图如下所示。 19 数据结构练习题 (1)要求用Kruskal算法求出最小生成树; 5 1 2 5 6 5 3 18 3 4 6 (2)指出生成树的第一条边。 (3，4)3 四、判断题 1(具有线性排序关系的集合中，若a，b是集合中的任意两个元素，则必有anext; q->next=HL; HL=q; } } 对于结点类型为Lnode的单链表，写出以上算法的功能。 2(将一个单链表按逆序链接 3(写出以下函数的功能。 void DD(List &L,int i,ElemType x) { for(int j=L.size-1;j>=i-1;j--) L.list[j+1]=L.list[j]; L.list[i-1]=x; L.size++; } 3(向线性表L中第i个元素位置插入一个元素。 4(写出以下函数的功能。 bool EE(List &L) { int i=0; while (inext,*q; while (p!=NULL && p->data!=x) p=p->next; //找data域值为x的节点*p if (p==NULL) //未找到的情况 return false; else //找到的情况 { p->freq++; //频度增1 q=p->prior; //*q为p前驱节点 while (q!=h && q->freqfreq) { p->prior=q->prior;p->prior->next=p;//交换*p和*q的位置 q->next=p->next; if (q->next!=NULL) //*p不为最后一个节点时 q->next->prior=q; p->next=q;q->prior=p; q=p->prior; //q重指向*p的前趋节点 24 数据结构练习题 } return true; } } 3(编写一函数，按升序输出线性表L中的元素。 void OrderOutputList(LinearList &L) { } void OrderOutputList(LinearList& L) { int *b=new int[L.size]; int i,k; for(i=0;inext,*q; L->next=NULL; while (p!=NULL) //扫描所有的结点 25 数据结构练习题 { q=p->next; //让q指向*p结点的下一个结点 p->next=L->next; //总是将*p结点作为第一个数据结点 L->next=p; p=q; //让p指向下一个结点 } } 5(有一个带头结点的单链表，编写在值为x的结点之后插入m 个结点的算法。 算法描述如下: linklist insert(Linlist *head,float x,int m) { linklist *p,*q,*s; int i; float b; p=head->next; while(p!=NULL&&p->data!=x) p=p->next; if(p==NULL) printf("%f x not fount\n",x); else{ q=p->next; for(i=1;i<=m;i++){ s=(linklist *)malloc(sizeof(linklist)); scanf("%f",&b); s->data=b; p->next=s; p=s; } p->next=q; } return head; } 6(有两个串s1和s2，设计一个算法求这样一个串，该串中的字 符是s1和s2中的公共字符。 算法如下: 26 数据结构练习题 SqString CommChar(SqString s1,SqString s2) { SqString s3; int i,j,k=0; for (i=0;in;i++) { p=G->adjlist[i].firstarc; printf("%2d: ",i); while (p!=NULL) { printf("%2d",p->adjvex); p=p->nextarc; } printf("\n"); } } 8(给定n个记录的有序表A[0..n-1]和m个记录的有序表B[0..m-1]，将它们归并为一个有序表，存放到C[0..m+n-1]中，试写出这一算法。 算法如下: 27 数据结构练习题 void Merge(RecType A[],int n,RecType B[],int m,RecType C[]) { int i,j,k=0; while (iB[j]) { C[k]=B[j]; k++;j++; } else //A[i]=B[j] { C[k]=A[i]; k++;i++; C[k]=B[j]; k++;j++; } } while (i