试卷代号：1252 座位口 中央广播电视大学2012一2013学年度第一学期“开放本科”期末考试 数据结构（本）试题 2013年1月 题 号 三 四 总 分 分数 得 分 评卷人 一、单项选择题（每小题2分，共30分） 1.同一种逻辑结构( )。 A.只能有唯一的存储结构 B.可以有不同的存储结构 C.只能表示某一种数据元素之间的关系 D.以上三种说法均不正确 2.链表所具备的特点是()。 A可以随机访问任一结点 B占用连续的存储空间 C.插人删除元素的操作不需要移动元素结点 D.可以通过下标对链表进行直接访问 3.数据的物理结构(·)。 A与数据的逻辑结构无关 B仅仅包括数据元素的表示 C只包括数据元素间关系的表示 D.包括数据元素的表示和关系的表示 4.线性结构中数据元素的位置之间存在( )的关系。 A一对一 B一对多 C.多对多 D.每一个元素都有一个直接前驱和一个直接后继 1143
试卷代号 座位号IT] 仅仅包 示和 〉的关系。 中央广播电视大学 2 0 3学年度第一学期"开放本科"期末考试 数据结构(本)试题 2013 年1 |题号|一|二 l三|四|总分| |分数 I I I I I |得分|评卷人| 一、单项选择题{每小题 2分，共 0分} I I I 1.同一种逻辑结构( )。 A.只能有唯一的存储结构 .可以有不同的存储结构 C. 能表 一种 据元 间的 系 且 上三种 法均 正确 2. 表所 )。 一结 且占用连续的存储空间 插入 需要 通过 直接访 3. 理结 )。 A 与 辑结 无关 包括数据元素 表示 4. 性结 据元 位置 存在 一个 有一 直接 直接后 1143
5.以下表中可以随机访问的是()。 A单向链表 B双向链表 C.单向循环链表 D.顺序表 6.算法的时间复杂度与()有关。 A所使用的计算机 B与计算机的操作系统 C.与算法本身 D.与数据结构 7.设有一个长度为n的顺序表，要删除第1个元素需移动元素的个数为( A n-i+1 Bn-i C.n-i-1 Di 8.在一个单链表中，P、q分别指向表中两个相邻的结点，且q所指结点是P所指结点的直接后 继，现要删除q所指结点，可用的语句是( A.p=q->next B p->next=q C.p->next=q->next D.q->next=NULL 9.从一个栈顶指针为to即的链栈中删除一个结点时，用变量x保存被删结点的值，则执 行( )。 A.x=top->data;top=top->next; B.x=top->data; C.top=top->next;x=top->data; D.top=top->next;x=data; 10.在一个链队中，假设f和r分别为队头和队尾指针，则删除一个结点的运算为()。 A.r=f->next; B.r=r->next; C.f=f->next; D.f=r->next; 11.一个栈的进栈序列是a,b,c,d,e,则栈的不可能输出序列是( )(进栈出栈可以交 替进行)。 A.dceab B.edcba C.decba D.abcde 12.有一个长度为10的有序表，按折半查找对该表进行查找，在等概率情况下查找成功 的平均比较次数为()。 A.26/10 B.29/10 C.29/9 D.31/10 13.排序算法中，从未排序序列中依次取出元素与已排序序列（初始为空）中的元素进行 比较（要求比较次数尽量少），然后将其放人已排序序列的正确位置的方法是()。 A.冒泡 B.直接插人 C.折半插入 D.选择排序 1144
5. 问 的 )。 链表 序表 6. 算法 )有关。 所使 算法 身B 据结 7. 有一 长度 除第 个元 需移 元素 个数 )。 An一i+1 c. Rn-i D.i 8. 个单链表 相邻 接后 继，现要删除 q所指结点，可用的语句是( )。 A p=q->next C. p- ext ext R p-> next= q D.q-> next= NULL 9. 个楼 为top 删 除 量x 保存被删结点 行( )。 A. x=top->data;top=top->next; c. top=top->next;x=top->data; B. x=top->data; D. top=top->next;x=data; 10. 在一 假设 尾指针 则删除 A. r=f->next; C. f=f->next; B. r=r->next; D. f=r->next; 1. 进战序 ，b ，d 可 能 )(进拽出钱可以交 替进行〉。 A. dceab C. decba B. edcba D. abcde 12. 有一 长度为10 有序 进行 在等概 况下 的平均比较次数为( )。 A.26/10 B.29/10 C.29/9 D.31/10 13. 算法 序序 排序序 比较(要求比较次数尽量少)，然后将其放入巳排序序列的正确位置的方法是( ) 0 A. 泡B.直接 C. 半插入D. 1144
14.设有一个10阶的对称矩阵A,采用压缩存储的方式，将其下三角部分以行序为主存储到 一维数组B中（数组下标从1开始），则矩阵中元素A.5在一维数组B中的下标是()。 A.33 B.32 C.85 D.41 15.在一个无向图中，所有顶点的度数之和等于边数的( )倍。 A.3 B2.5 C.1.5 D.2 得分 评卷人 二、填空题（每小题2分，共24分） 16.栈和队列的操作特点分别是 和 17.结构中的数据元素存在多对多的关系称为 结构。 18.根据数据元素间关系的不同特性，通常可分为集合、线性、 、四类基 本结构。 19.要求在个数据元素中找其中值最大的元素，设基本操作为元素间的比较。则比较的 次数和算法的时间复杂度分别为 和 20.在一个单向链表中P所指结点之后插人一个s所指向的结点时，应执行 和p>next=s:的操作。 21.在二叉树的链式存储结构中，通常每个结点中设置三个域，它们是值域、 22.一棵二叉树中顺序编号为i的结点，若它存在左、右孩子，则左右孩子的编号分别为 23.向一个栈顶指针为h的链栈中插人一个s所指结点时，可执行s>next=h;和 24.在一个链队中，设f和r分别为队头和队尾指针，则插入s所指结点的操作为 和r=s;(结点的指针域为next)。 25.设有一棵深度为4的完全二叉树，第四层上有5个结点，该树共有个结点。（根 所在结点为第1层) 26.对稀疏矩阵进行压缩存储，矩阵中每个非零元素对应的三元组包括该元素的 和非零元素值三项信息。 27.在对一组记录(55,39,97,22,16,73,65,47,88)进行直接插人排序时，当把第7个记录65 插入到有序表时，为寻找插人位置需比较次。 1145
14. 有一个10 称矩阵A 采用 缩存 方式 将其 一维数组 B中(数组下标从 ，则矩阵中元素Aa 5在一维数组 B中的下标是( )。 A.33 C. 85 B.32 D.41 15. 有顶 )倍。 A. 3 C. 1. 5 |得分|评卷人| I I I B. 2.5 D. 2 二、填空题{每小题 2分，共 4分} 16. 队列 17. 18. 特性 常可 集合 类基 本结构。 19. 要求 个数 本操作 间 的 次数和算法的时间复杂度分别为一一一一和 20. 在 一 个 单 指 结 插 入 执 行 和p- xt ;的操作。 1. 二叉 链式存储结 常每个结 三个 它们 22. 棵二 编号 存在 右 孩 右孩子 号分 23. 钱顶指针为h 插入一个s 执行 s->next=h; 24. 在一 队 头 和 队 操 作 (结点的指针域为 )。 25. 棵深 为4 有5 个结 该树共 个结 所在结点为第 1层) 26. 稀疏 存储 每个非 元组包 和非零元素值三项信息。 27. 录(55 ，39 ，97 ，22 ，16 ，73 ，65 ，47 ，88) 进行直接插 序时 第7 个记录65 插入到有序表时，为寻找插入位置需比较次。 1145
得分 评卷人 三、综合题（每小题10分，共30分） 28.(1)以2,3,4,7,8,9作为叶结点的权，构造一棵哈夫曼树（要求每个结点的左子树根结点 的权小于等于右子树根结点的权)，给出相应权重值叶结点的哈夫曼编码。 (2)一棵哈夫曼树有n个叶结点，它一共有多少个结点？简述理由。 29.一组记录的关键字序列为(46,79,56,38,40,84) (1)利用快速排序的方法，给出以第一个记录为基准得到的一次划分结果（给出逐次交换元 素的过程，要求以升序排列)。 (2)对上述序列用堆排序的方法建立大根堆，要求以二叉树逐次描述建堆过程。 30.设查找表为(50,60,75,85,96,98,105,110,120,130) (1)说出进行折半查找成功查找到元素120需要进行多少次元素间的比较？ (2)为了折半查找元素95，经过多少次元素间的比较才能确定不能查到？ (3)画出对上述有序表进行折半查找所对应的判定树（要求以数据元素作为树结点）。 得分 评卷人 四、程序填空题（每空2分，共16分】 31.以下是用尾插法建立带头结点且有个结点的单向链表的程序，结点中的数据域从前 向后依次为1,2,3，，n,完成程序中空格部分。 NODE create(n) {NODE*head,*p,￥q; int i; p=(NODE *)malloc(sizeof(NODE)); head=(1) ;(2) ;p>next=NULL;/*建立头结点*/ for(i=1;idata=i; p->next=NULL; 1146
|得分|评卷人| I I I 三、综合题{每小题 0分，共 0分} 28. (1)以 2， 3， 4， 7， 8， 9作为叶结点的权，构造一棵晗夫曼树(要求每个结点的左子树根结点 的权小于等于右子树根结点的权) ，给出相应权重值叶结点的晗夫曼编码。 (2) 一棵 个结 29. 关键 为(46 ，79 ，56 ，38 ，40 ，84) (1)利用快速排序的方法，给出以第一个记录为基准得到的一次划分结果(给出逐次交换元 素的过程，要求以升序排列〉。 (2) 立大根堆 要求 逐次描述 过程 30. 查找 为(50 ，60 ，75 ，85 ，96 ，98 ，105 ，110 ，120 ，130) (1)说出进行折半查找成功查找到元素 0需要进行多少次元素间的比较? (2) 素95 多少 较才能确 不能 (3) 有序表进行折半查找所对应 定树 要求 数据 |得分|评卷人| I I I 四、程序填空题{每空 2分，共 6分} 1. 有n 域从前 向后依次为 1， 2， 3，····.虫 n，完成程序中空格部分。 NODE 祷create(n) {NODE 祷h四d 善p mt 1; p=(NODE 赞)malloc(sizeof(NODE» ; head= (1) forO= 1;idata= i; p-> next= NULL ; 1146 ;(2) ;p- NULL 建立头结 铃 /
q->next=(4) (5) } return(head); 32.以下程序是中序遍历二叉树的递归算法的程序，完成程序中空格部分（树结构中左、右 指针域分别为lef和right,数据域data为字符型，BT指向根结点)。 void Inorder(structBTreeNode BT) if(BT!=NULL)( (1) (2) (3) 1147
q->next=(4) (5) retum(head) ; 32. 二叉 程序 成程 部分 树结 指针域分别为 t和 ri t，数据域也ta为字符型， T指向根结点)。 void Inorder(structB 巴Node 铃BT) if(BT! =NULL){ (1) (2) (3) 1147
试卷代号：1252 中央广播电视大学2012一2013学年度第一学期“开放本科”期末考试 数据结构（本） 试题答案及评分标准 (供参考) 2013年1月 一、单项选择题（每小题2分，共30分） 1.B 2.C 3.D 4.A 5.D 6.C 7.B 8.C 9.A 10.C 11.A 12.B 13.C 14.A 15.D 二、填空题（每题2分，共24分） 16.后进先出 先进先出 17.图状（网状） 18.树形 图状 19.n-1,0(n) 20.s->next=p->next; 21.左指针右指针 22.2i2i+1 23.h=s: 24.r->next=s; 25.12 26.行下标 列下标 27.3 三、综合应用题（每小题10分，共30分】 28.(1) 1148
试卷代号 中央广播电视大学 3学年度第-学期"开放本科"期末考试 数据结构(本)试题答案及评分标准 (供参考) 2013 年1 一、单项选择题{每小题 1.B 2. C 3.0 ~C ~B &C 11. A 12. B 13. C 二、填空题{每题 16. 后进先 17. 18. 树形 19. n-1 ,O(n) 20. s-> next = p-> next ; 1. 指针 22. 2i 2i+1 23. h=s; 24. r->next=s; 25.12 26. 下标 27.3 三、综合应用题{每小踵 28. (1) AA- 5.0 10. C 15.0 1148
2:1110 3:1111 4:110 7:00 8:01 9:10 (2)2一1个，因为非叶结点数比叶结点数少一个。 29.(1)初始序列 46,79,56,38,40,84 40,79,56,38,40,84 40,79,56,38,79,84 40,38,56,38,79,84 40,38,56,56,79,84 40,38,46,56,79,84 (2) 46 46 79 56 79 84 38 40 84 38 40 56 84 84 79 6 多 38 40 56 38 40 图3 1149
2: 1110 3: 1111 4: 110 7, 00 8: 01 9: 10 (2)2n一1 29. (1)初始序列 图，队 6， 8， 0， 8 40 队56 ，38 ，84 40 ，56 ，38 ，79 ，84 40 ，38 队84 40 ，38 ，56 ，79 ，84 40 ，38 固.56. 队84 (2) 1149
30.(1)3次 (2)4次 (3) 96 60 110 50 120 75 98 85 105 130 图5 四、程序填空题（每空2分，共16分） 31.(1)p (2)g=p (3)(NODE *)malloc(sizeof(NODE)) (4)p (5)q=p 32.(1)Inorder(BT->left) (2)printf(“%c”,BT->data) (3)Inorder(BT->right) 1150
30. (1) (2)4 (3) 四、程序填空题{每空 31. (1 ) p (2)q=p (3)(NODE祷)matloc(sizeof(NODE)) (4)p (5)q=p 32. (1)Inorder(BT':'>left) (2)printf(" %c" ,BT-> data) (3)Inorder(BT->right) 1150