2022年2007~2008学年《数据结构》A

1、华侨高校数据结构试卷（ A）系别：班级：学号：姓名：考试日期：年月日题号一二三四五总分得分一，选择题（每题 1.5 分,共 15 分）1，如长度为 n 的线性表接受次序储备结构,删除它的第i 数据元素之前,需要先依次向前移动（）个数据元素.A.n-iB.n+iC.n-i-1 D.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. 69210B.626 10C.769 10D. 724 106，由权值分别为 3,8,6,2,5的叶子结点生成一棵赫夫曼树,它的带权路径长度WPL为（）.A. 24B. 48C. 72D. 537， 一个无向连通图的生成树是含有该连通图的全部顶点的（）.A. 微小连通子图B. 微小子图C. 极大连通子图D. 极大子图8，具有 n 个顶点的有向完全图可包含（）条有向边.An-1BnCnn-12D

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

4、一棵高度为 5 的完全二叉树中,最少含有个结点,最多含有个结点.4，在线性表中接受折半查找法（二分查找法）查找一个数据元素,线性表中元素应当按值有序,并且接受储备结构.5，如对序列 49 , 38, 65, 97, 76,13, 27, 50 接受简洁选择排序法排序,就其次趟终止后序列的状态是.三，解答题（每题 5 分,共 30 分）1，指出下面算法中,带下划线语句的语句频度,并估量该算法的时间复杂度.int Sum_factint nint s=0,m,k,t; form=1;m=n;m+t=1;fork=1;k=1 & order=Get_lengthlist / Get_lengthli

5、st返回表 list 的长度coutnext; int num=1; whilenumnext;cout name ”,”age ”,”scoreendl;2，阅读下面算法,指出该算法的功能.Statusfun2char*strStack T;Queue Q;char ch1, ch2;int i ; InitStack （ T）; InitQueueQ;for i = 0;stri .=0;i+ Push T,stri ;EnQueue Q, stri ;for i =1;i lchild。= NULL & T-rchild .= NULL return 1; elsereturn fun3

6、 T-lchild + fun3 T-rchild;五，算法设计题（共 30 分）（说明：你所设运算法中如需调用基本操作,需给出实现该基本操作的算法）1， 设 L 为带头结点的单链表头指针且链表长度大于2,试设运算法删除链表L 的首结点,并将该结点插入到链表 L 的尾结点之后. （ 10 分）2， 设二叉排序树 bt 以二叉链表为储备结构,试设运算法删除二叉排序树bt 中值最大的结点. （8 分）3， 试设运算法 Create_dgMgraphg1,Algraph&g2 ,将数组表示的有向图g1,转换成邻接表表示的有向图g2.（ 12 分）可编辑资料 - - - 欢迎下载#defineINFI

7、NITYINT_MAX #defineMAX_NUM20/图的数组（邻接矩阵）储备表示： typedef structArcCellVRTypeadj; InfoType*info; ArcCell; typedefstructVertexTypevexsMAX_NUM ; ArcCellarcsMAX_NUM MAX_NUM; intvexnum , arcnum;MGraph;/ 图的邻接表储备表示： typedef structArcNodeintadjvex;struct ArcNode*nextarc;ArcNode;typedefstructVNode VertexTypedata

8、; ArcNode*firstarc;VNode;typedefstructVNodeverticesMAX_NUM; intvexnum , arcnum;ALGraph;可编辑资料 - - - 欢迎下载A 卷 参考答案一，选择题（共 15 分,每道题 1.5 分）题号12345答案C题号答案678910二，填空题（共 10 分,每道题 1 分）.5.三，解答题（共 30 分,每道题 5 分）1.t=1; 的语句频度是n-（ 1 分）t*=k;的语句频度是nn+1/2-2分2该算法的时间复杂度是Onn+1/2=On-2分2.可以得到 D,C,E,B,A的出栈序列,其出栈操作序列

9、是：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.该二叉树的后序遍历序列为：DBCAHJKIGF（E2 分）,中序线索二叉树（不带头结点）为：（ 3 分）可编辑资料 - - - 欢迎下载5可编辑资料 - - - 欢迎下载4. 无向图 G的邻接表表示如下:2分1240 A03503412450231

10、31 B2 C3 D4 E5 F从 A 动身的 bfs 序列是： A,B,C,E,D,F 1.5分 bfs 生成树是： 1.5分5. 判定树（ 2 分）7311可编辑资料 - - - 欢迎下载152469138101214可编辑资料 - - - 欢迎下载可编辑资料 - - - 欢迎下载ASLsucc = 114Ci =1 1+2*2+3*4+4*7=45（1.5 分）可编辑资料 - - - 欢迎下载14 i 11414可编辑资料 - - - 欢迎下载ASLunsucc = 5915115ci15 i 0= 1 3*1+4*14=591515（1.5 分）可编辑资料 - - - 欢迎下载6. 快

11、速排序算法进行排序时第一趟快速划分的详细过程如下（5 分）4870336524561292862222703365245612928622336524561292867022123365245692867022123324566592867022123324566592867022123324485665928670四，算法阅读题（共 15 分,每道题 5 分）1. 依据给定的位序order,返回第 order 个元素所在位置的指针.如链表中没有第order 个元素,就返回 NULL .2. 判定字符串是不是回文（对称） .3. 统计二叉树 T 中全部结点的个数五，算法设计题（共 30 分）1

12、 void def_f_ins_lLinklist &l1/删除首结点,插入在尾结点之后p = l-next;-1分while p-nexet p = p-next; /p指向尾结点分-3分q = l-next;/q指向首结点1l-next = q-next;/ 删除2分分p-next = q;/ 插入1q-next = NULL;/ 或者 q-next=p-next; p-next = q;/del_f_ins_l分-1分2.Status del_maxBiTree &bt1分/删除二叉排序树 bt 中值最大结点if .bt return ERROR;/ 空树p = bt;if bt-rch

13、ild = NULL /根无右子树-2分bt = bt-lchild;p-lchild = NULL;/此语句可不要freep;可编辑资料 - - - 欢迎下载elsewhilep-rchild .= NULL/p移至最右下结点q = p;p = p-rchild;ifp-lchild .= NULL/有左子树-5分q-rchild = p-lchild;elseq-rchild = NULL;/无左子树freep;/del_max3.Status Create_dgMgraph g1.Algraph &g2-1分/ 将数组表示的有向图g1 转换成邻接表表示的有向图g2g2.vexnum = g1.vexnum; g2.arcnum = g1.arcnum;-1分fori=0;ig1.vexnum;+i/生成 g2 的表头向量-3分g2.verticesi.data =