1、全国自考（数据结构）模拟试卷 9 及答案与解析一、单项选择题1 堆排序的最坏时间复杂度为( )（A）O(n)（B） O(10g2n)（C） O(nlog2n)（D）O(n 2)2 对广义表(a) ，(b)进行下面的操作 head(head(a)，(b)后的结果是( )（A）a（B） (a)（C） ( )（D）不确定3 已知某二叉树的后序遍历序列是 dabec，中序遍历序列是 debac，则它的前序遍历序列是 ( )（A）a c b e d（B） d e c a b（C） d e a b c（D）c e d b a4 判断一个有向图是否存在回路，除了可以利用拓扑排序方法，还可以利用( )（A）求
2、关键路径的方法（B）求最短路径的 Dijkstra 方法（C）广度优先遍历方法（D）深度优先遍历方法5 将含有 83 个结点的完全二叉树从根结点开始编号，根为 1 号，后面按从上到下、从左到右的顺序对结点编号，那么编号为 41 的结点的双亲结点编号为( )（A）42（B） 40（C） 21（D）206 设数组 A0,m作为循环队列 sq 的存储空间，front 为队头指针，rear 为队尾指针，则执行入队操作的语句是( )（A）sq.front=(sq.front+1)%m（B） sq.front=(sq.front+1)%(m+1)（C） sq.rear=(sq.rear+1)%m（D）sq
3、.rear=(sq.rear+1)%(m+1)7 如果 T2 是由有序树 T 转换而来的二叉树，那么 T 中结点的后序就是 T2 中结点的( )（A）前序（B）中序（C）后序（D）层次序8 链栈与顺序栈相比，有一个比较明显的优点即( )（A）插入操作更加方便（B）通常不会出现栈满的情况（C）不会出现栈空的情况（D）删除操作更加方便9 串是任意有限个( )（A）符号构成的集合（B）符号构成的序列（C）字符构成的集合（D）字符构成的序列10 堆是一个键值序列(k 1，k 2，k，k 1，k 0)，对 i=1，2，n/2 ，满足( )（A）k ik2ik2i+1（B） kik 2ik 2i+1（C）
4、 kik2i 且 kk2i+1(2i+1n)（D）k ik2i 或 kik2i+l(2i+1n)11 带头结点的单链表 Head 为空的判定条件是( )（A）Head=NULL;（B） Head.next=NULL;（C） Head.nextHead;（D）Head.next=Head12 如果待排序的记录的规模很大，则在下面的排序方式中，我们最好不要选择使用 ( )（A）快速排序（B）直接插入排序（C）堆排序（D）归并排序13 串是一种特殊的线性表，其特殊性体现在( )（A）可以顺序存储（B）数据元素是一个字符（C）可以链接存储（D）数据元素可以是多个字符14 线性表若采用链表存储结构时，要
5、求内存中可用存储单元的地址( )（A）必须是连续的（B）部分地址必须是连续的（C）一定是不连续的（D）连续不连续都可以15 假设有一个数组，它的行号从 0 到 8，列号从 0 到 10，数组中每个元素所占的存储空间为 3 个单元，则现在将此数组从某一个地址开始连续存放在一个存储器中，试问至少需要( ) 个存储单元才能完全将此数组存放进去。（A）240（B） 297（C） 270（D）300二、填空题16 在索引顺序文件中需建立一张指示逻辑记录和物理记录之间的一一对应关系的_。它通常采用_结构来组织。17 数组 A110，-26 ，28 以行优先顺序存储，设第一个元素的首地址是 100，每个元素
6、占 3 个存储长度的存储空间，则元素 A5,0,7的存储地址为_。18 对磁带上的顺序文件进行更新某个记录时，必须_整个文件。而在顺序文件的最后添加新的记录时，则不必_整个文件。19 若二叉树的一个叶子是某子树的中序遍历序列中的第一个结点，则它必是孩子树的后序遍历序中的_个结点。20 文件的记录均存放在数据集中，数据集中的一个结点称为_，它是一个_操作的基本单位。21 设线性表 L=(a1，a 2，a n)(n2)，表中元素按值的递增顺序排列。对一个给定的值 k，分别用顺序检索和二分法检索查找与 k 相等的元素，比较次数分别为 s和 b，若检索不成功，则 s 和 b 的数量关系是_ 。22 在
7、按照顺序存储方式存储的数组中，元素 aij 的存储地址应该是数组的 _加上排在 aij 前面的元素所占用的单元数。23 _查找法的平均查找长度与元素个数 n 无关。24 在计算机软件系统中，有两种处理字符串长度的方法：一种是采用_，第二种是设置_。25 在顺序队列中，应该有队头和队尾两个指针来指示，队头指针和队尾指针的初值在队列的初始化时均应该设置为_，当对队列进行插入和删除的操作后，如果头指针和尾指针相等时，队列为_。三、解答题26 已知一棵二叉树的前序遍历序列是 ABDGCEFH，其中序遍历序列为DGBAECHF。请画出相应的二叉树，并求出对应此二叉树的后序遍历序列，此二叉树是完全二叉树吗
8、? 完全二叉树有什么性质 (特点 )?27 已知有一关键字序列为97,86,53,108,72,34,215,146,11,68 ，如果我们采用直接选择排序方法对此序列进行排序(按照升序排列)，请给出每一趟的排序结果。28 请根据下面所给出的邻接矩阵画出相应的有向图或者是无向图(顶点 vi 表示)。28 判别下列二序列是否为堆，如不是，按照对序列建堆的思想把它调整为堆，用图表示建堆的过程。29 (1,5,7,25,21,8,8,42)30 (3,9,5,8,4,17,21,6)四、算法阅读题31 以下算法假定以线性探测法解决冲突，在闭散列表 HL 中查找键值为 K 的结点，成功时回送该位置；不
9、成功时回送标志-1。请分析程序，并在_上填充合适的语句。 int search_closehash(keyt,ype K,closehash HL) d=H(K); /*计算散列地址 */ i=d; while(HLi.key!=K(i!=d-1)i=_;)/*未成功且未查遍整个 HL 时继 续扫描*/ if(_)return(i); /*查找成功*/ else return(-1); /*查找失败*/ 32 以下为单链表的删除运算，分析算法，请在_处填上正确的语句。 void delete_lklist(1klist head,int i) p=find_lklist(head,i-1)；
10、if(_) q=_; pnext=qnext; free(q); else error(“不存在第 i 个结点“) 33 以下为顺序表的定位运算，分析算法，请在_处用正确的语句予以填充。 int locate_sqlist(sqlist L,datatype X) /*在顺序表 L 中查找第一个值等于 X 的结点。若找到回传该结点序号；否则回传0*/_； while(iL.last)(L.datai-1!=x)i+; if(_)return(i); else return(0); 34 以下为单链表的建表算法，分析算法，请在_处填上正确的语句。 lklist create_iklist2()
11、/*直接实现的建表算法。*/ head=malloc(size); p=head; scanf(“%“,x); while(X!=$) q=malloc(size); qdata=x; pnext=q; _; scanf(“%“,x); _; return(head); 此算法的量级为_。五、算法设计题35 假设在表示一棵二叉树的二叉链表上增加两个域，双亲域用于指示其双亲结点，标志域 flag(可取，02)的值，用以区分在遍历过程中到达该结点时继续向左或向右或访问该结点。试以此存储结构编写不用栈进行后序遍历的递推形式的算法。全国自考（数据结构）模拟试卷 9 答案与解析一、单项选择题1 【正确答
12、案】 C2 【正确答案】 A3 【正确答案】 D4 【正确答案】 D5 【正确答案】 D6 【正确答案】 D7 【正确答案】 B8 【正确答案】 B9 【正确答案】 D10 【正确答案】 C11 【正确答案】 B12 【正确答案】 B13 【正确答案】 B14 【正确答案】 D15 【正确答案】 B二、填空题16 【正确答案】 索引 表树17 【正确答案】 91318 【正确答案】 复制 复制19 【正确答案】 第一20 【正确答案】 控制区间 I/021 【正确答案】 sb22 【正确答案】 基地址23 【正确答案】 散列表24 【正确答案】 固定长度 长度指针25 【正确答案】 0 空三、
13、解答题26 【正确答案】 根据二叉树的遍历规则，前序遍历总是先访问根结点，然后依次遍历其左右子树，而中序遍历规则是先遍历左子树，再访问根结点，然后访问右子树，则由以上规则，我们极易得出此二叉树的根结点是 A，中序遍历序列中，根结点左右两边的结果分别属于其左、右子树，所以得出左子树包含 3 个节点：B，D，G，右子树包含四个结点 C，E，F，H。在左子树中，先序遍历序 B 位于最前，而中序遍历序列中，B 位于最后，则可以得出结点 B 无右子树，只有左子树，又在 B 的子树中，无论先序遍历还是中序遍历，D 都位于 G 的前面，则 G 只能是 D 的右孩子，且 D 无左孩子，27 【正确答案】 直接
14、选择排序的过程为：从第 i 趟开始时，当前的有序区和无序区分别为 R1i和 R1n(1-1n-1)，则在该趟排序是从当前无序区中选出关键字最小的记录 RK，将它与无序区中的第 1 个记录 Ri交换，使 R1i和Ri+1n分别变成新的有序区和新的无序区，每次排序都使有序区增加一个记录，无序区减少一个记录，按照以上规则，我们得到各趟结果如下：初始：97,86,53,108,72,34,215,232,11,68 第 1 趟：1186,53,108,72,34,215,23228 【正确答案】 A，B，C 对应的图分别为：29 【正确答案】 为堆；30 【正确答案】 不是堆，调整为堆的过程如下图所示：四、算法阅读题31 【正确答案】 (i+1)/m HLi.key=K32 【正确答案】 (p!=NULL) P=t; while(p!=Null) switch( flag) case 0:pflag=1; if(plchild!=Null) p=plehild; break; case 1:pflag=2 if(jprchild!=Null) p=prchild; break; case 2:pflag=0; printf(pdata); p=jpparent; break; default; /*postorder*/
