04软件工程数据结构期末试卷3352

《04软件工程数据结构期末试卷3352》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、04软件工程数据结构期末试卷33523、人的影响短暂而微弱，书的影响则广泛而深远——普希金　　　　　华南农业大学期末考试试卷（A卷）　　　　2004学年第1学期　考试科目：数据结构（04软件工程）　　　　　　　　考试类型：（闭卷）考试时间：120分钟　　　　学号姓名年级专业题号一二三四总分得分评阅人说明：1本试卷的答案必须写在答题卡上，答题卡同时写上专业、班级、学号、姓名；一、选择题（每题2分，共30分）1.hh设子串s1='ABCDEFG'，s2='PQRST'，函数con(x,y)返回x和y串的连接

2、串，subs(s,i,j)返回串s的从序号i的字符开始的j个字符组成的子串，len(s)返回串s的长度，则　　con(subs(s1,2,len(s2),subs(s1,len(s2),2))的结果串是（）　　　　　　A．BCDEFB．BCDEFG　　　C．BCPQRSTD．BCDEFEF2.某堆栈的输入序列为a，b，c，d，下面的四个序列中，_________不可能是它的输出序列　　　A．a，c，b，dB．b，c，d，a　　　C．c，d，b，aD．d，c，a，b3.将长度为n的单链表链接在长度为m的单

3、链表之后的算法的时间复杂度为_________.　　A．0（1）B．0（n）C．0（m）D．0（m+n）4.长度为n（1...n）的顺序循环队列中，front和rear分别指示队首和队尾判断队列满的条件为_________.A．rear%n=frontB．front%n+1=rearC．rear%n-1=frontD．rear%n+1=front5.设二叉树有2n个结点，则对于m0个结点的二叉

4、树的先序序列正好相反，则该二叉树一定不是_________的二叉树A．任一结点无左孩子B．任一结点无右孩子C．深度为nD．存在度为2的结点7.二叉树用二叉链表表示，若要将其所有结点的左，右子树相互交换位置，则采用下列--遍历的方法较为合适A．先序B．中序C．后序D．按层8.对于二叉树的两个结点X和Y，应该选择_________两个序列来判断X是否Y的祖先A．先序和后序B．先序和中序C．中序和后序D．任意两个序列都行9.最小生成树指的是连通图中_________.A．边数最少的生成树B．顶点相对较少的生成

5、树C．极小连通子图D．所有生成树中权值之和最小的生成树10.具有n个顶点的强连通图至少有_________条弧A．n-1B．nC．2nD．n（n-1）11.对20个有序记录进行折半查找，查找成功的平均查找长度为_________.A．5B．37/10C．39/10D．41/1012.哈希表长度为m，哈希函数H（K）=K%P，一般来说P应取小于m的最大_________.A．奇数B．偶数C．素数D．合数13.对动态查找有高效率的查找表组织结构是_________.A．有序表B．分块有序表C．循环链表DB-

6、树14.当初始数据有序时，不应采用_________.A．堆排序B．快速排序C．基数排序D．希尔排序15.在n个元素中找出两个最小的元素，当n很大时，采用_________方法比较次数较少A．树型选择排序B．简单选择排序C．归并排序D．快速排序二、填空题（每空1分，共15分）1.一个算法的效率可分为效率和效率2.向一个长度为n的向量的第i个元素(1≤i≤n+1)之前插入一个元素时，需向后移动________个元素3.在具有n个单元的循环队列中，队满时共有个元素4.假设有二维数组A6×8，每个元素用相邻的

7、6个字节存储，存储器按字节编址已知A的起始存储位置（基地址）为1000，则数组A的体积（存储量）为；末尾元素A57的第一个字节地址为；若按行存储时，元素A14的第一个字节地址为；若按列存储时，元素A47的第一个字节地址为5.设一棵完全二叉树具有1000个结点，则此完全二叉树有个叶子结点，有个度为2的结点，有个结点只有非空左子树，有个结点只有非空右子树6.10、线性有序表（a1，a2，a3，...，a256）是从小到大排列的，对一个给定的值k，用二分法检索表中与k相等的元素，在查找不成功的情况下，最多需要

8、检索次设有100个结点，用二分法查找时，最大比较次数是7.散列法存储的基本思想是由决定数据的存储地址三、应用题(共40分)1.假设一棵二叉树的层次遍历序列是ABCDEFGHIJ和中序遍历序列是DBGEHJACIF,请画出该树（5分）2.已知一个图的顶点为A、B、C、D，其邻接矩阵的上三角元素全为0（包括主对角线元素），其他元素均为1请画出该图，并给出其邻接表（5分）3.给定权值{8，12，4，5，26，16，9}，构造一棵带权路径长度最短的