绵职院计科系计应班软件班数据结构期末试卷001a1.doc

数据结构一、选择题：(151分)1. 设有二维数组A09，019其中每个元素占两个字节。数组按列优先顺序存贮。第一个元素的存贮地址为100。则元素A6，6的存贮地址为（ ）。A126 B132 C226 D2322. 数据项的集合的集合称为（ ）。A文件 B记录 C索引 D关键字3. 设元素的长度为1，则对队列q施以出队delq(q)运算后（ ）。A队头指针增量1 B队尾指针增量1 C队尾元素出队 D队头、队尾指针不动4. 在下列排序方法中，哪一个是稳定的排序方法（ ）。A堆排序 B直接选择排序C希尔排序 D快速排序5. 设有一棵三叉树（树的度为3的树）。其叶子结点数为N。度为1的结点数为N1，度为2的结点为N2，度为3 的结点数为N3，则N0与N1、N2、N3的关系满足（ ）。AN0=N2+1 BN0=N2+2*N3+1CN0=N2+N3+1 DN0=N1+N2+N36. 有6个元素按6，5，4，3，2，1的顺序进栈，入栈过程允许栈顶元素出找。问下列哪一个不是合法的出栈序列（ ）。A5 4 3 6 1 2 B4 5 3 1 2 6C3 4 6 5 2 1 D2 3 1 4 5 67. 下面关于串的叙述中，哪一个是不正确的（ ）。A串是字符的有限序列 B空串是由空格构成的串 C模式匹配是串的一种重要的运算D串既是可采用顺序存贮，也可采用链式存贮装 订. 线8. 对包含n个元素的散列表进行检索，平均检索长度为（ ）。A0（log2n） B0(n)C0(nlog2n) D不直接依赖于n9. 在堆排序中，当初堆建成后，该堆根的记录必是（ ）。A.文件中的第一个记录B.文件中具有最大（或最小）关键字的记录C.文件中的一个记录D.文件中的最后一个记录10. 下面有向图可以排成不同的拓扑序列，其中不正确的序列为（ ）。A. 1 2 3 4 5 6 B. 1 2 4 3 6 5C. 1 4 2 3 6 5 D. 1 2 3 4 6 511. 树形结构中，每个结点（ ）A、无直接前驱 B、可有多个直接前驱C、至多只能有一个直接前驱 D、有三个以上的直接前驱12. 设有向图G有n个顶点,它的邻接矩阵为A，G中第i个顶点Ui的度为( )。A、Ai，i B、Ai，jC、（Ai，j+Aj，i） D、Ai，j+Ai，j13. m叉树的后序遍历结果和该树转换所得二叉树的_结果完全相同（）A、前序遍历 B、中序遍历C、后序遍历 D、层次遍历14. 设只含根结点的二叉树的高度为1，则高度为k的二叉树的最大结点数为（）A、2k-1-1 B、2k-1C、2k-1 D、2k15. 对n个排序码进行排序，具有平均时间复杂度为O(n2)的排序方法是（）A、合并排序 B、堆排序C、快速排序 D、直接插入排序二、填空：(53分+35分)1. 在顺序表（5，13，17，42，46，55，70，94）中，用二分法查找关键码值为12，需做的关键码比较次数为 _。2. 对某非空二叉树进行前序、中序遍历时，所得的结果完全相同（即结点序列一致），则这棵二叉树必定是_。3. 对于有n个顶点的连通图，至少有_条边。由此而构成的生成树有_条边。有_条边的无向图为完全图。4. 设有一个用线性探测法解决冲突得到的Hash表（Hash函数为H(k)=K Mod 11）有一组数（13,25,80,16,17,6,14），则探测元素14的地址值为_（填入上Hash表中）5. 二叉树的前根遍历为：ABCDEFGHI，中根遍历：BCAEDGHFI，这棵二叉树的后根遍历序列为_。以下是算法填空6. 该算法实现折半查找，查找表中的数据按递增次序排列int BinSearch(DataType list,int low,int high,DataType key) int mid; DataType midvalue; while(low=high) mid=(low+high)/2; midvalue=listmid; if (key=midvalue) return mid; else if(keydata); inorder(tree-rlink); 三、简答题：(40分)1. 设电文中出现字字母A,B,C,D,每个字母在电文中出现的次数分别是2,7,4,5按哈夫曼编码求A,B,C,D的编码,请作出哈夫曼树.并求WPL.2. 己知如图所示的一棵树，写出此树的先根遍历序列，并画出其孩子链表表示法的存储结构图。3. 已知如下带权图，请给出该图的邻结表，并用C语言描述起存储结构。（将其结构填充完整）A卷 第7页 共7 页 #define MAXtypedef struct ArcNode ArcNode; /边typedef struct VnodeVnode,AdjlistMAX; /结点typedfe stru int kind /图的种类标志ALGrph /图4. 求图的最小生成树（描述过程）四、算法设计(15分)在一维数组An中，从下标1到n-1的单元中，存放着n-1个整数，使用插入法排序，将数组递增排列。插入法排序的基本操作是将一个个数据不断地插入到已