fccjxxw.com
非常超级学习网 学习超级帮手
当前位置:首页 >> 数学 >>

数据结构试卷及答案


…….……………………….密…………………封…………………线…………………………

期末考试《数据结构》A 卷
注意事项: 题号 得分 得分 评卷人 一、单项选择题(请将正确答案的字母填写在每 题对应的括号内,每小题 1 分,共 20 分) 一 二 三 四 总分 核分人

1、下面关于串的叙述中,哪一个是不正确的?( ) A.串是字符的有限序列 B.空串是由空格构成的串 C.模式匹配是串的一种重要运算 D.串既可以采用顺序存储,也可以采用链式存储 2、设无向图的顶点个数为n,则该图最多有( )条边。 A.n-1 B.n(n-1)/2 C. n(n+1)/2 D.0 3、以下数据结构中, ( )是非线性数据结构。 A.树 B.字符串 C.队列 D.栈 4、下面关于线性表的叙述中,错误的是哪一个?( ) A.线性表采用顺序存储,必须占用一片连续的存储单元。 B.线性表采用顺序存储,便于进行插入和删除操作。 C.线性表采用链接存储,不必占用一片连续的存储单元。 D.线性表采用链接存储,便于插入和删除操作。 5、假设以数组A[m]存放循环队列的元素,其头尾指针分别为front和rear,则当前队列 中的元素个数为( ) 。 A.(rear-front+m)%m B.rear-front+1 C.(front-rear+m)%m D.(rear-front)%m 6、在单链表指针为p的结点之后插入指针为s的结点,正确的操作是( ) 。 A.p->next=s; s->next=p->next; B.s->next=p->next; p->next=s; C.p->next=s; p->next=s->next; D.p->next=s->next; p->next=s; 7、设栈的输入序列是1,2,3,4,则( )不可能是其出栈序列。 A.1,2,4,3 B.2,1,3,4 C.1,4,3,2 D.4,3,1,2, 8、广义表(a,(b,c),d,e)的表头和表尾分别为( ) 。 A.a和(b,c),d,e B. (a)和(b,c),d,e C.a 和 ((b,c),d,e) D.(a) 和((b,c),d,e)
本试卷共 6 页第 1 页

9、栈和队都是( ) A.顺序存储的线性结构 B.链式存储的非线性结构 C.限制存取点的线性结构 D.限制存取点的非线性结构 10、从逻辑上可以把数据结构分为( )两大类。 A.动态结构、静态结构 B.顺序结构、链式结构 C.线性结构、非线性结构 D.初等结构、构造型结构 11、下列四个序列中,哪一个是堆( ) 。 A.75,65,30,15,25,45,20,10 B.75,65,45,10,30,25,20,15 C.75,45,65,30,15,25,20,10 D.75,45,65,10,25,30,20,15 12、在下述结论中,正确的是( ) ①只有一个结点的二叉树的度为0; ②二叉树的度为2; ③二叉树的左右子树可任意交换; ④深度为K的完全二叉树结点个数小于或等于深度相同的满二叉树。 A.①②③ B.②③④ C.②④ D.①④ 13、 若一棵二叉树具有10个度为2的结点, 5个度为1的结点, 则度为0的结点个数是 ( ) A.9 B.11 C.15 D.不确定 14、设森林F中有三棵树,第一,第二,第三棵树的结点个数分别为M1,M2和M3。 与森林F对应的二叉树根结点的右子树上的结点个数是( ) 。 A.M1 B.M1+M2 C.M3 D.M2+M3 15、在下面的程序段中,对x的赋值语句的频度为( ) 。 FOR i:=1 TO n DO FOR j:=1 TO n DO x:=x+1; A. O(2n) B.O(n) C.O(n2) D.O(log2n) 16、一个n个顶点的连通无向图,其边的个数至少为( ) 。 A.n-1 B .n C.n+1 D.nlogn; 17、二叉树的第I层上最多含有结点数为( ) A.2I B. 2I-1-1 C. 2I-1 D.2I -1 18、 下列排序算法中( )排序在一趟结束后不一定能选出一个元素放在其最终位置上。 A.选择 B.冒泡 C.归并 D.堆 19、二维数组A的元素都是6个字符组成的串,行下标i的范围从0到8,列下标j的范围 从1到10。若A按行存放,元素A[8,5]的起始地址与A按列存放时的元素( ) 的起始地址一致。 A.A[8,5] B. A[3,10] C. A[5,8] D. A[0,9] 20、散列文件使用散列函数将记录的关键字值计算转化为记录的存放地址,因为散列 函数是一对一的关系,则选择好的( )方法是散列文件的关键。 A.散列函数 B.除余法中的质数 C.冲突处理 D.散列函数和冲突处理
本试卷共 6 页第 2 页

