数据结构习题集1

A．O(n) B．O(n*n) C．O(nlogn) D．O(n*i) 2. 已知一堆栈的进栈序列为：1234，则下列哪个序列为不可能的出栈序列（ ）。

A．1234 B．4321 C．2143 D．4123 3. 深度为5的二叉树至多有（ ）个结点.

A．16 B．32 C．31 D．10 4. 堆(HEAP)是一种（ ）。

A．二叉树 B．线性表 C．图 D．算法

5. 若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3。当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为多少？（ ）。

A．1和5 B．2和4 C．4和2 D．5和1 6. 下列哪种排序算法的平均时间复杂度为O（nlogn）（ ）。

A．简单选择排序 B．简单插入排序 C．冒泡排序 D．归并排序

7. 用冒泡排序（交换排序）算法对(12 37 42 19 27 35 56 44 10)数据进行从小到大排序。在将最大的数“沉”到最后时，数据的顺序是（ ）。

A．12 37 42 19 27 35 44 10 56 B．12 37 42 19 27 35 10 44 56 C．12 37 19 27 35 42 44 10 56 D．10 12 19 27 35 37 42 44 56 8. 下列哪种排序算法更适合于外部排序（ ）。

A．选择排序 B．插入排序 C．冒泡排序 D．归并排序 9. 数据结构中的DIJKSTRA方法是用来求（ ）。

A．关键路径 B．最短路径 C．拓扑排序 D．字符串匹配 10. 对下列二叉树进行后序遍历，其遍历结果为（ ）。

a

b c d e f

g

A．gfedcba B．dbegfca C．bdecgfa D．dbaecgf 11.稀疏矩阵（SPARSE MATRIX）一般的压缩存储方法有以下两种（ ）。

A．二维数组和三维数组 B．三元组（TRIPES）和哈希表（HASH TABLE） C．三元组（TRIPES）和十字链表（cross linked） D．哈希表和十字链表 12. 在待排序的元素基本有序的前提下，效率最高的排序方法是（ ）。

A．简单插入排序 B．简单选择排序 C．快速排序 D．归并排序 二、填空题（共16分）

1.、栈和队列都是________线性表。（2分）

2.、下三角形矩阵按行存储的下标计算公式为________(2分)，三对角矩阵按行存储的计算公式为________。（2分）

3.、（4分）在简单插入排序、希尔排序、简单选择排序、快速排序、堆排序、归并排序和基数排序中，排序是不稳定的有：________。

4.、（2分）请举例输出树形结构的两种存储方法________。

5.、（4分）按满二叉数的概念可推广出满K叉数的概念。若对满K叉树的节点逐层编号（从1开始，同层中从左到右），则编号为i的节点的父节点编号是________，编号为i的节点的第j个儿子的编号是________。 三、应用题（共34分）

1.、请对右图有向图（共10分）：

23

（1）画出相应邻接链表（adjacency list）表示法（链表中，按节点编号大小从小到大向后排）（6

分）

（2）指出按深度优先遍历算法在上述表示的基础上进行遍历的两个输出结果。（4分）

2.、对于下列二叉树（14分）

（1）请画出其对应的中序线索（thread）二叉树。（8分每个线索一

分）

（2）请将下列用于中序线索二叉树遍历的程序的空白部分填上。（6分每空3分） threaded_pointer insucc( threaded_pointer tree) {

threaded_pointer temp; temp = tree->right_child; if ( !tree->right_thread ) while(________) temp = temp->left_child; return temp; }

void tinorder ( threaded_pointer tree) { threaded_pointer temp=tree; for(; ;){ temp = insucc (temp); if (________) break; printf (\

24

} }

3.、（10分）选取哈希函数H(k)=k mod 11, 用线性探测（linear probing）冲突解决策略(H(k)+i). 试在0-10的哈希地址空间中对关键字序列(22,41,53,46,30,13,01,67)构造哈希表, 并求等概率情况下查找成功的平均查找长度。

四、（12分）下面是将删除大顶堆(MAX HEAP)堆顶元素的算法，请将空白部分填上： element delete_max_heap(int *n) { int parent,child;

element item, temp; if (HEAP_EMPTY(*n)) {

fprintf (stderr, \exit (1); }

item = heap[1];

temp = heap[________]; parent = 1; child = 2;

while (child <=*n) {

if (child < *n) && (heap[child].key< heap[child+1].key) ________;

if (temp.key >= heap[child].key) break; heap[parent] =________; parent = child; child* = 2; }

heap [parent] = temp; return item; }

五、编写计算二叉树中叶节点个数的递归函数（14分）。

数据结构模拟试题（自测二）

一、判断题

25

1．数据结构、数据元素和数据项在计算机中的映象分别为存储结构、结点和数据域。（ ） 2．二叉树是度为2的有序树。（ ）

3．用二叉树的前序遍历和中序遍历可以导出后序遍历。（ ） 4．连通分量是无向图中的极小连通子图。（ ） 5．最佳二叉树一定是平衡二叉树。（ ）

6．M阶B-树每一个结点的子树个数都大于或等于[m/2]。( )

7．快速排序的速度在所有排序方法中为最快，而且所附加空间也最小。 （ ） 8．堆排序所需的时间与待排序的记录个数无关。（ ）

9．磁盘的寻址时间是磁头找到目的磁道所需的时间。（ ）

10．存放在磁带、磁盘上的文件，既可以是顺序文件，也可以是索引结构或其它结构类型的文件。（ ）

二、单项选择题

1.具有线性结构的数据结构是（ ）。 A．广义表 B．数组 C．双端队列 D．二叉树 2.已知广义表L=（（x,y,z）,a,(u,t,w)）,从L表中取出原子 t的运算是（ ）。 A．head(tail(tail(L))) B．tail(head(head(tail(L)))) C．head(tail(head(tail(L)))) D．head(tail(head(tail(tail(L)))))

3.将一个A[1…100,1…100]的下三角矩阵，按以行优先存入一维数组B[1….298] 中，A中元素a66,65在数组中的位置k为（ ）。 A．194 B．195 C．196 D．197 4.树B的层号为la,2b,3d,3e和2c，对应下列选择中（ ）括号表示。 A．la[2b[3d,3e],2c] B．a[b[[d],e],c] C．a[b,d[e,c]] D．a[b[d,e],c] 5.在折半查找过程中，当n=2d-1时，描述查找过程的二叉树一定是深度为d的( ). A．满二叉树 B．平衡二叉树 C．完全二叉树 D．二叉排序树 6.下列（ ）排序算法在最坏情况下不会达到O（n2）. A．插入排序 B．冒泡排序 C．快速排序 D．2-路归并排序 7.快速排序在（ ）情况下最不利发挥其特长。 A．被排序的数据量太大 B．被排序中含有多个相同值 C．被排序的数据已基本有序 D．被排序的数据中有实数 三、简答题

1.试证明：若借助栈由输入序列1，2，。。。。，n得到输出序列p1,p2,…..pn

（它是输入序列的一个排列），则在输入序列中不可能出现这样的情形：存在I

设单链表中存放着n个字符，试设计算法判断字符是否中心对称。例如xyzzyx和xyzyx都是中心对称的字符串。

数据结构模拟试题（自测三）

一、判断题

1.两个字符串相等的充分必要条件是（ ）。

2.设n0为哈夫曼树的叶子结点数目，则该哈夫曼树共有（ ）个结点。

3.设有一个10阶对称矩阵A采用压缩存储方式（以行为主序存储：a11=1）,则a85的地址为（ ）。

26