数据结构习题23501

1、2.1 概 述 是数据的基本单位，有些情况下也称为元素、结点、顶点、记录等。 是数据不可分割的最小单元，是具有独立含义的最小标识单位。例如构成一个数据元素的字段、域、属性等。2.2 何谓算法?它与程序有何区别?算法分析是对一种算法所消耗的计算机资源的估算，其中包括计算机 的长短和 的大小。2.3 何谓频度、时间复杂度、空间复杂度？说明其含义。时间复杂度的计算：2.5 题目改为“计算下列各片段程序的时间复杂度”(1) (3) (5)i=1;while(i<=n) i=i*5;i=0;s=0;while(s<n) i+; s+=i;2.2 线性表在一个具有n个结点的有序单链表中插入一个

2、新结点，使得链表仍然有序，该算法的时间复杂度是( )A.O(log2n) B.O(1) C.O(n2) D.O(n)如果某线性表中最常用的操作是取第i个结点及其前驱，则采用（ ）存储方式最节省时间。A.单链表 B.双向链表 C.单循环链表 D.顺序表写出带头结点的双向循环链表L为空表的条件（假设结点包括data, next, prior三个域）： 顺序存储的线性表不可以随机存取。 （ ）线性表的长度是线性表所占用的存储空间的大小。 （ ）2.25 2.26 (1) 写出带头结点的单链表和不带头结点的单链表的插入、删除算法，并比较。已知线性表(al，a2，an)中的元素值按递增有序排列，选用顺序

3、表结构存放，试编写算法删除线性表中的值介于c与d (cd)之间的元素。设计算法，求带头结点的循环链表的长度，如下图所示。带头结点的循环链表设计算法，在带头结点的单循环链表的第i个结点前插入元素值为x的结点。设计算法，删除带头结点的单循环链表的第i个结点。设计算法，将不带头结点的单链表(a1, a2, ., an)中的元素逆置。算法思想：另建一链表p（初值为空），依次删除原链表头指针head所指点结点插入到p表表头。2.3 栈与队循环队列首尾相连的状态是通过 运算来实现的。已知栈的输入序列为1,2,3,n，输出序列为a1, a2, , an, 符合a2=n的输出序列共有 种。已知循环队列用数组d

4、ata1n存储元素值，用f,r分别作为头尾指针，则当前元素个数为 。在解决计算机主机与打印机之间速度不匹配问题时通常设置一个打印数据缓冲区，主机将要输出的数据依次写入该缓冲区，而打印机则从该缓冲区中取走数据打印。该缓冲区应该是一个（ ）结构。A.栈 B.队 C.数组 D.线性表总结各种栈、队（顺序栈、链栈、循环队、链队）的判空、判满条件。2.22 2.5 树与二叉树将一棵树T转换为二叉树T2，则T的先序遍历序列是T2的 遍历序列，T的后序遍历序列是T2的 遍历序列一棵非空的二叉树，先序与后序遍历序列正好相反，则该二叉树满足（ ）A.无左孩子 B.无右孩子 C.叶子结点只有一个 D.任意二叉树2

5、.29 2.30 2.32 2.33 2.41程序填空题：#define MAXNUM 100typedef structkeytype key; elemtype data;sqlist;sqlist stMAXNUM;int BinarySearch( sqlist st, int n, keytype key )int mid, low, high, find;find=0; low=1;high=n;while( (low<=high)&&(find=0) ) (1) if ( key<stmid.key ) (2) else if ( key>stm

6、id.key ) (3) else (4) printf("find st%d.key=%dn",mid,key); (5) if( find=0 )return(0);/*BinarySearch*/2.6 图有n个结点的无向图的边数最多为 用邻接矩阵存储有向图，其第i行的所有元素之和等于顶点i的 。在有n个顶点的有向图中，每个顶点的度最大可达 。在一个图中，所有顶点的度数之和等于所有边数之和的（ ）倍。A. 1/2 B. 1 C. 2 D. 4对有向图进行拓扑排序，若排序后图中仍有结点未被输出，这说明图中存在 。图的广度优先搜索序列是唯一的。 （ ）无向图采用邻接矩阵表示，图中的边数等于邻接矩阵中非零元素之和的一半。（ ）对任意一个图从它的某个顶点出发进行一次深度优先或广度优先搜索遍历可访问到该图的每个顶点。 （ ）2.34 2.7 查找uu2.8 排序已知一个数据表为56，45，45*，82，60，73，请写出在进行快速排序的过程中每次划分后数据表的变化。