2022年数据结构期末考试试题 .pdf
2005年 2006学年第二学期“ 数据结构 ” 考试试题（ A）姓名学号 ( 序号 )_ 答案隐藏班号要求：所有的题目的解答均写在答题纸上（每张答题纸上要写清楚姓名、班号和学号），需写清楚题目的序号。每张答题纸都要写上姓名和序号。一、单项选择题（每小题2 分，共 20 分）1数据的运算a 。A. 效率与采用何种存储结构有关 B. 是根据存储结构来定义的C. 有算术运算和关系运算两大类 D. 必须用程序设计语言来描述答： A。2. 链表不具备的特点是 a 。A. 可随机访问任一结点 B. 插入删除不需要移动元素C. 不必事先估计存储空间 D. 所需空间与其长度成正比答：参见本节要点3。本题答案为：A。3. 在顺序表中删除一个元素的时间复杂度为 c 。A.O(1) B.O(log2n) C.O(n) D.O(n2) 答： C。4以下线性表的存储结构中具有随机存取功能的是 d 。A. 不带头结点的单链表 B. 带头结点的单链表C. 循环双链表 D. 顺序表解 D 。5. 一个栈的进栈序列是a， b，c，d，e，则栈的不可能的输出序列是 c 。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 7 页 - - - - - - - - - A.edcba B.decba C.dceab D.abcde 答： C。6. 循环队列qu 的队空条件是 d 。A. (qu.rear+1)%MaxSize=(qu.front+1)%MaxSize B. (qu.rear+1)%MaxSize=qu.front+1 C.(qu.rear+1)%MaxSize=qu.front D.qu.rear=qu.front 答： D 。7. 两个串相等必有串长度相等且 b 。A. 串的各位置字符任意 B. 串中各位置字符均对应相等C. 两个串含有相同的字符 D. 两个所含字符任意答： B。8. 用直接插入排序对下面四个序列进行递增排序，元素比较次数最少的是c 。A.94,32,40,90,80,46,21,69 B.32,40,21,46,69,94,90,80 C.21,32,46,40,80,69,90,94 D.90,69,80,46,21,32,94,40 答： C。9. 以下序列不是堆（大根或小根）的是 d 。A.100,85,98,77,80,60,82,40,20,10,66 B.100,98,85,82,80,77,66,60,40,20,10 C.10,20,40,60,66,77,80,82,85,98,100 D.100,85,40,77,80,60,66,98,82,10,20 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 7 页 - - - - - - - - - 答： D 。10. 以下排序方法中，b ，在初始序列已基本有序的情况下，排序效率最高。A. 直接选择排序B. 昌泡排序C. 快速排序 D. 堆排序答： B。二、填空题（每题2 分，共 10 分）1. 将 f=1+ (n3)转化成递归函数，其递归出口是，递归体是答：f(1)=1 f(n)=f(n-1)+ 评分标准：每空1 分2广义表 (),a,(a),(a)的长度是4 ，深度是3 。答： 4 3 评分标准：每空1 分3. 具有 n 个结点的二叉树采用二叉链存储结构，共有n+1 个空指针域。答： n+1 。4. 在有 n 个顶点的有向图中，每个顶点的度最大可达2(n-1) n-1 。答： 2(n-1)。5. 外排序的基本方法是归并法。它一般要经历文件预处理和多路归并两个阶段。答：产生初始归并段（或顺串）多路归并评分标准：每空1 分三、问答题（共30 分）1设 n 是偶数，试计算运行下列程序段后m 的值并给出该程序段的时间复杂度（需写出过程） 。 （6 分）int m=0,i,j; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 7 页 - - - - - - - - - for (i=1;i=n;i+) for (j=2*i;j=n;j+) m+; i=1i=n/2 (n-2i+1) (n+1)n/2-2*(1+2+ n/2)=(n+1)n/2-2*(n/2+1)*n/2/2 =(n+1)n/2-(n/2+1)*n/2 =n2/4 2. 如果对线性表的运算只有4 种，即删除第一个元素，删除最后一个元素，在第一个元素前面插入新元素，在最后一个元素的后面插入新元素，则最好使用以下哪种存储结构，需说明理由：（10 分）（1 ）只有表尾指针没有表头指针的循环单链表（2 ）只有表尾指针没有表头指针的非循环双链表（3 ）只有表头指针没有表尾指针的循环双链表（4 ）既有表头指针也有表尾指针的循环单链表解本题答案为（ 3） ，原因是在该链表上实现这4 种运算的时间复杂度均为O(1) 。评分标准：结论占3 4 分，说明理由占6 分，如果结论错误，但分析了一部分运算的时间复杂度，给15 分。3. 有一个有序表R1.13=2,3,5,10,32,41,45,62,75,77,85,95,100，当用二分查找法查找关键字为75 的结点时， 经多少次比较后查找成功，依次与哪些关键字进行比较？（6 分）解： 1.13 ：R(1+13)/2=R7=4575，8.9 ：R(8+9)/2=R8=6275，名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 7 页 - - - - - - - - - 9.9 ：R(9+9)/2=R9=75 经 4 次比较后查找成功，依次45 、77 、62 和 75 关键字进行比较。评分标准： 比较次数正确给3 分，关键字正确给3 分（顺序要正确） 。部分正确给14 分。4. 设二叉排序树中关键字互不相同，证明，其中最小关键字结点必无左孩子，最大关键字结点必无右孩子。 （8 分）证明： 因为假设最小元为min ，若最小元min有左孩子min ，根据二叉排序树的定义得到minnext,*r1,*r2; L1=L;r1=L1; L2=( LinkList *)malloc(sizeof(LinkList); r2=L2; while (p!=NULL) if (p-data%2=1) /为奇数 r1-next=p;r1=p; p=p-next; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 7 页 - - - - - - - - - else / 为偶数 r2-next=p;r2=p; p=p-next; r1-next=r2-next=NULL; 评分标准：根据算法的正确性评分，不考虑算法的时间复杂度。2假设二叉树采用二叉链存储结构存储，设计一个算法，求先序遍历序列中第k(1 k 二叉树中结点个数) 个结点的值。 （15 分）解：先序遍历序列中根结点对应的序号为1。当二叉树b 为空时返回返回特殊字符( 为空格字符 )，当 k=n时表示找到了满足条件的结点，返回b-data；当 kn时，在左子树中查找，若找到了返回该值，否则在右子树中查找，并返回其结果。对应的递归模型如下：f(b,k,n)= 当 b=NULL时返回特殊字符 f(b,k,n)=b-data 当 k=n f(b,k,n)=(ch=f(b-lchild,k,n+1)= ?f(b-rchild,k,n+1):ch) 其他情况对应的递归算法如下：ElemType PreNode(BTNode *b,int k,int n) /n的初值为根结点对应的先序遍历序号即为1 ElemType ch; if (b=NULL) return ; if (n=k) return(b-data); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 7 页 - - - - - - - - - ch=PreNode(b-lchild,k,n+1); /遍历左子树if (ch!= ) return(ch); /在左子树中找到后返回ch=PreNode(b-rchild,k,n+1); /遍历右子树return(ch); / 返回右子树中的遍历结果 评分标准：如果先求出先序序列放在一个数组中，再取第k 个元素也正确。另外，根据算法的正确性评分，不考虑算法的时间复杂度。3. 假设图 G 采用邻接表存储，设计一个算法，判断无向图G 是否连通。若连通则返回1；否则返回0。 （15 分）提示：采用深度优先遍历或广度优先遍历求解，需写出相应的遍历算法。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页，共 7 页 - - - - - - - - -
