自考数据结构容易错误试题汇总

《自考数据结构容易错误试题汇总》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、2011年1月全国自考数据结构24+14+16+9I.下列选项中与数据存储结构无关的术语是()A.顺序表B.链表C.链队列D.栈II.平均时间复杂度为0(”励/?)的稳定排序算法是()A.快速排序B.堆排序C.归并排序D.冒泡排序14.在含有10个关键字的3阶B■树中进行查找，至多访问的结点个数为()B.3A.2C.4D.520.广义表G=(a,b,(c,d,(e,f)),G)的长度为_4_无穷大。23.当待排关键字序列基本有序时，快速排序、简单选择排序和直接插入排序三种排序方法中，运行效率最高的是—直接插入排序0A*12A1B亠23A2C♦4A3D-►2A4E03A

2、25.不定长文件指的是文件的—记录—大小不固定。(2)从结点A出发,写出该图的深度优先遍历序列。ABCED(2)画出第二次重建堆之后的堆。31.假设以二叉链表表示二叉树，其类型定义如下：typedefstructnode{chardata;structnode*Ichild,*rchild;〃左右孩子指针}*BinTree；阅读下列程序。voidf31(BinTreeT){InitStack(S);//初始化一个堆栈Swhile(T11!StackEmpty(S)while(T)Push(S,T);T=T->lchild;讦(!StackEmpty(S))T=Pop(

3、S);printf(“％c”,T->data);T=T->rchild;回答下列问题：(1)已知以T为根指针的二叉树如图所示,请写出执行f31(T)的输出结果:(2)简述算法f31的功能。31.阅读下列程序。voidf32(intA[],intn){inti,j,m=l,t；for(i=0;ivn-l&&m；i++){for(j=0：jA[j]){t=AU-l];AU-1]=A

4、j]；A[j]=t；m=l；回答问题:己知整型数组A[

5、]={34,26,15,89,42),写出执行函数调用f32(A,5)后的输出结果。31.（1）CBEDFAG11【评分参考】裕1个结点位置扣1分.扣完4分为止"（2）中序遍为二叉树32.输出结果:342615894226153442891S26344289五、算法设计题（本题10分）34.假设用带头结点的单循坏链表表示线性表，单链表的类型定义如卞：typedefstructnode{intdata;structnode*ncxl;JLinkNode,*LinkList;编写程序，求头指针为head的单循坏链表中data域值为正整数的结点个数占结点总数的比例，若为空表

6、输出0,并给出所写算法的时间复杂度。函数原型为：floatf34（LinkListhead）:34.参考答案：floatf34(LinkfJsthead){（赋初值2分）（術环条件1分〉（结点计数2分）（修改指针I分）I.inkNodc•p~head->ncxt;intm=0,irX);while(p!-head){m-H-;if(p->dma>0)n+*;p^p->nexuif(m)return(float)n/m;elsereturn0;(计算返回值2分)时何复杂度为（为）.（2分）说明：若用其他方法实现该功能，请参照此评分标准给分。