数据结构数字081-2

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

2、;s-next= q3若让元素a，b，c 依次进栈，则出栈次序不可能出现（）种情况。A、c，b，a C、c，a，b4下列陈述中正确的是（A.二叉树是度为 2 的有序树B、b，a，c D、a，c，b）B.二叉树中结点只有一个孩子时无左右之分 C.二叉树中必有度为 2 的结点D.二叉树中最多只有两棵，并且有左右之分5树中所有结点的度等于所有结点数加（）。A、0 C、-1B、1 D、26AVL 树是一种平衡的二叉排序树，树中任一结点的（）A.B.C.D.左.右左.右的高度均相同高度差的绝对值不超过 1树的高度均大于右树的高度均小于右的高度的高度得分阅卷人题号一二三四五六总分得分阅卷人7对长度为 n

3、的有序单链表，若搜索每个元素的概率相等，则顺序搜索到表中任一元素的平均搜索长度为（A、n/2C、(n-1)/2 8已知一个有向图如右所示，则从顶点a 出发进行深度优先遍历，）。B、(n+1)/2 D、n/4b不可能得到的DFS 序列为（）acefA. a d b e f cC. a d c b f eB. a d c e f bD. a d e f c bd49不可能生成右图所示二叉排序树的关键字序列是（）A.4 5 3 1 2C.4 5 2 1 3B.4 2 5 3 1D.4 2 3 1 5523110n 个顶点的有向完全图中含有向边的数目最多为（）A.n-1B.n-1)/2D.n(n-1)

4、二、多项选择题(52= 10)1、下面关于算法说法错误的是（）A、算法最终必须由计算机程序实现B、为解决某问题的算法与为该问题编写的程序的含义是相同的 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、在无向图中，边的条

5、数是结点度数之和。 B、在图结构中，结点可以没有任何前趋和后继C、在n 个结点的无向图中，若边数大于n-1，则该图必是连通图 D、图的邻接矩阵必定是对称矩阵5、下面的排序算法中，不稳定的是（）A.起泡排序B.直接排序D.堆排序C.排序得分阅卷人题号12345678910三、填空题(102=20)1串S=“I am a student”的长度是。2对关键字序列（52，80，63，44，48，91）进行一趟快速排序之后得到的结果为。链表适用于查找。队列的操作在进行，删除操作在进行。5N 个顶点的连通图的生成树有条边。6设 r 指向单链表的最后一个结点，要在最后一个结点之后s 所指的结点，需执行的三

6、条语句是；r=s;r-next=null;。无向图中的极大连通子图称作；有向图中的极大强连通子图称作 。在一棵树中，结点没有前驱结点。四、判断题 (101= 10)1. 对链表进行和删除操作时，不必移动结点。（），通）2表示的空间一般在程序的运行过程中动态分配和常器中还有空闲空间，就不会产生溢出的问题。（3在一个有向图的拓扑序列中，若顶点 a 在顶点 b 之前，则图中必有一条弧。()4对有向图G，如果从任一顶点出发进行一次深度优先或广度优先搜索就能每个顶点，则该图一定是完全图。（）5在循环队列中，front 指向队列中第一个元素，rear 指向实际的队尾元素的下一个位置，队列为满的条件是 fr

7、ont=rear。（）6对于一棵具有n 个结点，其高度为 h 的二叉树，进行任一种次序遍历的时间复杂度为 O(n)。 7进行折半搜索的表必须是顺序（）的有序表。8、当改变网上某一关键路径上任一关键活动后，必将产生不同的关键路径。（）9、二叉树中结点只有一个孩子时无左右之分。10、AVL 树是一种平衡的二叉排序树，左.右的高度均相同。得分阅卷人得分阅卷人题号12345五 应用题 (45= 20)已知图 G=（V，E），其中： V=a,b,c,d,e,E=(a,b),(b,d),(c,b),(c,d),(d,e),(e,a),(e,c)。画出图G；画出图G 的邻接表。2、画出下图所示二叉树的中序线索链表的表示。EBDACKF3、如何衡量 hash 函数的优劣？简要叙述 hash 表技术中的概念，并三种解决的方法。得分阅卷人题号123456789104、对下面数据表，写出采用排序算法排序的每一趟的结果，并标出数据移动情况。（125，11，22， 34，15，44，76，66，100，8，14，20，2，5，1）六、算法设计题( 210= 20)1、假设表达式中允许包含两种括号：圆