若对大小均为n的有序顺序表和无序顺序表分别进行顺序查

数据结构练习（三）参考一、选择题1.顺序查找法适合于存储结构为的线性表A）哈希存储C）压缩存储D）索引存储2.一个长度为100的已排好序的表，用二分查找法进行查找，若查找不成功，至少比较________次。

A）9 B）8 C）73.采用顺序查找方法查找长度为n的线性表时，平均比较次数为。

A）n B）n/2 n+1）/2 D）（n-1）/24.对线性表进行折半查找时，要求线性表必须。

A）以顺序方式存储C）以链表方式存储D）以链表方式存储，且结点按关键字有序排列5.采用二分查找法查找长度为n的线性表时，每个元素的平均查找长度为。

A）O（n2）B）O（nlog2n）C）O（n）（log2n）6.有一个长度为12的有序表R[0…11]，按折半查找法对该表进行查找，在表内各元素等概率查找情况下查找成功所需的平均比较次数为。

A）35/12 C）39/12 D）43/127.有一个有序表为{1，3，9，12，32，41，45，62，75，77，82，95，99}，当采用折半查找法查找关键字为82的元素时，次比较后查找成功。

A）1 B.2 D）88.当采用分块查找时，数据的组织方式为。

A）数据分成若干块，每块内存数据有序每块内数据不必有序，但块间必须有序，每块内最大(或最小)的数据组成索引块C）数据分成若干块，每块内数据有序，每块内最大（或最小）的数据组成索引块D）数据分成若干块，每块（出最后一块外）中的数据个数需相同9.采用分块查找时，若线性表中共有625个元素，查找每个元素的概率相同，假设采用顺序查找来确定结点所在的块时，每块应有个结点最佳。

A）10 C）6 D）62510.不能生成右图所示二叉排序树的关键字序列是_____。

B）42531 C）45213 D）4231511.按____遍历二叉排序树，可以得到按值递增或递减次序的关键码序列。

A）先序C）后序D）层序12.在一棵平衡二叉树中，每个结点的平衡因子的取值范围是。

习题一一、填空题1. 算法具有有穷性、确定性、可行性、输入和输出五大特征。

2. 数据结构的内容包括以下三个方面：数据元素、数据关系和运算集合。

3. 数据结构的存储结构分为顺序、链式、索引、散列。

4. 评价算法性能的标准主要从算法执行时间和空间两方面考虑。

5. 在线性结构、树形结构和图状结构中，数据元素之间分别存在着1对1 、1对多和多对多关系。

二、分析题2.设n为整数，分析下列程序段中，用*标明的语句的语句频度及时间复杂度。

（1）for(n =1;n<=10;n++)*s=s+n;(2) for(i =1;i<=n;i++)*s=s+n;(3) for(i =1;i<=n;i++)for(j=1;j<=n;j++)*s=s+n(4) for(i =1;i<=n;i++)for(j=1;j<=i ;j++)*s=s+n;（5）for(i =1;i<=n;i++)for(j=1;j<=n;j++){c[i][j]=0;for(k=1;k<=n;k++)*c[i][j]=c[i][j]+a[i][k]*b[k][j];}习题二3.填空题1.在顺序表中，逻辑上相邻的元素，其物理位置上一定相邻。

2.在单链表中，逻辑上相邻的元素，其物理位置上不一定相邻。

3.设单链表中，指针p指向结点s，若要删除s之后的结点（若存在），则需修改指针的操作为P=s->next;s->next=s->next->next;free(p); 。

4.在一个长度为n的顺序表中，如果要删除第i个元素，需移动n-i+1 个元素。

二、选择题1.某线性表中最常用的操作是存取序号为i的元素和在最后进插入和删除运算，则采用（C ）存储方式的时间性能最好。

A.双向链表B.双向顺环链表C.顺序表D.单向顺环链表2.在一个单链表中，已知q结点是p结点的前驱结点，若在p和q之间插入s结点，则需执行（ C ）。

数据结构（本科）期末综合练习一（单选题）单选题1.一个数组元素a[i] 与( )的表示等价。

