02142数据结构导论2016年10月份真命题及其答案~.doc

-_2016 年 10 月高等教育自学考试全国统一命题考试数据结构导论数据结构导论 试卷试卷(课程代码 02142)本试卷共本试卷共 4 4 页，满分页，满分 l00l00 分，考试时间分，考试时间 l50l50 分钟。分钟。 考生答题注意事项：考生答题注意事项： 1 1本卷所有试题必须在答题卡上作答。答在试卷上无效，试卷空白处和背面均可作草稿纸。本卷所有试题必须在答题卡上作答。答在试卷上无效，试卷空白处和背面均可作草稿纸。 2 2第一部分为选择题。必须对应试卷上的题号使用第一部分为选择题。必须对应试卷上的题号使用 2B2B 铅笔将铅笔将“答题卡答题卡”的相应代码涂黑。的相应代码涂黑。 3 3第二部分为非选择题。必须注明大、小题号，使用第二部分为非选择题。必须注明大、小题号，使用 0 05 5 毫米黑色字迹签字笔作答。毫米黑色字迹签字笔作答。 4 4合理安排答题空间。超出答题区域无效。合理安排答题空间。超出答题区域无效。第一部分第一部分 选择题选择题( (共共 3030 分分) )一、单项选择题一、单项选择题( (本大题共本大题共 1010 小题，每小题小题，每小题 2 2 分，共分，共 3030 分分) ) 在每小题列出的四个备选项中只有一个是符合题目要求的，请将其选出并将在每小题列出的四个备选项中只有一个是符合题目要求的，请将其选出并将“答题卡答题卡”的相应代码涂黑。错涂、的相应代码涂黑。错涂、 多涂或未涂均无分。多涂或未涂均无分。 1已知问题规模为 n，则下列程序片段的时间复杂度是 C2若用计算机来模拟银行客户排队等待办理业务的情形，则所应该采用的数据结构是 A栈 B队列 C树 D图 3若线性表采用链式存储结构，则适用的查找方法为 A随机查找 B散列查找 C二分查找 D顺序查找 4已知指针 P 和 q 分别指向某单链表中第一个结点和最后一个结点，假设指针 s 指向另一个单链表中某个结点， 则在 S 所指结点之后插入上述单链表应执行的语句为 Aqnext；snext；snext2P； Bsnext=P；qnext=snext； Cpnext=snext；snext=q； Dsnext2q；pnext2snext； 5栈的运算特点是先进后出，元素 a、b、c、d 依次入栈，则不能得到的出栈序列是 Aabed Bdcba Ccabd Dbcda 6在实现队列的链表结构中，其时间复杂度最优的是 A仅设置头指针的单循环链表 B仅设置尾指针的单循环链表 C仅设置头指针的双向链表 D仅设置尾指针的双向链表 7任意一棵二叉树的前序和后序遍历的结果序列中，各叶子结点之间的相对次序关系是 A不一定相同 B. 都相同 C都不相同 D互为逆序 8若某棵树的存储结构采用双亲表示法，如题 8 图所示，则该树的高度是-_A2 B3 C4 D5 9无向图的邻接矩阵一定是 A对称矩阵 B对角矩阵 C稀疏矩阵 D三角矩阵 10根据连通图的深度优先搜索的基本思想，如题 10 图所示的连通图的一个深度优先搜索的结果序列是A123456 B123465 C. 126345 D162543 11用顺序查找方法对含有 n 个数据元素的顺序表按从后向前查找次序进行查找，现假设查找 其中每个数据元素的概率不相等，那么 A该顺序表按查找概率由低到高的顺序来存储数据元素，其 ASL 最小 B该顺序表按查找概率由高到低的顺序来存储数据元素，其 ASL 最小 CASL 的大小与数据元素在该顺序表中的位置次序无关 DASL 的大小与查找每个数据元素的概率无关 12已知散列表的存储空间为 T0，l6，散列函数为 H(k)-k mod l7，用二次探测法解决冲突。散列表中 已插入下列关键字：TE53-39、T6一 57 和 T737，则下一个关键字值 23 在该散列表中插入的位置是 AT23 BT4 CT8 DT10 13对关键字序列eSC，tab，ah，con，brk，del进行排序时，若关键字序列的变化情况如下； esc，tab，ah，con，brk，del ah，tab，eSC，con，brk，del alt，brk，esc，con，tab，del alt，brk，con，esc，tab，del ah，brk，con，del，tab，esc ah，brk，con，del，esc，tab。则所用的排序方法是 A直接插入排序 B直接选择排序 C堆排序 D冒泡排序 14满足最小堆定义的是 A. 21，25，55，23，51，63 B21，51，55，63，25，23 C21，63，55，25，51，23 D21，51，23，63，55,25 15设有两个长度分别为 m、n 的降序有序序列a1，a2，am)、b1，b2，bn)，采用二路归并方法将它们合 并成长度为 m+12 的降序有序序列，则归并过程中元素比较次数最少的条件一定是 BCCCCCCCCCCCC第二部分非选第二部分非选-_择题择题( (共共 7070 分分) )二、填空题二、填空题( (本大题共本大题共 l3l3 小题，每小题小题，每小题 2 2 分，共分，共 2626 分分) ) 16从宏观上看，数据、数据元素和_数据项_ 反映了数据组织的三个层次。 17在表长为 n 的顺序表中插入或删除一个元素，则需移动元素的具体个数与表长和_元素位置_有关。 18非空的单循环链表的头指针为 head，尾指针为 rear，则 rear 一>next=_head_。 19设以数组 Qm存放循环队列的元素，变量 rear 和 queuelen 分别表示循环队列中队尾元素的下标位置和元素 的个数。则计算该队列中队头元素下标位置的公式是_ (rear queuelen + m )%m_。 20二维数组 A89按行优先顺序存储，若数组元素 A23的存储地址为 l087，A47 的存储地址为 ll53，则每个数组元素占用的存储单元的个数是_3_。 21设一个完全二叉树共含有 196 个结点，则该完全二叉树中含有叶结点的个数是_98_。 22假设高度为 h 二叉树中只有度为 2 和度为 0 这两种类型的结点，则该类二叉树中结点个数至多为 2h-1、至少 为_3_。 23若以数据集34，5，12，23，8，18为叶结点的权值构造一棵哈夫曼(HUffman)树，那么该 Huffman 树的带权 路径长度 WPL_238_。 24设有散列函数 H(k)和键值，则这种现象称为“冲突” ，且称键值 k1和 k2 互为_同义词_。 25一个图的最小生成树是满足一定条件的生成树，即一个图的最小生成树是指该图的所有生成树中_权值之和 最小_的生成树。 26对长度为 n 的有序顺序表进行二分查找，则查找表中的任意一个元素时，无论查找成功与失败，最多与表中 _longN_+1_个元素进行比较。 27排序方法中，从未排序序列中依次取出元素与已排序序列(初始时为空)中的元素按序进行比较，将其插入已 排序序列的正确位置上的方法称为_直接插入排序_。 28一般情况下，时闯复杂度是 O(nl0g2n)且其空间复杂度最优的排序方法是_堆排序_。 三、应用题三、应用题( (本大题共本大题共 5 5 小题，每小题小题，每小题 6 6 分，共分，共 3030 分分) ) 29借助于队列能够将含有 n 个数据元素的栈逆置，比如栈 S 中的元素为a，b，C逆置后变成C，b，a。试简 述你的解决方案。 30为便于表示二叉树的某些基本运算，则深度为 k的二叉树的顺序存储结构中的数组的大小为多少?画出如题 30 图所示的二叉树的顺序存储结构示意图，并说明对一般形态的二叉树不太适合使用顺序存储结构来表示的原因。31先序遍历、中序遍历一个森林分别等同于先序、中序遍历该森林所对应的二叉树。现已知一个森林的先序序 列和中序序列分别为 ABCDEFIGJH 和 BDCAIFJGHE，试画出该森林。 32设有一组关键字值序列e，b，d，f，a，g，C现要求：(1)根据二叉排序树的创建方法构造出相应的二叉排 序树(关键字值的大小按字母表顺序计)；(2)计算等概率情况下在该二叉排序树上查找成功的平均查找长度 ASL。 33若采用二路归并排序方法对关键字序列25，9，78，6，65，15，58，18，45，20进行升序排序，写出其每 趟排序结束后的关键字序列。 四、算法设计题四、算法设计题( (本大题共本大题共 2 2 小题，每小题小题，每小题 7 7 分，共分，共 l4l4 分分) ) 34某电商有关手机的库存信息，按其价格从低到高存储在一个带有头结点的单循环链表中，链表中的结点由品 牌型号(nametype)、价格(price)、数量(quantity)和指针(next)四个域组成。现新到 in 台、价格为 c、品牌型号 为 x 的新款手机需入库，写出相应的存储结构和实现该要求的算法。-_35写出向存储结构为邻接矩阵的无向图 G 中插入一条边(x，y)的算法。算法的头函数为： void AddEdgetoGraph(Graph*G，VertexType X，VertexType y>，无向图 G 的存储结构 为：-_-_