1、全国自考（数据结构）模拟试卷 10 及答案与解析一、单项选择题1 如图所示二叉树的中序遍历序列是( )（A）a b c d g e f（B） d f e b a g c（C） d b a e f c g（D）d e f b a g c2 长度为 12 的有序表：Apr，Aug ，Dec ，Feb，Jan，Jul，Jun，Mar，May，Nov ，Oct，Sep，按折半查找法对该表进行查找。在表内各元素等概率情况下查找成功所需的平均比较次数为( )（A）35/12 （B） 37/12 （C） 39/12 （D）43/12 3 采用分治法进行排序的方法是( )（A）快速排序（B）插入排序（C）堆排
2、序（D）希尔排序4 下面四种内排序方法中，要求内存容量最大的是( )（A）插入排序（B）选择排序（C）快速排序（D）归并排序5 设深度为 k 的二叉树上只有度为 0 和度为 2 的结点，则这类二叉树上所含结点总数量少( ) 个。（A）k+1（B） 2k（C） 2k-1（D）2k+16 串是一种特殊的线性表，其特殊性体现在( )（A）可顺序存储（B）数据元素是一个字符（C）可链接存储（D）数据元素可以是多个字符7 一个长度为 10 的有序表，按照二分查找法对该表进行查找，在表内各元素等概率的情况下，查找成功所需要的平均比较次数为( )（A）25/10 （B） 27/10 （C） 29/10 （D
3、）31/108 从一个包含 2000 个结点的散列表 A12000中查找结点的平均比较次数 ( )从一个包含 200 个结点的散列表 B1200中查找结点的平均比较次数。（A）大于（B）小于（C）等于（D）不确定9 深度为 k 的二叉树，所含叶子的个数最多为( )（A）2K（B） K（C） 2K-1（D）2K-110 设有 6 个结点的无向图，该图至少应有( )条边才能确保是一个连通图。（A）5（B） 6（C） 7（D）811 对一棵非空二叉树进行中序遍历，则根结点的左边( )（A）只有左子树上的所有结点（B）只有右子树上的所有结点（C）只有左子树上的部分结点（D）只有右子树上的部分结点12
4、索引非顺序文件是指( )（A）主文件无序，索引表有序（B）主文件有序，索引表无序（C）主文件有序，索引表有序（D）主文件无序，索引表无序13 由权值为 4,2,8,7 的四个叶子构成一棵哈夫曼树之后，此树的带权路径的长度为( )（A）21（B） 42（C） 40（D）4414 一棵二叉树满足下列条件：对任一结点，若存在左、右子树，则其值都小于它的左子树上所有结点的值，而大于右子树上所有结点的值。现采用【 】遍历方式就可以得到这棵二叉树所有结点的递增序列。（A）先根（B）中根（C）后根（D）层次15 将含 100 个结点的完全二叉树从根这一层开始，每层从左到右依次对结点编号，根结点的编号为 1。
5、编号为 71 的结点的双亲的编号为( )（A）34（B） 35（C） 36（D）无法确定二、填空题16 从树的根结点到树中的其余结点之间的路径_惟一的。17 一个字符串相等的充要条件是_和_。18 在线性结构中，_决定了它的遍历路线只有一条。19 带有一个头结点的单链表 head 为空的条件是_ 。20 散列文件关键在于选择好的_和_方法。21 ISAM 文件采用_索引结构，而 VSAM 文件采用_索引结构。22 已知广义表 A=(a,b,c)，(d,e,f) ，则运算 head(head(tail(tail(A)=_。23 具有 N 个顶点的无向完全图的边为_，具有 N 个顶点无向完全图的弧
6、为_。24 设树 T 的度为 4，其中度为 1、2、3 和 4 的结点个数分别是 4、2、1 和 1，则T 中叶子结点的个数是：_。25 任意一棵具有 n 个结点的二叉树，若它有 m 个叶子，则该二叉树上度数为 1 的结点为_个。三、解答题26 设某文件有 14 个记录，其关键字分别为25,75,125,93,241,203,19,198,121,173,218，80，214，329 。桶的容量 M=3，此时采用除留余数法构造散列函数，且散列函数为 h(k)=k%5，画出该散列文件的结构图，并说明如何对其进行删除或插入、检索等操作。27 对如图所示的有向图 G，请给出其广度优先遍历序列，并画其
7、 DFS 子树(以 A为源点)。28 已知：S=XYZ*+ T=(X+Z)*Y，试利用串的各种基本运算将 S 转换为 T。29 令 s=aaab，t=abcabaa，u=abcaabbabcabaacbacba，分别求出它们的 next 值。四、算法阅读题30 以下运算实现在循环队上的入队列，请在_处用适当的语句予以填充。 int EnCycQueue(CycquetaeTp*sq,DataType x) if(sqrear+1)%maxsize=_) error(“队满“);return(0);) else_; _; return(1); 31 以下程序段采用先根遍历方法求二叉树的叶子数，请
8、在_处填充适当的语句。 void countleaf(bitreptr t,int*count)/*根指针为 t，假定叶子数 count 的初值为 0*/ if(t!=NULL) if(tlchild=NULL)(trchild=NULL)_; countleaf(1lehild,count); _; 32 以下为冒泡排序的算法。请分析算法，并在_处用适当的语句予以填充。 void bubblesort(int n,list r) /*fiag 为特征位，定义为布尔型*/ for(i=1;i =_，i+) _; for(j=1;j=_;j+) if(rj+1.keyrj.key)flag=0;
9、p=rj;rj=rj+1;rj+1=P; if(flag)return; 33 基于三元组的稀疏矩阵转置的处理方法有两种，以下运算按照矩阵 A 的三元组a.data 的次序进行转置(快速转置)，请在_处用适当的语句予以填充。 Fast_Trans_Sparmat(SpMatrixTp a,SpMatrixTp*b) (*b)mu=a.nu;(*b).nu=a.mu;(*b).tu=a.tu; if(a.tu) for(col)=1;_col+)unmcol=0 for(t=1;t =a.tu;t+)numa.datat.j+; cpot1=1; for(col=2;col=a.nu;col+)
10、cpotcol=_; for(p=1;p=a.tu;p+) col=a.datap.j; q=cpotcol; (*b).dataq.i=adatap.j; (*b).dataq.j=a.datap.i; (*b).dataq.v=a.datap.v; _; 五、算法设计题34 对一个有 t 个非零值元素的 mn 矩阵，用 B0t,13的数组来表示，其中第 0行的三个元素分别是 m,n,t，从第一行开始到最后一行，每行表示一个非零元素，第一列为矩阵元素行号，第二列为其列号，第三列为其元素量，对这样的表示法，试编写一个算法确定任意一个元素 Aij的位置，并考虑若修改其元素值须用多少时间?(设 B
11、 中第 1 列原行号是递增的 )全国自考（数据结构）模拟试卷 10 答案与解析一、单项选择题1 【正确答案】 C2 【正确答案】 B3 【正确答案】 A4 【正确答案】 D5 【正确答案】 C6 【正确答案】 B7 【正确答案】 C8 【正确答案】 D9 【正确答案】 C10 【正确答案】 A11 【正确答案】 A12 【正确答案】 A13 【正确答案】 C14 【正确答案】 B15 【正确答案】 B二、填空题16 【正确答案】 是17 【正确答案】 两个字符串的长度相等 对应位置的字符相等18 【正确答案】 线性结构中后继的惟一性19 【正确答案】 Jaead next=NULL20 【正确
12、答案】 散列函数 冲突处理21 【正确答案】 静态 动态22 【正确答案】 e23 【正确答案】 n(n-1)/2 n(n-1)24 【正确答案】 8 个25 【正确答案】 n-2m+1三、解答题26 【正确答案】 由于散列函数 h(k)=k%5，从而可得按散列函数方法组织的文件结构如下(可选桶数为(14/3)(1+10%)=5) ； 当需对该散列文件中的记录进行检索时，可首先根据给定记录的关键字值，用散列函数求出其对应的散列地址，此地址即为桶的编号，然后按照散列表中第 i 项给出的地址把该桶中的所有记录读入内存，并对这些记录进行顺序检索。若找到说明检索成功，否则，若该桶不满或其指针域为空，说
13、明检索失败。此时若其指针域不空，则该指针把第一个溢出桶的记录读入内存，继续检索直到检索成功或失败时为止。 27 【正确答案】 图的广度优先遍历类似于树的按层遍历：首先访问源点，并将其记为访问过，接着访问 vi 的所有未被访问的邻接点 vi1，vi2，vit。并将它们均记为已经访问过，然后再按照 vi1，vi2，vit 的次序，访问每个顶点的所有未被访问的邻接点，并均记它们为已访问过，按此规则类推，直到图中所有和源点vi 有路径相通的顶点都访问过为止。则按照广度优先遍历规则，我们得到此遍历序列为 ABCDEFGHI。相应的子树为：28 【正确答案】 STR1=REPLACE(SUBSTR(S,1
14、,1)，X，(X) STR1=(X STR2=CONCAT(STRl SUBSTR(S,5,1) STR2=(X+1) STR3=REPLACE(SUBSTR(S,3,1)，Z，Z) STR3=Z) STR4=CONCAT(STR2,STR3) STR4=(X+Z) STR5=CONCAT(STR4,SUBSTR(S,4,1) STR5=(X+Z)* 29 【正确答案】 当位置 j=1 时，nextj=0；当位置 j1 时，nextj的值为模式串的位置 1 到 j-1 构成的串中所出现的首尾相同的子串的最大长度加 l，无首尾相同的子串时 nextj的值为 1。本题答案如下表所示： 四、算法阅读
15、题30 【正确答案】 sqfront sqrear=(sqrear+1)%maxsize sqdatasq rear=x31 【正确答案】 *count+ eountleaf(1 rehild,count)32 【正确答案】 n-1 flag-1 n-i33 【正确答案】 col=a.nu cpotcol-1+numcol-1 cpotcol+五、算法设计题34 【正确答案】 分析题意可得其算法思想为： 首先可在数组 B 中找到相应的行，然后找到相应的列，即可修改其元素值，可假定要修改的 Aij，原先就具有非零值。从而可将算法描述为： lorte(B,t,i,j,v) /*确定任意一个元素 A
16、ij的位置*/ datatype B;/*B 的杆标为 0t 和 13*/ int t,i,j; float v; datatype A; /*A 的下标为 1m 和 1n，A 表示 mn 矩阵*/ int p; p=1; while(Bp1!=1)(p=t) P+; if(pt)printf Chasnt element foundn“); else while(Bp1=i)*(p=t) if(Bp1=i) else printf (“no element foundn“); /*lorte*| 显然，在本算法中可能出现的最坏情况：一是需要修改的元素位于 B 中最后一行；二是 Bij先的元素值为零，而无法在 B 中查找到相应的位置。所以，在这两种情况下的时间复杂度为 0(t)。
