《数据结构》试题

1、线订_-装- :名姓 ：号学 ：号座 ：级班 ：级年 ：次层 :业专 人做信诚试考信自：示提别特 数据结构试题（样卷） 注意：请将选择题和判断题的答案写在答题纸上 一、选择题（共20题，每题2分，共40分） 1. 线性表L=（a1,a2,.,ai,.,an），下列说法正确的是 （） A 每个元素都有一个直接前驱和直接后继 B 线性表中至少要有一个元素 C. 表中诸元素的排列顺序必须是由小到大或由大到小的 D. 除第一个元素和最后一个元素外其余每个元素都有一个数且仅有一个直接前 驱和直接后继 2. 线性表采用链式存储时，结点的存储地址（） A .必须是不连续的B .连续与否均可 C.必须是连续的

2、D.和头结点的存储地址相连续 3. 在一个单链表L中，若要在指针q所指结点的后面插入一个由指针P所指向的 结点，则执行（）。 A . p_next = q_next; q_next = p; B. p_next = q_next; q = p; C. q_next = p_next; p_next = q; D . q_next = p_next; p_next = q 4. 假设p是指向线性表中第i个数据元素结点的指针，则p-next是指向第i+1个 数据元素结点的指针，若p-data=ai,贝y p-next-data=ai+1，那么 p-next-next 指 向的是第（）个结点 A .

3、 iB. i+1C. i+2D. i+3 5. 在双向链表中，一个结点包含（）个指针。 A. 1B. 2C. 3D. 4 6. 为了最快地对线性结构的数据进行某数据元素的读取操作，则其数据存储结构 宜采用（）方式。 A .顺序存储B .链式存储 C.索引存储D .散列存储 7. 有关栈的描述，正确的是（） A .栈是一种先进先出的特殊的线性表 B .只能从栈顶执行插入、删除操作 C.只能从栈顶执行插入、栈底执行删除 D .栈顶和栈底均可执行插入、删除操作 8. 一个栈的入栈序列是a,b,c,d,e，则栈的不可能的输出序列是（） A. e d c b aB . d e c b a C . d c

4、 e a b D . a b c d e 9. 对含有（）个结点的非空二叉树，采用任何一种遍历方式，其结点访问序列 均相同 A . 0B . 1C . 2D .不存在这样的二叉树 10. 若二叉树的前序序列和后序序列分别是1,2,3,4和4,3,2,1，则二叉树的中序序 列不是（） A、1,2,3,4 B、2,3,4,1 C、 3,2,4,1 D、4,3,2,1 11.已知完全二叉树有 2012个结点, 则叶子结点数是（ ）个 A. 1006 B. 1007 C . 998 D . 999 12. 一棵有16个结点的完全二叉树, 的双亲结点及右孩子结点的编号分别为 A . 2，14 B. 2，

5、15 对它按层编号, C. 3， 14 则对编号为7的结点X，它 D. 3， 15 13.对n（n大于等于2）个权值均不相同的字符构成哈夫曼树，关于该树的叙述中, 线订_-装- :名姓 ：号学 ：号座 ：级班 ：级年 ：次层 :业专 人做信诚试考信自：示提别特 错误的是（ ） A、该树一定是一棵完全二叉树 B、 树中一定没有度为1的结点 C、树中两个权值最小的结点一定是兄弟结点 D、树中任一非叶结点的权值一定不小于下一任一结点的权值 14.图的邻接矩阵表示法适用于表示（） A .稠密图B.有向图 C.无向图D .稀疏图 15.具有n个顶点的无向图，若要连通全部顶点，至少需要（）条边 A . （

6、n-1）B . nC. n （n-1）D. n （n-1）/2 16. n个顶点的有向完全图中含有向边的数目为 （） A . n-1B . nC. n（n-1）/2 17.无向图的邻接矩阵是一个（） A .对称矩阵B .零矩阵 C.上三角矩阵 D.对角矩阵 18.能进行折半查找的线性表，必须以（ A.链式方式存储，且元素按关键字有序 D. n(n-1) B .顺序方式存储，且元素按关键字有序 C .顺序方式存储，且元素按关键字分块有序 D .链式方式存储，且元素按关键字分块有序 19.为提高散列表的查找效率，可采取的正确措施是（） 增大装填因子设计冲突少的散列函数处理冲突时避免产生聚焦现象 A

