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

一、 选择题

1、数据结构在计算机内存中的表示是指____A__

A．数据的存储结构 B.数据结构

C. 数据的逻辑结构 D.数据元素之间的关系

2、若一个算法的时间复杂度用T(n)表示，其中n的含义是（ A ）

A．问题规模 B．语句条数

C．循环层数 D．函数数量

3、下列选项中与数据存储结构无关的术语是（ D ）

A.顺序表

C.链队列 B.链表 D.栈

4、已知循环队列的存储空间大小为m，队头指针front指向队头元素，队尾指针rear指向队尾元素的下一个位置，则向队列中插入新元素时，修改指针的操作是（ D ）

A.rear=(rear-1)%m;

B.front=(front+1)%m;

C.front=(front-1)%m;

D.rear=(rear+1)%m;

5、栈和队列的共同点是__C______

A.都是先进后出 B.都是先进先出

C.只允许在端点处插入和删除元素 D.没有共同点

6、已知一堆栈的进栈序列为1234,则下列哪个序列为不可能的出栈序列______D__

A.1234 B.4321

C.2143 D.4123

7、具有线性结构的数据结构是（ C ）

A．树 B．图

C．栈和队列 D．广义表

8、假设以数组A[60]存放循环队列的元素，其头指针是front=47，当前队列有50个元素，则队列的尾指针值为（ B ）

A．3 B．37

C．50 D．97

9、若栈采用链式存储结构，则下列说法中正确的是（ B ）

A．需要判断栈满且需要判断栈空

B．不需要判断栈满但需要判断栈空

C．需要判断栈满但不需要判断栈空

D．不需要判断栈满也不需要判断栈空

10、若一棵具有n(n>0)个结点的二叉树的先序序列与后序序列正好相反，则该二叉树一定是（ C ）

A.结点均无左孩子的二叉树 B.结点均无右孩子的二叉树

C.高度为n的二叉树 D.存在度为2的结点的二叉树

11、若一棵二叉树中度为l的结点个数是3，度为2的结点个数是4，则该二叉树叶子结点的个数是（ B ）

A.4 B.5

C.7 D.8

12、在n个结点的线索二叉树中，线索的数目为_C_______

A．n-1 B. n

C.n+1 D.2n

13、一棵完全二叉树有1001个结点,其中有____B_____叶子结点

A.500 B.501

C.503 D.505

15、一个有n个顶点的无向图最多有___C____条边。

A. n B. n(n-1)

C. n(n-1)/2 D. 2n

16、以v1为起始结点对下图进行深度优先遍历，正确的遍历序列是（ D ）

A．v1，v2，v3，v4，v5，v6，v7 B．v1，v2，v5，v4，v3，v7，v6

C．v1，v2，v3，v4，v7，v5，v6 D．v1，v2，v5，v6，v7，v3，v4

二、填空题

1、一个算法具有5个特性：__有穷性_____、__可行性____、确定性、输入和输出

4、 队列的存储方式有__顺序队列__________和 ____链式队列_______。

5、 递归过程或函数调用时，处理参数及返回地址，需要一种称为__栈_____的数据结构。

7、在单链表中某结点后插入一个新结点，需要修改___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、已知二维数组a[10][8]采用行主序存储，数组首地址是1000，每个元

素占用4字节，则数组元素a[4][5]的存储地址是____________1176______________。

12、已知一棵完全二叉树的根（第0个）结点层次为1，则第100个结点的层次为_____7___。

12、 中根遍历序列和后根遍历序列相反的二叉树是_______________结构均无左孩子的二叉树____________________。

13、由256个权值构造一棵哈夫曼树，则该二叉树共有___256+255_______结点。

14、用6个权值分别为6、13、18、30、7和16的结点构造一棵哈夫曼(Huffman)树，该树的带权路径长度为_____219____。

15、 深度为5的二叉树至多有___2^5-1___个结点。

17、一个有n个顶点的无向连通图，最少有______n-1__________条边。

18、交换排序法是对序列中的元素进行一系列比较，当被比较的两元素逆序时，进行交换。______和_____是基于这类方法的两种排序方法。

19、在长度为n的顺序表L中查找指定元素值的元素，其时间复杂度为__________

有一个有序表为{1,3,9,12,32,41,45,62,75,77,82,95,99},当采用二分查找法查找关键字为82的元素时，_______次比较后查找成功。

20、设用希尔排序对{98,36,-9,0,47,23,1,8,10,7}进行排序，给出的步长（也称增量序列）为5,则第一趟排序后的结果是__________________________________________。

三、应用题

1、将下列稀疏矩阵的非零元素表示成三元组的形式。

0007 3 00 100

A 1 2000 00000 0020 0

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)若将此二叉排序树看作森林的二叉链表存储，请画出对应的森林

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) this.value[this.front];

This.front=___(this.front +1)% this.valuelegth()________________; return _______temp____;

}

return null;

}

2、以下是顺序栈类的声明，其中成员变量Value 数组存储栈的数据元素，top表示当前栈顶元素的下标，请补充以下空白。

import dataStructure.linearList.SStack;

public class SeqStack<E> implements SStack <E> { private Object value[];

private int top;

public SeqStack(int capacity) {

}

public SeqStack()

{this(10);

}

回true

return this.top__== -1________; } public boolean push(E element){ //元素element 入栈，若public boolean isEmpty(){ //判断栈是否为空，若空栈返this.value=new Object[Math.abs(capacity)]; this.top=-1; 操作成功返回true

if(elem …… 此处隐藏：2041字，全部文档内容请下载后查看。喜欢就下载吧 ……