A.*(a+i)B.a+iC.*a+iD.&a+i2.若需要利用形参直接访问实参，则应把形参变量说明为( )参数。

A.指针B.引用C.传值D.常值3.下面程序段的时间复杂度为( )。

for(int i=0; i<m; i++)for(int j=0; j<n; j++) a[i][j] = i*j;A.O(m2)B.O(n2)C.O(m*n)D.O(m+n)4.执行下面程序段时，执行S语句的次数为( )。

for(int i=1; i<=n; i++)for(int j=1; j<=i; j++) S;A.n2B.n2/2C.n(n+1)D.n(n+1)/25.下面算法的时间复杂度为( )。

int f(unsigned int n) {if(n==0 || n==1) return 1;else return n*f (n-1);}A.O(1)B.O(n)C.O(n2)D.O(n!)6.一种抽象数据类型包括数据和( )两个部分。

A.数据类型B.操作C.数据抽象D.类型说明7.当一个作为实际传递的对象占用的存储空间较大并可能被修改时，应最好说明为( )，以节省参数值的传输时间和存储参数的空间。

A.基本类型B.引用型C.指针型D.常值引用型8.当需要进行标准I/O操作时，则应在程序文件中包含iostream.h头文件，当需要进行文件I/O 操作时，则应在程序文件中包含( )头文件。

A.fstream.hB.stdlib.hC.iomanip.hD.string.h9.一个记录r理论上占有的存储空间的大小等于所有域类型长度之和，实际上占有的存储空间的大小即记录长度为( )。

A.所有域长度之和B.最大域所占字节长度C.任意一个域长度D.sizeof(r)的值10.输出一个二维数组b[m][n]中所有元素值的时间复杂度为( )。

2022年上海海事大学计算机科学与技术专业《数据结构与算法》科目期末试卷A（有答案）一、选择题1、若需在O（nlog2n）的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方法是（）。

A.快速排序B.堆排序C.归并排序D.直接插入排序2、哈希文件使用哈希函数将记录的关键字值计算转化为记录的存放地址，因为哈希函数是一对一的关系，则选择好的（）方法是哈希文件的关键。

A.哈希函数B.除余法中的质数C.冲突处理D.哈希函数和冲突处理3、链表不具有的特点是（）。

A.插入、删除不需要移动元素B.可随机访问任一元素C.不必事先估计存储空间D.所需空间与线性长度成正比4、最大容量为n的循环队列，队尾指针是rear，队头：front，则队空的条件是（）。

A.（rear+1）MOD n=frontB.rear=frontC.rear+1=frontD.（rear-1）MOD n=front5、循环队列A[0..m-1]存放其元素值，用front和rear分别表示队头和队尾，则当前队列中的元素数是（）。

A.（rear-front+m）%mB.rear-front+1C.rear-front-1D.rear-front6、已知字符串S为“abaabaabacacaabaabcc”，模式串t为“abaabc”，采用KMP算法进行匹配，第一次出现“失配”（s!＝t）时，i＝j＝5，则下次开始匹配时，i和j的值分别（）。

A．i＝1，j＝0 B．i＝5，j＝0 C．i＝5，j＝2 D．i＝6，j＝27、下列叙述中，不符合m阶B树定义要求的是（）。

A．根结点最多有m棵子树 B．所有叶结点都在同一层上C．各结点内关键字均升序或降序排列 D．叶结点之间通过指针链接8、一棵非空的二叉树的前序序列和后序序列正好相反，则该二叉树一定满足（）。

A.其中任意一个结点均无左孩子B.其中任意一个结点均无右孩子C.其中只有一个叶结点D.其中度为2的结点最多为一个9、设X是树T中的一个非根结点，B是T所对应的二叉树。

第九章查找：习题习题一、选择题1．散列表查找中k个关键字具有同一散列值，若用线性探测法将这k个关键字对应的记录存入散列表中，至少要进行( )次探测。

A. k B。

k+l C. k(k+l）／2 D. l+k （k+l)/22．下述命题( )是不成立的。

A。

m阶B-树中的每一个结点的子树个数都小于或等于mB。

