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

2005-12-19准备题 填空题 1．顺序表、栈和队列都是_______结构，可以在顺序表的_______位置插入和删除元素；对于栈只能在_______插入和删除元素；对于队列只能在_______插入元素和_______删除元素。 2．由头指针head指向的非空循环单链表，尾结点为p，则head和p满足条件_______________。 3．共H层的完全二叉树至少有 个结点，至多有 个结点，若按自上而下、从左到右次序给结点编号（从0开始），则编号最小的叶子结点的编号是_________。 4．n个顶点的连通图至少有 条边。 5．在无向图G的邻接矩阵A中，若A[i][j]等于1，则A[j][i]等于 6．任何一个具有n个结点的无向图的边数小于或等于_______________。 7．任何一个具有n个结点的完全有向图的边数为_______________。 8．排序方法的稳定是指___________________________________。 9．根据数据元素之间的关系，数据在计算机中的存储有两种不同的存储结构，分别是：______存储结构和______存储结构。 10．在数据结构中，数据元素之间通常有下列四类基本结构：______、________、_______和________。 11．通过衡量一个算法的______复杂度和______复杂度来进行判定一个算法的好坏。 12．线性表的最主要的两种应用是______和______，它们之间最重要的区别是：一个是__________、另一个是__________。 m*n的稀疏矩阵中，有t个元素不为零，则该矩阵的稀疏因子为______，对于稀疏矩阵，我们通常对其进行______存储。 14．字符串的五种基本操作是：串______、串______、______、串______和______。 15．在二叉树的链式存储结构中，n个结点的二叉链表中有______个空链域。 16．对于n个结点的二叉树来说，遍历时的时间复杂度为______，空间复杂度为______。 17．树的常见的三种链表结构为________表示法、________表示法和________表示法。 18．在折半查找中，查找终止的条件为________________________________。 19．Hash表的构造方法中，经统计证明最好的方法是____________法。 20．在内部排序中，利用修改指针值来代替移动记录的排序方法是___________排序。 21．按照锦标赛排序的思想，决出8个选手的名次排列，共需要进行______场比赛（考虑最坏的情况）。 22．在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; p(right=s; 2．在数据结构中，从逻辑上可以把数据结构分成_________。 A．动态结构和静态结构 B．紧凑结构和非紧凑结构 C．线性结构和非线性结构 D．内部结构和外部结构 3．算法分析的两个主要方面是。 A．空间复杂性和时间复杂性B．正确性和简明性 C．可读性和文档性D．数据复杂性和程序复杂性 ______的存储结构，线性表的链式存储结构是一种______的存储结构。 A．随机存取 B．顺序存取 C．索引存取 D．散列存取 5．向量、栈和队列都是______结构，可以在向量的________位置插入和删除元素；对于栈只能在_________插入和删除元素；对于队列只能在_______插入元素和在_______删除元素。 6．设循环队列中数组的下标范围是1~n，其头尾指针分别为f和r，则其元素个数为___________。 A．r-f B．r-f+1 C．(r-f) mod n +1 D．(r-f+n) mod n 7．将下三角矩阵A[7,7]的下三角部分逐行地存储到起始地址为1000的内存单元中(下标从0开始，不存储上三角部分)，已知每个元素占4个单元，则A[5,4]的地址是_______