当前位置:首页 >> 院校资料 >> 数据结构试卷及答案

数据结构试卷及答案


模拟试卷一
一、 单选题(每题 2 分,共 20 分) 1. 以下数据结构中哪一个是线性结构?( ) A. 有向图 B. 队列 C. 线索二叉树 D. B 树 2. 在一个单链表 HL 中,若要在当前由指针 p 指向的结点后面插入一个由 q 指向的结点, 则执行如下( )语句序列。 A. p=q; p->next=q; B. p->next=q; q->

;next=p; C. p->next=q->next; p=q; D. q->next=p->next; p->next=q; 3. 以下哪一个不是队列的基本运算?( ) A. 在队列第 i 个元素之后插入一个元素 B. 从队头删除一个元素 C. 判断一个队列是否为空 D.读取队头元素的值 4. 字符 A、B、C 依次进入一个栈,按出栈的先后顺序组成不同的字符串,至多可以组成 ( )个不同的字符串? A.14 B.5 C.6 D.8 5. 由权值分别为 3,8,6,2 的叶子生成一棵哈夫曼树,它的带权路径长度为( )。 A. 11 B.35 C. 19 D. 53

图一 6. 该二叉树结点的前序遍历的序列为( A. E、G、F、A、C、D、B C. E、A、C、B、D、G、F 该二叉树结点的中序遍历的序列为( A. A、B、C、D、E、G、F C. E、A、C、B、D、G、F 该二叉树的按层遍历的序列为( A.E、G、F、A、C、D、B C. E、A、G、C、F、B、D )。 B. E、A、C、B、D、G、F D. E、G、A、C、D、F、B )。 B. E、A、G、C、F、B、D D. E、G、A、C、D、F、B )。 B. E、A、G、C、F、B、D D. B、D、C、A、F、G、E

7.

8.

9.

下面关于图的存储的叙述中正确的是( )。 A.用邻接表法存储图,占用的存储空间大小只与图中边数有关,而与结点个数无关 B.用邻接表法存储图,占用的存储空间大小与图中边数和结点个数都有关 C. 用邻接矩阵法存储图,占用的存储空间大小与图中结点个数和边数都有关 D.用邻接矩阵法存储图,占用的存储空间大小只与图中边数有关,而与结点个数无关 10. 设有关键码序列(q,g,m,z,a,n,p,x,h),下面哪一个序列是从上述序列出发建 堆的结果?( )

A. a,g,h,m,n,p,q,x,z B. a,g,m,h,q,n,p,x,z C. g,m,q,a,n,p,x,h,z D. h,g,m,p,a,n,q,x,z 二、 填空题(每空 1 分,共 26 分) 1. 数据的物理结构被分为_________、________、__________和___________四种。 2. 对于一个长度为 n 的顺序存储的线性表,在表头插入元素的时间复杂度为_________, 在表尾插入元素的时间复杂度为____________。 3. 向一个由 HS 指向的链栈中插入一个结点时 p 时, 需要执行的操作是________________; 删除一个结点时, 需要执行的操作是______________________________ (假设栈不空而 且无需回收被删除结点) 。 4. 对于一棵具有 n 个结点的二叉树,一个结点的编号为 i(1≤i≤n),若它有左孩子则左孩 子结点的编号为________,若它有右孩子,则右孩子结点的编号为________,若它有双 亲,则双亲结点的编号为________。 5. 当向一个大根堆插入一个具有最大值的元素时,需要逐层_________调整,直到被调整 到____________位置为止。 6. 以二分查找方法从长度为 10 的有序表中查找一个元素时,平均查找长度为________。 7. 表示图的三种常用的存储结构为_____________、____________和_______________。 8. 对于线性表(70,34,55,23,65,41,20)进行散列存储时,若选用 H(K)=K %7 作为散列函数,则散列地址为 0 的元素有________个,散列地址为 6 的有_______个。 9. 在归并排序中,进行每趟归并的时间复杂度为______,整个排序过程的时间复杂度为 ____________,空间复杂度为___________。 10. 在一棵 m 阶 B_树上, 每个非树根结点的关键字数目最少为________个, 最多为________ 个,其子树数目最少为________,最多为________。 三、 运算题(每题 6 分,共 24 分) 1. 写出下列中缀表达式的后缀形式: (1) 3X/(Y-2)+1 (2) 2+X*(Y+3) 2. 试对图 2 中的二叉树画出其: (1) 顺序存储表示的示意图; (2) 二叉链表存储表示的示意图。 3. 判断以下序列是否是小根堆? 如果不是, 将它调整 为小根堆。 图2 (1){ 12, 70, 33, 65, 24, 56, 48, 92, 86, 33 } (2){ 05, 23, 20, 28, 40, 38, 29, 61, 35, 76, 47, 100 } 4. 已知一个图的顶点集 V 和边集 E 分别为: V={1,2,3,4,5,6,7}; E={(1,2)3,(1,3)5,(1,4)8,(2,5)10,(2,3)6,(3,4)15,(3,5)12,(3,6)9,(4,6)4, (4,7)20,(5,6)18,(6,7)25}; 按照普里姆算法从顶点 1 出发得到最小生成树, 试写出在最小生成树中依次得到的各 条边。 四、 阅读算法(每题 7 分,共 14 分) 1. void AE(Stack& S){ InitStack(S); Push(S,3); Push(S,4); int x=Pop(S)+2*Pop(S); Push(S,x); int i,a[5]={1,5,8,12,15}; for(i=0;i<5;i++) Push(S,2*a[i]); while(!StackEmpty(S)) cout<<Pop(S)<<' '; } 该算法被调用后得到的输出结果为:

