1、“数据结构”期末考试试题 一、单选题 (每小题 2分，共 12 分 ) 1在一个单链表 HL 中，若要向表头插入一个由指针 p指向的结点，则执行 ( )。 A HL ps p 一 next HL B p 一 next HL； HL p3 C p 一 next Hl； p HL； D p 一 next HL 一 next;HL 一 next p； 2 n个顶点的强连通图中至少含有 ( )。 A.n l 条有向边 B.n 条有向边 C.n(n 1) 2 条有向 边 D.n(n 一 1)条有向边 3.从一棵二叉搜索树中查找一个元素时，其时间复杂度大致为 ( )。 A.O(1) B.O(n) C.O(
2、1Ogzn) D.O(n2) 4由权值分别为 3， 8， 6， 2， 5的叶子结点生成一棵哈夫曼树，它的带权路径长度为 ( )。 A 24 B 48 C 72 D 53 5当一个作为实际传递的对象占用的存储空间较大并可能需要修改时，应最好把它说明为( )参数，以节省参数值的传输时间和存储参数的空间。 A.整形 B.引用型 C.指针型 D.常值引用型 6向一个长度为 n 的顺序表中插人一个新元素的平均时间复杂度为 ( )。 A O(n) B O(1) C O(n2) D O(10g2n) 二、填空题 (每空 1 分，共 28分 ) 1数据的存储结构被分为 、 、 和 四种。 2在广义表的存储结构
3、中，单元素结点与表元素结点有一个域对应不同，各自分别为 域和 域。 3 中缀表达式 3 十 x*(2.4 5 6)所对应的后缀表达式为 。 4在一棵高度为 h的 3叉树中，最多含有 结点。 5假定一棵二叉树的结点数为 18，则它的最小深度为 ，最大深度为 6在一棵二叉搜索树中，每个分支结点的左子树上所有结点的值一定 该结点的值，右子树上所有结点的值一定 该结点的值。 7当向一个小根堆插入一个具有最小值的元素时，该元素需要逐层 调整，直到被调整到 位置为止。 8表示图的三种存储结构为 、 和 。 9对用邻接矩阵表示的具有 n 个顶点和 e 条边的图进行任一种遍历时，其时间复杂度为 ，对用邻接 表
4、表示的图进行任一种遍历时，其时间复杂度为 。 10从有序表 (12， 18， 30， 43， 56， 78， 82， 95)中依次二分查找 43 和 56元素时，其查找长度分别为 和 11假定对长度 n 144 的线性表进行索引顺序查找，并假定每个子表的长度均为 ，则进行索引顺序查找的平均查找长度为 ，时间复杂度为 12一棵 B 树中的所有叶子结点均处在 上。 13每次从无序表中顺序取出一个元素，把这插入到有序表中的适当位置，此种排序方法叫做 排序；每次从无序表中挑选出一个 最小或最大元素，把它交换到有序表的一端，此种排序方法叫做 排序。 14快速排序在乎均情况下的时间复杂度为 ，最坏情况下的
5、时间复杂度为 。 三、运算题 (每小题 6 分，共 24 分 ) 1假定一棵二叉树广义表表示为 a(b(c， d)， c(， 8)，分别写出对它进行先序、中序、后序和后序遍历的结果。 先序： 中序； 后序： 2已知一个带权图的顶点集 V 和边集 G分别为： V 0， 1， 2， 3， 4， 5； E=(0， 1)8， (0， 2)5， (0， 3)2， (1， 5)6， (2， 3)25， (2， 4)13， (3， 5)9， (4， 5)10， 则求出该图的最小生成树的权。 最小生成树的权； 3假定一组记录的排序码为 (46， 79， 56， 38， 40， 84， 50， 42)，则利用堆
6、排序方法建立的初始堆为 。 4有 7 个带权结点，其权值分别为 3， 7， 8， 2， 6， 10， 14，试以它们为叶子结点生成一棵哈夫曼树，求出该树的带权路径长度、高度、双分支结点数。 带权路径长度： 高度： 双分支结点数： 。 四、阅读算法 ，回答问题 (每小题 8 分，共 16 分 ) 1 VOldAC(List25)； InsertFront(L， 50)； IntaL4 5， 8， 12， 15， 36; for(inti 0; idata X)return 1; 根结点的层号为 1 向子树中查找 x结点 else int cl NodeLevel(BT 一 left， X)； i
7、f(cl 1)return cl+1; int c2 ； if ； 若树中不存在 X结点则返回 o else return 0； 六、编写算法 (8 分 ) 按所给函数声明编写一个算法，从表头指针为 HL 的单链表中查找出具有最大值的结点，该最大值由函数返回，若单链表为空则中止运行。 EIemType MaxValue(LNOde*HL); “数据结构”期末考试试题答案 一、单选题 (每小题 2 分，共 12 分 ) 评分标准；选对者得 2 分，否则不得分。 1 B 2 B 3 C 4 D 5 B 6 A 二、填空题 (每空 1分 ，共 28 分 ) 1顺序结构 链接结构 索引结构 散列结构
8、(次序无先后 ) 2值 (或 data) 子表指针 (或 sublist) 3 3 x 2 4 5 6 一 *十 4 (3h一 1) 2 5 5 18 6小于 大于 (或大于等于 ) 7向上 堆顶 8邻接矩阵 邻接表 边集数组 (次序无先后 ) 9 O(n2) O(e) 10 1 3 11 13 O( ) 12同一层 13插人 选择 14 O(nlog2n) O(n2) 三、运算题 (每小题 6 分，共 24 分 ) 1先序： a， b， c， d， e， f， e 2分 中序： c， b， d， a， f， 8， e 2分 后序： c， d， b， e， f， e， a 2分 2最小生成树的
9、权： 31 6分 3 (84， 79， 56， 42， 40， 46， 50， 38) 6分 4带权路径长度： 131 3 分 高度： 5 2 分 双分支结点数： 6 1分 四、阅读算法，回答问题 (每小题 8 分，共 16 分 ) 评分标准：每小题正确得 8分，出现一处错误扣 4分，两处及以上错误不得分。 1 (36， 12， 8， 50， 25， 5， 15) 2 5 15 8 6 20 28 五、算法填空，在画有横线的地方填写合适的内容 (每小题 6 分，共 12分 ) 1 feturn mid 2 分 returnBinsch(A， low， mid 一 1， K) 2分 return
10、Bmsch(A， mid+1， high， K) 2 分 2 NodeLevel(BT 一 right， X) 3分 (c2=1)returnc2 十 1 3分 六、编写算法 (8 分 ) 评分标准：请参考语句后的注释，或根据情况酌情给分。 ElemType MaxValue(LNodeO* HL。 ) if (HL =NUlL) 2分 cerrdata； 3分 LNOde*p=HI 一 next； 4 分 while(P!： NULL) 7分 if(maxdata)max p 一 data； p p一 next； returnmax； 8分 数据结构复习资料 一、填空题 1. 数据结构是一门
11、研究非数值计算的程序设计问题中计算机 的 操作对象 以及它们之间的 关系 和运算等的学科。 2. 数据结构被形式地定义为（ D, R），其中 D 是 数据元素 的有限集合， R 是 D 上的 关系 有限集合。 3. 数据结构包括数据的 逻辑结构 、数据的 存储结构 和数据的 运算 这三个方面的内容。 4. 数据结构按逻辑结构可分为两大类，它们分别是 线性结构 和 非线性结构 。 5. 线性结构中元素之间存在 一对一 关系，树形结构中元素之间存在 一对多 关系，图形结构中元素之间存在 多对多 关系。 6 在线性结构中，第一个结点 没有 前驱结点，其余每个结点有且只有 1个前驱结点；最后一个结点
12、没有 后续结点，其余每个结点有且只有 1 个后续结点。 7. 在树形结构中，树根结点没有 前驱 结点，其余每个结点有且只有 1 个前驱结点；叶子结点没有 后续 结点，其余每个结点的后续结点数可以 任意多个 。 8. 在图形结构中，每个结点的前驱结点数和后续结点数可以 任意多个 。 9数据的存储结构可用四种基本的存储方法表示，它们分别是 顺序 、 链式 、 索引 和 散列 。 10. 数据的运算最常用的有 5种，它们分别是 插入 、 删除、修改、 查找 、排序 。 11. 一个算法的效率可分为 时间 效率和 空间 效率。 12. 在顺序表中插入或删除一个元素，需要平均移动 表中一半 元素，具体移
13、动的元素个数与 表长和该元素在表中的位置 有关。 13. 线性表中结点的集合是 有限 的，结点间的关系是 一对一 的。 14. 向一个长度为 n 的向量的第 i 个元素 (1 i n+1)之前插入一个元素时，需向后移动 n-i+1 个元素。 15. 向一个长度为 n的向 量中删除第 i 个元素 (1 i n)时，需向前移动 n-i 个元素。 16. 在顺序表中访问任意一结点的时间复杂度均为 O(1) ，因此，顺序表也称为 随机存取 的数据结构。 17. 顺序表中逻辑上相邻的元素的物理位置 必定 相邻。单链表中逻辑上相邻的元素的物理位置 不一定 相邻。 18在单链表中，除了首元结点外，任一结点的
14、存储位置由 其直接前驱结点的链域的值 指示。 19 在 n个结点的单链表中要删除已知结点 *p，需找到它的 前驱结点的地址 ，其时间复杂度为 O（ n） 。 20. 向量、栈和队列都是 线性 结构，可以在向量的 任何 位置插入和删除元素；对于栈只能在 栈顶 插入和删除元素；对于队列只能在 队尾 插入和 队首 删除元素。 21. 栈是一种特殊的线性表，允许插入和删除运算的一端称为 栈顶 。不允许插入和删除运算的一端称为 栈底 。 22. 队列 是被限定为只能在表的一端进行插入运算，在表的另一端进行删除运算的线性表。 23. 不包含任何字符 （长度为 0） 的串 称为空串； 由一个或多个空格 （仅
15、由空格符） 组成的串 称为空白串。 24. 子串的定位运算称为串的模式匹配； 被匹配的主串 称为目标串， 子串 称为模式。 25. 假设有二维数组 A6 8，每个元素用相邻的 6个字节存储，存储器按字节编址。已知 A的起始存储位置（基地址）为 1000，则数组 A的体积（存储量）为 288 B ；末尾元素 A57的第一个字节地址为 1282 ；若按行存储时，元素 A14的第一个字节地址为 (8+4)6+1000=1072 ；若按列存储时，元素 A47的第一个字节地址为 (6 7 4) 6 1000） 1276 。 26 由个结点所构成的二叉树有 5 种形态。 27. 一棵深度为 6的满二叉树有
16、 n1+n2=0+ n2= n0-1=31 个分支结点和 26-1 =32 个叶子。 注：满二叉树没有度为 1的结点，所以分支结点数就是二度结点数。 28 一棵具有个结点的完全二叉树，它的深度为 9 。 （ 注：用 log2(n) +1= 8.xx +1=9 29设一棵完全二叉树有 700 个结点，则共有 350 个叶子结点。 答：最快方法：用叶子数 n/2 350 30 设一棵完全二叉树具有 1000 个结点，则此完全二叉树有 500 个叶子结点，有 499 个度为 2的结点，有 1 个结点只有非空左子树，有 0 个结点只有非空右子树。 答：最快方法：用叶子数 n/2 500 ， n2=n0
17、-1=499。 另外，最后一结点为 2i 属于左叶子，右叶子是空的，所以有 1 个非空左子树。完全二叉树的特点决定不可能有左空右不空的情况，所以非空右子树数 0. 31在数据的存放无规律而言的线性表中进行检索的最佳方法是 顺序查找（线性查找） 。 32. 线性有序表（ a1， a2， a3， a256)是从小到大排列的，对一个给定的值 k，用二分法检索表中与 k相等的元素，在查找不成功的情况下，最多需要检索 8 次。设有 100 个结点，用二分法查找时，最大比较次数是 7 。 33. 假设在有序线性表 a20上进行折半查找，则比较一次查找成功的结点数为 1；比较两次查找成功的结点数为 2 ；比
18、较四次查找成功的结点数为 8 ；平均查找长度为 3.7 。 解：显然，平均查找长度 O（ log2n） toptop=0 ST-toptop=m0 （ C ） 18. 在一个图中，所有顶点的度数之和等于图的边数的 倍。 A 1/2 B. 1 C. 2 D. 4 （ B ） 19. 在一个有向图中，所 有顶点的入度之和等于所有顶点的出度之和的 倍。 A 1/2 B. 1 C. 2 D. 4 （ B ） 20. 有 8 个结点的无向图最多有 条边。 A 14 B. 28 C. 56 D. 112 （ C ） 21. 有 8 个结点的有向完全图有 条边。 A 14 B. 28 C. 56 D. 11
19、2 （ B ） 22在表长为的链表中进行线性查找，它的平均查找长度为 . ; . （） ; . n ; . （） （ A ） 23折半查找有序表（ 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 （ C ） 24对 22 个记录的有序表作折半查找，当查找失败时，至少需要比较 次关键字。 A 3 B 4 C 5 D 6 （ A ） 25. 链表适用于 查找 A顺序 B二分法 C顺序，也能二
20、分法 D随机 数据结构与算法复习题 一、选择题。 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
21、各结点的值如何 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
22、( I =0; inext =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 16若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一个结点，则采用 D 存储方式最节省运算时间。 A单链表 B给出表头指针的单循环链表 C双链表 D带头结点的双循环链表 17需要分配较大空间，插入和删除不需要移动元素的线性表，其存储结构是 B 。 A单链表 B静态链表 C线性链表 D顺序存储结构 1
23、8非空的循环单链表 head 的尾结点（由 p所指向）满足 C 。 A p-next = NULL B p = NULL C p-next =head D p = head 19在循环双链表的 p 所指的结点之前插入 s 所指结点的操作是 D 。 A p-prior = s； s-next = p； p-prior-next = s； s-prior = p-prior B p-prior = s； p-prior-next = s； s-next = p； s-prior = p-prior C s-next = p； s-prior = p-prior； p-prior = s； p-prior-next = s D s-next = p； s-prior = p-prior； p-prior-next = s； p-prior = s 20如果最常用的操作是取第 i个结点及其前驱，则采用 D 存储方式最节省时间。 A单链表 B双链表 C单循环链表 D 顺序表 21在一个具有 n个结点的有序单链表中插入一个新结点并仍然保持有序的时间复杂度是 B 。 A O（ 1） B O（ n） C O（ n2） D O（ nlog2n） 22在一个长度为 n（ n1）的单链表上，设有头和尾两个指针，执行 B 操作与链表的长度有关。 A删除单链表中的第一个元素
