数据结构全面复习与实战练习10套

需积分: 3 124 浏览量更新于2024-07-21 收藏 597KB DOC 举报

本资源是一系列针对数据结构复习的练习题集合，共计十套试卷，涵盖了数据结构课程的核心内容，旨在帮助学生巩固理论知识并准备期末考试。每套试卷包含单选题，每题2分，共计20分，涉及栈与队列的基本操作、数据结构的类型判断（如线性结构、非线性结构）、矩阵定位、树的特性应用、二叉树的层次结构分析、二分查找算法的空间复杂度、快速排序的辅助存储需求、散列函数的应用以及连通图的基本理论等。此外，还提供了每套试卷的参考答案，方便学生自我测试和解析。通过这套练习题，学习者可以系统地复习和掌握数据结构的关键概念，提升解题能力和理解深度。这些题目适合用于课后练习或者自我测验，对于理解和掌握数据结构的精髓大有裨益。

4. 设有向图 G 用邻接矩阵 A[n][n]作为存储结构，则该邻接矩阵中第 i 行上所有元素之和

等于顶点 i 的________，第 i 列上所有元素之和等于顶点 i 的________。

5. 设哈夫曼树中共有 n 个结点，则该哈夫曼树中有________个度数为 1 的结点。

6. 设有向图 G 中有 n 个顶点 e 条有向边，所有的顶点入度数之和为 d，则 e 和 d 的关系

为_________。

7. __________遍历二叉排序树中的结点可以得到一个递增的关键字序列（填先序、中序

或后序）。

8. 设查找表中有 100 个元素，如果用二分法查找方法查找数据元素 X，则最多需要比较

________次就可以断定数据元素 X 是否在查找表中。

9. 不论是顺序存储结构的栈还是链式存储结构的栈，其入栈和出栈操作的时间复杂度均

为____________。

10. 设有 n 个结点的完全二叉树，如果按照从自上到下、从左到右从 1 开始顺序编号，则

第 i 个结点的双亲结点编号为____________，右孩子结点的编号为___________。

11. 设一组初始记录关键字为(72，73，71，23，94，16，5)，则以记录关键字 72 为

基准的一趟快速排序结果为___________________________。

12. 设有向图 G 中有向边的集合 E={<1，2>，<2，3>，<1，4>，<4，2>，<4，3>}，则该

图的一种拓扑序列为____________________。

13. 下列算法实现在顺序散列表中查找值为 x 的关键字，请在下划线处填上正确的语句。

struct record{int key; int others;};

int hashsqsearch(struct record hashtable[ ],int k)

{

int i,j; j=i=k % p;

while (hashtable[j].key!=k&&hashtable[j].flag!=0){j=(____) %m; if (i==j) return(-1);}

if (_______________________ ) return(j); else return(-1);

}

14. 下列算法实现在二叉排序树上查找关键值 k，请在下划线处填上正确的语句。

typedef struct node{int key; struct node *lchild; struct node *rchild;}bitree;

bitree *bstsearch(bitree *t, int k)

{

if (t==0 ) return(0);else while (t!=0)

if (t->key==k)_____________; else if (t->key>k) t=t->lchild; else_____________;

}

三、计算题(每题 10 分，共 30 分)

1.已知二叉树的前序遍历序列是 AEFBGCDHIKJ，中序遍历序列是 EFAGBCHKIJD，画出

此二叉树，并画出它的后序线索二叉树。

2．已知待散列的线性表为（36，15，40，63，22），散列用的一维地址空间为 [0..6]，假

定选用的散列函数是 H（K）= K mod 7，若发生冲突采用线性探查法处理，试：

（1）计算出每一个元素的散列地址并在下图中填写出散列表：

` 0 1 2 3 4 5 6

（2）求出在查找每一个元素概率相等情况下的平均查找长度。

3．已知序列（10，18，4，3，6，12，1，9，18，8）请用快速排序写出每一趟排序的结果。

四、算法设计题(每题 15 分，共 30 分)

剩余41页未读，继续阅读

qq_27243353

粉丝: 0
资源: 2

数据结构全面复习与实战练习10套

数据结构经典十套卷试题及答案.doc

十套数据结构试题及答案

数据结构10套练习题及答桉

数据结构习题全套练习很好的

数据结构全套练习题

数据结构全套练习题.rar

数据结构练习：我的数据结构课程的练习程序

数据结构全套练习及答案（经典）

数据结构算法：数据结构和算法练习库

数据结构练习

最新资源