数据结构-答案a

1、。装。订。线。2008 年2009 年第一学期 数据结构A 卷学院班级学号分数时间共 120 分钟一、单项选择题( 102= 20)1、从逻辑上可以把数据结构分为（C）两大类。A、动态结构、静态结构 C、线性结构、非线性结构B、顺序结构、链式结构 D、初等结构、构造型结构2、结点的单链表L 为空的判定条件是（B）A、L= =NULLC、L-next= =L栈和队列都是（ CB、L-next = =NULL D、L！=NULL3.）A顺序的线性结构B.D.链式的非线性结构C. 限制存取点的线性结构串的长度是指（B）A、串中所含不同字母的个数 C、串中所含不同字符的个数限制存取点的非线性结构4.B

2、、串中所含字符的个数D、串中所空格字符的个数5.若广义表A 满足Head（A）=Tail(A)，则A 为（B）A、（）C、（），（）有n 个叶子的 A、不确定B、( )D、（），（），（）树的结点总数为（D）6.B、2nC、2n+1D、2n-17.要连通具有n 个顶点的无向图，至少需要（A）条边。An-lBnCn+lD2n8、从键盘依次输入关键字的值：t、u、r、b、o、p、a、s、c、l。建立二叉排序树，则其先序遍历序列为（C）A、abcloprstu C、trbaoclpsuB、alcpobsrut D、trubsaocpl9、将 10 个元素散列到 100000 个单元的哈希表中，则（C

3、）产生。A. 一定会B. 一定不会C. 仍可能会10、对序列15，9，7，8，20，-1，4进行排序，进行一趟后数据的排列变为4，9，-1，8，20，7，15；则采用的是（C）排序。得分阅卷人题号一二三四五六总分得分阅卷人A. 选择B. 快速C.D. 冒泡二、多项选择题 (52= 10)1、下面关于算法说法错误的是（ABC） A、算法最终必须由计算机程序实现B、为解决某问题的算法与为该问题编写的程序的含义是相同的 C、算法的可行性是指指令不能有二义性D、以上几个都是错误的2、有六个元素 6，5，4，3，2，1 的顺序进栈，问下列哪些是合法的出栈序列？( ABD)A. 5 4 3 6 1 2B.

4、 4 5 3 1 2 6C. 3 4 6 5 2 1D. 2 3 4 1 5 63. 下述编码中是前缀码的是（CD）A、（0，01，10，11） C、（0，10，110，111）4、下面结论中错误的是（ACD）B、（0，1，00，11）D、（1，01，000，001）A、在无向图中，边的条数是结点度数之和。 B、在图结构中，结点可以没有任何前趋和后继C、在n 个结点的无向图中，若边数大于n-1，则该图必是连通图 D、图的邻接矩阵必定是对称矩阵5、下面的排序算法中，不稳定的是（ ACD）排序A.起泡排序B.直接 D.堆排序C.排序三、填空题(102=20)1、一个数据结构在计算机中的 （1） 称

5、为结构。2、若经常需要对线性表进行和删除运算，则最好采用 （2）结构，若经常需要对线性表进行查找运算，则最好采用 （3） 3、循环队列的引入，目的是为了克服（4）。4、空串与空格串的区别在于 （5） 5、 数组 A56的每个元素占 5 个字节，将其按列优先次序1000 的内存单元中，则元素 A44的地址是 （6） 。结构。在起始地位为得分阅卷人题号12345ABCABDCDACDACD得分阅卷人题号12345678910CBCBBDACCC6、若以4，5，6，7，8作为叶子结点的权值构造是 （7） 。树，则其带权路径长度7、一无向图 G（V，E），其中 V（G）=1,2,3,4,5,6,7，E

6、（G）=（1,2）,(1,3），（2,4），（2,5），（3,6），（3,7），（6,7）（5,1）,对该图从顶点 3 开始进行遍历，去掉遍历中未走过的边，得一生成树 G(V，E）,V（G）=V（G），E（G）=（1,3），、（3,6），（7,3），（1,2），（1,5），（2,4），则采用的遍历方法是 （8）。8、在顺序表（8,11,15,19,25,26,30,33,42,48,50）中，用二分（折半）法查找关键码值 20，需做的关键码比较次数为 （9）.9、从平均时间性能而言， （10）排序最佳.四、判断题 (101= 10)1、程序一定是算法。（）2、在一个结点的双向循环链表中，若要在

7、 p 所指的结点之前一个新结点，则需要相继修改 6 个指针域的值。（）3、即使对不含相同元素的同一输入序列进行两组不同的合法的入栈和出栈组合操作，所得的输出序列也一定相同。（），）4、串既可以采用顺序，也可以采用链式5、数组可看成线性结构的一种推广，因此与线性表一样，可以对它进行删除等操作。6、用二叉树的前序遍历和中序遍历可以导出树的后序遍历。7、一个有向图的邻接表和逆邻接表中结点的个数可能不等。（8、当改变网上某一关键路径上任一关键活动后，必将产生不同的关键路径。（）9、完全二叉树肯定是平衡二叉树。10、内排序要求数据一定要以顺序方式（。五 应用题 (45= 20)得分阅卷人题号123456

8、78910NNNYNYNNYN得分阅卷人题号12345表示链式顺序假溢出空串的长度为 0，空格串的长度为串中空格字符的个数题号678910112069广度优先3快速1、将下列由三棵树组成的森林转换为二叉树。（只要求给出转换结果）DGIAJHEBCKLMNOFP2、给出图G：（1）画出 G 的邻接表表示图；（2）根据你画出的邻接表，以顶点为根，画出 G 的深度优先生成树和广度优先生成树。3、用序列(46,88,45,39,70,58,101,10,66,34)建立一个排序二叉树，画出该树，并求在等概率情况下查找成功的平均查找长度。4、给出一组关键字 T=(12,2,16,30,8,28,4,10

9、,20,6,18),写出用下列算法从小到大排序时的序列:(1)(2)排序（排序的增量分别为 5、3、1）快速排序：1、2、（图略）每个学生的3、（图略）ASL=32/10。不同4、原始数据：第一趟：第二趟：第三趟：12,2,16,30,8,28,4,10,20,6,18(12,2,10,20,6,18,4,16,30,8,284,2,10,8,6,18,12,16,30,20,282,4,6,8,10,12,16,18,20,28,30排序)原始数据：12,2,16,30,8,28,4,10,20,6,18第一趟：第二趟：第三趟：6,2,10,4,8,12,28,30,20,16,184,2,

10、6,10,8,12,18,16,20,28,302,4,6,8,10,12,16,18,20,28,30六、算法设计题( 210= 20)1、已知 Q 是一个非空队列，S 是一个空栈，试编写一个算法，仅用队列和栈的ADT 函数和少量工作变量，将队列Q 中的所有元素逆置。栈的 ADT 函数有：makeEmpty(Stack S);置空栈push( Stack S, DaypeS );S);value);新元素 value 进栈Daype pop(Stack isEmpty(Stack出栈，返回栈顶值判断空否队列的 ADT 函数有：enQueue(Queue Q,Daypevalue);元素 value 进队出队列，返回队头值判队列空否Daype deQueue(Queue Q); isEmpty(Queue Q);2、分别编写在顺序表和结点的单链表上统计出值为 x 的元素个数的算法，统计结果由函数值返回。：1、基本是：顺序取出队元素，入栈；所有元素入栈后，再从栈中逐个取出，入队。算法：reverse_queue(queue q, stack s)while(!isEmpty(q)data=deQueue(q); push(s,data);while(!isEmpty(s)da