试卷代号：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个顶点的有向图的邻接矩阵表示中，删除一条边<i,j>需要的时间复杂 度为( )。 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,2>,<1,3>,<2,4>,<2,5>,<3,4>,<4,5>,<5,1>,<5,2>, <5,3>}； 假定此图采用邻接矩阵表表示，根据图的遍历算法分别写出从顶点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->data<=p2->data){ p->link=pl; 78
V= {1 ,2 ,3 ,4 ,5}; E= {< 1, 2> , < 1 , 3> , < 2 , 4> , < 2 , 5> , < 3 , 4> , < 4 , 5> , < 5 , 1>, < 5 , 2> , <5 ，3> 假定此图采用邻接矩阵表表示，根据图的遍历算法分别写出丛顶点 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 一>data<=p2 >data) { 一>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