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

1 卷号：湖北工业大学二/二一二学年第学期模拟考试数据结构试题（10 计算机本科）（120 分钟）题号一二三四五总分题分20 30 42 8 得分注意：学号、姓名和所在班级不写、不写全或写在密封线外者，试卷作废一、填空题（每小题2 分，共 20 分）1、设连通图G 中的边集E=(a，b)，(a，e)，(a，c)，(b，e)，(e，d)，(d，f)，(f，c)，则从顶点a出发可以得到一种深度优先遍历的顶点序列为abedfc结果不唯一)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，18，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、解决散列表冲突的两种方法是_开放地址法 _和 _链地址法 _二、选择题（每题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+N3 3、设有一个二维数组Amn，假设 A00 存放位置在644，A22 存放位置在676，每个元素占一个空间，问A33 存放位置是（）A688 B678 C692D696 4、设某棵二叉树中有2000 个结点，则该二叉树的最小高度为（）。

A.9 B.10 C.11D.12 5、设一组初始记录关键字序列(5，2，6，3，8)，以第一个记录关键字5 为基准进行一趟快速排序的结果为（）A.2，3，5，8，6 B.3，2，5，8，6 C.3，2，5，6，8D.2，3，6，5，8 6、对 n 个记录的文件进行快速排序，所需要的辅助存储空间大致为()A.O(1)B.O(n)C.O(1og2n）D.O(n2)7、若有 18 个元素的有序表存放在一维数组A19 中，第一个元素放A1 中，现进行二分查找，则查找A3的比较序列的下标依次为()A.1，2，3 B.9，5，2，3 C.9，5，3 D.9，4，2，38、设某哈夫曼树中有199 个结点，则该哈夫曼树中有（）个叶子结点A.99 B.100C.101 D.102 9、设顺序表的长度为99，则顺序查找的平均比较次数为（）A.99 B.49.5 C.50D.49 10、设有序表中的元素为(13，18，24，35，47，50，62)，则在其中利用二分法查找值为 24 的元素需要经过（）次比较A.1 B.2 C.3D.4 11、设顺序线性表的长度为30，分成 5 块，每块 6 个元素，如果采用分块查找，则其平均查找长度为（）。

总分核分人姓名一、密封线内不准答题二、姓名、学号、班级不许涂改，否则试卷无效三、考生在答题前应先将姓名、学号和班级填写在在指定的方框内四、试卷印刷不清楚，可举手向监考教师询问学号所在班级密封注 意名师资料总结-精品资料欢迎下载-名师精心整理-第 1 页，共 5 页 -2 A.6 B.11 C.5 D.6.512、设无向图中有n 个顶点，则该无向图中最多有（）条边A.n(n-1)/2B.n(n-1)C.n(n+1)/2 D.(n-1)/2 13、设某棵二叉树的中序遍历序列为ABCD，前序遍历序列为CABD，则后序遍历该二叉树得到序列为（）A.BADC B.BCDA C.CDAB D.CBDA 14、设有向无环图G中的有向边集合E=，则下列属于该有向图G的一种拓扑排序序列的是（）A.1，2，3，4B.2，3，4，1 C.1，4，2，3 D.1，2，4，3 15、设一组初始关键字记录关键字为(20，15，14，18，21，36，40，10)，则以20 为基准记录的一趟快速排序结束后的结果为()A.10，15，14，18，20，36，40，21 B.10，15，14，18，20，40，36，21 C.10，15，14，20，18，40，36，2l D.15，10，14，18，20，36，40，21 三、应用题（本大题共7 小题，每小题6 分，共 42 分）1、设无向图G（如图所示），要求：（1）求该图的深度优先遍历序列。

2）求该图的宽度优先遍历序列3）根据 Prim 算法求该图的最小生成树4）根据克鲁斯卡尔算法求该图的最小生成树5）以上算法都可得到生成树，各有什么特点？（1）假设以1 为起点：12345（或 14352,15432 等等）（2）假设以1 为起点：1 2 5 4 3(或 1 X X X 3,三个 X为 2、5、4 任意的一个序列，3 必须在最后)注意：（1）、（2）两个问题在不要求画邻接表或邻接矩阵时，其结果可以不唯一，但一旦要求画邻接表或邻接矩阵时，根据你画的邻接表或邻接矩阵所得到的深度优先遍历序列和宽度优先遍历序列应是唯一的3）由于本题的图不好画，我给一个相似的题目的答案，大家参考一下，抱歉4）由于本题的图不好画，我给一个相似的题目的答案，大家参考一下，抱歉5）深度优先遍历序列和宽度优先遍历序列得到的生成树不一定是最小生成树，普里姆和克鲁斯卡尔算法可以得到最小生成树，克鲁斯卡尔算法构造最小生成树的时间复杂度降为O(elog2e)由于它与 n 无关，只与e 有关，所以说克鲁斯卡尔算法适合于稀疏图Prim()算法中有两重for循环,所以时间复杂度为O(n2)，5 0 2 1 3 4 5(a)1 5 6 3 5 6 6 4 2 0 2 1 3 4 5(b)1 0 2 1 3 4 5(c)1 4 0 2 1 3 4 5(d)1 4 2 0 2 1 3 4 5(e)1 5 4 2 0 2 1 3 4 5(f)1 3 4 2 5 4 1 0 2 1 3 4 5(a)1 0 2 1 3 4 5(b)1 0 2 1 3 4 5(c)1 0 2 1 3 4 5(d)1 4 2(e)0 2 1 3 4 5 1 3 4 2 5 2 2 3 3 0 0 3 5 4 1 0 0 3 3 1 1 0 0 3 3 1 1 0 0 0 0 1 1 1 1 1 1 名师资料总结-精品资料欢迎下载-名师精心整理-第 2 页，共 5 页 -3 由于它与它与n 有关，只与e 无关，故适合稠密网。

2、设有一组初始记录关键字为(45，80，48，40，22，78)，要求：（1）构造一棵二叉排序树并给出构造过程；（2）插入结点44,41,70,66，画出每插入一个结点的二叉排序树3）删除结点45,40,78，画出每删除一个结点的二叉排序树4）计算该二叉排序树的平衡因子1）（2）（3）（4）3、如下图所示，要求：（1）写出该树的前序、中序、后序遍历2）树的度是多少？树的深度是多少？以结点B 为根的子树的深度是多少？（3）度为 0、1、2 的结点分别是哪些？（4）画出与下列二叉树对应的森林5）求该森林的前序遍历和后序遍历1）前序：EIJGBKACFD 中序：IGJEKBFCDA 45 45 80 48 45 80 48 45 80 40 48 45 80 40 220 48 45 80 40 220 78 48 45 80 40 220 78 44 48 45 80 40 220 78 44 410 48 45 80 40 220 78 44 410 700 48 45 80 40 220 78 44 410 700 660 48 44 80 40 220 78 41 700 660 48 44 80 22 78 41 700 660 48 44 80 22 70 41 660 48 44 80 22 70 41 660 0-1 0 1-2 3-2 名师资料总结-精品资料欢迎下载-名师精心整理-第 3 页，共 5 页 -4 后序:GJIKFDCABE（2）树的度为2，深度为5，以结点B 为根的子树的深度是4。

3）度为 0 的结点有G、K、F、D；度为 1 的结点有 I、J、A；度为 2 的结点有E、B、C4）（5）该森林的前序遍历：EIJGBKACFD 该森林的后序遍历：IGJEKBFCDA 4.写出下面程序的结果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，另外标注红色的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）=3，H（78）=0，H（31）=5，H（15）=2，H（36）=10 利用线性探查法造表：0 1 2 3 4 5 6 7 8 9 10 11 12 78 15 03 57 45 20 31 23 36 12 1 1 1 1 1 1 4 1 2 1 搜索成功的平均搜索长度为：ASLsucc=1/10（1+1+1+1+1+1+4+1+2+1）=14/10搜索不成功的平均搜索长度为：ASLunsucc=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）求 WPL3）为这 7 个字母设计哈夫曼编码；（4）对这 7 个字母进行等长编码，至少需要几位二进制数？（5）哈夫曼编码比等长编码使电文总长压缩多少？（1）（2）WPL=(0.04+0.08)*4+(0.10+0.11+0.16)*3+(0.20+0.31)*2=2.61（3）a:11;b:101;c:010;d:1001;e:011;f:00;g:100。