数据结构复习题1--和答案讲解.docx

说明： 此复习题为复习专用， 其给定了期末考试的 主要范围 ，并非给定考试原题， 考试时相关的题目基本都要进行改动。 因此同学们请注意，不要去背答案，要将题理解并做会。 （请注意这决不是原题，只有弄会才可能通过） 第 1 章 绪 论 ※ 1、数据结构主要研究的三个内容为 、 以及定义在该结构上的 。 2、数据结构从逻辑结构上可分为线性结构与非线性结构，其中树、图属于 。 3、数据结构被形式地定义为 （ D，R），其中 D 是 的有限集， R 是 D 上的 有限集。 4、数据的结构在计算机内存中的表示是指（ ） A. 数据的存储结构 B.数据结构 C.数据的逻辑结构 D.数据元素之间的关系 ※ 5、给出以下给定的两个程序段中划波浪线的语句的执行频度（次数） 。 （ 1） sum=0; for(i=0;in;i++) for(j=0; jn; j++) sum+=a[i][j]; （ 2） sum=0; for(i=0;in;i++) for(j=0; j=i; j++) sum+=a[i][j]; sum=0; for(i=0;in;i++) for(j=0; jm; j++) sum+=a[i][j]; ※ 6、分析以下各程序段的时间复杂度为（用大 O 记号表示） （ 1） i=s=0; while(sn) { i++; s+=i; } （ 2） i=1; while(i=n) i=i*3; 第 2 章 线性表 1、n(n=0) 个元素的线性结构表示成 (a1， a2, an)， a1 称为 元素， an 称为 元素， i 称为 ai 在线性表中的 。对任意一对相邻结点 ai、 ai+1 (1=in),a i 称为 ai+1 的 ， ai+1 称为 ai 的 。 2、在表长为 n 的顺序表的第 i 个位置插入一元素（ 1=i=n+1 ，插入的新元素作为第 i 个元素），则涉及到的元素的移动次数为 ；若删除第 i（ 1=i=n ）个元素，则涉及到的元素的移动次数为 。 ※ 3、线性表的顺序存储结构（顺序表）其存储空间 。 必须是连续的 B) 部分是连续的 一定是不连续的 D) 连续不连续都可以 4、一个顺序表的第一个元素的存储地址是 100，每个元素的长度为 2，则第 5 个元素的地址是 。 A ） 110 B） 108 C） 100 D ）120 5、顺序表的存取特点为 ，单链表的存取特点为 。 6、对于顺序表的优缺点，以下说法错误的是（ ） ①无需为表示结点间的逻辑关系而增加额外的存储空间 ②可以方便地随机存取表中的任一结点 ③插人和删除运算较方便 ④容易造成一部分空间长期闲置而得不到充分利用 7、以下说法正确的是 ①线性结构的基本特征是：每个结点有且仅有一个直接前趋和一个直接后继 ②线性表的各种基本运算在顺序存储结构上的实现均比在链式存储结构上的实现效率要低 ③在顺序存储线性表中，插入和删除元素时，移动元素的个数与插入或删除位置有关 ④顺序存储的线性表的插人和删除操作不需要付出很大的代价，因为平均每次操只有近一半的元素需要移动 8、以下说法正确的是（ ） ①顺序存储方式的优点是存储密度大、且插入、删除运算效率高 ②链表的每个结点中都恰好包含一个指针 ③线性表的顺序存储结构优于链式存储结构 ④顺序存储结构属于静态结构，链式结构属于动态结构 ※ 9、若某线性表中最常用的操作是取第 i 个元素和找第 i 个元素的前趋元素， 则采用（ ） 存储方式最节省时间。 ①顺序表 ②单链表 ③双链表 ④单循环链表 10、单链表中，增加头结点的目的是为了 ( ) ①使单链表至少有一个结点 ②标示表结点中首结点的位置 ③使每个元素都能有前驱结点，从而方便运算的实现 ④说明单链表是线性表的链式存储实现 ※ 11、对于一单链表 L(L 为头指针，且结点的后继指针分量为 next),其 p 结点（ p 为链表中某结点的指针）既不是第一个结点，也不是最后一个结点。 （ 1）在 p 结点后插入 s 结点 (s 为某结点的指针 )的语句序列是： 【1】 （ 2）删除 p 结点的直接后继结点的语句序列是： q=p-next; 【2】 ; free(q); （ 3）若 L 为带头结点的单链表，则： 在表首插入 s 结点的语句序列是： 【3】 单链表为空的判定条件为： 【4】 （ 4）若 L 为不带头结点的单链表，则： 在表首插入 s 结点的语句序列是： 【 5】 单链表为空的判定条件为： 【6】 ※ 12、已知 L 是带．表．头．结．点． 的双向链表 (L 为头指针，且结点的后继指针分量为 next，前驱指针为 pre ),其 p 结点（ p 为链表中某结点的指针）既不是首元结点，也不是尾元结点。 a）在 p 结点后插入 s 结点