当前位置:首页 >> 其它课程 >>

数据结构复习题tjuci0604


数据结构复习题
一、填空题
数据结构是一门研究非数值计算的程序设计问题中计算机的 以及它们之间 的 关系 和运算等的学科。 2. 数据结构包括数据的 、数据的 和数据的 等三个方面的内容。 3. 数据结构按逻辑结构可分为两大类,它们分别是 和 。 4.从逻辑关系上讲,数据结构主要分为 、 、 和 。 5. 线性结构中元素之间存在 关系,树形结构中元素之间存在

关系。 6. 在线性结构中,第一个结点 前驱结点,其余每个结点有且只有 1 个前驱结 点;最后一个结点 后续结点,其余每个结点有且只有 1 个后续结点。 7. 在树形结构中,树根结点没有 结点,其余每个结点有且只有 个前驱 结点;叶子结点没有 结点,其余每个结点的后续结点数可以 。 8. 在图形结构中,每个结点的前驱结点数和后续结点数可以 。 9.数据的存储结构常用的有两种,它们分别是 存储结构和 存储结构。 10.在顺序表中插入或删除一个元素,需要平均移动 元素,具体移动的元素 个数与 有关。 11. 在顺序表中访问任意一结点的时间复杂度均为 ,因此,顺序表也称为 的数据结构。 12. 顺序表中逻辑上相邻的元素的物理位置 相邻。单链表中逻辑上相邻的元素的 物理位置 相邻。在双链表中,每个结点设置了两个指针域,其中一个指向 结点, 另一个指向 结点。 13.线性表、 栈和队列都是 结构, 可以在线性表的 位置插入和删除元素; 对于栈只能在 插入和删除元素; 对于队列只能在 插入和 删除元素。 14. 栈是一种特殊的线性表,允许插入和删除运算的一端称为 。不允许插入 和删除运算的一端称为 。 15. 是被限定为只能在表的一端进行插入运算, 在表的另一端进行删除运算的 线性表。 16. 栈和队列是两种特殊的线性表,栈的操作特性是后进先出,队列的操作特性 是 ,栈和队列的主要区别在于对 。 17.顺序栈或链栈进行插入和删除操作的时间复杂度分别是 ,顺序队列或链 队列进行插入和删除操作的时间复杂度都是 。 18. 称为空串; 称为空白串。 19. 子串的定位运算称为串的模式匹配; 称为目标串, 称为模式。 20.两个串相等的充分必要条件是 。 21. 三元素组表中的每个结点对应于稀疏矩阵的一个非零元素,它包含有三个数据项, 分别表示该元素的 、 和 。 22.一棵深度为 6 的满二叉树有 个分支结点和 个叶子结点。 23. 设一棵完全二叉树具有 1000 个结点,则此完全二叉树有 个叶子结 点,有 个度为 2 的结点,有 个结点只有非空左子树,有 个结点只 有非空右子树。 24.一棵具有 257 个结点的完全二叉树,它的深度为 。 1.

