网络工程数据结构试卷及答案

1、总分所在班级注意核分人数据结构试题题号一二三四五总分题分2030428得分（10计算机本科）（120分钟）一、密封线内不准答题。二、姓名、学号、班级不许涂改，否则试卷无效。三、考生在答题前应先将姓名、学号和班级填写在在指定的方框内。四、试卷印刷不清楚，可举手向监考教师询问。卷号湖北工业大学二。一一/二。一二学年第一学期模拟考试注意：学号、姓名和所在班级不写、不写全或写在密封线外者，试卷作废。一、填空题（每小题2分，共20分）1、设连通图 G 中的边集 E=（a，b），（a，e），（a，c），（b，e），（e，d），（d，f），（f， c），则从顶点a出发可以得到一种深度优先遍历的顶点序列为ab

2、edfc 。（结 果不唯一）2、设一组记录关键字序列为（80，70，33，65，24，56，48），则用筛选法建成的 初始堆为（24，65，33，80，70，56，48）。3、对一组初始关键字序列（40，50，95，20，15，70，60，45，10）进行冒泡排 序，则第一趟需要进行相邻记录的比较的次数为_8，在整个排序过程 中最多需要进行 6趟排序才可以完成。4、设一组初始记录关键字序列为（49, 38，65，97，76，13，27，50），则以d=4为增量的一趟希尔排序结束后的结果为（49, 13, 27, 50，76, 38, 65, 97）_。5、设一组初始记录关键字序列为（20, 1

3、8, 22, 16, 30, 19）,则根据这些初始关键字序列建成的初始堆为（16, 18, 19, 20, 32, 22）。6、设有向图G的存储结构用邻接矩阵A来表示，则A中第i行中所有非零元素个数之和等于顶点i的出度,第i列中所有非零元素个数之和等于顶点 i的 入度。7、 在快速排序、堆排序、归并排序中，归并 排序是稳定的。（冒泡、插 入、归并和基数排序是稳定的；选择、快速、希尔和堆排序是不稳定的。）8、设查找表中有100个元素，如果用二分法查找方法查找数据元素X,则最多需要比较7次就可以断定数据元素X是否在查找表中。9、简单选择排序和直接插入排序算法的平均时间复杂度为一 O（n2）10、

4、解决散列表冲突的两种方法是 开放地址法和链地址法二、选择题（每题2分，共30分）1、下列程序段的时间复杂度为（）。i=0, s=0； while （sn） s=s+i； i+； A.O（n1/2）B.O（n1/3）C. O（n）D. O（n2）2、设F是由T1、T2和T3三棵树组成的森林，与F对应的二叉树为B, T1、T2 和T3的结点数分别为N1、N2和N3，则二叉树B的根结点的左子树的结点数为（）。A. N1-1 B. N2-1 C. N2+N3 D. N1+N33、设有一个二维数组Amn，假设A00存放位置在644, A存放位置在 TOC o 1-5 h z 676,每个元素占一个空间，

5、问A33存放位置是（）A. 688B. 678C. 692D. 6964、设某棵二叉树中有2000个结点，则该二叉树的最小高度为（）。A. 9B.10C.11D.125、设一组初始记录关键字序列（5, 2, 6, 3, 8）,以第一个记录关键字5为基准进 行一趟快速排序的结果为（）。A.2, 3,5, 8, 6B. 3,2,5,8, 6C. 3, 2,5, 6, 8D. 2,3,6,5, 86、 对n个记录的文件进行快速排序，所需要的辅助存储空间大致为（）A. O（1） B. O（n） C. O（1og2n）D. O（n2）7、若有18个元素的有序表存放在一维数组A19中，第一个元素放A1中，

6、现进行二分查找，则查找A 3的比较序列的下标依次为（）A. 1,2,3B. 9,5,2,3C. 9,5,3D. 9,4,2,38、设某哈夫曼树中有199个结点，则该哈夫曼树中有（）个叶子结点。A.99B. 100 C.101D. 1029、设顺序表的长度为99,则顺序查找的平均比较次数为（）。A. 99B. 49.5C.50D. 4910、设有序表中的元素为（13, 18, 24, 35, 47, 50, 62），则在其中利用二分法查 找值为24的元素需要经过（）次比较。A. 1B. 2C. 3D. 411、设顺序线性表的长度为30,分成5块，每块6个元素，如果采用分块查找， 则其平均查找长度

7、为（）。A. 6B. 11C. 5D. 6.512、设无向图中有n个顶点，则该无向图中最多有（）条边。A .n（n-1）/2 B. n（n-1） C. n（n+1）/2 D, （n-1）/213、设某棵二叉树的中序遍历序列为ABCD,前序遍历序列为CABD，则后序遍 历该二叉树得到序列为（）。A. BADC B.BCDA C. CDABD. CBDA14、设有向无环图G中的有向边集合E=，则 下列属于该有向图G的一种拓扑排序序列的是（）。A,1，2，3，4B.2，3，4，1深度优先遍历序列和宽度优先遍历序列应是唯一的。（3）由于本题的图不好画，C, 1，4，2，3D.1，2，4，315、设一组

8、初始关键字记录关键字为（20，15，14，18，21，36，40，10），则以20为基准记录的一趟快速排序结束后的结果为（）。A.10，15,14,18,20,36,40,21B.10，15,14,18,20,40,36,21C.10，15,14,20,18,40,36,2lD.15,10，14,18,20,36,40,21我给一个相似的题目的答案，三、应用题（本大题共7小题，每小题6分，共42分）1、设无向图G （如图所示），要求：（1）求该图的深度优先遍历序列。（2）求该图的宽度优先遍历序列。（3）根据Prim算法求该图的最小生成树。（4）根据克鲁斯卡尔算法求该图的最小生成树。（5）以上算

