当前位置：文档之家 › 数据结构-问题求解题

数据结构-问题求解题

  • 格式：doc
  • 大小：70.50 KB
  • 文档页数：7

希望对大家有所帮助，多谢您的浏览！ 授课：XXX 《数据结构》习题库之四：问题求解题 1. 用序列（46，88，45，39，70，58，101，10，66，34）建立一个排序二叉树，画出该树，并求在等概率情况下查找成功的平均查找长度。

2. 给出一组关键字：29，18，25，47，58，12，51，10，分别写出按归并排序方法进行排序时的变化过程，每归并一次书写一个次序。

3. 给出一组关键字：29，18，25，47，58，12，51，10，分别写出按快速排序方法进行排序时的变化过程，每划分一次书写一个次序。

4. 给出一组关键字：29，18，25，47，58，12，51，10，分别写出按堆排序方法进行排序时的变化过程，先建成一个堆，然后每从堆顶取下一个元素后，将堆调整一次。

5. 已知树T的先序遍历序列为ABCDEFGHJKL，后序遍历序列为CBEFDJIKLHGA。请画出树T。 6. 对关键字序列(72，87，61，23，94，16，05，58)进行堆排序，使之按关键字递减次序排列。请写出排序过程中得到的初始堆和前三趟的序列状态。 初始堆：________________________________ 第1趟：________________________________ 第2趟：________________________________ 第3趟：________________________________

7. 在关键字序列(07，12，15，18，27，32，41，92)中用二分查找法查找和给定值92相等的关键字，请写出查找过程中依次和给定值“92”比较的关键字。

8. 若对序列（76，38，65，13，97，27，50，49）采用堆积排序法（按照值的大小从小到大）进行排序，请分别在下表中写出每一趟的结果： 原始序列 76 38 65 13 97 27 50 49 第1趟结果 第2趟结果 第3趟结果 第4趟结果

9. 已知一带权连通图采用邻接矩阵存储方法，并且邻接矩阵采用三元组表表示，其中，第一个三元组 (5，5，16)分别表示邻接矩阵的行数、列数字与非零元素的个数，从第二个三元组开始，依次按行序为主序的次序分别给出16个非零元素，它们依次为(1，2，7)，(1，3，6)，(1，4，9)，(2，1，7)，(2，3，8)，(2，4，4)，(2，5，4)，(3，1，6)，(3，2，8)，(3，4，6)，(4，1，9)，(4，2，4)，(4，3，6)，(4，5，2)，(5，2，4)，(5，4，2)；请分别画出该带权连通图的两棵最小生成树。

10. 已知散列范围为[0：9]，散列函数为H(key)=key MOD 9，处理冲突的方法为链地址法，请画出依次插入关键字8,10,14,19,21,23,28,32以后的哈希表。希望对大家有所帮助，多谢您的浏览！ 授课：XXX 11. 已知某非空二叉排序树采用顺序存储结构依次将所有结点的数据信息存放于一维数组 ABDIC□EF□□C□□□H 请分别写出该二叉树的前序遍历序列与中序遍历序列。

12. 折半查找过程可以利用一棵称之为“判定树”的二叉树来描述，请画出在长度为13的表中进行折半查找对应的判定树。

13. 设二叉树后根遍历的结果为BCA，画出所有可得到这一结果的二叉树。 14. 已某个不带权的无向图采用邻接矩阵存储方法依次将顶点的数据信息存放于一维数组ABCDEFGH中，边的信息存放于邻接矩阵中，邻接矩阵为 0 1 1 0 0 0 0 0 1 0 0 0 1 0 1 1 1 0 0 1 0 1 0 0 0 0 1 0 0 1 0 0 0 1 0 0 0 0 0 1 0 0 1 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 1 0 0 0 请写出从顶点A出发对该图进行深度优先搜索后得到的顶点序列。

15. 若对序列(49,38,27,13,97,76,50,65)采用泡排序法(按照值的大小从小到大)进行排序，请分别在下表中写出每一趟排序的结果。 原 始 序 列 49 38 27 13 97 76 50 65 第1趟的结果 第2趟的结果 第3趟的结果 第4趟的结果

