933计算机基础_课件期末试题历年真题数据结构2009b

1、大学计算机学院“数据结构”试题（B）学号班号要求：所有的题目的解答均写在试题纸上。一、单项选择题（每小题 2 分，共 20 分）1. 计算机所处理的数据一般具备某种内在联系，这是指。A.数据和数据之间存在某种关系C. 元素内部具有某种结构2. 不是算法的基本特性。 A.可行性C.在规定的时间内完成B.元素和元间存在某种关系D.数据项和数据项之间存在某种关系B.长度有限D.确定性3. 线性表采用链表A.必须是连续的时，其地址。B.一定是不连续的C.部分地址必须是连续的D.连续与否均可以4.已知一个栈的进栈序列是 1，2，3，n，其输出序列是 p1，p2，pn，若 p1=n，则 pi 的值。A.i

2、C.n-i+1B.n-iD.不确定5. 若串 s=software，其子串的个数是。A.8C.36B.37D.96. 设二维数组 Amn，每个数组元素占用 k 个单元，第一个数组元素的地地址是 Loc(a00)，求按列优先顺序存放的数组元素 aij(0im-1，0jn-1)的址为。A.Loc(a00)+(i-1)*n+j-1*kC.Loc(a00)+j*m+i*kB.Loc(a00)+i*n+j*kD.Loc(a00)+(j-1)*m+i-1*k7. 对于一个具有n 个顶点和 e 条边的无向图，若采用邻接表表示，则表头向量的大小为 ；所有邻接表中的结点总数是 。 A. nC. n-1 A. e

3、/2C. 2e8. 采用邻接表A. 先序遍历C. 后序遍历B. n+1D. n+eB. eD. n+e的图的深度优先遍历算法类似于二叉树的。B. 中序遍历D. 按层遍历3. D4. C5. C6. D7. A C8. A9. B10. A1. B2. B2数据结构试题9. 有一个长度为 12 的有序表，按折半查找法对该表进行查找，在表内各元素等概率情况下查找成功所需的平均比较次数为。A. 35/12C. 39/12B. 37/12D. 43/1210.A.在待排序的元素序列基本有序的前提下，效率最高的排序方法是。B. 选择排序D. 归并排序排序C. 快速排序二、填空题（每小题 2 分，共 10

4、 分）1.2.3.广义表(a,()的长度是 ，深度是 。在各种查找方法中，平均查找长度与结点个数 n 无关的查法方法是。在排序、排序、选择排序、快速排序、堆排序、归并排序和基数排序中，排序是不稳定的有。G 是一个非连通无向图，共有 28 条边，则该图至少有个顶点。对n 个顶点的连通图来说，它的生成树一定有条边。三、问答题（每小题 8 分，共 40 分）1.分析以下算法的时间复杂度。void func(n)i=1,k=100;while (in)k+;i+=2;简述线性表、栈和队列的异同？具有 n 个结点的满二叉树的叶结点的个数是多少？一棵二叉树的先序、中序和后序序列分别如下，其中有一部分未显示

5、出来。试求出2.3.4.空格处的内容，并画出该二叉树。先序序列： B F ICEH G中序序列：D KFIA EJC 后序序列： K FBHJ G A5. 已知有序表为（12，18，24，35，47，50，62，83，90，115，134），当用折半法查找 90 时，需进行外多少次查找可确定成功？查找 47 时需进行多少次查找可确定成功？查找 100 时，需进行多少次查找才能确定不成功？3数据结构试题四、算法设计题（30 分）1.已知单链表 L(结点)是一个非有序表，设计一个算法，删除表中 data 值在大于或等于 min 小于或等于 max 之间的结点(若表中有这样的结点)，同时被删结点的空

6、间，这里 min 和 max 是两个给定的参数。并分析算法的时间复杂度。（15 分）2. 假设二叉树采用二叉链结构，t 指向根结点，p 所指结点为任一给定的结点，设计一个算法，输出从根结点到 p 所指结点之间路径。（15 分）参考一、单项选择题（每小题 2 分，共 20 分）1. B2. B3. D4. C5. C6. D7. A C8. A9. B10. A二、填空题（每小题 2 分，共 10 分）1. 2，22.哈希（散列）查找方法3.排序、选择排序、快速排序、堆排序4.图 G 是非连通无向图，至少有两个连通分量，其中通分量最少的顶点数是由 28 条边组成的无向图，其顶点数为 n，边数为

7、e，则 e n(n 1) ，e=28，则 n8；另一2个连通分量只有一个顶点，该图至少有 9 个顶点。5. n-1三、问答题（每小题 8 分，共 40 分）设 while 循环执行 T(n)次，i=2T(n)+1n，则 T(n)data,*pre=L,*q;while (p!=NULL)if (p-data=min & p-datanext=p-next; p=p-next; free(q);elsepre=p;p=p-next;算法的时间复杂度为 O(n)。2. 解：算法如下：void path(BTree* t,BTree *p)BTree* StMaxSize,*s; tagMaxSize;top=-1,i; s=t;dowhile(s!=NULL)/扫描左结点，入栈top+; Sttop=s; tagtop=0;s=s-lchild;if(top-1)if(tagtop=1)/左右结点均已过，则要该结点if (Sttop=p) /该结点就是要找的结点prf(路径:);/输出从栈底到栈顶的元素路径for (i=1;idata);prf(n);b