《数据结构与算法》模拟试卷.docVIP

《数据结构与算法》模拟试卷六 一、名词解释（5*3=15分） AOV网 队列 栈 哈夫曼树 生成树 二、 填空题（1*16=16分）L=p; p-next=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-i B、n-i+1 C、n-i-1 D、i 3. 在一个顺序队列中，队首指针指向队首元素的 位置。_____。 A、当前 B、后一个 C、前一个 D、后面 4. n个结点的线索二叉树中线索的数目为_____。 A、(n-1)个 B、n个 C、（n+1）个 D、(n+2)个 5. 设数组A[m]为循环队列Q的存储空间，front为队头指针，rear为队尾指针，则判定Q为空队列的条件是_____。 A.(rear-front)%m= =1 B.front= =rear C.(rear-front)%m= =m-1 D.front= =(rear+1)%m 假设一棵完全二叉树按层次遍历的顺序依次存放在数组BT[m]中，其中根结点存放在BT[0]，若BT[i]中的结点有左孩子，则左孩子存放在_____。 A.BT[i/2] B.BT[2*i-1] C.BT[2*i] D.BT[2*i+1] 连通图是指图中任意两个顶点之间_____。 A.都连通的无向图 B.都不连通的无向图 C.都连通的有向图 D.都不连通的有向图 左图所示带权无向图的最小生成树的权为 。 A.14 B.15 C.17 D.18 栈的插入和删除操作在_____进行。A.栈顶 B.栈底 C.任意位置 D.指定位置 以下说法正确的是 。 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．使用普里姆算法构造如下图所示的图G的一棵最小生成树。（画出构造过程） 3．待排序关键字（34,12,28,45,66,7,3,21），写出希尔排序的每趟结果。 五、算法填空（9*2=18分） 1.如果希望循环队列中的向量单元都能得到利用，则可设置一个标志域tag,每当尾指针和头指针值相同时，以tag的值为0或1来区分队列状态是“空”还是“满”。请对下列函数填空，使其分别实现与此结构相应的入队列和出队列的算法。 int EnQueue(CirQueue *Q,DataType x){ if( (1) ) return 0; Q-data[Q-rear]=x; Q-rear=(Q-rear+1)% MAXQSIZE (2) return 1; } int DeQueue(CirQueue *Q,DataType *x){ if( (3) ) return 0; *x=Q-data[Q-front]; Q-front= (4) ; (5) ; return 1; } (1) (2) (3) (4) (5) 2.下列算法利用二分查找方法在有序表r中插入元素x，并保持表r的有序性，其中参数*n为表r的长度。请在空缺处填入合适的内容，使其成为一个完整的算法。 void BinInsert(SeqList r,int *n,DataType x) { int low=1,high=*n,mid,i; while(low=high) { mid= (1) ; if (x.keyr[mid].key)high=mid-1; else (2) ; } for(i=*n; (3) ;i--) r[i+1]=r[i]; (4) ; *n++; } (1) (2) (3) (4) 六、算法设计题（2*10=20分） 编写递归算法，将二叉树中所有结点的左右子树相互交换。 给出图的邻接表存储结构，编写一深度优先遍历算法实现对存放在邻接表中图遍历。