徐英-07计信（1）（2）大专-数据结构期末考试B卷.doc

班级 姓名 学籍号 考 考 生 答 题 不 得 超 过 此 密 封 线编号：QMSD/JWC-21-01 数据结构期 末 试卷（B卷）（ 2008 / 2009 学年度第 二 学期）用卷班级07计信1五班07计信2五班班级编号07410742班级人数4138命 题 人徐英审核人王香菊核 对 人徐英一、填空题（选择题（将答案写在题后的方框内）（每题2分，共40分）1、一个向量第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是（ ）。A、110 B、108 C、100 D、1202、树最适合用来表示（ ）。A、有序数据元素B、无序数据元素C、元素之间具有分支层次关系的数据D、元素之间无联系的数据3、一棵二叉排序树T，用( )方法进行遍历，可以得到各结点键值的递增序列。 A、先根遍历B、中根遍历C、层次遍历D、后根遍历4、在下述的排序方法中，不属于内部排序的是 。A、选择排序法 B、插入排序法 C、拓扑排序法 D、归并排序法5、一棵二叉排序树T，用( )方法进行遍历，可以得到各结点键值的递增序列。 A、先根遍历B、中根遍历C、层次遍历D、后根遍历6、线性表中，只有直接前驱而无后继的元素是（ ）。A、尾元素B、首元素C、所有中间的元素D、全部元素7、已知某二叉树的前序遍历序列是abdgcefh，中序遍历序列是dgbaechf，则它的后序遍历序列是（ ）。A、bdgcefhaB、gdbecfhaC、bdgaechfD、gdbehfca8、向一个有126个元素的顺序表中插入一个新元素并保存，原来顺序不变，平均要移动（ ）个元素。A、8B、63.5C、63D、79、如果最常用的操作是取第i个结点及其前驱，最节省时间的存储方式是（ ）。A、单链表B、双向链表C、单循环链表D、顺序表10、按照二叉树的定义，具有3个结点的二叉树有_种. A. 3 B. 4 C. 5 D. 611、深度为5的二叉树至多有（ ）个结点。A、16B、32C、31D、1012、算法指的是（ ）。A、计算机程序B、解决问题的计算方法C、排序算法D、解决问题的有限运算序列13、以下何种排序是稳定的？（ ）A、直接插入排序 B、希尔排序C、快速排序 D、直接选择排序14、一组记录的关键码为（46，79，56，38，40，84），则利用快速的方法，以第一个记录为基准得到的一次划分结果为（ ）A、38，40，46，56，79，84B、40，38，46，79，56，84C、40，38，46，56，79，84D、40，38，46，84，56，7915、在单链表中，指针p指向元素为x的结点，实现“删除x的后继”的语句是（ ）。A、p =pnext；B、pnext=pnextnext；C、pnext=p；D、p=pnextnext；16、在( )运算中，使用顺序表比链表好。 A、插入 B、删除 C、根据序号查找 D、根据元素值查找17、线性表是一个（ ）。A、有限序列，可以为空B、有限序列，不能为空C、无限序列，可以为空D、无限序列，不能为空18、一个有n个顶点的无向图最多有（ ）条边。A、n B、n (n-1) C、n (n-1)/2 D、2n19、对线性表进行折半查找时，要求线性表必须（ ）。A、以顺序方式存储B、以链接方式存储C、以顺序方式存储，且结点按关键字有序排列D、以链接方式存储，且结点按关键字有序排列20、堆是( )。 A、完全二叉树 B、线性表 C、二叉排序树 D、平衡二叉树题号12345678910答案题号11121314151617181920答案二、填空（每空1分，共30分）1、组成数据的基本单位是 ，最小单位是 。2、算法的五个重要特性是 、 、 、 、 。3、数据的存储结构主要分为 和 两种。4、下面程序段的时间复杂度是 。for(i=0;in;i+) for(j=0;jm;j+) Aij=0;5、栈的特点是 ，队列的特点是 ，栈和队列都属于 结构。6、图定义为：G=(V，E)，其中，V是_的集合，E是_的集合。k1k2k3k4k5k6k77、有一棵树如图所示，请回答以下问题：（1）这棵树的根结点是_；（2）这棵树的叶子结点是_；（3）这棵树的深度是_；（4）结点k3的孩子结点是_；（5）结点k3的双亲结点是_；8、在任意二叉树中，若叶子结点的个数为n0，度为1的结点数为n1，度为2的结点数为n2，则满足关系 。9、二叉树的遍历有3 种序列 、 、 。 图的遍历方法_和_。10、已知某二叉树的后序遍历是dabec，中序遍历为debac,则它的前序遍历为 。11、图有两种基本的存储结构分别是 和邻接表12、按照排序过程中存储器的不同，可将排序分为 和 。三、综合题（30分）1、（1）将树转换成二叉树。（2）将二叉树转换成森林。（1）（2）2、对于权值W=14，15，7，4，20，2，试给出相应的哈夫曼树，并计算其带权路径长度WPL。（4分）613254184231225208155103、分别用Prim算法和Kruskal算法求图的最小生成树，要求分别画出构造过程。（6分）5、给出下图中V1到其余各顶点的最短路径，并写出每条路径的源点，终点及路径长度。（5分）69 13 32 30 17 25 81345162176、已知序列70，83，100，65，10，32，7，9，请给出