1、数据结构-10 及答案解析(总分：100.00，做题时间：90 分钟)一、B单项选择题/B(总题数：15，分数：30.00)1.在有向图中，所有顶点的入度之和是所有顶点出度之和的( )倍。（分数：2.00）A.0.5B.1C.2D.42.某二叉树的前序遍历结点访问顺序是 abdgcefh，中序遍历的结点访问顺序是 bgbaechf，则其后序遍历的结点访问顺序是( )（分数：2.00）A.bdgcefhaB.gdbecfhaC.bdgechfaD.gdbehfca3.C语言数组 Datam+1作为循环队列 SQ的存储空间，front 为队头指针，rear 为队尾指针，则执行出队操作的语句为( )
2、（分数：2.00）A.front=front+1B.front=(front+1)%mC.rear=(rear+1)%mD.front=(front+1)%(m+1)4.任何一个带权的无向连通图的最小生成树( )（分数：2.00）A.只有一棵B.有一棵或多棵C.一定有多棵D.可能不存在5.倒排文件的主要优点是( )（分数：2.00）A.便于进行插入和删除运算B.便于进行文件的合并C.能大大提高基于非关键码数据项的查找速度D.能大大节省存储空间6.在一个链队中，假设 f和 r分别为队首和队尾指针，则删除一个结点的运算是( )（分数：2.00）A.r=fnextB.r=rnextC.f=fnext
3、D.f=rnext7.在一棵完全二叉树的顺序存储方式中，若编号为 t的结点有右孩子，则此结点右孩子的编号为( )（分数：2.00）A.2tB.2t-1C.2t+1D.t/28.对采用二分查找法进行查找运算的查找表，要求按( )方式进行存储。（分数：2.00）A.顺序存储B.链式存储C.顺序存储且结点按关键字有序D.链式存储且结点按关键字有序9.森林 T中有 4棵树，第一、二、三、四棵树的结点个数分别是 n1，n 2，n 3，n 4，那么当把森林 T转换成一棵二叉树后，其根结点的左孩子上有( )个结点。（分数：2.00）A.n1-1B.n1C.n1+n2+n3D.n2+n3+n410.对于一个具
4、有 N个结点和 E条边的无向图，若采用邻接表示，则表头向量的大小是( )（分数：2.00）A.NB.N+1C.N-ED.N-111.在一个具有 n个单元的顺序栈中，假设栈底是存储地址的高端，现在我们以 top作为栈顶指针，则作退栈操作时，top 的变化是( )（分数：2.00）A.top=top-1B.top=top+1C.top不变D.top不确定12.在桶排序中，其平均时间复杂度是( )（分数：2.00）A.O(1)B.O(C.O(n2)D.O(1g13.一个队列的输入序列是 1,2,3,4，则队列的输出序列是( )（分数：2.00）A.4,3,2,1B.1,2,3,4C.1,4,3,2D
5、.3,2,4,114.如果以链表作为栈的存储结构，则退栈操作时( )（分数：2.00）A.必须判别栈是否满B.判别栈元素的类型C.必须判别栈是否空D.对栈不作任何判别15.从一个长度为 n的顺序表中删除第 i个元素(1in)8 寸，需要向前移动( ) A n-i Bn-i+1 Cn-i-1 Di（分数：2.00）A.B.C.D.二、B填空题/B(总题数：10，分数：20.00)16.拓扑排序指的是找一个有向图的 1 的过程。（分数：2.00）填空项 1:_17.存储在直接存储器上的顺序文件可以用顺序查找法存取，也可以用_和进行查找。（分数：2.00）填空项 1:_18.在 1 遍历二叉树的序列
6、中，任何结点的子树上的所有结点，都是直接跟在该结点之后。（分数：2.00）填空项 1:_19.设 N阶方阵 A中的任一元素 aij(1i，jN)，当 i=j或 i+1=j时，a ij0，否则 aij=0， 若将 A按如下方式映象到一维数组 S中 （分数：2.00）填空项 1:_20.在双向链表中，每个结点含有两个指针域，一个指向其_结点，另一个指向_结点。（分数：2.00）填空项 1:_21.栈和队列均可视为特殊的线性表，所不同的在于对这二种特殊线性表_和_运算的限定不一样。（分数：2.00）填空项 1:_22.在串的链式存储结构中，有一个串 S1=“ejidc“，我们假设存储时结点的大小为
7、1，并设指针占有 4个字节，则链串的存储密度为_，又假设串 S2=“abcdefg“在存储时我们设定结点的大小为 4，指针占有4个字节，则此链串的存储密度为_。（分数：2.00）填空项 1:_23.给定一个具有 n个元素的向量，建立一个有序单链表的时间复杂度是 1。（分数：2.00）填空项 1:_24.稀疏矩阵一般的压缩存储方法有 2种，它们分别是 1 和 2。（分数：2.00）填空项 1:_25.由权值为 1,2,3,4,5,6的六个叶子结点构成一棵哈夫曼树，则带权的路径的长度为 1。（分数：2.00）填空项 1:_三、B解答题/B(总题数：4，分数：20.00)26.对于下面用三元组表示的
8、稀疏矩阵，请分别写出它们所对应的稀疏矩阵。 （分数：5.00）_27.假设有下面所示的稀疏矩阵，请写出其三元组表(按行优先的顺序)。 （分数：5.00）_28.假设有一个长度为 n的有序序列，在进行查找时，可以借助二叉树来进行，请结合二叉树的性质来分析二分查找的最坏性能和平均性能。（分数：5.00）_29.已知一棵二叉树按照顺序结构存储，其存储结构如下： （分数：5.00）_四、B算法阅读题/B(总题数：4，分数：20.00)30.以下算法实现若开散列表 HP中无键值为 K的结点，则插入一个这样的结点。请分析程序，并在_上填充合适的语句。 void insert_openhash(keytyp
9、e K,openhash HP) if(research_openhash(K,HP)=NULL) i=H(K); q=malloc(size);qkey=_; /*生成新结点*/ _=HPi;HPi=_; /*前插法链入新结点*/ （分数：5.00）填空项 1:_31.以下运算实现在链队上的出队列，请在_处用适当的语句予以填充。 int OutQueue(QueptrTp*lq,DataType*x) LqueueTp*s; if(1qfront=lqrear)error(“队空“);return(0); else s=(lqfront)next; _=sdata; (lqfront)nex
10、t_; if(snext=NULL)lqrear=lqfront; free(s); return(1); （分数：5.00）填空项 1:_32.以下运算实现在链栈上的进栈，请在_处用适当的语句予以填充。 void Push(LStackTp*ls,DataType x) LStackTp*p;p=malloc(sizeof(LStackTp); _; pnext=ls; _; （分数：5.00）填空项 1:_33.以下将 ah，a m，和 am+1an，两个有序序列(它们相应的关键字值满足 KhK m，K m+1K n，)合并成一个有序序列 Rh，R n，(使其关键字值满足 Kh，K n，)
11、。请分析算法，并在_上填充适当的语句。 void merge(list a,list R,int h,int m,int n) i=h;k=h;j=m+1; while(im)_; elseRk=_;_; k+; while(i=_)Rk=ai;i+;k+;) while(j=_)Rk=aj;j+;k+; 此算法的执行时间为_。（分数：5.00）填空项 1:_五、B算法设计题/B(总题数：1，分数：10.00)34.采用单链表作为存储结构，试编写一个函数来实现用选择排序方法进行升序排列。（分数：10.00）_数据结构-10 答案解析(总分：100.00，做题时间：90 分钟)一、B单项选择题/
12、B(总题数：15，分数：30.00)1.在有向图中，所有顶点的入度之和是所有顶点出度之和的( )倍。（分数：2.00）A.0.5B.1 C.2D.4解析：2.某二叉树的前序遍历结点访问顺序是 abdgcefh，中序遍历的结点访问顺序是 bgbaechf，则其后序遍历的结点访问顺序是( )（分数：2.00）A.bdgcefhaB.gdbecfhaC.bdgechfaD.gdbehfca 解析：3.C语言数组 Datam+1作为循环队列 SQ的存储空间，front 为队头指针，rear 为队尾指针，则执行出队操作的语句为( )（分数：2.00）A.front=front+1B.front=(fro
13、nt+1)%mC.rear=(rear+1)%mD.front=(front+1)%(m+1) 解析：4.任何一个带权的无向连通图的最小生成树( )（分数：2.00）A.只有一棵B.有一棵或多棵 C.一定有多棵D.可能不存在解析：5.倒排文件的主要优点是( )（分数：2.00）A.便于进行插入和删除运算B.便于进行文件的合并C.能大大提高基于非关键码数据项的查找速度 D.能大大节省存储空间解析：6.在一个链队中，假设 f和 r分别为队首和队尾指针，则删除一个结点的运算是( )（分数：2.00）A.r=fnextB.r=rnextC.f=fnext D.f=rnext解析：7.在一棵完全二叉树的
14、顺序存储方式中，若编号为 t的结点有右孩子，则此结点右孩子的编号为( )（分数：2.00）A.2tB.2t-1C.2t+1 D.t/2解析：8.对采用二分查找法进行查找运算的查找表，要求按( )方式进行存储。（分数：2.00）A.顺序存储B.链式存储C.顺序存储且结点按关键字有序 D.链式存储且结点按关键字有序解析：9.森林 T中有 4棵树，第一、二、三、四棵树的结点个数分别是 n1，n 2，n 3，n 4，那么当把森林 T转换成一棵二叉树后，其根结点的左孩子上有( )个结点。（分数：2.00）A.n1-1 B.n1C.n1+n2+n3D.n2+n3+n4解析：10.对于一个具有 N个结点和
15、E条边的无向图，若采用邻接表示，则表头向量的大小是( )（分数：2.00）A.N B.N+1C.N-ED.N-1解析：11.在一个具有 n个单元的顺序栈中，假设栈底是存储地址的高端，现在我们以 top作为栈顶指针，则作退栈操作时，top 的变化是( )（分数：2.00）A.top=top-1B.top=top+1 C.top不变D.top不确定解析：12.在桶排序中，其平均时间复杂度是( )（分数：2.00）A.O(1)B.O( C.O(n2)D.O(1g解析：13.一个队列的输入序列是 1,2,3,4，则队列的输出序列是( )（分数：2.00）A.4,3,2,1B.1,2,3,4 C.1,4
16、,3,2D.3,2,4,1解析：14.如果以链表作为栈的存储结构，则退栈操作时( )（分数：2.00）A.必须判别栈是否满B.判别栈元素的类型C.必须判别栈是否空 D.对栈不作任何判别解析：15.从一个长度为 n的顺序表中删除第 i个元素(1in)8 寸，需要向前移动( ) A n-i Bn-i+1 Cn-i-1 Di（分数：2.00）A. B.C.D.解析：二、B填空题/B(总题数：10，分数：20.00)16.拓扑排序指的是找一个有向图的 1 的过程。（分数：2.00）填空项 1:_ （正确答案：拓扑序列）解析：17.存储在直接存储器上的顺序文件可以用顺序查找法存取，也可以用_和进行查找。
17、（分数：2.00）填空项 1:_ （正确答案：二分查找法 分块查找）解析：18.在 1 遍历二叉树的序列中，任何结点的子树上的所有结点，都是直接跟在该结点之后。（分数：2.00）填空项 1:_ （正确答案：先序）解析：19.设 N阶方阵 A中的任一元素 aij(1i，jN)，当 i=j或 i+1=j时，a ij0，否则 aij=0， 若将 A按如下方式映象到一维数组 S中 （分数：2.00）填空项 1:_ （正确答案：k=i+(j-i)n）解析：20.在双向链表中，每个结点含有两个指针域，一个指向其_结点，另一个指向_结点。（分数：2.00）填空项 1:_ （正确答案：前趋 后继）解析：21.
18、栈和队列均可视为特殊的线性表，所不同的在于对这二种特殊线性表_和_运算的限定不一样。（分数：2.00）填空项 1:_ （正确答案：插入 删除）解析：22.在串的链式存储结构中，有一个串 S1=“ejidc“，我们假设存储时结点的大小为 1，并设指针占有 4个字节，则链串的存储密度为_，又假设串 S2=“abcdefg“在存储时我们设定结点的大小为 4，指针占有4个字节，则此链串的存储密度为_。（分数：2.00）填空项 1:_ （正确答案：20% 50%）解析：23.给定一个具有 n个元素的向量，建立一个有序单链表的时间复杂度是 1。（分数：2.00）填空项 1:_ （正确答案：O(n 2)）解
19、析：24.稀疏矩阵一般的压缩存储方法有 2种，它们分别是 1 和 2。（分数：2.00）填空项 1:_ （正确答案：三元组十字链表）解析：25.由权值为 1,2,3,4,5,6的六个叶子结点构成一棵哈夫曼树，则带权的路径的长度为 1。（分数：2.00）填空项 1:_ （正确答案：55）解析：三、B解答题/B(总题数：4，分数：20.00)26.对于下面用三元组表示的稀疏矩阵，请分别写出它们所对应的稀疏矩阵。 （分数：5.00）_正确答案：()解析：从三元组表还原稀疏矩阵时，首先根据表的第 1行得出稀疏矩阵的行数和列数，否则，我们无法确定所求的稀疏矩阵的维数，然后根据三元组表所提供的行号和列号在
20、稀疏矩阵的对应位置上写上相应的元素的值，在其他地方补零即可，根据上述原则，此题答案如图(1)，(2)所示。 27.假设有下面所示的稀疏矩阵，请写出其三元组表(按行优先的顺序)。 （分数：5.00）_正确答案：()解析：稀疏矩阵的三元组指的是矩阵中非零元素的行号、列号和其对应的元素，而三元组表就是将其结点是三元组的线性表按照顺序结构进行存储，其表的结构为：(其中 i代表行号，j 代表列号，v 指的是相应的元素值) 5 5 50 1 11 0 31 4 13 2 24 4 128.假设有一个长度为 n的有序序列，在进行查找时，可以借助二叉树来进行，请结合二叉树的性质来分析二分查找的最坏性能和平均性
21、能。（分数：5.00）_正确答案：()解析：假设判定树的内部结点的总数为 n=2h-1。则判定树是深度为 h=lg(n+1)的满二叉树，树中第 k层上的结点的个数为 2h-1，查找它们所需要比较的次数是 k。则在等概率下，二分查找成功时的平均查找长度为：，如果 n很大，则可以用如下近似公式：lg(n+1)-1，作为二分查找成功时的平均查找长度。二分查找在查找失败时所需要比较的关键字的个数不超过判定树的深度，在最坏情况下查找成功的比较次数也不超过判定树的深度。因为判定树中度数小于 2的结点只可能在最下面的两层上，所以 n个结点的判定树的深度和 n个结点的完全二叉树的深度相同，即为 lg(n+1)
22、，所以，二分查找的最坏性能和平均性能十分接近。29.已知一棵二叉树按照顺序结构存储，其存储结构如下： （分数：5.00）_正确答案：()解析：(1)此二叉树如图所示： 四、B算法阅读题/B(总题数：4，分数：20.00)30.以下算法实现若开散列表 HP中无键值为 K的结点，则插入一个这样的结点。请分析程序，并在_上填充合适的语句。 void insert_openhash(keytype K,openhash HP) if(research_openhash(K,HP)=NULL) i=H(K); q=malloc(size);qkey=_; /*生成新结点*/ _=HPi;HPi=_; /
23、*前插法链入新结点*/ （分数：5.00）填空项 1:_ （正确答案：K qnext q）解析：31.以下运算实现在链队上的出队列，请在_处用适当的语句予以填充。 int OutQueue(QueptrTp*lq,DataType*x) LqueueTp*s; if(1qfront=lqrear)error(“队空“);return(0); else s=(lqfront)next; _=sdata; (lqfront)next_; if(snext=NULL)lqrear=lqfront; free(s); return(1); （分数：5.00）填空项 1:_ （正确答案：*x snext
24、）解析：32.以下运算实现在链栈上的进栈，请在_处用适当的语句予以填充。 void Push(LStackTp*ls,DataType x) LStackTp*p;p=malloc(sizeof(LStackTp); _; pnext=ls; _; （分数：5.00）填空项 1:_ （正确答案：pdata=x ls=P）解析：33.以下将 ah，a m，和 am+1an，两个有序序列(它们相应的关键字值满足 KhK m，K m+1K n，)合并成一个有序序列 Rh，R n，(使其关键字值满足 Kh，K n，)。请分析算法，并在_上填充适当的语句。 void merge(list a,list
25、R,int h,int m,int n) i=h;k=h;j=m+1; while(im)_; elseRk=_;_; k+; while(i=_)Rk=ai;i+;k+;) while(j=_)Rk=aj;j+;k+; 此算法的执行时间为_。（分数：5.00）填空项 1:_ （正确答案：ai i+ aj j+ m n P(n-h+1)）解析：五、B算法设计题/B(总题数：1，分数：10.00)34.采用单链表作为存储结构，试编写一个函数来实现用选择排序方法进行升序排列。（分数：10.00）_正确答案：()解析：首先定义单链表的结点： struct node int key; struet node*link; 函数如下: struct*selectsort(struct node*h) struet node*P,*q,*r,*s,*t; t=Null; while(h!=Null) p=h; q=Null; s=h; r=Null; while(P!=Null) if(pkeyskey) s=p; p=q; q=p; p=plink; if(s=h) h=hlink; else h=s; slind=t; t=s; h=t; return(h);
