徐英-07计信（1）（2）大专-数据结构期末考试B卷.doc
3页
班级 姓名 学籍号 考 考 生 答 题 不 得 超 过 此 密 封 线编号：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、bdgcefha B、gdbecfha C、bdgaechf D、gdbehfca8、向一个有126个元素的顺序表中插入一个新元素并保存，原来顺序不变，平均要移动（ ）个元素A、8 B、63.5 C、63 D、79、如果最常用的操作是取第i个结点及其前驱，最节省时间的存储方式是（ ）A、单链表 B、双向链表C、单循环链表 D、顺序表10、按照二叉树的定义，具有3个结点的二叉树有_______种. A. 3 B. 4 C. 5 D. 611、深度为5的二叉树至多有（ ）个结点。
A、16 B、32 C、31 D、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 =p→next； B、p→next=p→next→next；C、p→next=p； D、p=p→next→next；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;i 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}，试给出相应的哈夫曼树，并计算其带权路径长度WPL4分）613254184231225208155103、分别用Prim算法和Kruskal算法求图的最小生成树，要求分别画出构造过程6分）5、给出下图中V1到其余各顶点的最短路径，并写出每条路径的源点，终点及路径长度5分）69 13 32 30 17 25 81345162176、已知序列{70，83，100，65，10，32，7，9}，请给出采用快速排序法对该序列作升序排序时的每一趟的结果5分）7、已知序列{30，50，60，35，86，10，40，45}，请给出采用堆排序法对该序列作升序排序时的每一趟的结果共6分）信息工程系《数据结构》期末试卷 第 1 页 共 3 页。
