1、全国自考（数据结构）模拟试卷 7 及答案与解析一、单项选择题1 设有一个用线性探测法解决冲突得到的散列表：散列函数为H(k)=Kmod 11 若要查找元素 14，探测的次数(比较的次数)是（A）8（B） 9（C） 3（D）62 如果二叉树中任何一个结点的值都小于它的左子树上所有结点的值而大于右子树上所有结点的值，要得到各结点值的递增序列，应按下列哪种次序排列结点 ( )（A）先根（B）中根（C）后根（D）层次3 对含有( )个结点的非空二叉树，采用任何一种遍历方式，其结点访问序列均相同。（A）O（B） 1（C） 2（D）不存在这样的二叉树4 含 N 个顶点的连通图中的任意一条简单路径，其长度不
2、可能超过 ( )（A）1（B） N/2（C） N-1（D）N5 顺序存储结构 ( )（A）仅适合于静态查找表的存储（B）仅适合干动态查找表的存储（C）既适合静态又适合动态查找表的存储（D）既不适合静态又不适合动态查找表的存储6 已知一采用开放地址法解决 Hash 表冲突，要从此 Hash 表中删除一个记录，正确的做法是( )（A）将该元素所在的存储单元清空（B）将该元素用一个特殊的元素替代（C）将与该元素有相同 Hash 地址的后继元素顺次前移一个位置（D）用与该无素有相同 Hash 地址的最后插入表中的元素替代7 邻接表存储结构下图的广度优先遍历算法结构类似于树的( )（A）先根遍历（B）后
3、根遍历（C）按层遍历（D）先序遍历8 下列说法中正确的是( )（A）二叉树中任何一个结点的度都为 2（B）二叉树的度为 2（C）任何一棵二叉树中至少有一个结点的度为 2（D）一棵二叉树的度可以小于 29 已知一棵二叉树结点的先根序列为 ABDGCFK，中根序列为 DGBAFCK，则结点的后根序列为( )（A）ACFKBDG（B） GDBFKCA（C） KCFAGDB（D）ABCDFKG10 用二分查找法对具有 n 个结点的线性表查找一个结点所需的平均比较次数为( )（A）O(n 2)（B） O(nlog2n)（C） O(n)（D）O(log 2n)11 与其他查找方法相比，哈希查找法的特点是(
4、 )（A）通过关键字比较进行查找（B）通过关键字计算记录存储地址进行查找（C）通过关键字计算记录存储地址，并进行一定的比较进行查找（D）通过关键字记录数据进行查找12 下列说法正确的是( )（A）树的先根遍历序列与其对应的二叉树的先根遍历序列相同（B）树的先根遍历序列与其对应的二叉树的后根遍历序列相同（C）树的后根遍历序列与其对应的二叉树的先根遍历序列相同（D）树的后根遍历序列与其对应的二叉树的后根遍历序列相同13 设串 s1=ABCDEFG，s2=PQRST，函数 con(x,y)返回 x 和 y 串的连(s,i,j) 返回串s 的从序号 i 的字符开始的 j 个字符组成的子串，len(s)
5、返回串 s 的con(subs(s1，2，len(s2)，subs(s1，len(s2)，2)的结果串是( )（A）BCDEF（B） BCDEFG（C） BCPQRST（D）BCDEFEF14 设二叉树根结点的层次为 0，一棵高度为 h 的满二叉树中的结点个数是( )（A）2 h（B） 2h-1（C） 2h-1（D）2 h+1-115 顺序查找法适用于存储结构为( )的线性表。（A）散列存储（B）压缩存储（C）顺序存储或链接存储（D）索引存储二、填空题16 拓扑排序指的是找一个有向图的_的过程。17 存储在直接存储器上的顺序文件可以用顺序查找法存取，也可以用_和进行查找。18 在_遍历二叉树的
6、序列中，任何结点的子树上的所有结点，都是直接跟在该结点之后。19 设 N 阶方阵 A 中的任一元素 aij(1i，jN)，当 i=j 或 i+1=j 时，a ij0，否则aij=0， 若将 A 按如下方式映象到一维数组 S 中 通过计算公式_可随机地从 S 中取出 A 中任一元素 aij。20 在双向链表中，每个结点含有两个指针域，一个指向其_结点，另一个指向_结点。21 栈和队列均可视为特殊的线性表，所不同的在于对这二种特殊线性表_和_运算的限定不一样。22 在串的链式存储结构中，有一个串 S1=“ejidc“，我们假设存储时结点的大小为1，并设指针占有 4 个字节，则链串的存储密度为_，又
7、假设串 S2=“abcdefg“在存储时我们设定结点的大小为 4，指针占有 4 个字节，则此链串的存储密度为_。23 给定一个具有 n 个元素的向量，建立一个有序单链表的时间复杂度是_。24 稀疏矩阵一般的压缩存储方法有 2 种，它们分别是_和_。25 由权值为 1,2,3,4,5,6 的六个叶子结点构成一棵哈夫曼树，则带权的路径的长度为_。三、解答题26 已知有一关键字序列为(372,81,437,96,205,732,821,634,572,495,264)，如果采用归并排序方法对此序列进行升序排列，请给出每一趟的排序结果。27 假设一棵具有 12 个结点的二叉树的存储结构如下图所示，其中
8、 left 和 right 分别表示此结点左、右孩子的序号，data 表示此结点的数据，根结点为编号为 4 的结点。请根据此存储结构画出对应的二叉树，然后回答下面的问题： (1)写出前序遍历、中序遍历和后序遍历此二叉树时的遍历序列。 (2)求出此树的高度并分析叶结点的个数。 (3)结点 E 的双亲及子孙分别是什么 ?28 在一棵二叉树中，度为 O 的结点个数与度为 2 的结点个数和度数之间有什么关系?在一棵完全二叉树中，如果共有 200 个结点，则能判断出叶结点的个数吗? 如果能，请指出会有多少个叶结点，多少个度为 2 的结点?多少个度为 1 的结点? 如果有201 个结点呢?29 已知有如右
9、图所示的一棵树，请将其转化成二叉树。四、算法阅读题30 以下为单链表的建表算法，分析算法，请在_处填上正确的语句。 lklist create_1klistl() /*通过调用 intiate_lklist 和 insetr_lklist 算法实现的建表算法。假定 $是结束标志*/ ininiate_lklist(head); i=1; scanf(“%“,x); while(x!=$) _; _; scanf(“%f“,x); return(head); 该建表算法的时间复杂性约等于_，其量级为_。31 以下是图的深度优先搜索算法，请在_处填充适当的语句。 Dfs(GraphTp g,int
10、 v) ArcNodeTp*P; printf(“%“,v); visitedv=1; p=_; while(p!=NULL) if(!_)Dfs(g,padjvex); p=_; 32 以下为单链表的插入运算，分析算法，请在_处填上正确的语句。 void insert_lklist(lklist head,datatype x,int i) /*在表 head 的第 i 个位置上插入一个以 x 为值的新结点*/ p=find_lklist(head,i-1); if(p=NULL)error(“不存在第 i 个位置“); elses=_;sdata=x;snext=_; pnext=s; 3
11、3 根据文字说明，请在以下_处填充适当的语句。 采用静态链表作存储结构，设置一个大小为 2n-1 的数组，令数组的每个元素由四个域组成：wt 是结点的权值；lehild、rchild 分别为结点的左、右孩子指针；parent 是结点的双亲在数组中的下标。其数组元素类型定义如下： typedef struet float wt; /*权值*/ int parent,lchild rchild; /*指针域*/ node; typedef node hftree2*n-1; 在这种存储结构上的哈夫曼算法可描述如下： void huffman(int k,float Wk,hftree T) /*求
12、给定权值 W 的哈夫曼树 T*/ int i,j,x,y; float m,n; for(i=0;i 2*k-1;i+) Ti.parent=-1;Ti.lchild=-1;Ti.rchild=-1; if(_)Ti.wt=Wi; else Ti.wt=0 for(i=0;ik-1;i+) x=0;y=0;m=maxint;n=maxint; for(j=0;jk-i,j+) if(Tj.wtm)(Tj.parent=-1)n=m;y=_;m=_;x=j; else if(Tj.wtn)(Tj.parent=-1)n=Tj.wt;y=j;) Tx.parent=_;Ty.parent=_; T
13、k+i.wt=_; Tk+i.lchild=_;Tk+i.rchild=_; 五、算法设计题34 设计一个双向起泡排序算法，即在排序过程中交替改变扫描方向。全国自考（数据结构）模拟试卷 7 答案与解析一、单项选择题1 【正确答案】 D2 【正确答案】 B3 【正确答案】 B4 【正确答案】 C5 【正确答案】 C6 【正确答案】 B7 【正确答案】 C8 【正确答案】 D9 【正确答案】 B10 【正确答案】 D11 【正确答案】 C12 【正确答案】 A13 【正确答案】 D14 【正确答案】 D15 【正确答案】 C二、填空题16 【正确答案】 拓扑序列17 【正确答案】 二分查找法 分块
14、查找18 【正确答案】 先序19 【正确答案】 k=i+(j-i)n20 【正确答案】 前趋 后继21 【正确答案】 插入 删除22 【正确答案】 20% 50%23 【正确答案】 O(n 2)24 【正确答案】 三元组十字链表25 【正确答案】 55三、解答题26 【正确答案】 归并排序的基本思想是：第 l 趟归并排序是，将待排序的文件R1n看作是 n 个长度为 1 的有序子文件，将这些文件两两归并，若 n 是偶数，则得到 n/2 个长度为 2 的有序文件，若 n 为奇数，则最后一个文件轮空，此时得到n/2-1 个有序文件长度为 2，最后一个文件长度为 1，第 2 越是将第 1 趟得到的各个
15、有序子文件进行两两归并。这样依次类推，直到得到一个长度是 n 的有序文件为止。按照上述规则，我们得到各趟归并的结果如下： 初始：372,81,437,96,205,732,21,634,572,495,264 第 1 趟归并后：81,37296,437205,732634,821495,572264 第 2 趟归并后：81,96,372,437205,634,732,821264,495,572 第 3 趟归并后：81,96,205,372,437,634,732,821264,495,572 第 4 趟归并后：81,96,205,264,372,437,495,572,634,732,821
16、27 【正确答案】 在二叉树的链表中，每个结点不仅存放了结点的数值，还存放着指向其左、右孩子的指针，则按照此题中给出的条件，编号为 4 的结点为根结点，即 A 为根结点，然后，再根据 A 的左、右孩子指针所指向的编号，分别找出 A 的左、右孩子为 B，E，然后根据左、右孩子的左右孩子指针域所指向的编号，分别找出左、右孩子的左、右孩子，直到所找到的结点的左、右孩子的指针域都为0 时，则按照以上规则我们得到此二叉树的结构为： (1)此二叉树的前序遍历序列为：ABGEHCFEJLMN 中序遍历序列为：GIBCHFAJCMLN 后序遍历序列为：IGCFHBJMNLEA (2)此树的高度是 4，叶结点的
17、个数为 6。 (3)结点 E 的双亲是 A，它的子孙是 J，L ，M ，N 。28 【正确答案】 在一棵二叉树中，度数为 0 的结点(叶结点)的个数总是比度为 2的结点的个数多 1。根据完全二叉树的定义：若一棵二叉树至多只有最下面的两层上结点的度数可以小于 2，并且最下一层上的结点都集中在该层最左边的若干住置上，则我们可以得出这样一个结论：在一棵完全二叉树上，或者没有度为 1 的结点。则根据以上分析，我们可以这样计算此题：设度数为 2 的结点有 n 个，则必有 n+1个度为 0 的结点，即度数为 2 和度数为 0 的结点数之和为 2n+1(是奇数)，于是得出，如果一棵完全二叉树的结点总数为奇数
18、，则此树中必然不存在度为 1 的结点，若完全二叉树中结点总数为偶数，则必然有 1 个度为 1 的结点存在，于是若完全二叉树中有 200 个结点，就必有 100 个对结点，99 个度数为 2 的结点，12 个度数为 1 的结点，如果二叉树中有 201 个结点，则必有 101 个叶结点，100 个度数为 2 的结点，没有度数为 1 的结点。29 【正确答案】 将一棵树转换成二叉树的规则如下： (1)在所有的兄弟结点之间加一条线； (2)对于每个结点，除了保留与长子的连线外，去掉该结点和其他孩子的连线，则根据以上两个规则，我们得到转换后的二叉树为(从此图我们可以得到，将一棵普通树转换成二叉树后，其对
19、应的二叉树的右子树为空)： 四、算法阅读题30 【正确答案】 insert_lklist(head,x,i) i+ n(n-i)/2 O(n2)31 【正确答案】 g.adjlistv.firstarc visitedpadjvex pnextarc32 【正确答案】 malloc(size) pnext33 【正确答案】 ik x Tj.wt k+i k+i m+n x y五、算法设计题34 【正确答案】 可通过设置一个标志位进行区分的方式来进行交替扫描，算法描述如下： Alterbubblesort(r) /*交替扫描法起泡排序*/ Reetype R; int i,j，temp，flag; /*设置扫描标志 flag*/ flag=True; i=0; while(flag) /*开始扫描*/ flag=False; for(j=n=i,ji,j-) if(Rj,keyRj-1,key) flag=True; temp=Rj; Rj=Rj-1; Rj-1=temp; for(j=l;jn-1;j+) if(Rj.keyRj+1.key) flag=True; temp=Rj; Rj=Ri+1; Rj-1=temp; i+; /*往右扫描*/ /*AIterbubblesort*/