姓名:________ 学号:__________ 年级:______________ 专业:_____________

得分

评卷人

二、判断题,在正确的题后括号内打“√” ,在错误的题后 括号内打“×” (每小题 1 分,共 10 分) )

西哥(M),下表给定了这六大城市之间的交通里程: 世界六大城市交通里程表(单位:百公里) Pe Pe N Pa L T M 109 82 81 21 124 58 55 108 32 3 97 92 95 89 113 N 109 Pa 82 58 L 81 55 3 T 21 108 97 95 M 124 32 92 89 113

…….……………………….密…………………封…………………线…………………………

姓名:________ 学号:__________ 年级:______________ 专业:_____________

1、算法是由若干条指令组成的有穷序列,而一个程序不一定满足有穷性。 ( 2、顺序存储方式只能用于存储线性结构。( ) 3、对任何数据结构链式存储结构一定优于顺序存储结构。( ) 4、有向图的邻接矩阵是对称矩阵,无向图的邻接矩阵是非对称矩阵。 ( ) 5、所有二叉树的度均为 2。 ( ) 6、满二叉树一定是完全二叉树,但完全二叉树不一定是满二叉树。 ( ) 7、循环链表不是线性表。 ( ) 8、文件是记录的集合,文件上的操作主要有两类:检索和维护。 ( ) 9、线性表的特点是每个元素都有一个前驱和一个后继。( ) 10、按中序遍历二叉排序树所得到中序序列是一个递增有序序列。 ( ) 得分 评卷人 三、应用题(第 1、4、6 题每题 10 分,第 2、3 题每题 8 分,第 5 题 9 分,共 55 分) B,D ),( A,B ),(

(1)画出这六大城市的交通网络图; (2)画出该交通网络图按权值递增的顺序来构造的最小(代价)生成树。

1、已知一棵树边的集合为: {( I , M ),( I ,N ),( E, I ),( B,E ),( J ),( G,K ),( C,G ),( C,F ),(H,L ),( C,H ),( A,C )} 用树形表示法画出此树,并回答下列问题: (1)哪个是此树的根结点?哪些是叶子结点? (2)树的度数和树的深度是多少? (3)写出结点 G 的双亲、祖先、孩子? (4)写出结点 E 的子孙、兄弟和结点 E 所在的层次?

G,

4、假设用于通信的电文由字符集{a,b,c,d,e,f,g,h}中的字母构成。它们在电文中 出现的频度分别为{7,19,2,6,32,3,21,10}。要求: (1) 请为这 8 个字母设计哈夫曼编码,并画出对应的哈夫曼树; (2)计算该哈夫曼树的最小加权路径长度 WPL。

2 、 已 知 一 棵 二 叉 树 的 中 序 遍 历 序 列 和 后 序 遍 历 序 列 分 别 为 EBIFJAGDH 和 EIJFBGHDA。要求: (1)画出这棵二叉树; (2)写出这棵二叉树的前序遍历序列。

3、已知世界六大城市为:北京(Pe)、纽约(N)、巴黎(Pa)、 伦敦(L) 、 东京(T) 、 墨
本试卷共 6 页第 3 页

5、对给定的一组关键字:49,38,65,97,76,13,27,49,55,4
本试卷共 6 页第 4 页

分别写出希尔排序(增量为 5,3,1) 、起泡排序和归并排序的前 3 趟排序结果。

得分

评卷人 四、算法设计题(第 1 题 7 分,第 2 题 8 分,共 15 分)

…….……………………….密…………………封…………………线…………………………

姓名:________ 学号:__________ 年级:______________ 专业:_____________

1、 已知带头结点的动态单链表 L 中的结点是按整数值递增排列, 试写一算法将值为 X 的结点插入链表 L 中,使 L 仍然有序。单链表的描述如下: typedef int datatype; typedef struct node { datatype data; struct node *next; }linklist;

6、设散列表长度为 13,即其地址空间为 0-12,散列函数 H(k)=K mod 13,对关键字序 列{19,14,23,01,68,20,84,27,55,11,10,79}。要求: (1)画出用线性探查法解决冲突时构造的散列表(哈希表) 。 (2)设每个记录的查找概率相等,计算查找成功的平均查找长度(ASLsucc)以及查 找不成功的平均查找长度(ASLunsucc)。 2、试写出递归的二分查找(折半查找)算法。

本试卷共 6 页第 5 页

本试卷共 6 页第 6 页

黄淮学院 2006 —2007 年第二学期 计科系《 数据结构》 期末试卷(A)评分标准及标准答案
一、选择题,共 20 个小题,每小题 1 分,共 20 分;本题为单项选择题,多选或错选均不能 得分。 标准答案如下: 题号 答案 1 B 2 B 3 A 4 B 5 A 6 B 7 D 8 C 9 C 10 C 11 C 12 D 13 B 14 D 15 C 16 A 17 C 18 C 19 B 20 D

二、判断题(在正确的题后括号内打“√” ,在错误的题后括号内打“×” ,共 10 个小题, 每小题 1 分,共 10 分) 。 标准答案如下: 题号 答案 1 2 3 4 5 6 7 8 9 10



×

×

×

×



×



×



三、应用题(共计 55 分) 1、………………………………………………………………………………..10 分 (1)根结点为 A 叶子结点为:D,F,J,K,L,M,N (2)树的度为 3;树的深度为 5。 (3)结点 G 的双亲为 C 结点 G 祖先为 C,A 结点 G 孩子为 J,K (4)结点 E 的子孙为 I,M,N 结点 E 的兄弟为 D 结点 E 所在的层次为 3。 2、……………………………………………………………………..8 分 (1)该二叉树为: A B E I F G J D H (2)该二叉树前序序列:

ABE F IJ D G H

3、…………………………………………………………………..8 分 (1)六大城市的交通网络图

4

Pe

21 97

T

82 81 109 124

113

Pa
58 3 89 95

92
108 32

M

L 55

N

(2)最小生成树 6 个顶点和 5 条边的集合如下: V(G)={Pe,N,Pa,L,T,M} E(G)={(L,Pa,3),(Pe,T,21),(M,N,32),(L,N,55),(L,Pe,81)} 4、………………………………………………………………………………..10 分 (1)对应的哈夫曼树
100

40

60

19

21

28

32

11

17

5

6

7

10

2

3

这 8 个字母 a,b,c,d,e,f,g,h 的哈夫曼编码分别为: 1010 ,00 ,10000 ,1001 ,11 ,10001 ,01 ,1011 (2)其最小的加权路径长度: WPL=19*2+21*2+32*2+6*4+7*4+10*4+2*5+3*5=38+42+64+24+28+40+10+15=261

5

5、………………………………………………………………………………..9 分 希尔排序(增量为 5,2,1)的前 3 趟排序结果: 第 1 趟结果:13 27 49 55 4 49 38 65 97 76 第 2 趟结果:4 27 13 49 38 55 49 65 97 76 第 3 趟结果:4 13 27 38 49 49 55 65 76 97 起泡排序的前 3 趟排序结果: 第 1 趟结果:4 49 38 65 97 76 13 27 49 55 第 2 趟结果:4 13 49 38 65 97 76 27 49 55 第 3 趟结果:4 13 27 49 38 65 97 76 49 55 归并排序(二路归并)的前 3 趟排序结果: 第 1 趟结果:38 49 65 97 13 76 27 49 4 55 第 2 趟结果:38 49 65 97 13 27 49 76 4 55 第 3 趟结果:13 27 38 49 49 65 76 97 4 55 6、………………………………………………………………………………..10 分 (1)用线性探查法解决冲突时所构造的散列表: 散列地址 关键字 比较次数 0 1 14 1 2 1 2 3 68 1 4 27 4 5 55 3 6 19 1 7 20 1 8 84 3 9 79 9 10 23 1 11 11 1 12 10 3

(2) 在等概率情况下, 这种方法的查找成功及查找不成功的平均查找长度 (ASL) 分别为: ASLsucc=1+2+1+4+3+1+1+3+9+1+1+3)/12=30/12=5/2=2.5 ASLunsucc=(1+13+12+11+10+9+8+7+6+5+4+3+2)/13=7 四、算法设计(第 1 题 7 分,第 2 题 8 分,共计 15 分) 1、linklist * insert(linklist *h,datatype x) /*h 是递增有序单链表的头指针,X 为待插入元素*/ { linklist *p,*s; p=h; while(p->next!=NULL && p->next->data>x) { p=p->next;} if p->next==NUll { s=malloc(sizeof(linklist)); s->data=x; s->next=NULL; p->next=s; } else { s=malloc(sizeof(linklist)); s->data=x; s->next=p->next; p->next=s; } return (h); }
6

2、/*初始值:low=0;high=n-1;*/ int BINSEARCH(R,low,high,K) table R[ ]; keytype K; int low,high; { while(low<=high) {mid=(low+high)/2; if(K==R[mid].key) return mid; if(K<R[mid].key) BINSEARCH(R,low,mid-1,K); Else BINSEARCH(R,mid+1,high,K); } return(-1); }


更多相关文章:

非常超级学习网 fccjxxw.com

copyright ©right 2010-2021。
非常超级学习网内容来自网络,如有侵犯请联系客服。zhit325@126.com|网站地图