第第 1 1 章章 绪论绪论一、选择题一、选择题 1. 算法的时间复杂度取决于（ C ） A问题的规模 B. 待处理数据的初态 C. A 和 B 2.计算机算法指的是（C） ，它必须具备（B） 这三个特性。 (1) A计算方法 B. 排序方法 C. 解决问题的步骤序列 D. 调度方法 (2) A可执行性、可移植性、可扩充性 B. 可执行性、确定性、有穷性 C. 确定性、有穷性、稳定性 D. 易读性、稳定性、安全性 3从逻辑上可以把数据结构分为（ C ）两大类。 A动态结构、静态结构 B顺序结构、链式结构 C线性结构、非线性结构 D初等结构、构造型结构 4以下与数据的存储结构无关的术语是（ D ） 。 A循环队列 B. 链表 C. 哈希表 D. 栈 5在下面的程序段中，对 x 的赋值语句的频度为（ C ）FOR i:=1 TO n DOFOR j:=1 TO n DO x:=x+1; A O(2n) BO(n) CO(n2) DO(log2n) 6连续存储设计时，存储单元的地址（ A ） 。 A一定连续 B一定不连续 C不一定连续 D部分连续，部分不连续 二、判断题二、判断题 1. 数据元素是数据的最小单位。( F ) 【山东师范大学 2001 一、1 （2 分） 】 2. 记录是数据处理的最小单位。 ( F ) 3数据的物理结构是指数据在计算机内的实际存储形式。( T )【山东师范大学 2001 一、2（2 分） 】 4. 在顺序存储结构中，有时也存储数据结构中元素之间的关系。( F ) 5. 顺序存储方式的优点是存储密度大，且插入、删除运算效率高。( F ) 三、填空三、填空 1数据的物理结构包括 的表示和 的表示。 2. 对于给定的 n 个元素,可以构造出的逻辑结构有（1） ， （2） ， （3） ，_（4）四 种。 3数据的逻辑结构是指 。 4一个数据结构在计算机中 称为存储结构。 5数据结构中评价算法的两个重要指标是 6已知如下程序段 FOR i:= n DOWNTO 1 DO 语句 1 BEGIN x:=x+1； 语句 2 FOR j:=n DOWNTO i DO 语句 3y:=y+1; 语句 4 END； 语句 1 执行的频度为 （1） ；语句 2 执行的频度为 （2） ；语句 3 执行的频度为 （3） ；语句 4 执行的频度为 （4） 。 答案：1数据元素 数据元素间关系 2集合 线性结构 树形结构 图状结构或网状结构。3数据的组织形式，即数据元素之间逻辑关系的总体。而逻辑关系是 指数据元素之间的关联方式或称“邻接关系” 。4表示（映像） 。5时间复杂度和空间复 杂度。 6 （1）n+1 （2）n （3）n(n+3)/2 （4）n(n+1)/2。 四、应用题四、应用题 1. 数据元素之间的关系在计算机中有几种表示方法？各有什么特点？ 四种表示方法 （1）顺序存储方式。数据元素顺序存放，每个存储结点只含一个元素。存储位置反映数 据元素间的逻辑关系。存储密度大，但有些操作（如插入、删除）效率较差。 （2）链式存储方式。每个存储结点除包含数据元素信息外还包含一组（至少一个）指针。 指针反映数据元素间的逻辑关系。这种方式不要求存储空间连续，便于动态操作（如插入、 删除等） ，但存储空间开销大（用于指针） ，另外不能折半查找等。 （3）索引存储方式。除数据元素存储在一地址连续的内存空间外，尚需建立一个索引表， 索引表中索引指示存储结点的存储位置，兼有静态和动态特性。 （4）散列存储方式。通过散列函数和解决冲突的方法，将关键字散列在连续的有限的地 址空间内，并将散列函数的值解释成关键字所在元素的存储地址，这种存储方式称为散列 存储。其特点是存取速度快，只能按关键字随机存取，不能顺序存取，也不能折半存取。 2若有 100 个学生，每个学生有学号，姓名，平均成绩，采用什么样的数据结构最方便， 写出这些结构？【山东师范大学 1996 二、2】 将学号、姓名、平均成绩看成一个记录（元素，含三个数据项） ，将 100 个这样的记录 存于数组中。因一般无增删操作，故宜采用顺序存储。typedeftypedef structstructintint num;/学号charchar name8;/姓名floatfloat score;/平均成绩node；node student100;第第 2 2 章章 线性表线性表一一 选择题选择题 1线性表是具有 n 个（ 数据元素 ）的有限序列（n0） 。 2若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算， 则利用（顺序表）存储方式最节省时间。 3某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素， 则采用（ 仅有尾指针的单循环链表 ）存储方式最节省运算时间。 4设一个链表最常用的操作是在末尾插入结点和删除尾结点，则选用( D )最节省时 间。 A. 单链表 B.单循环链表 C. 带尾指针的单循环链表 D.带头结点的双循环链表 5若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一个结点。则 采用（ D ）存储方式最节省运算时间。 A单链表 B双链表 C单循环链表 D带头结点的双循环链表 6. 链表不具有的特点是（ B ） A插入、删除不需要移动元素 B可随机访问任一元素 C不必事先估计存储空间 D所需空间与线性长度成正比7. 下面的叙述不正确的是（ BC ） A线性表在链式存储时，查找第 i 个元素的时间同 i 的值成正比B. 线性表在链式存储时，查找第 i 个元素的时间同 i 的值无关 C. 线性表在顺序存储时，查找第 i 个元素的时间同 i 的值成正比 D. 线性表在顺序存储时，查找第 i 个元素的时间同 i 的值无关 8. 若长度为 n 的线性表采用顺序存储结构，在其第 i 个位置插入一个新元素的算法的时间 复杂度为（ C ）(1next=px-next; px-next=py); 3在单链表中设置头结点的作用是(主要是使插入和删除等操作统一，在第一个元素之前 插入元素和删除第一个结点不必另作判断)。 4.顺序存储结构是通过(物理上相邻)表示元素之间的关系的;链式存储结构是通过(指针)表 示元素之间的关系的。 5. 带头结点的双循环链表 L 中只有一个元素结点的条件是：（L-next-next=L） 6. 在单链表 L 中，指针 p 所指结点有后继结点的条件是：（p-next!=null） 7.带头结点的双循环链表 L 为空表的条件是：（L-next=L s-next=p; pre-next=s; 4设双向循环链表中结点的数据域、前驱和后继指针域分别为 data,pre 和 next,试写出 在指针 p 所指结点之前插入一 s 结点的算法。 五、算法设计题 1 假设有两个按元素值递增次序排列的线性表，均以单链表形式存储。请编写算法将这 两个单链表归并为一个按元素值递减次序排列的单链表，并要求利用原来两个单链表 的结点存放归并后的单链表。LinkedList Union(LinkedList la,lb)la,lb 分别是带头结点的两个单链表的头指针，链表中的元素值按递增序排列，本算 法将两链表合并成一个按元素值递减次序排列的单链表。 pa=la-next; pb=lb-next;pa，pb 分别是链表 la 和 lb 的工作指针la-next=null; la 作结果链表的头指针，先将结果链表初始化为空。whilewhile(pa!=null 将 pa 的后继结点暂存于 r。pa-next=la-next; 将 pa 结点链于结果表中，同时逆置。la-next=pa;pa=r; 恢复 pa 为当前待比较结点。elseelse r=pb-next; 将 pb 的后继结点暂存于 r。 pb-next=la-next; 将 pb 结点链于结果表中，同时逆置。la-next=pb; pb=r; 恢复 pb 为当前待比较结点。whilewhile(pa!=null) 将 la 表的剩余部分链入结果表，并逆置。r=pa-next; pa-next=la-next; la-next=pa; pa=r; whilewhile(pb!=null)r=pb-next; pb-next=la-next; la-next=pb; pb=r; 算法 Union 结束。 算法讨论上面两链表均不为空的表达式也可简写为 whilewhile(papb=hb-next;lc=(LinkedList )malloc(sizeofsizeof(LNode);pc=lc;pc 是结果链表中当前结点的前驱whilewhile(papc=pa;pa=pa-next;elseelse pc-next=pb;pc=pb;pb=pb-next;ifif(pa)pc-next=pa; elseelse pc-next=pb;free(la);free(lb);释放原来两链表的头结点。算法时间复杂度为 O（m+n） ，其中 m 和 n 分别为链表 la 和 lb 的长度。 3. 已知递增有序的两个单链表 A，B 分别存储了一个集合。设计算法实现求两个集合的交 集的运算 A:=AB 本题是求交集，即只有同时出现在两集合中的元素才出现在结果表中。核心语句段如下：pa=la-next;pb=lb-next;设工作指针 pa 和 pb； pc=la;结果表中当前合并结点的前驱的指针。whilewhile(papc=pa;pa=pa-next;u=pb;pb=pb-next;free(u);elseelse ifif(pa-datadata) u=pa;pa=pa-next;free(u); elseelse u=pb; pb=pb-next; free(u); whilewhile(pa) u=pa; pa=pa-next; free(u); 释放结点空间 whilewhile(pb) u=pb; pb=pb-next; free(u);释放结点空间 pc-next=null;置链表尾标记。4. 已知长度为 n 的线性表 A 采用顺序存储结构，请写一时间复杂度为 0(n)、空间复杂度 为 0(1)的算法，该算法删除线性表中所有值为 item 的数据元素。 题目分析 在顺序存储的线性表上删除元素，要涉及到一系列元素的移动（删第 i 个 元素，第 i+1 至第 n 个元素要依次前移） 。本题要求删除线性表中所有值为 item 的数据元 素，并未要求元素间的相对位置不变。因此可以考虑设头尾两个指针（i=1，j=n） ，从两端 向中间移动，凡遇到值 item 的数据元素时，直接将右端元素左移至值为 item 的数据元素 位置。 voidvoid Delete（ElemType A ，intint n） A 是有 n 个元素的一维数组，本算法删除