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

重庆理工大学考试试卷一、单项选择(每题2分，共20分)1．一个具有n个顶点的无向完全图的边数为（）A.n(n+1)/2B.n(n+1)C.n(n-1)D.n(n-1)/22．线性表若采用链式存储结构时，要求内存中可用存储单元的地址（）A.必须是连续的B.部分地址必须是连续的C.一定是不连续的D.连续不连续都可以3．一个顺序表第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是（）A.110B.108C.100D.1204．串是一种特殊的线性表，其特殊性体现在（）A.可以顺序存储B.数据元素是一个字符C.可以链接存储D.数据元素可以是多个字符5．顺序查找法适合于存储结构为（）的线性表。A.散列存储B.顺序存储或链接存储C.压缩存储D.索引存储6．下述几种排序方法中，平均时间复杂度昀小的是（）A.插入排序B.选择排序C.冒泡排序D.快速排序7.循环队列用数组A[0，m-1]存放其元素值，已知其头尾指针分别是front和rear，则当前队列中的元素个数是。A.(rear-front+m)%mB.read-front+1C.read-front-1D.read-front8.3个结点可构成（）个不同形态的二叉树。A.2B.3C.4D.59．对于关键字值序列（12，13，11，18，60，15，7，18，25，100），用筛选法建堆，必须从关键字值为（）的结点开始。A.100B.12C.60D.1510．栈操作的原则是（）A.先进先出B.后进先出C.栈顶插入D.栈顶删除二、填空题（每小题1分，共10分），将正确的答案写在每小题的空格内。1.在双循环链表中，在指针p所指结点前插入指针s所指的结点，需执行下列语句：s-next=p;s-prior=p-prior;p-prior=s;________________=s;2．散列法存储中处理碰撞（冲突）的两类基本方法是、3.设二维数组A[-2..10,-1..20]按行优先顺序存储，每个元素占4个存储单元，A[-2,-1]的存储地址是1000,则A[5,6]的存储地址是。4.设s[1..maxsize]为一个顺序存储的栈，变量top指示栈顶位置，栈为空的条件是___________，栈为满的条件是__________________。5．设有向图的邻接矩阵为A，如果图中不存在弧VI，VJ，则A[I][J]的值为：。6.设有一个链队列，结点结构为：队尾指针为Ls（≠null），则执行入队操作时，S-next=Ls-next；___________；___________。7.单链表中指针P所指结点不为尾结点的条件是___________。8.G为无向图，如果从q的某个顶点出发，进行一次广度优先搜索，即可访问图的每个顶点，则该图一定是图。9.串S=″Iamaworker″的长度是_____。10.按先根次序法遍历树林正好等同于按遍历对应的二叉树。、算法应用题(每小题5分,共20分)到昀小生成树，试在下表的空白处顶点134UV155423214三1、对上图所示的网，执行prim算法可得填上适当的内容，以说明该算法的执行过程。（U，V）（2，1）（2，3）（2，4）{2}{1，4}代价∞423，（U，V）（2，3）{2，4}{1，3}代价4（U，V）（3，1）{2，4，3}{1}代价1（U，V）{2，4，3，1}代价2、有一组关键码序列{8，9，，1采用冒泡排、快速排序、5，3，72，}，分别序直接选择排序、直接插入排序、二路归并排序方法由小到大进行排序，在下面的选项中选择各种排序第一趟排序的结果。冒泡排序：；快速排序：；直接选择排序：直接插入排序：；二路归并：A．{1，2，5，3，7，8，9}B．{1，9，5，3，7，2，8}C．{9，8，5，3，7，2，1}D．{9，5，3，7，2，1，8}E．{8，5，3，7，2，1，9}F．{8，9，3，5，2，7，1}3、设有序序列30,18,3,61,14,49，请按该序列构成一棵二叉排序树，并求查现有5个结点（A，B，C，D，E），它们的权值分别为{5，10，12，15，30}，、算法填空和分析（每小题5分，共30分）字符串是否是中心对称,如ardata；next；}cnode*h)arst[MaxLen]；找3的比较次数。4、在下面的选项中选择一个编号，说明这5个结点的哈夫曼编码。（）（1）A：1，B：001，C：010，D：011，E：000（2）A：000，B：001，C：010，D：011，E：1（3）A：001，B：011，C：010，D：000，E：1（4）A：000，B：1，C：010，D：011，E：001四1、设单链表存放字符串,下列算法使用栈判断该abccba即为中心对称字符串.根据题目填空完善程序.typedefstructnode{chstructnode*cnode；intjudge({chinttop=0；cnode*p=；[top]=p-data；while(p!=NULL){sttop；p=p-next；}p=；pwhile(p!=NULL){to；if(p-datast[top])p=p-next；elk；}if(p==NULL)elsurn0；}voidMerge(ElemSR[],ElemTR[],inti,intm,intn)sebreareturn1；eret2、{//将有序的SR[i..m]和SR[m+1..n]归并为有序的TR[i..n]for(j=m+1,k=i;i=m&&j=n;++k){//将SR中记录由小到大地并入TRif(SR[i].key=SR[j].key)TR[k]=；}if(elseTR[k]=SR[j++];)TR[k..n]=SR[i..m];//将剩余的SR[i..m]复制到TRif()TR[k..n]=SR[j..n];//将剩余的SR[j..n]复制到TR}//Merge3、intPartition(ElemR[],intlow,inthigh)记录到位，并返回//其地向中间扫描ivotkey)--high;{//交换记录子序列R[low..high]中的记录，使枢轴所在位置，此时，在它之前（后）的记录均不大（小）于它R[0]=R[low];//用子表的第一个记录作枢轴记录pivotkey=R[low].key;//枢轴记录关键字while(lowhigh){//从表的两端交替while(lowhigh&&R[high].key=pR[low]=R[high];//将比枢轴记录小的记录移到低端while(lowhigh&&R[low].key=pivotkey);R[high]=R[low];//将比枢轴记录大的记录移到高端}R[low]=;//枢轴记录到位intn,intk)=0))returnlow;//返回枢轴位置}//Partition4、折半查找算法：intbinsrch(JDr[],{intlow,high,mid,found;low=1;high=n;found=0;while((low=high)&&(found={mid=(low+high)/2;if(kr[mid].key);;found==1)elseif(k==r[mid].key)found=1elsehigh=mid-1;}if(return();urn(0);设有一个表头为head的单链表。通过遍历一趟链表，将链表中所有结点按ctnode*next;(pointerhead)elseret}5、逆序链接。typedefstru{intdata;structnode}pointer;Voidinvert{p=;while(head!=NULL)-next;{u=head;head=headu-next=;}head=p;已知带权图的邻接矩阵表示和邻接表表示的形式说明分别如下：昀大整数，表示∞//字符类型的顶点表整型的邻接矩阵p=u;}6、#defineMaxNum50//图的昀大顶点数#defineINFINITYINT_MAX//INT_MAX为typedefstruct{charvexs[MaxNum];intedges[MaxNum][MaxMum];//权值为intn,e;//图中当前的顶点数和边数}MGraph;//邻接矩阵结构描述typedefstructnode{intadjvex;//邻接点域intweight;//边的权值structnode*next;//链指针域域边表头指针MaxNum];//邻接表存储结构G1建立该图的邻接表存储结i,j;p;;i++)-adjlist[i].vertex=G1-vexs[i];}EdgeNode;//边表结点结构描述typedefstruct{charvertex;//顶点EdgeNode*firstedge;//}VertexNode;//顶点表结点结构描述typedefstruct{VertexNodeadjlist[intn,e;//图中当前的顶点数和边数}ALGraph;//邻接表结构描述下列算法是根据一个带权图的邻接矩阵构G2，请填入合适的内容，使其成为一个完整的算法。voidconvertM(MGraph*G1,ALGraph*G2){intEdgeNode*G2-n=G1-n;G2-e=G1-e;for(i=0;iG1-n{G2G2-adjlist[i].firstedge=;=0;iG1-n;i++)+)INFINITY)(EdgeNode*)malloc(sizeof(EdgeNode));}for(ifor(j=0;jG1-n;j+if(G1-edges[i][j]{p=p-weight=;p-adjvex=j;p-next=G2-adjlist[i].firstedge;;编写算法（每小题10分，共20分）：用于存放某人的电话薄，现在由}}五、1、设某单链表L的结点结构如下，单链表L于电话号码从7位升为8位（加60000000），请用C语言编写算法，实现电话薄中所有电话号码从7位升为8位。Typedefstructnode{charname[9];//姓名pointerL)设二叉树采用二叉链表表示，编写算法，将二叉树中所有结点的左右子树ctnodeintdata;e*lchild,rchild;Revolute(BitreeT)//交换所有结点的左右子树longdata;//电话号码structnode*next;}pointer;intchange({}2、相互交换。Typedefstru{structnod}*Bitree;voidBitree_{}