25.设一棵完全二叉树有 700 个结点,则共有 个叶子结点。 i-1 26.一棵二叉树的第 i(i≥1)层最多有 2 个结点;一棵有 n(n>0)个结点的满二叉 树共有 个叶子结点和 个非终端结点。 27.深度为 k 的二叉树中,所含叶子的个数最多为 。 28.在具有 n 个结点的二叉链表中,共有 个指针域,其中 个指针域用于 指向其左右孩子, 剩下的 个指针域则是空的。 29. 图的存储结构主要有两种,分别是 、 等存储结构,遍历图 有 、 等方法。 30. 有向图 G 用邻接表矩阵存储,其第 i 行的所有元素之和等于顶点 i 的 。 31. 设有一稀疏图 G,则 G 采用 存储较省空间。 32. 设有一稠密图 G,则 G 采用 存储较省空间。 33.设无向图 G 中顶点数为 n,则图 G 至少有 条边,至多有 条边;若 G 为 有向图,则至少有 条边,至多有 条边。 34.图的深度优先遍历类似于树的 编历,它所用到的数据结构是 ;图的广度 优先遍历类似于树的 遍历,它所用到的数据结构是 。 35.数据的存放无规律而言的线性表中进行检索的最佳方法是 。 36. 假设在有序线性表 a[20]上进行折半查找,则比较一次查找成功的结点数为 1;比 较两次查找成功的结点数为 ;比较四次查找成功的结点数为 ;平均查找长 度为 。 37.折半查找有序表(4,6,12,20,28,38,50,70,88,100) ,若查找表中元素 20,它将依次与表中元素 比较大小。 38. 在各种查找方法中,平均查找长度与结点个数 n 无关的查找方法是 。 39. 散列法存储的基本思想是由 决定数据的存储地址。 40. 大多数排序算法都有两个基本的操作: 和 。 41. 在对一组记录(54,38,96,23,15,72,60,45,83)进行直接插入排序时,当 把第 7 个记录 60 插入到有序表时,为寻找插入位置至少需比较 次。 42. 在插入和选择排序中,若初始数据基本正序,则选用 ;若初始数据 基本反序,则选用 。 43. 在堆排序和快速排序中,若初始记录接近正序或反序,则选用 ; 若初始记录基本无序,则最好选用 。 44. 对于 n 个记录的集合进行冒泡排序,在最坏的情况下所需要的时间是 。 若对其进行快速排序,在最坏的情况下所需要的时间是 。 45. 对于 n 个记录的集合进行归并排序,所需要的平均时间是 ,所需要的附加空 间是 。 46. 设要将序列(Q, H, C, Y, P, A, M, S, R, D, F, X)中的关键码按字母序的升序重新排 列,则: 冒泡排序一趟扫描的结果是 ; 初始步长为 4 的希尔(shell)排序一趟的结果是 ; 二路归并排序一趟扫描的结果是 ; 快速排序一趟扫描的结果是 ; 堆排序初始建堆的结果是 。 48.、一个稀疏矩阵(5 行 6 列)如下图所示,写出对应的三元组顺序表。

000300 000800 000000 000000 000090

49、用广义表的取表头head和取表尾tail的运算,从广义表LS=(b,c,(f),((d)))中分解出 原子c的操作为( )。

二、单项选择题
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. 顺序存储结构中数据元素之间的逻辑关系是由( )表示的,链接存储结构中的数 据元素之间的逻辑关系是由( )表示的。 A. 线性结构 B. 非线性结构 C. 存储位置 D. 指针 7. 链接存储结构中的数据元素之间的逻辑关系是由( )表示的。 A. 线性结构 B. 非线性结构 C. 存储位置 D. 指针 8. 数据在计算机存储器内存储时, 物理地址与逻辑地址相同并且是连续的, 称之为 ( ) 。 A. 存储结构 B. 逻辑结构 C. 顺序存储结构 D. 链接存储结构 9. 向一个有 127 个元素的顺序表中插入一个新元素并保持原来顺序不变,平均要移动 ( )个元素 A. 8 B. 63.5 C. 63 D. 7 10. 链接存储的存储结构所占存储空间( ) 。 A. 分两部分,一部分存放结点值,另一部分存放表示结点间关系的指针 B. 只有一部分,存放结点值 C. 只有一部分,存储表示结点间关系的指针 D. 分两部分,一部分存放结点值,另一部分存放结点所占单元数 11. 链表是一种采用( )存储结构存储的线性表; A. 顺序 B. 链接 C. 星式 D. 网状 12. 线性表若采用链式存储结构时,要求内存中可用存储单元的地址:

