1、全国自考（数据结构）模拟试卷 3 及答案与解析一、单项选择题1 设有两个串 p 和 q，求 q 在 p 中首次出现的位置的运算称为( )（A）连接（B）模式匹配（C）求子串（D）求串长2 对于 shell 排序来说，给定的一组排序数值为 49,38,65,97,13,27,49,55,04 则第二趟排序后的结果为( )（A）04,13,27,49,49,38,55,65,76,97（B） 04,13,27,38,49,49,55,65,76,97（C） 13,04,49,38,27,49,55,65,97,76（D）13,27,49,55,04,49,38,65,97,763 将上万个一组无序
2、并且互不相等的正整数序列，存放于顺序存储结构中，采用( )方法能够最快地找出其中最大的正整数。（A）快速排序（B）插入排序（C）选择排序（D）归并排序4 长度为 12 的按关键字有序的查找表采用顺序组织方式。若采用二分查找方法，则在等概率情况下，查找失败时的 ASL 值是( )（A）13850（B） 62/13（C） 14580（D）49/135 一个具有 N 个顶点的有向图最多有( )条边。（A）N(N-1)/2（B） N(N-1)（C） N(N+1)（D）N(N+1)/26 Aarr 和 Barr 两个数组的说明如下： VAR Aarr:ArrayO7of char; Barr:Array
3、-52,3,8of char; 这两个数组分别能存放的字符的最大个数是( )（A）7 和 35（B） 1 和 5（C） 8 和 48（D）1 和 67 对于一棵具有三个结点的二叉树，共有( )种不同的树的形态。（A）4（B） 5（C） 6（D）78 设一个数组中，行下标 i 的范围是从 1 到 8，列下标的范围是从 1 到 10，假设此数组的初始存储地址是 A，则如果将此数组按照列优先的顺序连续存放，则元素Q58的起始地址是( )（A）1（B） 23（C） 24（D）5299 具有 24 个记录的序列，采用冒泡排序最少的比较次数是( )（A）1（B） 23（C） 24（D）52910 下列说法
4、中正确的是( )（A）任何一棵二叉树中至少有一个结点的度为 2（B）任何一棵二叉树中的每个结点的度为 2（C）任何一棵二叉树中的度肯定等于 2（D）任何一棵二叉树中的度可以小于 211 二分查找算法要求被查找的表是( )（A）键值有序的链表（B）键值不一定有序的链表（C）键值有序的顺序表（D）键值不一定有序的顺序表12 下面的程序在执行时，S 语句共被执行了( )次。 i=1; while(i=n) for(j=i;jn;j+) S ; i=i+1; （A）i=n;i+) for(j=1;j=m;j+) Aij=i*j; （A）O(m 2)（B） O(n2)（C） O(m*n)（D）O(m+n
5、)15 与数据元素本身的形式、内容、相对位置、个数无关的是数据的( )（A）存储结构（B）存储实现（C）逻辑结构（D）运算实现二、填空题16 对无向图，其邻接矩阵是一个关于_对称的矩阵。17 多维数组和广义表是一种非常复杂的非线性结构，它们的逻辑特点是_。18 18.已知 L 是无表头结点的单链表，且 P 结点既不是首元结点，也不是尾元结点，试从下列提供的答案中选择合适的语句序列。 (1)在 P 结点之前插入 S 结点的语句序列是_； (2)在表首插入 S 结点的语句序列是_。 a Pnex=S b Pnext=Pnext next c Pnext=S next d Snext=P next
6、e Snext=L f Q=P g while(Pnext!=QP=Pnext h while(Pnext!=NULL)P=Pnext i P=L j L=S19 在散列技术中，处理冲突的方法有：_和_。20 如果我们定义一个长度为 N 的串空间，则它最多能放 _个字符。21 假设在图 G 中任意的顶点设为 vi，此顶点对应的度为 D(vi)，此图的顶点数为n。则边数 e 和度数之间的关系为 _。22 _的邻接矩阵不一定是不对称的。23 在串的匹配运算中，一般我们将主串称为_，而将子串称为_。24 当所有结点的权值都相等时，用这些结点构造的二叉排序树上只有_。25 N 个顶点的连通图，至少有_
7、条边。三、解答题26 已知有一个关键字序列为(99,38,309,08,27,145,67,96,186,122,71,63,59)，假设用散列函数为 h(key)=key%13，现在如果采用拉链法解决冲突问题，请画出这组关键字的散列表。27 已知有一关键字序列为486,79,596,34,900,120,789,179,703,307) ，如果我们采用基数排序方法对此序列进行排序(按照升序排列)，请给出每一趟的排序结果。28 写出二分查找的递归算法。29 已知连通图如下： 分别以邻接矩阵的邻接表实现存储，试给出该图的邻接矩阵和邻接表，若从顶点 B 出发对该图进行遍历，分别给出一个按深度优先搜
8、索和广度优先搜索的顶点序列。四、算法阅读题30 以下运算实现在链队上的入队列，请在_处用适当的语句予以填充。 void EnQueue(QueptrTp*lq,DataType x) LqueueTp*P; p=(LqueueTp*)malloc(sizeof(LqueueTp); _=x; pnext=NULL; (1qrear)next=_; _; 31 以下运算实现在链栈上的初始化，请在_处用适当的语句予以填充。 void InitStack(LStackTp*ls)_;)32 以下算法在指针 T 所指的二叉排序树上的查找键值等于 K 的结点。成功时回送指向该结点的指针；否则回送空指针。
9、请分析程序，并在_上填充合适的语句。bitreptr search_bst(bitreptr T,keytype K) if(T=NULL)return(NULL); else switch case Tkey=K:_; case_: return(search_bst(Tlchild,K); case_: return(search_bst(Trchild,K); 33 以下为顺序表的插入运算，分析算法，请在_处填上正确的语句。 void insert_sqlist(sqlist L,datatype x,int i)*将 X 插人到顺序表 L 的第 i-1 个位置* if(L.1ast=m
10、axsize)error(“表满“); if(i1)|(iL.last+1)error(“非法位置“); for(j=L.last;ji;j-) L.datai-=X; L.last=L.last+1; 五、算法设计题34 写出向某个有序文件中插入一个记录的程序。全国自考（数据结构）模拟试卷 3 答案与解析一、单项选择题1 【正确答案】 B2 【正确答案】 C3 【正确答案】 C4 【正确答案】 B5 【正确答案】 B6 【正确答案】 C7 【正确答案】 B8 【正确答案】 C9 【正确答案】 B10 【正确答案】 D11 【正确答案】 C12 【正确答案】 A13 【正确答案】 B14 【正
11、确答案】 C15 【正确答案】 C二、填空题16 【正确答案】 主对角线17 【正确答案】 一个数据元素可能有多个直接前趋和多个直接后继18 【正确答案】 figda e j19 【正确答案】 开放定址法 拉链法20 【正确答案】 N121 【正确答案】 22 【正确答案】 有向图23 【正确答案】 目标串 模式串24 【正确答案】 右子树25 【正确答案】 N1三、解答题26 【正确答案】 采用散列函数为：h(key)=key%13，得到对应的上述关键字序列的散列地址为(8,2,10,8,1,2,2,5,4,5,6,11,7)，用拉链法解决冲突的问题时，就是将所有关键字为同义词的结点连接在同
12、一个单链表中，且当把 h(key)=i 的关键字插入到第i 个单链表中时，既可以插入到单链表的头上，也可以插入到链袁的尾上。根据上述规则，我们可以得到此序列的散列表形式如下图。27 【正确答案】 基数排序的基本思想是：从低位到高位依次对 kj(j=d-1，d-20)进行箱排序，根据基数排序法的基本方法，我们得到如下的排序结果： 初始：486,79,596,34,900,120,789,179,703,307 第 1 趟：(按个位进行排序)：120,900,703,34,486,596,307,79,179,389 第 2 趟：(按十位进行排序)：307,703,900,120,34,79,17
13、9,486,789,596 第 3 趟：(按百位进行排序)：34,79,120,17928 【正确答案】 int binlist(datatype an;int s,t;datatype x) /*n 为元素个数，s ，t 分别为查找区间的上、下界*/ if(St)return(0); /*查找失败*/ else mid=(s+t)/2; switch(mid)of xamid:return(binlist(a,s,mid-1,x); /*在低端区间上递归*/ x=amid:retur29 【正确答案】 深度优先搜索顶点序列为： b a d f e c 广度优先搜索顶点序列为： b a c e
14、 d f四、算法阅读题30 【正确答案】 pdata P lqrear=p31 【正确答案】 ls=NULL32 【正确答案】 return(T) T keyK TkeyK33 【正确答案】 L.dataj=L.dataj-1五、算法设计题34 【正确答案】 所谓有序文件是指文件的记录按关键字由小到大(或由大到小)顺序存放。为方便起见，可设文件的每一个记录是一个整数，文件上数据是按由小到大顺序存放。设插入数据是命令行的第 3 个参数，且设为 d。若原文件中没有数据，则 d 写入文件；若有数据，则找到第 1 个比 d 大的数据 i，先写入 d，再将 i 和其后各数据写回文件中，可通过调用 fse
15、ek 函数采实现插入。相应程序为： #includestdio.h #includestdlib.h #includeio.h #includefcntl.h #define LEN sizeof(int) void main(int argi,char*argc) int fp,i,d; if(argi3) printf(“filename int11“) exit(0); d=atoi(argc2); fp=open(argc1,O_GREAT| O_RDWRI O_BINARY,s_IREAD| S_IWRITE); while(1) if( read(fp,) if(i=d) /*文件中读出数据 i，若 i=d，则先存 d*/ do fseek(fp,-1L*lan,SEEK_CUR); /*文件指针后退 1 个记录*/ write(fp, /*d 写到文件中*/ d=i; /*原 i 作 d，以便处理其他数据*/ while(read(fp, write(fp，/*继续读数据，并判别文件是否结束*/ break; close(fp); /*main*/
