四川师范大学2007-2008年第二学期数据结构期末试题A

计算机科学学院电子商务、教育技术学专业《数据结构》试卷A第1页(共8页)__________________学院__________级___________班姓名_______________学号_______________………………………………（密）………………………………（封）………………………………（线）………………………………密封线内答题无效四川师范大学计算机科学学院电子商务、教育技术学专业2007－2008学年度第二学期期末考试数据结构试卷AAAA卷答卷说明答卷说明答卷说明答卷说明：1.本试卷共8页，五个大题，满分100分，120分钟完卷。2.本试卷为闭卷考试，请将所有题目直接做在试卷上。3.本试卷适用于2006级4、5班。题号一二三四五总分总分人分数得分评卷人一、单项选择题一、单项选择题一、单项选择题一、单项选择题(每题2分，共20分，请将答案填在答题卡中)答题卡答题卡答题卡答题卡题号题号题号题号11112222333344445555答案答案答案答案题号题号题号题号666677778888999910101010答案答案答案答案1．下列说法正确的是：（）A．线性表的逻辑顺序和存储顺序总是一致的B．线性表的链式存储结构中，内存中可用的存储单元可以是连续的，也可以不连续C．线性表的顺序存储结构优于链式存储结构D．每种数据结构都具有插入、删除和查找三种基本操作。2.带头指针L的双向循环链表中，指针p指向双向循环链表的尾结点的条件是：（）A．p==LB．p==NULLC．L-prior==pD．p-next==NULL3.一个栈的输入序列为12345，则栈的不可能输出序列是（）。A．54321B．45321C．12345D．435124.设有两个串p和q，求q在p中首次出现的位置的运算称作()A.连接B.模式匹配C.求子串D.求串长计算机科学学院电子商务、教育技术学专业《数据结构》试卷A第2页(共8页)5.已知广义表A=（a，b），B=（A，A），C=（a，（b，A），B），则GetTail（GetHead（GetTail（C）））的值为：（）A.（a,b）B.((a,b))C.bD.a6.程序段：for(i=0;i=n;i++){++x;s+=x;}中，语句++x;的频度为（）。A．nB．n+1C．n+2D．n-17.最大容量为n的循环队列，队尾指针是rear，队头指针是front，则队满的条件是（）A.（rear+1）%n==frontB.rear==frontC.rear+1==frontD.(rear-1)%n==front8.以二叉链表作为二叉树存储结构，在具有n结点的二叉链表中（n0），空链域的个数为（）A.2n-1B.n-1C.n+1D.2n+19.有8个结点的无向图最多有（）条边。A．14B.28C.56D.11210.用快速排序法对数据文件进行排序时，（）记录在排序第一趟后就放在了合适的位置。A．关键值最大的B．关键值最小的C．第一条D．最后一条得分评卷人二、填空题二、填空题二、填空题二、填空题(每题2分，共10分，请将答案填在答题卡中。)答题卡答题卡答题卡答题卡题号题号题号题号11112222333344445555答案答案答案答案1．深度为K的满二叉树共有个结点。2.在一个图中，所有顶点的度数之和等于图的边（弧）数的倍计算机科学学院电子商务、教育技术学专业《数据结构》试卷A第3页(共8页)__________________学院__________级___________班姓名_______________学号_______________………………………………（密）………………………………（封）………………………………（线）………………………………密封线内答题无效3．哈夫曼树的结点数目n与叶结点数目m满足如下关系4.有一个10阶对称矩阵A，采用压缩存储方式（以行序为主存储，且A[1][1]=1），则A[8][5]的地址是_______________。5.一个无向图采用邻接矩阵存储方法，其邻接矩阵一定是一个。得分评卷人三、判断题判断题判断题判断题(每题1分，共10分，正确：√，错误：×，请将答案填在答题卡中。)答题卡答题卡答题卡答题卡题号题号题号题号11112222333344445555答案答案答案答案题号题号题号题号666677778888999910101010答案答案答案答案1.线性表的逻辑顺序与存储顺序总是一致的。（）2.栈和队列是一种非线性数据结构。（）3.队是一种插入与删除操作分别在表的两端进行的线性表，是一种先进先出结构。（）4.设有两个串p和q，求q在p中首次出现的位置的运算称作求子串。（）5.二叉树是树的特殊形式。（）6.一棵树的度为树中各个结点的度数之和（）7.对任意一个图，从它的某个顶点出发进行一次深度优先或广度优先遍历可访问到该图的每个顶点。（）8.向二叉排序树插入一个新结点时，新结点一定成为二叉排序树的一个叶子结点。（）9.对无序表用折半查找比顺序查找快。（）10.用邻接矩阵存储一个图时，在不考虑压缩存储的情况下，所占用的存储空间大小只与图中结点个数有关，而与图的边数无关。（）计算机科学学院电子商务、教育技术学专业《数据结构》试卷A第4页(共8页)得分评卷人三、简答题三、简答题三、简答题三、简答题(共6道小题，每小题6分，共36分)1.已知一棵二叉树的中序序列和后序序列分别为BDCEAFHG和DECBHGFA，画出这棵二叉树并画出该二叉树的中序线索化树。2.设某密码电文由8个字母（A，B，C，D，E，F，G，H）组成，每个字母在电文中的出现频率分别是7，19，2，6，32，3，21，10，试为这8个字母设计相应的哈夫曼编码。计算机科学学院电子商务、教育技术学专业《数据结构》试卷A第5页(共8页)__________________学院__________级___________班姓名_______________学号_______________………………………………（密）………………………………（封）………………………………（线）………………………………密封线内答题无效3．记录的关键字集合key={49,38,66,90,75,10,20}，写出快速排序第一趟和第二趟之后的状态，并判断快速排序是否稳定。4．给定下列网G:试着画出网G的最小生成树；计算机科学学院电子商务、教育技术学专业《数据结构》试卷A第6页(共8页)5.对于有向无环图（1）叙述求拓扑有序序列的步骤；（2）对于下图写出它的四个不同的拓扑有序序列。6．若关键字序列为（10，24，32，17，31，30，46，47，40，63，49），哈希函数为：H（K）＝KMOD11，K为关键字。给出用线性探测再散列法处理冲突所构造的哈希表。计算机科学学院电子商务、教育技术学专业《数据结构》试卷A第7页(共8页)__________________学院__________级___________班姓名_______________学号_______________………………………………（密）………………………………（封）………………………………（线）………………………………密封线内答题无效得分评卷人五、用类五、用类五、用类五、用类CCCC语言描述下列算法，并给出必要说明语言描述下列算法，并给出必要说明语言描述下列算法，并给出必要说明语言描述下列算法，并给出必要说明。（第一题14分，第二题10分，共24分）1、用算法建立含n个结点的带头结点的单链表La（n个结点的值由键盘输入），并删除所有等于数值x的结点。（14分）已知线性表的单链表存储结构如下：typedefstructLnode{elemtypedata;Lnode*next;}Lnode,*LinkList;给出算法voidcreatList(LinkList&La,intn)、voidDeleteList(LinkList&La，elemtypex)并给出必要的说明。计算机科学学院电子商务、教育技术学专业《数据结构》试卷A第8页(共8页)2、设二叉树采用二叉链表存储结构，试设计一个算法计算一棵给定二叉树的深度。（10分）//二叉树的存储表示typedefstructBiTNode{ElemTypedata;StuctBiTNode*lchild,*,*,*,*rchild;//左右指针标志}BiTNode,*BiTree