《数据结构》习题集杨先凤朱小梅编西南石油大学计算机科学学院二零零七年九月目录习题一绪论...................................................................................................................................1习题二线性表...............................................................................................................................5习题三栈和队列.........................................................................................................................10习题四串.....................................................................................................................................14习题五数组和广义表.................................................................................................................17习题六树和二叉树.....................................................................................................................21习题七图.....................................................................................................................................27习题八查找.................................................................................................................................32习题九排序.................................................................................................................................36习题十文件.................................................................................................................................401习题一绪论一、单项选择题1．数据结构被形式地定义为(K，R)，其中K是（①）的有限集，R是K上的（②）有限集。①A．算法B．数据元素C．数据操作D逻辑结构②A．操作B．映像C存储D关系2．在数据结构中，从逻辑上可以把数据结构分成（）。A动态结构和静态结构B紧凑结构和非紧凑结构C线性结构和非线性结构D．内部结构和外部结构3．数据结构在计算机内存中的表示是指（）。A．数据的存储结构B数据结构C数据的逻辑结构D．数据元素之间的关系4．在数据结构中，与所使用的计算机无关的是数据的（）结构。A．逻辑B．存储c．逻缉和存储D．物理5．算法分析的目的是（①），算法分析的两个主要方面是（②）。①A找出数据结构的合理性B研究算法中的输入和输出的关系C分折算治的效率以求改进D分析算法的易读性和文档性②A空间复杂度和时间复杂度B正确性和简明性C可读性和文档性D数据复杂性和程序复杂性6．在存储数据时，通常不仅要存储各数据元素的值，而且还要存储（）。A数据的处理方法B．数据元素的类型C数据元素之间的关系D数据的存储方法7.算法的计算量的大小称为计算的（）。A．效率B.复杂性C.现实性D.难度8.算法的时间复杂度取决于（）A．问题的规模B.待处理数据的初态C.A和B9.下面说法错误的是（）(1）算法原地工作的含义是指不需要任何额外的辅助空间（2）在相同的规模n下，复杂度O(n)的算法在时间上总是优于复杂度O(2n)的算法（3）所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界（4）同一个算法，实现语言的级别越高，执行效率就越低A．(1)B.(1),(2)C.(1),(4)D.(3)10．在下面的程序段中，对x的赋值语句的频度为（）for(i=1;i<=n;i++)for(j=1;j<=n;j++)x:=x+1;A．O(2n)B．O(n)C．O(n2)D．O(log2n)二、判断题（在各题后填写“√”或“×”）1.线性结构只能用顺序结构来存放，非线性结构只能用非顺序结构来存放。（）2.数据元素是数据的最小单位。()3.记录是数据处理的最小单位。()24.算法就是程序。（）5.数据的逻辑结构是指数据的各数据项之间的逻辑关系；()6．数据的物理结构是指数据在计算机内的实际存储形式。()7.在顺序存储结构中，有时也存储数据结构中元素之间的关系。()8.顺序存储方式的优点是存储密度大，且插入、删除运算效率高。()9.线性表若采用链式存储结构时，要求内存中可用存...
