数据结构期中试卷附答案.docVIP

苏州大学 《数据结构》课程 期中试卷1 页 参考答案 单项选择题（20%） 数据结构是一门研究____的程序设计问题中，计算机的操作对象及其关系和操作等的学科。 数据类型 抽象数据类型 数值计算 非数值计算 D 计算机科学知识体中，数据结构课程属于____领域的综合性专业基础课。 离散结构Discrete Structures (DS) 程序设计语言Programming Languages (PL) 算法与复杂性Algorithms and Complexity (AL) 程序设计基础Programming Fundamentals (PF) D 数据结构中，与计算机存储器无关的是数据的_____结构。 物理 线性 存储 逻辑 D 数据结构可记为DS = {D, R}，其中D是数据对象，R是D中所有成员之间_____的有限集合。 操作 组织 运算 关系 D 具有相同性质的数据集合及在这个集合上的一组____，称为数据类型。 结构 算法 关系 操作 D 数据的物理结构不包括_____。 顺序(sequence) 链接(link)和数组 索引(index)和散列(Hash) 树(tree)和图(graph) D 在n较大情况下，下列时间复杂度T(n)中，效率较高的为_____。 O(2n) O(10*n2) O(10*n) O(100*log2n) D 顺序表的特点有_____。 插入、删除效率高 存储空间能动态分配 逻辑关系与物理位置不一致 可方便随机存取数据元素 D 链表的特点有_____。 插入、删除效率低 逻辑关系与物理位置一致 存储空间不能静态分配 随机存取数据元素效率低 D 链表用一组任意的存储单元来依次存放线性表的结点，这组存储单元_____。 按结点的前后次序排列 一定是不连续的 一定是连续的 即可以是连续的，也可以是不连续的 D 下面有关链表特性描述正确的是_____。 双链表的插入、删除效率要比单链表高 单链表的插入、删除效率要比双链表高 双链表中的结点能容易找到直接后继，但不易找到直接前趋 单链表中的结点能容易找到直接后继，但不易找到直接前趋 D 循环链表中最后一个结点的指针域指向_____ 。 前一个结点 后一个结点 尾结点 头结点 D _____的一个重要应用是在程序中实现递归调用。 队列 数组 生成树 栈 D 对栈的操作所具有的特征为____。 “先进后出” “先进先出” “后进后出” 上面三者都不是 A 在队列中，允许插入的的一端叫_____。 顶 底 队头 队尾 D 对队列的操作所具有的特征为____。 “先进先出” “先进后出” “后进先出” 上面三者都不是 A 当队列的最大长度不能预估时，宜采用_____。 循环队列 顺序队列 双端队列 链队列 D C语言中，串的长度表示方法是_____。 串长用独立的单元存储，通常为最后一个元素 串长存在第1个单元中 在串的末尾用回车表示 在串的末尾设结束标记’\0’ D 子串定位运算又称为_____。 查找 排序 替换 模式匹配 D _____不是常见的串表示方法。 块链存储表示 堆分配存储表示法 定长顺序存储表示法 栈和队列 D 判断题（10%） 数据结构由基本的抽象数据类型组成，并包括一组相关的服务或操作。 [ ] X 科学家尼克劳斯·沃斯(Niklaus Wirth)认为“算法＋数据结构＝程序” [ ] V 数据结构是一门研究数值计算中，计算机的操作对象及其关系和操作的学科。 [ ] X 在数据结构中，算法的每条指令或语句的执行次数是有限的。 [ ] V 数据结构中，与计算机存储器有关的是物理结构,与CPU有关的是逻辑结构。 [ ] X 通常空间复杂度高的算法，其时间复杂度也相对较高。 [ ] X 算法的时间复杂度达到T(n)=O(2n)时，当n增大后，算法的执行时间会急剧增大，这类算法常称为“坏”的算法。 [ ] V 算法的健壮性是指：算法应具有容错处理。当输入错误数据时，算法仍能输出正确的结果。 [ ] X 递归算法的表达相对非递归的算法更简洁，但实际运行效率不一定比后者高。 [ ] V 串是一种特殊的线性表，其数据元素是单个字符，其长度不能超过256。 [ ] X 填空题（20%） ____是数据的基本单位，在数据结构中，常简称为结点或节点。 数据元素 “数据结构”是介于计算机硬件、____和代数系统三者之间的核心课程。 程序设计 在数据结构中，一个算法的输入有____个。 有0或多个(=0) 在数据结构中，一个算法的输出有____个。 有1或多个(,=1) 有一个长度为N的顺序表，在第i（1≤i≤N+1）个结点之前插入一个结点，需要后移___个结点。 N +1-i(i=1时，后移N个结点；i=N+1时，后移0个结点) 栈能进行插入或删除