安徽大学数据结构试卷A

1、院/系 年级 专业 姓名 学号 答 题 勿 超 装 订 线-装-订-线-安徽大学20 09 20 10学年第 2 学期 数据结构 考试试卷（A卷）（闭卷 时间120分钟）题 号一二三四五六七总分得 分阅卷人得分一、填空题（每空1分，共15分）1、在线性结构中，第一个结点 前驱结点，其余每个结点有且只有 个前驱结点；最后一个结点 后续结点，其余每个结点有且只有 个后续结点。2、下面程序段的时间复杂度是 。for (i=0;i<n;i+) for (j=0;j<m;j+) Aij=0;3、在具有n个单元的循环队列中，队满时共有 个元素。4、假定一棵二叉树的结点数为18，则它的最小深度为

2、 ，最大深度为 。5、在一个单链表中p所指结点之后插入一个s所指结点时，应执行下面的操作：snext=_ _;pnext=_;6、从有序表(12，18，30，43，56，78，82，95)中依次二分查找43和56元素时，其查找长度分别为 和 。7、.一棵二叉树有67个结点，这些结点的度要么是0，要么是2。这棵二叉树中度为2的结点有_个。8、在堆排序和快速排序中，若原始记录接近正序或反序，则选用_。9、若采用邻接表的存储结构，则图的广度优先搜索类似于二叉树的_遍历。得分二、单向选择题（每小题1.5分，共15分）1、n个顶点的强连通图中至少含有( )。A、nl条有向边 B、n条有向边C、n(n1)

3、2条有向边 D、n(n一1)条有向边2、在一个不带头结点的单链表HL中，若要向表头插入一个由指针p指向的结点，执行( )。A、 HLp; p一>nextHL; B、 p一>nextHL；HLp;C、 p一>nextHL; pHL; D、 p一>nextHL一>next; HL一>nextp;3、采用线性链表表示一个向量时，要求占用的存储空间地址（ ）。A: 必须是连续的 B 部分地址必须是连续的C: 一定是不连续的 D: 可连续可不连续4、如果想在4092个数据中只需要选择其中最小的5个，采用（ ）方法最好。A: 起泡排序 B: 堆排序 C: 锦标赛排序 D

4、: 快速排序5、在循环队列中用数组A0.m-1 存放队列元素，其队头和队尾指针分别为front和rear，则当前队列中的元素个数是（ ）。 A: ( front - rear + 1) % m B: ( rear - front + 1) % mC: ( front - rear + m) % m D: ( rear - front + m) % m6、数组A0.5,0.6的每个元素占五个字节，将其按列优先次序存储在起始地址为1000的内存单元中，则元素A5，5的地址是(      )。A: 1175   

5、0;        B: 1180            C: 1205            D: 12107、已知广义表LS(a,b,c),(d,e,f),运用head和tail函数取出LS中原子e的运算是(     )A: head(tail(LS) &

6、#160;                    B: tail(head(LS)C: head(tail(head(tail(LS)           D: head(tail(tail(head(LS)8、某二叉树的前序遍历结点访问顺序是abdgcefh,中序遍历的结点访问顺序是dgbaechf,则其后

7、序遍历的结点访问顺序是（ ）。A: bdgcefha B: gdbecfha C: bdgaechf D: gdbehfca 9、在一个无向图中,所有顶点的度数之和等于所有边数的（ ）倍。 A: 1/2 B: 1 C: 2D:410、设串s1=ABCDEFG，s2=PQRST，函数con (x,y)返回x和y串的连接串，subs(s,i,j)返回串s的从序号i的字符开始的j个字符组成的子串，len(s)返回串s的长度，则con (subs (s1,2,len (s2), subs (s1,len (s2),2)的结果串是（ ）。A： BCDEF B： BCDEFGC：BCPQRST D：BCD

8、EFEF得分 三、应用题（每小题8分，共32分）1 一棵深度为h的满m叉树具有如下性质:第h层上的结点都是叶结点,其余各层上每个结点都有m棵非空子树。若按层次从上到下,每层从左到右的顺序从1开始对全部结点编号,试计算:(1)第k层结点数(1kh)。(2)整棵树结点数。(3)编号为i的结点的双亲结点的编号。(4)编号为i的结点的第j个孩子结点(若有)的编号。 答 题 勿 超 装 订 线-装-订-线-2已知图G的邻接表如图1所示，请写出：（1）其从顶点v1出发的深度有限搜索序列；（2）其从顶点v1出发的广度优先搜索序列。v1v2v3v4 v5v6 V2V5V4 v3V5 V4V6V3 V6 图1

9、图G的邻接表3、 以关键码序列（503,087,512,061,908,170,897,275,653,426），为例，手工执行快速排序排序算法，写出每一趟排序结束时的关键码状态： 答 题 勿 超 装 订 线-装-订-线-4使用哈希函数H(key)=key % 11，把一个整数值转换成哈希表下标，现要把数据1、13、12、34、38、33、27、22插入到哈希表（表1）中。（1）使用线性探测再散列法构造哈希表，请在表1所示的哈希表中与哈希地址对应的位置上，填写出相应的关键字值和元素插入时的探查次数。（2）假设查找每个元素的概率相同，求出查找成功时的平均查找长度。表1哈希地址0123456789

10、10关键字值探查次数得分四、算法阅读题（每小题9分，共18分）1、完成二叉树按层遍历的算法。void leveltravel ( struct treenode *bt) struct treenode *p,*an; int rear=front = -1; p=bt; rear =_; arear=p; while (rear != front) front = _; p=afront; printf(“%c”,p->data);If ( p->left !=null) rear =(rear +1)% n arear= _; If (p->right!= null) r

11、ear = (rear +1)%n ; arear=_; 2、下面算法是对直接插入排序算法的改进，请填写完整void weizhisort(struct node r n+1,int n) int low,high,mid,j,i; for(i=2;i<=n;i+) r0=ri; low=_; high=_; while(low<=high) mid=(low+high)/2; if(r0.key<rmid.key) _; else low=mid+1; for(j=i-1;j>=low;j-) rj+1=rj; rlow=r0; 五、算法设计题（每小题10分，共20分）1、 已知二叉树中的结点类型BinTreeNode定义为：struct BinTreeNodeElemType data；BinTreeNode *left，*right；其中data为结点值域，left和right分别为指向左、右子女结点的指针域。请写一函数，功能