16. 已知一稀疏矩阵的三元组存储如下所示，请画出其十字链表表示。 6 7 8 1 4 6 2 3 5 2 6 2 4 2 7 5 1 2 5 5 1 5 6 4 6 1 8

17. 若杂凑表的地址范围为[0:9]，杂凑函数为H(key)=(key2+2)MOD 9，并且采用链地址方法处理冲突，请画出元素7,4,5,3,6,2,8,9,1依次插入该杂凑表以后，该杂凑表的状态。

18. 若一棵树有n1个度为1的结点，n2个度为2的结点，…，nm个度为m的结点，求该树中叶结点的个数。(要求写出推导过程)希望对大家有所帮助，多谢您的浏览！ 授课：XXX 19. 已知某二叉树的中序遍历序列为CBGEAFHD，后序遍历序列为CGEBHFDA，请画出该二叉树的前序线索二叉树的二叉链表表示。

20. 现有一组单词(WEK,SUN,MON,TUE,WED,THU,FRI,SAT),其相应的散列函数值为(3，2，6，3，2，5，6，0)，散列表长度为10(散列地址空间为0..9)，要求： (1)构造该闭散列表，并用线性探测法解决冲突； (2)若对每个元素查找一次，求总的比较次数。

21. 设要将序列(Q，H，C，Y，P，A，M，S，R)按字母升序排序，请画出采用堆排序方法时建立的初始堆及第一次输出堆顶元素后筛选调整以后的堆。

22. 假设通信电文使用的字符集为{a,b,c,d,e,f}，名字符在电文中出现的频度分别为：34，5，12，23，8，18，试为这6个字符设计哈夫曼编码。请先画出你所构造的哈夫曼树(要求树中左孩子结点的权值小于右孩子结点的权值)，然后分别写出每个字符对应的编码。

23. 已知两个4×5的稀疏矩阵的三元组表分别如下： 0 1 4 16 0 1 1 32 1 2 2 18 1 2 2 -22 2 3 4 -25 2 2 5 69 3 4 2 28 3 3 4 25 4 4 2 51 请画出这两个稀疏矩阵之和的三元组表。

24. 从空树起，依次插入关键字40，8，90，15，62，95，12，23，56，32，构造一棵二叉排序树。 (1)画出该二叉排序树 (2)画出删去该树中元素值为90的结点之后的二叉排序树。

25. 画出在一个初始为空的AVL树中依次插入3，1，4，6，9，8，5，7时每一步插入后AVL树的形态。若做了某种旋转，说明旋转的类型。然后，给出在这棵插入后得到的AVL树中删去根结点后的结果。

26. 以知一组元素为（46，25，78，62，12，37，70，29），试画出按元素排列次序插入生成的一棵二叉搜索树。

27. 设散列表的长度ｍ＝１３；散列函数为Ｈ（Ｋ）＝Ｋ mod m，给定的关键码序列为19，14，23，01，68，20，84，27，55，11，试画出用线性探查法解决冲突时所构造的散列表。并求出在等概率的情况下，这种方法的搜索成功时的平均搜索长度和搜索不成功的平均搜索长度。

0 1 2 3 4 5 6 7 8 9 10 11 12

搜索成功时的平均搜索长度为：ASLsucc=希望对大家有所帮助，多谢您的浏览！ 授课：XXX 搜索不成功时的平均搜索长度为：ASLunsucc= 28. 某二叉树的结点数据采用顺序存储表示如下： 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 E A F D H C G I B （1）试画出此二叉树的图形表示。（3分） （2）写出结点D的双亲结点及左、右子女。（3分） （3）将此二叉树看作森林的二叉树表示，试将它还原为森林。（3分）

29. 设待排序序列为{10，18，4，3，6，12，1，9，15，8}，请给出用希尔排序每一趟的结果。增量序列取为5，3，2，1。（每一趟2分，共8分）

