数据结构(java)复习题及答案.doc

1、一、 选择题1、数据结构在计算机内存中的表示是指_A_ A数据的存储结构 B.数据结构 C. 数据的逻辑结构 D.数据元素之间的关系 2、若一个算法的时间复杂度用T(n)表示，其中n的含义是（ A ）A问题规模 B语句条数C循环层数 D函数数量3、下列选项中与数据存储结构无关的术语是（ D ）A.顺序表B.链表C.链队列D.栈4、已知循环队列的存储空间大小为m，队头指针front指向队头元素，队尾指针rear指向队尾元素的下一个位置，则向队列中插入新元素时，修改指针的操作是（ D ）A.rear=(rear-1)%m;B.front=(front+1)%m;C.front=(front-1)%

2、m;D.rear=(rear+1)%m;5、栈和队列的共同点是_C_ A.都是先进后出 B.都是先进先出 C.只允许在端点处插入和删除元素 D.没有共同点6、已知一堆栈的进栈序列为1234,则下列哪个序列为不可能的出栈序列_D_ A.1234 B.4321 C.2143 D.41237、具有线性结构的数据结构是（ C ）A树 B图C栈和队列 D广义表8、假设以数组A60存放循环队列的元素，其头指针是front=47，当前队列有50个元素，则队列的尾指针值为（ B ）A3 B37C50 D979、若栈采用链式存储结构，则下列说法中正确的是（ B ） A需要判断栈满且需要判断栈空 B不需要判断栈满

3、但需要判断栈空 C需要判断栈满但不需要判断栈空 D不需要判断栈满也不需要判断栈空10、若一棵具有n(n0)个结点的二叉树的先序序列与后序序列正好相反，则该二叉树一定是（ C ）A.结点均无左孩子的二叉树 B.结点均无右孩子的二叉树C.高度为n的二叉树 D.存在度为2的结点的二叉树11、若一棵二叉树中度为l的结点个数是3，度为2的结点个数是4，则该二叉树叶子结点的个数是（ B ）A.4B.5C.7D.812、在n个结点的线索二叉树中，线索的数目为_C_ An-1 B. n C.n+1 D.2n13、一棵完全二叉树有1001个结点,其中有_B_叶子结点 A.500 B.501 C.503 D.50

4、5 15、一个有n个顶点的无向图最多有_C_条边。 A. n B. n(n-1) C. n(n-1)/2 D. 2n16、以v1为起始结点对下图进行深度优先遍历，正确的遍历序列是（ D ）Av1，v2，v3，v4，v5，v6，v7 Bv1，v2，v5，v4，v3，v7，v6Cv1，v2，v3，v4，v7，v5，v6 Dv1，v2，v5，v6，v7，v3，v4二、填空题1、一个算法具有5个特性：_有穷性_、_可行性_、确定性、输入和输出4、 队列的存储方式有_顺序队列_和 _链式队列_。5、 递归过程或函数调用时，处理参数及返回地址，需要一种称为_栈_的数据结构。7、在单链表中某结点后插入一个新

5、结点，需要修改_2_个结点指针域的值。8、设栈S的初始状态为空，若元素a、b、c、d、e、f依次进栈，得到的出栈序列是b、d、c、f、e、a，则栈S的容量至少是_3_。10、设一个顺序循环队列容量为60，当front=47，rear=23时，该队列有_36_个元素。11、已知二维数组a108采用行主序存储，数组首地址是1000，每个元素占用4字节，则数组元素a45的存储地址是_1176_。12、已知一棵完全二叉树的根（第0个）结点层次为1，则第100个结点的层次为_7_。12、 中根遍历序列和后根遍历序列相反的二叉树是_结构均无左孩子的二叉树_。13、由256个权值构造一棵哈夫曼树，则该二叉树

6、共有_256+255_结点。14、用6个权值分别为6、13、18、30、7和16的结点构造一棵哈夫曼(Huffman)树，该树的带权路径长度为_219_。15、 深度为5的二叉树至多有_25-1_个结点。17、一个有n个顶点的无向连通图，最少有_n-1_条边。18、交换排序法是对序列中的元素进行一系列比较，当被比较的两元素逆序时，进行交换。_和_是基于这类方法的两种排序方法。19、在长度为n的顺序表L中查找指定元素值的元素，其时间复杂度为_有一个有序表为1,3,9,12,32,41,45,62,75,77,82,95,99,当采用二分查找法查找关键字为82的元素时，_次比较后查找成功。 20、

7、设用希尔排序对98,36,-9,0,47,23,1,8,10,7进行排序，给出的步长（也称增量序列）为5,则第一趟排序后的结果是_。三、应用题1、将下列稀疏矩阵的非零元素表示成三元组的形式。 2、画出下列广义表的双链表示： 中国（北京，上海，江苏（南京，苏州），浙江（杭州），广东（广州）3、已知一棵二叉树的中根和后根遍历序列如下，画出据此构造的二叉树。 中根遍历序列：D B H E I A F K C G 后根遍历序列：D H I E B K F G C A 4.已知一棵二叉排序树（结点值大小按字母顺序）的前序遍历序列为EBACDFHG，请回答下列问题：(1)画出此二叉排序树；(2)若将此二叉

8、排序树看作森林的二叉链表存储，请画出对应的森林5、已知有向图的邻接表如图所示，请回答下面问题：(1)给出该图的邻接矩阵；(2)从结点A出发，写出该图的深度优先遍历序列。6、设用于通信的电文仅由5个字母A,B,C,D,E组成，字母在电文中出现的次数分别是2，4，5，7，8。为这五个字母设计哈夫曼编码。7、（1）分别以prim、kruscal 算法构造下图的最小生成树。（2）Dijkstra算法求下图中顶点1到其他所有顶点的最短路径及长度。 四、程序阅读题1、顺序循环队列中，出队方法如下，请补全空出的部分。 Public E dequeue() If(!isEmpty() E temp = (E)

9、 this.valuethis.front; This.front=_(this.front +1)% this.valuelegth()_; return _temp_;return null;2、以下是顺序栈类的声明，其中成员变量Value 数组存储栈的数据元素，top表示当前栈顶元素的下标，请补充以下空白。import dataStructure.linearList.SStack;public class SeqStack implements SStack private Object value;private int top; public SeqStack(int capaci

10、ty) this.value=new ObjectMath.abs(capacity); this.top=-1; public SeqStack() this(10); public boolean isEmpty() /判断栈是否为空，若空栈返回true return this.top_= -1_; public boolean push(E element) /元素element 入栈，若操作成功返回true if(element=null) return _false_; if(this.top=value.length-1) Object temp =this.value; this.value=new Objecttemp.length*2; for(int i=0;itemp.length;i+) this.valuei=tempi;this.top_+_; this.valuethis.top=_element_; return _true_;