02142数据结构导论201510

数据结构导论试卷第1页共8页2015年10月高等教育自学考试全国统一命题考试数据结构导论试卷(课程代码02142)本试卷共4页，满分l00分，考试时间l50分钟。考生答题注意事项：1．本卷所有试题必须在答题卡上作答。答在试卷上无效，试卷空白处和背面均可作草稿纸。2．第一部分为选择题。必须对应试卷上的题号使用2B铅笔将“答题卡”的相应代码涂黑。3．第二部分为非选择题。必须注明大、小题号，使用0．5毫米黑色字迹签字笔作答。4．合理安排答题空间。超出答题区域无效。第一部分选择题一、单项选择题(本大题共l5小题，每小题2分，共30分)在每小题列出的四个备选项中只有一个是符合题目要求的，请将其选出并将“答题卡”的相应代码涂黑。未涂、错涂或多涂均无分。1．“能正确地实现预定的功能，满足具体问题的需要”。这种评价算法好坏的因素称为A．正确性B．易读性C．健壮性D．时空性2．有一程序片段：{i=0；s=0；while(s=n){i++；s=s+i；}}，其时间复杂度是C3．在如题3图所示的数组A中链接存储了一个线性表，表头指针为A[0]．next，则该线性表中第一个数据元素的值是A.60B．50C．78D．404．在一个长度为n(n1)的单链表上，设有头和尾两个指针，下列操作与链表长度有关的是A．删除单链表中的第一个元素B．删除单链表中的最后一个元素C．在单链表中第一个元素前插入一个新元素D．在单链表中最后一个元素后插入一个新元素5．某双向链表中的结点如题5图所示。删除t所指结点的操作为D数据结构导论试卷第2页共8页6．下列关于栈和队列的叙述中：Ⅰ栈和队列都是线性表；Ⅱ栈和队列都是顺序表；Ⅲ栈和队列都不能为空；Ⅳ栈和队列都能用于递归过程实现；Ⅴ栈的特点是先进后出、队列的特点是先进先出，其中正确的是A．Ⅰ和VB．Ⅰ、Ⅱ、VC．Ⅲ和VD．Ⅱ、Ⅳ、V7．二维数组A按行序优先顺序存储，每个数据元素占1个存储单元。若数据元素A[1][1]的存储地址是420，A[3][3]的存储地址是446，则A[5][5]的存储地址是A．470B.471C．472D．4738．若对一棵含有199个结点的完全二叉树按自上而下、从左到右依次对结点编号，根结点的编号为l，则树中最后一个结点(即编号为l99)的双亲结点的编号为A．99B．100C．101D．1989．对长度为15的有序顺序表进行二分查找，在各记录的查找概率均相等的情况下，查找成功时平均查找长度(ASL)为B10．在如题l0图所示的有向图中，从顶点l出发进行深度优先搜索可得到的结果序列是A．1423B．1432C．1342D．124311．设森林F中有三棵树，其结点的个数分别为m1、m2、m3，则与F对应的二叉树根结点的右子树上的结点数是A．ml+m2B．m2+m3C．ml+m3D．ml+m2+m312．假设通信电文使用的字符集为{a，b，e，d，e，f}，各字符在电文中出现的频率分别为{34，5，12，23，8，18}，利用构造Huffman树对每个字符进行编码，则其中编码长度最长的字符是A．a．bB．a，dC．b，eD．e，f数据结构导论试卷第3页共8页13．元素的进栈次序为A，B，c，D，E，出栈的第一个元素为E，则第四个出栈的元素为A．DB．CC．BD．A14．平均时间复杂度和在最坏情况下的时间复杂度均是0(Nlog2n)的排序算法是A．插入排序B．快速排序C．选择排序D．堆排序15．在待排记录中其关键字序列基本有序的前提下，时间效率最高的排序方法是A．直接插入排序B．快速排序C．选择排序D．堆排序第二部分非选择题二、填空题(本大题共l3小题，每小题2分，共26分)请在答题卡上作答。16．数据的存储结构又称为物理结构，可分为顺序存储、链式存储、___索引存储____以及散列存储等几种方式。17．一般说来，在每个逻辑结构上都定义了一组基本运算，通常这些运算包括：建立、__查找_____、读取、插入和删除等。18．某带有头结点的单链表的头指针为head，则判断该单链表为非空的条件是__head-next！=NULL_____。19．数组Q[n]表示一个循环队列，设f的值为队列中第一个元素的位置，r的值为队列中实际队尾的位置加1，并假定队列中最多只有n一1个元素，则计算队列中元素个数的公式是___(r-f+n)%n____.20．稀疏矩阵可以采用___三元组表示____方法进行压缩存储。21．含有11个结点的完全二叉树中度为l的结点的个数最多为____1___。22．高度(深度)为k的二叉树中结点个数最多是2K-l、最少是____k___。23．对于有n个顶点的无向图，所有生成树中都有且仅有___n-1____条边。24．设散列表的地址空间为0到12，散列函数为h(k)=kmodl3，用线性探测法解决冲突。现要将关键字序列{10，100，32，45，58，128，3，29，200，400，0}映射到该散列表中，则其中关键字值58的地址为___8____。25．假设有K个关键字互为同义词，若用线性探测法把这K个关键字用散列函数H将它们存人长度为m的散列表中(K≤m)，则至少共需进行___K(K+1)/2____次探测。26．在关键字序列{07，12，15，18，27，32，41，92}中用二分法查找和给定值92相等的关键字，在查找过程中依次和给定值92比较的关键字是___18,32,41,92____。27．影响排序算法时间复杂度的两个因素是关键字的___比较____次数和记录的移动次数。28．在直接插入、直接选择和冒泡这三种排序方法中，不稳定的排序方法是___直接选择____。三、应用题(本大题共5小题，每小题6分，共30分)请在答题卡上作答。29．设栈S和队列Q的初始状态均为空，7个元素abcdefg依次进入栈S。若每个元素出栈后立即进入队列Q，且7个元素出队的顺序是bdcfeag．现要求：(1)栈s的容量至少是多少?(2)在(1)的情况下，画出该栈中元素最多时的一个状态示意图。答：（1）栈S的容量至少是3。（2）栈的状态示意图如下（只画出一个即可）：数据结构导论试卷第4页共8页30．某二叉树结点的中序遍历序列为ABCDEFG、后序遍历序列为BDCAFGE．现要求：(1)画出该二叉树；(2)写出该二叉树的先序遍历序列；(3)该二叉树所对应的森林包括几棵树?答：（1）所构造出的相应的二叉树为：（2）其先序遍历序列是：EACBDGF（3）所对应的森林中含有2棵树31．假设有一棵完全二叉树按自上而下、从左到右的层序组织包含A、B、C、D、E、F、G这7个结点，分别给出其邻接矩阵和邻接表。答：32．要求给出至少2个不同的关键字序列，均能构造出如题32图所示的二叉排序树；对此你会得出什么结论?答：（1）e,f,g,b,a,d,c或e,b,d,c,a,f,g或e,f,g,b,d,c,a等等（2）不同的关键字序列，可能会得到同样的二叉排序树数据结构导论试卷第5页共8页33．采用快速排序方法对关键字序列{265，301，751，129，937，863，742，694，076，438}进行升序排序，写出其每趟排序结束后的关键字序列。答：初始态：[265301751129937863742694076438]第一趟：[076129]265[751937863742694301438]第二趟：076[129]265[438301694742]751[863937]第三趟：076129265[301]438[694742]751863[937]第四趟：076129265301438694[742]751863937第五趟：076129265301438694742751863937四、算法设计题(本大题共2小题，每小题7分．共l4分)请在答题卡上作答.34．写出复制一棵二叉树的算法。设原二叉树根结点由指针root指向，复制得到的二叉树根结点由指针newroot指向，函数头为：voidCopyTree(BTNode*root，BTNode，*newroot)，二叉树的存储结构为：答：voidCopyTree(BTNode*root,BTNode*newroot){if(!root)newroot=NULL;else{newroot=(BTNode*)malloc(sizeof(BTNode));newroot-data=root-data;CopyTree(root-lchild,newroot-lchild);CopyTree(root-rchild,newroot-rchild);}}35．已知带头结点的单链表L是按数据域值非递减有序链接的，试写一算法将值为x的结点插入表L中，使得L仍然是有序链接的。答：数据结构导论试卷第6页共8页数据结构导论试卷第7页共8页数据结构导论试卷第8页共8页