30、设散列表的长度为13，散列函数为H（k）=k%13，给定的关键码序列为19，14，23，01，68，20，84，27。试画出用线性探查法解决冲突时所构成的散列表。（8分） 0 1 2 3 4 5 6 7 8 9 10 11 12

24. 对于一个n×n的矩阵A的任一矩阵元素a[I][j]，按行存储时和按列存储时的地址之差是多少。（若设两种存储的开始存储地址LOC（0，0）及元素所占存储单元d相同）

25. 假定一组数据对象为（40，28，16，56，50，32，30，63），按次序插入每个对象生成一棵AVL树（高度平衡的二叉搜索树），根据插入过程填写下表，在相应位置填写所需要的调整类型：“左单旋转”、“右单旋转”、“先左后右双旋转”、“先右后左双旋转”，若不需要旋转则填写“无”。 数据： 调整： 40 28 16 56 50 32 30 63

26. 设有一个二维数组A[10][20]，按行存放于一个连续的存储空间中，A[0][0]的存储地址是200，每个数组元素占1个存储字，则A[6][2]的存储字地址是多少。 A[6][2]的存储字地址：

27. 已知一棵二叉树的中序和后序序列如下，求该二叉树的高度（假定空树的高度为-1）和度为2、度为1及度为0的结点个数。 中序序列：c,b,d,e,a,g,i,h,j,f 后序序列：c,e,d,b,i,j,h,g,f,a

高度： 度为2的结点数： 度为1的结点数： 度为0的结点数：

28. 假定一组记录为(36,75,83,54,12,67,60,40)，将按次序把每个结点插入到初始为空的一棵AVL树中，请回答在插入时需进行“左单旋转”、“右单旋转”、“先左后右双旋转”、“先右后左双旋转”，“不调整”的结点数各是多少？

合集下载

数据结构习题及答案

数据结构习题及答案

数据结构习题习题一一、选择题1、数据结构是一门研究非数值计算的程序设计问题中的操作对象以及它们之间的（B）和运算的学科。

A．结构B．关系C．运算D．算法2、在数据结构中，从逻辑上可以把数据结构分成（C）。

A．动态结构和静态结构B．紧凑结构和非紧凑结构C．线性结构和非线性结构D．逻辑结构和存储结构3、线性表的逻辑顺序和存储顺序总是一致的，这种说法（B）。

A．正确B．不正确C．无法确定D．以上答案都不对4、算法分析的目的是（C）。

A．找出算法的合理性B．研究算法的输人与输出关系C．分析算法的有效性以求改进D．分析算法的易懂性二、填空题1、数据是信息的载体，是对客观事物的符号表示，它能够被计算机识别、存储、加工和处理，数据是对能够有效的输人到计算机中并且能够被计算机处理的符号的总称。

例如，数学中所用到的整数和实数，文本编辑所用到的字符串等。

2、数据元素是数据的基本单位，有些情况下也称为元素、结点、顶点、记录等。

3、数据项是数据不可分割的最小单元，是具有独立含义的最小标识单位。

例如构成一个数据元素的字段、域、属性等都可称之为_数据项。

4、简而言之，数据结构是数据之间的相互关系，即数据的组织形式。

5、数据的逻辑结构是指数据之间的逻辑关系。

逻辑结构是从逻辑关系上描述数据，它与具体存储无关，是独立于计算机的。

因此逻辑结构可以看作是从具体问题抽象出来的数学模型。

6、数据的存储结构指数据元素及其关系在计算机存储器内的表示。

存储结构是逻辑结构在计算机里的实现，也称之为映像。

7、数据的运算是指对数据施加的操作。

它定义在数据的逻辑结构之上，每种逻辑结构都有一个数据的运算。

常用的有：查找、排序、插人、删除、更新等操作。

8、数据逻辑结构可以分为四种基本的类型，集合结构中的元素除了仅仅只是同属于一个集合_，不存在什么关系。

