数据结构2008年2009第一学期试卷卷

1、。装。订。线。2008 年2009 年第一学期数据结构 试卷 B 卷学院班级学号分数时间共 120 分钟一、单项选择题( 102= 20)1在一个长度为（）。A、O(n) C、O(n2)n的顺序表的表尾一个新元素的渐进时间复杂度为B、O(1)D、O(log2n), link)。已知指针 q 所指结点是指针 p结点*s，则应执行下列哪一个操作？2设单链表中结点的结构为(data所指结点的直接前驱，若在*q 与*p 之间（）A、s-link B、q-link C、p-link D、p-link=p-link ;p-link = s s ;s-link = ps-link ;s-link = p s

2、 ;s-link = q3若让元素 1，2，3 依次进栈，则出栈次序不可能出现（）种情况。A、3，2，1 C、3，1，24栈和队列都是（B、2，1，3 D、1，3，2）A顺序的线性结构B. 链式的非线性结构C. 限制存取点的线性结构D. 限制存取点的非线性结构5树中所有结点的度等于所有结点数加（）。A、0 C、-1B、1 D、26在一棵具有 n 个结点的二叉树中，所有结点的空子树个数等于（）。A、nC、n+1B、n-1 D、2*n7对长度为 n 的有序单链表，若搜索每个元素的概率相等，则顺序搜索到表中任一元素的平均搜索长度为（A、n/2C、(n-1)/2）。B、(n+1)/2 D、n/48在无

3、向图中定义顶点 vi 与 vj 之间的路径为从 vi 到达 vj 的一个（）。得分阅卷人题号一二三四五六总分得分阅卷人A、顶点序列 C、权值总和B、边序列D、边的条数9如果只想得到1024 个元素组成的序列中的前5 个最小元素，那么用（方法最快。）A、起泡排序 C、堆排序B、快速排序D、直接选择排序10对序列15，9，7，8，20，-1，4进行排序，进行一趟后数据的排列变为4，9，-1，8，20，7，15；则采用的是（）排序。A.B. 快速C. 选择D. 冒泡二、多项选择题 (52= 10)1、下面关于算法说法错误的是（）A、算法最终必须由计算机程序实现B、为解决某问题的算法与为该问题编写的程

4、序的含义是相同的 C、算法的可行性是指指令不能有二义性D、以上几个都是错误的2、有六个元素 6，5，4，3，2，1 的顺序进栈，问下列哪些是合法的出栈序列？A. 5 4 3 6 1 2B. 4 5 3 1 2 6C. 3 4 6 5 2 1D. 2 3 4 1 5 63. 下述编码中是前缀码的是（A、（0，01，10，11） C、（0，10，110，111）B、（0，1，00，11）D、（1，01，000，001）4、下面结论中错误的是（）A、在无向图中，边的条数是结点度数之和。 B、在图结构中，结点可以没有任何前趋和后继C、在 n 个结点的无向图中，若边数大于 n-1，则该图必是连通图 D、

5、图的邻接矩阵必定是对称矩阵5、下面的排序算法中，不稳定的是（）A.起泡排序B.直接排序D.堆排序C.排序得分题号12345得分阅卷人题号12345678910在程序运行过程中不能扩充的数组是分配的数组。这种数组在它时必须指定它的大小。将一个 n 阶三对角矩阵 A 的三条对角线上的元素按行压缩存放于一个一维数组 B 中，A00存放于 B0中。对于任意给定数组元素 AIJ，如果它能够在数组 B 中找到，则它应在位置。链表适用于查找。队列的操作在进行，删除操作在进行。设有一个顺序栈 S，元素 s1，s2，s3，s4，s5，s6 依次进栈，如果 6 个元素的出栈顺序为 s2，s3，s4，s6，s5，s

6、1，则顺序栈的容量至少应为。通常程序在调用另一个程序时，都需要使用一个来保存被调用程序内分配的局部变量、形式参数的空间以及返回地址。广义表 A(a,b,c),(d,e,f) 的表尾为。在一棵树中，结点没有前驱结点。一棵树的广义表表示为 a(b(c, d(e,f),g(h),i(j,k(x,y)，结点 k 的所有祖先的结点数为个。10根据一组(56,42,50,64,48) 依次结点生成一棵 AVL 树（高度平衡的二叉搜索树）时，当到值为的结点时需要进行旋转调整。四、判断题 (101= 10)1二维数组可以视为数组元素为一维数组的一维数组。（），通）2表示的空间一般在程序的运行过程中动态分配和常

7、器中还有空闲空间，就不会产生溢出。（在用单链表表示的链式队列中，队头在链表的链尾位置。凡是递归定义的数据结构都可以用递归算法来实现它的操作。5当向一个小根堆（最小堆）中一个具有最小值的元素时，该元素需要逐层向上调整，直到被调整到堆顶位置为止。（）6对于一棵具有 n 个结点，其高度为 h 的二叉树，进行任一种次序遍历的时间复杂度为 O(n)。7进行折半搜索的表必须是顺序（）的有序表。8、当改变网上某一关键路径上任一关键活动后，必将产生不同的关键路径。（）9、完全二叉树肯定是平衡二叉树。得分阅卷人题号12345题号678910阅卷人三、填空题(102=20)10、内排序要求数据一定要以顺序方式。（

8、）五 应用题 (45= 20)1、假设一棵二叉树的层次序列为 ABCDEFGHIJ，中序序列 DBGEHJACIF。请画出这棵二叉树。2、已知一个无向图如下图所示，要求分别用 Prim 和 Kruskal 算法生成最小树（假设以为起点，试画出构造过程）。20125119106310614645183、如何衡量 hash 函数的优劣？简要叙述 hash 表技术中的的方法。概念，并三种解决4、对下面数据表，写出采用排序算法排序的每一趟的结果，并标出数据移动情况。（125，11，22， 34，15，44，76，66，100，8，14，20，2，5，1）六、算法设计题( 210= 20)1、假设一个单循环链表，其结点含有三个域 pre、data、link。其中 data 为数据域；pre 为指针域，它的值为空指针；link 为指