A. 必须是连续的 B. 连续或不连续都可以 C. 部分地址必须是连续的 D. 一定是不连续的 13. 线性表L在( )情况下适用于使用链式结构实现。 A. 需经常修改L中的结点值 B.需不断对L进行删除插入 C. L中含有大量的结点 D. L中结点结构复杂 14. 单链表的存储密度 A. 大于 1 B. 等于 1 C. 小于 1 D. 不能确定 15.线性表的链接存储结构是一种( )的存储结构。 A. 随机存取 B. 顺序存取 C. 索引存取 D. 散列存取 16.链表不具有的特点是() 。 A.可随机访问任一元素 B. 插入、删除不需要移动元素 C. 不必事先估计存储空间 D. 所需空间与线性表长度成正比 17.数组Q[n]用来表示一个循环队列,f为当前队列头元素的前一位置,r为队尾 元素的位置,假定队列中元素的个数小于n,计算队列中元素的公式为( ) 。 A. r-f B.(n+f-r)% n; C. n+r-f; D.(n+r-f)% n 18.若已知一个栈的入栈序列是 1,2,3,…,n,其输出序列为 p1,p2,p3,…,pn, 若 p1=n,则 pi 为( ) 。 A.i B.n=i C.n-i+1 D.不确定 19.串是一种特殊的线性表,其特殊性体现在: A.可以顺序存储 B.数据元素是一个字符 C.可以链式存储 D.数据元素可以是多个字符 20.设有两个串 p 和 q,求 q 在 p 中首次出现的位置的运算称作( ) 。 A.连接 B.模式匹配 C.求子串 D.求串长 21.假设有 60 行 70 列的二维数组 a[1…60, 1…70]以列序为主序顺序存储,其基地址 为 10000, 每个元素占 2 个存储单元, 那么第 32 行第 58 列的元素 a[32,58]的存储地址为 ( ) 。 (无第 0 行第 0 列元素) A.16902 B.16904 C.14454 D.答案 A, B, C 均不对 答: (57 列×60 行+31 行)×2 字节+10000=16902 22.不含任何结点的空树( ) 。 A.是一棵树 B.是一棵二叉树 C.是一棵树也是一棵二叉树 D.既不是树也不是二叉树 23.二叉树是非线性数据结构,所以( ) 。 A.它不能用顺序存储结构存储 B.它不能用链式存储结构存储 C.顺序存储结构和链式存储结构都能存储 D.顺序存储结构和链式存储结构都不能使用 24.具有 n(n>0)个结点的完全二叉树的深度为( ) 。 A. ?log2(n)? B. ? log2(n)? C. ? log2(n) ?+1 D. ?log2(n)+1? 25.把一棵树转换为二叉树后,这棵二叉树的形态是( ) 。 A.唯一的 B.有多种 C.有多种,但根结点都没有左孩子 D.有多种,但根结点都没有右孩子 26.二叉树的前序序列和后序序列正好相反,则该二叉树一定是( )的二叉树。 A. 空或只有一个结点 B. 高度等于其结点数

