(完整word版)2007~2008学年《数据结构》A

1、华侨大学数据结构试卷（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 中首次出现的位

2、置的运算叫做（）。A. 求子串B.模式匹配C. 串替换D.串连接5、设有一个二维数组A2030，以行为主序储存，假设A00存放位置在64410，每个元素占据一个储存空间，则 A45 存储在（）位置。A. 692 10B.626 10C.769 10D. 724 106、由权值分别为 3,8,6,2,5的叶子结点生成一棵赫夫曼树，它的带权路径长度WPL为（）。A. 24B. 48C. 72D. 537、 一个无向连通图的生成树是含有该连通图的全部顶点的（）。A. 极小连通子图B. 极小子图C. 极大连通子图D. 极大子图8、具有 n 个顶点的有向完全图可包含（）条有向边。An-1BnCn(n-1

3、)2Dn(n-1)9、设有一个用开放定址法的线性探测再散列处理冲突的哈希表如下：0123456789101325801617614哈希函数为 H（ key ） =key%11，若要查找关键字14 的记录，所需的探测次数是（）。A. 3B. 6C. 7D. 910、在下列排序方法中，不稳定的排序是（）。A. 直接插入排序B.归并排序C. 快速排序D. 冒泡排序1二、填空题（每空1 分，共 10 分）1、数据的逻辑结构被分为集合、和网状结构四种。2、在一个稀疏矩阵中，每个非零元素所对应的三元组包括该元素的、和值三项。3、一棵高度为 5 的二叉树中最少含有个结点，最多含有个结点；一棵高度为5 的完全

4、二叉树中，最少含有个结点，最多含有个结点。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,

5、C,D,E ，试问能否分别得到 D,C,E,B,A 和 C,D,A,B,E 的出栈序列？若不能得到，请说明理由；若可以得到，则写出以“ push”表示进栈， “pop”表示出栈的栈操作序列。3、已知二叉树bt 的中序遍历序列为：BDACEFHGJIK，先序遍历序列为：EABDCFGHIJK，请构造该二叉树（画出树形），并画出对应的后序线索二叉树（不带头结点）。4、 试画出如下图所示的无向图G的邻接表表示， 要求邻接表中的各顶点的邻接链表中表结点按顶点序号从小到大排列。根据你所给出的邻接表，写出从 A 出发的广度优先搜索序列 , 并画出从顶点 A 出发的广度优先搜索（ bfs ）生成树。ABFE

6、CD无向图 G25、已知表长为 14 的有序顺序表，试画出对其进行折半查找时的判定树，并计算等概率下查找成功的平均查找长度和查找不成功的平均查找长度。6、已知待排序序列为（ 48， 70，33，65，24， 56， 12， 92， 86，22），给出采用快速排序算法进行关键字从小到大排序时第一趟分划的详细过程。 （取第一个关键字为支点关键字）四、算法阅读题（每题5 分，共 15 分）1、设 list 为带头结点的单链表头指针，阅读下面算法，指出该算法的功能。typedef struct Nodechar name10;int age,score;struct Node* next;* Link

7、List;voidfun1(LinkList & list,int order)/order 表示结点在链表中的位序（从1 开始）if(! (order>=1 && order<=Get_length(list) )/ Get_length(list)返回表 list 的长度cout<<"Error order foundn"return NULL;LinkList t=list->next;int num=1;while(num<order)num+;t=t->next;cout <<t->

8、;name<< ”,”<<t->age<< ”,”<<t->score<<endl;2、阅读下面算法，指出该算法的功能。Statusfun2(char*str)Stack T;Queue Q;char ch1, ch2;int i ;InitStack （ T ）;InitQueue(Q);for( i = 0;stri !=0;i+) Push( T,stri );EnQueue( Q, stri );for ( i =1;i <= StackLength(T)/2 ;i+ )/StackLength(T) 返回栈

9、 T 的长度Pop(T, ch1) ;DeQueue( Q, ch2);if ( ch1 != ch2 )returnfalse;returntrue;33、设二叉树T 以二叉链表为存储结构，指出下面算法的功能。intfun3(BiTree T)if (!T )return 0;if (T->lchild！= NULL && T->rchild != NULL )return 1;elsereturn (fun3( T->lchild) + fun3 ( T->rchild);五、算法设计题（共30 分）（说明：你所设计算法中若需调用基本操作，需给出实现

10、该基本操作的算法）1、 设 L 为带头结点的单链表头指针且链表长度大于2，试设计算法删除链表L 的首结点，并将该结点插入到链表 L 的尾结点之后。 （ 10 分）2、 设二叉排序树bt 以二叉链表为存储结构，试设计算法删除二叉排序树bt 中值最大的结点。 （8 分）3、 试设计算法Create_dg(Mgraphg1,Algraph&g2) ，将数组表示的有向图g1，转换成邻接表表示的有向图g2。（ 12 分）#defineINFINITYINT_MAX/ 图的邻接表存储表示：#defineMAX_NUM20typedef structArcNode/图的数组（邻接矩阵）存储表示：in

11、tadjvex;typedef structArcCellstruct ArcNode*nextarc;VRTypeadj;ArcNode;InfoType*info;typedefstructVNode ArcCell;VertexTypedata;typedefstructArcNode*firstarc;VertexTypevexsMAX_NUM ;VNode;ArcCellarcsMAX_NUM MAX_NUM;typedefstructintvexnum , arcnum;VNodeverticesMAX_NUM;MGraph;intvexnum , arcnum;ALGraph;4

12、A 卷 参考答案一、选择题（共15 分，每小题1.5 分）题号12345答案C题号678910答案二、填空题（共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 的出栈子序列

13、，则A,B 必已进栈。由栈的后进先出特性， B 必先于 A 出栈，因此不可能得到C,D,A,B,E 的出栈序列。- （ 2.5分）3.该二叉树的后序遍历序列为：DBCAHJKIGFE（ 2 分），中序线索二叉树（不带头结点）为：（ 3 分）54. 无向图 G的邻接表表示如下 :(2 分)0A1241B0352C0343D12454E0235F13从 A 出发的 bfs 序列是： A,B,C,E,D,F (1.5分 )bfs 生成树是：(1.5分 )5判定树（ 2 分）7311191352468101214ASL =114Ci =1(1+2*2+3*4+4*7)=45succ14 i 11414

14、（ 1.5 分）6unsucc=591 15ci=1(3*1+4*14)=59（1.5分）ASL1515 i 015156. 快速排序算法进行排序时第一趟快速划分的详细过程如下（5 分）4870336524561292862222703365245612928622336524561292867022123365245692867022123324566592867022123324566592867022123324485665928670四、算法阅读题（共15 分，每小题 5 分）1. 根据给定的位序order，返回第order 个元素所在位置的指针；若链表中没有第order 个元素，则返

15、回 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;

16、 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);7elsewhile(p->rchild != NULL)/p移至最右下结点q = p;p = p->rchild;if(p->lchild != NULL)/有左子树-5分q->rchild = p->lchild;elseq->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.verticesi.data = g1.vexsi;g2.verticesi.firstarc =