1．算法分析的目的是( C )。
A.找出数据结构的合理性 B.研究算法中输入和输出的关系 C.分析算法的效率以求改进 D.分析算法的易懂性和文档性 2．（ B ）是具有相同特性数据元素的集合，是数据的子集。
A.数据符号 B.数据对象 C.数据 D.数据结构 3．用链表表示线性表的优点是 ( C )。
A.便于随机存取 B.花费的存储空间比顺序表少 C.便于插入与删除 D.数据元素的物理顺序与逻辑顺序相同 4．输入序列为（A,B,C,D）不可能的输出有（ D ）。
A.(A,B,C,D) B. (D,C,B,A) C. (A,C,D,B) D . (C,A,B,D)
5．在数组表示的循环队列中，front、rear分别为队列的头、尾指针，maxSize为数组的最大长度，队满的条件是( B )。
A. front=maxSize B. (rear+1)%maxSize=front C. rear=maxSize D. rear=front
6．设有串t='I am a good student '，那么Substr(t,6,6)=（ D ）。
A. student B. a good s C. good D. a good
7．设有一个对称矩阵A，采用压缩存储方式，以行序为主序存储a11为第一个元素，其存储地址为1，每个元素占一个地址空间，则 a85地址为（ B ）。
A.23 B.33 C.18 D. 40
8．已知广义表 LS=(A,(B,C,D),E)运用head和tail函数，取出LS中原子b的运算（ C ）。
A. Gethead(Gethead(LS)) B. Gettail(Gethead(LS)) C. Gethead(Gethead(Gettail(LS))) D. Gethead(Gettail(LS))
9．若已知一棵二叉树先序序列为ABCDEFG，中序序列为CBDAEGF，则其后序序列为( A ) 。
A. CDBGFEA B. CDBFGEA C. CDBAGFE D. BCDAGFE 10．下列存储形式中，( C ) 不是树的存储形式。
A.双亲表示法 B.左子女右兄弟表示法 C.广义表表示法 D.顺序表示法
11．对待排序的元素序列进行划分，将其分为左、右两个子序列，再对两个子序列施加同样的排序操作，直到子序列为空或只剩一个元素为止。这样的排序方法是 ( C)。
A.直接选择排序 B.直接插入排序 C.快速排序 D.起泡排序 12．采用折半查找方法进行查找，数据文件应为（ A ），且限于（ ）。
A.有序表 顺序存储结构 B.有序表 链式存储结构 C.随机表 顺序存储结构 D.随机表 链式存储结构 13．就平均查找速度而言，下列几种查找速度从慢至快的关系是（ B ）
A.顺序 折半 哈希 分块 B.顺序 分块 折半哈希 C.分块 折半 哈希 顺序 D.顺序 哈希 分块 折半 14．执行下面程序段时，执行S语句的次数为（ D ）
for(int I=1;I<=n;I++) for(int j=1;j<=I;j++)
S;
A. n2 B. n2/2 C. n(n+1) D. n(n+1)/2 15．串是一种特殊的线性表，其特殊性体现在（ B）
A.可以顺序存储 B.数据元素是一个字符 C.可以链接存储 D.数据元素可以是多个字符
16．树的基本遍历策略分为先根遍历和后根遍历；二叉树的基本遍历策略可分为先序遍历、中序遍历和后序遍历。结论( A)是正确的。
A.树的先根遍历序列与其对应的二叉树的先序遍历序列相同 B.树的后根遍历序列与其对应的二叉树的先序遍历序列相同 C.树的先根遍历序列与其对应的二叉树的中序遍历序列相同 D.以上都不对
17．由五个分别带权值为9，2，3，5，14的叶子结点构成的一棵哈夫曼树，该树的带权路径长度为(C )。 A. 60 B. 66 C. 67 D. 50
18．一棵二叉树有67个结点，这些结点的度要么是0，要么是2。这棵二叉树中度为2的结点有(A )个
A. 33 B. 34 C. 32 D. 30
19．有一个有序表为{1,3,9,12,32,41,45,62,75,77,82,95,100},当二分查找值82为的结点时，（C ）次比较后查找成功。
A. 1 B. 2 C. 4 D. 8
20．若有文件的关键字序列为：[265] [301] [751] [129] [937] [863] [742] [694] [076] [438]，以下为二路归并排序过程。第二趟为:( D )
A.[265 301] [129 751] [863 937] [694 742] [076 438] B.[076 129 265 301 438 694 742 751 863 937] C.[129 265 301 694 742 751 863 937] [076 438] D.[129 265 301 751] [694 742 863 937] [076 438]
二、填空题（本大题共6小题，每空2分，共12分；答案填在下表内） 1 算法是指令的有限序列，其中每一条指令表示一个或多个操作，此外，一个算法还具有五个重要特性，它们分别是 ___有穷性____ 、____确定性__ 、___可行性_____ 、有零或多个输入和有一或多个输出。 2 算法优劣的五个标准是正确性、可使用性、___可读性___、__健壮性____、__效率___。
3 有n个球队参加的足球联赛按主客场制进行比赛，共需进行___n（n-1）______场比赛。4 设有串t='I am a student '，s='good'，那么Concat(t,s)= 'I am a student good'，Substr(t,8,7)= _____'student'_____。
5 在解决计算机主机与打印机之间速度不匹配时通常设置一个打印数据缓冲区，主机将要输出的数据依次写入该缓冲区，而打印机从该缓冲区中取出数据打印。该缓冲区应该是一个____队列_____ 结构，其主要特点是___先进先出_______。
6 广义表((a),a)的表头是____（a）___，表尾是___（a）____。 三、判断题（对的打“√”，错的打“×”。每小题1分，共10分;答案填在下表内） 1数据的逻辑结构与数据元素本身的内容和形式无关 。( √ )
2 三个结点的二叉树和三个结点的树一样，都具有三种不同的形态。（ × ） 3中序序列和后序序列相同的二叉树为：空树和缺右子树的单支树 。( √ ) 4对于两棵具有相同关键字集合而形状不同的二叉排序树，中序遍历后得到的关键字排列顺序相同。( √ ) 5 序列{30，40，50，15，25，35，38，10}是堆 。（ × ） 6 对于无向图的生成树，从同一顶点出发所得的生成树相同 。（ × ） 7 若设哈希表长m=14，哈希函数H(key)=key，表中已有4个结点。 addr(15)=4 addr(38)=5 addr(61)=6 addr(84)=7 其余地址为空，如用二次探测再散列处理冲突，关键字为49的结点的地址是9。( √ )
8一个深度为k的，具有最少结点数的完全二叉树按层次，(同层次从左向右)用自然数依此对结点编号则，
k-2
则编号最小的叶子的序号是2+1 ；编号是i的结点所在的层次号是「log2 i|+1。（「log2 i|表示向上取整」（根所在的层次号规定为1层）。( √ )
9在一棵7阶B树中，一个结点中最多有6棵子树，最少有3棵子树。（ × ） 10算法可以没有输入，但是必须有输出 。( √ ) 四、画出树的孩子兄弟表示法示意的树或森林。（4分）
五、要求题（本大题共2小题，共12分） 设关键字的输入序列为{4，5，7，2，1，3，6} 1．（8分）从空树开始构造平衡二叉树，画出每加入一个新结点时二叉树的形态，若发生不平衡，指明需做的平衡旋转类型及平衡旋转的结果。
（4分）上面的数据作为待排序的数据，写出用快速排序进行一趟划分后的数据序列 六、按要求做题（本大题共2小题，共12分）
1画出无向图G的邻接表存储结构，根据邻接表存储结构写出深度优先和广度优先遍历序列。（7分）
∧ H ∧ I ∧ ∧ D A ∧ C ∧ ∧ F ∧ ∧ G ∧ B E
50 V2 60 52 V4 V4 V2 V1 V3 V5 V6 V7 V8 V3 2 用prim算法求下图的最小生成树，写出最小生成树的生成过程。（5分）
V1 V1 45 V7 30 V6 V2 V3 V1 50 V7 V3 65 50 V5 42 V4 V6 V4 V2 V7 40 70 V5 V5 V6 七、算法分析设计题（本大题共5小题，共30分）
1．写出程序段的功能,并给出一个测试用例（一个输入数据和一个输出结果）(5分)。 void conversion() {
Stack s; int n;
SElemType e; initstack(s);
printf(\ scanf(“%d”,&n); while(n)
{push(s,n%8); n=n/8; }
while(!stackempty(s)) {pop(s,e);
printf(“%d”,e); } }
2.下面是一个使用栈stack实现对二叉树进行非递归先根遍历的函数,请在标号处填写合适的语句。(每空1分，共5分) 程序:
Void preorder(bitree *T) {bitree *stack[m]; int top;
if(T!=NULL) {top=1;
stack[top]=(1); while( (2) ) {p=stack[top]; top--;
printf(“%d”,p->data);
if(p->rchild!=NULL){ (3) ; stack[top]=p->rchild;} if( (4) ) { top++; (5) ;} }