数据结构与算法复习题

一、填空题

1、 数据结构被形式地定义为（ D, R），其中D 是 的有限集合， R 是D 上的 有限集合。

2、 数据结构包括数据的 、数据的 和数据的 这三个方面的内容。 3、 写出带头结点的双向循环链表L 为空表的条件 。 4、 在具有n个元素的循环队列中，队满时具有 个元素。 5、 求子串在主串中首次出现的位置的运算称为 。 6、 由3个结点所构成的二叉树有 种形态。 7、 数据的逻辑结构是指 。 二、选择题

1、若某线性表中最常用的操作是取第i 个元素和找第i个元素的前驱，则采用（ ）存储方法最节省时间。

A.顺序表 B.单链表 C.双链表 D.单循环链表 2、二叉树的前序序列和后序序列正好相反，则该二叉树一定是（ ）的二叉树。 A.空或只有一个结点 B.高度等于其结点数 C.任一结点无左孩子 D.任一结点无右孩子

3、计算机算法指的是：（ ） A. 计算方法 B. 排序方法 4、栈和队列的主要区别在于（ ）。

A.它们的逻辑结构不一样 B.它们的存储结构不一样 C.所包含的运算不一样 D.插入删除运算的限定不一样 5、为5个使用频率不等的字符设计哈弗曼编码，不可能的方案是（ ）。 A.000,001,010,011,1 B. 0000,0001,001,01,1 C.000,001,01,10,11 D.00,100,101,110,111

6、用深度优先遍历方法遍历一个有向无环图，并在深度优先遍历算法中按退栈次序打印出相应的顶点，则输出的顶点序列是（ ）。

A.逆拓扑有序 B.拓扑有序 C.无序 D.顶点编号次序

7、对如图所示的无向连通网图从顶点d开始用Prim算法构造最小生成树，在构造过程中加

C. 解决问题的有限运算序列

D. 调度方法

入最小生成树的前4条边依次是（ ）。

A. （d,f）4, (f,e) 2 , (f,b) 3 (b,a) 5 B. （f,e）2, (f,b) 3 , (a,c) 3 (f,d) 4 C. （d,f）4, (f,e) 2 , (a,c) 3 (b,a) 5 D. （d,f）4, (d,b) 5 , (f,e) 2 (b,a) 5

8、在采用线性探测法处理冲突所构成的闭散列表上进行查找，可能要探测多个位置，在查找成功的情况下，所探测的这些位置的键值（ ）。

A.一定都是同义词 B.一定都不是同义词 C.不一定都是同义词 D.都相同 9、二叉排序树中，最小值结点的（ ）。

A．左指针一定为空 B．右指针一定为空 C．左右指针均为空 D．左右指针均不为空

10、数据序列{8，9，10，4，5，6，20，1，2}只能是（ ）的两趟排序后的结果。 A.选择排序 B.冒泡排序 C.插入排序 D.堆排序 三、判断题

1、线性表的逻辑顺序总是与其物理顺序一致。（ ）

2、当待排序序列初始有序时，简单选择排序的时间复杂性为O(n)。（ ） 3、对稀疏矩阵进行压缩存储是为了节省存储空间。（ ） 4、边数很少的稀疏图，适宜用邻接矩阵表示。（ ） 5、二叉树是一棵无序树。( )

6、对于一棵具有n个结点，其高度为h的二叉树，进行任一种次序遍历的时间复杂度为O(n)。( )

7、当待排序序列初始有序时，快速排序的时间复杂性为O(n)。（ ） 8、顺序表的空间利用率高于链表。（ ）

9、哈希查找法中解决冲突问题的常用方法是除留余数法。（ ）

10、顺序查找法适用于存储结构为顺序或链接存储的线性表。（ ）

四、名词解释 1、数据： 2、存储结构分为： 3、算法的五个重要特性： 4、栈： 5、完全二叉树： 五、简答题

1、由二叉树的中序序列及前序序列能唯一的建立二叉树，试问前序序列及后序序列是否也能唯一的建立二叉树，不能则举例说明理由。

2、关键码集合 {47, 7, 29, 11, 16, 92, 22, 8, 3}，散列函数为H(key)=key mod 11，用拉链法处理冲突，构造开散列表，并求查找成功时的平均查找长度。 3. 已知数据序列为（12，5，9，20，6，31，24），对该数据序列进行排序，写出简单选择排序以及快速排序每趟的结果。 4、程序分析填空题

（1）函数GetElem 实现返回单链表的第i 个元素，请在空格处将算法补充完整。

int GetElem(LinkList L,int i,Elemtype *e){ LinkList p ;int j; p=L->next;j=1; while(p&&j(1) ;++j; } if(!p||j>i) return ERROR;

*e= (2) ; return OK; }

（2）、函数实现单链表的插入算法，请在空格处将算法补充完整。

