《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 页 - - - - - - - - -
