数据结构复习资料1

1．算法的效率可分为 时间 效率和空间效率。

2．向一个长度为n的顺序表的第i个数据元素（0≤i≤n）之前插入一个数据元素时，需向后移动 n-i+1 个数据元素。

3． 队列 是被限定为只能在表的一端进行插入操作，在表的另一端进行删除操作的线性表。

4．设字符串S=″I□AM□A□STUDENT″（其中□表示空格字符），则S的长度为____14_______。

5．一棵有n个叶子的哈夫曼树的结点总数为 2n-1 个。 6．在树形结构中，没有后继的结点是 叶子 结点 7．含n个顶点的无向连通图中至少含有 n-1 条边。

8．n个顶点的无向图G用邻接矩阵A［n］［n］存储，其中第i列的所有元素之和等于顶点Vi的__|n-i|__。 9．对一组整数{60，40，90，20，10，70，50，80}进行直接插入排序时，当把第4个整数20插入到有序表中时，为寻找插入位置需比较 5 次。 10．在数据存放无规律的线性表中进行查找的最佳方法是 顺序查找 。

1. 设循环队列的容量为30（序号从0到29），现经过一系列的入队和出队操作后，有①front=11，rear=19 ②front=19，rear=11；问在这两种情况下，循环队列的长度各是多少？ ①19-11=8 ②30-(19-11)-1=21

2. 已知一棵二叉树如图所示，请写出先根序、中根序和后根序遍历序列。

先根序：ABDEGCF

中根序：DBEGAFC 后根序：DGEBFCA

3. 已知一个无向图的邻接表如下图所示，试写出从顶点0出发分别进行深度优先和广度优先搜索遍历得到的顶点序列。

4. 试写出一组键值（46，58，15，45，90，18，10，62）应用直接插入排序算法从小到大排序后各趟的结果。

第一趟：[46],58,15,45,90,18,10,62

1

0 3 6 4 2 5 1 深度优先：0361425 广度优先：0235614 第二趟：[46,58],15,45,90,18,10,62

5．（1） 第三趟：[15,46,58],45,90,18,10,62

45 第四趟：[15,45,46,58],90,18,10,62

第五趟：[15,45,46,58,90],18,10,62

57 23 第六趟：[15,18,45,46,58,90],10,62

第七趟：[10,15,18,45,46,58,90],62

66 36 49 18 第八趟：[10,15,18,45,46,58,62,90]

5. 已知一棵二叉排序树如图所示。

7 请回答下列问题：

(1)画出插入元素23后的树结构。

5．（2） (2)请画出在原图中删除元素57后的树结构。 45 18 66

7 49 36

1. 下面程序实现二分查找算法。 Typedef struct{

KeyType key；

InfoType otherinfo； }SeqList[N+1]；

int BinSearch(SeqList R, int n，KeyType K) { int low=1，high=n；

while( low

mid=(1ow+high)／2；

if( R.list[i].key==R[mid].key )

return mid；

if(R[mid]．key>K)

high=mid-1； else

low=mid+1 ；

}

return O； } ／／BinSearch

2. 以下运算实现在链队上的入队操作，请在” “处用适当的语句予以填空。

Void EnQueue(QueptrTP * lq,DataType x) {LqueueTp *p;

p=( LqueueTp *)malloc(sizeof(Lqueue Tp)); P->data =x; P—>next=NULL;

(lq—>rear) —>next = P ; rear++ ; }

2

已知二叉树采用二叉链表存储，其结点结构定义如下： typedef struct Node{

DataType data；

struct Node *lchild，*rchild； }*BiTree；

试分别写出二叉树的先根遍历和中根遍历的递归算法。 先根遍历：

void Preorder(BiTree *T) {

if(T) {

printf(“%d”,T->key); Preorder(T->lchild); preorder(T->rchild); } }

中根遍历：

void Inorder(BiTree *T) {

if(T) {

Inorder(T->lchild); printf(“%d”,T->key); Inorder(T->rchild); } }

3

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说教育文库数据结构复习资料1在线全文阅读。