9、数据逻辑结构的四种基本类型中，线性结构_中的元素是一种一对一的关系，这种结构的特征是：若结构是非空集，则有且只有一个开始结点和一个终端结点，并且所有结点最多只能有一个直接前驱和一个直接后继。

数据结构-数据结构题库

数据结构-数据结构题库

第一章绪论一．单项选择题1．数据对象是指______。

A. 描述客观事物且由计算机处理的数值、字符等符号的总称B. 数据的基本单位C. 性质相同的数据元素的集合D. 相互之间存在一种或多种特定关系的数据元素的集合2．在数据结构中，数据的基本单位是_________。

A. 数据项B. 数据类型C. 数据元素D. 数据变量3．数据结构中数据元素之间的逻辑关系被称为______。

A. 数据的存储结构B. 数据的基本操作C. 程序的算法D. 数据的逻辑结构4．在数据结构中，与所使用计算机无关的是数据的_______。

A. 存储结构B. 逻辑和物理结构C. 逻辑结构D. 物理结构5．在链式存储结构中，数据之间的关系是通过________体现的。

A. 数据在内存的相对位置B. 指示数据元素的指针C. 数据的存储地址D. 指针6．在定义ADT时，除数据对象和数据关系外，还需说明_______。

A. 数据元素B. 算法C. 基本操作D. 数据项7．计算算法的时间复杂度是属于一种_______。

A. 事前统计的方法B. 事前分析估算的方法C. 事后统计的方法D. 事后分析估算的方法8．在对算法的时间复杂度进行估计的时候，下列最佳的时间复杂度是_______。

A. n2B. nlognC. nD. logn9．设使用某算法对n个元素进行处理，所需的时间是T(n)=100nlog2n+200n+2000，则该算法的渐近时间复杂度为_______。

A. O(1)B. O(n)C. O(200n)D. O(nlog2n)10．有如下递归函数fact(a)，其时间复杂度为_________。

int fact(int a){if(n==0)retrun 1;elsereturn(n*fact(n-1));}A. O(n)B. O(n2)C. O(n3)D. O(n4)11．线性表若采用链式存储结构时，要求内存中可用存储单元的地址_______。

数据结构试题集(8套卷子+答案)

数据结构试题集(8套卷子+答案)

《数据结构》试卷一一、填空题：（共２０分）1、当线性表的元素总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素时，应采用存储结构。

2、队列是限制插入只能在表的一端，而删除在表的另一端进行的线性表，其特点是。

3、在一棵二叉树中，度为０的结点个数为n0，度为２的个数为n2，则n0= 。

4、二叉树的前序遍历序列等同于该二叉树所对应森林的遍历序列5、对一棵二叉排序树，若以遍历该树，将得到一个以关键字递增顺序排列的有序序列。

6、三个结点a,b,c组成二叉树，共有种不同的结构。

7、在AVL树中，由于在Ａ结点的右孩子的右子树上插入结点，使Ａ结点的平衡因子由-1变为-2，使其失去平衡，应采用型平衡旋转。

8、图的遍历有两种,它们是。

9、堆排序的时间复杂度为。

10、在含有N个结点的二叉链表中有空链域，通常用这些空链域存储线索，从而得另一种链式存储结构----线索链表。

