数据结构复习题

数据结构复习题第一章抽象数据类型数据结构基本要素数据逻辑结构------集合、线性、树型、图数据存储结构------- 顺序、链接、散列、索引算法及其分析----时间复杂度，空间复杂度，O()练习题1 数据结构形式地定义为（D，R），其中D是_________的有限集合，R是D上的_________ 有限集合。

2 数据结构包括数据的____________、数据的_______________和数据的___________三个方面的内容。

3 计算机算法指的是（）A. 计算方法B. 排序方法C. 解决问题的有限运算序列D. 调度方法4 在数据结构中，从逻辑上可以把数据结构分为（）A. 动态结构和静态结构B. 紧凑结构和非紧凑结构C. 线性结构和非线性结构D. 内部结构和外部结构5 数据结构在计算机内存中的表示是（）A. 数据的存储结构B. 数据结构C. 数据的逻辑结构D. 数据元素之间的关系第二章线性表----（直接）前驱、（直接）后继抽象数据类型-----插入操作、删除操作顺序表-----数据元素存储地址的计算链接表（插入+删除）----结点结构：数据域+ 指针域，单链表，双向链表，循环链表链表中头结点的用途习题1设有一线性表e=(e1, e2, …, en)，其逆线性表定义为e’=(en, en-1, …, e2,e1)。

请设计一个算法，将用顺序表表示的线性表逆置，要求逆线性表仍占用原线性表的存储空间。

2写一个算法，在带头结点的单链表list中，删除p所指的结点，并返回成功与否的标志。

3一个长度为n的线性表，在其第i个元素（1≤i≤n）之前插入一个元素时，需向后移动____________个元素；删除第i个元素时，需要向前移动____________个元素。

4链表不具备的特点是（）A. 可随机访问任一结点B. 插入删除不需要移动元素C. 不必事先估计存储空间D. 所需空间与其长度成正比5 如果最常用的操作是取第i个结点及其前驱，则采用（）存储方式最节省时间。

A. 单链表 B. 双链表 C. 单向循环链表 D. 顺序表6 请分析下面代码段的功能。

