当前位置:文档之家› 数据结构算法题复习

数据结构算法题复习

数据结构算法题复习
数据结构算法题复习

数据结构算法题复习(线性表和二叉树)1.设计在单链表中删除值相同的多余结点的算法。

2. 设计在链式存储结构上交换二叉树中所有结点左右子树的算法。

3. 设计一个在链式存储结构上统计二叉树中结点个数的算法。

4. 设计判断单链表中元素是否是递增的算法。

5.统计出单链表HL中结点的值等于给定值X的结点数。

6.设有两个集合A和集合B,要求设计生成集合C=A∩B的算法,其中集合A、B和C 用链式存储结构表示。

7.设计一个求结点x在二叉树中的双亲结点算法。

8设计计算二叉树中所有结点值之和的算法。

9.给出算法分别求出二叉树的叶结点、度数为1的结点、度数为2的结点的个数。

10.已知一个顺序表中的各结点值是从小到大有序的,设计一个算法,插入一个值为x的结点,使顺序表中的结点仍然是从小到大有序(不考虑空间不够用的情况)。

11.设计一个算法,判断一个单链表中的各个结点值是否递增有序(带头结点的单链表)。

数据结构与算法C语言版期末复习题

《数据结构与算法》期末复习题 一、选择题。 1.在数据结构中,从逻辑上可以把数据结构分为 C 。 A.动态结构和静态结构B.紧凑结构和非紧凑结构 C.线性结构和非线性结构D.内部结构和外部结构 2.数据结构在计算机内存中的表示是指 A 。 A.数据的存储结构B.数据结构C.数据的逻辑结构D.数据元素之间的关系 3.在数据结构中,与所使用的计算机无关的是数据的 A 结构。 A.逻辑B.存储C.逻辑和存储D.物理 4.在存储数据时,通常不仅要存储各数据元素的值,而且还要存储 C 。 A.数据的处理方法B.数据元素的类型 C.数据元素之间的关系D.数据的存储方法 5.在决定选取何种存储结构时,一般不考虑 A 。 A.各结点的值如何B.结点个数的多少 C.对数据有哪些运算D.所用的编程语言实现这种结构是否方便。 6.以下说法正确的是 D 。 A.数据项是数据的基本单位 B.数据元素是数据的最小单位 C.数据结构是带结构的数据项的集合 D.一些表面上很不相同的数据可以有相同的逻辑结构 7.算法分析的目的是 C ,算法分析的两个主要方面是 A 。 (1)A.找出数据结构的合理性B.研究算法中的输入和输出的关系C.分析算法的效率以求改进C.分析算法的易读性和文档性 (2)A.空间复杂度和时间复杂度B.正确性和简明性 C.可读性和文档性D.数据复杂性和程序复杂性 8.下面程序段的时间复杂度是O(n2) 。 s =0; for( I =0; i

算法与数据结构复习资料

算法与数据结构复习资料 一、单选题 在一个带有附加表头结点的单链表HL中,若要向表头插入一个由指针p指向的结点,则执行( B)。 A. HL=p;p->next=HL; B.p->next=HL->next;HL->next=p; C.p->next=HL;p=HL; D.p->next=HL;HL=p; 若顺序存储的循环队列的QueueMaxSize=n,则该队列最多可存储(B)个元素. A. n B.n-1 C.n+1 D.不确定 下述哪一条是顺序存储方式的优点?(A) A.存储密度大B.插入和删除运算方便 C. 获取符合某种条件的元素方便 D.查找运算速度快 设有一个二维数组A[m][n],假设A[0][0]存放位置在600 (10),A[3][3]存放位置在678 (10) , 每个元素占一个空间,问A[2][3] (10)存放在什么位置?(脚注 (10) 表示用10进制表示,m>3)C A.658 B.648 C.633 D.653 下列关于二叉树遍历的叙述中,正确的是( D) 。 A. 若一个树叶是某二叉树的中序遍历的最后一个结点,则它必是该二叉树的前序遍历最后一个结点 B.若一个点是某二叉树的前序遍历最后一个结点,则它必是该二叉树的中序遍历的最后一个结点 C.若一个结点是某二叉树的中序遍历的最后一个结点,则它必是该二叉树的前序最后一个结点 D.若一个树叶是某二叉树的前序最后一个结点,则它必是该二叉树的中序遍历最后一个结点 k层二叉树的结点总数最多为(A). A.2k-1 B.2K+1 C.2K-1 D. 2k-1 对线性表进行二分法查找,其前提条件是( C). A.线性表以链接方式存储,并且按关键码值排好序 B.线性表以顺序方式存储,并且按关键码值的检索频率排好序 C. 线性表以顺序方式存储,并且按关键码值排好序 D. 线性表以链接方式存储,并且按关键码值的检索频率排好序 对n个记录进行堆排序,所需要的辅助存储空间为(C) A. O(1og2n) B. O(n) C. O(1) D.O(n2) 对于线性表(7,34,77,25,64,49,20,14)进行散列存储时,若选用H(K)=K%7作为散列函数,则散列地址为0的元素有(D)个, A.1 B.2 C.3 D.4 下列关于数据结构的叙述中,正确的是( D). A. 数组是不同类型值的集合 B. 递归算法的程序结构比迭代算法的程序结构更为精炼 C. 树是一种线性结构 D. 用一维数组存储一棵完全二叉树是有效的存储方法 在决定选取何种存储结构时,一般不考虑( A )。 A.各结点的值如何B.结点个数的多少 C.对数据有哪些运算D.所用的编程语言实现这种结构是否方便 需要分配较大空间,插入和删除不需要移动元素的线性表,其存储结构是(B)。A.单链表B.静态链表C.线性链表D.顺序存储结构 设指针变量p指向单链表中结点A,若删除单链表中结点A,则需要修改指针的操作序列为(A)。 A.q=p->next;p->data=q->data;p->next=q->next;free(q); B.q=p->next;q->data=p->data;p->next=q->next;free(q); C.q=p->next;p->next=q->next;free(q);

数据结构与算法基础知识总结

数据结构与算法基础知识总结 1 算法 算法:是指解题方案的准确而完整的描述。 算法不等于程序,也不等计算机方法,程序的编制不可能优于算法的设计。 算法的基本特征:是一组严谨地定义运算顺序的规则,每一个规则都是有效的,是明确的,此顺序将在有限的次数下终止。特征包括: (1)可行性; (2)确定性,算法中每一步骤都必须有明确定义,不充许有模棱两可的解释,不允许有多义性; (3)有穷性,算法必须能在有限的时间内做完,即能在执行有限个步骤后终止,包括合理的执行时间的含义; (4)拥有足够的情报。 算法的基本要素:一是对数据对象的运算和操作;二是算法的控制结构。 指令系统:一个计算机系统能执行的所有指令的集合。 基本运算和操作包括:算术运算、逻辑运算、关系运算、数据传输。 算法的控制结构:顺序结构、选择结构、循环结构。 算法基本设计方法:列举法、归纳法、递推、递归、减斗递推技术、回溯法。 算法复杂度:算法时间复杂度和算法空间复杂度。 算法时间复杂度是指执行算法所需要的计算工作量。 算法空间复杂度是指执行这个算法所需要的内存空间。 2 数据结构的基本基本概念 数据结构研究的三个方面: (1)数据集合中各数据元素之间所固有的逻辑关系,即数据的逻辑结构; (2)在对数据进行处理时,各数据元素在计算机中的存储关系,即数据的存储结构;(3)对各种数据结构进行的运算。 数据结构是指相互有关联的数据元素的集合。 数据的逻辑结构包含: (1)表示数据元素的信息; (2)表示各数据元素之间的前后件关系。 数据的存储结构有顺序、链接、索引等。 线性结构条件:

(1)有且只有一个根结点; (2)每一个结点最多有一个前件,也最多有一个后件。 非线性结构:不满足线性结构条件的数据结构。 3 线性表及其顺序存储结构 线性表由一组数据元素构成,数据元素的位置只取决于自己的序号,元素之间的相对位置是线性的。 在复杂线性表中,由若干项数据元素组成的数据元素称为记录,而由多个记录构成的线性表又称为文件。 非空线性表的结构特征: (1)且只有一个根结点a1,它无前件; (2)有且只有一个终端结点an,它无后件; (3)除根结点与终端结点外,其他所有结点有且只有一个前件,也有且只有一个后件。结点个数n称为线性表的长度,当n=0时,称为空表。 线性表的顺序存储结构具有以下两个基本特点: (1)线性表中所有元素的所占的存储空间是连续的; (2)线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。 ai的存储地址为:adr(ai)=adr(a1)+(i-1)k,,adr(a1)为第一个元素的地址,k代表每个元素占的字节数。 顺序表的运算:插入、删除。(详见14--16页) 4 栈和队列 栈是限定在一端进行插入与删除的线性表,允许插入与删除的一端称为栈顶,不允许插入与删除的另一端称为栈底。 栈按照“先进后出”(filo)或“后进先出”(lifo)组织数据,栈具有记忆作用。用top表示栈顶位置,用bottom表示栈底。 栈的基本运算:(1)插入元素称为入栈运算;(2)删除元素称为退栈运算;(3)读栈顶元素是将栈顶元素赋给一个指定的变量,此时指针无变化。 队列是指允许在一端(队尾)进入插入,而在另一端(队头)进行删除的线性表。rear指针指向队尾,front指针指向队头。 队列是“先进行出”(fifo)或“后进后出”(lilo)的线性表。 队列运算包括(1)入队运算:从队尾插入一个元素;(2)退队运算:从队头删除一个元素。循环队列:s=0表示队列空,s=1且front=rear表示队列满

数据结构与算法复习题库含答案

数据结构复习题 第一章概论 一、选择题 1、研究数据结构就是研究( D )。 A. 数据的逻辑结构 B. 数据的存储结构 C. 数据的逻辑结构和存储结构 D. 数据的逻辑结构、存储结构及其基本操作 2、算法分析的两个主要方面是( A )。 A. 空间复杂度和时间复杂度 B. 正确性和简单性C. 可读性和文档性 D. 数据复杂性和程序复杂性 3、具有线性结构的数据结构是( D )。 A. 图 B. 树 C. 广义表 D. 栈 4、计算机中的算法指的是解决某一个问题的有限运算序列,它必须具备输入、输出、( B )等5个特性。 A. 可执行性、可移植性和可扩充性 B. 可执行性、有穷性和确定性 C. 确定性、有穷性和稳定性 D. 易读性、稳定性和确定性 5、下面程序段的时间复杂度是( C )。 fori0;im;i++ forj0;jn;j++ a[i][j]i*j; A. Om2 B. On2 C. Om*n D. Om+n 6、算法是( D )。

A. 计算机程序 B. 解决问题的计算方法 C. 排序算法 D. 解决问题的有限运算序列 7、某算法的语句执行频度为(3n+nlog2n+n2+8),其时间复杂度表示( C )。 A. On B. Onlog2n C. On2 D. Olog2n 8、下面程序段的时间复杂度为( C )。 i1; whilein ii*3; A. On B. O3n C. Olog3n D. On3 9、数据结构是一门研究非数值计算的程序设计问题中计算机的数据元素以及它们之间的( B )和运算等的学科。 A. 结构 B. 关系 C. 运算 D. 算法 10、下面程序段的时间复杂度是( A )。 is0; whilesn i++;s+i; A. On B. On2 C. Olog2n D. On3 11、抽象数据类型的三个组成部分分别为( A )。 A. 数据对象、数据关系和基本操作 B. 数据元素、逻辑结构和存储结构 C. 数据项、数据元素和数据类型 D. 数据元素、数据结构和数据类型 12、通常从正确性、易读性、健壮性、高效性等4个方面评价算法的质量,以下解释错误的是(D)。

数据结构与算法复习题10(C语言版)

习题9解答 判断题: 1.用向量和单链表表示的有序表均可使用折半查找方法来提高查找速度。答:FALSE (错。链表表示的有序表不能用折半查找法。) 2.有n个数据放在一维数组A[1..n]中,在进行顺序查找时,这n个数的排列有序或无序其平均查找长度不同。 答:FALSE (错。因顺序查找既适合于有序表也适合于无序表;对这两种表,若对于每个元素的查找概率相等,则顺序查找的ASL相同,并且都是(n+1)/2;对于查找概率不同的情况,则按查找概率由大到小排序的无序表其ASL要比有序表的ASL小。) 3.折半查找是先确定待查有序表记录的范围,然后逐步缩小范围,直到找到或找不到该记录为止。( ) 答:TRUE 4.哈希表的查找效率主要取决于哈希表哈希表造表时选取的哈希函数和处理冲突的方法。 答:TRUE 5.查找表是由同一类型的数据元素(或记录)构成的集合。 答:TRUE 单选题: 6.对于18个元素的有序表采用二分(折半)查找,则查找A[3]的比较序列的下标为( )。 A. 1、2、3 B. 9、5、2、3 C. 9、5、3 D.9、4、2、3

答:D (第一次??2/)181(+ = 9,第二次??2/)81(+ = 4,第三次??2/)31(+ = 2, (第四次??2/)33(+ = 3,故选D. 7. 顺序查找法适合于存储结构为____________的线性表。 A.散列存储 B.顺序存储或链式存储 C.压缩存储 D.索引存储 答:B 8.对线性表进行二分查找时,要求线性表必须( )。 A .以顺序方式存储 B. 以链接方式存储 C .以顺序方式存储,且结点按关键字有序排序 D. 以链接方式存储,且结点按关键字有序排序 答:C 9.设哈希表长m=14,哈希函数为H(k) = k MOD 11。表中已有4个记录(如下图所示),如果用二次探测再散列处理冲突,关键字为49的记录的存储地址是( )。 0 1 2 3 4 5 6 7 8 9 10 11 12 13 A .8 B. 3 C .5 D. 9 答:D (计算H(k),即H(49)=49 mod 11 = 5,冲突,进行二次探测再散列。而二次探测再散列的增量序列为:d i =12,-12,22,-22,32,…,土k 2,(k ≤m/2), 沿着增量序列选择不同的增量按照开放定址公式: H i =( H(key)+d i ) MOD m i =1,2,…,k (k ≤m-1)

数据结构与算法复习题10(C语言版)

习 9解答 判断题: 1.用向量和单链表表示的有序表均可使用折半查找方法来提高查找速度。 答:FALSE (错。链表表示的有序表不能用折半查找法。) 2.有n 个数据放在一维数组A[1..n]中,在进行顺序查找时,这n 个数的排列有序或无序其平均查找长度不同。 答:FALSE (错。因顺序查找既适合于有序表也适合于无序表;对这两种表,若对于每个元素的查找概率相等,则顺序查找的ASL 相同,并且都是(n+1)/2;对于查找概率不同的情况,则按查找概率由大到小排序的无序表其ASL 要比有序表的ASL 小。) 3.折半查找是先确定待查有序表记录的范围,然后逐步缩小范围,直到找到或找不到该记录为止。( ) 答:TRUE 4.哈希表的查找效率主要取决于哈希表哈希表造表时选取的哈希函数和处理冲突的方法。 答:TRUE 5.查找表是由同一类型的数据元素(或记录)构成的集合。 答:TRUE 单选题: 6.对于18个元素的有序表采用二分(折半)查找,则查找A[3]的比较序列的下标为( )。 A. 1、2、3 B. 9、5、2、3 C. 9、5、3 D.9、4、2、3 答:D (第一次??2/)181(+ = 9,第二次??2/)81(+ = 4,第三次??2/)31(+ = 2, (第四次??2/)33(+ = 3,故选D. 7. 顺序查找法适合于存储结构为____________的线性表。 A.散列存储 B.顺序存储或链式存储 C.压缩存储 D.索引存储 答:B 8.对线性表进行二分查找时,要求线性表必须( )。 A .以顺序方式存储 B. 以链接方式存储 C .以顺序方式存储,且结点按关键字有序排序 D. 以链接方式存储,且结点按关键字有序排序 答:C 9.设哈希表长m=14,哈希函数为H(k) = k MOD 11。表中已有4个记录(如下图

数据结构(c语言版)期末考试复习试题

《数据结构与算法》(c语言版)期末考复习题 一、选择题。 1.在数据结构中,从逻辑上可以把数据结构分为 C 。 A.动态结构和静态结构B.紧凑结构和非紧凑结构 C.线性结构和非线性结构D.内部结构和外部结构 2.数据结构在计算机内存中的表示是指 A 。 A.数据的存储结构B.数据结构C.数据的逻辑结构D.数据元素之间的关系 3.在数据结构中,与所使用的计算机无关的是数据的 A 结构。 A.逻辑B.存储C.逻辑和存储D.物理 4.在存储数据时,通常不仅要存储各数据元素的值,而且还要存储 C 。A.数据的处理方法B.数据元素的类型 C.数据元素之间的关系D.数据的存储方法 5.在决定选取何种存储结构时,一般不考虑 A 。 A.各结点的值如何B.结点个数的多少 C.对数据有哪些运算D.所用的编程语言实现这种结构是否方便。 6.以下说法正确的是 D 。 A.数据项是数据的基本单位

B.数据元素是数据的最小单位 C.数据结构是带结构的数据项的集合 D.一些表面上很不相同的数据可以有相同的逻辑结构 7.算法分析的目的是 C ,算法分析的两个主要方面是 A 。(1)A.找出数据结构的合理性B.研究算法中的输入和输出的关系C.分析算法的效率以求改进C.分析算法的易读性和文档性(2)A.空间复杂度和时间复杂度B.正确性和简明性 C.可读性和文档性D.数据复杂性和程序复杂性 8.下面程序段的时间复杂度是O(n2) 。 s =0; for( I =0; i

数据结构与算法复习题及参考答案

复习题集─参考答案 一判断题 (√)1. 在决定选取何种存储结构时,一般不考虑各结点的值如何。 (√)2. 抽象数据类型与计算机部表示和实现无关。 (×)3. 线性表采用链式存储结构时,结点和结点部的存储空间可以是不连续的。 (×)4. 链表的每个结点中都恰好包含一个指针。 (×)5.链表的删除算法很简单,因为当删除链中某个结点后,计算机会自动地将后续的各个单元向前移动。(×)6. 线性表的每个结点只能是一个简单类型,而链表的每个结点可以是一个复杂类型。 (×)7. 顺序表结构适宜于进行顺序存取,而链表适宜于进行随机存取。 (×)8. 线性表在物理存储空间中也一定是连续的。 (×)9. 顺序存储方式只能用于存储线性结构。 (√)10.栈是一种对所有插入、删除操作限于在表的一端进行的线性表,是一种后进先出型结构。 (√)11.对于不同的使用者,一个表结构既可以是栈,也可以是队列,也可以是线性表。 (√)12.栈是一种对所有插入、删除操作限于在表的一端进行的线性表,是一种后进先出型结构。 (√)13.两个栈共享一片连续存空间时,为提高存利用率,减少溢出机会,应把两个栈的栈底分别设在这片存空间的两端。 (×)14.二叉树的度为2。 (√)15.若二叉树用二叉链表作存贮结构,则在n个结点的二叉树链表中只有n—1个非空指针域。 (×)16.二叉树中每个结点的两棵子树的高度差等于1。 (√)17.用二叉链表法存储包含n个结点的二叉树,结点的2n个指针区域中有n+1个为空指针。 (√)18.具有12个结点的完全二叉树有5个度为2的结点。 (√)19.二叉树的前序遍历序列中,任意一个结点均处在其孩子结点的前面。 (×)20.在冒泡法排序中,关键值较小的元素总是向前移动,关键值较大的元素总是向后移动。 (×)21.计算机处理的对象可以分为数据和非数据两大类。[计算机处理的对象都是数据] (×)22.数据的逻辑结构与各数据元素在计算机中如何存储有关。 (×)23.算法必须用程序语言来书写。 (×)24.判断某个算法是否容易阅读是算法分析的任务之一。 (×)25.顺序表是一种有序的线性表。[任何数据结构才用顺序存储都叫顺序表] (√)26.分配给顺序表的存单元地址必须是连续的。 (√)27.栈和队列具有相同的逻辑特性。[它们的逻辑结构都是线性表] (√)28.树形结构中每个结点至多有一个前驱。 (×)29.在树形结构中,处于同一层上的各结点之间都存在兄弟关系。 (×)30.如果表示图的邻接矩阵是对称矩阵,则该图一定是无向图。 (×)31.如果表示图的邻接矩阵是对称矩阵,则该图一定是有向图。 (×)32.顺序查找方法只能在顺序存储结构上进行。 (×)33.折半查找可以在有序的双向链表上进行。

大数据结构考试精彩试题

数据结构辅导试题一 一、简答问题: 1.四类数据结构 2.线性结构与非线性结构有何差别? 3.简述算法的定义与特性。 4.设有1000个无序元素,仅要求找出前10个最小元素,在下列排序方法中(归并排序、基数排序、快速排序、堆排序、插入排序)哪一种方法最好,为什么? 二、判断正误:(每小题1分,共5分)正确在()内打√,否则打 。1.()二叉排序树或是一棵空树,或是具有下列性质的二叉树: 若它的左子树非空,则根结点的值大于其左孩子的值, 若它的右子树非空,则根结点的值大于其右孩子的值。 2.()索引顺序表的特点是块内可无序,块间要有序。 3.()子串是主串中任意个连续字符组成的序列。 4.()线性结构只能用顺序结构存放,非线性结构只能用链表存放。 5.()快速排序的枢轴元素可以任意选定。 三、单项选择题:(每小题1分,共4分) 1.栈S最多能容纳4个元素。现有6个元素按A、B、C、D、E、F的顺序进栈, 问下列哪一个序列是可能的出栈序列? A)E、D、C、B、A、F B)B、C、E、F、A、D C)C、B、E、D、A、F D)A、D、F、E、B、C 2.将一棵有100个结点的完全二叉树从根这一层开始,每一层从左到右依次对结点进行编号,根结点编号为1,则编号为49的结点的左孩子的编号为: A、98 B、99 C、50 D、48 3. 对下列关键字序列用快速排序法进行排序时,速度最快的情形是: A){21、25、5、17、9、23、30} B){25、23、30、17、21、5、9} B){21、9、17、30、25、23、5} D){5、9、17、21、23、25、30} 4. 设森林F中有三棵树,第一、第二和第三棵树的结点个数分别为M1、M2和M3。与森林F对应的二叉树根结点的右子树上的结点个数是: A)M1 B)M1+M2 C)M3 D)M2+M3 四、填空题:(每小题2分,共 20分) 1.设一哈希表表长M为100 ,用除留余数法构造哈希函数,即H(K)=K MOD P(P<=M), 为使函数具有较好性能,P应选 2.N个结点的二叉树采用二叉链表存放,共有空链域个数为 3.单链表与多重链表的区别是 4.在各种查找方法中,平均查找长度与结点个数无关的是 5.深度为6(根层次为1)的二叉树至多有个结点。 6.已知二维数组A[20][10]采用行序为主方式存储,每个元素占2个存储单元,并且A[10][5]的存储地址是1000,则A[18][9]的存储地址是 7.在一个单链表中p所指结点之后插入s所指结点时,应执行 s->next= 和p->next= 的操作. 8.广义表((a,b),c,d)的表头是 ,表尾是 9.循环单链表LA中,指针P所指结点为表尾结点的条件是 10.在一个待排序的序列中,只有很少量元素不在自己最终的正确位置上,但离他们的正确位置都不远,则使用排序方法最好。 五、构造题:(每小题5分,共25分) 1.已知一棵二叉树,其中序序列DBCAFGE,后序序列DCBGFEA,构造该二叉树。 2.设哈希表长度为11,哈希函数H(K)=(K的第一字母在字母表中的序号)MOD11,若输入顺序为(D,BA,TN,M,CI,I,K,X,TA),处理冲突方法为线性探测再散列或链

