数据结构测试题.docx
28页
一、填空题（每空1分，共35分）1.2.3.4.5.6.7.8.9.10.11.第1章绪论数据结构是一门研究非数值计算的程序设计问题中计算机的们之间的..等的学科数据结构被形式地定义为（D, R）,其中D是..有限集合数据结构按逻辑结构可分为两大类，它们分别是为4类，分别是线性结构中元素之间存在.系，图形结构中元素之间存在性结构中，第一个结点.前驱结点；最后一个结点.结点在树形结构中，树根结点没有以及它的有限集合，R是D上的—.和.和关系，树形结构中元素之间存在.关系前驱结点，其余每个结点有且只有后继结点，其余每个结点有且只有结点，其余每个结点有且只有结点；叶子结点没有后继结点，其余每个结点的后继结点数可以任意在图形结构中，每个结点的前驱结点数和后继结点数可以数据结构包括数据的这三个方面的内容若细分.个后继.个前驱、数据的和数据的.数据的存储结构可用四种基本的存储方法表示，它们分别是数据的运算最常用的有5种，它们分别是,、,、一个算法的效率可分为效率和效率二、B （每小题1分，共5分）1.数据结构中，与所使用的计算机无关的是数据的（）结构A、存储B、物理C、逻辑D、物理和存储2.算法分析的目的是（）。
A、找出数据结构的合理性B、研究算法中的输入和输出的关系3.4.C、分析算法的效率以求改进算法分析的两个主要方面是：（A、空间复杂性和时间复杂性C、可读性和文档性计算机算法指的是（）D、B、分析算法的易懂性和文档性正确性和简明性D、数据复杂性和程序复杂性A、计算方法B、排序方法C、解决问题的有限运算序列 D、调度方法5. 计算机算法必须具备输入、输出和（ ）等5个特性A、可行性、可移植性和可扩充性 B、可行性、确定性和有穷性C、确定性、有穷性和稳定性 D、易读性、稳定性和安全性三、 判断下列叙述的对错如果正确，在题前的括号内填入“寸”否则填入“x”每题1 分，共8分）1. （）数据元素是数据的最小单位2. （）数据结构是数据对象与对象中数据元素之间关系的集合3. （）数据结构是具有结构的数据对象4. （）算法和程序原则上没有区别，在讨论数据结构时二者是通用的5. （）所谓数据的逻辑结构是指数据元素之间的逻辑关系6. （）数据的逻辑结构与数据元素本身的内容和形式无关7. （）数据结构是指相互之间存在一种或多种关系的数据元素的全体8. （）从逻辑关系上讲，数据结构主要分为两大类：线性结构和非线性结构。
四、 设n为正整数，分析下列各程序段中加下划线的语句的执行次数每题4分，共24分）（1） for （int i = 1； i <= n； i++） for （int j = 1; j <= n; j++）{ c[i][j]=0.0； for （int k = 1; k <= n; k++） c[i][j] = c[i][j] + a[i][k] * b[k][j]； }（2） x = 0； y = 0；for （ int i = 1; i <= n; i++）for（ int j = 1; j <= i; j++）for（ int k = 1; k <= j; k++） x = x + y；（3）k=0;for（i=1; i<=n; i++） for（j=I; j<=n; j++）k++;⑷ i=1； j=0;while(i+j<=n) (由皿j++；else i++;}(5) x=n; y=0;while(x>=(y+1)*(y+1))y++ ;(6) x=91; y=100;while(y>0) (if(x>100) {x-=10; y--; }else x++;}五、分析下面各程序段的时间复杂度(每小题4分，共16分)2. s=0;1. for (i=0; i 2、 向一个长度为n的向量的第i个元素(1WiWn+1)之前插入一个元素时，需向后移动 个元素3、 向一个长度为n的向量中删除第i个元素(IWiWn)时，需向前移动 个元素4、 在顺序表中访问任意一结点的时间复杂度均为，因此，顺序表支持访问5、 顺序表中逻辑上相邻的元素的物理位 相邻单链表中逻辑上相邻的元素的物理位置 相邻6、 在带头结点的非空单链表中，头结点的存储位置由 指示，首元素结点的存储位置由 指示，除首元素结点外，其它任一元素结点的存储位置由 指示7、 在n个结点的单链表中要删除已知结点*p，需找到它的，其时间复 杂度为8、 循环单链表La中，指针P所指结点为表尾结点的条件是 9、 已知L是无表头结点的单链表，且P结点既不是首元素结点，也不是尾元素结点a) a.在P结点后插入S结点的语句序列是：b. 在P结点前插入S结点的语句序列是：c. 在表首插入S结点的语句序列是： d. 在表尾插入S结点的语句序歹U是： 二、判断正误(在正确的说法后面打勾，反之打叉)(每小题1分，共10分)( )1、链表的每个结点中都恰好包含一个指针 )2、顺序存储结构只能用来存放线性结构；链式存储结构只能用来存放非线性结构。 )3、链表的删除算法很简单，因为当删除链中某个结点后，计算机会自动将后续各个单元向前移动 )4、线性表的每个结点只能是一个简单类型，而链表的每个结点可以是一个复杂类型 )5、顺序表结构适宜于进行顺序存取，而链表适宜于进行随机存取 )6、顺序存储方式的优点是存储密度大，且插入、删除运算效率高 )7、线性表在物理存储空间中也一定是连续的 )8、线性表在顺序存储时，逻辑上相邻的元素未必在存储的物理位置次序上相邻 9、顺序存储方式只能用于存储线性结构 ）10、线性表的逻辑顺序与存储顺序总是一致的三、单项选择题（每小题2分，共20分）（ ）1、数据在计算机存储器内表示时，物理地址与逻辑地址相同并且是连续的，称之为：A、存储结构 B、逻辑结构 C、顺序存储结构 D、链式存储结构（ ）2、在n个结点的顺序表中，算法的时间复杂度是O（1）的操作是：A、 访问第i个结点（IWiWn）和求第i个结点的直接前驱（2WiWn）B、 在第i个结点后插入一个新结点（IWiWn）C、 删除第i个结点（IWiWn）D、 将n个结点从小到大排序（ ）3、链表不具有的特点A、可随机访问任一个元素 8、插入删除不需要移动元素C、不必事先估计存储空间 D、所需空间与线性表的长度成正比（ ）4、链接存储的存储结构所占存储空间：A、 分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针B、 只有一部分，存放结点值C、 只有一部分，存储表示结点间关系的指针D、 分两部分，一部分存放结点值，另一部分存放结点所占单元数（ ）5、对于只在表的首、尾进行插入操作的线性表，宜采用的存储结构为。 A、顺序表 B、用头指针表示的单循环链表C、用尾指针表示的单循环链表 D、单链表（ ）6、线性表若采用链式存储结构时，要求内存中可用存储单元的地址：A、必须是连续的 B、部分地址必须是连续的C、一定是不连续的 D、连续或不连续都可以（ ）7、线性表L在 情况下适用于使用链式结构实现A、需经常修改L中的结点值 B、需不断对L进行删除插入C、L中含有大量的结点 D、L中结点结构复杂（ ）8、单链表的存储密度A、大于1 B、等于1 C、小于1 D、不能确定（ ）9、设a1、a2、a3为3个结点，整数P0，3, 4代表地址，则如下的链式存储结构称为P0分A、循环链表a1B、单链表a2A3双向循环链表 D、双向链表（ ）10、若线性表最常用的操作是存取第i个元素及其前驱的值，则采用—存储方式节省时间A、单链表8、双链表C、单循环链表D、顺序表四、简答题(每小题4分，共8分)1、试比较顺序存储结构和链式存储结构的优缺点在什么情况下用顺序表比链表好?2、在单链表和单循环链表中，若仅知道指针p指向某一结点，不知道表头指针，能否将结 点*?从链表中删去？若可以，其时间复杂度各为多少？五、阅读分析题(4分)指出以下算法中的错误和低效(即费时)之处，并将它改写为一个既正确又高效的算法。 Status DeleteK(SqList&a, int i, int k)(//本过程从顺序存储结构的线性表a中删除第i个元素起的k个元素if ( i<1 II k<0 II i+k> a.length ) return INFEASIBLE; //参数不合法else(for(count = 1; count
