当前位置:首页 >> 其它课程 >> 2010-2011(2)数据结构B卷及答案

2010-2011(2)数据结构B卷及答案


安徽大学 2010—2011 学年第 2 学期
答 题 勿 超 装 订 线 ------------------------------装---------------------------------------------订----------------------------------------线------------------------------

----------

《 数据结构 》考试试卷(B 卷) (闭卷 时间 120 分钟) 考场登记表序号 题 号 得 分 阅卷人 一 二 三 四 五 六 七 总分

学号

一、填空题(每小题 1.5 分,共 15 分) 1.含有 36 个元素的有序表,进行二分查找时的判定树的深度为 6 2.在一个无向图中,所有顶点的度数之和等于所有边数的 2 。 倍。

得分

姓名

3. 由带权为 9、 2、 5、 7 的四个叶子结点构造一棵哈夫曼树, 该树的带权路径长度为 4.由 a,b,c 三个结点构成的二叉树,共有 5 种不同形态。

44



5.二维数组 A[0‥5][5‥10]以行序为主序存储,每个元素占 4 个存储单元,且 A[0][5]的 存储地址是 1000,则 A[3][9]的地址是 6.若串 s= ' soft ' ,则其子串个数是 11 1088 。 。

专业

7. 设循环队列的空间大小为 M,入队时修改队尾指针 rear 的语句为 rear=(rear+1)%M。 8.在顺序存储结构的线性表中,插入或删除一个数据元素大约需移动表中 一半 元素。 9.下列程序段的时间复杂度是 for (i=0;i<n;i++) for (j=0;j<m;j++) A[i][j]+=5; 10. 在数据结构中,与所使用的计算机无关的是数据的 二、单项选择题(每小题 2 分,共 20 分) 得分 1. 数据结构可以用二元组来表示,它包括( 集合 R。 A、数据元素 C、元素之间的关系 B、存储结构 D、逻辑结构 A )集合 D 和定义在 D 上的( C ) 逻辑 结构。 O(m*n) 。

院/系

年级

2. 已知 L 是一个不带头结点的单链表,p 指向其中的一个结点,选择合适的语句实现在
第 1 页 共 6 页

p 结点的后面插入一个结点 s 的操作( B A、p->next=s; s->next=p->next; B、s->next=p->next; p->next=s; C、p->next=s; s->next=p; D、s->next=p; p->next=s;

) 。

3. 假设以 I 和 O 分别表示入栈和出栈操作,栈的初态和终态均为空,入栈和出栈的操 作序列可表示为仅由 I 和 O 组成的序列。则下列序列( A、IOIIOIOO C、IIIOIOIO 4、空串和空格串是( B A、相同的 ) 。 B、不相同的 C、不能确定 B、IOOIOIIO D、OIIOIOIO A )是合法的。

5、设 W 为一个二维数组,其每个数据元素占用 6 个字节,行下标范围从 0 到 8,列下标 范围从 2 到 5,则二维数组 W 的数据元素共占用( A、480 B、192 C )个字节。 D、144

C、216

6、假设在一棵二叉树中,度为 2 的分支结点个数为 15,度为 1 的分支结点个数为 30,则 该二叉树的结点总数为( D ) 。 A、45 B、60 C、46 A ) 。 D、O(n+e) D、61

7. 对用邻接矩阵表示的图进行任一种遍历时,其时间复杂度为( A、O(n2) B、O(e) C、O(n) C ) 。

