数据结构复习题答案

江苏技术师范学院 数据结构复习题答案

答案

一、选择题

二、填空

1、数据元素的有限集，D上关系的有限集 2、n-i 3、队列 4、20 ,3

5、开放定址法，再哈希法，链地址法，建立一个公共溢出区 6、非零元很少(t<<m*n)且分布没有规律 7、简单路径 或 简单回路 或简单环 8、31 (n1+n2=0+ n2= n0-1=31）， 26-1 =32 9、 log2n

1、线性结构，树形结构，图形结构（网状结构） 2、表中一半，表长和该元素在表中的位置 3、栈顶，栈底

4、不包含任何字符（长度为0）的串 5、288 B

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． H C Q P A M S R D F X Y; 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．顺序查找（线性查找）

三、判断题

v x v v x x x v X v

× × ×

×

√

√ ×

√ √ √

x x x x v v v x v v

1、╳ 2、╳ 3、√ 4、√ 5、╳

1 X 2 V 3 x 4 x 5 V 6 x 7 v 8 v 9 x 10 v

四、简答、应用题

m

1 设n为正整数，给出下列程序段的时间复杂度。解：k<n, k的变化为1,3,9, 3 ,

m

即要求 3<n, mlog(3)<log(n),即k=k*3执行的频度m<log3n

所以T（n）=O(log3n) 或O（log (n)）

2 列出先序遍历能得到ABC序列的所有不同的二叉树。

江苏技术师范学院 数据结构复习题答案

3 已知某算法如下，试说明该算法实现的功能。 #define Max 100

void unknow(int num ,int r) {int st[Max],top=0; while (num!=0) { st[top++]=num%r; num=num/r; }

while (top>0)

cout << st[--top] << “ “; cout << endl; }

答：将十进制数num转换成r进制的数，并输出结果。

3 G是一个非连通无向图，共有28条边，则该图至少有多少个顶点？（5分）

解：设有一个顶点为独立的结点，其余结点为全连通图，则具有28条边的全连通图其有结点数为28<=n(n-1)/2,则n取满足该式的最小值为8，故该图至少有9个顶点。

5 对于下图所示的有向图G，给出从顶点0到其余各顶点的最短路径及路径长度。（6分）

1： 0-1 13 2： 0-2 8 3： 0-2-3 13 4： 0-2-3-4 19 5： 0-2-3-4-5 21 6： 0-1-6 20

6 已知某二叉树先序遍历的结果为：ABDGECFH，其中序遍历的结果为：DGBEAHFC，试画出这棵二叉树。）

7 对关键字序列（7，4，1，14，100，30，5，9，20，134），设哈希函数为H(k)=k mod 13,试给出表长为13的哈希表（用线性探测开放定址法处理冲突），并求出在等概率情况下，查找成功的平均查找长度。

江苏技术师范学院 数据结构复习题答案

解：

H(7)=7 mod 13 =7 H(4)=4 mod 13 =4 H(1)=1 mod 13 =1

H(14)=14 mod 13 =1 冲突

H1=（14+1） mod 13 =2 H(100)=100 mod 13 =9 H(30)=30 mod 13 =4 冲突 H1=（30+1）mod 13=5 H(5)=5 mod 13 =5 冲突 H1=（5+1）mod 13=6 H(9)=9 mod 13 =9 冲突 H1=（9+1）mod 13=10 H(20)=20 mod 13 =7 冲突 H1=（20+1）mod 13=8 H(134)=134 mod 13 =4 冲突 H1=（134+1）mod 13=5 冲突 H1=（134+2）mod 13=6 冲突

H1=（134+3）mod 13=7 冲突 H1=（134+4）mod 13=8 冲突 H1=（134+5）mod 13=9 冲突 H1=（134+6）mod 13=10 冲突 H1=（134+7）mod 13=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(a<b和c<d情况类似)，此时需2次比较，取b和d比较，若b>d，则有序a>b>d；若b<d时则有序c>d>b，此时已进行了3次比较。再把另外两个元素按折半插入排序方法，插入到上述某个序列中共需4次比较，从而共需7次比较。

1、每加对一个顶点和一条边得2分，全对得12分。

2、（1）二叉树的图形表示：）

(2) 对应森林为：

江苏技术师范学院 数据结构复习题答案

3计算各关键码得到的散列地址）

在散列表中散列结果

4. 解：设度为0的结点（即叶子结点或终端结点）数目为n0，树中分支数为B，树中结点总数为N，则有：

从度数看：N= n0+n1+n2+…+nm （1）

从分支数看，一棵树中只有一个根结点，其他的均为孩子结点，而孩子结点可由分支数得到，故有：N=B+1= 0*n0+1*n1+2*n2+…+m*nm +1 …… 此处隐藏：5385字，全部文档内容请下载后查看。喜欢就下载吧 ……