一、 单项选择:（每空2分，共30分）
1. 数据结构是一门研究非数值计算的程序设计问题中,数据元素的① C 、数据信息在计算机中的②
A 以及一组相关的运算等的课程。
① A．操作对象 Ｂ．计算方法 Ｃ．逻辑结构 Ｄ．数据映象 ② A．存储结构 Ｂ．关系 Ｃ．运算 Ｄ．算法 2. 线性表的逻辑顺序与存储顺序总是一致的，这种说法__ B _。
A. 正确 B. 不正确
3. 一个栈的入栈序列a，b，c，d，e，则栈的输出序列是_ A ___。 A. edcba B. decba C. dceab D. abcde 4. 栈的特点是__ B __，队列的特点是__ A __。 A. 先进先出 B. 先进后出 5．空串与空格串是相同的，这种说法_ B ___。
A. 正确 B. 不正确
6. 二维数组A中，每个元素A的长度为3个字节，行下标i从0到7，列下标j从0到9，从首地址SA开始连续存放在存储器内，该数组按行存放时，数组元素A[7][4]的起始地址为_ C ___。
A. SA+141 B. SA+144 C. SA+222 D. SA+225
7. 如果某二叉树的前根次序遍历结果为stuwv，中序遍历为uwtvs，那么该二叉树的后序
为_ B ___。 A. uwvts B. vwuts C. wuvts D. wutsv
8. 深度为5的二叉树至多有__ C __个结点。
A. 16 B. 32 C. 31 D. 10
9．在一个无向图中，所有顶点的度数之和等于所有边数的__ C __倍。
A. 1/2 B. 1 C. 2 D. 4
10.采用顺序查找方法查找长度为n的线性表时，每个元素的平均查找长度为_ C ___.
A. n B. n/2 C. (n+1)/2 D. (n-1)/2
11. 采用二分查找方法查找长度为n的线性表时，每个元素的平均查找长度为__ C __。
A．O（n2） B. O(nlog2n) C. O(n) D. O(log2n)
12. 下述几种排序方法中，要求内存量最大的是_ D ___。
A. 插入排序 B. 选择排序 C. 快速排序 D. 归并排序
13. 排序方法中，从未排序序列中依次取出元素与已排序序列（初始时为空）中的元素
进行比较，将其放入已排序序列的正确位置上的方法，称为_ C ___。
A. 希尔排序 B. 起泡排序 C. 插入排序 D. 选择排序
二、填空:（每空2分, 共20分）
1. 分析下面算法（程序段），给出最大语句频度 n ，该算法的时间复杂度是_ O (n2)_
for (i=0;i A[i][j]=0; 2. 在双向链表中，每个结点有两个指针域，一个指向____前驱结点__，另一个指向后继结点 3．空串是__ 零个字符的串 __，其长度等于_零_ __。 4．折半查找的存储结构仅限于___顺序存储结构 _，且是_有序的 ___。 5．一个图的 邻接矩阵 表示法是唯一的，而 邻接表 表示法是不唯一的。 2 三、用图表回答下列问题:（共20分） 1．设某通信系统使用八A，B ，C，D，E，F，G，H个字符，他们出现的概率w={５， ２９，７，８，１４，２３，３，１１}，试构造对应的哈夫曼树（请按左子树根结点的权小于右子树树根结点的权的次序构造）? 2．根据下面的邻接链表，画出相应的图，并写出每个顶点的度。 v2 v1 v2 v3 v3 v4 ^ v5 v6 ^ v4 v6 v3 ^ v6 v5 v5 v4 ^ 19 D 8 H 11 100 42 F 23 48 29 B 29 E 15 C 7 G 3 A 5 8 14 解： V1: 3 V2: 2 V3: 3 V4: 2 V5: 4 v4 v5 v1 v2 v3 V6: 2 V6 四、阅读下列算法，分析它的作用：（每小题10分，共20分） 1. 阅读下列算法，说明该算法的作用。 // 类定义 ElemTtype Sqstack::pop( ) { ElemType x; if ( top==0 ) x=-999; else { x = elem[top]; top--; } return x; } // pop const int MAX=20; typedef char ElemType ; class Sqstack { private: ElemType elem [MAX]; int top ; public: Sqstack(){top=0}; ElemType pop(); void push(ElemType x); //…….; } ; 答：该算法是顺序栈类的出栈算法。 如果栈空返回-999；否则返回出栈元素的值。 2. 有如下图所示单链表，经过reverse 算法处理后，单链表发生了什么变化 ？ 画出处理后的单链表图示。 struct Snode //结点结构 void Link ::reverse() { char data; { Snode *p, *q ; Snode *next ; } ; class Link //链表类 { private: Snode *Head; public: Link (){Head =NULL}; void creat(); void reverse (); void output(); //…….; p= Head ->next; Head ->next=NULL; while( p !=NULL) { q=p->next ; p->next= Head ->next; Head >next=p; p=q; } } // reverse Head a b c d e ^ 答：该算法是将链表逆置的算法。 链表逆置后，具体如下图： Head e d c b a ^ 五、算法设计题。 1. 写一算法，统计二叉树的叶子结点的个数。 //利用中序遍历方法，或者先序、后序均可以 void Btree ::inordern( bnode *p, int &n ) { if ( p!=NULL) { inordern( p->lch, n); if ( p->lch==NULL && p->rch==NULL) n++; inordern( p->rch, n); } } // inordern