8. 对线性表进行折半查找时,要求线性表必须( A、以顺序方式存储

B、以链接方式存储

C、以顺序方式存储,且结点按关键字有序排列 D、以链接方式存储,且结点按关键字有序排列 9、 设散列表长 m=14,散列函数 H(key)=key%11。表中已有 4 个结点: addr(15)=4、addr(38)=5、addr(61)=6、addr(84)=7,其余地址为空,如用二次探测再散 列解决冲突,关键字为 49 的结点的散列地址是( A、8 B、3 C、5 D ) 。 D、9

10. 一组记录的排序码为(46,79,56,38,40,84) ,则利用堆排序的方法建立的初始 堆为( B )。
第 2 页 共 6 页

A、79,46,56,38,40,80 C、84,79,56,46,40,38
------------------------------装---------------------------------------------订----------------------------------------线----------------------------------------

B、84,79,56,38,40,46 D、84,56,79,40,46,38

三、判断题(在正确的题后括号内打?,错的则打×,每小题 1 分,共 8 分) 得分 1. 链表必须要设置一个头结点。 2. 堆排序、快速排序和希尔排序都是不稳定的排序方法。 3. 二叉树是度为 2 的有序树。 4. 循环队列是指用循环链表存储的队列。 5. 若入栈序列为 abcd,则出栈序列不可能为 cdab。 ( × ) ( ? ) ( × ) ( × ) ( ? )

6. 在拓扑排序过程中,如果图中已不存在无前驱的顶点了,而此时还有顶点没有输出,则 说明图中存在环。 7.平衡二叉树是指这样的二叉树:树中任一结点的左右子树深度都相同。 8 .在任何情况下,快速排序都是最快的。 四、简答题(每小题 10 分,共 40 分) 得分 1. 已知二叉树如图 1 所示,要求: (1) 将其转换为树,并画出该树; (2) 分别写出对(1)所得到的树进行先根遍历和后根遍历得到的结点序列。
A B C E H F I D G

( ?



线

( × ) ( × )













图 1 2.对如图 2 所示的连通图,试分别用普里姆(Prim)算法和克鲁斯卡尔(Kruskar)算法构造 其最小生成树,并给出其构造过程。

第 3 页

共 6 页

1 2 2 5 图 2 4
5

1 4

7 2 3
6 4

3

6

3

3.假定一个待散列存储的线性表为(32,75,29,63,48,94,25,36,18,70) ,散列 地址空间为 HT[0~12],若采用除留余数法构造散列函数 H(key)=key % 13 和线性探测法处 理冲突,试求出每个元素的散列地址,画出最后得到的散列表,并求出平均查找长度。 散列地址为: H(32)=32%13=6 H(63)=63%13=11 H(94)=94%13=3(冲突) H(75)=75%13=10 H(48)=48%13=9 H1=(3+1)%13=4
第 4 页 共 6 页

H(29)=29%13=3

H(25)=25%13=12 H(36)=36%13=10(冲突) H1=(10+1)%13=11(冲突)
------------------------------装---------------------------------------------订----------------------------------------线----------------------------------------

H2=(10+2)%13=12(冲突)

H3=(10+3)%13=0 H(18)=18%13=5 H(70)=70%13=5(冲突) 散列表为: 0 36 1 2 3 29 4 94 5 18 6 32 7 70 8 9 48 10 75 11 63 12 25 H1=(5+1)%13=6(冲突) H2=(5+2)%13=7

ASL=(7*1+1*2+1*3+1*4)/10=16/10=1.6 4.对一组记录(50,40,95,20,15,70,60,45,80)进行快速排序,请写出每一趟 排序结束时的序列。





线



初始序列: 第一趟结束后: 第二趟结束后: 第三趟结束后: 第四趟结束后:

50 {45 {20

40 40 40

95 15 15}

20 20} 45

15 50 50 50 50

70 {70 {60} 60

60 60 70 70

45 95 {95 80 80

80 80} 80} {95} 95







{15} 20 15 20

{40} 45 40 45

60 70

五、算法阅读题(第 1 小题 4 分,第 2 小题 3 分,共 7 分) 得分 1、画出执行下列程序段后得到的链表示意图。 L=(LinkList) malloc (sizeof(LNode); P=L; for ( k=1;k<=4;k++) { P->next=(LinkList) malloc (sizeof(LNode)); P=P->next; } P->next=NULL; P->data=2*k-1;

第 5 页

共 6 页

2、已知 q 是指向中序线索二叉树上某个结点的指针,请阅读下面函数,说明其功能。 BiTree InX( BiTree q) {

r=q->rchild; if( !q->rtag) while( !r->ltag) r=r->lchild; return r; }

六、算法设计(每小题 10 分,共 10 分)

得分

1、试设计算法,对带头结点的单链表实现就地逆置,即利用原单链表中的结点的存储单 元,将链表 L 逆置为:
L L a1 an a2 an-1 … … an a1 ^ ^

其中,单链表及结点定义如下: typedef struct LNode { ElemType data; struct LNode *next; }LNode,*LinkList;

第 6 页

共 6 页


更多相关文档:

2010-2011(2)数据结构B卷及答案

2010-2011(2)数据结构B卷及答案_其它课程_高中教育_教育专区 暂无评价|0人阅读|0次下载|举报文档2010-2011(2)数据结构B卷及答案_其它课程_高中教育_教育专区。...

2010-2011上期末试卷数据结构

教学班号: 云南农业大学 20102011 学年 上学期期末考试 数据结构(课程代码本...(A) 2i (B) 树型结构 (B)(B) 2i (C) 队列 (C) 2i-1 (C...

海南大学2010-2011数据结构B期末试卷

海南大学 2010-2011 学年度第 1 学期试卷 科目: 《数据结构》试题 B 姓名: ...201 年 月 日 得分 评卷人 一、 选择题(共 30 分,每小题 2 分) 1.在...

2010-2011第2学期《概率论与数理统计》B卷及答案

2010-20112学期《概率论与数理统计》B卷及答案_教育学_高等教育_教育专区。...4, DX ? 3 , 则 a,=--- b=---。 6. 设随机变量 X 的数学期望为 ...

2010-2011统计学参考答案(B卷)

2010-2011统计学参考答案(B卷)_管理学_高等教育_教育...2) 变异指标的主要作用: ①说明数据的离散程度,...2. (10 分)答: (1)结构相对指标、作用:①反映...

2010~2011数据结构高校试题B

十套数据结构试题及答案 40页 1下载券 数据结构考试题(浙江科技... 7页 2下载...浙江林学院 2010---2011 学年第一学期末考试卷(B) 学年第一学期末考试卷(...

南方学院2010-2011-1数据结构b

2011 学年第一学期五 六 总分 名 注意:请将正确答案写在答题纸上,答在试卷...B.希尔排序 C.归并排序 D.基数排序 2 三.填空题(20 分) : 1.数据结构...

编译原理2010-2011试卷---A(答案)

华东交通大学 20102011 学年第二学期考试卷试卷编号: ( A )卷 编译原理(E...2. 给定文法 G[S]:S→(A)│a│b A→AcS│S 请在下面的算符优先关系表...

2011数据结构 B卷

2011数据结构 B卷_工学_高等教育_教育专区。长课程名称: 数据结构 出卷教师:...请把你认为正确答案的题号,填入题干的括号内。 多选不给分。每题 2 分,共...

2010-2011-2C语言A卷答案

2010-2011-1《C 程序设计》A 卷答案 答题试卷 一、是非判断题(每小题 1 ...(每小题 2 分,共 20 分) 1 C 2 C 3 B 4 C 5 C 6 C 7 B 22 ...
更多相关标签:
2010 2011nba总决赛 | 2011考研英语答案 | 2011年7月n2答案 | 2011年12月n2答案 | 2011年国考行测答案 | 2011国考行测答案 | 2010 2011欧冠 | 2011年7月n1答案 |
网站地图

文档资料共享网 nexoncn.com copyright ©right 2010-2020。
文档资料共享网内容来自网络,如有侵犯请联系客服。email:zhit325@126.com