数据结构复习题答案.docx
- 文档编号:8007433
- 上传时间:2023-05-12
- 格式:DOCX
- 页数:24
- 大小:196.85KB
数据结构复习题答案.docx
《数据结构复习题答案.docx》由会员分享,可在线阅读,更多相关《数据结构复习题答案.docx(24页珍藏版)》请在冰点文库上搜索。
数据结构复习题答案
答案
一、选择题
题号
1
2
3
4
5
6
7
8
9
10
答案
B
B
A
D
A
B
A
D
C
C
题号
1
2
3
4
5
6
7
8
9
10
答案
A
C
C
B
C
D
C
D
C
B
题号
1
2
3
4
5
6
7
8
9
10
答案
A
B
A
C
C
C
A
B
B
D
题号
1
2
3
4
5
6
7
8
9
10
答案
A
D
D
C
B
D
C
C
A
B
题号
1
2
3
4
5
6
7
8
9
10
答案
D
B
A
B
D
C
D
C
C
D
题号
1
2
3
4
5
6
7
8
9
10
答案
A
B
C
D
B
B
C
A
A
D
题号
1
2
3
4
5
6
7
8
9
10
答案
A
A
C
B
B
A
D
B
A
C
二、填空
1、数据元素的有限集,D上关系的有限集
2、n-i
3、队列
4、20,3
5、开放定址法,再哈希法,链地址法,建立一个公共溢出区
6、非零元很少(t< 7、简单路径或简单回路或简单环 8、31(n1+n2=0+n2=n0-1=31),26-1=32 9、log2n 1、线性结构,树形结构,图形结构(网状结构) 2、表中一半,表长和该元素在表中的位置 3、栈顶,栈底 4、不包含任何字符(长度为0)的串 5、288B 6、9(注: 用log2(n)+1=8.xx+1=9 7、出度 8、不是 9、快速 10、8,7 1、存储结构,运算 2、前驱结点(的地址),O(n)。 3、假溢出时大量移动数据元素。 4、被匹配的主串,子串 5、行下标,列下标,元素值 6、5 7、O(n2) 8、O(n2),O(n2) 9、顺序查找(线性查找) 1、操作对象,关系 2、n-i+1 3、S×SS×S×× 4、20,3 5、8950 。 不考虑0行0列,利用列优先公式: LOC(aij)=LOC(ac1,c2)+[(j-c2)*(d1-c1+1)+i-c1)]*L得: LOC(a32,58)=2048+[(58-1)*(60-1+1)+32-1]]*2=8950 6、n,2。 答: 当k=1(单叉树)时应该最深,深度=n(层);当k=n-1(n-1叉树)时应该最浅,深度=2(层)) 7、邻接表。 8、插入,选择 9、28,6,12,20 10、小于等于表长的最大素数或不包含小于20的质因子的合数 11、带权路径长度最小的二叉树,又称最优二叉树 1.有穷性,确定性 2.O(n) 3.后继 4.线性表 5.度,深度 6.2i-1,2k-1 7.无向,有向 8.O(n2),1 9.静态,动态 1.一对一,一对多 2.指针,从任一结点出发都可访问到链表中每一个元素。 3.表中一半的元素,该元素的位置 4.1208 5.(a),(((b),c),((d))) 6.p->lchild==null&&p->rchlid==null 7.顶点 8.9 9.2n0-1 10.HCQPAMSRDFXY; 11.16 1.一对多,多对多 2.n-i 3.9 4.队列 5、n、2e 6.i/2、2i+1 7.活动、活动间的优先关系、活动(边上的权代表活动持续时间) ABDECF、DBEAFC、DEBFCA 8.3,(10,7,-9,0,47,23,1,8,98,36) 9.顺序查找(线性查找) 三、判断题 vxvvxxxvXv ××××√√×√√√ xxxxvvvxvv 1、╳2、╳3、√4、√5、╳ 6、╳7、√8、√9、╳10、√ 1.错 2.错 3.错 4.错 5.错 6.错 7.错 8.对 9.错 10.对 1X2V3x4x5V6x7v8v9x10v 1.× 2.√ 3.√ 4.√ 5.× 6.√ 7.× 8.× 9.√ 10.× 四、简答、应用题 1设n为正整数,给出下列程序段的时间复杂度。 解: k 所以T(n)=O(log3n)或O(log(n)) 2列出先序遍历能得到ABC序列的所有不同的二叉树。 3已知某算法如下,试说明该算法实现的功能。 #defineMax100 voidunknow(intnum,intr) {intst[Max],top=0; while(num! =0){ st[top++]=num%r; num=num/r; } while(top>0) cout< cout< } 答: 将十进制数num转换成r进制的数,并输出结果。 3G是一个非连通无向图,共有28条边,则该图至少有多少个顶点? (5分) 解: 设有一个顶点为独立的结点,其余结点为全连通图,则具有28条边的全连通图其有结点数为28<=n(n-1)/2,则n取满足该式的最小值为8,故该图至少有9个顶点。 5对于下图所示的有向图G,给出从顶点0到其余各顶点的最短路径及路径长度。 (6分) 1: 0-113 2: 0-28 3: 0-2-313 4: 0-2-3-419 5: 0-2-3-4-521 6: 0-1-620 6已知某二叉树先序遍历的结果为: ABDGECFH,其中序遍历的结果为: DGBEAHFC,试画出这棵二叉树。 ) 7对关键字序列(7,4,1,14,100,30,5,9,20,134),设哈希函数为H(k)=kmod13,试给出表长为13的哈希表(用线性探测开放定址法处理冲突),并求出在等概率情况下,查找成功的平均查找长度。 解: H(7)=7mod13=7 H(4)=4mod13=4 H (1)=1mod13=1 H(14)=14mod13=1冲突 H1=(14+1)mod13=2 H(100)=100mod13=9 H(30)=30mod13=4冲突 H1=(30+1)mod13=5 H(5)=5mod13=5冲突 H1=(5+1)mod13=6 H(9)=9mod13=9冲突 H1=(9+1)mod13=10 H(20)=20mod13=7冲突 H1=(20+1)mod13=8 H(134)=134mod13=4冲突 H1=(134+1)mod13=5冲突 H1=(134+2)mod13=6冲突 H1=(134+3)mod13=7冲突 H1=(134+4)mod13=8冲突 H1=(134+5)mod13=9冲突 H1=(134+6)mod13=10冲突 H1=(134+7)mod13=11冲突 在等概率情况下: ASL=(1*4+5*2+1*8)/10=2.2 1、答: 研究数据的组织方式(结构)及相应的抽象操作。 2、答: (1)选链式存储结构。 它可动态申请内存空间,不受表长度(即表中元素个数)的影响,插入、删除时间复杂度为O (1)。 (2)选顺序存储结构。 顺序表可以随机存取,时间复杂度为O (1)。 3.答: 用队列长度计算公式: (N+r-f)%N ①L=(40+19-11)%40=8②L=(40+11-19)%40=32 4.解: 按行存储的元素地址公式是: Loc(aij)=Loc(a11)+[(i-1)*m+(j-1)]*K 5.答: 度为2的树从形式上看与二叉树很相似,但它的子树是无序的,而二叉树是有序的。 即,在一般树中若某结点只有一个孩子,就无需区分其左右次序,而在二叉树中即使是一个孩子也有左右之分。 6. 7.答: 可以做到。 取a与b进行比较,c与d进行比较。 设a>b,c>d(ad,则有序a>b>d;若b 再把另外两个元素按折半插入排序方法,插入到上述某个序列中共需4次比较,从而共需7次比较。 1、每加对一个顶点和一条边得2分,全对得12分。 S: 顶点号 Edge: (顶点,顶点,权值) ①③ (1,2,2) ①③② (1,5,5) ①③②④ (2,4,3) ①③②④⑦ (2,7,6) ①③②④⑦⑤ (2,5,8) ①③②④⑦⑤⑥ (7,6,10) 2、 (1)二叉树的图形表示: ) (2)对应森林为: 3计算各关键码得到的散列地址) 关键码 56 74 23 11 69 22 59 29 散列地址 1 10 1 0 3 0 4 7 在散列表中散列结果 0 1 2 3 4 5 6 7 8 9 10 11 56 23 69 22 59 29 74 4.解: 设度为0的结点(即叶子结点或终端结点)数目为n0,树中分支数为B,树中结点总数为N,则有: 从度数看: N=n0+n1+n2+…+nm (1) 从分支数看,一棵树中只有一个根结点,其他的均为孩子结点,而孩子结点可由分支数得到,故有: N=B+1=0*n0+1*n1+2*n2+…+m*nm+1 (2) 综合 (1) (2)两式可得: n0+n1+n2+…+nm=0*n0+1*n1+2*n2+…+m*nm+1 从而有: n0=1+0*n1+1*n2+……+(m-1)*nm=1+ 即,叶结点的数目为1+ 5.从节省存储空间考虑: 先选堆排序,再选快速排序,最后选择归并排序; 从排序结果的稳定性考虑: 选择归并排序。 堆排序和快速排序都是不稳定排序; 6、输入序列为123456,不能得出435612,其理由是,输出序列最后两元素是12,前面4个元素(4356)得到后,栈中元素剩12,且2在栈顶,不可能栈底元素1在栈顶元素2之前出栈。 1.解: 用队列长度计算公式: (N+r-f)%N ①L=(40+19-11)%40=8②L=(40+11-19)%40=32 2.答: 3.答: 树和二叉树逻辑上都是树形结构,区别有二点: 一是二叉树的度至多为2,树无此限制;二是二叉树有左右子树之分,即使在只有一个分枝的情况下,也必须指出是左子树还是右子树,树无此限制。 二叉树不是树的特例。 4解: (1)kj-1(j=0,1,……,h) (2) (3)(i一1)*k+m 5.解: (1)视待排序数列由10个有序子序列构成(每个子序列中只有一个数,自然有序)。 合并相邻的两个有序子序列为一个有序子序列后得5个有序子序列: (2550)(1535)(8085)(2040)(3670) (2)继续合并相邻的两个有序子序列为一个有序子序列后得3个有序子序列: (15253550)(20408085)(3670) (3)继续合并相邻的两个有序子序列为一个有序子序列后得2个有序子序列: (1520253540508085)(3670) (4)继续合并相邻的两个有序子序列为一个有序子序列后得1个有序序列: (15202535364050708085) 6.答: ①顺序存储时,相邻数据元素的存放地址也相邻(逻辑与物理统一);要求内存中可用存储单元的地址必须是连续的。 优点: 存储密度大(=1),存储空间利用率高。 缺点: 插入或删除元素时不方便。 ②链式存储时,相邻数据元素可随意存放,但所占存储空间分两部分,一部分存放结点值,另一部分存放表示结点间关系的指针。 优点: 插入或删除元素时很方便,使用灵活。 缺点: 存储密度小(<1),存储空间利用率低。 7. (1)G1最多n(n-1)/2条边,最少n-1条边 (2)G2最多n(n-1)条边,最少n条边 1数据结构的主要研究对象是什么? 答: 研究数据的组织方式(结构)及相应的抽象操作。 2.解: 先序遍历: A、B、D、E、C、E、F、H 中序遍历: D、G、B、A、E、C、H、F 后序遍历: G、D、B、E、H、F、C、A 3.解: 邻接表: 邻接矩阵: 4.解: 初始序列: (100)(86)(48)(73)(35)(39)(42)(57)(66)(21) 一趟归并后: (86100)(4873)(3539)(4257)(2166) 二趟归并后: (487386100)(35394257)(2166) 三趟归并后: (35394248577386100)(2166) 四趟归并后: (213539424857667386100) 5.解: 邻接矩阵按普里姆算法求其最小生成树 6.解: (1)先画出判定树如右图所示(注: mid=(1+12)/2=6) (2)查找元素54,需依次与30,63,42,54等元素比较; 1 (1)4.O(log3n) (2).O(n) 2写一算法,输入一个任意的非负十进制数,将其转换为等值的10进制数(8分) (算法正确,即可得分) voidconversion() { intN; InitStack(S);//构造空栈 scanf(“%d”,N); while(N){ Push(S,N%16); N=N/10; } while(! StackEmpty(S)){ Pop(S,e); Printf(“%d”,e); } } 3.解: 1.最小生成树可直接画出,如右图所示。 2.可用邻接矩阵和邻接表来描述: 邻接表为: 4.建立堆结构: 97,87,26,61,70,12,3,45 (2)70,61,26,3,45,12,87,97 (4)45,12,26,3,61,70,87,97(6)12,3,26,45,61,70,87,97 5.解: (1)查找元素90,需依次与30,63,87,95,72等元素比较; (2)求ASL之前,需要统计每个元素的查找次数。 判定树的前3层共查找1+2×2+4×3=17次;但最后一层未满,不能用8×4,只能用5×4=20次, 所以ASL=1/12X(17+20)=37/12≈3.08 1.O(log3n) 2.设q=p->llink;则 q->rlink=p->rlink; p->rlink->llink=q; p->llink=q->llink; q->llink->rlink=p; p->rlink=q; q->llink=p 3.答: 有5种可能的顺序。 ①第3辆列车先出来,只有1种: 3,2,1 ②第2辆列车先出来,有2种,2,3,12,1,3 ③第1辆列车先出来,有2种,1,2,31,3,2 4.解 三元组表中的每个结点对应于稀疏矩阵的一个非零元素,它包含有三个数据项,分别表示该元素的行下标、列下标和元素值。 8 8 5 3 2 3 3 6 8 5 4 6 7 8 5 8 1 2 5.解: 6.解 邻接表为: 克鲁斯卡尔算法步骤 将所有边去掉,形成8个连通分量,依次取权值最小的边将两个不同的连通分量合成一个连通分量,直到最后开成一个连通分量。 取边的顺序是: (f,g),(a,c),(e,f),(a,b),(d,h),(d,b),(g,d) 五、算法设计题 1.[题目分析]本题要求将链表中数据域值最小的结点移到链表的最前面。 首先要查找最小值结点。 将其移到链表最前面,实质上是将该结点从链表上摘下(不是删除并回收空间),再插入到链表的最前面。 LinkedListdelinsert(LinkedListlist) ∥list是非空线性链表,链结点结构是(data,link),data是数据域,link是链域。 ∥本算法将链表中数据域值最小的那个结点移到链表的最前面。 {p=list->link;∥p是链表的工作指针 pre=list;∥pre指向链表中数据域最小值结点的前驱。 q=p;∥q指向数据域最小值结点,初始假定是第一结点 while(p->link! =null) {if(p->link->data p=p->link; } if(q! =list->link)∥若最小值是第一元素结点,则不需再操作 {pre->link=q->link;∥将最小值结点从链表上摘下; q->link=list->link;∥将q结点插到链表最前面。 list->link=q; } }∥算法结束 [算法讨论]算法中假定list带有头结点,否则,插入操作变为q->link=list;list=q。 2.解: intLeafCount_BiTree(BitreeT)//求二叉树中叶子结点的数目 { if(! T)return0;//空树没有叶子 elseif(! T->lchild&&! T->rchild)return1;//叶子结点 elsereturnLeaf_Count(T->lchild)+Leaf_Count(T->rchild);//左子树的叶子数加上右子树的叶子数 }//LeafCount_BiTree 1.intGet_Depth(BitreeT)//求子树深度的递归算法 { if(! T)return0; else { m=Get_Depth(T->lchild); n=Get_Depth(T->rchild); return(m>n? m: n)+1; } }//Get_Depth 2.解: intLeafCount_BiTree(BitreeT)//求二叉树中叶子结点的数目 { if(! T)return0;//空树没有叶子 elseif(! T->lchild&&! T->rchild)return1;//叶子结点 elsereturnLeaf_Count(T->lchild)+Leaf_Count(T->rchild);//左子树的叶子数加上右子树的叶子数 }//LeafCount_BiTree 2.解: 折半查找的C程序有很多参考资料,注意此题要求是整型量。 折半查找的一个递归算法如下,形式非常简洁! intSearch_Bin_Recursive(SSTableST,intkey,intlow,inthigh)//折半查找的递归算法 { if(low>high)return0;//查找不到时返回0 mid=(low+high)/2; if(ST.elem[mid].key==key)returnmid; elseif(ST.elem[mid].key>key) returnSearch_Bin_Recursive(ST,key,low,mid-1); elsereturnSearch_Bin_Recursive(ST,key,mid+1,high); } }//Search_Bin_Recursive 算法思路是: 先创建两个表头结点B和C,pb和pc分别指向B和C的最后结点。 扫描单链表A的所有结点,对于结点*pa,若其data域值小于0,则将*pa链接到B链表后;否则将*pa链接到C链表后。 算法如下: typedefstructnode{ intdata; structnode*next; }Lnode; voidsplit(Lnode*A,Lnode*B,Lnode*C); {Lnode*pa=A->next,*pb,*pc; B=newLnode;//创建头结点 C=newLnode;//创建头结点 pb=B;pc=C; while(pa! =NULL){ if(pa->data<0){//小于0的数据插入B队列 pb->next=pa;pb=pa; } else{//大于0的数据插入C队列 pc->next=pa;pc=pa; } pa=pa->next; } pb->next=pc->next=NULL; 2、 解: 方案1;哈夫曼编码 先将概率放大100倍,以方便构造哈夫曼树。 w={7,19,2,6,32,3,21,10},按哈夫曼规则: <{【[(2,3),6],(7,10)】,32},(19,21)> 1.#definem0100/*m0为算术表达式中最多字符个数*/ intcorrect(char*exp) { charst[m0]; inttop=0,i=1,tag; tag=1; while(i<=m0&&tag) { if(exp[i]==‘(‘||exp[i]==’[‘||exp[i]==’{‘)/*遇到‘(‘、’[‘或’{‘,则将其入栈*/ { top++; st[top]=exp[i]; } if(exp[i]==’)’)/*遇到’)’,若栈顶是‘(‘,则继续处理,否则以不配对返回*/ if(st[top]==‘(‘)top--; elsetag=0; if(exp[i]==’)’)/*遇到’]’,若栈顶是‘[‘,则继续处理,否则以不配对返回*/ if(st[top]==‘[‘]top--; elsetag=0; if(exp[i]==’)’)/*遇到’}’,若栈顶是‘{‘,则继续处理,否则以不配
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 复习题 答案