试卷代号：1010 座位■ 中央广播电视大学2010一2011学年度第二学期“开放本科”期末考试 数据结构 试题 2011年7月 题 号 二 三 四 五 六 总分 分 数 得 分 评卷人 一、单项选择题（在括号内填写所选择的标号。每小题2分，共18 分) 1.一种抽象数据类型包括数据和( )两个部分。 A.数据类型 B.操作 C.数据抽象 D.类型说明 2.在-一个长度为n的顺序表的表尾插入一个新元素的时间复杂度为()。 A.O(1) B.O(n) C.O(n2) D.O(log2n) 3.已知L是带表头附加结点的单链表，删除第一个元素结点的语句是( )。 A.L L->link; B.L->link =L->link->link; C.L->link->link =L; D.L->link L; 4.在下列广义表中，()又是一个线性表。 A.E(a,(b,c)) B.E(a,E) C.E(a,b) D.E(a,()) 5.在一棵深度为3的三叉树中，最多含有( )个结点。假定树根结点的深度为1。 A.10 B.11 C.12 D.13 75
试卷代号 座位号 II 中央广播电视大学 1学年度第二学期"开放本科"期末考试 数据结构试题 2011 年7 !题号 - |分数 I I ·1 1- I ---1 I 得分|评卷人 一、单项选择题(在括号内填写所选择的标号。每小题 2分，共 分) 1. 种 抽 )两个部分。 A. 型B. c. 2. 在 一 )。 f\. OC 1) B. O(n) c. O(n2 ) D. O(log2n) 3. 知L 链表 一个 )。 A. L = 1.，一 c. L->link 一>link = L. B. L->1ink = 一>link 一>link; D. 一>link = L; 4. 在下 A. E ( a , (b , c) ) C. E(a , b) )又是一个线性表。 B. E(a ,E) D. E(a , ( » 5. 在一 为3 叉 树 )个结点 o假定树根结点的深度为 1。 A. 10 B. 11 c. 12 D. 13 75
6.向一棵AVL树插入元素时，可能引起对最小不平衡子树的双向旋转的调整过程，此 时需要修改相关()个指针域的值。 A.2 B.3 C.4 D.5 7.在一个具有n个顶点的有向图的邻接矩阵表示中，删除一条边需要的时间复杂 度为( )。 A.O(1) B.O(i) C.O(n) D.O(n2) 8.在一棵B树中，当插人一个元素时，若最终引起树根结点的分裂，则新树的高度比原 树的高度()。 A.减1 B.减2 C.增1 D.增2 9.对存储有n个元素的长度为m的散列表进行搜索，平均搜索长度与()有关。 A.n B.m C.n/m D.n*m 得 分 评卷人 二、填空题（在横线处填写合适的内容。每小题2分，共14分） 1.链表只适用于 查找。 2.归并排序算法的时间复杂度为 3.在一个链式队列中，若队头指针与队尾指针的值相同，则表示该队列至多有 个结点。 4.假定一棵树的广义表表示为a(b,c,d(e,f),g(h),则结点f的层数为 假定 树根结点的层数为0。 5.从一棵二叉搜索树中搜索一个元素时，若给定值大于根结点的值，则需要向根的 继续搜索。 76
6. 棵AVL 树插入元 对最小 整过程 时需要修改相关( )个指针域的值。 A. 2 c. 4 B. 3 D. 5 7. 邻 接 一条 需要 度为( )。 A.O(l) B.O(i) C.O(n) D. 0(n2 ) 8. 棵B 插入 起 树根 新树 树的高度( )。 A. 减1 B. 减2 c. D. 增2 9. 对存 索长度 )有关。 A. n c. n/m 得分|评卷人 B. m D. 长m 二、填空题(在横线处填写合适的内容。每小题 1. 2. 序 算 法 杂度 3. 尾 指 个结点 4. 广 义 为a ，c , g (h) ) ，则结点 f的层数为。假定 树根结点的层数为 5. 搜 索 素 时 给 定 继续搜索。 76
6.每次从第ⅰ至第个元素中顺序挑选出一个最小元素，把它交换到第i个位置，此种排 序方法叫做 排序。 7.快速排序在最坏情况下的时间复杂度为 得 分 评卷人 三、判断题（在每小题后面的括号内打对号“√”表示叙述正确或打叉 号“×”表示叙述错误。每小题2分，共14分) 1.若每次从队列中取出的是具有最高优先权的元素，则称此队列为优先级队列。 () 2.递归定义的数据结构通常不需要采用递归的算法对其运算。() 3.当从一个最小堆中删除一个元素时，需要把堆尾元素填补到堆顶位置，然后再按条件 把它逐层向下调整，直到调整到合适位置为止。() 4.对于一棵具有n个结点、高度为h的二叉树，进行任一种次序遍历的时间复杂度均为 O(n)。() 5.对于同-一组记录集合，生成二叉搜索树的形态与插人记录的次序无关。（) 6.装载因子是散列存储中的一个重要指标，它反映了散列表的装满程度。() 7.在一棵B树中，所有叶结点都处在同一层上。() 得分 评卷人 四、运算题（每小题6分，共30分）】 1.假定一棵普通树的广义表表示为a(b(e),c(f(h,i,j),g)),分别写出对其进行先根和按 层遍历的结果。 先根： 按层： 2.假定一个线性表为(38,52,25,74,68,16,30)，根据此表中的元素排列次序生成一棵二 叉搜索树，求出该二叉搜索树中分支结点数和叶子结点数。 分支结点数： 叶子结点数： 77
6. 次从 挑选 个最 序方法叫做排序。 7. 快速 最坏 复 杂度 得分|评卷入 三、判断题(在每小题后面的括号内打对号"飞 "表示叙述正确或打叉 "表示叙述错误。每小题 2分，共 4分) 1. 优先 ( ) 2. 通 常 ) 3. 位 置 然 后 把它逐层向下调整，直到调整到合适位置为止。( ) 4. 高 度 一 种 O(n) 0 ( ) 5. 索树 形态 插入记 ) 6. 装 载 存储 它反 映 满 程 ) 7. 在 一棵B 处在 ) 得分|评卷人 四、运算题(每小题 6分，共 0分) 1. 假定 广 义 表表 为a(b(e) , c(f( h, i, j ) »，分别写出对其进行先根和按 层遍历的结果。 先根: 按层: 2. 一个 性表 为(38 ，52 ，25 ，74 ，16 ，30) 根据此 成一 叉搜索树，求出该二叉搜索树中分支结点数和叶子结点数 分支结点数: 叶子结点数: 77
3.已知一个数据集合为{28,12,16,49,34,30}，试把它调整为一个最大堆。 最大堆： 4.已知一个图的顶点集V和边集G分别为： V={1,2,3,4,5}; E={,,,,,,,, }； 假定此图采用邻接矩阵表表示，根据图的遍历算法分别写出从顶点1出发进行深度优先 搜索和广度优先搜索所得到的顶点序列。 深度优先搜索序列： 广度优先搜索序列： 5.设散列表的长度m=7,散列函数为H(K)=K mod m,若采用线性探查法解决冲突， 待依次插入的关键码序列为{19,14,23,68,20}，试求出最后得到的散列表。 0 1 234 56 得 分 评卷人 五、算法分析题（每小题8分，共16分） 1.下面算法的功能为：将两个有序单链表合并成一个有序单链表并返回其表头指针。阅 读算法，在划有横线的上面填写合适的内容。 ListNode Mergel(ListNode *pl,ListNode *p2) ListNode p=new ListNode,f=p; while(pl！=NULL&&.p2！=NULL) if(pl->datadata){ p->link=pl; 78
V= {1 ,2 ,3 ,4 ,5}; E= { , , , , , , , , 假定此图采用邻接矩阵表表示，根据图的遍历算法分别写出丛顶点 i出发进行深度优先 搜索和广度优先搜索所得到的顶点序列 深度优先搜索序列: 广度优先搜索序列: 5. 度m=7 为H ( K) = K mod nl 解决 冲 突 待依次插入的关键码序列为 9， 4， 3， 8， }，试求出最后得到的散列表。 o 123 4 5 6 得分|评卷人 五、算法分析题(每小题 8分，共 6分) 1. 算法 个有 链 表合 其表 读算法，在划有横线的上面填写合适的内容。 ListNode 头Merge1 (ListNode pI , ListNode p2) ListNode 头p=new ListNode 美£=p; whileCpI! = NULL && p2! = NULL) if(pl 一>datadata) { 一>link=pl; 78
else (p->link=p2;p2=p2->link;} if(p1!=NULL)p->link=pl;else p->link=p2; pl=p2=NULL; return f->link; } 2.已知二叉树中的结点类型BinTreeNode定义为： struct BinTreeNode (ElemType data;BinTreeNode left,right;); 其中data为结点值域，left和right分别为指向左、右子女结点的指针域。根据下面算法 的定义指出其功能。算法中参数BT指向一棵二叉树。 BinTreeNode BTreeSwopX(BinTreeNode BT) { if(BT==NULL)return NULL; else BinTreeNode pt=new BinTreeNode; pt->data=BT->data; pt->right=BTreeSwopX(BT->left); pt->left=BTreeSwopX(BT->right); return pt; } 算法功能： 79
else {p 一>link=p2; p2==p2一>link if(pl! =NULL) 一>link=pl; else p->link=p2; pl=p2=NULL; return f- > link; 2. 型BinTreeNode struct Bin'freeNode {ElemType data; BinTreeNode 头left 关right; }; 其中 a为结点值域， left 和right 指 针 根据 的定义指出其功能。算法中参数 T指向一棵二叉树。 BinTreeNode 祷BTreeSwopXCBinTreeNode 关BT) ifCBT= = NULL) return NULL; else { BinTreeNode 头pt=new BinTreeNode; pt 一>data=B1'一>data; pt 一>right=B1'reeSwopX(BT一>left) ; pt left = BTreeSwopX(BT一>right) ; return pt; 算法功能: 79
得分 评卷人 六、算法设计题(8分)】 已知二叉树中的结点类型BinTreeNode定义为： struct BinTreeNode (char data;BinTreeNode left,right;); 其中data为结点值域，left和right分别为指向左、右子女结点的指针域，根据下面函数声 明编写出求一棵二叉树中分支结点总数的算法，该总数值由函数返回。假定参数BT初始指 向这棵二叉树的根结点。 int BTreeCount(BinTreeNode BT); 80
得分|评卷人 六、算法设计题 已知二叉树中的结点类型 od e定义为: struct BinTreeNode {char data; BinTreeNode 祷left 铃right;}; 其中 a为结点值域，left 和right 明编写出求一棵二叉树中分支结点总数的算法，该总数值由函数返回。假定参数T初始指 向这棵二叉树的根结点。 int BTreeCount(BinTreeNode铃B1') ; 80
试卷代号：1010 中央广播电视大学2010一2011学年度第二学期“开放本科”期末考试 数据结构 试题答案及评分标准 (供参考) 2011年7月 一、单项选择题（在括号内填写所选择的标号。每小题2分，共18分） 1.B 2.A 3.B 4.C 5.D 6.D 7.A 8.C 9.C 二、填空题（在横线处填写合适内容。每小题2分，共14分） 1.顺序 2.O(nlogzn) 3.1 4.2 5.右子树 6.直接选择 7.0(n2) 三、判断题（在每小题后面的括号内打对号“√”表示叙述正确或打叉号“X”表示叙述错误。每 小题2分，共14分) 1.对 2.错 3.对 4.对 5.错 6.对 7.对 四、运算题（每小题6分，共30分） 1.先根：a,b,e,c,f,h,i,j,g /3分 按层：a,b,c,e,f,g,h,i,j /13分 2.分支结点数：4//3分 叶子结点数：3//3分 3.{49,34,30,12,28,16} 81
试卷代号 中央广播电视大学 1学年度第二学期"开放本科"期末考试 数据结构试题答案及评分标准 〈供参考〉 2011 年7 一、单项选择题(在括号内填写所选择的标号。每小题 1. B 2. A 3. B 4. C 5. D 6. D 7. A 8. C 9. C 二、填空题(在横线处填写合适内容。每小题 1. 2. O(nlogzn) 3. 1 4. 2 5. 6. 7. 0(n2 ) 三、判断题(在每小题后面的括号内打对号"~ "表示叙述正确或打叉号 "表示叙述错误。每 小题 1. 对2. 错3. 对4. 对5. 6. 对7. 四、运算题(每小题 1. ，h ， i //3 按层 a， b， c， e， f， g， h， i， //3 2. 数:4 //3 叶子结点数 //3 3. {49 ,34 ,30 ,12 ,28 ,16} 81
4.深度搜索序列：1,2,4,5,3/13分 广度搜索序列：1,2,3,4,5//3分 5.散列表中的每个元素占1分，全对得6分。 0 1 2 3 4 5 6 14 20 23 19 68 五、算法分析题（每小题8分，共16分） 1.pl=pl->link,p=p->link /每空4分 2.生成一棵新二叉树并返回树根指针，该二叉树是已知二叉树BT中所有结点的左、右 子树（或左、右孩子的值）交换的结果。 六、算法设计题(8分) 评分标准：根据编程酌情给分。 int BTreeCount(BinTreeNode BT) { if(BT==NULL)return 0; /12分 else if(BT->left==NULL &BT->right==NULL)return 0; /14分 else return BTreeCount(BT->left)+BTreeCount(BT->right)+1;//8 } 说明：函数体中的每个else保留字可以省略。 82
4. 列:1 ，2 ，4 ，5 ，3 //3 广度搜索序列 1， 2， 3， 4， //3 5. 占1 得6 I 14 I 20 I 23 I I 五、算法分析题(每小题 8分，共 6分) 1. p1=p1 一>link 、p=p 一>link / /每空 4分 2. 棵新二叉树并 指 针 子树(或左、右孩子的值〉交换的结果。 六、算法设计题 8分) 评分标准:根据编程酌情给分。 int BTreeCount(BinTreeNode赞BT) 82 if(B1'==NULL) return 0; //2 else if(BT 一>left==NULL && BT >right= = NULL) return 0; else return BTreeCount(BT一>left)十BTreeCount(BT一>right)十1 ; 说明:函数体中的每个 e保留字可以省略。 //4 //8
