1、全国自考（数据结构）模拟试卷 5 及答案与解析一、单项选择题1 内部排序的方法有许多种，( )方法是从未排序序列中依次取出元素，与已排序序列中的元素作比较，将其放入已排序序列的正确位置上。（A）归并排序（B）插入排序（C）快速排序（D）选择排序2 散列表的目的是( )（A）插入（B）删除（C）快速查找（D）排序3 设数组 data0m作为循环队列 SQ 的存储空间， front 为队头指针，rear 为队尾指针，则执行出队操作的语句为( )（A）front:=front+1（B） front:=(front+1)mod m（C） rear:=(rear+1)mod m（D）front:=(fr
2、ont+1)mod(m+1)4 在一个长度为 n 的顺序表(顺序存储的线性表)中，向第 i 个元素(1in+1) 之前插入一个新元素时，需向后移动( )个元素。（A）n-i（B） n-i+1（C） n-i-1（D）i5 线性表 L=(a1，a 2，a 1，a n)，下列说法正确的是 ( )（A）每个元素都有一个直接前趋和直接后继（B）线性表中至少要有一个元素（C）表中诸元素的排列顺序必须是由小到大或由大到小的（D）除第一个元素和最后一个元素外，其余每个元素都有一个且仅有一个直接前趋和直接后继6 在下图中，从顶点 V1 出发，按广度优选遍历图的顶点序列是 ( )（A）V 1 V5 V3 V4 V
3、2 V6 V7（B） V1 V5 V3 V4 V2 V7 V6 （C） V1 V7 V2 V6 V4 V5 V3 （D）V 1 V2 V4 V7 V6 V5 V3 7 在 Hash 函数 H(k)=k MOD m 中，一般来讲，m 应取( )（A）奇数（B）偶数（C）素数（D）充分大的数8 如果我们采用二分查找法查找一个长度为 n 的有序表，则查找每个元素的平均比较次数( ) 对应的判定树的高度(假设树高 h2)。（A）大于（B）小于（C）等于（D）无法确定9 对于一个具有 N 个顶点的图，如果我们采用邻接矩阵法表示，则此矩阵的维数应该是( )（A）(N-1)(N-1)（B） NN（C） (N
4、+1)(N+1)（D）不确定10 快速排序在最坏情况下的时间复杂度是( )（A）O(nlogn)（B） O(n2)（C） O(n3)（D）都不对11 向一个栈顶指针为 Top 的链栈中插入一个 s 所指结点时，其操作步骤为( )（A）Top next=s;（B） snext=Topnext;Top next=s;（C） snext=Top;top=s;（D）snext=Top; Top=Topnext;12 树最适合用来表示( )（A）有序数据元素（B）无序数据元素（C）元素之间具有分支层次关系的数据（D）元素之间无联系的数据13 设有一个无向图 G=(V,E)和 G=(V,E)，如果 G是
5、G 的生成树，则下面不正确的说法是( )（A）G为 G 的子图（B） G为 G 的连通分量（C） G为 G 的极小连通子图且 V=V（D）G是 G 的一个无环子图14 实现任意二叉树的后序遍历的非递归算法而不使用栈结构，最佳方案是二叉树采用( )存储结构。（A）二叉链表（B）广义表（C）三叉链表（D）顺序15 下面四种排序方法中，平均查找长度最小的是( )（A）插入排序（B）选择排序（C）快速排序（D）归并排序二、填空题16 对快速排序来讲，其最好情况下的时间复杂度是_，其最坏情况下的时间复杂度是_。17 假设在线索二叉树中，结点的标志域的值为 0 时，表示其指针域是指向孩子的指针，当结点的标
6、志域为 1 时，表示其指针域是指向前趋或者后继的线索，则一个结点是叶结点的充要条件是_。18 散列函数的作用是：_。19 内部排序的方法可以分为五类：_、_、_、_、_。20 树的结点数目至少为_，二叉树的结点数目至少为_。21 在结点数目相同的二叉树中，_的路径长度最短。22 从一个顺序存储的循环队列中删除一个元素时，应该_。23 对于数组，通常具有的基本操作有_种，它们分别是_。24 设有两个散列函数 H1(k)=k mod 13 和 H2(k)=k mod 11+1，散列表为 T012，用双重散列解决冲突。函数 H1 用来计算散列地址，当发生冲突时， H2 作为计算下一个探测地址的地址增
7、量，假定在某一时刻表 T 的状态为 下一个被插入的关键码是 42，其插入的位置是：_。25 无向图的邻接矩阵是_，并且主对角线上的元素的值为_。三、解答题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，请给出该散列文件的表示方法。27 已知下面的一个图，请根据普里姆算法构出它的一棵最小
8、生成的树。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)树的度数是多少 ?29 对于如图所示的二叉树，请画出其顺序存储
9、结构图。四、算法阅读题30 以下算法实现若开散列表 HP 中无键值为 K 的结点，则插入一个这样的结点。请分析程序，并在_上填充合适的语句。 void insert_openhash(keytype K,openhash HP) if(research_openhash(K,HP)=NULL) i=H(K); q=malloc(size);q key=_; /*生成新结点 */_=HPi;HPi=_; /*前插法链入新结点 */ 31 以下运算实现在链队上的出队列，请在_处用适当的语句予以填充。 int OutQueue(QueptrTp*lq,DataType*x) LqueueTp*s;
10、if(1q front=lqrear)error(“队空“);return(0); else s=(lqfront)next; _=sdata; (lqfront)next_; if(snext=NULL)lqrear=lq front; free(s); return(1); 32 以下运算实现在链栈上的进栈，请在_处用适当的语句予以填充。 void Push(LStackTp*ls,DataType x) LStackTp*p;p=malloc(sizeof(LStackTp); _; pnext=ls; _; 33 以下将 ah， am，和 am+1an，两个有序序列(它们相应的关键字值
11、满足KhKm，K m+1K n，)合并成一个有序序列 Rh，R n，(使其关键字值满足Kh，K n，)。请分析算法，并在_上填充适当的语句。 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+; 此算法的执行时间为_。五、算法设计题34 有两个磁盘文件 A、B，各存放一行字母，要求把这两个文件中的信息按字母顺序排列合并，输出到一个新文件 C 中。全国自考（数据结构）模拟试卷 5 答案
12、与解析一、单项选择题1 【正确答案】 B2 【正确答案】 C3 【正确答案】 D4 【正确答案】 B5 【正确答案】 D6 【正确答案】 A7 【正确答案】 C8 【正确答案】 B9 【正确答案】 B10 【正确答案】 B11 【正确答案】 C12 【正确答案】 C13 【正确答案】 B14 【正确答案】 C15 【正确答案】 C二、填空题16 【正确答案】 O(nlog 2n) O(n2)17 【正确答案】 结点的左右标志都是 118 【正确答案】 压缩待处理的下标范围，待处理的|u|个值减少到 m 个值，从而降低空间开销19 【正确答案】 插入排序 选择排序 交换排序 归并排序 分配排序2
13、0 【正确答案】 1 021 【正确答案】 完全二叉树22 【正确答案】 先移动队首指针，后取出元素23 【正确答案】 两 查找和修改24 【正确答案】 位置为 025 【正确答案】 对称零三、解答题26 【正确答案】 磁盘上的文件记录通常是成组存放的，若干个记录组成一个存储单位，在散列文件中，这个存储单位叫做桶。 如果一个桶能放 m 个记录，则如果现在已经存放了 m 个记录时，继续存放记录就会产生“溢出 ”，当发生 “溢出”时，一般采用拉链法，就是将第 m+1 个同义词存放在另外_个桶中，通常此桶就称为“溢出桶” ，相应的前 m 个同义词存放的桶就称为是“基桶”，溢出桶和基桶大小相同。 根据
14、散列函数，得到对应的关键字的散列地址为：2,4,6,4,5,2,3,5,4,5,5,2,3,4,0,4,1,6，则得到的散列文件表示如下27 【正确答案】 构造最小生成树的过程如下：28 【正确答案】 树的结构如下图所示： (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 【正确答案】 二叉树的顺序存储就是将二叉树的结点按编号存在向量 B0,n中，其中 B0用来存放结点 T 数，如果树
15、中某些编号对应的结点不存在，则对应存储空间为“空”，根据上述规则，我们得到：四、算法阅读题30 【正确答案】 K qnext q31 【正确答案】 *x snext32 【正确答案】 pdata=x ls=P33 【正确答案】 ai i+ aj j+ m n P(n-h+1)五、算法设计题34 【正确答案】 可先分别将 A、B 文件的内容读出放到数组 C 中，再对数组 C 排序，最后再将数组内容写到文件 C 中，程序为： #includestdio.h main() /*合并 A、B 文件内容到 C 文件中*/ FILE*fp; int i,j,n,m; char c160,t,ch; if(
16、fp=fopen(“A“,“r“)=Null) printf(“文件 A cant openn“); exit(0); else printf(“n 文件 A 的内容为n“) for(i=0;(ch=fgetc(fp)!=EOF:i+) Ci=oh; putchar(C-i); fclose(fp); m=i; if(fp=fopen(“B“,“r“)=Null) printf(“B 文件 cant openn“); exit(0); else printf(“nB 文件内容是n“); for(i=m;(ch=fgetc(fp)!=EOF;i+) Ci=ch; putchar(i); fclose(fp); n=i;/*排序 */ for(i=0;in;i+) for(j=i+1;jm,j+) if(Cicj) t=ci; ci=cj; cj=t; printf(“nC 文件是n“); fp=fopen(“c“,“w“) /* 写入 C 文件中*/ for(i=0;im;i+) putchar(ci,fp); putchar(ci); fclose(fp); /*main*/
