完整版,数据结构试卷及答案.docx

留意事项：期末考试《数据结构》 A 卷9、栈和队都是（ ）A ．次序储备的线性结构 B．链式储备的非线性结构 C．限制存取点的线性结构 D．限制存取点的非线性结构10、从规律上可以把数据结构分为（ ）两大类；A ．动态结构、静态结构 B．次序结构、链式结构 C．线性结构、非线性结构 D ．初等结构、构造型结构11、以下四个序列中，哪一个是堆（ ）；________:业专 线______________: 封级年__________: 密.号学________:名姓 .题号 一 二 三 四 总分 核分人 得分得分 评卷人 一、单项挑选题 （请将正确答案的字母填写在每题对应的括号内，每道题 1 分，共 20 分）1、下面关于串的表达中，哪一个是不正确的？（ ）A ．串是字符的有限序列 B ．空串是由空格构成的串 C．模式匹配是串的一种重要运算D ．串既可以采纳次序储备，也可以采纳链式储备2、设无向图的顶点个数为 n，就该图最多有（ ）条边；A ．n-1 B． n〔n-1〕/2 C． n〔n+1〕/2 D． 03、以下数据结构中， （ ）是非线性数据结构；A ．树 B ．字符串 C．队列 D．栈4、下面关于线性表的表达中，错误选项哪一个？（ ） A ．线性表采纳次序储备，必需占用一片连续的储备单元；B ．线性表采纳次序储备，便于进行插入和删除操作；C．线性表采纳链接储备，不必占用一片连续的储备单元；D ．线性表采纳链接储备，便于插入和删除操作；5、假设以数组 A[m] 存放循环队列的元素 ,其头尾指针分别为 front 和rear，就当前队列中的元素个数为（ ）；A ． 〔rear-front+m〕%m B ． rear-front+1C． 〔front-rear+m〕%m D ． 〔rear-front〕%m6、在单链表指针为 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,eC． a 和 〔〔b,c〕 ，d,e〕 D ． 〔a〕 和〔〔b,c〕， d,e〕A ． 75,65,30,15,25,45,20,10 B ．75,65,45,10,30,25,20,15C． 75,45,65,30,15,25,20,10 D． 75,45,65,10,25,30,20,1512、在下述结论中，正确选项（ ）①只有一个结点的二叉树的度为 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+M315、在下面的程序段中，对 x 的赋值语句的频度为（ ）；FOR i:=1 TO n DO FOR j:=1 TO n DOx:=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 -118、以下排序算法中 〔 〕排序在一趟终止后不肯定能选出一个元素放在其最终位置上； 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 页 第 1 页 本试卷共 6 页 第 2 页_____________:业专 线_____________:_ 封级年__________: 密.号学______:__名姓 .得分 评卷人 二、判定题，在正确的题后括号内打“√” ，在错误的题后 括号内打“” （每道题 1 分，共 10 分）1、算法是由如干条指令组成的有穷序列，而一个程序不肯定满意有穷性； （ ）2、次序储备方式只能用于储备线性结构； 〔 〕3、对任何数据结构链式储备结构肯定优于次序储备结构； 〔 〕4、有向图的邻接矩阵是对称矩阵，无向图的邻接矩阵是非对称矩阵； （ ）5、全部二叉树的度均为 2；（ ）6、满二叉树肯定是完全二叉树，但完全二叉树不肯定是满二叉树； （ ）7、循环链表不是线性表； 〔 〕8、文件是记录的集合，文件上的操作主要有两类：检索和保护； （ ）9、线性表的特点是每个元素都有一个前驱和一个后继； 〔 〕10、按中序遍历二叉排序树所得到中序序列是一个递增有序序列； （ ）得分 评卷人 三、应用题（第 1、4、6 题每题 10 分，第 2、3 题每题 8分，第 5 题 9 分，共 55 分）1、已知一棵树边的集合为：{〔 I , M 〕,〔 I ,N 〕,〔 E, I 〕,〔 B,E 〕,〔 B,D 〕,〔 A,B 〕,〔 G,J 〕,〔 G,K 〕,〔 C,G 〕,〔 C,F 〕,〔H,L 〕,〔 C,H 〕,〔 A,C 〕}用树形表示法画出此树，并回答以下问题：（ 1）哪个是此树的根结点？哪些是叶子结点？（ 2）树的度数和树的深度是多少？（ 3）写出结点 G 的双亲、祖先、孩子？（ 4）写出结点 E 的子孙、兄弟和结点 E 所在的层次？2 、 已 知 一 棵 二 叉 树 的 中 序 遍 历 序 列 和 后 序 遍 历 序 列 分 别 为 EBIFJAGDH 和EIJFBGHDA ；要求：（ 1）画出这棵二叉树；（ 2）写出这棵二叉树的前序遍历序列；3、已知世界六大城市为 :北京 〔Pe〕、纽约 〔N〕 、巴黎 〔Pa〕、 伦敦 〔L〕 、 东 京 〔T〕 、 墨西哥 〔M〕, 下表给定了这六大城市之间的交通里程 :世界六大城市交通里程表 〔单位 : 百公里 〕 Pe N Pa L T MPe109828121124N109585510832Pa825839792L815539589T211089795113M124329289113（ 1）画出这六大城市的交通网络图 ;（ 2）画出该交通网络图按权值递增的次序来构造的最小 〔代价 〕生成树；4、假设用于通信的电文由字符集 {a,b,c,d,e,f,g ， h} 中的字母构成；它们在电文中显现的频度分别为 {7,19,2,6,32,3,21,10} ；要求：（ 1〕 请为这 8 个字母设计哈夫曼编码，并画出对应的哈夫曼树；（ 2）运算该哈夫曼树的最小加权路径长度 WP；L5、对给定的一组关键字： 49， 38， 65， 97， 76， 13， 27， 49， 55，4本试卷共 6 页 第 3 页 本试卷共 6 页 第 4 页分别写出希尔排序（增量为 5， 3， 1）、起泡排序和归并排序的前 3 趟排序结果；得分 评卷人四、算法设计题（第 1 题 7 分，第 2 题 8 分，共 15 分）_____________:业专 线______________: 封级年__________: 密.号学________:名姓 .6、设散列表长度为 13，即其地址空间为 0-12 ，散列函数 H〔k〕=K mod13, 对关键字序列{19 ， 14， 23， 01， 68， 20， 84， 27， 55， 11， 10， 79} ；要求：（ 1）画出用线性探查法解决冲突时构造的散列表（哈希表） ；（ 2）设每个记录的查找概率相等，运算查找胜利的平均查找长度（ ASLsucc）以及查 找不胜利的平均查找长度 〔ASLunsucc〕 ；1、已知带头结点的动态单链表 L 中的结点是按整数值递增排列， 试写一算法将值为 X的结点插入链表 L 中，使 L 仍旧有序；单链表的描述如下： typedef int datatype;typedef struct node{ datatype data; struct node *next;}linklist;2、试写出递归的二分查找（折半查找）算法；本试卷共 6 页 第 5 页 本试卷共 6 页 第 6 页黄淮学院 2006 — 2007 年其次学期计科系《 数据结构》期末试卷（ A ）评分标准及标准答案一、挑选题， 共 20 个小题，每道题 1 分，共 20 分；此题为单项挑选题，多项或错选均不能得分；标准答案如下：题号 123456789101112131415。