算法与数据结构C卷答案

2009–2010学年第1学期期末考试试卷（C卷）开课学院：数计学院课程名称：算法与数据结构考试形式：闭卷所需时间：120分钟题号一二三四五六七八总分得分评卷人注意事项：1、教师出题时请勿超出边界虚线；2、学生答题前将密封线外的内容填写清楚，答题不得超出密封线；3、答题请用蓝、黑钢笔或圆珠笔。一、选择题（每小题2分，共计20分）1.计算机算法指的是（C）A．计算方法B.排序方法C.解决问题的步骤序列D.调度方法2．线性表是具有n个（B）的有限序列（n>0）。A．字符B．数据元素C．数据项D．信息项3．设一个链表最常用的操作是在末尾插入结点和删除尾结点，则选用(D)最节省时间。A.单链表B.单循环链表C.带尾指针的单循环链表D.带头结点的双循环链表4.一个栈的输入序列为123…n，若输出序列的第一个元素是n，输出第i（1<=i<=n）个元素是（B）。A.不确定B.n-i+1C.iD.n-i5.用不带头结点的单链表存储队列时,其队头指针指向队头结点,其队尾指针指向队尾结点，则在进行删除操作时(D)。A．仅修改队头指针B.仅修改队尾指针C.队头、队尾指针都要修改D.队头,队尾指针都可能要修改6.设树T的度为4，其中度为1，2，3和4的结点个数分别为4，2，1，1则T中的叶子数为（D）A．5B．6C．7D．87.下面关于二分查找的叙述正确的是(C)A.表必须有序，表可以顺序方式存储，也可以链表方式存储B.表必须有序且表中数据必须是整型，实型或字符型C.表必须有序，且表只能以顺序方式存储D.表必须有序，而且只能从小到大排列8.一棵左右子树均不空的二叉树在先序线索化后，其中空的链域的个数是：(B)。A.0B.1C.2D.不确定9．某内排序方法的稳定性是指(D)。A．该排序算法不允许有相同的关键字记录B．该排序算法允许有相同的关键字记录C．平均时间为0（nlogn）的排序方法D．以上都不对10．图中有关路径的定义是（A）。A．由顶点和相邻顶点序偶构成的边所形成的序列B．由不同顶点所形成的序列C．由不同边所形成的序列D．上述定义都不是二、填空题（每空1分，共计10分）1.下面程序段的时间复杂度为__O(n)______。(n>1)sum=1；for(i=0;sum<n;i++)sum+=1;2.已知指针p指向单链表L中的某结点，则删除其后继结点的语句是：_u=p->next;p->next=u->next;free(u);3.一个栈的输入序列是：1，2，3则不可能的栈输出序列是__312_____。4.顺序栈用data[1..n]存储数据，栈顶指针是top,则值为x的元素入栈的操作是___data[++top]=x；____。5.设循环队列存放在向量sq.data[0:M]中，若用牺牲一个单元的办法来区分队满（设队尾指针sq.rear）,则队满的条件为_(sq.rear+1)%(M+1)==sq.front；。6．在完全二叉树中，编号为i和j的两个结点处于同一层的条件是__ëlog2iû=ëlog2jû____。7.顺序查找n个元素的顺序表，当使用监视哨查找失败，则比较关键字的次数为__n+1。。8．具有N个结点的二叉树，采用二叉链表存储，共有__N+1____个空链域。9．若不考虑基数排序，则在排序过程中，主要进行的两种基本操作是关键字的__比较____和记录的移动。10．N个顶点的连通图的生成树含有__N-1____条边。三、判断题（每小题2分，共计20分）1.数据结构的抽象操作的定义与具体实现有关。(×)2.顺序存储结构的主要缺点是不利于插入或删除操作。(√)3.栈是实现过程和函数等子程序所必需的结构。（√）4.栈和队列都是线性表，只是在插入和删除时受到了一些限制。（√）5.二叉树是度为2的有序树。(×)6．对一棵二叉树进行层次遍历时，应借助于一个栈。(×)7.空字符串是只包含“空白”字符的字符串。（×）8.折半查找法的查找速度一定比顺序查找法快。（×）9．当待排序的元素很大时，为了交换元素的位置，移动元素要占用较多的时间，这是影响时间复杂度的主要因素。（√）10．在n个结点的无向图中，若边数大于n-1,则该图必是连通图。（×）四、应用题（每小题5分，共计30分）1、画出下图采用邻接表表示的示意图。答：2、已知一棵二叉树的中根周游结点序列为DGBAECHIF，后根周游结点序列为GDBEIHFCA，试画出该二叉树并写出其先根周游序列。先根周游序列：ABDGCEFHI3、已知元素个数为12的字典，其元素集合为：{jan,feb,mar,apr,may,june,july,aug,sep,oct,nov,dec}试按元素的次序依次插入一棵初始时为空的二叉排序树，请画出插入完成之后的二叉排序树，并求其在等概率情况下检索成功的平均检索长度。AVL=(1*1+2*2+3*3+4*3+5*2+6*1)/12=42/12=3.5(次)4、设有一组元素的关键码集为：05,10,18,25,27,32,41,51,68,73,99,试给出采用二分法检索关键码9的具体过程。答：step1:low=1,high=11,mid=(1+11)/2=6,key=32>10step2:high=mid-1=5,mid=(1+5)/2=3,key=18>10step3:high=mid-1=2,mid=(1+2)/2=1,key=05<10step4:low=mid+1=2,mid=(2+2)/2=2,key=10>9step5:high=mid-1=1,high<low查找失败5、对于初始排序码[49,38,65,97,76,13,27,49’初始排序码：[49,38,65,97,76,13,27,49’i=1[273813]49[76976549’i=2[13]27[38]49[76976549’i=31327[38]49[76976549’i=413273849[76976549’i=513273849[49’i=61327384949’i=71327384949’最后1327384949’6、采用Kruskal算法，画出下图最小生成树的生成过程。答：五、算法与编程（每小题10分，共计20分）1、写一算法，在带头结点的单链表llist中，p所指结点前面插入值为x的新结点，并返回插入成功与否的标志。注：单链表数据结构定义如下：structNode;/*结点类型*/typedefstructNode*Pnode;/*结点指针类型*/structNode{/*结点结构*/DataTypeinfo;/*数据域*/Pnodelink;/*指针域/}typedefstructNode*LinkList;/*单链表类型*/答：intinsertPre_link(LinkListllist,Pnodep,DataTypex){Pnodep1;if(llist==NULL)return0;p1=llist;/*寻找p所指结点的前趋结点*/while(p1!=NULL&&p1->link!=p)p1=p1->link;if(p1==NULL)return0;PNodeq=(PNode)malloc(sizeof(structNode));if(q==NULL){printf(“OVERFLOW!\n”);return0;}q->info=x;q->link=p1->link;p1->link=q;return1;}2、试给出二叉树链接存储方式的描述，并写一算法计算给定二叉树中叶子结点数（给定二叉树采用链接存储方式）。答：structBinTreeNode;/*二叉中结点*/typedefstructBinTreeNode*PbinTreeNode;/*结点的指针类型*/structBinTreeNode{DataTypeinfo;/*数据域*/PbinTreeNodellink;/*左指针*/PbinTreeNoderlink;/*右指针*/};typedefstructBinTreeNode*BinTree;typedefBinTree*P