2.

void ABC (BTNode *BT,int &c1,int &c2) { if (BT !=NULL ) { ABC(BT->left,c1,c2); c1++; if (BT->left==NULL&&BT->right==NULL) c2++; ABC(BT->right,c1,c2); }//if }

该函数执行的功能是什么? 五、 算法填空(共 8 分) 向单链表的末尾添加一个元素的算法。 Void InsertRear(LNode*& HL,const ElemType& item) { LNode* newptr; newptr=new LNode; If (______________________) { cerr<<"Memory allocation failare!"<<endl; exit(1); } ________________________=item; newptr->next=NULL; if (HL==NULL) HL=__________________________; else{ LNode* P=HL; While (P->next!=NULL) ____________________; p->next=newptr; } } 六、 编写算法(共 8 分) 编写从类型为 List 的线性表 L 中将第 i 个元素删除的算法, (假定不需要对 i 的值进行 有效性检查,也不用判别 L 是否为空表。 ) void Delete(List& L, int i)

模拟试卷一参考答案
一、 单选题(每题 2 分,共 20 分) 1.B 2.D 3.A 4.B 5.B 6.C 7.A 8.C 9.B 10.B 二、 填空题(每空 1 分,共 26 分) 1. 顺序 链表 索引 散列 2. O(n) O(1) 3. p->next=HS;HS=p HS=HS->next 4. 2i 2i+1 ?i/2?(或 i/2) 5. 向上 根 6. 2.9 7. 邻接矩阵 邻接表 边集数组 8. 1 4 9. O(n) O(nlog2n) O(n) ? 10. ?m/2?-1 m-1 m/2? m 三、 运算题(每题 6 分,共 24 分) 1. (1) 3 X * Y 2 - / 1 + (2) 2 X Y 3 + * + 图3

2. (1) 0 1 2 1 3. 2

3 3

4 4

5

6 5

7 6

8

9 7

10

11

12

13 8

14

… …

18 9



31

(2)见图 3 所示: (1)不是小根堆。调整为:{12,24,33,65,34,56,48,92,86,70} (2)是小根堆。 4. 普里姆算法从顶点 1 出发得到最小生成树为: (1,2)3, (1,3)5, (1,4)8, (4,6)4, (2,5)10, (4,7)20 四、 阅读算法(每题 7 分,共 14 分) 1. 30 24 16 10 2 10 2. 该函数的功能是:统计出 BT 所指向的二叉树的结点总数和叶子总数 五、 算法填空(共 8 分,每一空 2 分) newptr==NULL newptr->=data newptr p=p->next 六、 编写算法(8 分) void Delete(List& L, int i) { for(int j=i-1;j<L.size-1; j++) L.list[j]=L.list[j+1]; //第 i 个元素的下标为 i-1 L.size--; }


更多相关文档:

数据结构期末考试题

8. 9. 中,所含边结点分别有___e___个和___2e__个。 7. AOV 网是一...a1。 Void contrary (Lnode * & HL) 数据结构试题(答案)一、单选题(每小题...

十套数据结构试题及答案

十套数据结构试题及答案_IT认证_资格考试/认证_教育专区 暂无评价|0人阅读|0次下载|举报文档十套数据结构试题及答案_IT认证_资格考试/认证_教育专区。数据结构...

《数据结构》期末考试试题及答案

数据结构》期末考试试题及答案 (2003-2004 学年第 2 学期) 贵州大学理学院数学系信息与计算科学专业 一、 单项选择题 1.对于一个算法,当输入非法数据时,也...

数据结构试题库集及答案

数据结构试题及答案 第一章 概论一、选择题 1、研究数据结构就是研究( D )。 A. 数据的逻辑结构 B. 数据的存储结构 C. 数据的逻辑结构和存储结构 D. ...

数据结构试题及答案

数据结构试题及答案_计算机软件及应用_IT/计算机_专业资料。数据结构试卷一、填空殖(每空 1 分共 20 分) 1. 数据的物理结构主要包括 ___ 顺序存储结构 ___...

数据结构试卷及答案

数据结构试卷及答案_教育学_高等教育_教育专区。《数据结构》期末考试一、单项选择题(请将正确答案的字母填写在每题对应的括号内,每小题1分,共20 分) 1、下面...

数据结构试题集(含答案)

数据结构试题集(含答案)_哲学_高等教育_教育专区。程序复杂性 3、具有线性结构的数据结构是( D )。 A. 图 B. 树 C. 广义表 D. 栈 4、计算机中的算法指...

数据结构试题库及答案

数据结构试题及答案 第一章 概论一、选择题 1、研究数据结构就是研究( D )。 A. 数据的逻辑结构 B. 数据的存储结构 C. 数据的逻辑结构和存储结构 D. ...

数据结构试卷及答案

数据结构试卷及答案_计算机软件及应用_IT/计算机_专业资料。《数据结构》试卷及答案 1.算法分析的目的是( C )。 B.研究算法中输入和输出的关系 D.分析算法的易...

数据结构试题集(包含答案_完整版)

数据结构试题集(包含答案_完整版)_理学_高等教育_教育专区。第一章 概论 一、...数据复杂性和程序复杂性 3、具有线性结构的数据结构是( D )。 A. 图 B. ...
更多相关标签:
网站地图

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