9、法都可得到生成树，各有什么特点？（4）由于本题的图不好画，我给一个相似的题目的答案，大家参考一下，抱歉。(c)（1）假设以 1 为起点：12345 （或 14352,15432 等等）（2）假设以1为起点：1 2 5 4 3 或 1 X X X 3,三个X为2、5、4任意的一个序 列，3必须在最后）注意：（1）、（2）两个问题在不要求画邻接表或邻接矩阵时，其结果可以不唯 一，但一旦要求画邻接表或邻接矩阵时，根据你画的邻接表或邻接矩阵所得到的（5）深度优先遍历序列和宽度优先遍历序列得到的生成树不一定是最小生成树， 普里姆和克鲁斯卡尔算法可以得到最小生成树，克鲁斯卡尔算法构造最小生成树 的时间复杂

10、度降为O（elog2e）。由于它与n无关，只与e有关，所以说克鲁斯卡 尔算法适合于稀疏图。Prim（）算法中有两重for循环，所以时间复杂度为O（n2），由于它与它与n有关，只与e无关，故适合稠密网。2、设有一组初始记录关键字为（45, 80, 48, 40, 22, 78）,要求:（1）构造一棵二叉排序树并给出构造过程；（2）插入结点44,41,70,66，画出每插入一个结点的二叉排序树。（3）删除结点45,40,78，画出每删除一个结点的二叉排序树。（4）计算该二叉排序树的平衡因子。3、如下图所示，要求：（1）写出该树的前序、中序、后序遍历。（2）树的度是多少？树的深度是多少？以结点B为根

11、的子树的深度是多少?（3）度为0、1、2的结点分别是哪些？（4）画出与下列二叉树对应的森林。（5）求该森林的前序遍历和后序遍历。后序：GJIKFDCABE（2）树的度为2,深度为5,（3）度为0的结点有G、K、以结点B为根的子树的深度是4。F、D；度为1的结点有I、J、A；度为2的结点有=3， H （78） =0, H （31） =5, H （15） =2, H （36） =10 利用线性探查法造表：E、B、C。0123456789101112781503574520312336121111114121（5）该森林的前序遍历：EIJGBKACFD该森林的后序遍历：IGJEKBFCDA写出下面程

12、序的结果。typedef int datatype;typedef struct node datatype data; struct node *next;lklist;void delredundant(lklist *&head)lklist *p,*q,*s;for(p=head;p!=0;p=p-next)for(q=p-next,s=p;q!= 0;)if (q-data=p-data) s-next=q-next; free(q);q=s-next;else s=q,q=q-next;答：在不带头结点的单链表中删除值相同数据元素的算法。(原始卷中s=q要改为s=p，另外标注红色的

13、0其实就是NULL）5、设散列表为HT13,散列函数为H （key） =key%13。用闭散列法解决冲突，对 下列关键码序列 12, 23, 45, 57, 20, 03, 78, 31, 15, 36 造表。（1）采用线性探查法寻找下一个空位，画出相应的散列表。（2）计算等概率下搜索成功的平均搜索长度和搜索不成功的平均搜索长度。答案：使用散列函数H（key）二key mod 13有：H（12）=12，H（23）=10，H（45）=6, H（57）=5, H（20）=7, H（03）搜索成功的平均搜索长度为：ASL =1/10 （1+1+1+1+1+1+4+1+2+1） =14/10搜索不成功

14、的平均搜索长度为：AS、。=1/13（2+1+3+2+1+5+4+3+2+1+5+4+3）=36/136、假设用于通信的电文由字符集a,b,c,d,e,f,g中的字母构成。它们在电文中 出现的频度分别为0.31,0.16,0.10,0.08,0.11,0.20,0.04,（1）画出哈夫曼树。（2）求 WPL。（3）为这7个字母设计哈夫曼编码；（4）对这7个字母进行等长编码，至少需要几位二进制数？（5）哈夫曼编码比等长编码使电文总长压缩多少？a:11 ;b:101; c:010 ;d:1001;e:011;f:00;g:1000对这7个字母进行等长编码，至少需要3位二进制数。0.31+0.08+

15、0.10+0.11+0.16+0.04+0.20=1(0.31*2+0.20*2+0.10*3+0.11*3+0.16*3+0.04*4+0.08*4)/3=87%压缩了 13% 7、设有序顺序表中的元素依次为017, 094, 154, 170, 275,503, 509, 512, 553, 612, 677, 765, 897, 908。试画出对其进行折半搜索时的判定树。并计算搜索成功的平均搜索长度和搜索不成功的平均搜索长度。若有n个有序数据元素，则查找不成功最大查找深度为多少？答案：折半搜索时的判定树为：ASL =1/14 (1+2*2+3*4+4*7) =45/14ASL；=1/15(3*1+4*14)=59/15else if (p-data=0 & p-datanext=hb; hb=p; p-next=hc; hc=p;else若有N个有序数据元素，则查找不成功最大查找深度为 ceiling(log2N)+1,ceiling()表示天花板函数，也可以是floor(log2(N+1)+1， floor()是地板函数四、算法设计题(本大题共1小题，每小题8分，共8分)1、设单链表中有仅三类字符的数据元素(大写字母、数字和其它字符)，要求利用 原单链表中结点空间设计出三个单链表的算法，使每个单链表只包含同类字