数据结构与算法分析—期末复习题及答案

单选题(每题2 分,共20分) 1.对一个算法的评价,不包括如下(B )方面的容。 A.健壮性和可读性B.并行性C.正确性D.时空复杂度 2.在带有头结点的单链表HL中,要向表头插入一个由指针p指向的结点,则执行( A )。 A. p->next=HL->next; HL->next=p; B. p->next=HL; HL=p; C. p->next=HL; p=HL; D. HL=p; p->next=HL; 3.对线性表,在下列哪种情况下应当采用链表表示?( B ) A.经常需要随机地存取元素 B.经常需要进行插入和删除操作 C.表中元素需要占据一片连续的存储空间 D.表中元素的个数不变 4.一个栈的输入序列为1 2 3,则下列序列中不可能是栈的输出序列的是( C ) A. 2 3 1 B. 3 2 1 C. 3 1 2 D. 1 2 3 6.若需要利用形参直接访问实参时,应将形参变量说明为(D )参数。 A.值B.函数C.指针D.引用 8.在稀疏矩阵的带行指针向量的存储中,每个单链表中的结点都具有相同的(A )。 A.行号B.列号C.元素值D.非零元素个数 10. 从二叉搜索树中查找一个元素时,其时间复杂度大致为(C )。 A. O(n) B. O(1) C. O(log2n) D. O(n2) 二、运算题(每题6 分,共24分) 1.数据结构是指数据及其相互之间的_联系。当结点之间存在M对N(M:N)的联系时,称这种结构为 __图__。 2.队列的插入操作是在队列的___尾_进行,删除操作是在队列的_首_进行。 3.当用长度为N的数组顺序存储一个栈时,假定用top==N表示栈空,则表示栈满的条件是___top==0___(要超出才为满)_______________。 4.对于一个长度为n的单链存储的线性表,在表头插入元素的时间复杂度为___ O(1)__,在表尾 插入元素的时间复杂度为___ O(n)___。 5.设W为一个二维数组,其每个数据元素占用4个字节,行下标i从0到7 ,列下标j从0到3 , 则二维数组W的数据元素共占用_128__个字节。W中第6 行的元素和第4 列的元素共占用__44_个字节。 若按行顺序存放二维数组W,其起始地址为100,则二维数组元素W[6,3]的起始地址__108_。 7.二叉树是指度为2的___有序___树。一棵结点数为N的二叉树,其所有结点的度的总和是 ___n-1____。 8.对一棵二叉搜索树进行中序遍历时,得到的结点序列是一个_有序序列__。对一棵由算术表达式组 成的二叉语法树进行后序遍历得到的结点序列是该算术表达式的__后缀表达式____。 9.对于一棵具有n个结点的二叉树,用二叉链表存储时,其指针总数为_____________个,其中 _______________个用于指向孩子,_________________个指针是空闲的。 10.若对一棵完全二叉树从0开始进行结点的编号,并按此编号把它顺序存储到一维数组A中,即编号为0 的结点存储到A[0]中。其余类推,则A[ i ]元素的左孩子元素为________,右孩子元素为_______________,双亲元素为____________。 11.在线性表的散列存储中,处理冲突的常用方法有________________________和 _____________________________两种。

