《中央电大计算机科学与技术专业数据结构试卷》由会员分享，可在线阅读，更多相关《中央电大计算机科学与技术专业数据结构试卷（12页珍藏版）》请在金锄头文库上搜索。
1、中央电大计算机科学与技术专业数据结构（本科）试卷72003年7月已考一、选择题（每小题1分，共10分）1. 在一个长度为n的顺序表的任一位置插入一个新元素的渐进时间复杂度为（）。A. O（n）B. O（n/2）C. O（1）D. O（n2）2. 带头结点的单链表first为空的判定条件是：A. first = NULL;B. first- link = NULL;C. first-link = first;D. first != NULL;3. 当利用大小为n的数组顺序存储一个队列时，该队列的最大长度为（）。A. n-2B. n-1C. nD. n+14.在系统实现递归调用时需利用递归工作记录
2、保存实际参数的值。在传值参数情形，需为 对应形式参数分配空间，以存放实际参数的副本；在引用参数情形，需保存实际参数的（），在被调用程序中可直接操纵实际参数。B.副本 C.返回地址 D.地址A. 空间5.在一棵树中，（A.分支结点）没有前驱结点。B. 叶结点 C.树根结点D.空结点6. 在一棵二叉树的二叉链表中，空指针域数等于非空指针域数加（）。A. 2B. 1C. 0D. - 17. 对于长度为9的有序顺序表，若采用折半搜索，在等概率情况下搜索成功的平均搜索长度为（）的值除以9。A. 20B. 18C. 25D.228. 在有向图中每个顶点的度等于该顶点的（）。A.入度B.出度C. 入度与出度
3、之和D.入度与出度之差9. 在基于排序码比较的排序算法中，（）算法的最坏情况下的时间复杂度不高于O（nlog2n）。A.起泡排序B.希尔排序C.归并排序D.快速排序10. 当a的值较小时，散列存储通常比其他存储方式具有（）的查找速度。A.较慢B.较快C.相同二、填空题(每小题1分，共10分)1. 二维数组是一种非线性结构，其中的每一个数组元素最多有个直接前驱(或直接后继)。2. 将一个n阶三对角矩阵A的三条对角线上的元素按行压缩存放于一个一维数组B中，A00存放于B0中。对于任意给定数组元素BK，它应是A中第行的元素。3. 链表对于数据元素的插入和删除不需移动结点，只需改变相关结点白 域的值。
4、4. 在一个链式栈中，若栈顶指针等于NULL则为。5. 主程序第一次调用递归函数被称为外部调用，递归函数自己调用自己被称为内部调用，它们都需要利用栈保存调用后的 地址。6. 在一棵树中，结点没有后继结点。7. 一棵树的广义表表示为a (b (c, d (e, f), g (h) ), i (j, k (x, y)，结点f的层数为。假 定根结点的层数为0。8. 在一棵AVL树(高度平衡的二叉搜索树)中，每个结点的左子树高度与右子树高度之差的绝对值不超过。9. n (n 0)个顶点的无向图最多有条边，最少有 条边。10. 在索引存储中，若一个索引项对应数据对象表中的一个表项(记录)，则称此索引为索
5、引，若对应数据对象表中的若干个表项，则称此索引为索引。三、判断题(每小题1分，共10分)1. 数组是一种复杂的数据结构，数组元素之间的关系既不是线性的也不是树形的。2. 链式存储在插入和删除时需要保持物理存储空间的顺序分配，不需要保持数据元素之间 的逻辑顺序。3. 在用循环单链表表示的链式队列中，可以不设队头指针，仅在链尾设置队尾指针。4. 通常递归的算法简单、易懂、容易编写，而且执行的效率也高。5. 一个广义表的表尾总是一个广义表。6. 当从一个小根堆(最小堆)中删除一个元素时，需要把堆尾元素填补到堆顶位置，然后再按条件把它逐层向下调整，直到调整到合适位置为止。7. 对于一棵具有n个结点，其
6、高度为h的二叉树，进行任一种次序遍历的时间复杂度为 0(h)。8. 存储图的邻接矩阵中，邻接矩阵的大小不但与图的顶点个数有关，而且与图的边数也有 关。9. 直接选择排序是一种稳定的排序方法。10. 闭散列法通常比开散列法时间效率更高。四、运算题(每小题8分，共40分)1. 设有一个10 10的对称矩阵A，将其下三角部分按行存放在一个一维数组B中，A00 存放于B0中，那么A85存放于B中什么位置。2. 这是一个统计单链表中结点的值等于给定值x的结点数的算法，其中while循环有错， 请重新编写出正确的while循环。int count ( ListNode * Ha, ElemType x )
7、/ Ha为不带头结点的单链表的头指针int n = 0;while ( Ha-link != NULL ) Ha = Ha-link;if ( Ha- data = x ) n+;return n;3. 已知一棵二叉树的前序和中序序列，求该二叉树的后序序列。前序序列：A, B, C, D, E, F, G H, I, J中序序列：C, B, A, E, F, D, I, H, J, G后序序列：4. 已知一个有序表(15, 26, 34, 39, 45, 56, 58, 63, 74, 76, 83, 94 )顺序存储于一维数组 a12 中，根据折半搜索过程填写成功搜索下表中所给元素34, 5
8、6, 58, 63, 94时的比较次数。元素值比较次数34565863945. 设散列表为 HT17,待插入关键码序列为 Jan, Feb, Mar, Apr, May, June, July, Aug, Sep, Oct, Nov, Dec ，散列函数为H (key) = Li/ 2，其中，i是关键码第一个字胃在字胃表中 的序号。现采用线性探查法解决冲突。字田ABCDEFGHIJKLM序号12345678910111213字胃NOPQRSTUVWXYZ序号14151617181920212223242526(1)试画出相应的散列表;(2)计算等概率下搜索成功的平均搜索长度；五、算法分析题(每
9、小题8分，共24分)1. 阅读下列算法，并补充所缺语句void purge_linkst ( ListNode *& la ) /从头指针为la的带表头结点的有序链表中删除所有值相同的多余元素, /并释放被删结点空间。ListNode p, q, t； ElemType temp;p = la- link;while (p != NULL ) q = p;temp=p-data ;p = p-link;if ( p != NULL &) p = p-link;else while ( p != NULL & ) t = p; p = p-link;delete t;q-link=p;2. 下面
10、给出一个排序算法，它属于数据表类的成员函数，其中currentSize是数据表实例的 当前长度，Vector是存放数据表元素的一维数组。template void dataList : unknown ( ) T temp; int i, j, n = currentSize;fOr ( i = 1; i n; i+ )if ( Vectori .key = 0; j-)if ( temp.key data = BT-data;pt- rightChild = BinTreeSwopX ( BT- leftChild );pt-lefthild = BinTreeSwopX ( BT- rig
11、htChild );return pt;六、算法设计题(6分)已知二叉树中的结点类型用BinTreeNode表示，被定义为：struct BTreeNode char data;BinTreeNode *leftChild, *rightChild; ;其中data为结点值域，leftChild和rightChild分别为指向左、右子女结点的指针域，根 据下面函数声明编写出求一棵二叉树中结点总数的算法，该总数值由函数返回。假定参 数BT初始指向这棵二叉树的根结点。int BTreeCount ( BinTreeNode* BT );中央电大计算机科学与技术专业数据结构(本科)试题参考答案及评分
12、标准7一、选择题(每小题1分，共10分)1. A 2. B 3. B 4. D 5. C 6. A 7. C 8. C9. C 10. B二、填空题(每小题1分，共10分)1. 22. L(K+1)/33,指针 4.空栈5,返回6.叶子7. 38. 19. n(n-1)/2, 010.稠密，稀疏第9和10小题中有一空错则1分全扣。三、判断题(每小题1分，共10分)1.对 2.错 3.对 4.错 5.对 6.对 7.错 8.错9. 错 10. 错 四、运算题(每小题8分，共40分)1.根据题意，矩阵A中当元素下标I与J满足IJ时，任意元素AIJ在一维数组B中 的存放位置为I * (I + 1) / 2 +，因此，A85在数组B中位置为8 * (8 + 1) / 2 + 5 = 41。2.while ( Ha != NULL ) if ( Ha- data = x ) n+;Ha = Ha-link;2. 后序序列：C, B, F, E, I, J, H, G D, A对1个给1分，全对给8分H(Jan) = L10/2J = 5，H(Mar) = L13/2=6，H(May) = L13/2 J = 6,H(July) = L10/2 J = 5
