2011〜2012学年第1学期期末考试试卷（A卷）课程名称：数据结构 ____________ 任课教师姓名：______________卷面总分：100 分考试时长：100 分钟考试类别：闭卷院（系）：_________________ 专业：_______________________________ 年级：2010阅卷教师（签字）：________________________单项选择题（每题2分，共10题20 分）1. ________________________________________________ 以下那一个术语与数据的存储结构无关？________________________________________A. 栈 C .线索树B .哈希表 D .双向链表2. ________________________________________ 链表不具有的特点是。
A. 插入、删除不需要移动元素C•不必事先估计存储空间B. 可随机访问任一元素D.所需空间与线性表长度成正比3. ________________________________________________________ 算术表达式a+b* （c+d/e）转为后缀表达式后为______________________________ 。
A . ab+cde/* C. abcde/*++B. abcde/+*+ D. abcde*/++4. 二维数组A[10][20]采用列优先的存储方法，若每个元素占2个存储单元，设A[0][0]的地址为100,则元素A[7][6]的存储地址为____________________ 。
A. 232B. 234C. 390 D . 3925•若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是 ________ B。
A . 9B . 11C . 15D .不确定6•—棵二叉树中序序列为 FEABDC,后序序列为FBADCE ，则层序序列为 D <A . G 中有弧<Vi ，Vj>C . G 中没有弧<Vi,Vj>B. G 中有一条从Vi 到Vj 的路径 D . G 中有一条从Vj 到Vi 的路径8. _________________________________ 对于二叉排序树，下面的说法 C 是正确的。
A .二叉排序树是动态树表，查找不成功时插入新结点时，会引起树的重新分裂 和组合（不用移动元素的树）B .对二叉排序树进行层序遍历可得到有序序列（ 应该是中序遍历）C. 用逐点插入法构造二叉排序树时，若先后插入的关键字有序，二叉排序树的 深度最大D .在二叉排序树中进行查找，关键字的比较次数不超过结点数的 1/2 （取决于 二叉排序树的形状）9. 一组记录的关键字为｛47、75、55、30、42、90｝，则用快速排序方法并以第一个记录为支点得到的第一次划分结果是 A. 30,42,47,55,75,90 B. 42,30,47,75,55,90 10.下述文件中适合于磁带存储的是 ___________________ 。
A. 顺序文件 C.散列文件B. 索引文件D.多关键字文件顺序文件：原理是顺序表查找法C. 42,30,47,55,75,90D. 42,30,47,90,55,75索引文件：原理是线性索引查找（如最大关键码和次关键码）多关键字文件: 散列文件：原理是散列函数(哈希函数)判断(每题1分，共10题10 分)1 •顺序存储方式插入和删除时效率太低，因此它不如链式存储方式好。
----()(如果插入和删除次数较少时顺序存储方式为首选)2. ------------------------------------------------------------------------------------------------ KMP算法的特点是在模式匹配时指示主串的指针不会变小。
----------------------- ()(主串在匹配过程中是不会移动的，只有匹配的串在移动，所以其指针不会动)3. 若输入序列为1,2,3,4,5,6,则通过一个栈可以输出序列325,6,4,1. ---()4. 数组可看成线性结构的一种推广，因此与线性表一样，可以对它进行插入，删除等操作。
------------------------------------ ()数组不能进行插入删除等操作5. ---------------------------------------------------------------------------------------------- 若一个广义表的表头为空表，则此广义表亦为空表。
----------------------------- ()6. ------------------------------------------------------------------------------------------------ 完全二叉树中，若一个结点没有左孩子，则它必是树叶。
------------------------- ()完全二叉树的关键之一就是：元素又是有序排列的，顺序不可间断7. ------------------------------------------------------------------------------------------------ —个有向图的邻接表和逆邻接表中结点的个数可能不等。
------------------------- ()必须相等8. ------------------------------------------------------------------------------- AOE网一定是有向无环图。
-------------------------------------------------- ()AOE网的特征和定义9. 对一棵二叉排序树按先序方法遍历得出的结点序列是从小到大的序列。
---()应该是中序排列10. 倒排文件与多重表文件的次关键字索引结构是不同的。
---------- ()o三、填空题(每题2分，共10题20分)1.带头结点的双循环链表L中只有一个元素结点的条件是：_L->next->next==L下一个元素的后继恒为自身2•已知链队列的头尾指针分别是f和r,则将s指向的结点入队的操作是_____________r->next=s ; r=s ______ 。
将插入元素赋值给原队尾指针的后继3. 广义表A((( ),(a,(b),c))) ,head(tail(head(tail(head(A)))) 等于_(b) _。
HeadA=(( ),(a,(b),c))tail(head(A))= (a,(b),c)head(tail(head(A))= (a,(b))tail(head(tail(head(A)))= ((b))head(tail(head(tail(head(A))))= (b)4. _______________________________ 高度为5的完全二叉树至少有8 _个叶子结点5. —棵树T中，包括一个度为1的结点，两个度为2的结点，三个度为3的结点，四个度为4的结点和若干叶子结点，则T的叶结点数为_ 1+2*1+3*2+4*3 = 21_____________________________________________________________________ 。
6. ________________________________ 求图的最小生成树有两种算法中，prim 算法适合于求稠密图的最小生成树。
7. _________________________________________________________ 具有10个关键字的有序表，折半查找的平均查找长度____________________________ 。
8. ____________________________________ 高度为7的平衡二叉树的结点数至少有__________________________________________ 33 ___ 个。
用斐波那契序数进行计算9. 在一棵n阶B-树中,若在某结点中插入一个新关键字而引起该结点分裂,则此结点中原有的关键字的个数是___ m-1 _____ 。
B-树是一种多路查找树。
M阶的B树具有如下特性：每一个分支结点都有k-1个元素和k个孩子。
？10. 对n个记录进行简单选择排序，所需进行的关键字间的比较次数为__________1+2+3+…+(n-1) = n(n-1)/2 。
四、简答题(每题5分，共10题50分)1.画出广义表(a，( b，c，d)，e)的存储结构图(采用头尾指针的链表结构，标志1表示表结点，标志0表示原子结点)广义表的注意点：同一个括号内的横向表示2•画出下列由三棵树组成的森林转换为二叉树。
森林转化为二叉树的要点：先将每一棵树都转化为二叉树，再进行组合3.给定一组叶子的权值分别为：8 6、3、2、7、24，填写下表构造一棵赫夫曼树，并画出该18900268003370042700579006241100758438111078915105110261189赫夫曼树（同一层的左子树根权值小于右子树根权值）HT：weight pare nt Ichild rchild325006104. 已知某图的邻接表(1).画出此邻接表对应的图；(2).写出由v1开始的深度优先遍历的序列;(3).画出由v1开始的深度优先的生成树；v1开始深度优先遍历的序列：v1-v2-v5-v3-v4-v65. 画出带权无向图的一棵最小生成树。
源点AV(i) 路径终占 ―二八、、 B CD E i=1路径 路径长度AB 3AC 20AE 45B ABi=2路径 路径长度ABC 18ABE 43 C ABCi=2路径 路径长度ABCD 38ABE 43 D ABCDi=4路径 路径长度ABE 43E ABE7•由字符序列(t, d, e, s, u, g,)建立一棵平衡的二叉排序树(画出主要过程)最后一步：因为在右子树上的左子树上进行插入所以首先对大右子树进行向右旋转, 整体树再向左旋转，最后整体调节一下平衡。
8.已知散列表的地址空间为A[0..11]，散列函数H(k) =k mod 11 ,采用线性探测法处理冲突。