1、数据结构-8 及答案解析(总分：100.00，做题时间：90 分钟)一、B单项选择题/B(总题数：15，分数：30.00)1.如果二叉树中任何一个结点的值都小于它的左子树上所有结点的值而大于右子树上所有结点的值，要得到各结点值的递增序列，应按下列哪种次序排列结点 ( )（分数：2.00）A.先根B.中根C.后根D.层次2.下列说法正确的是( )（分数：2.00）A.树的先根遍历序列与其对应的二叉树的先根遍历序列相同B.树的先根遍历序列与其对应的二叉树的后根遍历序列相同C.树的后根遍历序列与其对应的二叉树的先根遍历序列相同D.树的后根遍历序列与其对应的二叉树的后根遍历序列相同3.已知一采用开放地
2、址法解决 Hash表冲突，要从此 Hash表中删除一个记录，正确的做法是( )（分数：2.00）A.将该元素所在的存储单元清空B.将该元素用一个特殊的元素替代C.将与该元素有相同 Hash地址的后继元素顺次前移一个位置D.用与该无素有相同 Hash地址的最后插入表中的元素替代4.顺序查找法适用于存储结构为( )的线性表。（分数：2.00）A.散列存储B.压缩存储C.顺序存储或链接存储D.索引存储5.下列说法中正确的是( )（分数：2.00）A.二叉树中任何一个结点的度都为 2B.二叉树的度为 2C.任何一棵二叉树中至少有一个结点的度为 2D.一棵二叉树的度可以小于 26.已知一棵二叉树结点的先
3、根序列为 ABDGCFK，中根序列为 DGBAFCK，则结点的后根序列为( )（分数：2.00）A.ACFKBDGB.GDBFKCAC.KCFAGDBD.ABCDFKG7.设串 s1=ABCDEFG，s2=PQRST，函数 con(x,y)返回 x和 y串的连(s,i,j)返回串 s的从序号 i的字符开始的 j个字符组成的子串，len(s)返回串 s的 con(subs(s1，2，len(s2)，subs(s1，len(s2)，2)的结果串是( )（分数：2.00）A.BCDEFB.BCDEFGC.BCPQRSTD.BCDEFEF8.顺序存储结构 ( )（分数：2.00）A.仅适合于静态查找表
4、的存储B.仅适合干动态查找表的存储C.既适合静态又适合动态查找表的存储D.既不适合静态又不适合动态查找表的存储9.用二分查找法对具有 n个结点的线性表查找一个结点所需的平均比较次数为( )（分数：2.00）A.O(n2)B.O(nlog2C.O(D.O(log210.与其他查找方法相比，哈希查找法的特点是( )（分数：2.00）A.通过关键字比较进行查找B.通过关键字计算记录存储地址进行查找C.通过关键字计算记录存储地址，并进行一定的比较进行查找D.通过关键字记录数据进行查找11.邻接表存储结构下图的广度优先遍历算法结构类似于树的( )（分数：2.00）A.先根遍历B.后根遍历C.按层遍历D.
5、先序遍历12.含 N个顶点的连通图中的任意一条简单路径，其长度不可能超过( )（分数：2.00）A.1B.N/2C.N-1D.N13.对含有( )个结点的非空二叉树，采用任何一种遍历方式，其结点访问序列均相同。（分数：2.00）A.OB.1C.2D.不存在这样的二叉树14.设有一个用线性探测法解决冲突得到的散列表： （分数：2.00）A.8B.9C.3D.615.设二叉树根结点的层次为 0，一棵高度为 h的满二叉树中的结点个数是( )（分数：2.00）A.2hB.2h-1C.2h-1D.2h+1-1二、B填空题/B(总题数：10，分数：20.00)16.在直接插入和直接选择排序中，如果初始数据
6、基本正序，则选用_，若初始数据基本反序，则选用_。（分数：2.00）填空项 1:_17.设一个链栈的栈顶指针为 ls，栈中结点两个字段分别为 info和 next，其中 next是指示后继结点的指针，栈空的条件是 1。如果栈不空，则退栈操作为 p：=ls； 2；dispose(p)。（分数：2.00）填空项 1:_18.在分块查找法中，首先查找 1，然后再查找相应的 2。（分数：2.00）填空项 1:_19.对于一个二维数组 Amn，若按行序为主序存储，则任一元素 Aij相对于 A00的地址为 1。（分数：2.00）填空项 1:_20.在一个按行优先顺序存储的二维数组(MN)中，假设数组的基地
7、址是 P，并且数组的每一个元素所占的存储空间为 d个字节，则 aij的地址计算公式为 1。（分数：2.00）填空项 1:_21.对角矩阵中，除了_的元素之外，其余的元素都是零。则对于一个 k对角线矩阵(k 为奇数)A 是满足下面的条件的矩阵；如果_，则元素 aij=0。（分数：2.00）填空项 1:_22._中结点的最大度数允许大于 2，而_中结点的最大度数不允许大于 2。（分数：2.00）填空项 1:_23.计算机软件系统中，有两种处理字符串长度的方法：一种是采用_，第二种是_。（分数：2.00）填空项 1:_24.在单链表中，除了首元结点外，任一结点的存储位置是由 1 指示。（分数：2.0
8、0）填空项 1:_25.大多数排序算法都有两个基本操作，它们是_和_。（分数：2.00）填空项 1:_三、B解答题/B(总题数：4，分数：20.00)26.对于散列文件来说，其存储单位是什么?对于一个能存储 m个桶，若需要存放的同义词大于 m，则需要如何处理?现在假设一个文件有 18个记录，其关键字分别为：30,11,27,04,19,86,73,89,32,05,103,58,45,67,77,81,08,48，假设桶的容量 m=3，桶数 b=7，现在要求用除余法做散列函数 H(key)=key%7，请给出该散列文件的表示方法。（分数：5.00）_27.已知下面的一个图，请根据普里姆算法构出
9、它的一棵最小生成的树。 （分数：5.00）_28.假设在树中，如果结点 x是结点 y的双亲时，用(x,y)来表示树边，已知一棵树的树边的集合为(i,m)，(i,n)，(e,i)，(b,e)，(b,d)，(a,b)，(g,j)，(g,k)，(c,g)，(c,f)，(h,l)，(c,h)，(a,c)，请用树形结构画出此树，并回答下面的问题。 (1)哪个是根结点? (2)哪些是叶结点? (3)哪个是 g的双亲? (4)哪些是 g的祖先? (5)哪些是 g的孩子? (6)哪些是 e的子孙? (7)哪些是 e的兄弟? (8)树的深度是多少? (9)树的度数是多少?（分数：5.00）_29.对于如图所示的
10、二叉树，请画出其顺序存储结构图。 （分数：5.00）_四、B算法阅读题/B(总题数：4，分数：20.00)30.INITIATE()的功能是建立一个空表。请在_处填上正确的语句。 lklist initiate_lklist() /*建立一空表*/ _; _; return(t); （分数：5.00）填空项 1:_31.以下运算实现在顺序栈上的退栈，请在_处用适当的语句予以填充。 int Pop(SqStackTp*sq,DataType*x) if(sqtop=0)error(“下溢“);return(0);) else*x=_; _; return(1); （分数：5.00）填空项 1:_
11、32.以下算法在开散列表 HP中查找键值等于 K的结点，成功时返回指向该点的指针，不成功时返回空指针。请分析程序，并在_上填充合适的语句。 pointer research_openhash(keytype K,openhash HP) i=H(K); /*计算 K的散列地址*/ p=HPi; /*i 的同义词子表表头指针传给 P*/ while(_)p=pnext; /*未达到表尾且未找到时，继续扫描*/ _; （分数：5.00）填空项 1:_33.基于三元组的稀疏矩阵转置的处理方法有两种，以下运算按照矩阵 A的列序来进行转置，请在_处用适当的语句予以填充。 Trans_Sparmat(Sp
12、MatrixTp a,SpMatrixTp*b) (*b).mum=a.nu;(*b).nu=a.mu;(*b).tu=a.tu if(a.tu) q=1; for(col=1;_;col+) for(p=1;p=a.tu;p+) if(_)=col) (*b).dataq.i=a.datap.j; (*b).dataq.j=a.datap.i; (*b).dataq.v=a.datap.v; _; （分数：5.00）填空项 1:_五、B算法设计题/B(总题数：1，分数：10.00)34.写出向某个有序文件中插入一个记录的程序。（分数：10.00）_数据结构-8 答案解析(总分：100.00，
13、做题时间：90 分钟)一、B单项选择题/B(总题数：15，分数：30.00)1.如果二叉树中任何一个结点的值都小于它的左子树上所有结点的值而大于右子树上所有结点的值，要得到各结点值的递增序列，应按下列哪种次序排列结点 ( )（分数：2.00）A.先根B.中根 C.后根D.层次解析：2.下列说法正确的是( )（分数：2.00）A.树的先根遍历序列与其对应的二叉树的先根遍历序列相同 B.树的先根遍历序列与其对应的二叉树的后根遍历序列相同C.树的后根遍历序列与其对应的二叉树的先根遍历序列相同D.树的后根遍历序列与其对应的二叉树的后根遍历序列相同解析：3.已知一采用开放地址法解决 Hash表冲突，要从
14、此 Hash表中删除一个记录，正确的做法是( )（分数：2.00）A.将该元素所在的存储单元清空B.将该元素用一个特殊的元素替代 C.将与该元素有相同 Hash地址的后继元素顺次前移一个位置D.用与该无素有相同 Hash地址的最后插入表中的元素替代解析：4.顺序查找法适用于存储结构为( )的线性表。（分数：2.00）A.散列存储B.压缩存储C.顺序存储或链接存储 D.索引存储解析：5.下列说法中正确的是( )（分数：2.00）A.二叉树中任何一个结点的度都为 2B.二叉树的度为 2C.任何一棵二叉树中至少有一个结点的度为 2D.一棵二叉树的度可以小于 2 解析：6.已知一棵二叉树结点的先根序列
15、为 ABDGCFK，中根序列为 DGBAFCK，则结点的后根序列为( )（分数：2.00）A.ACFKBDGB.GDBFKCA C.KCFAGDBD.ABCDFKG解析：7.设串 s1=ABCDEFG，s2=PQRST，函数 con(x,y)返回 x和 y串的连(s,i,j)返回串 s的从序号 i的字符开始的 j个字符组成的子串，len(s)返回串 s的 con(subs(s1，2，len(s2)，subs(s1，len(s2)，2)的结果串是( )（分数：2.00）A.BCDEFB.BCDEFGC.BCPQRSTD.BCDEFEF 解析：8.顺序存储结构 ( )（分数：2.00）A.仅适合于
16、静态查找表的存储B.仅适合干动态查找表的存储C.既适合静态又适合动态查找表的存储 D.既不适合静态又不适合动态查找表的存储解析：9.用二分查找法对具有 n个结点的线性表查找一个结点所需的平均比较次数为( )（分数：2.00）A.O(n2)B.O(nlog2C.O(D.O(log2 解析：10.与其他查找方法相比，哈希查找法的特点是( )（分数：2.00）A.通过关键字比较进行查找B.通过关键字计算记录存储地址进行查找C.通过关键字计算记录存储地址，并进行一定的比较进行查找 D.通过关键字记录数据进行查找解析：11.邻接表存储结构下图的广度优先遍历算法结构类似于树的( )（分数：2.00）A.先
17、根遍历B.后根遍历C.按层遍历 D.先序遍历解析：12.含 N个顶点的连通图中的任意一条简单路径，其长度不可能超过( )（分数：2.00）A.1B.N/2C.N-1 D.N解析：13.对含有( )个结点的非空二叉树，采用任何一种遍历方式，其结点访问序列均相同。（分数：2.00）A.OB.1 C.2D.不存在这样的二叉树解析：14.设有一个用线性探测法解决冲突得到的散列表： （分数：2.00）A.8B.9C.3D.6 解析：15.设二叉树根结点的层次为 0，一棵高度为 h的满二叉树中的结点个数是( )（分数：2.00）A.2hB.2h-1C.2h-1D.2h+1-1 解析：二、B填空题/B(总题
18、数：10，分数：20.00)16.在直接插入和直接选择排序中，如果初始数据基本正序，则选用_，若初始数据基本反序，则选用_。（分数：2.00）填空项 1:_ （正确答案：直接插入排序 直接选择排序）解析：17.设一个链栈的栈顶指针为 ls，栈中结点两个字段分别为 info和 next，其中 next是指示后继结点的指针，栈空的条件是 1。如果栈不空，则退栈操作为 p：=ls； 2；dispose(p)。（分数：2.00）填空项 1:_ （正确答案：ls=null 这是指链栈没有设置头结点的情况，一般情况下也不必设置 ls：=ls.next；这一操作让头指针指示下一个结点）解析：18.在分块查找
19、法中，首先查找 1，然后再查找相应的 2。（分数：2.00）填空项 1:_ （正确答案：索引表块）解析：19.对于一个二维数组 Amn，若按行序为主序存储，则任一元素 Aij相对于 A00的地址为 1。（分数：2.00）填空项 1:_ （正确答案：ij+i 全元素位置）解析：20.在一个按行优先顺序存储的二维数组(MN)中，假设数组的基地址是 P，并且数组的每一个元素所占的存储空间为 d个字节，则 aij的地址计算公式为 1。（分数：2.00）填空项 1:_ （正确答案：LOC(a ij)=P+iN+jd）解析：21.对角矩阵中，除了_的元素之外，其余的元素都是零。则对于一个 k对角线矩阵(k
20、 为奇数)A 是满足下面的条件的矩阵；如果_，则元素 aij=0。（分数：2.00）填空项 1:_ （正确答案：主对角线和主对角线相临两侧的若干条对角线上 ik 或jk）解析：22._中结点的最大度数允许大于 2，而_中结点的最大度数不允许大于 2。（分数：2.00）填空项 1:_ （正确答案：树 二叉树）解析：23.计算机软件系统中，有两种处理字符串长度的方法：一种是采用_，第二种是_。（分数：2.00）填空项 1:_ （正确答案：固定长度 设置长度指针）解析：24.在单链表中，除了首元结点外，任一结点的存储位置是由 1 指示。（分数：2.00）填空项 1:_ （正确答案：其直接前趋结点的链
21、域的值）解析：25.大多数排序算法都有两个基本操作，它们是_和_。（分数：2.00）填空项 1:_ （正确答案：比较两个关键字的大小 改变指向记录的指针或者移动记录本身）解析：三、B解答题/B(总题数：4，分数：20.00)26.对于散列文件来说，其存储单位是什么?对于一个能存储 m个桶，若需要存放的同义词大于 m，则需要如何处理?现在假设一个文件有 18个记录，其关键字分别为：30,11,27,04,19,86,73,89,32,05,103,58,45,67,77,81,08,48，假设桶的容量 m=3，桶数 b=7，现在要求用除余法做散列函数 H(key)=key%7，请给出该散列文件的
22、表示方法。（分数：5.00）_正确答案：()解析：磁盘上的文件记录通常是成组存放的，若干个记录组成一个存储单位，在散列文件中，这个存储单位叫做桶。 如果一个桶能放 m个记录，则如果现在已经存放了 m个记录时，继续存放记录就会产生“溢出”，当发生“溢出”时，一般采用拉链法，就是将第 m+1个同义词存放在另外_个桶中，通常此桶就称为“溢出桶”，相应的前 m个同义词存放的桶就称为是“基桶”，溢出桶和基桶大小相同。 根据散列函数，得到对应的关键字的散列地址为：2,4,6,4,5,2,3,5,4,5,5,2,3,4,0,4,1,6，则得到的散列文件表示如下： 27.已知下面的一个图，请根据普里姆算法构出
23、它的一棵最小生成的树。 （分数：5.00）_正确答案：()解析：构造最小生成树的过程如下： 28.假设在树中，如果结点 x是结点 y的双亲时，用(x,y)来表示树边，已知一棵树的树边的集合为(i,m)，(i,n)，(e,i)，(b,e)，(b,d)，(a,b)，(g,j)，(g,k)，(c,g)，(c,f)，(h,l)，(c,h)，(a,c)，请用树形结构画出此树，并回答下面的问题。 (1)哪个是根结点? (2)哪些是叶结点? (3)哪个是 g的双亲? (4)哪些是 g的祖先? (5)哪些是 g的孩子? (6)哪些是 e的子孙? (7)哪些是 e的兄弟? (8)树的深度是多少? (9)树的度数
24、是多少?（分数：5.00）_正确答案：()解析：树的结构如下图所示： (1)a 是根结点 (2)m,n,d,f,l,j,k 是叶结点 (3)c 是 g的双亲 (4)a 和 e是 g的祖先 (5)j,k 是 g的孩子 (6)i,m,n 是 e的子孙 (7)d 是 e的兄弟 (8)树的深度是 5 (9)树的度数是3 29.对于如图所示的二叉树，请画出其顺序存储结构图。 （分数：5.00）_正确答案：()解析：二叉树的顺序存储就是将二叉树的结点按编号存在向量 B0,n中，其中 B0用来存放结点 T数，如果树中某些编号对应的结点不存在，则对应存储空间为“空”，根据上述规则，我们得到： 四、B算法阅读题
25、/B(总题数：4，分数：20.00)30.INITIATE()的功能是建立一个空表。请在_处填上正确的语句。 lklist initiate_lklist() /*建立一空表*/ _; _; return(t); （分数：5.00）填空项 1:_ （正确答案：t=malloc(size) tnext=NULL）解析：31.以下运算实现在顺序栈上的退栈，请在_处用适当的语句予以填充。 int Pop(SqStackTp*sq,DataType*x) if(sqtop=0)error(“下溢“);return(0);) else*x=_; _; return(1); （分数：5.00）填空项 1:
26、_ （正确答案：sqdatasqtop sqtop-）解析：32.以下算法在开散列表 HP中查找键值等于 K的结点，成功时返回指向该点的指针，不成功时返回空指针。请分析程序，并在_上填充合适的语句。 pointer research_openhash(keytype K,openhash HP) i=H(K); /*计算 K的散列地址*/ p=HPi; /*i 的同义词子表表头指针传给 P*/ while(_)p=pnext; /*未达到表尾且未找到时，继续扫描*/ _; （分数：5.00）填空项 1:_ （正确答案：(P!=NULL)(*b).nu=a.mu;(*b).tu=a.tu if(
27、a.tu) q=1; for(col=1;_;col+) for(p=1;p=a.tu;p+) if(_)=col) (*b).dataq.i=a.datap.j; (*b).dataq.j=a.datap.i; (*b).dataq.v=a.datap.v; _; （分数：5.00）填空项 1:_ （正确答案：col=a.nu a.datap.j q+）解析：五、B算法设计题/B(总题数：1，分数：10.00)34.写出向某个有序文件中插入一个记录的程序。（分数：10.00）_正确答案：()解析：所谓有序文件是指文件的记录按关键字由小到大(或由大到小)顺序存放。为方便起见，可设文件的每一个记
28、录是一个整数，文件上数据是按由小到大顺序存放。设插入数据是命令行的第 3个参数，且设为d。若原文件中没有数据，则 d写入文件；若有数据，则找到第 1个比 d大的数据 i，先写入 d，再将 i和其后各数据写回文件中，可通过调用 fseek函数采实现插入。相应程序为： #includestdio.h #includestdlib.h #includeio.h #includefcntl.h #define LEN sizeof(int) void main(int argi,char*argc) int fp,i,d; if(argi3) printf(“filename int/11“) exi
29、t(0); d=atoi(argc2); fp=open(argc1,O_GREAT| O_RDWRI O_BINARY,s_IREAD| S_IWRITE); while(1) if( read(fp,) if(i=d) /*文件中读出数据 i，若 i=d，则先存 d*/ do fseek(fp,-1L*lan,SEEK_CUR); /*文件指针后退 1个记录*/ write(fp, /*d 写到文件中*/ d=i; /*原 i作 d，以便处理其他数据*/ while(read(fp, write(fp，/*继续读数据，并判别文件是否结束*/ break; close(fp); /*main*/
