华侨大学《数据结构》试卷（A）系别：班级：学号：姓名：考试日期：年月日一、选择题（每题1.5分，共15分）1、若长度为n的线性表采用顺序存储结构，删除它的第i数据元素之前，需要先依次向前移动（）个数据元素。
A.n-iB.n+iC.n-i-1D.n-i+12、对于只在表的首、尾两端进行插入操作的线性表，宜采用的存储结构为（）。
A.顺序表B.用头指针表示的单循环链表C. 用尾指针表示的单循环链表D.单链表3、将一个递归算法改为对应的非递归算法时，通常需要使用（）。
A. 栈B. 队列C. 循环队列D. 优先队列4、设有两个串t和p，求p在t中首次出现的位置的运算叫做（）。
A. 求子串B. 模式匹配C. 串替换D. 串连接5、设有一个二维数组A[20][30]，以行为主序储存，假设A[0][0]存放位置在64410，每个元素占据一个储存空间，则A[4][5]存储在（）位置。
A. 69210B.62610C.76910D. 724106、由权值分别为3,8,6,2,5的叶子结点生成一棵赫夫曼树，它的带权路径长度WPL为（）。
A. 24B. 48C. 72D. 537、一个无向连通图的生成树是含有该连通图的全部顶点的（）。
A.极小连通子图B.极小子图C.极大连通子图D.极大子图8、具有n个顶点的有向完全图可包含（）条有向边。
A．n-1 B．n C．n(n-1)／2 D．n(n-1)9、设有一个用开放定址法的线性探测再散列处理冲突的哈希表如下：哈希函数为H（key）=key%11，若要查找关键字14的记录，所需的探测次数是（）。
A. 3B. 6C. 7D. 910、在下列排序方法中，不稳定的排序是（）。
A. 直接插入排序B. 归并排序C. 快速排序D.冒泡排序二、填空题（每空1分，共10分）1、数据的逻辑结构被分为集合、和网状结构四种。
2、在一个稀疏矩阵中，每个非零元素所对应的三元组包括该元素的、和值三项。
3、一棵高度为5的二叉树中最少含有个结点，最多含有个结点；一棵高度为5的完全二叉树中，最少含有个结点，最多含有个结点。
4、在线性表中采用折半查找法（二分查找法）查找一个数据元素，线性表中元素应该按值有序，并且采用存储结构。
5、若对序列(49，38，65，97，76，13，27，50)采用简单选择排序法排序，则第二趟结束后序列的状态是。
三、解答题（每题5分，共30分）1、指出下面算法中，带下划线语句的语句频度，并估计该算法的时间复杂度。
int Sum_fact(int n){int s=0,m,k,t;for(m=1;m<=n;m++){t=1;for(k=1;k<=m;k++) t*=k;s+=t;}return s;}2、设进栈序列为A,B,C,D,E，试问能否分别得到D,C,E,B,A和C,D,A,B,E的出栈序列？若不能得到，请说明理由；若可以得到，则写出以“push”表示进栈，“pop”表示出栈的栈操作序列。
3、已知二叉树bt的中序遍历序列为：BDACEFHGJIK，先序遍历序列为：EABDCFGHIJK，请构造该二叉树（画出树形），并画出对应的后序线索二叉树（不带头结点）。
4、试画出如下图所示的无向图G的邻接表表示，要求邻接表中的各顶点的邻接链表中表结点按顶点序号从小到大排列。
根据你所给出的邻接表，写出从A出发的广度优先搜索序列,并画出从顶点A出发的广度优先搜索（bfs）生成树。
无向图G5、已知表长为14的有序顺序表，试画出对其进行折半查找时的判定树，并计算等概率下查找成功的平均查找长度和查找不成功的平均查找长度。
6、已知待排序序列为（48，70，33，65，24，56，12，92，86，22），给出采用快速排序算法进行关键字从小到大排序时第一趟分划的详细过程。
（取第一个关键字为支点关键字）四、算法阅读题（每题5分，共15分）1、设list为带头结点的单链表头指针，阅读下面算法，指出该算法的功能。
typedef struct Node{char name[10];int age,score;struct Node* next;}* LinkList;void fun1(LinkList & list,int order) //order表示结点在链表中的位序（从1开始）{if(! (order>=1 && order<=Get_length(list)) ){// Get_length(list)返回表list的长度cout<<"Error order found\n";return NULL;}LinkList t=list->next;int num=1;while(num<order){num++;t=t->next;}cout <<t->name<<”,”<<t->age<<”,”<<t->score<<endl;}2、阅读下面算法，指出该算法的功能。
Status fun2(char *str){Stack T; Queue Q;char ch1, ch2; int i ;InitStack（T）;InitQueue(Q);for ( i = 0; str[i] != ‘\0’; i++) {Push( T, str[i] );EnQueue( Q, str[i] );}for ( i =1; i <= StackLength(T)/2 ; i++ ){ //StackLength(T)返回栈T的长度Pop(T, ch1) ;DeQueue( Q, ch2);if ( ch1 != ch2 ) return false;}return true;}3、设二叉树T以二叉链表为存储结构，指出下面算法的功能。
int fun3(BiTree T){if (!T ) return 0;if (T->lchild ！= NULL && T->rchild != NULL ) return 1;else return (fun3( T->lchild) + fun3 ( T->rchild));}五、算法设计题（共30分）（说明：你所设计算法中若需调用基本操作，需给出实现该基本操作的算法）1、设L为带头结点的单链表头指针且链表长度大于2，试设计算法删除链表L的首结点，并将该结点插入到链表L的尾结点之后。
（10分）2、设二叉排序树bt以二叉链表为存储结构，试设计算法删除二叉排序树bt中值最大的结点。
（8分）3、试设计算法Create_dg(Mgraph g1,Algraph &g2)，将数组表示的有向图g1，转换成邻接表表示的有向图g2。
（12分）#define INFINITY INT_MAX#define MAX_NUM 20//图的数组（邻接矩阵）存储表示：typedef struct ArcCell{VRType adj;InfoType *info;} ArcCell;typedef struct{VertexType vexs[MAX_NUM] ;ArcCell arcs[MAX_NUM] [MAX_NUM];int vexnum , arcnum;}MGraph; //图的邻接表存储表示：typedef struct ArcNode{int adjvex;struct ArcNode *nextarc;}ArcNode;typedef struct VNode{VertexType data;ArcNode *firstarc;}VNode;typedef struct{VNode vertices[MAX_NUM];int vexnum , arcnum;}ALGraph;A卷参考答案一、选择题（共15分，每小题1.5分）二、填空题（共10分，每小题1分）1.2.3.4.5.三、解答题（共30分，每小题5分）1.t=1;的语句频度是n-----------------------（1分）t*=k; 的语句频度是n(n+1)/2---------------(2分)该算法的时间复杂度是O(n(n+1)/2)=O(n2)----(2分)2.可以得到D,C,E,B,A的出栈序列，其出栈操作序列是：push,push,push,push,pop,pop,push,pop,pop,pop---------（2.5分）不能得到C,D,A,B,E的出栈序列,因为要先得到C,D的出栈子序列，则A,B必已进栈。
由栈的后进先出特性，B必先于A出栈，因此不可能得到C,D,A,B,E的出栈序列。
----（2.5分）3.该二叉树的后序遍历序列为：DBCAHJKIGFE（2分），中序线索二叉树（不带头结点）为：（3分）4. 无向图G 的邻接表表示如下:(2分)从A 出发的bfs 序列是：A,B,C,E,D,F (1.5分) bfs 生成树是： (1.5分)5．判定树（2分）ASL succ =1114i i C =∑= 114(1+2*2+3*4+4*7)=4514 （1.5分）ASL unsucc=591515115iic=∑=115(3*1+4*14)=5915（1.5分）6.快速排序算法进行排序时第一趟快速划分的详细过程如下（5分）48 70 33 65 24 56 12 92 86 2222 70 33 65 24 56 12 92 8622 33 65 24 56 12 92 86 7022 12 33 65 24 56 92 86 7022 12 33 24 56 65 92 86 7022 12 33 24 56 65 92 86 70{22 12 33 24} 48 {56 65 92 86 70}四、算法阅读题（共15分，每小题5分）1.根据给定的位序order，返回第order个元素所在位置的指针；若链表中没有第order个元素，则返回NULL。
2. 判断字符串是不是回文（对称）。
3.统计二叉树T中所有结点的个数五、算法设计题（共30分）1．void def_f_ins_l(Linklist &l){ --------1分//删除首结点，插入在尾结点之后p = l->next; --------1分while ( p->nexet) p = p->next; //p指向尾结点--------3分q = l->next; //q指向首结点--------1分l->next = q->next; //删除--------2分p->next = q; //插入--------1分q->next = NULL; //或者 q->next=p->next; p->next = q; --------1分}//del_f_ins_l2.Status del_max(BiTree &bt){ --------1分//删除二叉排序树bt中值最大结点if (!bt) return ERROR; //空树p = bt;if (bt->rchild == NULL){ //根无右子树--------2分bt = bt->lchild; p->lchild = NULL;//此语句可不要free(p);}else{while(p->rchild != NULL){//p移至最右下结点q = p; p = p->rchild;}if(p->lchild != NULL)//有左子树--------5分q->rchild = p->lchild;else q->rchild = NULL;//无左子树free(p);}}//del_max3.Status Create_dg(Mgraph g1.Algraph &g2){ --------1分//将数组表示的有向图g1转换成邻接表表示的有向图g2g2.vexnum = g1.vexnum; g2.arcnum = g1.arcnum; --------1分for(i=0;i<g1.vexnum;++i){//生成g2的表头向量--------3分g2.vertices[i].data = g1.vexs[i];g2.vertices[i].firstarc = NULL;}for(i=0;i<g1.vexnum;++i){//遍历g1的邻接矩阵--------7分for(j=0;j<g1.vexnum;++j)if(g1.arcs[i][j] != 0){p = (arcnode*)malloc(sizeof(arcnode));if(!p) exit(OVERFLOW);p->adjvex = j; //生成表头结点p->nextarc = g2.vertices[i].firstarc; //插入g2.vertices[i].firstarc = p;}//if}//for-ireturn OK；}Create_dg。
![2008~2009数据结构(A)[1]](https://img.taocdn.com/s1/m/158573faf705cc175527095c.png)
