命题：一、单项选择题。
在题后括号内，填上正确答案代号。
（本大题共15小题，每小题2分，总计30分）。
1.数据结构是研究数据的（ ）以及它们之间的相互关系。
（A ）理想结构，物理结构 （B ）理想结构，抽象结构（C ）物理结构，逻辑结构 （D ）抽象结构，逻辑结构2.算法分析的两个主要方面是（ ）（A ）正确性和简单性 （B ）可读性和文档性（C ）数据复杂性和程序复杂性 （D ）时间复杂度和空间复杂度3. 对于一个头指针为head 的带头结点的单链表，判定该表为空表的条件是（ ）（A ）head==NULL （B ）head →next==NULL （C ）head →next==head （D ）head!=NULL 4.队列操作的原则是（ ） （A ）先进先出 （B ）后进先出（C ）只能进行插入 （D ）只能进行删除5．设循环队列Q[N]的头尾指针为F 、R ，头指针F 总是指在队列中的第一个元素的前一位置，则判断队列为空的条件是（ ）。
（A ）R==F （B ）R!=F （C ）F==(R+1)%N （D ）F!=(R+1)%N6. 设有二维数组A[50][60]，其元素长度为4字节，按行优先顺序存储基地址为200，则元素A[18][25]的存储地址为（）。
（A ）3700 （B ）4376 （C ）3900 （D ）46207. 若长度为n 的线性表采用顺序存储结构，在其第i(1<=i<=n+1)个位置插入一个新元素的算法的时间复杂度为（ ）。
（A ） O(0) （B ） O(1) （C ） O(n) （D ） O(n 2) 8.n 个顶点的连通图至少有（ ）条边（A ）n-1 （B ）n （C ）n+1 （D ）09.请指出在顺序表{2、5、7、10、14、15、18、23、35、41、52}中，用二分法查找关键码17需做（ ）次关键码比较。
（A）2 （B）3 （C）4 （D）510.设有字符序列{Q、H、C、Y、P、A、M、S、R、D、F、X}，问新序列{F、H、C、D、P、A、M、Q、R、S、Y、X}是下列哪个排序算法一趟扫描的结果。
（）(A)起泡排序（B）初始步长为4的shell的排序（C）二路归并排序（D）以第一个元素为分界元素的快速排序11．设一个栈的输入序列是1，2，3，4，5 ，则下列序列中，是合法输出序列的是（）（A）5 1 2 3 4 （B）4 5 1 3 2（C）3 2 1 5 4 （D）4 3 1 2 512．已知有向图G=(V,E)，其中V={V1,V2,V3,V4,V5,V6,V7}，E={<V1,V2>,<V1,V 3>,<V1,V4>,<V2,V5>,<V3,V5>,<V3,V6>,<V4,V6>,<V5,V7>,<V6,V7>},G的拓扑序列是（）。
(A)V1,V3,V4,V6,V2,V5,V7(B)V1,V3,V2,V6,V4,V5,V7(C)V1,V3,V4,V5,V2,V6,V7(D)V1,V2,V5,V3,V4,V6,V713．用链表表示线性表的优点是（）。
（A）便于随机存取（B）便于插入删除操作（C）花费的存储空间较顺序存储少（D）元素的物理顺序与逻辑顺序相同14．在一个无向图中，所有顶点的度数之和等于所有边数的（）倍。
(A) 1/2 (B) 1 (C) 2 (D) 415．下列排序算法中，其中（）是稳定的。
（A）堆排序，冒泡排序（B）快速排序，堆排序（C）直接选择排序，归并排序（D）归并排序，冒泡排序二、填空题。
在题中“”处填上答案。
（本大题共7小题，每空1分，总计12分）。
1．数据的逻辑结构被分为____________________,线性结构,________________,_________________四种。
2．下面程序段中带下画线的语句的执行次数的数量级是___________。
for (int i=0;i<m;i++)for (int j=0;j<n;j++)a[i][j]=i*j;3．若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3，当从队列中删除一个元素，再加入两个元素后，rear的值为___________，front的值为____________。
4．一组记录的排序码为(48,24,18,53,16,26,40)，采用冒泡排序法进行排序(升序)，则第一趟排序需要进行记录交换的次数是__________。
5．给定表（653,503,87, 61,908,170, 512,897,275, 462），用筛选法建立初始堆(大堆)，则初始堆表为。
6．设有n个结点的完全二叉树，如果按照从自上到下、从左到右从1开始顺序编号，则第i个结点（非根结点）的双亲结点编号为______________，右孩子结点的编号为_____________。
7.已知一有向图的邻接表存储结构如下图：从顶点1出发，深度优先（DFS）遍历的输出序列是，广度优先（BFS）遍历的输出序列是。
三、程序填空题。
在题中“”处填上答案。
（本大题共3小题，每空3分，总计18分）得分1.下面程序段的功能实现数据x进栈，要求在下划线处填上正确的语句。
typedef struct {int s[100]; int top;} sqstack;void push(sqstack &stack,int x){if (stack.top==Maxsize-1)printf(“overflow”);else{ ____________________;____________________;}}2.下列算法实现在二叉排序树上查找关键值k，请在下划线处填上正确的语句。
typedef struct node{int key;struct node *lchild;struct node *rchild;}bitree;bitree *bstsearch(bitree *t, int k){if (t==NULL ) return(0);else while (t!=NULL)if (t->key==k)_____________;else if (t->key>k)t=t->lchild;else_____________;}3.下面程序段的功能是实现快速排序的划分算法，请在下划线处填上正确的语句。
typedef struct { int key;InfoType otherinfo;}RecType;typedef RecType SeqList[N+1];int Partition(SeqList R,int i,int j){ RecType pivot=R[i];while(i<j){while(i<j&&R[j].key>=pivot.key)j--;if(i<j)R[i++]=R[j];while(____________________________________)i++;if(i<j)_________________________________;}R[i]=pivot;return i; }四、应用题。
（共4小题，每题6分，总计24分）。
先序遍历序列： A B D F C E G H中序遍历序列： B F D A G E H C（1）画出这棵二叉树；（2）写出这棵二叉树的后序遍历序列。
2.设哈希表地址空间是0…8，哈希函数是H(k)=k%7，采用线性探测再散列处理冲突，将序列{100,20,21,35,3,78}数据序依次存入此哈希表中。
根据要求构造哈希表，列出插入时的比较次数，并求出在等概率下的平均查找长度。
3.应用希尔排序算法对关键字序列从小到大进行排序，键值序列为{178,512, 170,897, 653,426,154,509,782}，增量序列为{5，3，1}，试写出每趟排序的结果。
4. 下图表示一个地区的通讯网，边表示城市间的通讯线路，边上的权表示架设线路花费的代价，画出用普里姆(Prim)算法选择能沟通每个城市且总代价最省的n-1条线路。
五、算法设计题。
（共2题，每题8分，共16分）。
1．编写递归算法，求二叉树的深度。
树的定义如下：typedef struct BiTNode {TElemType data;struct BiTNode *lchild, *rchild; // 左右孩子指针 } BiTNode, *BiTree;2．已知两个单链表中的元素递增有序，写一函数将两个单链表合并成一个递增有序的单链表，并说明算法的时间复杂度。
说明：链表有表头，单链表的结点定义如下：typedef struct LNode{ int data; struct LNode *next;}LN;函数头定义: void MergeList(LN *la, LN *lb, LN *lc)// la,lb分别是被合并链表的头指针，lc是合并后链表的头指针。