int ListInsert(LinkList L,int i,ElemType e){ LNode *p,*s; int j; p=L;j=0;

while((p!=NULL)&&(jnext;j++; }

if(p==NULL||j>i-1) return ERROR; s=(LNode *)malloc(sizeof(LNode)); s->data=e;

(1) ; (2) ; return OK; }/*ListInsert*/

《数据结构与算法》复习题B（专升本）

一、填空题

1、数据结构按逻辑结构可分为两大类，它们分别是 和 。 2、线性结构中元素之间存在 关系，树形结构中元素之间存在 关系，图形结构中元素之间存在多对多关系。

3、带头结点的单链表head 为空的条件是 。

4、两个串相等的充分必要条件是两个串的长度相等且 。 5、二维数组，可以按照 和 两种不同的存储方式。 6、一棵具有257个结点的完全二叉树，它的深度为 。

7、内部排序方法按排序采用的策略可划分为五类： 、 、 、 和基数排序。 二、选择题

1、计算机算法必须具备输入、输出和（ ）等5 个特性。 A. 可行性、可移植性和可扩充性 C. 确定性、有穷性和稳定性

B.可行性、确定性和有穷性 D. 易读性、稳定性和安全性

2、串与普通的线性表相比较，它的特殊性体现在（ ）。 A. 顺序的存储结构

B. 链式存储结构 D. 数据元素任意

C. 数据元素是一个字符

3、以下与数据的存储结构无关的术语是（ ）。

A．循环队列 B. 链表 C. 哈希表 D. 栈 4、以下属于逻辑结构的是（ ）。

A．顺序表 B. 哈希表 C.有序表 D.单链表

5、将一棵有100 个结点的完全二叉树从根这一层开始，每一层上从左到右依次对结点进行编号，根结点的编号为1，则编号为49 的结点的左孩子编号为（ ）。 A. 98

B. 99 C. 50 D. 48

6、已知关键码序列{78，19，63，30，89，84，55，69，28，83}采用基数排序，第一趟排序后的关键码序列为（）

A. {19，28，30，55，63，69，78，83，84，89} B. {28，78，19，69，89，63，83，30，84，55}

C. {30，63，83，84，55，78，28，19，89，69} D. {30，63，83，84，55，28，78，19，69，89}

7、在一个长度为n 的顺序表中，在第i 个元素之前插入一个新元素时，需向后移动（ ）个元素。

A. n-i B. n-i+1 8、空串和空格串（ ）。

A. 相同 B. 不相同

C. 可能相同 D. 无法确定 C. n-i-1

D. i

9、常对数组进行两种基本操作是（ ）。

A. 建立和删除 B. 索引和修改 C. 查找和修改 D. 查找与索引 10、二叉树的深度为k ，则二叉树最多有（ ）个结点。

A. 2k B. 2 k-1 C. 2 k-1 D. 2k-1

三、判断题

1、 线性表的顺序存储优于链式存储。（ ）

2、用邻接矩阵存储一个图时，在不考虑压缩存储的情况下，所占用的存储空间大小只与图中的顶点个数有关，而与图的边数无关。 ( )

3、当向一个最小堆插入一个具有最小值的元素时，该元素需要逐层向上调整，直到被调整到堆顶位置为止。（ ）

4、采用不同的遍历方法，所得到的无向图的生成树是不同的。（ ） 5、有回路的有向图不能完成拓扑排序。( )

6、若让元素1,2,3依次进栈，则出栈次序1,3,2是不可能出现的情况。（ ） 7、在线性链表中删除中间的结点时，只需将被删结点释放。（ ） 8、线性表若采用链式存储表示, 在删除时不需要移动元素。（ ） 9、采用不同的遍历方法，所得到的无向图的生成树总是相同的。（ ） 10、递归的算法简单、易懂、容易编写，而且执行效率也高。（ ） 四、名词解释 1、算法： 2、队列： 3、满二叉树：

4、连通图： 5、数据项： 五、简答题

1、已知一棵度为m的树中有：n1个度为1的结点，n2个度为2的结点，……nm个度为m的结点，问该树中共有多少个叶子结点？

2、 已知一个AOV网如图所示，写出所有的拓扑序列。

v0v1v5v2v3v4v6

3、已知数据序列为(12,5,9,20,6,31,24)，对该数据序列进行排序，写出直接插入排序、堆排序每趟的结果。

4、程序分析填空题 （1）、函数ListDelete_sq 实现顺序表删除算法，请在空格处将算法补充完整。

int ListDelete_sq(Sqlist *L,int i){ int k;

if(i<1||i>L->length) return ERROR; for(k=i-1;klength-1;k++)

L->slist[k]= （1） ; （2） ; return OK;

}

（2）函数实现单链表的删除算法，请在空格处将算法补充完整。

int ListDelete(LinkList L,int i,ElemType *s){

LNode *p,*q; int j; p=L;j=0;

while(( （1） )&&(jp=p->next;j++;

}

if(p->next==NULL||j>i-1) return ERROR;

q=p->next;

（2） ; *s=q->data; free(q); return OK;

}/*listDelete*/