C. 任一结点无左孩子 D. 任一结点无右孩子 27.讨论树、森林和二叉树的关系,目的是为了( ) 。 A 借助二叉树上的运算方法去实现对树的一些运算 B 将树、森林按二叉树的存储方式进行存储并利用二叉树的算法解决树的有关问题 C 将树、森林转换成二叉树 D 体现一种技巧,没有什么实际意义 28.一个高度为 h 的满二叉树共有 n 个结点,其中有 m 个叶子结点,则有( )成立。 A n=h+m B h+m=2n C m=h-1 D n=2m-1 29. 在一个图中,所有顶点的度数之和等于图的边数的( )倍。 A.1/2 B. 1 C. 2 D. 4 30.在一个有向图中,所有顶点的入度之和等于所有顶点的出度之和的( )倍。 A.1/2 B. 1 C. 2 D. 4 31. 有 8 个结点的无向图最多有( )条边。 A.14 B. 28 C. 56 D. 112 32. 有 8 个结点的无向连通图最少有( )条边。 A.5 B. 6 C. 7 D. 8 33. 有 8 个结点的有向完全图有( )条边。 A.14 B. 28 C. 56 D. 112 34. 用邻接表表示图进行广度优先遍历时,通常是采用( )来实现算法的。 A.栈 B. 队列 C. 树 D. 图 35.无向图的邻接矩阵是一个( ) ,有向图的邻接矩阵是一个( ) 。 A.上三角矩阵 B.下三角矩阵 C.对称矩阵 D.无规律 36.在表长为n的链表中进行线性查找,它的平均查找长度为( ) 。 A. ASL=n; B. ASL=(n+1)/2; C. ASL= n +1; D. ASL≈log2(n+1)-1 37.折半查找有序表(4,6,10,12,20,30,50,70,88,100) 。若查找表中元素 58,则它将依次与表中( )比较大小,查找结果是失败。 A.20,70,30,50 B.30,88,70,50 C.20,50 D.30,88,50 38.对 22 个记录的有序表作折半查找,当查找失败时,至少需要比较( )次关键字。 A.3 B.4 C.5 D. 6 39. 链表适用于( ) 。查找 A.顺序 B.折半查找 C.顺序和折半查找 D.随机 40.将 5 个不同的数据进行排序,至多需要比较( ) 。次。 A. 8 B. 9 C. 10 D. 25 41. 排序方法中,从未排序序列中依次取出元素与已排序序列(初始时为空)中的元 素进行比较,将其放入已排序序列的正确位置上的方法,称为( ) 。 A. 希尔排序 B. 冒泡排序 C. 插入排序 D. 选择排序 42.从未排序序列中挑选元素,并将其依次插入已排序序列(初始时为空)的一端的方 法称为( ) 。 A. 希尔排序 B. 归并排序 C. 插入排序 D. 选择排序 43.对n个不同的排序码进行冒泡排序,在下列哪种情况下比较的次数最多。 ( ) 。 A. 从小到大排列好的 B. 从大到小排列好的 C. 元素无序 D. 元素基本有序 44.对n个不同的排序码进行冒泡排序,在元素无序的情况下比较的次数为( ) 。

A. n+1 B. n C. n-1 D. n(n-1)/2 45.快速排序在下列哪种情况下最易发挥其长处。 ( ) 。 A. 被排序的数据中含有多个相同排序码 B. 被排序的数据已基本有序 C. 被排序的数据完全无序 D. 被排序的数据中的最大值和最小值相差 悬殊 46. 对有 n 个记录的表作快速排序,在最坏情况下,算法的时间复杂度是( ) 。 2 3 A.O(n) B.O(n ) C.O(nlog2n) D.O(n ) 47.若一组记录的排序码为(46, 79, 56, 38, 40, 84) ,则利用快速排序的方法,以第一个 记录为基准得到的一次划分结果为( ) 。 A. 38, 40, 46, 56, 79, 84 B. 40, 38, 46 , 79, 56, 84 C. 40, 38,46, 56, 79, 84 D. 40, 38, 46, 84, 56, 79 48.下列关键字序列中, ( ) 。是堆。 A. 16, 72, 31, 23, 94, 53 B. 94, 23, 31, 72, 16, 53 C. 16, 53, 23, 94,31, 72 D. 16, 23, 53, 31, 94, 72 49.堆是一种( ) 。排序。 A. 插入 B.选择 C. 交换 D. 归并 50.堆的形状是一棵 C A. 二叉排序树 B.满二叉树 C. 完全二叉树 D. 平衡二叉树 51.若一组记录的排序码为(46, 79, 56, 38, 40, 84) ,则利用堆排序的方法建立的初始堆 为( ) 。 A. 79, 46, 56, 38, 40, 84 B. 84, 79, 56, 38, 40, 46 C. 84, 79, 56, 46, 40, 38 D. 84, 56, 79, 40, 46, 38 52. 下述几种排序方法中,要求内存最大的是( ) 。 A. 插入排序 B.快速排序 C. 归并排序 D. 选择排序

