当前位置:首页 >> 数学 >>

数据结构 试题(A)-答案 (2)

第二学期“数据结构”考试试题(A) 姓名 学号(序号)_ 班号 要求: 所有的题目的解答均写在答题纸上 (每张答题纸上要写清楚姓名、 班号和学号) , 需写清楚题目的序号。每张答题纸都要写上姓名和序号。 一、单项选择题(每小题 2 分,共 20 分) 1.数据的运算 a 。 A.效率与采用何种存储结构有关 B.是根据存储结构来定义的 C.有算术运算和关系运算两大类 D.必须用程序设计语言来描述 2. 链表不具备的特点是 a 。 A.可随机访问任一结点 B.插入删除不需要移动元素 C.不必事先估计存储空间 D.所需空间与其长度成正比 3. 在顺序表中删除一个元素的时间复杂度为 c 。 A.O(1) B.O(log2n) C.O(n) D.O(n2) 4.以下线性表的存储结构中具有随机存取功能的是 d 。 A. 不带头结点的单链表 B. 带头结点的单链表 C. 循环双链表 D. 顺序表 。 5. 一个栈的进栈序列是 a,b,c,d,e,则栈的不可能的输出序列是 c A.edcba C.dceab 。 6. 循环队列 qu 的队空条件是 d 。 B.decba D.abcde 。 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 7. 两个串相等必有串长度相等且 b 。 A.串的各位置字符任意 B.串中各位置字符均对应相等 C.两个串含有相同的字符 D.两个所含字符任意 。 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 。 9. 以下序列不是堆(大根或小根)的是 d 。 。 2 数据结构期末考试试题(共 3 页) 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} 。 10. 以下排序方法中,b ,在初始序列已基本有序的情况下,排序效率最高。 A.直接选择排序 B.昌泡排序 C.快速排序 D.堆排序 。 二、填空题(每题 2 分,共 10 分) 1. 将 f=1+ 1 2 + +… 3 1 1 n (n>3)转化成递归函数,其递归出口是 ① ,递归体是 ② 评分标准:每空 1 分 2.广义表((),a,(a),((a)))的长度是 4 ① ,深度是 3 ② 。 评分标准:每空 1 分 3. 具有 n 个结点的二叉树采用二叉链存储结构,共有 n+1 个空指针域。 4. 在有 n 个顶点的有向图中,每个顶点的度最大可达 n-1 。 5. 外排序的基本方法是归并法。它一般要经历文件预处理①和 多路归并②两个阶段。 评分标准:每空 1 分 三、问答题(共 30 分) 1.设 n 是偶数,试计算运行下列程序段后 m 的值并给出该程序段的时间复杂度(需 写出过程)。(6 分) int m=0,i,j; for (i=1;i<=n;i++) for (j=2*i;j<=n;j++) m++; ∑i=1```i=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 页) 3 3. 有一个有序表 R[1..13]={2,3,5,10,32,41,45,62,75,77,85,95,100}, 当用二分查找法查找 关键字为 75 的结点时,经多少次比较后查找成功,依次与哪些关键字进行比较?(6 分) 4. 设二叉排序树中关键字互不相同,证明,其中最小关键字结点必无左孩子,最大关 键字结点必无右孩子。(8 分) 四、算法设计题(共 40 分) 1.设计一个算法,将一个头结点为 L 的单链表(假设结点值为整数)分解成两个单链 表 L1 和 L2,使得 L1 链表中含有原链表 L1 中值为奇数的元素,而 L2 链表中含有原链表 A 中值为偶数的元素,且保持原来的相对顺序。(10 分) { 2.假设二叉树采用二叉链存储结构存储,设计一个算法,求先序遍历序列中第 k(1≤k ≤二叉树中结点个数)个结点的值。 (15 分) 3. 假设图 G 采用邻接表存储,设计一个算法,判断无向图 G 是否连通。若连通则返 回 1;否则返回 0。 (15 分) 提示:采用深度优先遍历或广度优先遍历求解,需写出相应的遍历算法。

相关文章:
数据结构 试题(A)-答案 (2).doc
数据结构 试题(A)-答案 (2) - 第二学期“数据结构”考试试题(A) 姓名
数据结构试题(A卷2012)答案.doc
数据结构试题(A卷2012)答案 - 2012~2013 学年第一学期期末考试 《数据结构》试题 A 答案 一、 选择(每空 2 分,共 30 分) BCDBD 二、 1. 答: (1)...
数据结构试卷(A卷及答案).doc
数据结构试卷(A卷及答案) - 数据结构试卷(A 卷) 一、选择题(30 分)
数据结构试题及答案(2).doc
数据结构试题答案(2) - 数据结构试题 一、 单选题(每题 2 分,共 20
数据结构试题库答案.doc
数据结构试题库答案 - 数据结构试题及答案 一、单项选择题 (1) 一个算法应该是( A) 程序 C) 要满足五个基本属性 (2) 算法指的是( A) 计算机程序 C) ...
数据结构试题及答案(免费).doc
数据结构试题及答案(免费) - 数据结构试卷(十一) 一、选择题(30 分) 1.设某无向图有 n 个顶点,则该无向图的邻接表中有( )个表头结点。 (A) 2n (B)...
数据结构试题及答案(10套最新).doc
数据结构试题答案(10套最新) - 一、 单选题(每题 2 分,共 20 分)
2012数据结构试卷A及答案 - 副本 (2)_图文.doc
2012数据结构试卷A答案 - 副本 (2) - ( 密封线内不答题 ) ……
数据结构试题2015(A卷)答案.doc
数据结构试题2015(A)答案 - 一、填空题(每空 1 分,共 10 分)
2011级数据结构试卷A及答案 - 副本 (2)_图文.doc
2011级数据结构试卷A答案 - 副本 (2) - ( 密封线内不答题 ) …
2007数据结构试题A(答案).doc
2007数据结构试题A(答案) - 准鄙 绷抨惑漂巍烙 刁现蛛退决 棒傲坏陋位郴
09-10学年第2学期数据结构试题(A卷).doc
09-10学年第2学期数据结构试题(A) - 2009~2010 学年第二学期期末考试 《数据结构》试题 A 一、选择题(每题 2 分,15 题,共 30 分,请将答案写到后附...
2016数据结构试卷A - 副本 (2).doc
2016数据结构试卷A - 副本 (2)_游戏_生活休闲。( 密封线内不答题 ) ……...所有答案请直接答在试卷上; 3.考试形式:闭卷; 4. 本试卷共十大题,满分 100...
2008级数据结构试卷A及答案_图文.doc
2008级数据结构试卷A答案_IT认证_资格考试/认证_教育专区。( 密封线内不答题...本试卷共十大题,满分 100 分,考试时间 120 分钟。 题号一二三得分 评卷人 ...
成教数据结构试题(A卷).doc
成教数据结构试题(A卷)_其它_工作范文_实用文档。班级: 鸵氖 簇箭絮桐钢囱 ...2、所有 答案都写在答 题纸上,答 到试卷上不给 分。郧它创麓 锈绑悦髓...
数据结构试题2(有答案).doc
数据结构试题2(有答案) - 试题 2 一、 单选题(每题 2 分,共 20 分
09-10第二学期数据结构试卷A-答案.doc
09-10第学期数据结构试卷A-答案_工学_高等教育_教育专区。大学计算机数据结构考试 学生签名: 承诺:我将严格遵守考场纪律,知道考试违纪、作弊的严重性,还知道请...
郑州轻工业学院09-10第二学期数据结构试卷(A卷)及答案.doc
郑州轻工业学院09-10第学期数据结构试卷(A卷)及答案 - 郑州轻工业学院 2009~2010 学年第二学期期末考试 《数据结构》试题 A 一、选择题(每题 2 分,15 ...
2011年数据结构期末试题(附完整答案).pdf
2011年数据结构期末试题(附完整答案) - 2011年数据结构期末试卷 1.算法分析的目的是( C )。 A.找出数据结构的合理性 C.分析算法的效率以求改进 B.研究算法中...
2007数据结构试题A(答案).doc
2007数据结构试题A(答案) - 中国人民公安大学 2006~2007 学年第二学期 2005 级侦查学专业计算机犯罪侦查专业方向 《数据结构》期末考试卷(A 卷)参考答案及评分...