天津理工大学数据结构期末考试复习试卷.pdf

《天津理工大学数据结构期末考试复习试卷.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、一、单项选择题（每小题2分，共30分）1、程序段s=i=0;do{i=i+1;s=s+i;}while(i<=n);的时间复杂度为(A)。22A.O(n)B.O(nlog2n)C.O(n)D.O(n/2)2、在单链表指针为p的结点之后插入指针为s的结点，正确的操作是：（B）。A．p->next=s;s->next=p->next;B．s->next=p->next;p->next=s;C．p->next=s;p->next=s->next;D．p->next=s->next;p->next=s;3、假设以数组A[m]存放循环队列的元素,其头尾指针分别为front和re

2、ar，则当前队列中的元素个数为（A）。A．(rear-front+m)%mB．rear-front+1C．(front-rear+m)%mD．(rear-front)%m4、对N个元素的表做顺序查找时，若查找每个元素的概率相同，则平均查找长度为(A)A．（N+1）/2B.N/2C.ND.[（1+N）*N]/25、在图采用邻接表存储时，求最小生成树的Prim算法的时间复杂度为(B)。23A.O(n)B.O(n+e)C.O(n)D.O(n)6、设森林F对应的二叉树为B，它有m个结点，B的根为p,p的右子树结点个数为n,则森林F中第一棵树的结点个数是（A）A．m-nB．m-

3、n-1C．n+1D．m+n7、在有向图G的拓扑序列中，若顶点Vi在顶点Vj之前，则下列情形不可能出现的是（D）。A．G中有弧B．G中有一条从Vi到Vj的路径C．G中没有弧D．G中有一条从Vj到Vi的路径8、一棵非空的二叉树的先序遍历序列与后序遍历序列正好相反，则该二叉树一定满足（C）A．所有的结点均无左孩子B．所有的结点均无右孩子C．只有一个叶子结点D．是任意一棵二叉树9、下面关于二分查找的叙述正确的是(D)A.表必须有序，表可以顺序方式存储，也可以链表方式存储B.表必须有序且表中数据必须是整型，实型或字符型C.表必须有序，而且只能从小到大

4、排列D.表必须有序，且表只能以顺序方式存储10、要连通具有n个顶点的有向图，至少需要（B）条边。A．n-lB．nC．n+lD．2n11、下列排序算法中，其中（D）是稳定的。A.堆排序，冒泡排序B.快速排序，堆排序C.直接选择排序，归并排序D.归并排序，冒泡排序11、设abcdef以所给的次序进栈，若在进栈操作时，允许退栈操作,则得不到的序列为（D）。A．fedcbaB.bcafedC.dcefbaD.cabdef12、下列数据中，（C）是非线性数据结构。A．栈B.队列C.完全二叉树D.堆13、一组记录的关键码为（46，79，56，38，40，84），则利用快速排序的方

5、法，以第一个记录为基准得到的一次划分结果为（C）。A．(38,40,46,56,79,84)B.(40,38,46,79,56,84)C．(40,38,46,56,79,84)D.(40,38,46,84,56,79)14、下列叙述中，不符合m阶B树定义要求的是（D）。A.根节点最多有m棵子树B.所有叶结点都在同一层上C.各结点内关键字均升序或降序排列D.叶结点之间通过指针链接15、设A是n*n的对称矩阵，将A的对角线及对角线上方的元素以列为主的次序存放在一维数组B[1..n(n+1)/2]中，对上述任一元素aij(1≤i，j≤n，且i≤j)在B中的位置为(B)。A.

6、i(i-l)/2+jB.j(j-l)/2+iC.j(j-l)/2+i-1D.i(i-l)/2+j-1二、计算分析题（共40分）1、（10分）设用于通讯的电文仅由8个字母组成，他们在电文中出现的频率分别为0.30，0.07，0.10，0.03，0.20，0.06,0.22，0.02。（1）试设计哈夫曼树及其编码。（2）若使用0-7的二进制表示形式是另一种编码方案。给出两种编码的对照表、带权路径长度WPL值并比较两种方案的优缺点2、（5分）设散列表的长度为15，散列函数H(K)=K%13，给定的关键字序列为20，16，29，82，37，02，06，28，55，39，23，

7、10，试写出用线性探测法解决冲突时所构造的散列表，并求出在等概率情况下，查找成功时的平均查找长度。3、（10分）根据下面的无向加权图：（1）写出它的邻接矩阵；（2）按Prim算法求其最小生成树。4、（10分）设记录关键字集合K={28，17，85，96，75，8，42，65，4}（1）写出对K进行“二路归并”且按关键字递增次序排序时，各趟排序的结果；（2）将K建成一个完全二叉树形式的最小堆。5、（5分）依次删除下面AVL树中关键字g和m，画出调整过程（如果需要的话），画出最终结果，标出每个节点的平衡因子。三、算法设计题（共30分）1、（6分）下面程序