数据结构作业
一、设n为整数，利用大“O”记号，求下列程序段的时间复杂度
1、i=0;k=0;
Do
{ k=k*10*i; i++;
} while (i 2、i=1; j=0; while(i+j<=n) { if(i>j) j++; else i++; } 3、x=n; //n>1 while (x>=(y+1)*(y+1)) y++; 4、x=91; y=100; while (y>0) if (x>100) {x=x-10; y- -;} else x++; 二、选择题 1、从逻辑上可以把数据结构分为（）两大类。 A．动态结构、静态结构B．顺序结构、链式结构 C．线性结构、非线性结构D．初等结构、构造型结构 2、以下数据结构中，哪一个是线性结构（）？ A．广义表 B. 二叉树 C. 稀疏矩阵 D. 串 3、在下面的程序段中，对x的赋值语句的频度为（） for (i=1;i<=n;i++) for (j=1;j<=n;j++) x=x+1; A． O(2n) B．O(n) C．O(n2) D．O(log2n) 4、下面关于线性表的叙述中，错误的是哪一个？（） A．线性表采用顺序存储，必须占用一片连续的存储单元。 B．线性表采用顺序存储，便于进行插入和删除操作。 C．线性表采用链接存储，不必占用一片连续的存储单元。 D．线性表采用链接存储，便于插入和删除操作。 5、某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（）存储方 式最节省运算时间。 A．单链表 B．仅有头指针的单循环链表 C．双链表 D．仅有尾指针的单循环链表 6、静态链表中指针表示的是（）. A．内存地址 B．数组下标 C．下一元素地址 D．左、右孩子地址 7、下面的叙述不正确的是（） A．线性表在链式存储时，查找第i个元素的时间同i的值成正比 B. 线性表在链式存储时，查找第i个元素的时间同i的值无关 C. 线性表在顺序存储时，查找第i个元素的时间同i 的值成正比 D. 线性表在顺序存储时，查找第i个元素的时间同i的值无关 8、若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为（）(1<=i<=n+1)。 A. O(0) B. O(1) C. O(n) D. O(n2) 9、在单链表指针为p的结点之后插入指针为s的结点，正确的操作是：（）。 A．p->next=s;s->next=p->next; B． s->next=p->next;p->next=s; C．p->next=s;p->next=s->next; D． p->next=s->next;p->next=s; 10、对于一个头指针为head的带头结点的单链表，判定该表为空表的条件是（） A．head==NULL B．head→next==NULL C．head→next==head D．head!=NULL 11、一个栈的输入序列为123…n，若输出序列的第一个元素是n，输出第i（1<=i<=n）个元素是（）。 A. 不确定 B. n-i+1 C. i D. n-i 12、有六个元素6，5，4，3，2，1 的顺序进栈，问下列哪一个不是合法的出栈序列？（） A. 5 4 3 6 1 2 B. 4 5 3 1 2 6 C. 3 4 6 5 2 1 D. 2 3 4 1 5 6 13、设有三个元素X，Y，Z顺序进栈（进的过程中允许出栈），下列得不到的出栈排列是( )。 A．XYZ B. YZX C. ZXY D. ZYX 14、假设以数组A[m]存放循环队列的元素,其头尾指针分别为front和rear，则当前队列中的元素个数为（）。 A．(rear-front+m)%m B．rear-front+1 C．(front-rear+m)%m D．(rear-front)%m 15、若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3，当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为多少？( ) A. 1和 5 B. 2和4 C. 4和2 D. 5和1 16、下面关于串的的叙述中，哪一个是不正确的？（） A．串是字符的有限序列 B．空串是由空格构成的串 C．模式匹配是串的一种重要运算 D．串既可以采用顺序存储，也可以采用链式存储 17、设有两个串p和q，其中q是p的子串，求q在p中首次出现的位置的算法称为（） A．求子串 B．联接 C．匹配 D．求串长 18、设有数组A[i,j]，数组的每个元素长度为3字节，i的值为1 到8 ，j的值为1 到10，数组从内存首 地址BA开始顺序存放，当用以列为主存放时，元素A[5，8]的存储首地址为( )。 A. BA+141 B. BA+180 C. BA+222 D. BA+225 19、广义表A=(a,b,(c,d),(e,(f,g))),则下面表达式的值为（）。 Head(Tail(Head(Tail(Tail(A))))) A. (g) B. (d) C. c D. d 三、判断题 1、数据元素是数据的最小单位。( ) 2、顺序存储方式的优点是存储密度大，且插入、删除运算效率高。( ) 3、线性表采用链表存储时，结点和结点内部的存储空间可以是不连续的。( ) 4、线性表的特点是每个元素都有一个前驱和一个后继。( ) 5、一个稀疏矩阵A m*n采用三元组形式表示，若把三元组中有关行下标与列下标的值互换，并把m和n的值 互换，则就完成了A m*n的转置运算。（） 6、所谓取广义表的表尾就是返回广义表中最后一个元素。（） 四、填空题 1、当线性表的元素总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素时，应采用_______存储结构。 2、线性表L=（a1,a2,…,an）用数组表示，假定删除表中任一元素的概率相同，则删除一个元素平均需要移动元素的个数是________。 3、对于一个具有n个结点的单链表，在已知的结点*p后插入一个新结点的时间复杂度为________,在给定值为x的结点后插入一个新结点的时间复杂度为________。 4、带头结点的双循环链表L中只有一个元素结点的条件是：________ 5、一个栈的输入序列是：1，2，3则不可能的栈输出序列是_______。 6、用S表示入栈操作，X表示出栈操作，若元素入栈的顺序为1234，为了得到1342出栈顺序，相应的S和X的操作串为_______。 7、________又称作先进先出表。 8、组成串的数据元素只能是________。 9、设有C语言描述的二维数组A[10][20],其每个元素占两个字节，第一个元素的存储地址为100，若按行优先顺序存储，则元素A[6][6]存储地址为_______。 五、算法设计题 1、请设计一算法：已知顺序表L，表中元素为整型且递增有序，现有一值为e的元素要插入L表，使插入后L表仍然有序。 2、已知L为非递减的顺序表，请设计算法删除L中重复的元素（即删除后使L表变为一递增表）。 3、已知带头结点的动态单链表L中的结点是按整数值递增排列的，试写一算法将值x为的结点插入到表L中，使L仍然有序。 4、设计一算法，逆置带头结点的动态单链表L。 5、在长度大于1的单循环链表中，既无头结点也无头指针。s为指向链表中某个结点的指针，试编写算法删除结点*s的直接前趋结点。 六、程序填空题 不带头结点的单链表L进行就地逆置的算法，用L返回逆置后的链表的头指针。 void reverse（linklist &L） { p=null；q=L； while（q！=null） { (1) ; q->next=p；p=q；(2)___ ; } (3)_____; } 第六章树 选择题 1．已知一算术表达式的中缀形式为 A+B*C-D/E，后缀形式为ABC*+DE/-，其前缀形式为( ) A．-A+B*C/DE B. -A+B*CD/E C．-+*ABC/DE D. -+A*BC/DE 2．算术表达式a+b*（c+d/e）转为后缀表达式后为（） A．ab+cde/* B．abcde/+*+ C．abcde/*++ D．abcde*/++ 3. 设树T的度为4，其中度为1，2，3和4的结点个数分别为4，2，1，1 则T中的叶子数为（） A．5 B．6 C．7 D．8 4. 设森林F对应的二叉树为B，它有m个结点，B的根为p,p的右子树结点个数为n,森林F中第一棵树的结 点个数是（） A．m-n B．m-n-1 C．n+1 D．条件不足，无法确定 5．若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（）A．9 B．11 C．15 D．不确定 6．具有10个叶结点的二叉树中有（）个度为2的结点， A．8 B．9 C．10 D．ll 7．一棵完全二叉树上有1001个结点，其中叶子结点的个数为（） A． 250 B． 500 C．254 D．505 E．以上答案都不对 8. 有n个叶子的哈夫曼树的结点总数为（）。 A．不确定 B．2n C．2n+1 D．2n-1 9. 一棵具有 n个结点的完全二叉树的树高度（深度）是（） A．?logn?+1 B．logn+1 C．?logn? D．logn-1 10．深度为h的满m叉树的第k层有（）个结点。(1= A．m k-1 B．m k-1 C．m h-1 D．m h-1 11．在一棵高度为k的满二叉树中，结点总数为（） A．2k-1 B．2k C．2k-1 D．?log2k?+1 12．对二叉树的结点从1开始进行连续编号，要求每个结点的编号大于其左、右孩子的编号，同一结点的左右孩子中，其左孩子的编号小于其右孩子的编号，可采用( )次序的遍历实现编号。 A．先序 B. 中序 C. 后序 D. 从根开始按层次遍历 13．树的后根遍历序列等同于该树对应的二叉树的( ). A. 先序序列 B. 中序序列 C. 后序序列 14．已知某二叉树的后序遍历序列是dabec, 中序遍历序列是debac , 它的前序遍历是（）。 A．acbed B．decab C．deabc D．cedba 15．二叉树的先序遍历和中序遍历如下：先序遍历：EFHIGJK；中序遍历: HFIEJKG 。该二叉树根的右子树的根是： A、 E B、 F C、 G D、 H 16．n个结点的线索二叉树上含有的线索数为（） A．2n B．n－l C．n＋l D．n 17．下述编码中哪一个不是前缀码（）。 A．（00，01，10，11） B．（0，1，00，11） C．（0，10，110，111） D．（1，01，000，001）18．从下列有关树的叙述中,选出5条正确的叙述（） A．二叉树中每个结点有两个子结点,而树无此限制,因此二叉树是树的特殊情况。 B．当K≥1时高度为K的二叉树至多有2k-1个结点。 C．用树的前序周游和中序周游可以导出树的后序周游。 D．线索二叉树的优点是便于在中序下查找前驱结点和后继结点。 E．将一棵树转换成二叉树后,根结点没有左子树。 F．一棵含有N个结点的完全二叉树,它的高度是?LOG2N?+1。 G．在二叉树中插入结点,该二叉树便不再是二叉树。 H．采用二叉树链表作树的存储结构,树的前序周游和其相应的二叉树的前序周游的结果是一样的。 I．哈夫曼树是带权路径最短的树,路径上权值较大的结点离根较近。 J．用一维数组存储二叉树时,总是以前序周游存储结点。 判断题： 1．完全二叉树中，若一个结点没有左孩子，则它必是树叶。 2. 二叉树只能用二叉链表表示。 3．在二叉树的第i层上至少有2i-1个结点(i>=1) 4．度为二的树就是二叉树。 5. 在中序线索二叉树中，每一非空的线索均指向其祖先结点。 填空题： 1．具有256个结点的完全二叉树的深度为______。 2．已知一棵度为3的树有2个度为1的结点，3个度为2的结点，4个度为3的结点，则该树有______个叶子结点。 3．在一棵二叉树中，度为零的结点的个数为N0,度为2的结点的个数为N2,则有N0 =______ 4．已知二叉树有50个叶子结点，则该二叉树的总结点数至少是______。 5．设F是由T1,T2,T3三棵树组成的森林,与F对应的二叉树为B,已知T1,T2,T3的结点数分别为n1,n2和n3则二叉树B的左子树中有__(1)_个结点，右子树中有_(2)__个结点。 6．如某二叉树有20个叶子结点，有30个结点仅有一个孩子，则该二叉树的总结点数为______。 算法应用题 1、已知一棵度为m的树中有n1个度为1的结点，n2个度为2的结点，……，n m个度为m的结点，问该树 中有多少个叶子结点？ 2、已知一棵满二叉树的结点个数为20到40之间的素数，此二叉树的叶子结点有多少个？ （请给出具体的推理过程） 3、请采用顺序存储方式和链式存储方式，分别写出下图所示二叉树的存储结构。 A B C D E F G H 4、求出上图所示二叉树的前序、中序和后序序列。 5、以二叉链表做存储结构，试编写按层次顺序（同一层自左至右）遍历二叉树的算法。 6、设一棵二叉树的先序、中序遍历序列分别为 先序遍历序列： A B D F C E G H 中序遍历序列： B F D A G E H C （1）画出这棵二叉树。 （2）画出这棵二叉树的中序线索树 （3）画出这棵二叉树的后序线索树 7、给定一组权值3，27，7，8，14，23，6，12 （1）试画出用Huffman算法建造的Huffman树； （2）求Huffman编码和平均编码长度（考虑概率） 8、将下列森林转化为二叉树。 9、求上述森林的前序和中序序列。 算法设计题： 1．设计算法，求前序线索树中结点P的后继 2．设计算法，求中序线索树中结点P的后继 3．用二叉链表表示的二叉树T，结点的值为整型，请设计算法，求T中结点值大于0的结点数，并作为算法的返回值。 第七章图 选择题 1．设无向图的顶点个数为n，则该图最多有（）条边。 A．n-1 B．n(n-1)/2 C． n(n+1)/2 D．0 E．n2 2．一个n个顶点的连通无向图，其边的个数至少为（）。 A．n-1 B．n C．n+1 D．nlogn； 3．一个有n个结点的图，最少有（）个连通分量，最多有（）个连通分量。 A．0 B．1 C．n-1 D．n 4．在一个无向图中，所有顶点的度数之和等于所有边数（）倍，在一个有向图中，所有顶点的入度之和等于所有顶点出度之和的（）倍。 A．1/2 B．2 C．1 D．4 5．下列哪一种图的邻接矩阵是对称矩阵？（） A．有向图 B．无向图 C．AOV网 D．AOE网 6．当一个有N个顶点的图用邻接矩阵A表示时，顶点Vi的度是（）。 A．∑ = n i j i A 1 ] ,[ B． [] ∑ = n 1 j j,i A C． ∑ = n i i j A 1 ], [ D． ∑ = n i j i A 1 ] ,[ + [] ∑ = n 1 j i,j A 7．下面哪一方法可以判断出一个有向图是否有环（回路）： A．深度优先遍历 B. 拓扑排序 C. 求最短路径 D. 广度优先遍历 8. 在图采用邻接表存储时，求最小生成树的 Prim 算法的时间复杂度为( )。 A. O(n) B. O(n+e) C. O(n2) D. O(n3) 9. 求解最短路径的Floyd算法的时间复杂度为( )。 A．O（n） B. O（n+c） C. O（n*n） D. O（n*n*n） 10．若一个有向图的邻接距阵中,主对角线以下的元素均为零,则该图的拓扑有序序列（）。 A．存在 B．不存在 11．一个有向无环图的拓扑排序序列（）是唯一的。 A．一定 B．不一定 12. 在有向图G的拓扑序列中，若顶点Vi在顶点Vj之前，则下列情形不可能出现的是（）。 A．G中有弧 C．G中没有弧 13. 在用邻接表表示图时，拓扑排序算法时间复杂度为( )。 A. O(n) B. O(n＋e) C. O(n*n) D. O(n*n*n) 14. 关键路径是事件结点网络中（）。 A．从源点到汇点的最长路径 B．从源点到汇点的最短路径 C．最长回路 D．最短回路15．下列关于AOE网的叙述中，不正确的是（）。 A．关键活动不按期完成就会影响整个工程的完成时间 B．任何一个关键活动提前完成，那么整个工程将会提前完成 C．所有的关键活动提前完成，那么整个工程将会提前完成 D．某些关键活动提前完成，那么整个工程将会提前完成 判断题 1. 有e条边的无向图，在邻接表中有e个结点。（） 2. 有向图的邻接矩阵是对称的。（） 3．任何无向图都存在生成树。（） 4. 不同的求最小生成树的方法最后得到的生成树是相同的.（） 5. 有环图也能进行拓扑排序。（） 6. 关键路径是AOE网中从源点到终点的最长路径。（） 填空题 1．具有10个顶点的无向图，边的总数最多为______。 2. 在有n 个顶点的有向图中，若要使任意两点间可以互相到达，则至少需要______条弧。 3．n 个顶点的连通无向图，其边的条数至少为______。 4．N 个顶点的连通图用邻接矩阵表示时,该矩阵至少有_______个非零元素。 5．构造连通网最小生成树的两个典型算法是______。 6. 有一个用于n 个顶点连通带权无向图的算法描述如下： （1）．设集合T1与T2，初始均为空； （2）．在连通图上任选一点加入T1； （3）．以下步骤重复n-1次： a.在i 属于T1，j 不属于T1的边中选最小权的边； b.该边加入T2。 上述算法完成后，T2中共有______条边，该算法称______算法，T2中的边构成图的______。 7．AOV 网中,结点表示______,边表示______。AOE 网中,结点表示______,边表示______。 8. 当一个AOV 网用邻接表表示时，可按下列方法进行拓扑排序。 （1）．查邻接表中入度为______的顶点，并进栈； （2）．若栈不空，则①输出栈顶元素Vj ，并退栈；②查Vj 的直接后继Vk ，对Vk 入度处理，处理方法是______； （3）．若栈空时，输出顶点数小于图的顶点数，说明有______，否则拓扑排序完成。 算法应用题 1、对n 个顶点的无向图，采用邻接矩阵表示，如何判别下列有关问题 1）图中有多少条边？ 2）任意两个顶点i 和j 是否有边相连？ 3）任意一个顶点的度是多少？ 2．设G=(V,E)以邻接表存储，试写出深度优先和广度优先序列。 3、已知一无向图的邻接矩阵如下，求该图从顶点V 1出发的广度优先遍历和深度优先遍历序列。 0 0 1 0 0 1 0 0 0 0 1 0 0 1 1 0 0 1 0 1 0 0 1 1 0 1 1 1 0 0 0 1 0 0 0 1 0 1 1 0 0 1 0 1 0 1 0 1 0 4．下图表示一个地区的通讯网，边表示城市间的通讯线路，边上的权表示架设线路花费的代价，如何选择能沟通每个城市且总代价最省的n-1条线路，画出所有可能的选择。 123 45134124Λ12324Λ 234Λ5Λ5Λ 5、对下面的有向图，试利用DIJKSTRA 算法从顶点1到其它顶点的最短路径，并写出执行该算法过程中每次循环的状态。 6、对下面的AOE 网，求出各项活动的最早开始时间e(i)和最迟开始时间l(i)，并回答：工程完成的最短时间是多少？哪些是关键活动？ 7．下图是带权的有向图G 的邻接表表示法，求： （1）．以结点V1出发深度遍历图G 所得的结点序列； （2）．以结点V1出发广度遍历图G 所得的结点序列； （3）．从结点V1到结点V8的最短路径； （4）．从结点V1到结点V8的关键路径。 第九章 查找 选择题 1、 对N 个元素的表做顺序查找时，若查找每个元素的概率相同，则平均查找长度为( ) v4 v2 v6 v5 v1 v310 10 10 15 4 30 4 20 2 15 v1 V3 V2 V5 V4 V7 V8 V9 V6 v10 5 6 6 3 3 3 4 5 5 4 2 2 4 1 A．（N+1）/2 B. N/2 C. N D. [（1+N）*N ]/2 2. 下面关于二分查找的叙述正确的是 ( ) A. 表必须有序，表可以顺序方式存储，也可以链表方式存储 B. 表必须有序且表中数据必须是整型，实型或字符型 C. 表必须有序，而且只能从小到大排列 D. 表必须有序，且表只能以顺序方式存储 3. 二叉查找树的查找效率与二叉树的( （1）)有关, 在 (（2）)时其查找效率最低 (1): A. 高度 B. 结点的多少 C. 树型 D. 结点的位置 (2): A. 结点太多 B. 完全二叉树 C. 呈单枝树 D. 结点太复杂。 4. 若采用链地址法构造散列表，散列函数为H（key）=key MOD 17，则需 (（1）) 个链表。这些链的链首 指针构成一个指针数组，数组的下标范围为 (（2）) （1） A．17 B. 13 C. 16 D. 任意 （2） A．0至17 B. 1至17 C. 0至16 D. 1至16 判断题 1．Hash表的平均查找长度与处理冲突的方法无关。 2. 若散列表的负载因子α<1，则可避免碰撞的产生。 3. 就平均查找长度而言，分块查找最小，折半查找次之，顺序查找最大。 填空题 1. 在顺序表（8,11,15,19,25,26,30,33,42,48,50）中，用二分（折半）法查找关键码值20，需做的关键码比较次数为____. 算法应用题 1. 设有一组关键字{9,01,23,14,55,20,84,27}，采用哈希函数：H（key）=key mod 7 ，表长为10，用开放地址法的二次探测再散列方法Hi=(H(key)+di) mod 10解决冲突。要求：对该关键字序列构造哈希表，并计算查找成功的平均查找长度。 2. 已知散列表的地址空间为A[0..11]，散列函数H（k）=k mod 11，采用线性探测法处理冲突。请将下列数据{25,16,38,47,79,82,51,39,89,151,231}依次插入到散列表中，并计算出在等概率情况下查找成功时的平均查找长度。 ３、对长度为20 的有序表进行二分查找，试画出它的一棵判定树，并求等概率情况下的平均查找长度。４、设散列表的长度为15，散列函数H（K）=K%13，给定的关键字序列为20，16，29，82，37，02，06，28，55，39，23，10，试写出分别用拉链法和线性探测法解决冲突时所构造的散列表，并求出在等概率情况下，这两种方法查找成功时的平均查找长度。 第十章内部排序 选择题 1．下面给出的四种排序法中( )排序法是不稳定性排序法。 A. 插入 B. 冒泡 C. 二路归并 D. 堆排序 2．下列排序算法中，其中（）是稳定的。 A. 堆排序，冒泡排序 B. 快速排序，堆排序 C. 直接选择排序，归并排序 D. 归并排序，冒泡排序 3．下面的排序算法中，不稳定的是（） A.起泡排序 B.折半插入排序 C.简单选择排序 D.希尔排序 E.基数排序 F.堆排序。 4. 在下面的排序方法中，辅助空间为O（n）的是( ) 。 A．希尔排序 B. 堆排序 C. 选择排序 D. 归并排序 5. 下列排序算法中，占用辅助空间最多的是：( ) A. 归并排序 B. 快速排序 C. 希尔排序 D. 堆排序 6．直接插入排序在最好情况下的时间复杂度为（） A． O(logn) B． O(n) C． O(n*logn) D． O(n2) 7．下列四个序列中，哪一个是堆（）。 A. 75,65,30,15,25,45,20,10 B. 75,65,45,10,30,25,20,15 C. 75,45,65,30,15,25,20,10 D. 75,45,65,10,25,30,20,15 判断题 1．内排序要求数据一定要以顺序方式存储。（） 2．排序的稳定性是指排序算法中的比较次数保持不变，且算法能够终止。（） 3．直接选择排序算法在最好情况下的时间复杂度为O（N）。（） 4．在待排数据基本有序的情况下，快速排序效果最好。（） 5．快速排序总比选择排序快。（） 填空题 1．若不考虑基数排序，则在排序过程中，主要进行的两种基本操作是关键字的______和记录的_____。2．关键码序列（ Q，H，C，Y，Q，A，M，S，R，D，F，X），要按照关键码值递增的次序进行排序，若采用初始步长为4的Shell排序法，则一趟扫描的结果是_____；若采用以第一个元素为分界元素的快速排序法，则扫描一趟的结果是______。 算法应用题 1．对下列记录进行希尔排序（增量分别为：5，3，1） 21，27，10，14，75，45，9，28，16，55，70，18，32 2．对下列记录进行一趟快速排序 30，41，15，48，60，18，77，25，43，10，12，61 3．对下列序列建成一个大根堆 21，27，10，14，75，45，9，28，16，55，70，18，32 第十二章文件 选择题 1．下述文件中适合于磁带存储的是（）。 A. 顺序文件 B. 索引文件 C. 散列文件 D. 多关键字文件 判断题 1. 文件是记录的集合，每个记录由一个或多个数据项组成，因而一个文件可看作由多个记录组成的数据结构。填空题 1. 文件可按其记录的类型不同而分成两类，即______和______文件。 2. 数据库文件按记录中关键字的多少可分成______和______两种文件。 数据结构习题 第一章绪论 1.6 在程序设计中，常用下列三种不同的出错处理方式： 1) 用exit语句终止执行并报告错误； 2) 以函数的返回值区别正确返回或错误返回； 3) 设置一个整形变量的函数参数以区别正确返回或某种错误返回。 试讨论这三种方法各自的优缺点。 1.7 在程序设计中，可采用下列三种方法实现输出和输入： 1) 通过scanf和printf语句； 2) 通过函数的参数显示传递； 3) 通过全局变量隐式传递。 试讨论这三种方法的优缺点。 1.8 设n为正整数。试确定下列各程序段中前置以记号@的语句的频度： 5) for (i = 1; i <= n; i++ ) { for (j = 1; j <= i; j++) { for (k = 1; k <= j; k++) { @ x += delta; } } } 答案：n*(n+1)*(n+2) =1+（1+2）+（1+2+3）+...+(1+2+3+...+n) =∑ =+ n i i i 1 2 / )1 ( * =1/2*∑ =+ n i i i i 1 * =n*(n+1)*(2n+1)/12 +n*(n+1)/4 =n*(n+1)*(n+2)/6 7) x = n; //n是不小于1的常数 y = 0; while (x >= (y + 1) * (y + 1)) { @ y++; } 答案：n向下取整 8) x = 91; y = 100; while (y > 0) { @ if (x > 100) { x -= 10; y--;} else { x++; } } 答案：if 执行次数为1100， if 判断内部执行为100次 1.19 试编写算法，计算i!·2i （i = 0, 1, …, n-1）的值并分别存入数组a[arrsize]的各个分量中。假设计算机中允许的整数最大值为MAXINT ，则当n > arrsize 或对某个k （0 ≤ k ≤ n-1）使k!·2k > MAXINT 时，应按出错处理。注意选择你认为较好的出错处理方法。 1.20 试编写算法求一元多项式∑==n i i i x a x 0n )(P 的值P n (x 0)，并确定算法中每一语句的执行 次数和整个算法的时间复杂度。注意选择你认为较好的输入和输出方法。本题的输入为a i （i=0, 1, …, n ）、x 0和n ，输出为P n (x 0)。 第1章绪论 一、选择题 1. 算法的计算量的大小称为计算的（）。 A．效率 B. 复杂性 C. 现实性 D. 难度 2. 算法的时间复杂度取决于（） A．问题的规模 B. 待处理数据的初态 C. A和B 3.计算机算法指的是（1），它必须具备（2）这三个特性。 (1) A．计算方法 B. 排序方法 C. 解决问题的步骤序列 D. 调度方法 (2) A．可执行性、可移植性、可扩充性 B. 可执行性、确定性、有穷性 C. 确定性、有穷性、稳定性 D. 易读性、稳定性、安全性 4．一个算法应该是（）。 A．程序 B．问题求解步骤的描述 C．要满足五个基本特性 D．A和C. 5. 下面关于算法说法错误的是（） A．算法最终必须由计算机程序实现 B.为解决某问题的算法同为该问题编写的程序含义是相同的 C. 算法的可行性是指指令不能有二义性 D. 以上几个都是错误的 6. 下面说法错误的是（） (1）算法原地工作的含义是指不需要任何额外的辅助空间 （2）在相同的规模n下，复杂度O(n)的算法在时间上总是优于复杂度O(2n)的算法（3）所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界 （4）同一个算法，实现语言的级别越高，执行效率就越低 A．(1) B.(1),(2) C.(1),(4) D.(3) 7．从逻辑上可以把数据结构分为（）两大类。 A．动态结构、静态结构 B．顺序结构、链式结构 C．线性结构、非线性结构 D．初等结构、构造型结构 8．以下与数据的存储结构无关的术语是（）。 A．循环队列 B. 链表 C. 哈希表 D. 栈 9．以下数据结构中，哪一个是线性结构（）？ A．广义表 B. 二叉树 C. 稀疏矩阵 D. 串 10．以下那一个术语与数据的存储结构无关？（） A．栈 B. 哈希表 C. 线索树 D. 双向链表 11．在下面的程序段中，对x的赋值语句的频度为（） FOR i:=1 TO n DO FOR j:=1 TO n DO x:=x+1; A． O(2n) B．O(n) C．O(n2) D．O(log2n) 12．程序段 FOR i:=n-1 DOWNTO 1 DO FOR j:=1 TO i DO IF A[j]>A[j+1] THEN A[j]与A[j+1]对换； 《数据结构-C语言版》 第一章绪论 单项选择题 1．在数据结构中，数据的基本单位是_____ ____。 A. 数据项 B. 数据类型 C. 数据元素 D. 数据变量 2．数据结构中数据元素之间的逻辑关系被称为__ ____。 A. 数据的存储结构 B. 数据的基本操作 C. 程序的算法 D. 数据的逻辑结构3．在数据结构中，与所使用计算机无关的是数据的____ ___。 A. 存储结构 B. 逻辑和物理结构 C. 逻辑结构 D. 物理结构4．在链式存储结构中，数据之间的关系是通过____ ____体现的。 A. 数据在内存的相对位置 B. 指示数据元素的指针 C. 数据的存储地址 D. 指针 5．计算算法的时间复杂度是属于一种____ ___。 A. 事前统计的方法 B. 事前分析估算的方法 C. 事后统计的方法 D. 事后分析估算的方法 6．在对算法的时间复杂度进行估计的时候，下列最佳的时间复杂度是____ __。 A. n2 B. nlogn C. n D. logn 7．设使用某算法对n个元素进行处理，所需的时间是T(n)=100nlog2n+200n+2000，则该算法的渐近时间复杂度为____ ___。 A. O(1) B. O(n) C. O(200n) D. O(nlog2n) CDCBBDD 第二章线性表 单项选择题 1．链表不具有的特点是____ ____。 A. 可随机访问任一元素 B. 插入和删除时不需要移动元素 C. 不必事先估计存储空间 D. 所需空间与线性表的长度正比 2．设顺序表的每个元素占8个存储单元。第1个单元的存储地址是100，则第6个元素占用的最后一个存储单元的地址为。 A. 139 B. 140 C. 147 D. 148 3．在线性链表存储结构下，插入操作算法。 A. 需要判断是否表满 B. 需要判断是否表空 C. 不需要判断表满 D. 需要判断是否表空和表满 4．在一个单链表中，若删除p所指结点的后继结点，则执行。 A. p->next = p->next->next; B. p->next = p->next; C. p = p->next->next; D. p = p->next; p->next = p->next->next; 5．将长度为n的单链表接在长度为m的单链表之后的算法时间复杂度为。A. O(n) B. O(1) C. O(m) D. O(m+n) 6．需要预分较大空间，插入和删除不需要移动元素的线性表，其存储结构是。 A. 单链表 B. 静态链表 C. 线性链表 D. 顺序存储方式ACCABB 填空题 1．在带表头结点的单链表中，当删除某一指定结点时，必须找到该结点的_____结点。2．在单链表中，指针p所指结点为最后一个结点的条件是。 3．将两个各有n个元素的有序表归并成一个有序表，其最少的比较次数是。4．在一个长度为n的顺序表中第i个元素（1≤i≤n）之前插入一个元素时，需向后移动元素的个数是。 5．在长度为n的顺序表中插入一个元素的时间复杂度为。 1前驱 2 p->next==NULL 第十一章文件 一、选择题 1. 散列文件使用散列函数将记录的关键字值计算转化为记录的存放地址，因为散列函数是一对一的关系，则选择好的（）方法是散列文件的关键。【哈尔滨工业大学 2001二、5 （2分）】 A. 散列函数 B. 除余法中的质数 C. 冲突处理 D. 散列函数和冲突处理 2. 顺序文件采用顺序结构实现文件的存储，对大型的顺序文件的少量修改，要求重新复制整个文件，代价很高，采用（）的方法可降低所需的代价。【北京邮电大学 2000 二、 8 （20/8分）】 A. 附加文件 B. 按关键字大小排序 C. 按记录输入先后排序 D. 连续排序 3. 用ISAM组织文件适合于（）。【中科院软件所 1998】 A．磁带 B．磁盘 4．下述文件中适合于磁带存储的是（）。【中科院计算所 2000 一、7（2分）】 A. 顺序文件 B. 索引文件 C. 散列文件 D. 多关键字文件 5. 用ISAM和VSAM组织文件属于（）。 A. 顺序文件 B. 索引文件 C. 散列文件 【中国科技大学 1998 二、5（2分）中科院计算所 1998 二、5（2分）】 6. ISAM文件和VASM文件属于（）。【山东大学 2001 二、5 (1分)】 A. 索引非顺序文件 B. 索引顺序文件 C. 顺序文件 D. 散列文件 7. B+树应用在（）文件系统中。【北京邮电大学 2001 一、1（2分）】 A. ISAM B. VSAM 二、判断题 1. 文件是记录的集合，每个记录由一个或多个数据项组成，因而一个文件可看作由多个记录组成的数据结构。【长沙铁道学院 1998 一、5 (1分)】 2. 倒排文件是对次关键字建立索引。【南京航空航天大学 1997 一、10（1分）】 3. 倒排序文件的优点是维护简单。【南京航空航天大学 1995 五、10（1分）】 4. 倒排文件与多重表文件的次关键字索引结构是不同的。【西安交通大学 1996 二、6 (3分)】 5. Hash表与Hash文件的唯一区别是Hash文件引入了‘桶’的概念。【南京航空航天大学1996六10(1分）】 6. 文件系统采用索引结构是为了节省存储空间。【北京邮电大学 2000 一、10 （1分）】 7. 对处理大量数据的外存介质而言，索引顺序存取方法是一种方便的文件组织方法。 【东南大学 2001 一、1-10 （1分）】 8. 对磁带机而言，ISAM是一种方便的稳健组织方法。【中科院软件所 1997 一、10（1分）】 9. 直接访问文件也能顺序访问，只是一般效率不高。【北京邮电大学 2002 一、10（1分）】 10. 存放在磁盘，磁带上的文件，即可以是顺序文件，也可以是索引结构或其他结构类型的文件。 【山东大学 2001 一、7 (1分)】 11. 检索出文件中的关键码值落在某个连续的范围内的全部记录，这种操作称为范围检索。对经常需要做范围检索的文件进行组织，采用散列法优于顺序检索法。【中山大学 1994 一、 数据结构课程作业_A 交卷时间：2017-08-09 10:08:51 一、单选题 1. (7分)设有一个二维数组A[m][n]，假设A[0][0]存放位置在644(10)，A[2][2]存放位置在676(10)，每个元素占一个空间，问A[3][3](10)存放在什么位置脚注(10)表示用10进制表示。 A. 688 B. 678 C. 692 D. 696 纠错 得分： 7 知识点：第五章 展开解析 答案 C 解析第五章第二节综合题目 2. (7分)若有18个元素的有序表存放在一维数组A[19]中，第一个元素放A[1]中，现进行二分查找，则查找A［3］的比较序列的下标依次为( ) A. 1，2，3 B. 9，5，2，3 C. 9，5，3 D. 9，4，2，3 纠错 得分： 0 知识点：第九章 展开解析 答案 D 解析第九章第一节有序表的查找 (7分)设某完全无向图中有n个顶点，则该完全无向图中有（）条边。 A. n(n-1)/2 B. n(n-1) C. n2 D. n2-1 纠错 得分： 7 知识点：第七章 展开解析 答案 A 解析第七章第一节综合题目 4. (7分)若在任意一棵二叉树中，有n0个叶子结点，有n2个度为2的结点，则：n0=_____ A. n2+1 B. n2-1 C. n2+2 D. n2-2 纠错 得分： 7 知识点：第六章 展开解析 答案 A 解析第六章第二节二叉树的性质 5. (7分)栈的插入和删除操作在（）进行。 A. 栈顶 B. 栈底 C. 任意位置 D. 指定位置 得分： 7 知识点：第三章 展开解析 答案 A 解析第三章第一节栈的表示和实现 6. (7分)设有序表中有1000个元素，则用二分查找查找元素X最多需要比较（）次。 A. 25 B. 10 C. 7 D. 1 纠错 得分： 7 知识点：第九章 展开解析 答案 B 解析第九章第一节有序表的查找 7. (7分)设某棵二叉树的高度为10，则该二叉树上叶子结点最多有（）。 A. 20 B. 256 C. 512 D. 1024 纠错 得分： 7 知识点：第六章 展开解析 答案 C 解析第六章第六节二叉树的性质 知识点： 01．绪论 02．顺序表 03．链表 04．栈 05．链队列 06．循环队列 07．串 08．数组的顺序表示 09．稀疏矩阵 10．广义表 11．二叉树的基本概念 12．二叉树遍历、二叉树性质 13．树、树与二叉树的转换 14．赫夫曼树 15．图的定义、图的存储 16．图的遍历 17．图的生成树 18．静态查找（顺序表的查找、有序表的查找） 19．动态查找（二叉排序树、平衡树、B树） 20．哈希查找 21．插入排序（直接插入、折半插入、2路插入、希尔排序）22．选择排序（简单选择、树形选择、堆排序） 23．快速排序、归并排序 101A1（1）．数据的逻辑结构是（A）。 A．数据的组织形式B．数据的存储形式C．数据的表示形式D．数据的实现形式 101A1（2）．组成数据的基本单位是（C）。 A．数据项B．数据类型C．数据元素D．数据变量 101B1（3）．与顺序存储结构相比，链式存储结构的存储密度（B）。 A．大B．小C．相同D．以上都不对 101B2（4）．对于存储同样一组数据元素而言，（D）。 A．顺序存储结构比链接结构多占空间B．在顺序结构中查找元素的速度比在链接结构中查找要快C．与链接结构相比，顺序结构便于安排数据元素D．顺序结构占用整块空间而链接结构不要求整块空间101B2（5）．下面程序的时间复杂度为（B）。 x=0； for（i=1；i 第1章绪论 1. 填空 （1）（）是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。 （2）（）是数据的最小单位，（）是讨论数据结构时涉及的最小数据单位。 （3）从逻辑关系上讲，数据结构主要分为（）、（）、（）和（）。 （4）数据的存储结构主要有（）和（）两种基本方法，不论哪种存储结构，都要存储两方面的内容：（）和（）。 （5）算法具有五个特性，分别是（）、（）、（）、（）、（）。 （6）在一般情况下，一个算法的时间复杂度是（）的函数。 （7）设待处理问题的规模为n，若一个算法的时间复杂度为一个常数，则表示成数量级的形式为（），若为n*log25n，则表示成数量级的形式为（）。 2. 选择题 ⑴顺序存储结构中数据元素之间的逻辑关系是由（）表示的，链式存储结构中的数据元素之间的逻辑关系是由（）表示的。 A 线性结构 B 非线性结构 C 存储位置 D 指针 ⑵假设有如下遗产继承规则：丈夫和妻子可以相互继承遗产；子女可以继承父亲或母亲的遗产；子女间不能相互继承。则表示该遗产继承关系的最合适的数据结构应该是（）。 A 树 B 图 C 线性表 D 集合 ⑶算法指的是（）。 A 对特定问题求解步骤的一种描述，是指令的有限序列。 B 计算机程序 C 解决问题的计算方法 D 数据处理 ⑷下面（）不是算法所必须具备的特性。 A 有穷性 B 确切性 C 高效性 D 可行性 ⑸算法分析的目的是（），算法分析的两个主要方面是（）。 A 找出数据结构的合理性 B 研究算法中输入和输出的关系 C 分析算法的效率以求改进 D 分析算法的易读性和文档性 E 空间性能和时间性能 F 正确性和简明性 G 可读性和文档性H 数据复杂性和程序复杂性 3. 判断题 （1）算法的时间复杂度都要通过算法中的基本语句的执行次数来确定。 （2）每种数据结构都具备三个基本操作：插入、删除和查找。 （3）逻辑结构与数据元素本身的内容和形式无关。 （4）基于某种逻辑结构之上的基本操作，其实现是唯一的。 4. 分析以下各程序段，并用大O记号表示其执行时间。 排序算法（19） 1.以单链表为存储结构，写一个直接选择排序算法。 2.设计一算法，使得在尽可能少的时间内重排数组，将所有取负值的关键字放在所有取非负值的关 键字之前。请分析算法的时间复杂度。 3.写一个双向冒泡排序的算法，即在排序过程中交替改变扫描方向。 4. 4.下面是一个自上往下扫描的冒泡排序的伪代码算法，它采用lastExchange 来记录每趟扫描中进 行交换的最后一个元素的位置，并以它作为下一趟排序循环终止的控制值。请仿照它写一个自下往上扫描的冒泡排序算法。 void BubbleSort(int A[],int n) //不妨设A[0..n-1]是整型向量 int lastExchange,j,i=n-1; while (i>0) lastExchange=0; for(j=0;j if([j+1] 交换A[j]和A[j+1]; lastExchange=j; } i=lastExchange;//将i置为最后交换的位置 }//endwhile }//BubbleSort 5.改写快速排序算法，要求采用三者取中的方式选择划分的基准记录；若当前被排序的区间长度小于等于3时，无须划分而是直接采用直接插入方式对其排序。 6.对给定的j(1 ≤ j ≤ n ),要求在无序的记录区R[1..n]中找到按关键字自小到大排在第j个位置上的记录(即在无序集合中找到第j个最小元)，试利用快速排序的划分思想编写算法实现上述的查找操作。 7.以单链表为存储结构，写一个直接选择排序算法。 8.写一个heapInsert(R,key)算法，将关键字插入到堆R中去，并保证插入R后仍是堆。提示：应为堆R增加一个长度属性描述(即改写本章定义的SeqList类型描述，使其含有长度域)；将key先插入R 中已有元素的尾部(即原堆的长度加1的位置，插入后堆的长度加1)，然后从下往上调整，使插入的关键字满足性质。请分析算法的时间。 9.写一个建堆算法：从空堆开始，依次读入元素调用上题中堆其中。 10.写一个堆删除算法：HeapDelete(R,i),将R[i]从堆中删去，并分析算法时间，提示：先将R[i]和堆中最后一个元素交换，并将堆长度减1，然后从位置i开始向下调整，使其满足堆性质。 .栈通常采用的两种存储结构是______________________ .用链表表示线性表的优点是_______________________ 8.在单链表中，增加头结点的目的是___________________ 9.循环链表的主要优点是________________________- 12.线性表的顺序存储结构和线性表的链式存储结构分别是__________________________ 13.树是结点的集合，它的根结点数目是_____________________ 14.在深度为5的满二叉树中，叶子结点的个数为_______________ 15.具有3个结点的二叉树有（_____________________ 16.设一棵二叉树中有3个叶子结点，有8个度为1的结点，则该二叉树中总的结点数为____________________ 17.已知二叉树后序遍历序列是dabec，中序遍历序列是debac，它的前序遍历序列是____________________________ 18.已知一棵二叉树前序遍历和中序遍历分别为ABDEGCFH和DBGEACHF，则该二叉树的后序遍历为______________________ 19.若某二叉树的前序遍历访问顺序是abdgcefh，中序遍历访问顺序是dgbaechf，则其后序遍历的结点访问顺序是_______________________ 20.数据库保护分为：安全性控制、完整性控制、并发性控制和数据的恢复。 在计算机中，算法是指_______________________ 算法一般都可以用哪几种控制结构组合而成_____________________ .算法的时间复杂度是指______________________ 5. 算法的空间复杂度是指__________________________ 6. 算法分析的目的是__________________________ 第 1 章 绪 论 (2005-07-14) - 第 1 章 绪 论 课后习题讲解 1. 填空 ⑴（ ）是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。 【解答】数据元素 ⑵（ ）是数据的最小单位，（ ）是讨论数据结构时涉及的最小数据单位。 【解答】数据项，数据元素 【分析】数据结构指的是数据元素以及数据元素之间的关系。 ⑶ 从逻辑关系上讲，数据结构主要分为（ ）、（ ）、（ ）和（ ）。 【解答】集合，线性结构，树结构，图结构 ⑷ 数据的存储结构主要有（ ）和（ ）两种基本方法，不论哪种存储结构，都要存储两方面的内容：（ ）和（）。 【解答】顺序存储结构，链接存储结构，数据元素，数据元素之间的关系 ⑸ 算法具有五个特性，分别是（ ）、（ ）、（ ）、（ ）、（ ）。 【解答】有零个或多个输入，有一个或多个输出，有穷性，确定性，可行性 ⑹ 算法的描述方法通常有（ ）、（ ）、（ ）和（ ）四种，其中，（ ）被称为算法语言。 【解答】自然语言，程序设计语言，流程图，伪代码，伪代码 ⑺ 在一般情况下，一个算法的时间复杂度是（ ）的函数。 【解答】问题规模 ⑻ 设待处理问题的规模为n，若一个算法的时间复杂度为一个常数，则表示成数量级的形式为（ ），若为 n*log25n，则表示成数量级的形式为（ ）。 【解答】Ο(1)，Ο(nlog2n) 【分析】用大O记号表示算法的时间复杂度，需要将低次幂去掉，将最高次幂的系数去掉。 2. 选择题 ⑴ 顺序存储结构中数据元素之间的逻辑关系是由（ ）表示的，链接存储结构中的数据元素之间的逻辑关系是由（ ）表示的。 A 线性结构 B 非线性结构 C 存储位置 D 指针 【解答】C，D 【分析】顺序存储结构就是用一维数组存储数据结构中的数据元素，其逻辑关系由存储位置（即元素在数组中的下标）表示；链接存储结构中一个数据元素对应链表中的一个结点，元素之间的逻辑关系由结点中的指针表示。 ⑵ 假设有如下遗产继承规则：丈夫和妻子可以相互继承遗产；子女可以继承父亲或母亲的遗产；子女间不能相互继承。则表示该遗产继承关系的最合适的数据结构应该是（ ）。 A 树 B 图 C 线性表 D 集合 【解答】B 【分析】将丈夫、妻子和子女分别作为数据元素，根据题意画出逻辑结构图。 ⑶ 算法指的是（ ）。 A 对特定问题求解步骤的一种描述，是指令的有限序列。 B 计算机程序 C 解决问题的计算方法 D 数据处理 【解答】A 【分析】计算机程序是对算法的具体实现；简单地说，算法是解决问题的方法；数据处理是通过算法完成的。所以，只有A是算法的准确定义。 ⑷ 下面（ ）不是算法所必须具备的特性。 A 有穷性 B 确切性 C 高效性 D 可行性 【解答】C 【分析】高效性是好算法应具备的特性。 ⑸ 算法分析的目的是（ ），算法分析的两个主要方面是（ ）。 A 找出数据结构的合理性 B 研究算法中输入和输出的关系 C 分析算法的效率以求改进 D 分析算法的易读性和文档性 E 空间性能和时间性能 F 正确性和简明性 G 可读性和文档性 H 数据复杂性和程序复杂性 第一章绪论 一、选择题 1.D 2.C 3.C 4.B 5.D 6.C 7.D 8.C 9.A 10.D 11.D 12.B 二、填空题 1. 逻辑结构存储结构运算 2. 集合结构线性结构树形结构图状结构 3. 有穷性. 确定性. 可行性. 输入. 输出 4. 顺序存储. 链式存储 5. 数据元素 6. 线性结构非线性结构 三、简答题 1. 尽管算法的含义与程序非常相似，但两者还是有区别的。首先，一个程序不一定满 有穷性，因为它不是一个算法。其次，程序中的指令必须是计算机可以执行的，而 算法中的指令却无此限制。如果一个算法采用机器可执行的语言来书写，那么它就 是一个程序。 2. 数据结构是指数据对象以及该数据对象集合中的数据元素之间的相互关系（数据元 素的组织形式）。例如：队列的逻辑结构是线性表（先进后出）；队列在计算机中 既可以采用顺序存储也可以采用链式存储；队列可进行删除数据元素. 插入数据元 素. 判断是否为空队列，以及队列置空等操作。 3. 数据元素之间的逻辑关系，也称为数据的逻辑结构。数据元素以及它们之间的相互 关系在计算机存储器内的表示（又称映像）称为数据的存储结构，也称数据的物理 结构。 4. 算法是对特定问题求解步骤的一种描述，它是指令的有限序列，其中每一条指令表 示一个或者多个操作。此外，一个算法还具有下列5个特性： （1）有穷性：一个算法必须在执行有穷步之后结束，即算法必须在有限时间内完 成。 （2）确定性：算法中每一步必须有明确的含义，不会产生二义性。并且，在任何 条件下，算法只有唯一的一条执行路径，即对于相同的输入只能得出相同的输出。 （3）可行性：一个算法是能执行的，即算法中的每一步都可以通过已经实现的基 本运算执行有限次得以实现。 （4）输入：一个算法有零个或者多个输入，它们是算法开始时对算法给出的初始 量。 （5）输出：一个算法有一个或者多个输出，它们是与输入有特定关系的量 5. 举例说明四种基本结构的区别: 集合: 数据元素之间无任何关系,如集合A={x,5,t,&}; 线性结构: 数据元素之间存在一个对一个的关系,如线性表L=（2,3，4,5,7,10）； 树形结构: 数据元素之间存在一个对多个的关系,如文件系统目录管理； 图状结构: 数据元素之间存在多个对多个的关系,如教学计划课程安排顺序图。 四. 算法设计题 9-12章数据结构作业答案 第九章查找 选择题 1、对n个元素的表做顺序查找时，若查找每个元素的概率相同，则平均查找长度为( A ) A．（n+1）/2 B. n/2 C. n D. [（1+n）*n ]/2 2. 下面关于二分查找的叙述正确的是 ( D ) A. 表必须有序，表可以顺序方式存储，也可以链表方式存储 B. 表必须有序且表中数据必须是整型，实型或字符型 C. 表必须有序，而且只能从小到大排列 D. 表必须有序，且表只能以顺序方式存储 3. 二叉查找树的查找效率与二叉树的( （1）C)有关, 在 (（2)C ）时其查找效率最低 (1): A. 高度 B. 结点的多少 C. 树型 D. 结点的位置 (2): A. 结点太多 B. 完全二叉树 C. 呈单枝树 D. 结点太复杂。 4. 若采用链地址法构造散列表，散列函数为H（key）=key MOD 17，则需 (（1）A) 个链表。 这些链的链首指针构成一个指针数组，数组的下标范围为 (（2）C) （1） A．17 B. 13 C. 16 D. 任意 （2） A．0至17 B. 1至17 C. 0至16 D. 1至16 判断题 1．Hash表的平均查找长度与处理冲突的方法无关。 (错) 2. 若散列表的负载因子α<1，则可避免碰撞的产生。（错） 3. 就平均查找长度而言，分块查找最小，折半查找次之，顺序查找最大。（错） 填空题 1. 在顺序表（8,11,15,19,25,26,30,33,42,48,50）中，用二分（折半）法查找关键码值20， 需做的关键码比较次数为 4 . 算法应用题 1. 设有一组关键字{9,01,23,14,55,20,84,27}，采用哈希函数：H（key）=key mod 7 ，表长 为10，用开放地址法的二次探测再散列方法Hi=(H(key)+di) mod 10解决冲突。要求：对该关 键字序列构造哈希表，并计算查找成功的平均查找长度。 2. 已知散列表的地址空间为A[0..11]，散列函数H（k）=k mod 11，采用线性探测法处理冲 突。请将下列数据{25,16,38,47,79,82,51,39,89,151,231}依次插入到散列表中，并计算出在 等概率情况下查找成功时的平均查找长度。 ３、对长度为20 的有序表进行二分查找，试画出它的一棵判定树，并求等概率情况下的平均 查找长度。 ４、设散列表的长度为15，散列函数H（K）=K%13，给定的关键字序列为20，16，29，82，37，02，06，28，55，39，23，10，试写出分别用拉链法和线性探测法解决冲突时所构造的散 列表，并求出在等概率情况下，这两种方法查找成功时的平均查找长度。 1.数据的四种存储结构是( ) A.顺序存储结构、链接存储结构、索引存储结构和散列存储结构 B.线性存储结构、非线性存储结构、树型存储结构和图型存储结构 C.集合存储结构、一对一存储结构、一对多存储结构和多对多存储结构 D.顺序存储结构、树型存储结构、图型存储结构和散列存储结构 2.若对某线性表最常用的操作是在最后一个结点之后插入一个新结点或删除最后一个结点，要使操作时间最少， 下列选项中，应选择的存储结构是( ) A.无头结点的单向链表 B.带头结点的单向链表 C.带头结点的双循环链表 D.带头结点的单循环链表 3.若带头结点的单链表的头指针为head，则判断链表是否为空的条件是( ) A.head=NULL B.head->next=NULL C.head!=NULL D.head->next!=head 7.若一棵二叉树的前序遍历序列与后序遍历序列相同，则该二叉树可能的形状是( ) A.树中没有度为2的结点 B.树中只有一个根结点 C.树中非叶结点均只有左子树 D.树中非叶结点均只有右子树 8.若根结点的层数为1，则具有n个结点的二叉树的最大高度是( ) A.n B. C. +1 D.n/2 9.在图G中求最小生成树可以采用的算法是( ) A.迪杰斯特拉（Dijkstra）算法 B.克鲁斯卡尔（Kruskal）算法 C.深度优先遍历(DFS)算法 D.广度优先遍历(BFS)算法 10.下图G=(V,E)是一个带权连通图，G的最小生成树的权为( ) A.15 B.16 C.17 D.18 11.在下图中，从顶点1出发进行深度优先遍历可得到的序列是( ) A.1 2 3 4 5 6 7 B.1 4 2 6 3 7 5 C.1 4 2 5 3 6 7 D.1 2 4 6 5 3 7 12.如果在排序过程中不改变关键字相同元素的相对位置，则认为该排序方法是( ) A.不稳定的 B.稳定的 C.基于交换的 D.基于选择的 13.设有一组关键字(19, 14, 23, 1，6，20, 4，27, 5，11, 10, 9)，用散列函数H(key)=key%13构造散列表，用拉链法解 决冲突，散列地址为1的链中记录个数为( ) A.1 B.2 C.3 D.4 14.已知二叉树结点关键字类型为字符，下列二叉树中符合二叉排序树性质的是( ) 习题二 ⒉１描述以下四个概念的区别：头指针变量，头指针，头结点，首结点（第一个结点）。解：头指针变量和头指针是指向链表中第一个结点（头结点或首结点）的指针；在首结点之前附设一个结点称为头结点；首结点是指链表中存储线性表中第一个数据元素的结点。若单链表中附设头结点，则不管线性表是否为空，头指针均不为空，否则表示空表的链表的头指针为空。 2.2简述线性表的两种存储结构有哪些主要优缺点及各自使用的场合。 解：顺序存储是按索引直接存储数据元素，方便灵活，效率高，但插入、删除操作将引起元素移动，降低了效率；而链式存储的元素存储采用动态分配，利用率高，但须增设表示结点之间有序关系的指针域，存取数据元素不如顺序存储方便，但结点的插入和删除十分简单。顺序存储适用于线性表中元素数量基本稳定，且很少进行插入和删除，但要求以最快的速度存取线性表中的元素的情况；而链式存储适用于频繁进行元素动态插入或删除操作的场合。 2.3 在头结点为h的单链表中，把值为b的结点s插入到值为a的结点之前，若不存在a，就把结点s插入到表尾。 Void insert(Lnode *h,int a,int b) {Lnode *p,*q,*s; s=(Lnode*)malloc(sizeof(Lnode)); s->data=b; p=h->next; while(p->data!=a&&p->next!=NULL) {q=p; p=p->next; } if (p->data==a) {q->next=s; s->next=p;} else {p->next=s; s->next=NULL; } } 2.4 设计一个算法将一个带头结点的单链表A分解成两个带头结点的单链表A和B，使A中含有原链表中序号为奇数的元素，而B中含有原链表中序号为偶数的元素，并且保持元素原有的相对顺序。 Lnode *cf(Lnode *ha) {Lnode *p,*q,*s,*hb; int t; p=ha->next; q=ha; t=0; hb=(Lnode*)malloc(sizeof(Lnode)); s=hb; while(p->next!=NULL) {if (t==0) {q=p;p=p->next;t=1;} else {q->next=p->next; p->next=s->next; s->next=p; s=p; p=p->next; t=0; } } s->next=NULL; return (hb); } 第一章绪论 一、选择题 1.数据结构是一门研究非数值计算的程序设计问题中计算机的1以及它们之间的2和运算等的学科。1 A.数据元素 B.计算方法 C.逻辑存储 D.数据映像 2 A.结构 B.关系 C.运算 D.算法 2.数据结构被形式地定义为(K, R)，其中K是1的有限集，R是K上的2有限集。 1 A.算法 B.数据元素 C.数据操作 D.逻辑结构 2 A.操作 B.映像 C.存储 D.关系 3.在数据结构中，从逻辑上可以把数据结构分成。 A.动态结构和静态结构 B.紧凑结构和非紧凑结构 C.线性结构和非线性结构 D.内部结构和外部结构 4.线性结构的顺序存储结构是一种1的存储结构，线性表的链式存储结构是一种2的存储结构。A.随机存取 B.顺序存取 C.索引存取 D.散列存取 5.算法分析的目的是1，算法分析的两个主要方面其一是指2，其二是指正确性和简单性。1 A.找出数据结构的合理性 B.研究算法中的输入和输出的关系 C.分析算法的效率以求改进 D.分析算法的易懂性和文档性 2 A.空间复杂度和时间复杂度 B.研究算法中的输入和输出的关系 C.可读性和文档性 D.数据复杂性和程序复杂性k 6.计算机算法指的是1，它必须具备输入、输出和2等5个特性。 1 A.计算方法 B.排序方法 C.解决问题的有限运算序列 D.调度方法 2 A.可执行性、可移植性和可扩充性 B.可行性、确定性和有穷性 C.确定性、有穷性和稳定性 D.易读性、稳定性和安全性 7.线性表的逻辑顺序与存储顺序总是一致的，这种说法。A.正确 B.不正确 8线性表若采用链式存储结构时，要求内存中可用存储单元的地址。 A.必须连续的 B.部分地址必须连续的 C.一定是不续的D连续不连续都可以 9.以下的叙述中，正确的是。A.线性表的存储结构优于链式存储结构 B.二维数组是其数据元素为线性表的线性表C.栈的操作方式是先进先出D.队列的操作方式是先进后出10.每种数据结构都具备三个基本运算：插入、删除和查找，这种说法。A.正确B.不正确 二、填空题1.数据逻辑结构包括三种类型、和，树形结构和图形结构合称为。2.在线性结构中，第一个结点前驱结点，其余每个结点有且只有个前驱结点；最后一个结点后续结点，其余每个结点有且只有个后续结点。3.算法的五个重要特性是、、、、。 4.下面程序段的时间复杂度是。 for( i = 0; i < n; i++) for( j = 0; j < m; j++) A[i][j] = 0; 5.下面程序段的时间复杂度是。 i = s = 0; while ( s < n) { i ++; /* i = i +1*/ s += i; /* s = s + i*/ } 6.下面程序段的时间复杂度是。 s = 0; for( i = 0; i < n; i++) for( j = 0; j < n; j++) s += B[i][j]; sum = s; 7.下面程序段的时间复杂度是。 i = 1; while ( i <= n ) i = i * 3; 《数据结构》习题集 第一章序论 思考题： 1.1简述下列术语：数据、数据元素、数据对象、数据结构、存储结构、数据类型、抽象数据类型 作业题： 1.2设有数据结构（D，R），其中 D={d1, d2, d3, d4 } R={r1, r2} r1={ (5) x=n; y=0; //n是不小于1的常数 while(x>=(y+1)*(y+1)){ △y++; } (6) x=91; y=100; while ( y>0 ) { △if(x>100) { x-=10; y--; } else x++ ; } (7) for( i=0; i 第六章习题 1．试分别画出具有3个结点的树和3个结点的二叉树的所有不同形态。 2．对题1所得各种形态的二叉树，分别写出前序、中序和后序遍历的序列。 3．已知一棵度为k的树中有n1个度为1的结点，n2个度为2的结点，……，n k个度为k的结点，则该树中有多少个叶子结点并证明之。 4.假设一棵二叉树的先序序列为EBADCFHGIKJ，中序序列为ABCDEFGHIJK，请画出该二叉树。5．已知二叉树有50个叶子结点，则该二叉树的总结点数至少应有多少个？ 6．给出满足下列条件的所有二叉树： ①前序和后序相同 ②中序和后序相同 ③前序和后序相同 7．n个结点的K叉树，若用具有k个child域的等长链结点存储树的一个结点，则空的Child域有多少个？ 8．画出与下列已知序列对应的树Ｔ： 树的先根次序访问序列为GFKDAIEBCHJ； 树的后根次序访问序列为DIAEKFCJHBG。 9．假设用于通讯的电文仅由8个字母组成，字母在电文中出现的频率分别为： 0.07，0.19，0.02，0.06，0.32，0.03，0.21，0.10 请为这8个字母设计哈夫曼编码。 10．已知二叉树采用二叉链表存放,要求返回二叉树T的后序序列中的第一个结点指针,是否可不用递归且不用栈来完成?请简述原因. 11. 画出和下列树对应的二叉树： 12．已知二叉树按照二叉链表方式存储，编写算法，计算二叉树中叶子结点的数目。 13．编写递归算法：对于二叉树中每一个元素值为x的结点，删去以它为根的子树，并释放相应的空间。 14．分别写函数完成：在先序线索二叉树T中，查找给定结点*p在先序序列中的后继。在后序线索二叉树T中，查找给定结点*p在后序序列中的前驱。 15．分别写出算法，实现在中序线索二叉树中查找给定结点*p在中序序列中的前驱与后继。16．编写算法，对一棵以孩子-兄弟链表表示的树统计其叶子的个数。数据结构作业
数据结构第1章作业
数据结构复习题目和答案
数据结构习题及答案-第11章 文件
数据结构课程作业
数据结构习题库汇总
数据结构作业第1章
数据结构习题
经典数据结构面试题(含答案)
数据结构第一章课后习题与答案
数据结构1-4章习题答案
数据结构(C语言版)9-12章练习 答案 清华大学出版社
数据结构习题2011级
数据结构上机例题及答案
数据结构作业及答案
数据结构习题
数据结构课后习题及解析第六章
相关主题
文本预览