typedef struct Node{Elemtype data;Struct Node *next;} Node;int Count ( Node *list, ElemType x){int i=0; Node *p=list;while(p!=NULL){if (p->data = = x)i++; p=p->next;}7 建立带头结点且有n个结点的单向链表的程序，结点中的数据域从前向后依次为1,2,3,……,n，要求创建过程中的结点的数据域依次为n, n-1, ……, 2, 1。

8 /* 单链表结点的定义*/typedef struct Node{int data ; struct Node *next; } Node;Node *create(n){ Node *head , *p; int i;p=(Node *)malloc(sizeof(Node));head=（6）;p next=NULL; /*建立头结点*/for(i=n; i>=1; i--){ p=（7）; //为节点申请内存空间p->data=i;p->next=（8）;（9）;}return(head);}算法的时间复杂度为（10）;第四章栈------（1）特点：FILO；栈顶、出栈、入栈（2）顺序栈和链栈（3）栈在递归中的作用队列—--（1）特点：FIFO；队头、队尾、出队列、入队列（2）队列的顺序存储实现和链接存储实现（3）循环队列（4）队列满和空的条件栈和队列的综合应用习题1 若已知一个栈的入栈序列是1, 2, 3, …, n，其输出序列是p1, p2, p3, …, pn，若p1=n，则pi是（）A. 1B. n-1C. n-i+1D. 不确定2 一个队列的入队顺序是1, 2, 3, 4，则队列的输出序列是（）A. 4, 3, 2, 1B. 1, 2, 3, 4C. 1, 4, 3, 2D. 3, 2, 4, 13 若用一个大小为6的数值来实现循环队列，且当前rear和front的值分别为0和3，则队列中删除一个元素，再加入两个元素后，rear和front的值分别为（）A. 1和5B. 2和4C. 4和2D. 5和15请借助于栈的作用，将循环队列的内容倒置，循环队列和栈均采用数组存储（假设队列和栈的存储空间均足够大），下图给出了将队列进行倒置的示意图。

请根据上述要求将下面的代码补充完整。

6#define MAXSIZE 100typedef struct Queue{ //队列定义Elemtype data[MAXSIZE];int front, rear; //队头指针和队尾指针，队头指针始终指向队列第一个元素的前一个位//置，队尾指针始终指向队列的最后一个元素}Queue;//栈定义typedef struct Stack{Elemtype data[MAXSIZE];int top; //栈顶指针，其始终指向栈顶元素}Stack;Queue * Reverse(Queue *q){Stack *s=(Stack *) malloc (sizeof(Stack));s->top=-1;while ( (1) ){ (2) ;(3) ;s->data[s->top]=q->data[q->front]; }while ( s->top!=-1 ){ q->rear++;(4) ;(5) ;}return q;}第五章二叉树的基本术语----（1）根结点、父结点、孩子结点、兄弟结点（2）树叶、分支结点（3）路径、路径长度（4）结点的层数（根结点的层数为0）、树的高度（5）结点的度、树的度完全二叉树、满二叉树及其性质----父节点和孩子结点编号的对应关系二叉树的存储结构---（1）顺序存储（2）二叉链表（3）三叉树表二叉树的遍历（周游）---（1）先序、中序、后序遍历（2）哈夫曼树（最优二叉树）（3）堆的基本概念及构造过程注：树部分（5.5、5.6、5.7）的内容不作为考试内容。

习题1一棵深度为6的满二叉树有___________个分支结点和__________个叶子结点。

设一棵完全二叉树有700个结点，则共有__________个叶子结点。

2 具有10个叶子结点的二叉树中有（）个度为2的结点。

A. 8B. 9C. 10D. 113 某二叉树结点的中序序列为ABCDEFG，后序序列为BDCAFGE，则其左子树中结点数目为（）A. 3 B. 2 C. 4 D. 54 某二叉树的谦虚遍历序列是abdgcefh，中序序列是dgbaechf，则其后序序列是5 设有一组初始记录关键字为（16，60，20，40，22，78），请构造一棵哈夫曼树，要求给出构造过程。

第六第七章静态查找----简单顺序查找、二分查找、分块查找动态查找----二叉排序树的定义散列表查找----（1）散列函数的构造方法：直接定址法、除留余数法（2）散列冲突：开放定址法（线性探测法）、链地址法（3）具体散列查找表的平均查找长度计算习题1折半查找有序表（4, 6, 12, 20, 28, 38, 50, 70, 88, 100），若查找表中元素20，它将依次与表中元素___________ __比较大小。

2顺序查找法适合存储结构为（）的线性表。

A. 散列存储B. 顺序存储或链式存储C. 压缩存储D. 索引存储3已知待散列的线性表为（36，15，40，63，22），散列用的一维地址空间为[0..6]，假定选用的散列函数是H（K）=K % 7，若发生冲突采用线性探查法处理，请：计算出每一个元素的散列地址并画出散列表；求出在每个元素查找概率相等情况下的平均查找长度。

第八章插入排序----直接插入排序、二分插入排序、希尔排序选择排序----直接选择排序、堆排序交换排序---冒泡排序、快速排序分配排序（基数排序）归并排序习题1 排序方法中，从未排序序列中依次取出元素与已排序序列中的元素进行比较，将其放入已排序序列的正确位置上的方法，称为（）A. 希尔排序B. 冒泡排序C. 插入排序D. 选择排序2 设一组初始记录关键字序列（5, 2, 6, 3, 8），以第一个记录关键字5为基准进行一趟快速排序的结果是（）A. 2, 3, 5, 8, 6B. 3, 2 5, 8, 6C. 3, 2, 5, 6, 8D. 2, 3, 6, 5, 83一组记录的键码为（46，79，56，38，40，84，50，42），请给出这组键码建堆的过程第九章图的定义及相关术语----（1）有向图、无向图（2）顶点的度、简单路径（3）连通图、连通分量（4）完全图图的存储结----（1）邻接矩阵（2）邻接表图的遍历----（1）深度优先（2）广度优先最小生成树----（1）克鲁斯卡尔（2）普里姆最短路径的概念拓扑排序与关键路径的概念----AOV网与AOE网习题1 在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的（）倍。

A. ½B. 1C. 2D. 42 有8个结点的无向图最多有（）边。

A. 14B. 28C. 56D. 1123 具有n个结点的连通图至少有（）条边。

A. n-1B. nC. n(n-1)/2D. 2n4 给定如下图：请画出该图的邻接矩阵，并基于给定的邻接矩阵给图其深度优先遍历序列。

5已知一个图的顶点集V和边集E分别为：V={1, 2, 3, 4, 5, 6, 7, 8};E={(1,2), (1,3), (2,4), (2,5), (3,6), (3,7), (4,8), (5,8), (6,8), (7,8)};若采用邻接表存储该图，并且每个顶点邻接表中的边结点都是按照终点序号从小到大的次序链接的，则：给出从1号顶点出发按深度优先搜索遍历的顶点序列给出从1号顶点出发按广度优先搜索遍历的顶点序列6请分别使用克鲁斯卡尔算法和普里姆算法画出下图的最小生成树。

选择题1 设栈S和队列Q的初始状态为空，元素E1、E2、E3、E4、E5和E6依次通过栈S，一个元素出栈后即进入队列Q，若6个元素出列的顺序为E2、E4、E3、E6、E5和E1，则栈S的容量至少应该是（）。

(A) 6 (B) 4 (C) 3 (D) 22 由权值分别为11，8，6，2，5的叶子结点生成一棵哈夫曼树，它的带权路径长度为 A. 24 B. 71 C. 48 D. 533 P200具有e条边的无向图，它的邻接表中有（）个边结点。