2013年1月自考数据结构导论试题[2]

在一个具有n个顶点的无向图中要连通全部顶点至少需要的边数为( )

An Bn

Cn+ D 若构造一棵具有n个结点的二叉排序树最坏的情况下其深度不超过( )

A B n

C D n+

闭散列表中由于散列到同一个地址而引起的堆积现象是( )

A由同义词之间发生沖突引起的

B由非同义词之间发生沖突引起的

C由同义词之间或非同义词之间发生沖突引起的

D由散列表溢出引起的

一个序列中有个元素若只想得到其中前个最小元素最好采用的排序方法是( )

A 快速排序 B 堆排序

C 插入排序 D 二路归并排序

在排序方法中从未排序序列中依次取出元素与已排序序列(初始时为空)中的元素进行比较将其放入已排序序列的正确位置上的方法称为( )

A希尔排序 B插入排序

C冒泡排序 D快速排序得分

二填空题(本大题共小题每小题分共分)

请在每小题的空格中填上正确答案错填不填均无分

数据的逻辑结构通常包括集合线性结构____________和图状结构

设双链表中结点的前趋指针和后继指针的域名分别为t和r指针s指向双链表中的一个结点(该结点既非头结点也非尾结点)则删除s指针所指向结点的操作为s>tl>r=s>r;和____________

对稀疏矩阵进行压缩存储的目的是节省____________

在一个具有n个结点的单链表中查找值为m的某结点若查找成功则需平均比较的结点数为____________

深度为的满二叉树上第层有____________个结点

对一棵有个结点的完全二叉树按层编号则编号为的结点它的左孩子的编号为____________

一个具有个顶点的无向完全图有____________条边

一个有向图G中若有孤和则在图G的拓扑序列中顶点ViVj和Vk的相对位置为____________

在一棵二叉排序树上按____________遍历得到的结点序列是一个有序序列

实现二分查找的存储结构仅限于顺序存储结构且其中元素排列必须是____________的

文件的检索有三种方式它们是顺序存取直接存取和____________存取

在插入排序和选择排序中若原始记录已基本有序则较适合选用____________

对n个元素的序列进行冒泡排序时最多需进行____________趟

三应用题(本大题共小题每小题分共分)

写出利用直接选择排序方法对一组关键码为()的记录进行排序时每趟排序的结果

已知一棵二叉树的中根遍历序列和后根遍历序列分别为BDAFEHGC和DBFHGECA试画出这棵二叉树

设闭散列表容量为(散列地址空间)给定表()散列函数H(K)=K mod 采用线性探测法解决沖突要求

()构造散列表;

()求查找数需要比较的次数

如题图所示在栈的输入端有个元素顺序为ABCDEF能否在栈的输出端得到序列DCFEBA及EDBFCA?若能给出栈操作的过程若不能简述其理由 题图

[] [] []