m阶B-树中的每一个结点的子树个数都大于或等于『m/2-1C。

m阶B-树中的每一个结点的子树高度都相等D。

m阶B—树具有k个子树的非叶子结点含有(k-l）个关键字3．如果要求一个基本线性表既能较快地查找，又能适应动态变化的要求，可以采用( ）查找方法.A。

分块 B. 顺序 C. 二分 D.散列4．设有100个元素，用折半查找法进行查找时，最大比较次数是( ),最小比较次数是( ）.A。

7，1 B.6，l C.5，1 D. 8，15．散列表长m=15，散列表函数H(key）=key％13。

表中已有4个结点：addr（18)=5；addr(32）=6; addr(59)=7；addr(73)=8;其余地址为空，如果用二次探测再散列处理冲突，关键字为109的结点的地址是( )。

A. 8 B。

3 C. 5 D。

46．用分块查找时，若线性表中共有729个元素，查找每个元素的概率相同，假设采用顺序查找来确定结点所在的块时，每块应分( )个结点最佳。

A。

15 B. 27 C。

25 D。

307．散列函数有一个共同性质，即函数值应当以( )取其值域的每个值。

A.同等概率B。

最大概率C。

最小概率D。

平均概率8．设散列地址空间为O.。

m—1，k为关键字，假定散列函数为h(k)=k％p，为了减少冲突，一般应取p为( )。

A.小于m的最大奇数B. 小于m的最大素数C.小于m的最大偶数D.小于m的最大合数9．当向一棵m阶的B-树做插入操作时，若使一个结点中的关键字个数等于( )，则必须分裂成两个结点。

A。

m B。

m-l C.m+l D。

《数据结构》填空作业题答案第1章绪论（已校对无误）1．数据结构包括数据的逻辑结构、数据的存储结构和数据的运算三方面的内容。

2．程序包括两个内容：数据结构和算法。

3. 数据结构的形式定义为：数据结构是一个二元组： Data Structure =（D，S）。

4. 数据的逻辑结构在计算机存储器内的表示，称为数据的存储结构。

5. 数据的逻辑结构可以分类为线性结构和非线性结构两大类。

6. 在图状结构中，每个结点的前驱结点数和后继结点数可以有多个。

7. 在树形结构中，数据元素之间存在一对多的关系。

8. 数据的物理结构，指数据元素在计算机中的标识（映象），也即存储结构。

9. 数据的逻辑结构包括线性结构、树形结构和图形结构 3种类型，树型结构和有向图结构合称为非线性结构。

10. 顺序存储结构是把逻辑上相邻的结点存储在物理上连续的存储单元里，结点之间的逻辑关系由存储单元位置的邻接关系来体现。

11. 链式存储结构是把逻辑上相邻的结点存储在物理上任意的存储单元里，节点之间的逻辑关系由附加的指针域来体现。

12. 数据的存储结构可用4种基本的存储方法表示，它们分别是顺序存储、链式存储、索引存储和散列存储。

13. 线性结构反映结点间的逻辑关系是一对一的，非线性结构反映结点间的逻辑关系是一对多或多对多。

14. 数据结构在物理上可分为顺序存储结构和链式存储结构。

15. 我们把每种数据结构均视为抽象类型，它不但定义了数据的表示方式，还给出了处理数据的实现方法。

16. 数据元素可由若干个数据项组成。

17. 算法分析的两个主要方面是时间复杂度和空间复杂度。

18. 一个算法的时间复杂度是用该算法所消耗的时间的多少来度量的，一个算法的空间复杂度是用该算法在运行过程中所占用的存储空间的大小来度量的。

19. 算法具有如下特点：有穷性、确定性、可行性、输入、输出。

20. 对于某一类特定的问题，算法给出了解决问题的一系列操作，每一操作都有它的确切的定义，并在有穷时间内计算出结果。

第九章 查找一、填空题1. 在数据的存放无规律而言的线性表中进行检索的最佳方法是 顺序查找（线性查找） 。

2. 线性有序表（a 1，a 2，a 3，…，a 256)是从小到大排列的，对一个给定的值k ，用二分法检索表中与k 相等的元素，在查找不成功的情况下，最多需要检索 8 次。

设有100个结点，用二分法查找时，最大比较次数是 7 。

3. 假设在有序线性表a[1..20]上进行折半查找，则比较一次查找成功的结点数为1；比较两次查找成功的结点数为 2 ；比较四次查找成功的结点数为 8 ,其下标从小到大依次是1,3,6,8,11,13,16,19______，平均查找长度为 3.7 。

解：显然，平均查找长度＝O （log 2n ）<5次（25）。

但具体是多少次，则不应当按照公式)1(log 12++=n nn ASL 来计算（即（21×log 221）/20＝4.6次并不正确！）。

因为这是在假设n ＝2m -1的情况下推导出来的公式。

应当用穷举法罗列：全部元素的查找次数为＝（1＋2×2＋4×3＋8×4＋5×5）＝74； ASL ＝74/20=3.7 ！！！ 4．折半查找有序表（4，6，12，20，28，38，50，70，88，100），若查找表中元素20，它将依次与表中元素 28，6，12，20 比较大小。

5. 在各种查找方法中，平均查找长度与结点个数n 无关的查找方法是 散列查找 。

6. 散列法存储的基本思想是由 关键字的值 决定数据的存储地址。

7. 有一个表长为m 的散列表，初始状态为空，现将n （n<m ）个不同的关键码插入到散列表中，解决冲突的方法是用线性探测法。

如果这n 个关键码的散列地址都相同，则探测的总次数是 n(n-1)/2=（ 1＋2＋…＋n-1） 。

(而任一元素查找次数 ≤n-1)8、设一哈希表表长M 为100 ，用除留余数法构造哈希函数，即H （K ）=K MOD P （P<=M ）, 为使函数具有较好性能，P 应选（ 97 ）9、在各种查找方法中，平均查找长度与结点个数无关的是哈希查找法 10、对线性表进行二分查找时，要求线性表必须以 顺序 方式存储，且结点按关键字有序排列。

头歌桂林电子科技大学数据结构答案1、线性结构中数据元素之间是（）关系。

[单选题] *A、一对多B、多对多C、多对一D、一对一(正确答案)2、在计算机中存储数据时，通常不仅要存储各数据元素的值，而且要存储（）。

[单选题] *A、数据的处理方法B、数据元素的类型C、数据元素之间的关系(正确答案)D、数据的存储方法3、计算机算法指的是（）。

[单选题] *A、计算方法B、排序方法C、求解问题的有限运算序列(正确答案)D、调度方法4、算法分析的目的是（）。

[单选题] *A、找出数据结构的合理性B、研究算法中的输入和输出的关系C、分析算法的效率以求改进(正确答案)D、分析算法的易懂性和文档性5、某算法的时间复杂度为O（n²），表明该算法的（）。

[单选题] *A、问题规模是n²B、执行时间等于n²C、执行时间与n²成正比(正确答案)D、问题规模与n²成正比6、线性表是（）。

[单选题] *A、一个有限序列，可以为空(正确答案)B、一个有限序列，不可以为空C、一个无限序列，可以为空D、一个无限序列，不可以为空7、在n个元素的顺序表中，算法的时间复杂度是O(1)的操作是（）。

[单选题] *A、访问第i个元素(2≤i≤n)及其前驱元素(正确答案)B、在第i(1≤i≤n)个元素后插入一个新元素C、删除第i个元素(1≤i≤n)D、将n个元素从小到大排序8、将两个分别含有m、n个元素的有序顺序表归并成一个有序顺序表，对应算法的时间复杂度是（）。

这里MIN表示取最小值。

[单选题] *A、O(n)C、O(m+n)(正确答案)D、O(MIN(m , n))9、线性表的链式存储结构和顺序存储结构相比，其优点是（）。

[单选题] *A、所有的操作算法实现简单B、便于随机存取C、便于插入和删除元素(正确答案)D、节省存储空间10、设线性表中有n个元素，以下运算中，（）在单链表上实现要比在顺序表上实现效率更高。

第九章 查找一、填空题1. 在数据的存放无规律而言的线性表中进行检索的最佳方法是 顺序查找（线性查找） 。

2. 线性有序表（a 1，a 2，a 3，…，a 256)是从小到大排列的，对一个给定的值k ，用二分法检索表中与k 相等的元素，在查找不成功的情况下，最多需要检索 8 次。

设有100个结点，用二分法查找时，最大比较次数是 7 。

3. 假设在有序线性表a[1..20]上进行折半查找，则比较一次查找成功的结点数为1；比较两次查找成功的结点数为 2 ；比较四次查找成功的结点数为 8 ,其下标从小到大依次是1,3,6,8,11,13,16,19______，平均查找长度为 3.7 。

解：显然，平均查找长度＝O （log 2n ）<5次（25）。

但具体是多少次，则不应当按照公式)1(log 12++=n n n ASL 来计算（即（21×log 221）/20＝4.6次并不正确！）。

因为这是在假设n ＝2m -1的情况下推导出来的公式。

应当用穷举法罗列：全部元素的查找次数为＝（1＋2×2＋4×3＋8×4＋5×5）＝74； ASL ＝74/20=3.7 ！！！4．折半查找有序表（4，6，12，20，28，38，50，70，88，100），若查找表中元素20，它将依次与表中元素 28，6，12，20 比较大小。

5. 在各种查找方法中，平均查找长度与结点个数n 无关的查找方法是 散列查找 。

6. 散列法存储的基本思想是由 关键字的值 决定数据的存储地址。

7. 有一个表长为m 的散列表，初始状态为空，现将n （n<m ）个不同的关键码插入到散列表中，解决冲突的方法是用线性探测法。

如果这n 个关键码的散列地址都相同，则探测的总次数是 n(n-1)/2=（ 1＋2＋…＋n-1） 。

(而任一元素查找次数 ≤n-1)8、设一哈希表表长M 为100 ，用除留余数法构造哈希函数，即H （K ）=K MOD P （P<=M ）, 为使函数具有较好性能，P 应选（ 97 ）9、在各种查找方法中，平均查找长度与结点个数无关的是哈希查找法10、对线性表进行二分查找时，要求线性表必须以 顺序 方式存储，且结点按关键字有序排列。

《数据结构》习题集第一章序论思考题：1。

1简述下列术语：数据、数据元素、数据对象、数据结构、存储结构、数据类型、抽象数据类型作业题：1。

2设有数据结构（D，R）,其中D={d1, d2, d3, d4}R=｛r1，r2｝r1=｛<d1, d2〉，<d2，d3>，<d3，d4〉，〈d1, d4>，〈d4，d2>, 〈d4, d1〉}r2=｛（d1, d2)，（d1，d3)，（d1, d4)，（d2, d4）, (d2, d3）}试绘出其逻辑结构示意图。

1。

3设n是正整数。

试写出下列程序段中用记号“△”标注的语句的频度: （1）i=1; k=0;while（i〈=n-1）｛△k+=10*i;i++;}（2) i=1； k=0；do {△k+=10＊i;i++；}while（i〈=n-1)（3）i=1； k=0；do {△k+ = 10*i; i++；｝while（i==n）;（4) i=1； j=0；while(i+j≤n) ｛△if（i〈j) i++;else j++;}（5) x=n; y=0; //n是不小于1的常数while（x〉=（y+1）＊（y+1）)｛△y++;｝(6）x=91; y=100；while （ y>0 ）{△if(x>100) ｛ x—=10； y——; }else x++ ；}(7) for( i=0; i〈n； i++）for（ j=i； j〈n; j++）for( k=j； k〈n； k++)△x+=2;1。

4 试写一算法，自大至小依次输出顺序读入的三个整数X，Y和Z的值。

1.5 已知k阶斐波那契序列的定义为:f0=0,f1=0，……,f k—2=0，f k—1=1；f n=f n—1+f n-2+……+f n-k, n=k,k+1,……试编写求k阶斐波那契序列的第m项值的函数算法,k和m均以值调用的形式在函数参数表中出现。