02142数据构造导论2022年10月份真题及答案 - 2022年10月高等教育自学考试全国统一命题考试 数据构造导论 试卷 (课程代码 02142) 本试卷共4页，总分值l00分，考试时间l50分钟 考生答题考前须知： 1．本卷所有试题必须在答题卡上作答答在试卷上无效，试卷空白处和反面均可作草稿纸 2．第一局部为选择题必须对应试卷上的题号使用2B铅笔将“答题卡”的相应代码涂黑 3．第二局部为非选择题必须注明大、小题号，使用0．5毫米黑色字迹签字笔作答 4．合理安排答题空间超出答题区域无效 第一局部 选择题(共30分) 一、单项选择题(本大题共10小题，每题2分，共30分) 在每题列出的四个备选项中只有一个是符合题目要求的，请将其选出并将“答题卡”的相应代码涂黑错涂、多涂或未涂均无分 1．问题规模为n，那么以下程序片段的时间复杂度是C 2．假设用计算机来模拟银行客户排队等待办理业务的情形，那么所应该采用的数据构造是 A．栈 B．队列 C．树 D．图 3．假设线性表采用链式存储构造，那么适用的查找方法为 A．随机查找 B．散列查找 C．二分查找 D．顺序查找 4．指针P和q分别指向某单链表中第一个结点和最后一个结点，假设指针s指向另一个单链表中某个结点，那么在S所指结点之后插入上述单链表应执行的语句为 A．q→next；s→next；s→next2P； B．s→next=P；q→next=s→next； C．p→next=s→next；s→next=q； D．s→next2q；p→next2s→next； 5．栈的运算特点是先进后出，元素a、b、c、d依次入栈，那么不能得到的出栈序列是 A．abed B．dcba C．cabd D．bcda 6．在实现队列的链表构造中，其时间复杂度最优的是 A．仅设置头指针的单循环链表 B．仅设置尾指针的单循环链表 C．仅设置头指针的双向链表 D．仅设置尾指针的双向链表 7．任意一棵二叉树的前序和后序遍历的结果序列中，各叶子结点之间的相对次序关系是 A．不一定一样 B. 都一样 C．都不一样 D．互为逆序 8．假设某棵树的存储构造采用双亲表示法，如题8图所示，那么该树的高度是 A．2 B．3 C．4 D．5 9．无向图的邻接矩阵一定是 A．对称矩阵 B．对角矩阵 C．稀疏矩阵 D．三角矩阵 10．根据连通图的深度优先搜索的根本思想，如题10图所示的连通图的一个深度优先搜索的结果序列是 A．123456 B．123465 C. 126345 D．162543 11．用顺序查找方法对含有n个数据元素的顺序表按从后向前查找次序进展查找，现假设查找 其中每个数据元素的概率不相等，那么 A．该顺序表按查找概率由低到高的顺序来存储数据元素，其ASL最小 B．该顺序表按查找概率由高到低的顺序来存储数据元素，其ASL最小 C．ASL的大小与数据元素在该顺序表中的位置次序无关 D．ASL的大小与查找每个数据元素的概率无关 12．散列表的存储空间为T[0，?，l6]，散列函数为H(k)----k mod l7，用二次探测法解决冲突。
散列表中已插入以下关键字：TE53--39、T[6]一57和T[73—7，那么下一个关键字值23在该散列表中插入的位置是 A．T[23 B．T[4] C．T[8] D．T[10] 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} B．{21，51，55，63，25，23} C．{21，63，55，25，51，23} D．{21，51，23，63，55,25} 15．设有两个长度分别为m、n的降序有序序列{a1，a2，?，am)、{b1，b2，?，bn)，采用二路归并方法将它们合并成长度为m+12的降序有序序列，那么归并过程中元素比拟次数最少的条件一定是BCCCCCCCCCCCC 第二局部非选择题(共70分) 二、填空题(本大题共l3小题，每题2分，共26分) 16．从宏观上看，数据、数据元素和__数据项___ 反映了数据组织的三个层次。
17．在表长为n的顺序表中插入或删除一个元素，那么需挪动元素的详细个数与表长和_元素位置_有关 18．非空的单循环链表的头指针为head，尾指针为rear，那么rear一>next=___head____ 19．设以数组Q[m]存放循环队列的元素，变量rear和queuelen分别表示循环队列中队尾元素的下标位置和元素的个数那么计算该队列中队头元素下标位置的公式是__ (rear – queuelen + m )%m___ 20．二维数组A[8][9]按行优先顺序存储，假设数组元素A[2][3]的存储地址为l087，A[4][7] 的存储地址为ll53，那么每个数组元素占用的存储单元的个数是___3_____ 21．设一个完全二叉树共含有196个结点，那么该完全二叉树中含有叶结点的个数是___98_____ h22．假设高度为h二叉树中只有度为2和度为0这两种类型的结点，那么该类二叉树中结点个数至多为2-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小题，每题6分，共30分) 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小题，每题7分，共l4分) 34．某电商有关的库存信息，按其价格从低到高存储在一个带有头结点的单循环链表中，链表中的结点由品牌型号(nametype)、价格(price)、数量(quantity)和指针(next)四个域组成现新到in台、价格为c、品牌型号为x的新款需入库，写出相应的存储构造和实现该要求的算法 35．写出向存储构造为邻接矩阵的无向图G中插入一条边(x，y)的算法算法的头函数为： void AddEdgetoGraph(Graph*G，VertexType X，VertexType y>，无向图G的存储构造 为： 第 8 页 共 8 页。