数据结构与算法基础

数据结构与算法基础 一.判断题: 1.数据元素是数据的最小单位。 2.数据结构是带有结构的数据元素的集合。 3.数据结构、数据元素、数据项在计算机中的映像(或表示)分别称为存储结构、结点、数据域。 4.数据项是数据的基本单位。 5.数据的逻辑结构是指各数据元素之间的逻辑关系,是用户按使用需要而建立的。 6.数据的物理结构是指数据在计算机内实际的存储形式。 7.算法和程序没有区别,所以在数据结构中二者是通用的。 答案: 1.错误 2.正确 3.正确 4.错误 5.正确 6.正确 7.错误 二. 数据结构是研究数据的 A 和 B 以及它们之间的相互关系,并对这种结构定义相应的 C ,设计出相应的 D ,而确保经过这些运算后所得到的新结构是 E 结构类型。 供选择答案: A、B:a理想结构b抽象结构c物理结构d逻辑结构 C、D、E:a运算b算法c结构d规则e现在的f原来的 答案: A:cB;dC:aD:bE:f 三.从供选择的答案中选取正确的答案填在下面叙述中的横线上: 1. A 是描述客观事物的数字、字符以及所能输入到计算机中并被计算机程序加工处理的符号的集合。 2. B 是数据的基本单位,即数据集合中的个体。有时一个 B 由若干个___C____组成,在这种情况下,称 B 为记录。 C 是数据的最小单位。而由记录所组成的线性表为 D 。 3. E 是具有相同特性的数据元素的集合,是数据的子集。 4. F是带有结构特性数据元素的集合。 5. 被计算机加工的数据元素不是孤立无关的,它们彼此之间一般存在着某种联系。通常将数据元素的这种关系称为G。 6. 算法的计算量的大小称为计算的H。 供选择的答案: A-F:a数据元素b符号c记录d文件e数据f数据项g数据对象h关键字i数据结构

