《2022年数据结构成教学位考试收集》由会员分享,可在线阅读,更多相关《2022年数据结构成教学位考试收集(10页珍藏版)》请在金锄头文库上搜索。
1、第 1 页 共 10页华东交通大学 2003 2004学年第 2学期考试卷数据结构课程课程类别:必闭卷:题号一二三四五六七八九总分分数评卷人一、 单选题: (每小题 1.5 分,共 15分)1. 假设某算法语句总的执行次数为T(n)=5n5+n3 +n2,那么该算法的时间复杂性量级为 _。A) O(2) B) O(n5) C) O(n4) D) O(1) 2. 若长度为 n 的线性表采用顺序存储结构,删除它的第i 数据元素之前,需要先依次向前移动 _个数据元素。 ( ) A.n-i B.n+i C. n-i-1 D.n-i+1 3. 在一个采用顺序存储方式的线性表中,若表的第一个元素的存储地址
2、是100,每一个元素的长度为2,则第 5 个元素的地址是A) 110 B) 108 C) 100 D) 120 4.以下关于线性表的说法不正确的是( )。A、线性表中的数据元素可以是数字、字符、记录等不同类型。B、线性表中包含的数据元素个数不是任意的。C、线性表中的每个结点都有且只有一个直接前趋和直接后继。D、存在这样的线性表:表中各结点都没有直接前趋和直接后继。5. 带头结点的单链表为空的判断条件是。A) head=NULL B) head-next=NULL C) head-next=head D) head!=NULL 6.栈的插入和删除操作在()进行。A 栈顶B 栈底C 任意位置D 指
3、定位置7. 某堆栈的输入序列为a,b,c,d, 下面的四个序列中, _不可能是它的输出序列。 ( ) A) a,c,b,d B) b,c,d,a C) d,c,a,b D) c,d,b,a 8. 一棵有 16 结点的完全二叉树,对它按层编号,则对编号为7 的结点 X,它的双亲结点及右孩子结点的编号分别为A) 2,14 B) 2,15 C) 3,14 D) 3,15 9. 广大义表 A=(),(a),(b,(c,d)的长度为 ( ) A) 2 B) 3 C) 4 D) 5 10. 一棵满二叉树 ,同时又是一棵 _ 。A)二叉排序树B)完全二叉树承诺:我将严格遵守考场纪律,并知道考试违纪、作弊的严
4、重性,承担由此引起的一切后果。专业班级学号学生签名:名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页,共 10 页 - - - - - - - - - 第 2 页 共 10页C)非完全二叉树D)哈夫曼树二、 填空题: (每小题 1 分,共 10 分) 1. 数据结构包括那三方面的内容:逻辑结构、 数据的运算。2. 队列中允许进行删除的一端为_ 。3. 数据元素之间有四类基本结构,它们是:集合_ 树形结构图形或网状结构。4. 线性表的单链表存储结构用C语言可定义为:Typedef
5、 struct Lnode datatype data; *next; Lnode,*LinkList; 5.栈操作的原则是;队列的操作原则是。6. 在二叉树链表上实现后序遍历的递归算法:void postorder (BiTree r) if (r!=NULL) postorder(rlchild);;visit(r) ; 7. 在一个无向图中,所有顶点的度数之和等于所有边的数目的_倍。8. 深度优先搜索遍历类似于树的遍历;广度优先搜索遍历类似于树的遍历。9.三、 判断题(判断下列各题是否正确, 若正确在括号里打 “” , 错误的打“” ,每小题 1 分,共 10 分)1、如果两个串含有相同
6、的字符,则这两个串相等。()2、数组可以看成线性表结构的一种推广,因此可以对它进行插入, 删除等运算。()3、线性表只能采用顺序存储结构或者链式存储结构。()4、在栈满的情况下不能作进栈运算,否则产生“上溢”。()5、程序越短,程序运行的时间就越少。 ()6、对任意一个图,从它的某个顶点出发,进行一次深度优先搜索或广度优先搜索,即可访问图的每个顶点。 ()7、一个有向图的邻接表和逆邻接表中表结点的个数一定不相等。()8、一个图的邻接矩阵表示法是不是唯一的,而邻接表表示法是唯一的。()9、数据的逻辑结构与数据元素本身的内容和形式有关。()10、二叉树是深度为2 的有序树。()名师资料总结 - -
7、 -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页,共 10 页 - - - - - - - - - 第 3 页 共 10页四、 简答题: (每小题 8 分 共 16 分)1 简述什么是线性表。2 简述空串与空格串有何区别?3 稀疏矩阵压缩存储采用的三元组顺序表是线性表吗?为什么?五、作图题(按题目要求写出结果) (共 24分)1、 画出下列二叉树的二叉链表表示图,并写出该二叉树的中序遍历序列 (8 分)A B C D E F G H 名师资料总结 - - -精品资料欢迎下载 - - - - - -
8、 - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页,共 10 页 - - - - - - - - - 第 4 页 共 10页2、画出下图所对应的邻接表, 并写出从 A 点开始广度优先遍历该图的结果3、假设用于通信的电文由字符集a,b,c,d,e,f,g,h中的字母构成,这 8 个字母在电文中出现的概率分别为0.07, 0.19, 0.02, 0.06, 0.32, 0.03, 0.21, 0.10. 试构造哈夫曼树,并给出它们的哈夫曼编码。(要求左边的权值小于右边的权值 ) A B C D E F 名师资料总结 - - -精品资料欢迎下载 -
9、 - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页,共 10 页 - - - - - - - - - 第 5 页 共 10页六、写算法( 25 分)1、如右图所示的双向链表i 位置之后插入一个结点s,试写出语句(包含多条语句)将空白处补充完整已知该双向链表结构形式描述如下:typedef struct dnode datatype data; struct dnode *prior,*next; dlinklist; dlinklist * head; Dinsertbefore(p,x) /*在带头结点的双链表中,将值为
10、x 的新结点插入 *p 之前 */ dlinklist *p; datatype x; dlinklist * s; s=malloc(sizeof(dlinklist); s p q ai-1 bi ci+1 d名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页,共 10 页 - - - - - - - - - 第 6 页 共 10页2、 已知带头节点的动态单链表L 中的结点是按整数值递增排列的,试写一算法将值为x 的结点插入表 L 中,使 L 仍然有序。名师资料总结 - -
11、-精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页,共 10 页 - - - - - - - - - 第 7 页 共 10页答案一、1 2 3 4 5 6 7 8 9 10 B A B C B A C D B B 二、1存储结构2.队头3.线性结构4.struct Lnode 5后进先出先进先出6.postorder(rrchild); 7. 2 8.先序层次三、1 2 3 4 5 6 7 8 9 10 四、1是由 n(n 0)各元素(结点) a1,a2, an 组成的有限序列。其中,数据元素的个数
12、n 定义为表的长度。 当 n=0 时称为空表, 常常将非空的线性表( n 0)记作: (a1,a2,an)2.长度为 0 的串称为空串,它不包含任何字符空格串是由空格字符组成的字符串, 其长度大于或等于1 的非空串2. 是线性表。将表示稀疏矩阵的非零元素的三元组按行优先(或列优先)的顺序排列(跳过零元素),则得到一个其结点均是三元组的线性表。该线性表的顺序存储结构称为三元组表。五、名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页,共 10 页 - - - - - - - - -
13、 第 8 页 共 10页1、2.其邻接表表示如下:从 A 开始广度优先遍历该图的结果是:AEDBFC 或 ABDECF 3a,b,c,d,e,f,g,h 出现的概率可转换为: 7 ,19,2,6,32,3,21,10 A B C A B C D E F B E E A D C B D D F A B C E F A D F C D E 前序遍历序列:ABCDFGHE 中序遍历序列:BADGFHCE 后序遍历序列:BGHFDECA 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 8 页
14、,共 10 页 - - - - - - - - - 第 9 页 共 10页六、1、sdata=d; snext=pnext; pnext=s;1.00 0.40 0.60 0.19 0.21 0.32 0.28 0.11 0.05 0.06 0.07 0.17 0.10 0.02 0.03 0 0 0 0 0 0 0 1 1 1 1 1 1 1 a c f d h e b g a: 1010 b:00 c:10000 d:1001 e: 11 f:10001 g:01 h:1011 if(pdatax) q=p; p=pnext; Else s=malloc(sizeof(linklist);
15、 sdata=x; qnext=s; snext=p; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 9 页,共 10 页 - - - - - - - - - 第 10 页 共 10页2、linklist *insert(L,x) Linklist *L; int x; Linklist *p,*s; p=L; if(pnext=NULL) S=malloc(sizeof(linklist); sdata=x; pnext=s; snext=NULL; else p=pnext; while(pnext!=NULL) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 10 页,共 10 页 - - - - - - - - -