最新自考02331数据结构试题及答案含评分标准资料

1、精品文档2018年 10 月高等教育自学考试全国统一命题考试数据结构 试卷( 课程代码 02331)本试卷共 7 页，满分 l00 分，考试时间 l50 分钟。 考生答题注意事项： 1本卷所有试题必须在答题卡上作答。答在试卷上无效，试卷空白处和背面均可作草稿纸。 2第一部分为选择题。必须对应试卷上的题号使用2B 铅笔将“答题卡”的相应代码涂黑。3第二部分为非选择题。必须注明大、小题号，使用0 5 毫米黑色字迹签字笔作答。4合理安排答题空间，超出答题区域无效。第一部分 选择题一、单项选择题：本大题共 l5 小题，每小题 2 分，共 30 分。在每小题列出的备选项中 只有一项是最符合题目要求的。请

2、将其选出。1下列数据结构中，逻辑结构不同的是A.线性表B .栈 C .队列 D .二叉树2将 l6 个数据元素的线性表按顺序存储方式存储在数组中，若第一个元素的存储地 址是 l000 ，第 6 个元素的存储地址是1040，则最后一个元素的存储地址是A . 1112 B . 1120 C . 1124 D . 11283. 设栈的初始状态为空，元素1，2，3，4，5 依次入栈，不能得到的出栈序列是A . 1，2，3， 4，5 B . 4，5，3，2，1 C . 1，2，5，4，3 D . 1，2，5，3，44. 设指针变量 P 指向非空单链表中的结点，next 是结点的指针域，则判断P 所指结点