二、单项选择题（共２０分）１、若进栈序列为１，２，３，４，假定进栈和出栈可以穿插进行，则可能的出栈序列是（）（A）２，４，１，３（B）３，１，４，２（C）３，４，１，２（D）１，２，３，４２、有一棵非空的二叉树，（第０层为根结点），其第i层上最多有多少个结点？（）（A）２i（B）２1-i（C）２1+i（D） i３、设电文中出现的字母为A，B，C，D，E，每个字母在电文中出现的次数分别为９，２７，３，５，１１，按huffman编码，则字母A编码为（）（A）１０（B）１１０（C）１１１０（D）１１１１４、下面关于数据结构的叙述中，正确的叙述是（）（A）顺序存储方式的优点是存储密度大，且插、删除运算效率高（B）链表中每个结点都恰好包含一个指针（C）包含n个结点的二叉排序树的最大检索长度为logn2（D）将一棵树转为二叉树后，根结点无右子树５、程序段：y:＝0while n>=(y+1)*(y+1) doy:=y+1enddo的时间复杂度为（）（A）O(n) （B）O(n2) （C）O(n2/1) （D）O(1)6、排序方法中,关键码比较的次数与记录的初始排列无关的是( )(A) shell排序 (B) 归并排序 (C) 直接插入排序 (D) 直接选择排序7、数组q[0..n-1]作为一个环行队列,f 为当前队头元素的前一位置,r为队尾元素的位置,假定队列中元素的个数总小于n,则队列中元素个数为( )(A) r-f (B) n+f-r (C) n+r-f (D) (n+r-f) mod n8、为了有效的利用散列查找技术,需要解决的问题是:( )Ⅰ:找一个好的散列函数Ⅱ:设计有效的解决冲突的方法Ⅲ:用整数表示关键码值(A) Ⅰ和Ⅲ (B) Ⅰ和Ⅱ (C) Ⅱ和Ⅲ (D) Ⅰ,Ⅱ和Ⅲ9、引入线索二叉树的目的是（）(A) 加快查找结点的前驱或后继的速度(B) 为了能在二叉树中方便的进行插入与删除(C) :为了能方便的找到双亲(D) 使二叉树的遍历结果唯一10、用二分（折半）查找表的元素的速度比用顺序法（）(A) 必然快(B) 必然慢(C): 相等(D): 不能确定三、简答题：（共40分）１、已知某二叉树按中序遍历序列为BFDAEGC，按前序遍历序列为ABDFCEG,试画出该二叉树形状，并写出它的后序遍历序列。

数据结构问题解答

数据结构问题解答

4、若有n个元素的序列近似有序，即除掉少数K个元素后是有序序列且K<<n，在冒泡排序、快速排序、直接插入排序、堆排序方法中，请给出哪些方法不适合，哪些方法最快最适合，简述原因。

【参考解答】在待排序列近似有序的情况下，快速排序、堆排序都不太适合，直接插入排序、冒泡排序比较快。

因为在这种情况下，快速排序接近最坏情况，时间复杂度接近O(n2)，堆排序的时间复杂度仍然是O(nlogn)，相反，由于比较和移动次数较少，直接插入排序和冒泡排序的时间复杂度接近O(n)（这里假设冒泡排序在一趟排序没有交换发生时结束。

）五、编写一程序，实现在链式存储方式下的模式匹配。

设主串s和子串t分别以单链表存储，t和s 中每个字符均用一结点表示（如图）。

即s中第一次出现的位置指针。

【分析】思路类似简单模式匹配算法，但是，链表不像数组那样方便（i=i-j+2）回溯，所以应该增加一个指针变量（如下程序中的指针变量 ps），记录每一趟开始匹配的起点。

【参考解答】采用简单模式匹配算法的思路，为方便回溯，增加一个指针变量记录每一趟匹配开始的位置。

1．分别采用堆排序、快速排序、直接插入排序、归并排序算法对初始状态为递增序列的表按递增顺序排序，给出最省时间与最费时间的算法名称，简述原因。

【参考解答】对初始状态为递增序列的表按递增顺序排序，（1）直接插入排序最省时间。

因为算法此时总的比较次数为n-1，移动次数为0，为最好情况，是最省时间的。

（2）快速排序最费时间。

待排序列有序时，快速排序退化为冒泡排序，时间复杂度为O(n2)。

而堆排序和归并排序的时间复杂度都是O(nlogn)。

所以，此时快速排序最费时间。

4．只想得到N个元素序列中第K个最大元素之前的部分递减有序序列（K<<N），列出3种速度快的方法名称与原因。

【分析】总的思路是尽量避免对所有N个元素排序，从而提高算法的速度。

因为对N个元素进行快速排序、堆排序或归并排序，（平均）时间复杂度均为O(pNlogN)，p为某个常数，所以，所谓速度快的方法，时间复杂度应该更低。