2014澳门特别行政区JAVA版数据结构考资料

1、假设K1，„，Kn是n个关键词，试解答：

试用二叉查找树的插入算法建立一棵二叉查找树，即当关键词的插入次序为K1，K2，„，Kn时，用算法建立一棵以LLINK / RLINK 链接表示的二叉查找树。

2、有一种简单的排序算法，叫做计数排序（count sorting）。这种排序算法对一个待排序的表(用数组表示)进行排序，并将排序结果存放到另一个新的表中。必须注意的是，表中所有待排序的关键码互不相同，计数排序算法针对表中的每个记录，扫描待排序的表一趟，统计表中有多少个记录的关键码比该记录的关键码小，假设针对某一个记录，统计出的计数值为c，那么，这个记录在新的有序表中的合适的存放位置即为c。

(1) (3分)给出适用于计数排序的数据表定义;

(2) (7分)使用Pascal或C语言编写实现计数排序的算法；

(3) (4分)对于有n个记录的表，关键码比较次数是多少?

(4) (3分)与简单选择排序相比较，这种方法是否更好?为什么?

3、本题要求建立有序的循环链表。从头到尾扫描数组A，取出A[i]（0<=i

LinkedList creat(ElemType A[],int n)

//由含n个数据的数组A生成循环链表，要求链表有序并且无值重复结点

{LinkedList h;

h=(LinkedList)malloc(sizeof(LNode));//申请结点

h->next=h; //形成空循环链表

for(i=0;i

{pre=h;

p=h->next;

while(p!=h && p->data

{pre=p; p=p->next;} //查找A[i]的插入位置

if(p==h || p->data!=A[i]) //重复数据不再输入

{s=(LinkedList)malloc(sizeof(LNode));

1、设单链表中指针p指着结点A，若要删除A之后的结点（若存在），则需要修改指针的操

作为（ A ）。

A）p->next=p->next->next B）p=p->next

C）p=p->nexe->next D）p->next=p

2、设给定问题的规模为变量n，解决该问题的算法所需时间为Tn=O(f(n)),Tn表示式中记号

O表示（ A ）。

A）一个数量级别 B）一个平均值

C）一个最大值 D）一个均方值

3、若采用邻接矩阵法存储一个n个顶点的无向图，则该邻接矩阵是一个（ D ）。

A）上三角矩阵 B) 稀疏矩阵

C) 对角矩阵 D) 对称矩阵

4、若采用邻接矩阵法存储一个n个顶点的无向图，则该邻接矩阵是一个（ D ）。

A）上三角矩阵 B) 稀疏矩阵

C) 对角矩阵 D) 对称矩阵

5、已知栈的最大容量为4。若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行,

则可能出现的出栈序列为（ C ）。

A) 5，4，3，2，1，6 B) 2，3，5，6，1，4

C) 3，2，5，4，1，6 D) 1，4，6，5，2，3

6、若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点的个数是( B )。

A）9 B）11 C）15 D）不能确定

7、如果结点A有3个兄弟，而且B为A的双亲，则B的度为（ B ）。

A）3 B）4 C）5 D）1

8、广义表A=（A,B,(C,D),(E,(F,G))），则head(tail(head(tail(tail(A)))))=（ D ）。

A） (G) B） (D) C） C D） D

9、下面程序段的时间复杂度是( A )。

s =0;

for( i =0; i

for(j=0;j

s +=B[i][j];

sum = s ;

A） O(n2) B） O(n)

C） O(m*n) D）O(1)

10、下面程序段的时间复杂度是( A )。

1、n个顶点的图的最小生成树必定（ D ），是不正确的描述。

A）不唯一 B）权的总和唯一

C）不含回路 D）有n条边

2、数据结构中，在逻辑上可以把数据结构分成（ B ）。

A）动态结构和静态结构

B）线性结构和非线性结构

C）紧凑结构和非紧凑结构 D）内部结构和外部结构

3、数据结构研究的内容是（ D ）。

A）数据的逻辑结构 B）数据的存储结构

C）建立在相应逻辑结构和存储结构上的算法 D）包括以上三个方面

4、栈进行插入和删除操作的特点是（ A ）。

A）LIFO B）FIFO

C）FCFS D）HPF

5、采用链结构存储线性表时，其地址（ B ）。

A）必须是连续的 B）连续不连续都可以

C）部分地址必须是连续 D）必须是不连续的

6、二叉树第i(i≥1)层上至多有（ C ）结点。 A）2i B）2i C）2i-1 D）2i-1

7、对待排序的元素序列进行划分，将其分为左、右两个子序列，再对两个子序列施加同样的

排序操作，直到子序列为空或只剩一个元素为止。这样的排序方法是（ A ）。

A）直接选择排序 B）直接插入排序 C）快速排序 D）起泡排序

8、已知栈的最大容量为4。若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行,

则可能出现的出栈序列为（ C ）。

A) 5，4，3，2，1，6 B) 2，3，5，6，1，4 C) 3，2，5，4，1，6 D) 1，4，6，5，2，3

9、在一棵度为3的树中，度为3的结点个数为2，度为2的结点个数为1，则度为0的结点

个数为（ C ）。

A）4 B）5 C）6 D）7

10、n个顶点，e条边的有向图的邻接矩阵中非零元素有（ C ）个。

A）n B）2e C）e D） n+e

11、在数据结构中，从逻辑上可以把数据结构分为（ C ）。 A）动态结构和静态结构 B）紧凑结构和非紧凑结构

C）线性结构和非线性结构 D）内部结构和外部结构

机密★启用前

江苏大学2004年硕士研究生入学考试试题

考试科目：数据结构

考生注意：答案必须写在答题纸上，写在试题及草稿纸上无效！

一、单项选择题（每小题2分，共20分）

1. 在数据结构中,从存储结构上可以把数据结构分成（ ）

A.顺序存储和链式存储 B.紧凑结构和非紧凑结构

C.线性结构和非线性结构 D.动态结构和静态结构

2. 线性表是n个( )的有限序列。

A. 字符 B. 数据元素 C. 数据项 D. 信息项

3. 一个栈的入栈序列是1,2,3,4,5,则栈的不可能的输出序列是（ ）。

A. 43512 B. 54321 C. 12345 D. 45321

4. 用不带头结点的单链表存储队列，其队头指针指向队头结点，队尾指针指向队尾结点，则在进行出队操作时（）

A. 仅修改队头指针 B. 仅修改队尾指针

C. 队头，队尾指针都可能要修改 D. 队头，队尾指针都要修改

5. 数组A中，每个元素A的长度为3个字节，行下标i从1到8，列下标j从1到10，

从首地址SA开始连续存放在存储器中，该数组按行存放时，元素A[8][6]的起始地址为（ ）

A.SA＋141 B.SA＋144 C.SA＋222 D.SA＋225

6. 设高度为h的二叉树只有度为0和度为2的结点，则此类二叉树中所包含的结点数至少为（ ）

A.2h B.2h＋1 C.2h-1 D. h-1

7. 对二叉排序树进行( )遍历，可以得到该二叉树所有结点构成的排序序列。

A. 前序 B. 中序 C. 后序 D. 层次