三、应用题
1、已知二叉树的前序和中序序列分别为 ABDFJGKCE 和 BFJDGKACE,试构造该二叉 树,并写出它的后序序列。

2、试写出如图所示的二叉树分别按前序、中序、后序遍历时得到的结点序列。

3.已知二叉树的中序和后序序列分别为 CBEDAFIGH 和 CEDBIFHGA,试构造该二叉树,并 写出该树的前序序列。

4.对给定的一组权值 W={5,2,9,11,8,3,7},试构造相应的哈夫曼树,并计算 它的带权路径长度。

5.已知某字符串 S 中共有 8 种字符,各种字符分别出现 2 次、1 次、4 次、5 次、7 次、 3 次、4 次和 9 次,对该字符串用[0,1]进行前缀编码,问该字符串的编码至少有多少位。

6、已知某字符串中共有8种字符abcdefgh,每种字符出现的次数分别为(9,2,5,1, 8,3,7,15) ,试为这8个字符设计哈夫曼编码。请先画出构造的哈夫曼树(要求树中左孩子 结点的权值小于右孩子结点的权值),然后分别写出每个字符对应的编码。

7.把如图所示的树转化成二叉树。

8.画出和下列二叉树相应的森林。

9.在一棵空的二叉排序树中依次插入关键字序列为 12,7,17,11,16,2,13,9,21,4,请画出所 得到的二叉排序树,并求查找成功时的平均查找长度。

10.假定对有序表: (3,4,5,7,24,30,42,54,63,72,87,95)进行折半查找, 试回答下列问题: (1) 画出描述折半查找过程的判定树; (2) 若查找元素 54,需依次与哪些元素比较? (3) 若查找元素 90,需依次与哪些元素比较? (4) 假定每个元素的查找概率相等,求查找成功时的平均查找长度。 11.设哈希(Hash)表的地址范围为 0~17,哈希函数为:H(K)=K % 16。 K 为关键字,用线性探测法再散列法处理冲突,输入关键字序列: (10,24,32,17,31,30,46,47,40,63,49) 造出 Hash 表,试回答下列问题: (1) 画出哈希表的示意图; (2) 若查找关键字 63,需要依次与哪些关键字进行比较? (3) 若查找关键字 60,需要依次与哪些关键字比较? (4) 假定每个关键字的查找概率相等,求查找成功时的平均查找长度。

12、选取散列函数H(key)=(key)%13,用线性探测法处理冲突,对关键码序列39, 08,46,22,41,53,23,31,66,25构造一个散列地址空间为0~12,表长为13的散列表, 并求查找成功时的平均查找长度。

13. 选取散列函数 H(key)=(key)%11,用线性探测法处理冲突,对关键码序列 22, 41,53,08,46,30,01,31,66,构造一个散列地址空间为 0~10,表长为 11 的散列表, 并求查找成功时的平均查找长度。 14.设哈希函数 H(K)=k%11,给定键值序列为 69,72,78,10,26,38,43,55,哈希 表长度为 11,采用拉链法处理冲突,试构造散列表,并计算查找成功时的平均查找长度。

15. 应用希尔排序算法从小到大进行排序,键值序列为 908,17,512, 503,170,897,275,653,426,增量序列为{5,3,1},试写出每趟排序的结果。

16. 应用希尔排序算法,对键值序列 45,93,34,49,57,65,37,51,13, 7 从小 到大进行排序,试写出每趟排序的结果。 (增量序列为:5 3 1)

17、应用希尔排序算法从小到大进行排序,键值序列为56,31,75,12,93,86,74,69, 6, 38,增量序列为{5,3,1},试写出每趟排序的结果。 18.应用希尔排序算法,对键值序列 9,57,95,37,51,13, 7,85,93,34 从小到 大进行排序,试写出每趟排序的结果。 (增量序列为:5 3 1) 19、 已知含有V1,V2,V3,V4,V5,V6,V7等七个顶点的图的邻接矩阵, 求从顶点V1出发进行深度 优先遍历和广度优先遍历的结点序列。

