1、全国自考（数据结构）模拟试卷 1 及答案与解析一、单项选择题1 索引顺序文件的记录，在逻辑上按关键字顺序排列，但物理上不一定按关键字顺序存储，故需要建立一张指示逻辑记录和物理记录之间一一对应关系的( )（A）索引表（B）链接表（C）符号表（D）交叉访问题2 在循环双链表的 p 所指结点之后插入 s 所指结点的操作是 ( )（A）Pnext=s；（B） pnext=s ； s prior=p； pnextprior=s； pnextprior=s； sprior=p； snext=pnext； s next=pnext（C） sprior=p ；（D）sprior=p； snext=p next
2、； snext=pnext； pnext=s； p nextprior=s； pnextprior=s； pnext=s；3 在下面的程序中，语句 S 的执行次数为( ) for(i=1;i=n-1;i+) for(j=n;j=i;j-) S; （A） else return(0); 32 以下算法在有序表 R 中用二分查找法查找键值等于 K 的元素，请分析程序，并在_上填充合适的语句。 int binsearch(sqtable R,keytype K) low=l;hig=R.n;/*置查找区间初值。low，hig 分别标记查找区间的下、上界 */while(low=hig) mid=(l
3、ow+hig)/2; switch case K=R.itemi.key:return(mid); /*找到，返回位置 mid*/ case KR.itemi.key:_.break;/*缩小区间*/ case KR.itemi.key:_;break/*缩小区间*/ return(0); /*若区间长度已为 0 但仍不成功，则返回 0，表示查找不成功*/ 33 以下运算实现在链栈上的退栈，请在_处用适当的语句予以填充。 int Pop(LStackTp*is,DataType*x) LStackTp*P; if(1s!=NULL) p=ls; *x=_; ls=lsnext; _; retu
4、rn(1); else return(0); 34 分析下面程序段的时间复杂度_。 j=1; while(j=n) j=j*2; 五、算法设计题35 设计一个用链表表示的直接选择排序算法。全国自考（数据结构）模拟试卷 1 答案与解析一、单项选择题1 【正确答案】 A2 【正确答案】 D3 【正确答案】 B4 【正确答案】 A5 【正确答案】 A6 【正确答案】 A7 【正确答案】 C8 【正确答案】 C9 【正确答案】 C10 【正确答案】 A11 【正确答案】 B12 【正确答案】 C13 【正确答案】 B14 【正确答案】 C15 【正确答案】 B二、填空题16 【正确答案】 fhca b
5、 egcj17 【正确答案】 线性表18 【正确答案】 物理19 【正确答案】 2m-120 【正确答案】 在树上查找被删除关键字 K 所在的地点 删除 K21 【正确答案】 双亲表示法22 【正确答案】 出度数 度数23 【正确答案】 顺序集 关键字24 【正确答案】 能惟一标识数据元素的数据项 不能惟一标识数据元素的数据项25 【正确答案】 1-1三、解答题26 【正确答案】 含有三个结点的树只有两种形式见(1)和(2)；含有 3 个结点的二叉树有 5 种形态见(3)，(4)，(5)，(6)，(7) 对于一棵普通的树来说，图(4)，(5) ，(6)，(7)是完全相同的，但如果它们作为二叉树
6、，则表示不同的二叉树，因为在一棵二叉树中，每个结点的孩子都有左右之分，即使某节含有一个孩子，则此孩子结点仍有左右点之分。27 【正确答案】 t=CONCAT(Rep(sup(s,1,5),y,+),Rep(sub(s,6,1),*,*y) s=CONCAT(Rep(sub(t,1,5),+,y)，Rep(sub(t,6,2),*y,*)28 【正确答案】 第一种表示需要 n+2 个实数存储单元，其中 n 为多项式的最高幂数；第二种表示需要 2m+1 个实数存储单元，其中 m 为非零系数的个数。显然，当非零系数较少时 ，第二种表示法需要较少的存储空间。29 【正确答案】 采用每种表示法处理多项式
7、相加比较简单，只需将次数较低的多项式的各项的系数加到次数较高的多项式的相应项的系数上去即可。而第二种方法要查找到相同的指数才能将系数相加，相加之和可能为 0，这就要修改项数 m；另外当某个多项式中有的项而在另一个多项式中没有，显然其和也应作相应的修改。30 【正确答案】 根据队列的操作规则：进队时，将新元素插入到 rear 所指的位置，然后将 rear 加 1， front 不变，出队时，删除 front所指的元素，然后将 front 加 1，rear 不变，则有：A ，B，C 进队列后，rear 指针指向 3，front 不变，A 出队列时，删除 A，将 front 加 1，所以 front
8、 指向 1，rear不变，B ，C 都出队时，fron 加 2，rear 不变，此时， rear 和 front 相等。四、算法阅读题31 【正确答案】 sq.rear=sq.front32 【正确答案】 hig=mid-1 lowlow+133 【正确答案】 pdata free(p)34 【正确答案】 O(log 2n)五、算法设计题35 【正确答案】 Void selesort(lklist L) /*设链表 L 带头结点*/ q=L; /*指向第一数据前趋*/ while(qnext!=NULL) p1=qntxt; minp=p1; /*minp 指向当前已知的最小数*/ while
9、(p1next!=NULL) if(p1nextdataminpdata)minp=p1next; /*找到了更小数*/ p1=p1next; /*继续往下找*/ if(minp!=qnext; /*将最小数交换到第一个位置上*/ r1=minpnext minpnext=r1 next; /*删除最小教*/ r2=qnext; qnext=r2 next; /*删除当前表中第一个数*/ r1next=qnext; qnext=r1; /*将最小插入到第一位置上 */ r2next=minp next; minpnext=r2; /*将原第一个数放到最小数原位置上*/ q=qnext; /*选择下一个最小数 */
