重庆理工大学算法与数据结构试卷三

-1-重庆理工大学考试试卷一、单项选择题（每题1分，共10分）1．广义表((b)，b)的表尾是（）A.bB.((b)C.(b)D.((b))2．带头结点的单链表h为空的判定条件是（）。A.h==NULLB.h-next==NULLC.h-next==hD.h!=NULL3．一个向量（一维数组）第一个元素的存储地址是100，每个元素的长度为2，则第6个元素的地址是（）。A.110B.108C.106D.1124．判定一个循环队列Q（最多元素为m）为空的条件是（）。A.Q-front==Q-rearB.Q-front!=Q-rearC.Qfront=(Q-rear+1)%mD.Q-front!=(Q-rear+1)%m5．数组B中，每个元素的长度为3个字节，行下标i从1到8，列下标j从1到10，从首地址SB开始连续存放在存储器内，该数组按行存放时，元素A[8][5]的起始地址为（）A.SB+141B.SB+219C.SB+222D.SB+2256．有一个有序表为{2，3，8，10，30，40，45，62，75，77，88，95，99}，当二分查找值为88的结点时，需（）次比较后查找成功。A.2B.3C.4D.57．队列的特点是（）。A.先进先出B.先进后出C.同时进出D.以上都不对8．一个有m个顶点的有向图最多有（）条边。A.mB.m(m-1)C.m(m-1)/2D.2m9．在一个单链表中，已知q所指结点是p所指结点的前驱结点，若在q和p之间插入f结点，则执行（）。A.f-next=p-next;p-next=fB.p-next=f-next;f-next=pC.q-next=f;f-next=pD.p-next=f;f-next=q10．在一个单链表中，若删除q所指结点的后续结点，则执行（）。A.q-next=q-next-next;B.q=q-next;q-next=q-next-next;C.q-next=q-nextD.q=q-next-next二、填空题（每空1分，共15分）1.在带有头结点的单链表L中，若要删除第一个结点，则需执行下列三条语句：；L-next=U-next；free(U)；-2-2．G为无向图，如果从q的某个顶点出发，进行一次广度优先搜索，即可访问图的每个顶点，则该图一定是。3．在无头结点的双链表中，指针P所指结点是第一个结点的条件是。4．有向图G用邻接矩阵A[1..n,1..n]存储，其第i行的所有元素之和等于顶点i的_________。5．在以HL为表头指针的带表头附加结点的单链表和循环单链表中，链表为空的条件分别为和。6．阅读下列算法，并填空回答下列问题：(1)该算法采用策略进行排序?(2)算法中R[n+1]的作用是?typedefstruct{KeyTypekey;infoTypeotherinfo;}nodeType;typedefnodeTypeSqList［MAXLEN］;voidsort(SqListR,intn){//n小于MAXLEN-1intk;i;for(k=n-1;k=1;k--)if(R[k].keyR[k+1].key){R[n+1]=R[k];for(i=k+1;R[i].keyR[n+1].key;i++)R[i-1]=R[i];R[i-1]=R[n+1];}}7.下面是将键值为x的结点插入到二叉排序树中的算法，请在划线处填上适当的内容：typedefstructpnode{intkey;structpnode*lchild,*rchild;}pnode;voidsearchinsert(intx,pnodet)/*t为二叉排序树根结点的指针*／{if((1)){p=(pnode*)malloc(sizeof(pnode));p-key=x;p-lchild=null;p-rchild=null;t=p;-3-}elseif(xt-key)searchinsert(x,(2))else____(3)_____}8.如下为C语言表示的拓扑排序算法,试在下划线的序号处填上适当内容。voidtopsort(hdnodegraph[],intn){inti,j,k,top;node_pointerptr;top=-1;for(i=0;in;i++)if(!graph[i].count){graph[i].count=top;top=i;}for(i=0;in;i++)if(__（1）___){fprintf(stderr,\ngraphhasacycle\n);exit(1);}else{j=top;____（2）____;printf(v%d,,j);for(ptr=graph[j].link;（3）;ptr=ptr-link){k=ptr-vertex;graph[k].count--;if(____（4）___){graph[k].count=top;top=k;}}}}三、应用题（每小题5分，共20分）1、二叉树结点数值采用顺序存储结构，如表1所示。表11234567891011121314151617181920eafdgcjhib（1）画出二叉树表示；（2）写出前序遍历，中序遍历和后序遍历的结果；（3）画出把此二叉树还原成森林的图。2、已知一个无向图的邻接表如下图1所示。（1）画出这个图。（2）从顶点8出发，对图进行深度优先搜索，写出其搜索序列。图13、线性表的关键字集合{87，25，310，08，27，132，68，95，187，123，70，63，7}，共有13个元素，已知散列函数为：H(k)=k%13。采用拉链法处理冲突。设计出这种链表结构，并计算该表的成功查找的平均查找长度。4、画出对长度为10的有序表进行二分查找的一棵判定树，并求其等概率时查找成功的平均查找长度。四、设计题（每小题10分，共30分）1.编写递归算法，求二叉树T的叶子结点的个数。2.设有一个表头为head的单链表。试写一算法Reverse(List&head)，将链表中所有结点按逆序链接。Typedefstructnode{intdata；structnode*next；}*List；3.编写按层次遍历二叉树算法。structnode{chardata；structnode*lchild；structnode*rchild；}bnode；-4-