3、为尾结点前一个结点的逻辑表达式中，正确的是A. p->next!=NULL&&p->next 一 >next->next = NULLB . p->next!=NULL&&p->next->next NULLC . p->next->next=NULLD . p->next NULL5 已知广义表 LS=(a , b, c) , d) , (e , (fg , (h i), LS 的深度是A. 2B. 3C. 4 D. 56. 已知一棵完全二叉树T的第5层上共有5个叶结点，则T中叶结点个数最少是A. 5

4、8. 8C. 10 D . 277. 已知二叉树 T的前序遍历序列为 a，b，c, e, d，中序遍历序列为 C, e, b, d，a，则T 的后序遍历序列为A . c, e, d,b , a B . d, e, c, b, a C . e, c, d, b, a D . e, c, b, a, d&有向图G有玎个顶点和e条边，G保存在邻接矩阵 M中，M中0与1的个数差是A . n(n+1) / 2-e B . n(n +1) /2-2e C . nx n-e D . nx n-2e9有向图G中所有顶点的度数之和是24，则G中弧的数量是A 10 B 12 C 14 D1610.设有向图

5、G含有n个顶点、e条边，使用邻接表存储。对G进行深度优先搜索遍历算法的时间复杂度是A . 0(n) B . 0( 口) C . O(n+e) D . O(n x e)11 对数据序列 (26, 14, 17, 12, 7, 4, 3)采用二路归并排序进行升序排序,两趟排序后, 得到的排序结果为A14,26,17, l2, 4, 7, 3B12, l4, l7, 26, 3, 4, 7C14,26,12, l7 , 3, 4, 7D14, 26, l2 , l7 , 3, 7, 412下列选项中，不稳定的排序方法是A 希尔排序 B 归并排序 C 直接插入排序 D 冒泡排序13一组记录的关键字为

6、(35 ，48，47，23，44，88) ，利用堆排序算法进行降序排序，建立 的初始堆为A 23，35，48，47，44，88 B 23，35，47，48，44，88C 35，23，47，48，44，88 D 35，23，47，44，48，8814. 一棵二叉排序树中，关键字n所在结点是关键字 m所在结点的孩子，则A n 一定大于 m B n 一定小于 mC . n 定等于m D . n与m的大小关系不确定15. 设敖列表长 m=16散列函数H(key)=key % 15。表中已保存4个关键字：addr(18)=3 ,addr(35)=5， addr(51)=6 ， addr(22)=7 ，其

7、余地址均为开放地址。存储关键字 36时存在冲突，采用线性探测法来处理。则查找关键字 36时的探查次数是A . 1 B . 2 C . 3 D . 4第二部分 非选择题二、填空题：本大题共 l0 小题，每小题 2分，共 20 分。16. 数据项是具有独立含义的 标识单位。17. 指针P和q分别指向单链表 L中的两个相邻结点，即 q->next=P。若要在q所指结 点后插入指针r所指结点，则执行的语句是r->ne处=p; 。18. 递归算法设计中的最小子问题称为递归的 。19. 广义表 (a ， b)， (c ， d)， e， (f (g,h) 的表尾是 。20. 已知二叉树的前序遍历

8、序列和后序遍历序列，则对应的二叉树确定。21. 如果有向无环图 G中仅有一个顶点的入度为0,若要求G的拓扑序列不唯一，则 G中必须存在一个出度至少为 的顶点。22. 将森林T转换为一棵二叉树 T1,在T中结点A是结点B的右邻的兄弟(下一个兄弟)，则在T1中，A是B的结点。23. 对含玎个元素的数据序列采用快速排序算法进行排序,平均时间复杂度24. 散列存储中,常用的解决冲突的方法有开放地址法和 两大类。25. 假设顺序存储的有序表 R含有8个关键字，进行二分查找时，平均查找长度为 。三、解答题：本大题共 4 小题,每小题 5 分,共 20 分。26. 设电文字符集是 el , e2, e3,

9、e4, e5) ,各字符出现的次数分别为 36, l3 , 26, l8 , 23 。现要为该字符集设计哈夫曼编码。请回答下列问题。(1) 给出构造的哈夫曼树。(2) 给出各字符的哈夫曼编码。(3) 计算电文编码总长。27已知图G采用邻接矩阵存储，邻接矩阵如题 27图所示。A B C D E F G/<ro i i o o o£ 0 0 0 0 01F 0 0 0 0 0 0<7 0 0 0 0 00001010题27图(1)根据邻接矩阵画出图G(2)根据图G写出从顶点A开始图G的1个深度优先搜索遍历序列。根据图G写出从顶点A开始图G的1个广度优先搜索遍历序列。28. 有

10、数据序列(12 ,17 , 05, 10 , 20, 24, 45, II , 10 , 12)，使用希尔排序方法将其排成 升序序列。请回答下列问题。(1)分别写出增量为3和1的希尔排序结果。(2) 计算第一趟希尔排序中数据元素之间的总交换次数(两个 元素之间的交换记I次)。29. 设有二叉排序树 T如题29图所示。现需在 T中删除结点e,请 回答下列问题。(1) 画出删除后的二叉排序树(仅需画出一棵)。(2) 在你实现的删除过程中，指针域更新的次数是多少题29图四、算法阅读题：本大题共 4小题，每小题5分，共20分。30. 顺序表类型定义如下：# define ListSize 100typ

11、edef struct int dataLisiSize;int length; SeqList;阅读下列程序'并回答问题。int partminf S eq List *SLlt SeqList *SL2) int minlength minvalue, k = 0；*minlength = SL2->iength;minvalue = SL2->data0;while( k < oiinlength ) if( SLl->datak < SL2->datak && SL1 *>datak<ni in value ) m

12、in value = SLl->datak;else i f( SL2-> datak <minvahie)minvalue 上 SL2->datak;k+;return min value;int f30( SeqList *SL1, SeqList *SL2 )精品文档32.待排序记录的数据类型定义如下：#define MAXSIZE 100typedef int KeyType;typedef struct Key Type key; Reclype;typedef RecType SeqList MAXSIZE;下列函数实现顺序表的直接插入排序，请在空白处填上适

13、当内容使算法完整。void f32( SeqList 比 int n)£int i,j；Reclype temp;for (il; iQ ;i+) temp = Ri;冷J = 1;while (j > 0 && temp.key < Rj-l.key) R沪 RH; ；,3):33二叉树的存储结构类型定义如下：typedef int Dataiype;typedef struct nodeDatalype key;" data 是数据域struct node * Ichild, * rchild;/ 分别指向左右孩子BinTNode;typed

14、ef BinTNode * BinTree;阅读下列程序，并回答问题.void £33( Binlree root, int left, int right)if(roof=NULL) return;63( rootlchild, left, right);if( root->key >= eft && rocrt->key<right ) ptintfif 11%d root->key )；f33( root-TChiid, left, right);(l)设二更树T如题弗图所示，出是指向银结点的指针.给出执33(bt, 14, 30五

15、、算法设计题：本题10分.34.已铀“个单链表的表头指针保存在数组A中，单链表中的结点类型及数组类型定文如下，存储形式如题34图所示。define MAXSIZE 100typedef int Datalype;typed ef struct node Dauiypedata;/data 是数据域struct node *next;/指向下一结点的指针Node;typedef Node * SeqList MAXSIZEAlU-1 AI»Ji4+*l d题34图试设计算法.在多个链表中查找值为徐y的数据元素，査找成功返回X查找 失败返回 0* 函数原型为 int f34 ( SeqL

16、ist A, int n, int key)»绝艳査启用前2018年10月高等教育自学考试全国统一命题考试数据结构试题答案及评分参考（课程代码02331）里琐选僅题：本大35共汁小題，旬小聽？分.具祁分.L D土 H3, ）A H5. RS. 09. BID. C15. l14” f)15. C二、境空扯：本大题共IU小扯，鬲小題？分.共F分*L6.戢小17. q-'next -* r;8 终止箫件（戍iftlUllIl） 19-谑川）点仪鸟h"）20.彳M（或 /陡）2L 22工 fi/S i23- 0（用log”）24.拉聂仏f叹 亚地rlrZ）25. 2hX