?0 ?1 ? ?1 ? ?1 ?1 ? ?0 ?1 ?

1 1 1 1 0 1? 0 0 1 0 0 1? ? 0 0 0 1 0 0? ? 1 0 0 1 1 0? 0 1 1 0 1 0? ? 0 0 1 1 0 1? 1 0 0 0 1 0? ?

20、试用Prim算法从顶点a出发构造下图的最小生成树,要求分步给出构造过程。

四、程序理解题
1. 写出下列程序段的输出结果,简述算法的功能 void main() {

SeqStack <int>S; int d; CirQueue <int> Q; Q.EnQueue(1); Q.EnQueue(2); Q.EnQueue(3); Q.EnQueue(4); Q.EnQueue(5); while(!Q.Empty()) { d=Q.DeQueue(); S.Push(d); } while(!S.Empty()) { d=S.Pop(); Q.EnQueue(d); cout<<d; } }

2.写出下列程序段的输出结果 void main() { CirQueue <char>Q; char x='e', y='c'; Q.EnQueue ('h'); Q.EnQueue ('r'); Q.EnQueue (y); x=Q.DeQueue (); Q.EnQueue (x); x=Q.DeQueue (); Q.EnQueue ('a'); while(!Q.Empty()) { y=Q.DeQueue (); cout<<y; } cout<<x<<endl; }

3、在操作序列 push(1)、push(2)、pop、push(5)、push(7)、pop、push(6)之后,栈 顶元素、栈底元素、栈中元素分别是什么?(push(k)表示整数 k 入栈,pop 表示栈顶元素 出栈。), 4、在操作序列 EnQueue(1)、 EnQueue(3)、 DeQueue、EnQueue(5)、EnQueue(7)、 DeQueue、EnQueue(9)之后,队头元素和队尾元素分别是什么?(EnQueue(k)表示整数 k 入队,DeQueue 表示队头元素出队)。

5、算法理解题 (每空2分,共4分) [程序说明] 下面的函数实现把十进制整数a转换为d(2~9)进制整数并输出,试补全程序。 提示:使用栈实现 [程序] void Dec_to_Ocx(int a,int d) { int div,x; SeqStack <int>s; while(a!=0) { div=a%d; ; a=a/d; } while( ) { x=s.Pop(); cout<<x; } cout<<endl; }

五、算法设计题
1、试编写一算法,求不带头结点单链表的长度。 template <class T> struct node //单链表的结点结构 { T data; struct node *next; }; template <class T> int LinkList::length(node *first) //first 为不带头结点单链表的头指针 {

} 2. 试编写一算法,求带头结点单链表的长度。 struct node //单链表的结点结构 { int data; struct node *next; } int length(struct node *first) //first 为带头结点单链表的头指针 {

} 3、设一棵二叉树T以二叉链表为存储结构,试编写一个函数,求二叉树中结点个数。 template <class T> struct binode {T data; binode<T> *lchild,*rchild; }; 4.设计算法求二叉树的叶子结点个数。 struct BiNode //二叉树的结点结构 { int data; BiNode *lchild, *rchild; }; int count(BiNode * root) /* root 为二叉树的根结点*/ {

} 5.设计算法求二叉树的深度。 struct BiNode //二叉树的结点结构 { int data; BiNode *lchild, *rchild; }; int depth(BiNode * root) /* root 为二叉树的根结点*/ {

}


相关文章:
数据结构复习题tjuci0604
数据结构复习题tjuci0604_其它课程_高中教育_教育专区。数据结构复习题一、填空题数据结构是一门研究非数值计算的程序设计问题中计算机的 以及它们之间 的 关系 和运...
更多相关标签: