《《数据结构教学资料》期末复习卷(赵).doc.pdf》由会员分享，可在线阅读，更多相关《《数据结构教学资料》期末复习卷(赵).doc.pdf（10页珍藏版）》请在三一文库上搜索。
1、一. 是非题 （正确的打“ J” ，错误的打“ X” 。） 1.数据结构可用三元式表示（D, S, P）。其屮： D 是数据对象， S是 D 上的关系， P是对 D 的基本操作集。 2.线性表的链式存储结构具有可直接存取表中任一元素的优点。 3.队列是数据对象特定的线性表。 4.二叉树是一棵结点的度最大为二的树。 5.邻接表可以用以表示无向图，也可用以表示有向图。 6.可从任意有向图小得到关于所有顶点的拓扑次序。 7.一棵无向连通图的生成树是其极大的连通子图。 8.二叉排序树的查找长度至多为log2 n。 9.对于一棵 m 阶的 B 树，树中每个结点至多有m 个关键字。除根之外的所有非终端结点
2、至少 有m/2 -1 个关键字。 10. 对于目前所知的排序方法，快速排序具有最好的平均性能。 11?顺序存储方式的优点是存储密度大，且插入、删除运算效率高。 12. 二维数组是其数据元素为线性表的线性表。 13. 连通图 G 的生成树是一个包含G 的所有 n 个顶点和 n? l 条边的子图。 14. 折半查找不适用于有序链表的查找。 15. 完全二叉树必定是平衡二叉树。 16. 中序线索二叉树的优点是便于在中序下查找直接前驱结点和直接后继结点。 17. 队列是与线性表完全不同的一种数据结构。 18. 平均查找长度与记录的查找概率有关。 19. 广义表的表头和表尾都有可能是原子或广义表。 20
3、. 算法的时间复杂性越好，可读性就越差；反Z,算法的可读性越好，则时间复杂性就越差。 二. 选择题 1.若广义表LS 满足 Head (LS)=Tail (LS),则 LS%() 。 A.( ) B. ( ) C. ( ), ( ) D.(),(),() ）具有先进后出 （FTLO）特性。 ）转化为非递归程序。 a:线性表 b:栈c:队列 d:数组 3.在下列数据结构中 （）具有先进先出(FIFO)特性, a:线性表b:栈c:队列d:广义表 2.递归程序可借助于 （ 4.假设用于通讯的电文仅由6个字符组成，字母在电文中出现的频率分别为7, 19, 22, 6, 32, 14o若为这 6个字母设
4、计哈夫曼编码（设生成新的二叉树的规则是按给出的次序从左 32的字符编码是（）。 a: 00b: 01 c: 10 d: 11 e: Oilf: 110 g: 1110 h:llll 5.对二叉排序树按（）可得到有序序列。 a:层次遍历b:前序遍历c:中序遍历d:后序遍历 6.已知某树的先根遍历次序为abcdefg,后根遍历次序为 cdebgfao若将该树转换为二叉树，其后 序遍历次序为 （ ）o a: abcdefg b: cdebgfa c: cdegbfa d: edcgfba 7.对一棵完全二叉树进行层序编号。则编号为n的结点若存在右孩子，其编号是（）。 编号为 n的结点若存在双亲，其编
5、号是（）。 a: n/2 b: 2n c:2n-l d:2n+l e:n f: 2（n+l） 8.关键路径是指在只有一个源点和一个汇点的有向无环网中源点至汇点（）的路径。 a:弧的数目最多b:弧的数目最少c:权值之和最大d:权值之和最小 9.哈希表的查找效率取决于（）0 a:哈希函数b:处理冲突的方法。 c:哈希表的装填因子。 d:以上都是 10.从逻辑上可以把数据结构分成（）。 11.在计算递归函数时，如不用递归过程，应借助于（）这种数据结构。 12. 若己知某二叉树的中序和后序遍历序列分别BCAEFD 和 CBFEDA,则该二叉树的先序序列为 （）。 A. ABCDEF B. ABDCEF
6、 C. ABDCFE D. ACBDEE 13. 当待排序序列的关键字次序为倒序时，若需为之进行正序排序，下列方案中（）为佳。 A.起泡排序B.快速排序 C.直接插入排序D.简单选择排序 14. 若从二叉树的根结点到其它任一结点的路径上所经过的结点序列按其关键字递增有序, 则 该二叉树是（）。 A.二叉排序树B.赫夫曼树C.堆D.平衡二叉树 A.动态结构和静态结构B. 顺序组织和链接组织 C. 线性结构和非线性结构D. 基本类型和组合类型 A.线性表B.栈C.队列D.双向队列 15.下图所有可能的拓扑序列有（）种。 19?根据插入次序（80, 90, 100, 110, 图（）是最终变化的结果
7、。 若仍以该插入次序建立平衡二叉树O a: 85, 70, 图（ b: 75, 60, 72）建立二叉排序树 q 是最终变化的结果。 110 72 10 80 75 90 60 70 85 100 18.设森林 F中有三棵树，第一、第二和第三棵树的结点个数分别为ml、m2 和 m3,则与 森林 F 对应的二叉树根结点的右子树上的结点个数是 A. ml B. ml+m2 C. m3 D. m2+m3 D. 5 16.下列排序算法中，（ ）算法可能会出现 : 初始数据为正序时 , A.堆排序B.起泡排序 花费的时间反而最多。 D.快速排序 17.右图为一棵 3阶 B树。 在该树上插入元素15 后的
8、 B树是（）。 C?归并排序 72 20.设输入序列为 20, 45, 30, 89, 70, 3 在等概率情况下查找成功的平均查找长度为（）。 A. 0 B. 1 C. 2 D. 3 E. 4 F. 5 G. 6 II. 7 27.已知某有向图的邻接表存储结构如图所示。 0 E 2 A】 4 # 1 A 1 D0A 34 A 2 C? 4A 3 B k 1 2 ? 0 A 4 A 一 2 A 根据存储结构，依教材屮的算法其深度优先遍历次序为（ ）o 广度优先遍历次序为（）。 各强连通分量的顶点集为（）。 28.已知某无向图的邻接表如下所示； （）是英原图。 是按该邻接表遍历所得深度优先生成树
9、。 设一棵二叉树 BT 的存储结构如下： 12 34 6 7 8 lchiId 23 006000 data ABCDEFGH rchi1d 054 08 7 00 23. 其中 lchild, rchild 分别为结点的左、右孩子指针域，data为结点的数据域。则 d: ecadb. e: abc 及 ed f: ac 及 bed g: ab 及 ced h: be 及 aed B. 3 行（）次比较。 A. 1 B. 2 C. 3 D. 4 A. 2 C. 4 D. 5 a: abcde. b: edcba. c: ecdab. 29. 设有二维数组 Ax：,每一元素用相邻的4 个字节存储
10、，存储器按字节编址。已知 A 的起始地 址为 100。则按行存储时， 元素騙的存储地址是 () ；按列存储时， 元素 Aoo 的存储地址是 () 。 a. 220 b. 200 c. 140 d. 124 30.若顺序表中各结点的查找概率不等，则可用如下策略提高顺序查找的效率：若找到指定的 结点，将该结点与其后继(若存在 ) 结点交换位置，使得经常被查找的结点逐渐移至表尾。 以下为据此策略编写的算法，请选择适当的内容，完成此功能。 顺序表的存储结构为：typedef struct ElemType *elem; / 数据元素存储空间， 0 号单元作监视哨int length; / 表 长度 S
11、STable; int search_seq(SSTable ST, KeyType key) /在顺序表 ST中顺序查找关键字等于key 的数据元素。 / 若找到，则将该元素与其后继交换位置，并返回其在表中的位置，否则为0。 ST.elem0. key 二 key; i=ST? length; while (ST. elemi. key !=key) _ ; if( _ ) ST. elemi ST. elemi+l； E? a - b ll c d 0 I D? a - b f e return i; A. i0B. i=0C. iST.lengthD. i=ST. length E. i+F. iG. A 和 C同时满足H. B 和 D 同时满足 三. 算法设计题 1?单链表结点的类型定义如下： typedef struct LNode int data; struct LNode *next; LNode, *Linklist; 写一算法，Contrarydinklist Struct BiTNode *lchild, *rchild; BiTNode, * BiTree; 试编写销毁二叉树T 的算法 DestroyBiTree （ BiTree Struct LNode *next; LNode, *LinkList;