数据结构习题汇总(北邮)

《数据结构习题汇总(北邮)》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、2005-12-19准备题填空题1．顺序表、栈和队列都是_______结构，可以在顺序表的_______位置插入和删除元素；对于栈只能在_______插入和删除元素；对于队列只能在_______插入元素和_______删除元素。2．由头指针head指向的非空循环单链表，尾结点为p，则head和p满足条件_______________。3．共H层的完全二叉树至少有个结点，至多有个结点，若按自上而下、从左到右次序给结点编号（从0开始），则编号最小的叶子结点的编号是_________。4．n个顶点的连通图至少有条边。5．在无向图G的邻接矩阵A中，若

2、A[i][j]等于1，则A[j][i]等于6．任何一个具有n个结点的无向图的边数小于或等于_______________。7．任何一个具有n个结点的完全有向图的边数为_______________。8．排序方法的稳定是指___________________________________。9．根据数据元素之间的关系，数据在计算机中的存储有两种不同的存储结构，分别是：______存储结构和______存储结构。10．在数据结构中，数据元素之间通常有下列四类基本结构：______、________、_______和________。11．通过衡

3、量一个算法的______复杂度和______复杂度来进行判定一个算法的好坏。12．线性表的最主要的两种应用是______和______，它们之间最重要的区别是：一个是__________、另一个是__________。13．m*n的稀疏矩阵中，有t个元素不为零，则该矩阵的稀疏因子为______，对于稀疏矩阵，我们通常对其进行______存储。14．字符串的五种基本操作是：串______、串______、______、串______和______。15．在二叉树的链式存储结构中，n个结点的二叉链表中有______个空链域。16．对于n个结点的二

4、叉树来说，遍历时的时间复杂度为______，空间复杂度为______。17．树的常见的三种链表结构为________表示法、________表示法和________表示法。18．在折半查找中，查找终止的条件为________________________________。19．Hash表的构造方法中，经统计证明最好的方法是____________法。20．在内部排序中，利用修改指针值来代替移动记录的排序方法是___________排序。21．按照锦标赛排序的思想，决出8个选手的名次排列，共需要进行______场比赛（考虑最坏的情况）。22．

5、在n个元素的顺序表中插入或删除一个元素，需平均移动______个元素。选择1．在双向链表p所指结点之后插入s所指结点的操作是______________A．pàright=s;sàleft=p;pàrightàleft=s;sàright=pàright;B．pàright=s;pàrightàleft=s;sàleft=p;sàright=pàright;C．sàleft=p;sàright=pàright;pàright=s;pàrightàleft=s;D．sàleft=p;sàright=pàright;pàrightàleft=s;

6、pàright=s;2．在数据结构中，从逻辑上可以把数据结构分成_________。A．动态结构和静态结构B．紧凑结构和非紧凑结构C．线性结构和非线性结构D．内部结构和外部结构3．算法分析的两个主要方面是____。 A．空间复杂性和时间复杂性B．正确性和简明性 C．可读性和文档性D．数据复杂性和程序复杂性 4．线性表的顺序存储结构是一种______的存储结构，线性表的链式存储结构是一种______的存储结构。A．随机存取B．顺序存取C．索引存取D．散列存取5．向量、栈和队列都是______结构，可以在向量的________位置插入和删除元素；

7、对于栈只能在_________插入和删除元素；对于队列只能在_______插入元素和在_______删除元素。6．设循环队列中数组的下标范围是1~n，其头尾指针分别为f和r，则其元素个数为___________。A．r-fB．r-f+1C．(r-f)modn+1D．(r-f+n)modn7．将下三角矩阵A[7,7]的下三角部分逐行地存储到起始地址为1000的内存单元中(下标从0开始，不存储上三角部分)，已知每个元素占4个单元，则A[5,4]的地址是_____________。8．某二叉树的前序遍历结点访问顺序是abdgcefh,中序遍历的结点

8、访问顺序是dgbaechf,则其后序遍历的结点访问顺序是______A.bdgcefhaB.gdbecfhaC.bdgaechfD.gdbehfca9.串是一种特殊