《数据结构 习题doc》由会员分享，可在线阅读，更多相关《数据结构 习题doc（64页珍藏版）》请在金锄头文库上搜索。
1、1第一章概论 一、填空题一、填空题1、 数据的存储结构可用四种基本的存储方法表示，分别是顺序、 链式 、 索引 和 散列。2、一个算法具有 5 个特性: 有穷性 、确定性、可行性，有零个或多个输入、有一个或多个输出 。3、 数据结构包括数据的 逻辑结构 、存储结构 和 运算（或基本操作）这三个方面的内容。4、数据结构中评价算法的两个重要指标是 时间 效率和 空间 效率。5、一个数据结构在计算机中的表示称为 存储结构 。6、从逻辑上可以把数据结构分为线性结构、非线性结构两大类7、数据逻辑结构除了集合以外，还包括线性结构、树形结构和 图形结构 。8、数据的存储结构形式包括顺序存储、链式存储、索引存
2、储和 散列存储。9、数据结构主要研究数据的逻辑结构、存储结构和算法（或运算）3 个方面的内容。10、算法效率的度量可以分为事先估算和 事后统计法 。二、单项选择题二、单项选择题1、 数据结构中，与所使用的计算机无关的是数据的是（ C ） ；A、 存储结构 B、 物理结构 C、逻辑结构 D、 物理和逻辑结构2、算法分析的目的是（ C ）A) 找出数据结构的合理性 B) 研究算法中的输入和输出的关系C) 分析算法的效率以求改进 D) 分析算法的易懂性和文档性3、 计算机算法指的是（ C ）A) 计算方法 B) 排序方法 C) 解决问题的有限运算序列 D) 调度方法4、 计算机算法必须具备输入、输出
3、和（ B ）等 5 个特性。A) 可行性、可移植性和可扩充性 B) 可行性、确定性和有穷性C) 确定性、有穷性和稳定性 D) 易读性、稳定性和安全性5、从逻辑上可以把数据结构分为（ C ）两大类。A）动态结构、静态结构 B）顺序结构、链式结构 C）线性结构、非线性结构 D）初等结构、构造型结构6、下列数据中，（ C ）是非线性数据结构。A栈 B. 队列 C. 完全二叉树 D. 堆7、算法分析的两个主要方面是（ A ） 。A) 空间复杂性和时间复杂性 B) 正确性和简明性2C) 可读性和文档性 D) 数据复杂性和程序复杂性8、下面程序段的时间复杂度是（ D ）i=1;while(inext=px
4、-next; _ px-next=py4在顺序表中访问任意一结点的时间复杂度均为 O(1) ，因此，顺序表也称为 随机存取 的数据结构。5、链接存储的特点是利用_指针 来表示数据元素之间的逻辑关系。在单链表中，除了首元结点外，任一结点的存储位置由 其直接前驱结点的链域的值 指示，查找结点都必须从头结点开始，因此，链表也称为 顺序存取 的数据结构。在 n 个结点的单链表中要删除已知结点*p，需找到它的前驱结点的地址，其时间复杂度为 O（n） ，在给定值为 x 的结点后插入一个新结点的时间复杂度为 O(n)_。7已知指针 p 指向单链表 L 中的某结点，则删除其后继结点的语句是： u=p-next
5、; 为空表的条件是：_ L-next=L 8带头结点的双循环链表 L 中只有一个元素结点的条件是：L-next-next=L；二、判断正误（在正确的说法后面打勾，反之打叉）（ ）1. 线性表的特点是每个元素都有一个前驱和一个后继。 （ ）2. 链表的物理存储结构具有同链表一样的顺序。（ ）3. 链表的删除算法很简单，因为当删除链中某个结点后，计算机会自动地将后续的各个单元向前移动。（ ）4. 取线性表的第 i 个元素的时间同 i 的大小有关.（ ）5. 顺序表结构适宜于进行顺序存取，而链表适宜于进行随机存取。 6. 顺序存储方式的优点是存储密度大，且插入、删除运算效率高。 （ ）( )7链表是
6、采用链式存储结构的线性表,进行插入、删除操作时，在链表中比在顺序存储结构中效率高。（ ）8. 线性表在顺序存储时，逻辑上相邻的元素未必在存储的物理位置次序上相邻。（ ）9. 顺序存储方式只能用于存储线性结构。（ ）10. 线性表的逻辑顺序与存储顺序总是一致的。( )11. 链表中的头结点仅起到标识的作用。( )12. 顺序存储结构的主要缺点是不利于插入或删除操作。5( ) 13线性表采用链表存储时，结点和结点内部的存储空间可以是不连续的。14顺序存储方式插入和删除时效率太低，因此它不如链式存储方式好。( )( )15. 对任何数据结构链式存储结构一定优于顺序存储结构。三、单项选择题三、单项选择
7、题1数据在计算机存储器内表示时，物理地址与逻辑地址相同并且是连续的，称之为（ C ）（A）存储结构 （B）逻辑结构 （C）顺序存储结构 （D）链式存储结构2一个向量第一个元素的存储地址是 100，每个元素的长度为 2，则第 5 个元素的地址是（ B ）（A）110 （B）108 （C）100 （D）1203. 在 n 个结点的顺序表中，算法的时间复杂度是 O（1）的操作是（ A ）（A） 访问第 i 个结点（1in）和求第 i 个结点的直接前驱（2in） （B） 在第 i 个结点后插入一个新结点（1in）（C） 删除第 i 个结点（1in）（D） 将 n 个结点从小到大排序4. 向一个有 12
8、7 个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动（ B ）个元素（A）8 （B）63.5 （C）63 （D）75. 线性表（ a1,a2,an）以链接方式存储时，访问第 i 位置元素的时间复杂性为（ C ）AO（i） BO（1） CO（n） DO（i-1）6. 链表是一种采用（ B ）存储结构存储的线性表；（A）顺序 （B）链式 （C）星式 （D）网状7. 线性表若采用链式存储结构时，要求内存中可用存储单元的地址（ D ）（A）必须是连续的 （B）部分地址必须是连续的（C）一定是不连续的 （D）连续或不连续都可以8 线性表在（ B ）情况下适用于使用链式结构实现。（）需经常修改
9、中的结点值 （）需不断对进行删除插入 （）中含有大量的结点 （）中结点结构复杂9 单链表的存储密度（ C ）（）大于 1； （）等于 1； （）小于 1； （）不能确定10对于一个头指针为 head 的带头结点的单链表，判定该表为空表的条件是（ B ）Ahead=NULL Bheadnext=NULL Cheadext=head Dhead!=NULL11下面关于线性表的叙述中，错误的是哪一个？（ B ）6A线性表采用顺序存储，必须占用一片连续的存储单元。B线性表采用顺序存储，便于进行插入和删除操作。C线性表采用链接存储，不必占用一片连续的存储单元。D线性表采用链接存储，便于插入和删除操作。1
10、2某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（ D ）存储方式最节省运算时间。A单链表 B仅有头指针的单循环链表 C双链表 D仅有尾指针的单循环链表13链表不具有的特点是（ B ） A插入、删除不需要移动元素 B可随机访问任一元素 C不必事先估计存储空间 D所需空间与线性长度成正比14、设一个链表最常用的操作是在末尾插入结点和删除尾结点，则选用( D )最节省时间。A. 单链表 B.单循环链表 C. 带尾指针的单循环链表 D.带头结点的双循环链表15、若长度为 n 的线性表采用顺序存储结构，在其第 i 个位置插入一个新元素的算法的时间复杂度为（ C ）(1n
11、ext=s;s-next=p-next; B s-next=p-next;p-next=s;Cp-next=s;p-next=s-next; D p-next=s-next;p-next=s;18、线性表是具有 n 个（ C ）的有限序列（n0）。 A表元素 B字符 C数据元素 D数据项 19、若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（ A ）存储方式最节省时间。A顺序表 B双链表 C带头结点的双循环链表 D单循环链表20在双向链表指针 p 的结点前插入一个指针 q 的结点操作是（ C ）。A. p- prior =q;q- next =p;p- pri
12、or - next =q;q- prior =q；B. p- prior =q;p- prior - next =q;q- next =p;q- prior =p- prior;C. q- next =p;q- prior =p- prior ;p- prior - next =q;p- prior =q;D. q- prior =p- prior ;q- next =q;p- prior =q;p- prior =q; 21、若某线性表中最常用的操作是取第 i 个元素和找第 i 个元素的前趋元素，则采用（D 7）存储方式最节省时间。A、单链表 B、双链表 C、单向循环 D、顺序表22. 链表
13、不具有的特点是（ B ） A插入、删除不需要移动元素 B可随机访问任一元素 C不必事先估计存储空间 D所需空间与线性长度成正比24. 单链表中，增加一个头结点的目的是为了（ C） 。A使单链表至少有一个结点 B标识表结点中首结点的位置C方面运算的实现 D说明单链表是线性表的链式存储25、在含有 n 个结点的顺序存储的线性表中，在任一结点前插入一个结点所需移动结点的平均次数为( B )。AnBn/2C(n+1)/2D(n-1)/226、设指针变量 p 指向单向链表中结点 A，若删除单向链表中结点 A，则需要修改指针的操作序列为（ A ） （q 是指向该类结点的空指针）Aq=p-next;p-da
14、ta=q-data;p-next=q-next;free(q);Bq=p-next;q-data=p-data;p-next=q-next;free(q);Cq=p-next; p-next=q-next; free(q);Dq=p-next; p-data=q-data; free(q);27、与单链表相比，双链表的优点之一是（ D） 。A、插入、删除操作更简单B、可以进行随机访问C、可以省略表头指针或表尾指针D、顺序访问相邻结点更灵活28、对于顺序存储的线性表，访问结点和增加、删除结点的时间复杂度为（ C ）。AO(n) O(n) B. O(n) O(1) C. O(1) O(n) D. O(1) O(1)四、简答题四、简答题1.试比较顺序存储结构和链式存储结构的优缺点。在什么情况下用顺序表比链表好？答： 顺序存储时，相邻数据元素的存放地址也相邻（逻辑与物理统一） ；要求内存中可用存储单元的地址必须是连续的。优点：存储密度大（1？） ，存储空间利用率高。缺点：插入或删除元素时不方便。链式存储时，相邻数据元素可随意存放，但所占存储空间分两部分，一部分存放
