发布时间 : 星期一 文章数据结构习题集1更新完毕开始阅读
4.一个无序序可以通过构造一棵（ ）树而变成一个有序序列，构造树的过程即为对无序序列进行排序的过程。
5.如果结点A有3个兄弟，而且B是A的双亲，则B的度是（ ）。 6.高度为h的２－３树中叶子结点的数目至多为（ ）。
7.设有向图有n 个顶点和e条边，进行拓扑排序时，总的计算时间为( ). 8.外部排序中两个相对对立的阶段是（ ） 和（ ）。 二、简要回答
1.线性表有两种存储结构： 一种是顺序表，二是链式。试问：
（1） 如果有n个线性表同时并存，并且在处理过程中各表的长度会动态变化，线性表的总数也会
自动地改变。在此情况下，应选用何种存储结构？为什么？
（2） 若线性表的总数基本稳定，且很少进行插入和删除，但要求以最快的速度存取线性表的元素，
那么应采用哪种存储结构？为什么？
2.采用折半查找方法进行查找的数据文件应满足什么条件？
三、已知一棵二叉树的前序序列和中序序列分别存于两个一维数组PRE[1..n] 和INO[1..n]中，试编写算法建立该二叉树的二叉链表。
四、假设一个单循环链表。其结点含有三个域pre 、data和link。其中data为数据域；pre为指针域，它的值为空指针（NULL）;link为指针域，它指向后继结点。请设计算法，将此表改成双向循环链表。
数据结构模拟试题（自测三参考答案）
一、
1.长度相同且对应位置上的字符相同 2.2n0-1 3.33
4.二叉排序树 5.4 6.2h-1 7.O(n+e)
8.划分归并段、归并排序 二、
1.（1）应选用链式存储结构。因链式存储结构有一组任意存储空间存储线性表里的各元素，存储空间可以是连续的，也可以是不连续的。而且这种存储结构对元素进行插入和删除操作时都不必移动元素，仅仅修改指针即可，所以很适宜实现线性表的容量的变化。
（2）应选用顺序存储结构。因为顺序存储结构一旦确定了起始位置，线性表中的任何一个元素都可以进行随机存取，存取速度当然很高。而链式存储是一种顺序存取的存储结构。 2.数据文件中的记录应当按关键字有序且顺序存储的。 三、struct node{int lchild,rchild;char ch};
void bitree(char A[],struct node B[],int n) {sqstack s;int top ;int I,j,t;top=0; for(I=0;I while B[j].ch!=A[i] j++; if top==0 {top++;s[top]=j;} else if j 27 {B[s[top]].lchild=j;top++;} else {while(j>s[top])&&(top!=0) {t=s[top]; top--;} B[t].rchild=j; Top++; S[top]=j; } } } 四、设s为指向该循环链表中的某结点的指针，引进p和q作为中间结点的指针；指针s 在搜索过程中保持不变，用于循环结束条件的判断。每执行一次就将指针p赋给q所指结点pre域，并修改p和q，保持p在后，q在前。 Void doublelinks(linklist & s) {Lnode *p,*q; p=s; do{q=p->link; q->pre=p; p=q;}while(p==q); } 数据结构模拟试题（自测四） 一、选择题 １．在有n个叶子结点的哈夫曼树中，其结点总数为（ ）。 A．不确定 B．2n C．2n+1 D．2n-1 2．下列序列中，（ ）是执行第一趟快速排序得到的序列（排序的关键字类型是字符串）。 A．[da,ax,eb,de,bb]ff[ha,gc] B．[cd,eb,ax,da]ff[ha,gc,bb] C．[gc,ax,eb,cd,bb]ff[da,ha] D．[ax,bb,cd,da]ff[eb,gc,ha] 3．若线性表最常用的操作是存取第i个元素及其前趋的值，则采用（ ）存储方式节省时间。 A．单链表 B．双链表 C．单循环链表 D．顺序表 4．下列排序算法中，时间复杂度不受数据初始状态影响，恒为O（nlog2n）的是（ ）。 A．堆排序 B．冒泡排序 C．直接选择排序 D．快速排序 5．某二叉树的先序序列和后序序列正好相反，则该二叉树一定是（ ）的二叉树。 A．空或只有一个结点 B．高度等于其结点数 C．任一结点无左孩子 D．任一结点无右孩子 6．下列排序算法中，某一趟结束后未必能选出一个元素放在其最终位置上的是（ ）。 A．堆排序 C．直接插入排序 B．冒泡排序 D．快速排序 7．二叉数在线索化后，仍不能有效求解的问题是（ ）。 A．先序线索二叉树中求先序后继 B．中序线索二叉树中求中序后继 C．中序线索二叉树中求中序前驱 D．后序线索二叉树中求后序后继 8．在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡结点为A，并已知A的左孩子的平衡因子为-1，右孩子的平衡因子为0，则应作（ ）型调整以使其平衡。 A．LL B．LR C．RL D．RR 9．快速排序算法在最好情况下的时间复杂度为（ ）。 A．O(n) B．O(n2) C．O(nlog2n) D．O(log2n) 28 10．已知数据表A中每个元素距其最终位置不远，则采用（ ）排序算法最省时间。 A．堆排序 B．插入排序 C．直接选择排序 D．快速排序 11．在用邻接表表示图的情况下，建立图的算法的时间复杂度为（ ）。 A．O(n+e) B．O(n2) C．O(n×e) D．O(n3) 12．在有n个结点的二叉链表中，值为非空的链域的个数为（ ）。 A．n-1 B．2n-1 C．n+1 D．2n+1 13.带权有向图G用邻接矩阵A存储，则顶点i的入度为A中（ ）。 A．第i行非∞的元素这和 B．第i列非∞的元素之和 C．第i行非∞且非0的元素个数 D．第i列非∞且非0的元素个数 14．在有n个结点且为完全二叉树的二叉排序树中查找一个键值，其平均比较次数的数量级为（ ）。 2 A．O(n) B．O(n) C．O(nlog2n) D．O(log2n) 二、判断题 1.对任意一个图，从它的某个顶点出发进行一次深度优先或广度优先搜索遍历可访问到该图的每个顶点。（ ） 2.在索引顺序表上实现分块查找，在等概率查找情况下，其平均查找长度不公与表的个数有关，而且与每一块中的元素个数有关。（ ） 3.只有在初始数据为逆序时，冒泡排序所执行的比较次数最多。（ ） 4.图G的最小生成树的代价一定小于其他生成树的代价。（ ） 5.已知一棵树的先序序列和后序序列，一定能构造出该树。（ ） 6.对一个堆按层次遍历，不一定能得到一个有序序列。（ ） 7.设与一棵树T所对应的二叉树为BT，则与T中的叶子结点所对应的BT中的结点也一定是叶子结点。（ ） 8.任一AOE网中至少有一条关键路径，且是从源点到汇点的路径中最长的一条。（ ） 9.删除二叉排序树中一个结点，再重新插入上去，一定能得到原来的二叉排序树。（ ） 10.快速排序是排序算法中最快的一种。（ ） 三、填空题 1．取出广义表A=（（X，Y，Z），（A，B，C，D））中的原子B的函数是________。 2．在有序表A[1..20]中，中，采用二分查找算法查找元素值等于A[12]的元素，所比较过元素的下标依次为________。 3．若某串的长度小于一个常数，则采用________存储方式最节省空间。 4．在有n个顶点的有向图中，每个顶点的度最大可达________。 5．已知二叉树中叶子数为50，共有一个孩子的结点数为30，则总结点数为________。 6．在左右子树均不空的先序线索二叉树中，空链域的数目是________。 7．在二叉链表中判断某指针P所指结点为叶子结点的条件是________。 8．直接选择排序算法在最好情况下所作的交换元素的次数为________。 9．下列排序算法中，占用辅助空间最多的是________。 （堆排序，希尔排序，快速排序，归并排序） 四、应用题 1．设散函数H（k）=k，给定键值序列为13，41，15，44，6，68，12，25，38，64，试画出相应的散列表，并求在等概率下成功查找时的平均查找长度。 2．求出下面图中顶点1到其余顶点的最短路径。 29 五、算法设计题 1．编写一个算法交换单链表中P所指向的位置和其后续位置上的两个结点，HEAD指向该链表的表头，P指向该链表中的某一结点。 2．假设二叉树采用链接存储结构进行存储，ROOT指向根结点，P所指结点为任一给定的结点，编写一个求出从根结点到这所指结点之间路径的算法。 30