资源描述：
《《数据结构与算法》模拟试卷六》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、《数据结构与算法》模拟试卷六一、名词解释（5*3=15分）AOV网队列栈哈夫曼树生成树二、填空题（1*16=16分）1.根据数据元素之间关系的不同特性，通常有下列四类基本结构：_____、_____、_____、_____。2.数据元素之间的关系在计算机中可用顺序映像和非顺序映像表示，由此得到两种存储结构是_____、_____。3.用具有n个元素的一维数组存储一个循环队列，该循环队列的最大长度为_____。一棵高度为5的二叉树中最少含有_____个结点，最多含有_____个结点；4.在无向图G的邻接矩阵A中，若(vi,vj)属于图G的边的集合，则对应元素A[i][j]
2、等于_______，否则等于_________。5.二分查找的存储结构仅限于________，且是__________。6.在对一组记录(54，38，96，23，15，72，60，45，83)进行直接插入排序时，当把第7个记录60插入到有序表时，为寻找插入位置需比较________次。7.设顺序表中有n个关键字，采用顺序的方法查找，其平均查找长度为________。8.二叉树第i（i≥1）层上最多有________个结点。三、选择题（1*10=10分）1.在一个不带头结点的单链表HL中，若要向表头插入一个由指针p指向的结点，则执行_____。A、L=p;p->next=
3、HL;B、p->next=HL;HL=p;C、p->next=HL;p=HL;D、p->next=HL->next;HL->nxet=p;2.在一个长度为n的顺序存储的线性表中，删除第i个元素（1≤i≤n+1）时，需要从前向后依次移动个元素_____。A、n-iB、n-i+1C、n-i-1D、i3.在一个顺序队列中，队首指针指向队首元素的位置。_____。A、当前B、后一个C、前一个D、后面4.n个结点的线索二叉树中线索的数目为_____。A、(n-1)个B、n个C、（n+1）个D、(n+2)个5.设数组A[m]为循环队列Q的存储空间，front为队头指针，rear为队
4、尾指针，则判定Q为空队列的条件是_____。A.(rear-front)%m==1B.front==rearC.(rear-front)%m==m-1D.front==(rear+1)%m6.假设一棵完全二叉树按层次遍历的顺序依次存放在数组BT[m]中，其中根结点存放在BT[0]，若BT[i]中的结点有左孩子，则左孩子存放在_____。A.BT[i/2]B.BT[2*i-1]C.BT[2*i]D.BT[2*i+1]6.连通图是指图中任意两个顶点之间_____。A.都连通的无向图B.都不连通的无向图C.都连通的有向图D.都不连通的有向图7.左图所示带权无向图的最小生成树的
5、权为。A.14B.15C.17D.188.栈的插入和删除操作在_____进行。A.栈顶B.栈底C.任意位置D.指定位置9.以下说法正确的是。A．连通图的生成树是该连通图的一个极小连通子图B．无向图的邻接矩阵是对称的，有向图的邻接矩阵一定是不对称的C．任何一个有向图，其全部顶点可以排成一个拓扑序列D．有回路的图不能进行拓扑排序四、计算和应用题（共21分）1．假设用于通信的电文仅由8个字母组成，字母在电文中出现的频率分别为0.08,0.18,0.02,0.06,0.35,0.10,0.16,0.05。试为这8个字母设计哈夫曼编码。并计算其平均编码长度（即WPL）。2．使用普
6、里姆算法构造如下图所示的图G的一棵最小生成树。（画出构造过程）3．待排序关键字（34,12,28,45,66,7,3,21），写出希尔排序的每趟结果。五、算法填空（9*2=18分）1.如果希望循环队列中的向量单元都能得到利用，则可设置一个标志域tag,每当尾指针和头指针值相同时，以tag的值为0或1来区分队列状态是“空”还是“满”。请对下列函数填空，使其分别实现与此结构相应的入队列和出队列的算法。intEnQueue(CirQueue*Q,DataTypex){if((1))return0;Q->data[Q->rear]=x;Q->rear=(Q->rear+1)%M
7、AXQSIZE(2)return1;}intDeQueue(CirQueue*Q,DataType*x){if((3))return0;*x=Q->data[Q->front];Q->front=(4);(5);return1;}(1)(2)(3)(4)(5)2.下列算法利用二分查找方法在有序表r中插入元素x，并保持表r的有序性，其中参数*n为表r的长度。请在空缺处填入合适的内容，使其成为一个完整的算法。voidBinInsert(SeqListr,int*n,DataTypex){intlow=1,high=*n,mid,i;while
