1、全国自考（数据结构）模拟试卷 4 及答案与解析一、单项选择题1 对文件进行直接存取的是根据( )（A）逻辑记录号去存取某个记录（B）逻辑记录的关键字去存取某个记录（C）逻辑记录的结构去存取某个记录（D）逻辑记录的具体内容去存取某个记录2 一个栈的人栈序列是 a,b,c,d,e，则栈的不可能的输出序列是( )（A）e d c b a（B） d e c b a（C） d c e a b（D）a b c d e3 带头结点的单链表 head 为空的判断条件是( )（A）head=NULL（B） headnext=NULL（C） headnext=head（D）head!=NULL4 非空的单循环链表
2、 L 的尾结点 P，满足( )（A）P.next=NULL;（B） P=NULL;（C） P.next=L;（D）P=L5 在下面的排序方法中，不需要通过比较关键字就能进行排序的是( )（A）箱排序（B）快速排序（C）插入排序（D）希尔排序6 通常要求同一逻辑结构中的所有数据元素具有相同的特性，这意味着( )（A）数据元素具有同一特点（B）不仅数据元素所包含的数据项的个数要相同，而且对应数据项的类型要一致（C）每个数据元素都一样（D）数据元素所包含的数据项的个数要相等7 从具有 n 个结点的单链表中查找值等于 x 的结点时，在查找成功的情况下，平均需比较( ) 个结点。（A）n（B） n/2（
3、C） (n-1)/2（D）(n+1)/28 在一个链队列中，若 f，r 分别为队首、队尾指针，则插入 s 所指结点的操作为( )（A）fnext=c;f=s;（B） rnext=s;r=s;（C） snext=r;r= s（D）snext=f,f=s;9 设散列函数为 H(k)=k mod7，一组关键码为 23,14,9,6,30,12 和 18，散列表 T 的地址空间为 0.6，用线性探测法解决冲突，依次将这组关键码插入 T 中，得到的散列表为( )（A） _; return(t); 31 以下运算实现在顺序栈上的退栈，请在_处用适当的语句予以填充。 int Pop(SqStackTp*sq
4、,DataType*x) if(sqtop=0)error(“下溢“);return(0);) else*x=_; _; return(1); 32 以下算法在开散列表 HP 中查找键值等于 K 的结点，成功时返回指向该点的指针，不成功时返回空指针。请分析程序，并在_上填充合适的语句。 pointer research_openhash(keytype K,openhash HP) i=H(K); /*计算 K 的散列地址 */ p=HPi; /*i 的同义词子表表头指针传给 P*/ while(_)p=pnext; /*未达到表尾且未找到时，继续扫描*/ _; 33 基于三元组的稀疏矩阵转置
5、的处理方法有两种，以下运算按照矩阵 A 的列序来进行转置，请在_处用适当的语句予以填充。 Trans_Sparmat(SpMatrixTp a,SpMatrixTp*b) (*b).mum=a.nu;(*b).nu=a.mu;(*b).tu=a.tu if(a.tu) q=1; for(col=1;_;col+) for(p=1;p=a.tu;p+) if(_)=col) (*b).dataq.i=a.datap.j; (*b).dataq.j=a.datap.i; (*b).dataq.v=a.datap.v; _; 五、算法设计题34 采用单链表作为存储结构，试编写一个函数来实现用选择排序
6、方法进行升序排列。全国自考（数据结构）模拟试卷 4 答案与解析一、单项选择题1 【正确答案】 A2 【正确答案】 C3 【正确答案】 B4 【正确答案】 C5 【正确答案】 A6 【正确答案】 B7 【正确答案】 D8 【正确答案】 B9 【正确答案】 B10 【正确答案】 A11 【正确答案】 A12 【正确答案】 C13 【正确答案】 A14 【正确答案】 B15 【正确答案】 C二、填空题16 【正确答案】 O(1) O(n)17 【正确答案】 模式匹配18 【正确答案】 (n+1)/2 n+119 【正确答案】 小于20 【正确答案】 (n+r-f)mod n21 【正确答案】 统一
7、固定22 【正确答案】 n(n+1)/223 【正确答案】 LOC(a 1)=LOC(a1)+(i-1)*c24 【正确答案】 n125 【正确答案】 静态 动态三、解答题26 【正确答案】 A，B，C 对应的图分别为：27 【正确答案】 根据二分查找的过程，我们可以得到如下的比较结果： 第一次比较：5,9,12,18,23,31,37,46,59,66,71,78,85, 第二次比较：5,9,12,18,23,31,37,46,59,66,71,78,85 第三次比较：5,9,1218,23,31,37,46,59,66,71,78,85 28 【正确答案】 快速排序采用分治法进行，其基本思
8、想如下：将原问题分解成为若干个规模更小但结构和原问题相似的子问题，递归地解这些子问题，然后将这些子问题的解的组合为原问题的解，根据上述思想，我们可以得到如下快速排序的各趟结果如下： 初始：505,94,512,61,908,170,897,275,653,432 第 1 趟：462,94,295,61,170505897,908,653,512 第 2 趟：170,94,295,61462,505897,908,653,512 第 3 趟29 【正确答案】 初始值键值序列125 9 20 6 31 24 初始键值序列12 5 9 20 6 31 24 第一趟之后5 9 12 6 20 2431
9、 第二趟之后5 9 6 12 2024 31 第三趟之后5 6 9 1220 24 31 第四趟之后 5 6 9 12 20 24 31四、算法阅读题30 【正确答案】 t=malloc(size) tnext=NULL31 【正确答案】 sqdatasq top sqtop-32 【正确答案】 (P!=NULL) struet node*link; 函数如下: struct*selectsort(struct node*h) struet node*P,*q,*r,*s,*t; t=Null; while(h!=Null) p=h; q=Null; s=h; r=Null; while(P!=Null) if(pkeyskey) s=p; p=q; q=p; p=p link; if(s=h) h=h link; else h=s; slind=t; t=s; h=t; return(h);
