数据结构062A卷

1、嘉应学院数学系数据结构课程考试题（A卷）15.题号二三四总分复核人得分评卷人得分 -、单选题（每小题1分，共20分）17.2.3.4.5.6.7.B.D.C.解决问题的步骤序列两大类。顺序结构、链式结构初等结构、构造型结构D.调度方法C.下一元素地址D.左、右孩子地址可随机访问任一元素所需空间与线性长度成正比C.后进后出 D.不分顺序D.下溢B.串中所含字符的个数D.串中所含非空格字符的个数C.上溢8.C. 35D. 369.11.12.13.14.C. AOV 网D. AOE 网16.18.19.20.元素有序元素有序A.B.C.D.冲突小A.B.C.D.B. 32,40,21,46,69,

2、94,90,80D. 90,69,80,46,21,32,94,40共20分)得分1.根据数据元素之间关系的不同特性，通常有以下4类的基本结构：线性结构、树形结构、图状结构和,结构。3.算法一般用return OK;(2007 年 1 月)计算机算法指的。A.计算方法B.排序方法从逻辑上可以把数据结构分为A.动态结构、静态结构 B.C.线性结构、非线性结构 D.静态链表中指针表示的是。A.内存地址 B.数组下标链表不具有的特点是A-插入、删除不需要移动元素C.不必事先估计存储空间对于栈操作数据的原则。A.先进先出B.后进先出在作进栈运算时，应先判别栈是否A.空B.满串的长度是指A.串中所含不同

3、字母的个数C.串中所含不同字符的个数设有一个10阶矩阵A，以行序为主存储，A00为第一元素，其存储地址为1，每个元素占 一个地址空间，则A25的地址为。A. 25B. 26对稀疏矩阵进行压缩存储目的是.A.便于进行矩阵运算B.便于输入和输出C.节省存储空间D.降低运算的时间复杂度 10.设森林F对应的二叉树为B，它有m个结点，B的根为p,p的右子树结点个数为n,森林F中第 一棵树的结点个数是A. m-nB. m-n-1 C. n+1D.条件不足，无法确定二叉树的第I层上最多含有结点数为A. 2iB. 2i-1-1C. 2i-1D. 2i -1若一棵二叉树具有10个度为2的结点，5个度为1的结点

4、，则度为0的结点个数是A. 9B. 11C. 15 D.不确定设无向图的顶点个数为n，则该图最多有 条边。A. n-1B. n（n-1）/2C. n（n+1）/2D. n2下列哪一种图的邻接矩阵是对称矩阵？A卷第一页A.有向图B.无向图关键路径是事件结点网络中。A.从源点到汇点的最长路径B.从源点到汇点的最短路径C.最长回路D.最短回路 适用于折半查找的表的存储方式及元素排列要求为_ A.链接方式存储，元素无序B.链接方式存储C.顺序方式存储，元素无序D.顺序方式存储下面关于哈希查找的说法正确的哈希函数构造的越复杂越好，因为这样随机性好 除留余数法是所有哈希函数中最好的不存在特别好与坏的哈希函

5、数，要视情况而定若需在哈希表中删去一个元素，只要将该元素从表中删去即可某内排序方法的稳定性是指。该排序算法不允许有相同的关键字记录 该排序算法允许有相同的关键字记录 平均时间为0 （n log n）的排序方法关键字相同的记录，排序前排在前面的记录,排序后仍然排在前面 就平均性能而言，目前最好的内排序方法 排序法。A.冒泡 B.希尔插入C.交换D.快速用直接插入排序方法对下面四个序列进行排序（由小到大），元素比较次数最少的是A. 94,32,40,90,80,46,21,69C. 21,32,46,40,80,69,90,94、填空题（每空1分，2.抽象数据类型ADT的定义中包括三部分即：数据对

6、象、数据关系和，来度量其效率。线性表中哪一个数据元素没有直接后继?以下算法是在带头结点的单链表L中第i个位置之前插入元素的算法，填空完善该算法。Status ListInsert(LinkList &L,int i,ElemType e)P=L;j=0;while(p&jdata=e;6.栈是,.的线性表。设有一个空栈，现有输入序列为 1, 2, 3, 4, 5,经过 PUSH,PUSH,POP,PUSH,POP,PUSH,PUSH假定用于通讯的电文仅有8个字母ABCDEFGH组成，各个字母在电文中出现的频率分别为25, 3, 6, 10, 12, 35, 4,试为这8个字母设计Huffman

7、树，给出各字母的Huffman编码。之后，输出序列是模式串P= abaabcac的next函数值序列为组成串的数据元素只能是10.数组的存储结构采用.,存储方式。11.广义表的表尾是指除第一个元素之外的3.已知无向图的邻接矩阵表示法如下，画出该图并给出其邻表表示法12.具有256个结点的完全二叉树的深度为13.深度为k的满二叉树的结点数为14.一个无序序列可以通过构造一棵，树而变成一个有序序列，构造树的过程即为对无序序列进行排序的过程。A0 10 10B10 10 1C0 10 11D10 10 0E0 110 015.16.对于一个具有n个顶点e条边的无向图的邻接表的表示，则表头向量大小为对

8、下图使用prim算法画出从顶点1出发构造最小生成树的过程图17.顺序查找n个元素的顺序表，若查找成功，则比较关键字的次数最多为18.在顺序表（8,11,15,19,25,26,30,33,42,48,50）中，折半法查找关键码值20,需做的关键码比较次数为得分三、应用题（每1小题5分，共40分）1.已知一棵二叉树的中序（或中根）遍历结点排列为DBEAFCG，后序（或后根）遍历结点排列为 DEBFGCA,（1）试画出该二叉树；（2）给出其先序遍历结果。V为图G的一个顶点，则以V为弧头的弧的数目称为顶点V的,5.使用第4题图，写出对其从顶点1出发进行深度优先遍历结果和广度优先遍历结果。A卷 第页封号座名封姓二班密 已知输入关键字序列为(100,90,120,60,78,35,42,31,15)地址区间为010。哈希函数 H(key) = key/20,使用线性探测再散列解决冲突，计算每个关键字的哈希函数值并画出哈希表。对序列48, 38, 35, 90, 65, 13给出使用表插入排序的过程。|得分|四、算法设计题(每小题10分，共20分)试编写算法，对棵以孩子兄弟链表表示的树统计叶子的个数。树的结点结