数据结构与算法期末考试复习试题

《数据结构与算法》复习题 一、选择题。 1.在数据结构中,从逻辑上可以把数据结构分为 C 。 A.动态结构和静态结构 B.紧凑结构和非紧凑结构 C.线性结构和非线性结构 D.内部结构和外部结构 2.数据结构在计算机内存中的表示是指 A 。 A.数据的存储结构 B.数据结构 C.数据的逻辑结构 D.数据元素之间的关系 3.在数据结构中,与所使用的计算机无关的是数据的 A 结构。 A.逻辑 B.存储 C.逻辑和存储 D.物理 4.在存储数据时,通常不仅要存储各数据元素的值,而且还要存储 C 。A.数据的处理方法 B.数据元素的类型 C.数据元素之间的关系 D.数据的存储方法 5.在决定选取何种存储结构时,一般不考虑 A 。 A.各结点的值如何 B.结点个数的多少 C.对数据有哪些运算 D.所用的编程语言实现这种结构是否方便。 6.以下说法正确的是 D 。 A.数据项是数据的基本单位 B.数据元素是数据的最小单位 C.数据结构是带结构的数据项的集合 D.一些表面上很不相同的数据可以有相同的逻辑结构 7.算法分析的目的是 C ,算法分析的两个主要方面是 A 。 (1)A.找出数据结构的合理性 B.研究算法中的输入和输出的关系C.分析算法的效率以求改进 C.分析算法的易读性和文档性 (2)A.空间复杂度和时间复杂度 B.正确性和简明性 C.可读性和文档性 D.数据复杂性和程序复杂性 8.下面程序段的时间复杂度是 O(n2) 。 s =0; for( I =0; i

for(j=0;jnext ==NULL C.head->next ==head D head!=NULL 15.带头结点的单链表 head 为空的判定条件是 B 。 A.head == NULL B head->next ==NULL C.head->next ==head D head!=NULL

算法与数据结构练习题

《算法与数据结构》习题1 一、单项选择题 1. 数据结构从逻辑上分为()。 A.动态结构和静态结构 B.内部结构和外部结构 C.紧凑结构和非紧凑结构 D.线性结构和非线性结构 2. 栈和队列的共同点是()。 A.都是先进后出 B.都是后进先出 C.只允许在端点处插入和删除元素 D.没有共同点 3.若按从左到右的顺序读入已知序列a、b、c、d、e、f、g中的元素,然后结合栈的操作,能得到下列序列中的哪些序列?() A.decfbga B.fegdacb C.efdgbca D.dcbefag 4. 在一个单链表中,若q结点是p结点的前驱结点,若在q与p之间插入结点 s,则执行()。 A.s→link=p→link;p→link =s;

B.p→link =s;s→link=q; C.p→link=s→link;s→link =p; D.q→link =s;s→link=p; 5.算法的计算量的大小称为计算的()。 A.效率 B. 复杂性 C. 现实性 D. 难度 6. 一个算法应该是()。 A.程序 B.问题求解步骤的描述 C.要满足五个基本特性 D.A和C 7. 从逻辑上可以把数据结构分为()两大类。 A.动态结构、静态结构 B.顺序结构、链式结构 C.线性结构、非线性结构 D.初等结构、构造型结构 8. 以下数据结构中,哪一个是线性结构?() A.广义表 B. 二叉树 C. 稀疏矩阵

D. 串 二、多项选择题 1. 以下说法正确的是()。 A. 二叉树的特点是每个结点至多只有两棵子树 B. 二叉树的子树无左右之分 C. 二叉树只能进行链式存储 D. 树的结点包含一个数据元素及若干指向其子树的分支2.在数组上能做的操作有()。 A.插入 B.删除 C.取值操作 D.赋值操作 3. 图的应用算法有()。 A. 克鲁斯卡尔算法 B. 哈弗曼算法 C. 迪杰斯特拉算法 D. 拓扑排序算法 4. 计算机算法必须具备()等特性。 A. 可行性、确定性 B. 可行性、可移植性 C. 输入、输出

全国计算机二级第1章数据结构与算法

考点1 算法的复杂度 【考点精讲】 1.算法的基本概念 计算机算法为计算机解题的过程实际上是在实施某种算法。 算法的基本特征:可行性、确定性、有穷性、拥有足够的情报。 2.算法复杂度 算法复杂度包括时间复杂度和空间复杂度。 名称 描述 时间复杂度 是指执行算法所需要的计算工作量 空间复杂度 是指执行这个算法所需要的内存空间 考点2 逻辑结构和存储结构 【考点精讲】 1.逻辑结构 数据的逻辑结构是对数据元素之间的逻辑关系的描述,它可以用一个数据元素的集合和定义在此集合中的若干关系来表示。数据的逻辑结构有两个要素:一是数据元素的集合,通常记为D;二是D上的关系,它反映了数据元素之间的前后件关系,通常记为R。一个数据结构可以表示成 B=(D,R) 其中B表示数据结构。为了反映D中各数据元素之间的前后件关系,一般用二元组来表示。例如,如果把一年四季看作一个数据结构,则可表示成 B =(D,R) D ={春季,夏季,秋季,冬季} R ={(春季,夏季),(夏季,秋季),(秋季,冬季)} 2.存储结构 数据的逻辑结构在计算机存储空间中的存放形式称为数据的存储结构(也称数据的物理结构)。 由于数据元素在计算机存储空间中的位置关系可能与逻辑关系不同,因此,为了表示存放在计算机存储空间中的各数据元素之间的逻辑关系(即前后件关系),在数据的存储结构中,不仅要存放各数据元素的信息,还需要存放各数据元素之间的前后件关系的信息。 一种数据的逻辑结构根据需要可以表示成多种存储结构,常用的存储结构有顺序、链接等存

储结构。 顺序存储方式主要用于线性的数据结构,它把逻辑上相邻的数据元素存储在物理上相邻的存储单元里,结点之间的关系由存储单元的邻接关系来体现。 链式存储结构就是在每个结点中至少包含一个指针域,用指针来体现数据元素之间逻辑上的联系。 考点3 线性结构和非线性结构 【考点精讲】 根据数据结构中各数据元素之间前后件关系的复杂程度,一般将数据结构分为两大类型:线性结构与非线性结构。如果一个非空的数据结构满足下列两个条件: (1)有且只有一个根结点; (2)每一个结点最多有一个前件,也最多有一个后件。 则称该数据结构为线性结构。线性结构又称线性表。在一个线性结构中插入或删除任何一个结点后还应是线性结构。栈、队列、串等都线性结构。 如果一个数据结构不是线性结构,则称之为非线性结构。数组、广义表、树和图等数据结构都是非线性结构。 考点4 栈 【考点精讲】 1.栈的基本概念 栈(stack)是一种特殊的线性表,是限定只在一端进行插入与删除的线性表。在栈中,一端是封闭的,既不允许进行插入元素,也不允许删除元素;另一端是开口的,允许插入和删除元素。通常称插入、删除的这一端为栈顶,另一端为栈底。当表中没有元素时称为空栈。栈顶元素总是后被插入的元素,从而也是最先被删除的元素;栈底元素总是最先被插入的元素,从而也是最后才能被删除的元素。 栈是按照“先进后出”或“后进先出”的原则组织数据的。例如,枪械的子弹匣就可以用来形象的表示栈结构。子弹匣的一端是完全封闭的,最后被压入弹匣的子弹总是最先被弹出,而最先被压入的子弹最后才能被弹出。 2.栈的顺序存储及其运算 栈的基本运算有三种:入栈、退栈与读栈顶元素。 (1)入栈运算:入栈运算是指在栈顶位置插入一个新元素。 (2)退栈运算:退栈是指取出栈顶元素并赋给一个指定的变量。 (3)读栈顶元素:读栈顶元素是指将栈顶元素赋给一个指定的变量。 考点5 队列 【考点精讲】 1.队列的基本概念 队列是只允许在一端进行删除,在另一端进行插入的顺序表,通常将允许删除的这一端称为队头,允许插入的这一端称为队尾。 当表中没有元素时称为空队列。 队列的修改是依照先进先出的原则进行的,因此队列也称为先进先出的线性表,或者后进后出的线性表。例如:火车进遂道,最先进遂道的是火车头,最后是火车尾,而火车出遂道的时候也是火车头先出,最后出的是火车尾。若有队列: Q =(q1,q2,…,qn) 那么,q1为队头元素(排头元素),qn为队尾元素。队列中的元素是按照q1,q2,…,qn 的顺序进入的,退出队列也只能按照这个次序依次退出,即只有在q1,q2,…,qn-1 都退队之后,qn才能退出队列。因最先进入队列的元素将最先出队,所以队列具有先进先出的

数据结构与算法(线性表)练习题

三、写一个算法合并两个已排序的线性表。(用两种方法:数组表示的线性表(顺序表)和指针表示的线性表(链表)) 要求:1、定义线性表节点的结构,并定义节点的型和位置的型。 2、定义线性表的基本操作 3、在1,2的基础上,完成本题。 4、在main 函数中进行测试:先构建两个有序的线性表,然后合并这两个线性表。 四、已知一个单向链表,试给出复制该链表的算法。 要求:1、定义线性表的节点的结构以及节点的型和位置的型。 2、定义线性表的基本操作 3、在1,2的基础上,完成本题。 4、在main 函数中进行测试:先构建一个线性表,并定义一个空线性表,然后进行复制。 五、写出从一个带表头的单链表中删除其值等于给定值x 的结点的算法函数: int delete(LIST &L, int x);如果x 在该链表中,则删除对应结点,并返回其在链表中的位置(逻辑位置,第一个结点的逻辑位置为1),否则返回-1。 要求:1、定义线性表的节点的结构以及节点的型和位置的型。 2、定义线性表的基本操作 3、在1,2的基础上,完成本题。 4、在main 函数中进行测试:先构建一个线性表,然后调用函数删除值等于给定值的节点。 六、写出一个将两个静态链表(属于同一个存储池)合并的算法函数: void Merge(cursor M, cursor N); 合并的方法是将N 链表中的所有结点添加到M 链表的后面,并将N 链表的表头结点添加到空闲结点链表中。 要求:1、定义静态链表的结点的结构以及结点的型SPACE 以及位置(position )和游标(cursor )的型。 2、定义静态链表的基本操作:void Initialize(); 初始化,将所有存储池中的结点设置为空闲;cursor GetNode(); 从空闲链中获取一个结点;void FreeNode(cursor q); 将结点q 加入到空闲链; void Insert ( elementtype x, position p, cursor M ); 在链表M 中的位置为p 的元素后面添加一个值为x 的结点;void Delete (cursor M, position p ); 在链表M 中删除位置为p 的元素的后一个元素。 3、在1、2的基础上完成本题。 4、在main 函数中进行测试:先构建一个存储池,然后在该存储池中创建两个静态 表,最后将这两个静态表合并。 七、利用指针表示的线性表(链表)表示一个多项式,并实现两个多项式的相加和相乘运算。假设多项式形式为:11 11...)(e e m e m x a x a t a x A m m +++= -- 其中,系数a i ≠0,指数e i 满足e m >e m-1>…>e 2>e 1>=0。 要求:1、定义多项式每一项的结构。 2、定义两个多项式的相加和相乘运算函数。 3、在main 函数中,构建两个多项式,并测试相加和相乘运算。

数据结构及算法_考试范围题及答案解析like

数据结构与算法考试参考题 专业:计算机科学与技术 13年 一、单选( 30分) 1. 在数据结构中,数据的逻辑结构可分( B.线性结构和非线性结构) 2. 在以单链表为存储结构的线性表中,数据元素之间的逻辑关系用( C.指向后继元素的指针表示) 3.设p指向单链表中的一个结点。S指向待插入的结点,则下述程序段的功能是( D.在结点*p之前插入结点*s ) s->next=p->next; p->next=s! t=p->data; p->data=s->data; s->data=t; B.在p所指结点的元素之前插入元素 D.在结点*p之前插入结点*s 4. 栈和队列都是( C:链式存储的线性结构) A:限制存取位置的线性结构 B:顺序存储的线性结构 C:链式存储的线性结构D:限制存取位置的非线性结构 5.下列关于线性表的基本操作中,属于加工型的操作是( B初始化、插入、删除操作) 6. 根据定义,树的叶子结点其度数( B.必等于0 ) 7. 多维数组之所以有行优先顺序和列优先顺序两种存储方式是因为( A.数组的元素处在行和列两个关系中) 8. 从广义表LS=(( p,q ),r,s )中分解出原子q的运算是(B. head(tall(head (LS))) 9. 在具有n个叶子结点的满二叉树中,结点总数为( C. 2n-1 ) 10. 若是有向图的一条边,则称( D. Vi与Vj不相邻接) 11. 二叉树若采用二叉链表结构表示,则对于n个结点的二叉树一定有( B. 2n个指针域其中n+1个指针为NULL ) 12. 在一个无向图中,所有顶点的度数之和等于边数的( B. 2倍) 13. 一个含n个顶点和e条弧的有向图以邻接矩阵表示法为存储结构,则计算该有向图中某个顶点出度的时间复杂度为( A.O(n) ) 14. 散列法存储中出现的碰撞(冲突)现象指的是( B.不同关键码值对应到相同的存储地址) 15. 循环链表适合的查找方式是( A. 顺序) 二、填空( 20分) 1.若一棵完全二叉树中含有121个结点,则该树的深度为( 7 ) 2.若以邻接矩阵表示有向图,则邻接矩阵上第i行中非零元素的个数之和即为顶点Vi的 。 3.二叉树的遍历主要有先序遍历、后序遍历和(中序遍历)三种。 4.深度为3的完全二叉树至少有( 4 )个结点。 5.若图的邻接矩阵是一个对称矩阵,则该图一定是一个(无向图) 6.若某无向图G的邻接表如下图所示,试给出以顶点V3为出发点,按广度优先搜索所产生的结点序列( V3-2V1-V4-V5 ) 7.在无向图中,若从顶点a到顶点b存在(路径),则称a与b之间是连通的。 8.我们通常把队列中允许删除的一端称为(队头) 9.表头和表尾均为( a,(b,c) )的广义表L= () 10.假定对有序表:( 3.4.5.7.24.30.42.54.63.72.87.95 )进行折半查找,若查找元素24(程序设定为向下取整),需依次与( 30.5.7.24 )元素进行比较。

相关主题
相关文档 最新文档