C．三元组和十字链表 D．散列和十字链表
8、任何一棵二叉树的叶子结点在前序、中序和后序遍历序列中的相对次序（ ）。
阅卷 ： | | | | | | |
2014 ~ 2015-1数据结构试卷(B)
二 三 四 五 总分 教师 A．不发生改变 B．发生改变 C．不能确定 D．以上都不对
9、若一棵二叉树具有15个度为0的结点，5个度为1的结点，则度为2的结点的个数是 （ ）。
题号 得分 一 A．14 B．16 C．20 D．不能确定
10、设森林F对应的二叉树为B，它有m个结点，B的根为p，F的第一颗树结点个数为n，二叉树B中右子树结点的个数是（ ）。
一、
阅卷教师 得 分 选择题（本大题共 15小题，每题2分，共30分。）
名姓| 装 | | | | ：号|学订 | | | | ：|级班| 线 | | | ：| 号序| 卷试| | |
1、以下说法正确的是（ ）。 A．数据项是数据的基本单位 B．数据元素是数据的最小单位 C．数据结构是带结构的数据项的集合
D．一些表面上很不相同的数据可以有相同的逻辑结构 2、单链表中，增加一个头结点的目的是为了（ ）。
A．使单链表至少有一个结点 B．标识表结点中首结点的位置 C．方面运算的实现 D．说明单链表是线性表的链式存储
3、在n个结点的线性表的数组实现中，算法的时间复杂度是O（1）的操作是（ ）。A．访问第i（1<=i<=n）个结点和求第i个结点的直接前驱（1 4、设计一个判别表达式中左、右括号是否配对出现的算法，采用（ ）数据结构最佳。A．线性表的顺序存储结构 B．队列 C．线性表的链式存储结构 D．栈 5、对于循环队列（ ）。 A．无法判断队列是否为空 B．无法判断队列是否为满 C．队列不可能满 D．以上说法都不对 6、数组A中，每个元素的长度为3个字节，行下标i从1到8，列下标j从1到10，从首地址SA开始连续存放的存储器内，该数组按行存放，元素A[5][8]的起始地址为（ ）。A．SA＋141 B． SA＋180 C．SA＋222 D．SA＋225 7、稀疏矩阵一般的压缩存储方式有两种，即（ ）。 A．二维数组和三维数组 B．三元组和散列 第1页(共3页) A．m－n B．m－n－1 C．n＋1 D．不能确定 11、在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的（ ）倍。 A．1/2 B．1 C．2 D．4 a12、已知一个图，如图所示，若从顶点a出发按广度搜索法进行遍历，则可能得到的一种顶点序列为（ ）。 becA．a，b，c，e，d，f B．a，b，c，e，f，d dfC．a，e，b，c，f，d， D．a，c，f，d，e，b 图113、顺序查找法适合于存储结构为（ ）的线性表。 A．散列存储 B．顺序存储或链式存储 C．压缩存储 D．索引存储 14、哈希表中的冲突指的是（ ）。 A．两个元素具有相同的序号 B．两个元素的键值不同，而其他属性相同 C．数据元素过多 D．不同键值的元素对应于相同的存储地址 15、在所有的排序方法中，关键字比较的次数与记录的初始排列次序无关的是（ ）。 A．希尔排序 B．冒泡排序 C．直接插入排序 D．直接选择排序 选择题请将答案填写在下面的表格中。 1-5 6-10 11-15 二、 阅卷教师 得 分 | | | | | | 装 填空题（本大题共8小题，每空1分，共10分。） 1、数据结构的基本存储方法是 、 、索引和散列存储 。 2、在n个结点的单链表中要删除指针p指向的结点，需找到它的前驱结点，其时间复杂度为 。 3、带头结点的循环链表，其头指针为L，则循环链表中只有一个结点的条件是 。 4、栈是限定仅在 进行插入或删除操作的线性表，其运算遵循后进先出的原则。 5、若某二叉树有20个叶子结点，有30个结点仅有一个孩子，则该二叉树的总结点个数为 。 2、假设通信电文使用的字符集为{a，b，c，d，e，f，g，h}，各字符在电文中出现的频度分别为：13，10，3，11，7，26，2，28，试为这8个字符设计哈夫曼编码。要求： ：名姓| | | | | 订 ：|号学| | | | | 线 ：级|班 | | | | | ：号| 序卷| 试|6、假定一棵二叉树的结点数为18，则它的最小深度为 ，最大深度为 。 7、具有10个顶点的有向图，边的总数最多为__ _。 8、在数据的存放无规律而言的线性表中进行查找的最佳方法是 。 三、 阅卷教师得 分 判断题（本大题共10小题，每题1分，共10分。） （ ）1、顺序存储方式的优点是存储密度大，且插入、删除运算效率高。 （ ）2、链表的删除算法很简单，因为当删除链中某个结点后，计算机会自动地将后续的各个单元向前移动。 （ ）3、线性表的逻辑顺序与存储顺序总是一致的。 （ ）4、栈和队列的存储方式既可是顺序方式，也可是链接方式。 （ ）5、用二叉链表法存储包含n个结点的二叉树，结点的2n个指针区域中有n+1个为空指针。 （ ）6、对于一棵非空二叉树，它的根结点作为第一层，则它的第i层上最多能有2i—1个结点。 （ ）7、邻接表可以表示有向图，也可以表示无向图。 （ ）8、强连通图的各顶点间均可达。 （ ）9、对线性表进行折半查找时，要求线性表必须以链式方式存储，且结点按关键字有序排列。 （ ）10、拓扑排序是按AOE网中每个结点事件的最早发生时间对结点进行排序。 四、 阅卷教师 得 分 应用题（本大题共5小题，每题8分，共40分。） 1、已知二叉树的中序序列和后序序列分别ADCBHFEG和ABCDEFGH。 （1）画出该二叉树；(3分) （2）给出该二叉树的先序遍历序列；(2分) （3）画出与（1）求得的二叉树对应的树或森林。(3分) 第2页(共3页) (1)画出你所构造的哈夫曼树(要求树中左孩子结点的权值不大于右孩子结点的权值) (4分)；(2)按左分支为0和右分支为1的规则，分别写出与每个字符对应的编码(2分)； (3)问该字符串的编码至少有多少位 (2分)。 3、右图表示一个地区的交通网，顶点表示城市，边表示连结城市间的公路，边上的权表示修建公路花费的代价。怎样选择能够沟通每个城市且总造价最省的n-1条公路（6分），并求出公路花费总值M(2分)。要求：使用Kruskal算法，并画出每一个步骤。 ： | | | | | | 装 | （1）简单选择排序(2分) （2）快速排序(要求写出排序过程)(6分) 名姓| | | | 订 | ：号|学| | | | 线 ：|级班| | | | | ：| 号序| 卷试| 4、设有关键字序列，表示为一个线性表｛32，75，29，63，48，94，25，46，18，70｝，散列地址为HT[0]~HT[12]，哈希函数H（K）=K，试用线性探测再散列解决冲突，实现散列存储，画出散列表(6分)，要求写出求解步骤，并求出查找成功的平均查找长度（2分）。 5、给出一组关键字K={24，38，27，19，7，31，23，14，11}，写出用下列方法进行升序排序，第一趟结束时关键字的排列状态。 第3页(共3页) 阅卷教师 五、 得 分 算法设计题（本大题共1小题，共10分。） 假设某个单向链表中，各元素均为整型。已知头指针first指向头结点，p为指向链表中某个结点的指针，试编写算法完成如下操作： (1) 删除链表中指针p所指结点的后继结点， 用变量x返回待删除结点的值，使用函数void ListDelete(LNode *p) 完成（4分）。 (2) 在链表中指针p所指结点的前面插入一个值为x的结点，使用函数void ListInsert(LNode *p, DataType x)完成(6分)。 各结点的结构体类型如下： typedef int DataType; // DataType为线性表的数据类型 typedef struct LNode { DataType data; // 数据域 struct LNode *next; // 指针域 } LNode;