7、、仅B、仅C、仅D、仅 20.对于键值序列(12, 13, 11, 18, 60, 15, 7, 18, 25, 100)用筛选法建堆, 必须从键值为（）结点开始 A . 12B. 60C . 15D . 100 二、判断题（共10题，共10分） 1. 在顺序表中取出第i个元素所花费的时间与i成正比。 2. 栈的操作特点是先进先出。 3. 设与一棵树T所对应的二叉树为 BT,则与T中的叶子结点所对应的 BT中的 结点也一定是叶子结点。 4. 二叉树的前序遍历序列中，任意一个结点均处在其孩子结点的前面。 5. 完全二叉树中，若一个结点没有左孩子，则它必是树叶。 6. 由树转换过来的一棵二叉树，其

8、根一定没有右孩子。 7. 无向图的邻接矩阵是对称的，有向图的邻接矩阵一定是不对称的。 8. 在AOE网中一定只有一条关键路径。 9. 向二叉排序树插入一个结点所需比较的次数可能大于此二叉排序树的高度。 10. 负载因子（装填因子）是散列表的一个重要参数，它反映散列表的装满程度。 人做信诚试考信自：示提别特 0 线 B B 6 d H a 6 订 0 I H 9 ! 装 数据结构试题（样卷）答题纸 题号 -一一 -二二 -三 四 总分 复核人 得分 2、（ 7分）已知二叉树的先序遍历序列是：ABCDEF，中序遍历序列是：CBADFE 求：（1）二叉树 （2）后序遍历序列 （3）对应的森林 得分

9、阅卷人 得分 阅卷人一选择题（共20题，每题2分，共40分） 题号 1 2 3 4 5 6 7 8 9 10 答案 题号 11 12 13 14 15 16 17 18 19 20 答案 3、（ 6 分） 得分 阅卷人 、判断题（共10题，共10分） 题号 1 2 3 4 5 6 7 8 9 10 答案 得分 阅卷人 三、解答题（共6题，共40 分） 1、（ 6分）已知三个结点，可以构造成多少棵不同的树形态？可以构成多少棵不同 的二叉树形态？分别画出它们。 求：（1 ）画出邻接表的存储结构（下标的标号即为该结点在图中的序号） （2）从开工到交工所有拓扑序列的可能 4、（ 6分）已知下图 人做信

10、诚试考信自：示提别特 0 d H a 6 订 0 I H 9 ! 装 求：（1）以V1为出发点，画出广度优先生成树（顶点下 标序号从小到大），并写出相应的序列 （2）写出使用普里姆算法生成最小生成树依次得到 的边的集合（只写依次得到边集，不画图） 得分 阅卷人 四、算法设计题（共2题，共10分） 5、（ 9 分）已知五个工作日：Monday， Tuesday， Wednesday, Thursday， Friday。 （1）左边是以五个工作日构造成的二叉排序树树 型，请将五个工作日分别填到相应的结点里。 （2 ）对所得二叉排序树进行 遍历, 可得从小到大的有序表。从小到大的有序表是： （3）对

11、第（2）题所得的有序表进行折半查找，画出其判定树，列式计算等概率 时查找成功的平均查找长度。 1. （ 4分）如下为二分查找的递归算法，试将其填写完整。 Int Binsch（ElemType A,int low,int high,KeyType K） if int mid=（low+high）/2; if （） return mid; / 查找成功，返回元素的下标 else if （KAmid.key） return Bin sch（A,low,mid-1,K）;/在左子表上继续查找 else return； /在右子表上继续查找 else；查找失败，返回-1 2. （6分）已知一个带有表头结点的单链表，假设该链表只给出了头指针。在不 改变链表的前提下，请设计一个尽可能高效的算法，查找链表中倒数第k个位置 上的结点（k为正整数）。若查找成功