2013湖南省JAVA版数据结构试题及答案

up=!up;
}
for (int i=0; i<mat.length; i++)//输出二维数组元素
{
for (int j=0; j<mat[i].length; j++)//i、j是行、列下标
System.out.print(" "+mat[i][j]);
System.out.println();
else
{
Node<E> p=this.head;
while (p.next!=null)
p = p.next;
p.next = list.head;
}
}
【习3.5】实验2.2复制单链表。
在SinglyLinkedList单链表类中，增加构造方法如下。
public SinglyLinkedList(SinglyLinkedList<E> list)//以单链表list构造新的单链表
{
p = new Node(element[i]);
p.next = create(element, i+1);
}
return p;
}
单链表的复制操作也可设计为以下的递归方法：
public SinglyLinkedList(SinglyLinkedList<E> list)//以单链表list构造新的单链表
图3.2p.next=p将改变结点间的链接关系
【习3.1】实验2.2由指定数组中的多个对象构造单链表。
在SinglyLinkedList单链表类中，增加构造方法如下。
public SinglyLinkedList(E[] element)//由指定数组中的多个对象构造单链表

一、选择题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)%m;D.rear=(rear+1)%m;5、栈和队列的共同点是__C______A.都是先进后出B.都是先进先出C.只允许在端点处插入和删除元素D.没有共同点6、已知一堆栈的进栈序列为1234,则下列哪个序列为不可能的出栈序列______D__A.1234B.4321C.2143D.41237、具有线性结构的数据结构是（C）A．树B．图C．栈和队列D．广义表8、假设以数组A[60]存放循环队列的元素，其头指针是front=47，当前队列有50个元素，则队列的尾指针值为（B）A．3B．37C．50D．979、若栈采用链式存储结构，则下列说法中正确的是（B）A．需要判断栈满且需要判断栈空B．不需要判断栈满但需要判断栈空C．需要判断栈满但不需要判断栈空D．不需要判断栈满也不需要判断栈空10、若一棵具有n(n>0)个结点的二叉树的先序序列与后序序列正好相反，则该二叉树一定是（C）A.结点均无左孩子的二叉树B.结点均无右孩子的二叉树C.高度为n的二叉树D.存在度为2的结点的二叉树11、若一棵二叉树中度为l的结点个数是3，度为2的结点个数是4，则该二叉树叶子结点的个数是（B）A.4B.5C.7D.812、在n个结点的线索二叉树中，线索的数目为_C_______A．n-1 B.nC.n+1D.2n13、一棵完全二叉树有1001个结点,其中有____B_____叶子结点A.500B.501C.503D.50515、一个有n个顶点的无向图最多有___C____条边。

1、因为后序遍历栈中保留当前结点的祖先的信息，用一变量保存栈的最高栈顶指针，每当退栈时，栈顶指针高于保存最高栈顶指针的值时，则将该栈倒入辅助栈中，辅助栈始终保存最长路径长度上的结点，直至后序遍历完毕，则辅助栈中内容即为所求。

void LongestPath(BiTree bt)//求二叉树中的第一条最长路径长度{BiTree p=bt,l[],s[]; //l, s是栈，元素是二叉树结点指针，l中保留当前最长路径中的结点int i，top=0,tag[],longest=0;while(p || top>0){ while(p) {s[++top]=p；tag[top]=0; p=p->Lc;} //沿左分枝向下if(tag[top]==1) //当前结点的右分枝已遍历{if(!s[top]->Lc && !s[top]->Rc) //只有到叶子结点时，才查看路径长度if(top>longest) {for(i=1;i<=top;i++) l[i]=s[i]; longest=top; top--;}//保留当前最长路径到l栈，记住最高栈顶指针，退栈}else if(top>0) {tag[top]=1; p=s[top].Rc;} //沿右子分枝向下}//while(p!=null||top>0)}//结束LongestPath2、设t是给定的一棵二叉树，下面的递归程序count(t)用于求得:二叉树t中具有非空的左,右两个儿子的结点个数N2;只有非空左儿子的个数NL;只有非空右儿子的结点个数NR和叶子结点个数N0。

N2、NL、NR、N0都是全局量，且在调用count(t)之前都置为0.typedef struct node{int data; struct node *lchild,*rchild;}node;int N2,NL,NR,N0;void count(node *t){if (t->lchild!=NULL) if (1)___ N2++; else NL++;else if (2)___ NR++; else (3)__ ;if(t->lchild!=NULL)(4)____; if (t->rchild!=NULL) (5)____;}26.树的先序非递归算法。

《数据结构(Java语言版)》试卷1
一、选择题（每题5分，共25分）
1.
在Java中，哪种数据结构不支持“修改”操作？
A. ArrayList
B. LinkedList
C. HashSet
D. HashMap
2.
下列哪个算法的时间复杂度为O(nlogn)？
A. 冒泡排序
B. 快速排序
C. 插入排序
D. 选择排序
3.
以下哪个是栈（Stack）数据结构的特性？
A. 先入后出（FILO）
B. 先入先出（FIFO）
C. 按值访问
D. 按索引访问
4.
下列哪个是队列（Queue）数据结构的特性？
A. 先入后出（FILO）
B. 先入先出（FIFO）
C. 按值访问
D. 按索引访问
5.
在Java中，哪种数据结构可以存储重复的元素？
A. HashSet
B. TreeSet
C. ArrayList
D. LinkedList
6.
二、填空题（每空3分，共18分）
1.在Java中，ArrayList是基于____________实现的。

2.二叉树的深度为h，则最多有____________个节点。

3.图的遍历方法有____________和____________。

4.堆排序的时间复杂度为____________。

5.链表的特点是每个节点包含两部分：和。

三、简答题（每题10分，共20分）
1.简述数组和链表的区别。

2.简述二叉树的中序遍历过程。