当前位置:首页 >> 其它课程 >> 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)A卷

A卷中国石油大学(北京)20102011 学年 第 2 学期 《数据结构》期末考试试卷...165432 )。 7、广义表 A=(a, b, (c, d), (e, (f, g))),则...

数据库原理试卷(2010-2011 2 B)

数据库原理试卷(2010-2011 2 B) 安工2010-2011年期末试题安工2010-2011年期末...按数据结构的组织形式, 数据库可以分为层次数据库、 网状数据库和 2、数据模型...

北京交通大学研究生2010-2011数据结构与算法题及答案

北京交通大学考试试题 课程名称: 数据结构与算法 2010-2011 学年第二学期 出题教师:张勇 (请考生注意:(1)本试卷共有五道大题, (2)答案一律写在答题纸上, (...

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

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

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

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

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

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

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

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

2010-2011-2《计算机组成原理》B卷答案

201 2011 学年第二 洛阳师范学院 20102011 学年第二学期 期末考试计算机组成原理》课程( ) 网络工程 专业 2008 级《计算机组成原理》课程(B)卷 参考答案及...

2010-2011高数A-2试题B卷-答案

广西师范学院课程评分细则(20102011 学年度第二学期) 《 高等数学 A—2 》 课程 (A 考核形式: 考核时间: /B 闭卷 √ 卷) 考核年级、专业、 班级: 命题...

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 ...
更多相关标签:
2011 新 2010 | 砌体结构设计规范2011 | 2010 2011欧冠 | 2010 2011nba总决赛 | 产业结构调整目录2011 | 2011国考行测答案 | 2011山东高考英语答案 | 2011考研英语答案 |
网站地图

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