当前位置:首页 >> 学科竞赛 >>

06-07数据结构试题A答案


系主任 审批并签名

教研室主任 审批并签名

刘顺海

A卷

拟题 人

刘顺海

学年考试卷(答案) 广州大学松田学院 2006 ~ 2007 学年考试卷(答案)
课程: 数据结构 考试形式(闭卷 闭卷) 闭卷 姓名:
五 30 六 七

总分 100

专业: 计算机科学与技术 准考证号:
题次 分数 评卷人 一, 填空题( 填空题(每空 1 分,共计 16 分) 一 16 二 10 三 14 四 30

装 订 线 (此 线 外 不 能 答 题 )

1. 数据(Data)是人们利用文字符号,数字符号以及其他规定的符号对现实世界 的事物及其活动的抽象描述. 2. 下面程序段的时间复杂度是_ O( n*m)__. For(i=0;i<n;i++) For(j=0;j<m;j++) A[i][j]=0; 3. 在一个循环顺序队列 Q 中,判断队空的条件为 件为 (rear+1)%QueueMaxSize==front . front==rear ,判断队满的条

4. 若已知一棵二叉树的深度为 k(k≥1),则这棵树至多有 2k-1 个结点,这棵 i-1 树的第 i (1≤i≤k)层上至多有 2 个结点,若这是一棵具有 n 结点的完全 二叉树,则 k 与 n 的关系为 k=└log2n┘+1 . 5. 中缀算术表达式 3+4/(25-(6+15))*8 所对应的波兰算术表达式 为_____3 4 25 6 15 +-/8*+_____. 6. 一个有向图中有 1000 个顶点,1000 条边,则形成的邻接矩阵有 1000 个非 零元素,因此是 稀疏矩阵 . 7. 每次从待排序的区间中选择出具有最小排序码的元素, 把该元素与该区间的第 一个元素交换位置,此种排序方法叫做__直接选择______排序;使两个有序表 合并成一个有序表的排序方法叫做_二路归并_______排序. 8. 对于下图 1,请写出其一种拓扑序列的结果: _________0,1,2,3,4,5,6,7,8,9______________.

1

图1 9. 向 线 性 表 中 满 足 条 件 的 位 插 入 一 个 元 素 是 void Insert(List&L,const Elimtype&item) .在下面的程序段中,假定线性表 La 的类型为 List,元素类 型 ElemType 为 int,并假定每个程序段是连续执行的,则程序段执行后所得到 的线性表 La 为: . 26,34,48,57,62,79 InitList(La); int a[]={48,26,57,34,62,79}; for(i=0; i<6; i++) Insert(La,a[i]); TraverseList(La); 10. 假定一组记录的排码为 (46,79,56,38,40,84),则利用堆排序方法建立的初始 堆为 (84,79,56,38,40,46) .

二,

选择题(在每小题的四个备选答案中,选出一个正确的答案, 选择题(在每小题的四个备选答案中,选出一个正确的答案,并将其代码填入 题干后的括号内 括号内. 题干后的括号内.每小题 1 分,共计 10 分) 一个数组元素 a[i]的另一种等价表示方式为 A *(a+i) B a+i C *a+i ( A ) D &a+I

1.

2.

链栈与顺序栈相比,有一个较明显的优点是 ( A ) A 通常不会出现栈满的情况 B 通常不会出现栈空的情况 C 插入操作更加方便 D 删除操作更加方便

3. 若查找表中的记录按关键字的大小顺序存放在一个一维数组中,用二分法(折 半法)查找的平均搜索长度为 ( B ) 2 A 0(n) B 0(log2n) C 0(nlog2n) D 0((log2n) ) 4. 在一个单链表 HL 中,若要向表头插入一个由指针 p 指向的结点,则执行(B) A. HL = p; p->next = HL; B. p->next = HL; HL = p;

2

C. p->next = HL; p = HL; D. p->next = HL->next; HL->next = p; 5. 下列广义表中是线性表的只有 A. E(a,(b,c)) B. E(a, E) ( C ) C. E(a,b)

D. E(a, L())

6. 设线性链表中结点的结构为(data,link).已知指针 p 所指结点不是尾结点,若 在 p 指针指向的结点之后插入 s 指针指向的结点,则应执行以下哪个操作 ( C ) A s->link:=p; p->link:=s B s->link:=p->link; p:=s; C s->link:=p->link; p->link:=s; D p->link:=s; s->link:=p; 7. 设图中有 n 个顶点和 e 条边,进行深度优先搜索遍历的时间复杂度至多为 ( A ) . A. O(n + e ) B. O(n*e) C. O(nlog2 n) D. (elog2 e) 8. 采用折半查找方法进行查找,数据文件应为且限于( A ) . A. 有序表 顺序存储结构 B. 有序表 链式存储结构 C. 随机表 顺序存储结构 D. 随机表 链式存储结构

9. 若已知一棵二叉树先序序列为 ABCDEFG,中序序列为 CBDAEGF,则其后序序列为 ( A ) . A CDBGFEA B CDBFGEA C CDBAGFE D BCDAGFE 10. 对于含有 n 个顶点和 e 条边的无向连通图, 利用普里姆(Prim)算法产生最小生 成树,其时间复杂度为 ( D ) . 2 A. O(n ) B. O(n*e) C. O(nlog2 n) D. (elog2 e)

三,

判断题(下列各题,你认为正确的,请在前面的括号内打√ 错误 错误的打 判断题(下列各题,你认为正确的,请在前面的括号内打√ ,错误的打 X . 每小题 2 分,共计 14 分)

1. ( × )在单链表中,要取得某个元素,只要知道该元素指针即可,因此单链 表是随机存储结构. 2. ( √ )线性表若采用链式存储表示时所有存储单元的地址可连续可不连续. 3. ( × )删除二叉排序树中一个结点,再重新插入上去,一定能得到原来的二 叉排序树. 4. ( √ )任一 AOV 网中至少有一条关键路径,且是从源点到汇点的路径中 最长的一条.

3

5. ( √ )在索引顺序表上实现分块查找(Blocking Search 属于索引查找), 在等概率查找情况下, 其平均查找长度不仅与表的个数有关,而且与每一块中 的元素个数有关. 6. ( × )图 G 由两个集合 V(G)和 E(G)所组成,其中顶点集 V(G)能为空 集, 而边集 E(G)不能为空. 7. ( × )只有在初始数据为逆序,冒泡排序所执行的比较次数最多.

四,

综合题( 综合题(每小题 6 分,共计 30 分)

1. 有一组关键码序列{23,20,30,15,17,45,18},画图给出建堆过程的每个 步骤.

1.

初始 23

第一步 23

20

30

20

18

15

17

45

18

15

17

45

30

第二步

23

第三步

15

15

18

17

18

20

17

45

30

20

23

45

30

4

2. 列出右图所示二叉树的叶结点, 分支结点和每个结点的层次. (根结点的层次为 0)

【解答】 二叉树的叶结点有⑥,⑧,⑨. 分支结点有①,②,③,④,⑤,⑦. 结点①的层次为 0;结点②,③的层次为 1; 结点④,⑤,⑥的层次为 2;结点⑦,⑧的层次为 3; 结点⑨的层次为 4.

3.

设有序顺序表中的元素依次为 017, 094, 154, 170, 275, 503, 509, 512, 553, 612, 677, 765, 897, 908.试画出对其进行折半查找时的二叉排序树, 并计算搜索成 功的平均搜索长度和搜索不成功的平均搜索长度. 【解答】

509 154 017 094 170 275 503 512 553 612 765 677 897 908

ASL succ =

1 14 1 45 ∑ C i = 14 (1 + 2 * 2 + 3 * 4 + 4 * 7) = 14 14 i =1
= 1 15
15

ASL

unsucc

∑C
i=0

' i

=

1 59 (3 * 1 + 4 * 14) = 15 15

5

4.

画出 1 个顶点,2 个顶点,3 个顶点,4 个顶点和 5 个顶点的无向完全图.试 证明在 n 个顶点的无向完全图中,边的条数为 n(n-1)/2.

【解答】

1 个顶点的 无向完全图

2 个顶点的 无向完全图

3 个顶点的 无向完全图

4 个顶点的 无向完全图

5 个顶点的 无向完全图

【证明】 在有 n 个顶点的无向完全图中,每一个顶点都有一条边与其它某一顶点相连,所以 每一个顶点有 n-1 条边与其他 n-1 个顶点相连,总计 n 个顶点有 n(n-1)条边.但在无向 图中,顶点 i 到顶点 j 与顶点 j 到顶点 i 是同一条边,所以总共有 n(n-1)/2 条边.

5. 在操作序列 push(1),push(2),pop,push(5),push(7),pop,push(6)之后, 栈顶元素和栈底元素分别是什么?并画出执行过程. (push(k)表示整数 k 入 栈,pop 表示栈顶元素出栈)

【解答】栈顶元素为 6,栈底元素为 1.其执行过程如下所示: 入栈 出栈

7 2 1 (a)push(1),push(2) 5 1 (b)pop,push(5),push(7)

6 5 1 (c)pop,push(6)

6

五, 1.

算法设计题( 算法设计题(共计 30 分) 设计一个算法,从线性表中删除表头元素.下面已经给出程序的大体内容,请 完善之. (其中有 4 个空缺,每空 3 分,共 12 分)

Elemtype DeleteFront(List& L) { if( L.size==0 ) { cerr<<"Deleting from an empty list!"<<endl; exit(1); } Elemtype temp=L.list[0]; For(int i=1;i<L.size; i++) Lilst[i-1]=L.list[i]; L.size--; Return temp; } 设有一个表头指针为 h 的单链表.试设计一个算法,通过遍历一趟链表,将链 表中所有结点的链接方向逆转,如下图所示.要求逆转结果链表的表头指针 h 指向原链表的最后一个结点. (其中有 4 个空缺,每空 3 分,共 12 分)

2.

template<class Type> void List<Type> :: Inverse ( ) { if ( first == NULL ) return; ListNode<Type> *p = first->link, *pr = NULL; while ( p != NULL ) { first->link = pr; pr = first; first = p; p = p->link;
7

//逆转 first 指针

//指针前移

} first->link = pr; }

3.

若用二叉链表作为二叉树的存储表示, 试以二叉树为参数, 交换每个结点的左 子女和右子女问题,编写递归算法: (其中有 3 个空缺,每空 2 分,共 6 分)

void BinaryTree<Type> :: exchange ( BinTreeNode<Type> * ptr ) { BinTreeNode<Type> * temp; if ( ptr->leftChild != NULL || ptr->rightChild != NULL ) { temp = ptr->leftChild; ptr->leftChild = ptr->rightChild; ptr->rightChild = temp; exchange ( ptr->leftChild ); exchange ( ptr->rightChild ); } }

8

相关文章:
06-07-数据结构试卷-A+答案
06-07-数据结构试卷-A+答案_理学_高等教育_教育专区。北京师范大学 2006~2007 学年第 1 学期期末考试试卷(A 卷)课程名称:卷面总分: 100 分院(系) : 数学...
06-07数据结构试题A答案
06-07数据结构试题A答案 111111隐藏>> 系主任 审批并签名 教研室主任 审批并签名 刘顺海 A卷 拟题 人 刘顺海 学年考试卷(答案) 广州大学松田学院 2006 ~ ...
06-07数据结构与算法A卷参考答案
06-07数据结构与算法A卷参考答案 隐藏>> 江西财经大学 06-07 第一学期 期末考试参考答案与评分标准试卷代码:03266A 课程名称:数据结构与算法 一、单项选择题(每...
数据结构试题及答案
数据结构试题及答案_其它课程_高中教育_教育专区。数据结构试卷(一)... 1 数据...设某数据结构的二元组形式表示为 A=(D,R),D={01,02,03,04,05,06,07,...
06级数据结构A试卷答案及评分标准
安徽大学 20 07 —20 08 学年第 2 学期 《数据结构考试试题 A 卷参考答案及评分标准一 单项选择(每题 1 分,共 20 分) 1C 2B 3D 4D 5C 6A 7C 8...
2007《数据结构》期末试卷_A_答案
2007数据结构》期末试卷_A_答案_哲学_高等教育_教育专区。厦门大学《_数据...文档贡献者 双鱼hongse 贡献于2016-06-06 1/2 相关文档推荐 《数据库管理系统...
07-08-数据结构试卷-A卷+答案
北京师范大学 2007~2008 学年第 1 学期期末考试试卷(A 卷)标准答案课程名称:卷面总分: 100 分院(系) :姓名: 数据结构考试时长: 任课教师姓名:分钟 专业: ...
安大2006-2007第1学期数据结构与算法试卷(A卷)
重庆邮电大学 20 0620 07 学年第 1 学期 《 数据结构与算法 》考试试卷(A 卷)得分 一、选择题(每小题 1.5 分,共 15 分) 1、某双向链表中的结点如...
数据结构试题及答案
数据结构试题及答案_计算机软件及应用_IT/计算机_专业资料。数据结构试卷一、填空...设某数据结构的二元组形式表示为 A=(D,R),D={01,02,03,04,05,06,07,...
06-07数据结构与算法A卷
江西财经大学 06-07 第一学期期末考试试卷试卷代码:03266A 课程名称:数据结构与算法 授课课时:112 适用对象:本科 一、单项选择题(从下列各题四个备选答案中选出...
更多相关标签:
结构化面试试题及答案 | 结构力学试题及答案 | 数据结构试题及答案 | 数据结构面试题及答案 | 建筑结构试题及答案 | 砌体结构试题及答案 | 数据结构试题库及答案 | 结构动力学试题及答案 |