《算法与数据结构》04级期末考试B卷

PAGEPAGE4一、填空题（每小题2分，共18分）1、数据的逻辑结构在计算机中的基本存储结构有和。2、算法的时间复杂度取决于。3、队列是的线性表，其操作数据的基本原则是。4、设有一个二维数组A[0…9][0…9]，若每个元素占2个基本存储单元，A[0][0]的地址是200，若按列优先（以列为主）顺序存储，则A[6][6]的存储地址是。5、在高度为h的二叉树的中只有度为0和度为2的结点，则该类二叉树中所包含的结点数至少为。6、对于一个有n个顶点和e条弧的有向图，若采用正邻接链表存储，则表头向量的大小为，邻接表中的结点总数为。7、若采用分块查找，要求线性表块内，块间。8、对于文件，按其记录的类型可将文件分为文件、文件。9、外部排序的最基本方法是，其主要时间花费在方面。二、单项选择题（请将答案写在题目后的括号中。每题2分，共18分）1、下面程序段的时间复杂度是（）。for(i=1；i<=m；i++)for(j=1；j<=n；j++)A[i][j]=i+j;（A）O(m+n)（B）O(m)（C）O(n)（D）O(m*n)2、判断一个循环队列Q（最多元素个数为m）为满队列的条件是（）。（A）Q.front==Q.rear；（B）Q.front!=Q.rear；（C）Q.front==(Q.rear+1)%m；（D）Q.front!=(Q.rear+1)%m；3、设有一个栈顶指针为top的顺序栈S，则将元素p压入栈S中的操作是（）。（A）S[top++]=p；（B）S[++top]=p；（C）S[top--]=p；（D）S[--top]=p；4、广义表((a),((b),c),(((d))))的长度是，深度是。（）（A）3,4（B）3,3（C）4,3（D）4,45、在二叉树中，指针P所指的结点是叶子结点的条件是（）。（A）P->Lchild!=NULL&&P->Rchild!=NULL；（B）P->Lchild!=NULL&&P->Rchild==NULL；（C）P->Lchild==NULL&&P->Rchild!=NULL；（D）P->Lchild==NULL&&P->Rchild==NULL；6、一棵二叉树，其先序遍历序列是abdghcefi，中序遍历序列是bgdhaecfi，则其后序遍历序列是()。（A）ghdbiefca（B）ghdbeicfa（C）ghdbeifca（D）gdheibfca7、若以{4,5,6,7,8}作为叶子的权值构造Huffman树(按左子树根结点的权小于等于右子树根结点的权的次序构造)，则其带权路径长度WPL为（）。（A）60（B）61（C）73（D）698、在无权图G的邻接矩阵中，若(Vi,Vj)或<Vi,Vj>属于G的边集，则对应元素A[i][j]等于，否则等于。（）（A）1，1（B）1，0（C）0，1（D）0，09、设有一组记录的关键字是（37，28，56，80，60，14，25，50），用快速排序法以第一个记录为基准得到的一次划分结果是（）。（A）25，28，14，37，60，80，56，50（B）25，28，37，14，60，80，56，50（C）25，28，14，37，60，56，80，50（D）25，28，37，14，56，80，60，50三、分析题（每题6分，共30分）1、设有一棵树如下图，请先将此树转换为二叉树，然后给出该二叉树的前序线索树和中序线索树。2、已知某有向图的逆邻接链表如下图所示，请先画出该有向图，然后给出其邻接矩阵和正邻接链表。40401231234538∧510∧18∧3424∧361952∧abdifchjeg3、将关键字序列（17，19，13，7，15，9，25）依此插入到初态为空的二叉排序树中，请画出建立二叉排序树T的过程；然后画出删除13之后的二叉排序树T1。4、线性表的关键字集合{21，25，28，19，42，57，15，43，17，36，49，27，65}，共有13个元素，已知散列函数为：H（k）=kMOD13，采用线性探测法处理冲突，请给出对应的散列表结构，并计算该表成功查找的平均查找长度。5、已知数据序列为{35，29，22，16，17，9，38，27，13，45}，请给出采用选择排序方法按非递减要求进行排序的过程。四、算法填空（每空2分，共20分）请在下面各算法的空白处填上相应语句以实现算法功能。每个空白只能填一个语句。1、在以L为头结点的双向链表中删除所有值为key的结点，结点结构定义如下。typedefstructLnode{ElemTypedata;/*数据域，保存结点的值*/structLnode*prior;/*指针域，指向直接后继*/structLnode*next;/*指针域，指向直接前趋*/}DULNode;/*结点的类型*/VoidDel_Node(DULNode*L，intkey){DULNode*q,*p=L–>next;while(p!=NULL){if(p–>data==key){q=p->next;if(p->next!=NULL){p->next->prior=p->prior;;}elsep->prior->next=NULL;;};}}2、设T是指向二叉树根结点的指针变量，用非递归方法统计树中叶子结点的数目。#defineMax_Node_Num50TypedefstructBTNode{ElemTypedata;/*数据域，保存结点的值*/structBTNode*Lchild,*Rchild;/*指针域*/}BTNode;/*结点的类型*/Voidcount_leaf_node(BTNode*T){BTNode*Stack[Max_Node_Num],*p=T,*q;inttop=0,leaf_num=0;/*leaf_num保存叶子结点的数目*/if(T==NULL)printf(“TheBinaryTreeisEmpty!\n”);else{do{if(p->Lchild==NULL&&p->Rchild==NULL);q=p->Rchild;if(q!=NULL);p=p->Lchild;}while();printf(“叶子结点的数目是:%d\n”,leaf_num);}}链表结点adjvexinfonextarc顶点结点链表结点adjvexinfonextarc顶点结点indegreedatafirstarcVoidcount_indegree(ALGraph*G){intk;LinkNode*p;for(k=0;k<G->vexnum;k++)G->adjlist[k].indegree=0;for(k=0;k<G->vexnum;k++){;while(p!=NULL){G->adjlist[p->adjvex].indegree++;;}}}4、H->R[s…m]中记录关键字除H->R[s].key均满足堆定义，调整H->R[s]的位置使之成为小根堆。VoidHeap_adjust(Sqlist*H,ints,intm){intj=s,k=2*j;/*计算H->R[j]的左孩子的位置*/H->R[0]=H->R[j];/*临时保存H->R[j]*/for(k=2*j;k<=m;k=2*k){if((k<m)&&(H->R[k].key>H->R[k+1].key)k++;/*选择左、右孩子中关键字的最小者*/