insert(str)； }
三、程序理解题（每题10分，共30分）
1、已知函数f的功能是求1-n的和。 int f( int n ) {
int i,sum; for(i=1;i<=n;i++) ； return sum;
}
问题（1）将函数f补充完整；（5分） 问题（2）写出主函数，求1-100的和。（5分） 2、编程求下列分段函数的值(x,y均为整型变量) 2x-10 x>0 y = x+5 x=0 2x+10 x<0
3、编程对10个正整数排序（可采用起泡法或选择法任意一种完成）。
第二部分 数据结构
一、选择题（2分×25＝50分）
1、数据的最小单位是（ ）。
A) 数据项 B) 数据类型 C) 数据元素 D) 数据变量 2、字符串的长度是指（ ）。
A) 串中不同字符的个数 B) 串中不同字母的个数 C) 串中所含字符的个数 D) 串中不同数字的个数 3、以下数据结构中（ ）是非线性结构？
A) 队列 B) 栈 C) 线性表 D) 二叉树 4、建立一个长度为n的有序单链表的时间复杂度为（ ）。
2
A) O(n) B) O(1) C) O(n) D) O(log2n) 5、两个字符串相等的充要条件是（ ）。
A) 两个字符串的长度相等 B) 两个字符串中对应位置上的字符相等 C) 同时具备(A)和(B)两个条件 D) 以上答案都不对 6、算法的时间复杂度是指（ ）。
A) 执行算法程序所需要的时间 B) 算法程序的长度
C) 算法执行过程中所需要的基本运算次数 D) 算法程序中的指令条数 7、队列是一种（ ）的线性表。
A) 先进先出 B) 先进后出 C) 只能插入 D) 只能删除
8、长度为N的线性表进行顺序查找，在查找不成功时，与关键字的比较次数为 ( )。 A) N B) 1 C) N-1 D) 0
9、若有18个元素的有序表存放在一维数组A[19]中，第一个元素放A[1]中，现进行二分查找，则查找A[3]的比较序列的下标依次为（ ）。
第 6 页 共 9 页
A） 1，2，3 B） 9，5，2，3 C） 9，4，3 D） 9，4，2，3
10、设某有向图中有n个顶点，则该有向图对应的邻接表中有（ ）个表头结点。 A) n-1 (B) n (C) n+1 (D) 2n-1 11、线性链表不具有的特点是（ ）。
A) 随机访问 B) 不必事先估计所需存储空间大小 C) 插入与删除时不必移动元素 D) 所需空间与线性表长度成正比
12、设有6个结点的无向图，该图至少应有（ ）条边才能确保是一个连通图。 A) 5 B) 6 C) 7 D) 8
13、设某棵二叉树的中序遍历序列为ABCD，先序遍历序列为CABD，则后序遍历该二叉树得到序列为（ ）。
A) BADC B) BCDA C) CDAB D) CBDA
14、在有n个叶子结点的正则二叉树（无度为1的结点）中，其结点总数为（ ）。 A) 2n B) 2n-1 C） 2n+1 D) 2n-1
15、设一组初始记录关键字序列为(50，40，95，20，15，70，60，45)，则以增量d=4的一趟希尔排序结束后前4条记录关键字为（ ）。 A) 40，50，20，95 B) 15，40，60，20 C) 15，20，40，45 D) 45，40，15，20
16、函数substr(“DATASTRUCTURE”，5，9)的返回值为（ ）。 A) “STRUCTURE” B) “DATA”
C) “ASTRUCTUR” D) “DATASTRUCTURE”
17、设一个有序的单链表中有n个结点，现要求插入一个新结点后使得单链表仍然保持有序，则该操作的时间复杂度为（ ）。
2
A) O(log2n) B) O(1) C) O(n) D) O(n) 18、以下不是堆的是（ ）。
A) （100，98，88，82，80，77，66，60，40，28，18） B) （18，28，40，60，66，77，80，82，85，98，100） C) （100，88，98，77，80，60，82，40，28，18，66） D) （100，85，40，77，80，60，66，98，82，18，28） 19、顺序存储设计时存储单元的地址（ ）。 A) 一定连续 B) 一定不连续
C) 不一定连续 D） 部分连续，部分不连续
20、设一组权值集合W=(15，3，14，2，6，9，16，17)，要求根据这些权值集合构造一棵哈夫曼树，则这棵哈夫曼树的带权路径长度为（ ）。 A) 129 B) 219 C) 189 D) 229
21、设一组初始记录关键字序列为(Q，H，C，Y，P，A，M，S，R，D，F，X)，则按字母升序的第一趟冒泡排序结束后的结果是（ ）。
A) F，H，C，D，P，A，M，Q，R，S，Y，X B) P，A，C，S，Q，D，F，X，R，H，M，Y C) A，D，C，R，F，Q，M，S，Y，P，H，X D) H，C，Q，P，A，M，S，R，D，F，X，Y
22、设有一组初始记录关键字序列为(34，76，45，18，26，54，92)，则由这组记录关键字生成的二叉排序树的深度为（ ）。 A) 4 B) 5 C) 6 D) 7
23、具有n个顶点的无向图最多可包含（ ）条边。 A) n-1 B) n C) n(n-1)/2 D) n(n-1)
第 7 页 共 9 页
24、设无向图G中的边的集合E={(a，b)，(a，e)，(a，c)，(b，e)，(e，d)，(d，f)，(f，c)}，则从顶点a出发进行深度优先遍历可以得到的一种顶点序列为（ ）。 A) aedfcb B) acfebd C) aebcfd D) aedfbc
25、对初始状态为递增序列的表按照递增顺序排序，最省时间的是（ ）算法。 A) 堆排序 B) 插入排序 C) 基数排序 D) 归并排序
二、填空题（2分×15＝30分）
1、从题后给出的选项中选择一个合适的项填空。
1）在计算机内实现递归算法时所需要的辅助数据结构是 ；银行排队系统实现时需要的辅助数据结构是 。（可选项： 栈、队列） 2）用二叉链表表示具有n个节点的二叉树时，值为空的指针域的个数为 。（可选项：2n、n+1）
3）一个程序能确切地满足具体问题的需求，表明此程序满足 要求；若能很好地处理异常，表明此程序满足 要求。（可选项：正确性、可读性、健壮性）。
4）向一棵二叉排序树中插入一个元素时，若元素的值小于根结点的值，则应把它插入到根结点的 上。（可选项：左子树、右子树）
5）在用于表示有向图的邻接矩阵中，对第i行的元素进行累加，可得到第i个顶点的 度；而对第j列的元素进行累加，可得到第j个顶点的 度。 （可选项：出、入） 2、算法填空。
1）下列算法是在顺序表中的第i个位置插入一个元素x,插入成功返回1,插入不成功返回0,将此算法补充完整。
int ListInsert(Seqlist *L , int i , DataType x) { int j;
if(L->size>=MaxSize || i<0||i>L->size) return 0; for(j=L->size;j>i;j--) （1） ; L->list[i]=x; （2） ; return 1; }
2）下面程序段的功能是实现二分查找算法，将此算法补充完整。
struct record {
int key; int others; };
int bisearch(struct record r[ ], int k) {
int low=0,mid,high=n-1; while(low<=high) {
第 8 页 共 9 页
（1） ;
if(r[mid].key==k) return(mid+1);
else if( （2） ) high=mid-1; else （3） ; }
return(0); }
3）下面程序段的功能是实现数据x进栈，要求在下划线处填上正确的语句。 typedef struct { int s[100] ; int top; } sqstack; void push(sqstack *s,int x) {
if (s->top==m-1) printf(“overflow”); else { （1） ;
（2） ; } }
三、计算分析算法题（每题10分，共20分）
1、写出下列二叉树的先序、中序、后续遍历序列（10分）。
C B D F A E G 2、设一组12个数据元素的关键字序列为{30，42，36，9，33，22，85，12，49，39}，设哈希函数为H（key）=key % 15,哈希冲突函数采用线性探测法，即冲突函数为：
d0 = H(key) di = (di-1 + 1) % m (i=1,2,3,??) 其中，m为哈希表空间大小，并设哈希表空间大小m=15。
问题（1）构造数据元素序列的哈希表，把关键字序列填到下表合适的位置（8分）。 0
1 2 3 4 5 6 7 8 9 10 11 12 13 14 问题（2）计算该哈希表在等概率情况下查找成功的平均查找长度ASL（2分）。
第 9 页 共 9 页