17、（戍2 62S）购买白暂JW年真蛊534恥们橄苗同兮（代frUJ）三、幫答丹：本次铀共4小融，毎小越*分，義纹分. J6. （ i 哈犬赠种为1字苻口C1C4CaII10001101W31 电崔妬碍总K: - 36*2*13*3*26*2-1*3+23*2 = 263,（1 分）【评井说明】儿題和»的答事亦啡”若r 1 出的禅秦丘踊.同样给见 莎分厂确酌怙丹分號州皓构试恿拎舉峻评分参苇血I H捷3页）AIEFFg煌咅）评分说明1応射杵寬办啡 It他答議包拆! ABIXjEFC> ACDKrGB, ACDGtifB-（1）AJKf>F.GEQ 分、【评分说矚】t；腔拎貿小啡

18、.ABCLX；EF< ACODEGF. ACBDGEF.IS. （H轴站为3时金來卅了结毗10 M0、12 17 10 12 20 2145炸分增QAM时弗苏打1卡姑驭常皿KHI 12 12 172（） 24 S,1分）（2），肚.4 分）a” "毎号拧灾-冲善赛二賂伸U)CJ|>4»拎什域更Urinn2次）令【评井说明】這群窜兀啡丐1釀吕一种庐确荐事即可.襌分芒确枕情络好”四，算诜询鎮題；本大赶共卜题誓小题$分，共加井*30. （I）调州何X由対迪因値崔対"E3Q） iMJItfc援團冲tvt黑的最预怏度mktefljlh件按两个栽性卷申flaminlength亍兀盍的费卜備（2；>>II. （IlCEDAlk门好 ><2）时冋址杂曜为OF）.尺屮料址二义城中纳台结点卜味C2>>曲据诰村试题存案朋评分参号詢2巾（伏1氏j <削十24：1 / Rjt 価叩T33. 1 i 23.氏M 1W2讥<31£2；授屮序色农 倉村屮：H|满迪计G