2022年期末数据结构复习习题 .pdf

《2022年期末数据结构复习习题 .pdf》由会员分享，可在线阅读，更多相关《2022年期末数据结构复习习题 .pdf（18页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、1 数据结构练习题数据结构练习题（ 15 章）一、选择题1、从逻辑上 可以把数据结构分为（ C ）两大类。A动态结构、静态结构B顺序结构、链式结构C线性结构、非线性结构D初等结构、构造型结构2、以下数据结构中，哪一个是线性结构（ D ）？A广义表 B. 二叉树 C. 稀疏矩阵 D. 串3、在下面的程序段中，对x 的赋值语句的频度为（ C ）for (i=1;i=n;i+) for (j=1;j=n;i+) x=x+1; A O(2n) BO(n) CO(n2) DO(log2n) 4、下面关于线性表的叙述中，错误的是哪一个？（ B ）A线性表采用顺序存储，必须占用一片连续的存储单元。B线性表采

2、用顺序存储，便于进行插入和删除操作。C线性表采用链接存储，不必占用一片连续的存储单元。D线性表采用链接存储，便于插入和删除操作。5、某线性表中最常用的操作是在最后一个元素之后 插入一个元素和删除第一个元素，则采用（ D ）存储方式最节省运算时间。A单链表 B仅有头指针的单循环链表 C 双链表 D仅有尾指针的单循环链表6、 静态链表中指针表示的是（ B ）. A 内存地址 B数组下标 C 下一元素地址 D左、右孩子地址7、下面的叙述 不正确 的是（ BC ）A线性表在链式存储时，查找第i 个元素的时间同 i 的值成正比 B. 线性表在链式存储时，查找第i 个元素的时间同 i 的值无关C. 线性表

3、在顺序存储时，查找第i 个元素的时间同 i 的值成正比D. 线性表在顺序存储时，查找第i 个元素的时间同 i 的值无关8、 若长度为 n 的线性表采用顺序存储结构，在其第i 个位置插入一个新元素的算法的时间复杂度为（ C ）(1=inext=s;s-next=p-next; B s-next=p-next;p-next=s; Cp-next=s;p-next=s-next; D p-next=s-next;p-next=s; 10、对于一个头指针为head 的带头结点的单链表，判定该表为空表的条件是（ B ）Ahead=NULL B headnext=NULL Cheadnext=head D

4、 head!=NULL 11、 一个栈的输入序列为123,n，若输出序列的第一个元素是n，输出第 i （1=i( 空格串是由空格组成的 ) C模式匹配是串的一种重要运算 D 串既可以采用顺序存储，也可以采用链式存储17、设有两个串 p 和 q，其中 q 是 p 的子串，求 q 在 p 中首次出现的位置的算法称为 （ C ）A求子串 B联接 C匹配 D求串长18、 设有数组 Ai,j，数组的每个元素长度为3 字节，i 的值为 1 到 8 ，j 的值为 1 到 10，数组从内存首地址BA 开始顺序存放，当用以 列为主存放 时，元素A5，8 的存储首地址为( B )。30*6180A. BA+141

5、 B. BA+180 C. BA+222 D. BA+225 19、已知广义表 L=（ （x,y,z ） ，a， （u，t ，w） ） ，从 L 表中取出原子项t 的运算是（ D ） 。A. head （tail（tail（L） ） ） B. tail（head（head（tail（L） ） ） ）C. head （tail（head（tail（L） ） ） ） D. head（tail(head（tail（tail（L） ） ）) ）20、广义表 A=(a,b,(c,d),(e,(f,g),则下面式子的值为（ D ） 。Head(Tail(Head(Tail(Tail(A) A. (g) B

6、. (d) C. c D. d 二、判断题1、 数据元素是数据的最小单位。( ) 2、算法可以用不同的语言描述，如果用C 语言或 PASCAL 语言等高级语言来描述，则算法实际上就是程序了。 ( Y ) 3、 顺序存储方式的优点是存储密度大，且插入、删除运算效率高。( ) 4、线性表采用链表存储时，结点和结点内部的存储空间可以是不连续的。( ) 5、线性表的特点是每个元素都有一个前驱和一个后继。( )6、一个稀疏矩阵Am*n采用三元组形式表示，若把三元组中有关行下标与列下标的值互换，并把 m和 n 的值互换，则就完成了Am*n的转置运算。（ ）7、所谓取广义表的表尾就是返回广义表中最后一个元素

7、。（ ）三、填空题1、数据的 物理结构 包括数据元素的表示和关系的表示。2、当线性表的元素总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素时，应采用_顺序_存储结构。3、线性表 L=（a1,a2, ,an ）用数组表示，假定删除表中任一元素的概率相同，则删除一个元素平均需要移动元素的个数是_(n-1)/2_ 。4、对于一个具有n 个结点的单链表，在已知的结点*p 后插入一个新结点的时间复杂度为_O(1)_, 在给定值为 x 的结点后插入一个新结点的时间复杂度为_ O(n)_ 。5、带头结点的双循环链表L 中只有一个元素 结点的条件是： _L-next-next=L

8、_ 6、一个栈的输入序列是：1，2，3 则不可能的 栈输出序列是 _3 1 2_ 。7、用 S表示入栈操作， X表示出栈操作，若元素入栈的顺序为1234，为了得到 1342 出栈顺序，相应的 S和 X的操作串为 _ SXSSXSXX_。8、_队列_又称作 先进先出 表。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 18 页 - - - - - - - - - 3 9、组成 串的数据元素 只能是 _字符_。10、设有 C语言描述的二维数组A1020,其每个元素占两个字节

9、，第一个元素的存储地址为 100，若按行优先 顺序存储，则元素 A66存储地址为 _352_。(没说明，则下标从 0 开始) 四、算法与应用题1. 设线性表存放在向量Aarrsize的前 elenum 个分量中且递增有序，试写一算法将x 插入到线性表的适当位置，以保持线性表的有序性并分析其时间复杂度。#define arrsize 100 bool sortinsert(Elemtype A,int elenum , Elemtype x) int i; if(elenum = = arrsize) printf(“该数组向量已满” ) ；return false; i=elenum-1; w

10、hile(Aix & i=0) Ai+1=Ai; i- -; Ai+1=x; return true; / 2. 已知带头结点的动态单链表L 中的结点是按整数值递增排列的，试写一算法将值x 为的结点插入到表 L中，使 L 仍然有序。/ 线性表的单链表存储结构 typedef struct Lnode ElemType data; struct Lnode *next; LNode , *LinkList; LinkList sortinsert(LinkList L,int x) /* 带头结点 */ LinkList p,q, s; s=(LinkList)malloc(sizeof(LNo

11、de); if(!s) printf(“动态空间分配不成功” ) ； exit(-1); s-data=x; q=L; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 18 页 - - - - - - - - - 4 p=L-next; while ( p!=NULL & p-data next; s-next=q-next; q-next=s ; return L; 3. 在长度大于 1 的单循环链表L 中，既无头结点也无头指针。s 为指向链表中某个结点的指针，试编写算

12、法删除结点*s 的直接前趋结点。/ 条件是长度大于一#include using namespace std; typedef struct Lnode ElemType data; struct Lnode *next; LNode , *LinkList; bool delete_prior(LinkList s) LinkList p; LinkList q; q=s; p=s-next; while(p-next!=s) q=p; p=p-next; q-next =s; delete p; 五、程序填空题1、 下面是用 c 语言编写的对不带头结点的单链表进行就地逆置的算法，该算法用L

13、 返回逆置后的链表的头指针，试在空缺处填入适当的语句。void reverse（linklist &L） p=null ；q=L；while （q！=null ） (1) L=L-next ; q-next=p；p=q；(2) q=L _ ; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 18 页 - - - - - - - - - 5 (3) L=p； 2、对单链表中元素按插入方法排序的C语言描述算法如下，其中L 为链表头结点指针。请填充算法中标出的空白处，完成其功能

14、。 （10分）typedef struct node int data; struct node *next; linknode,*link; void Insertsort(link L) link p,q,r,u; p=L-next; (1) L-next=NULL _; while(2)_ p!=NULL _) r=L; q=L-next; while(3) q!=NUll _& q-datadata) r=q; q=q-next; u=p-next; (4)_ p-next=q _ ; (5)_ r-next= p_; p=u; 第六章练习选择题1. 设树 T的度为 4，其中度为 1，

15、2，3 和 4 的结点个数分别为4，2，1，1 则 T中的叶子数为（ D ）A5 B6 C7 D8 2. 设森林 F 对应的二叉树为 B，它有 m个结点， B的根为 p,p 的右子树结点个数为n, 森林 F中第一棵树的结点个数是（ A ）Am-n B m-n-1 Cn+1 D 条件不足，无法确定3若一棵二叉树具有10 个度为 2 的结点， 5个度为 1 的结点，则度为 0 的结点个数是（ B ）A9 B11 C15 D不确定4具有 10个叶结点的二叉树中有（ B ）个度为 2 的结点，A8 B9 C10 Dll 5一棵完全二叉树上有1001 个结点，其中叶子结点的个数是（ E ）A 250 B

16、 500 C254 D505 E以上答案都不对6. 有 n 个叶子的哈夫曼树的结点总数为（ D ） 。A不确定 B2n C2n+1 D2n-1 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 18 页 - - - - - - - - - 6 7. 一棵具有 n 个结点的完全二叉树的树高度（深度）是（ A ）A logn +1 Blogn+1 C logn Dlogn-1 8深度为 h 的满 m叉树的第 k 层有（ A）个结点。 (1=k=1) 4度为二的树就是二叉树。5.

17、 在中序线索二叉树中，每一非空的线索均指向其祖先结点。填空题：1如某二叉树有20 个叶子结点，有30 个结点仅有一个孩子，则该二叉树的总结点数为_69_。2具有 256个结点的完全二叉树的深度为_9_。3已知一棵度为3 的树有 2 个度为 1 的结点， 3 个度为 2 的结点， 4 个度为 3 的结点，则该树有_12_个叶子结点。4 在一棵二叉树中，度为零的结点的个数为N0, 度为 2的结点的个数为 N2, 则有 N0=_ N2 _+ 1_ 5已知二叉树有50 个叶子结点，则该二叉树的总结点数至少是_99_。6一个有 2001个结点的完全二叉树的高度为_11_。7设 F 是由 T1,T2,T3

18、 三棵树组成的森林 , 与 F 对应的二叉树为 B,已知 T1,T2,T3 的结点数分别为 n1,n2 和 n3则二叉树 B的左子树中有 _n1-1_个结点，右子树中有 _n2+n3_个结点。作业题1、给定一组权值2,3,5,7,11,13,17,19,23,29，31，37，41，（1）试画出用 Huffman 算法建造的 Huffman 树；（2）求平均编码长度（）考虑概率解： （1）名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页，共 18 页 - - - - - - -

19、 - - 8 （2） （7（23） 6557 4（176613）3（313741291923） ）/ 238 2、 设一棵二叉树的先序、中序遍历序列分别为先序遍历序列： A B D F C E G H 中序遍历序列： B F D A G E H C （1）画出这棵二叉树。（2）画出这棵二叉树的后序线索树。解： （1）(2) 后序遍历为： F D B G H E C A A B C D E G H F 238 143 95 65 78 34 31 17 17 10 7 5 5 2 3 37 41 53 42 24 29 19 23 11 13 名师资料总结 - - -精品资料欢迎下载 - - -

20、 - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 8 页，共 18 页 - - - - - - - - - 9 3二叉树存储结构同上题，以下程序为求二叉树深度的递归算法，请填空完善之。 int depth(bitree bt) /*bt为根结点的指针 */ int hl,hr; if (bt=NULL) return(1)_ 0_); hl=depth(bt-lchild); hr=depth(bt-rchild); if(2) hlhr _) (3)_ hr=hl_； return(hr+1); 4线索二叉树有数据域data，左右孩子

21、域 lchild和 rchild，左右标志 ltag及 rtag ，规定标志为 1 对应的孩子域是线索， 0 则为指向孩子的指针。规定在储存线索二叉树时，完成下面中序线索化过程。（存储线索二叉树，不增加头结点，只在原有的由tree 指向的二叉树中增加线索，此处也不考虑c 语言的具体语法与约定，线索化前所有的标志tag 都是 0） 。/* pre是同 tree 类型相同的指针，初值是null */ thread_inorder (tree) if(tree!=null) thread_inorder(1) tree-lchild _); if(tree-lchild=(2)_ NULL_) tr

22、ee-ltag=1; tree-lchild=pre; if(3) tree-rchild_ = null) (4) tree-rtag=1_; (5) tree-rchild=tree _; pre=p; thread-inorder(6)_ tree-rchild _); 5、已知一棵满二叉树的结点个数为20 到 40 之间的素数，此二叉树的叶子结点有多少个？（请给出具体的推理过程）解： 16 6、一棵共有 n 个结点的树，其中所有分支结点的度均为K，求该树中叶子结点的个数。kknn1) 1(07. 假设一个二叉树的两种遍历如下：A B C D E G H F 名师资料总结 - - -精品

23、资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 9 页，共 18 页 - - - - - - - - - 10 前序： ABFGCHDEIJLK 中序： FGBHCDILJKEA 画出这棵二叉树以及它的中序线索树；解：第七章练习选择题1设无向图的顶点个数为n，则该图最多有（ B ）条边。An-1 Bn(n-1)/2 C n(n+1)/2 D0 En22一个 n 个顶点的连通无向图，其边的个数至少为（ A ）。An-1 Bn Cn+1 Dnlogn ；3一个有 n 个结点的图，最少有（ B ）个连通分量，最多有（

24、 D ）个连通分量。A0 B1 Cn-1 Dn 4在一个无向图中，所有顶点的度数之和等于所有边数（ B ）倍，在一个有向图中，所有顶点的入度之和等于所有顶点出度之和的（ C ）倍。A1/2 B2 C1 D4 5下列哪一种图的邻接矩阵是对称矩阵？（ B ）A有向图 B无向图 CAOV 网 DAOE 网6当一个有 N个顶点的图用邻接矩阵A表示时，顶点 Vi 的度是（ B ） 。AnijiA1, Bn1jj , iA CniijA1, DnijiA1,+ n1ji , jA7无向图 G=(V,E), 其中：V=a,b,c,d,e,f, E=(a,b),(a,e), (a,c), (b,e), (c,

25、f), (f,d), (e,d)， 对该图进行深度优先遍历，得到的顶点序列正确的是（ D ） 。Aa,b,e,c,d,f Ba,c,f,e,b,d Ca,e,b,c,f,d Da,e,d,f,c,b 8下面哪一方法可以判断出一个有向图是否有环（回路）： （ B ）A B F C L J H G D I E K A B F C L J H G D I E K 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 10 页，共 18 页 - - - - - - - - - 11 A深度优先遍历

26、 B. 拓扑排序 C. 求最短路径 D. 广度优先遍历9. 在图采用邻接表存储时，求最小生成树的 Prim 算法的时间复杂度为 ( B )。A. O(n) B. O(n+e) C. O(n2) D. O(n3) 10. 求解最短路径的Floyd 算法的时间复杂度为 (D )。AO （n） B. O（n+c） C. O（n*n） D. O（n*n*n ）11已知有向图 G=(V,E)，其中 V=V1,V2,V3,V4,V5,V6,V7，E=,G 的拓扑序列是（ A ） 。AV1,V3,V4,V6,V2,V5,V7 BV1,V3,V2,V6,V4,V5,V7CV1,V3,V4,V5,V2,V6,V

27、7 DV1,V2,V5,V3,V4,V6,V712若一个有向图的邻接距阵中, 主对角线以下的元素均为零, 则该图的拓扑有序序列（ A ） 。A存在 B 不存在13一个有向无环图的拓扑排序序列（ B ）是唯一的。A一定 B不一定14. 在有向图G 的拓扑序列中，若顶点Vi 在顶点 Vj 之前，则下列情形不可能出现的是（ D ） 。AG中有弧 BG中有一条从 Vi 到 Vj 的路径C G中没有弧 DG中有一条从 Vj 到 Vi 的路径15. 在用邻接表表示图时，拓扑排序算法时间复杂度为( B )。A. O(n) B. O(ne) C. O(n*n) D. O(n*n*n) 16. 关键路径是事件结

28、点网络中（ A ） 。A从源点到汇点的最长路径 B从源点到汇点的最短路径C最长回路 D最短回路17下列关于 AOE 网的叙述中，不正确的是（ B ） 。A关键活动不按期完成就会影响整个工程的完成时间B任何一个关键活动提前完成，那么整个工程将会提前完成C所有的关键活动提前完成，那么整个工程将会提前完成D某些关键活动提前完成，那么整个工程将会提前完成判断题1. 有 e 条边的无向图，在邻接表中有e 个结点。 （ ）2. 有向图的邻接矩阵是对称的。 （）3任何无向图都存在生成树。 （）4. 不同的求最小生成树的方法最后得到的生成树是相同的. （）5. 有环图也能进行拓扑排序。 （ ）6. 关键路径是

29、 AOE 网中从源点到终点的最长路径。 （）填空题1具有 10个顶点的无向图，边的总数最多为_45_。2. 在有 n 个顶点的有向图中，若要使任意两点间可以互相到达，则至少需要_ n _条弧。3n 个顶点的连通无向图，其边的条数至少为_n-1_。4N个顶点的连通图用邻接矩阵表示时, 该矩阵至少有 _2(n-1)_ 个非零元素。5构造连通网最小生成树的两个典型算法是_普里姆算法、克鲁斯卡尔算法_。6. 有一个用于 n 个顶点连通带权无向图的算法描述如下：名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - -

30、- - - 第 11 页，共 18 页 - - - - - - - - - 12 （1） 设集合 T1与 T2，初始均为空；（2） 在连通图上任选一点加入T1；（3） 以下步骤重复 n-1 次：a. 在 i 属于 T1，j 不属于 T1 的边中选最小权的边；b. 该边加入 T2。上述算法完成后， T2中共有 _n-1_条边，该算法称 _普里姆算法 _算法，T2中的边构成图的 _最小生成树 _。7AOV网中, 结点表示 _活动_,边表示 _联系_。AOE网中, 结点表示 _事件 _, 边表示_活动_。8. 当一个 AOV 网用邻接表表示时，可按下列方法进行拓扑排序。（1） 查邻接表中入度为 _零

31、_的顶点，并进栈；（2） 若栈不空，则输出栈顶元素Vj，并退栈；查 Vj 的直接后继 Vk，对 Vk入度处理，处理方法是 _ Vk 的入度减 1，如为 0 则入栈 _；（3） 若栈空时，输出顶点数小于图的顶点数，说明有_环路_，否则拓扑排序完成。作业题1n 个顶点的有向图用邻接矩阵array 表示，下面是其拓扑排序算法，试补充完整。注： （1） 图的顶点号从 0 开始计；（2） indegree 是有 n 个分量的一维数组，放顶点的入度；（3） 函数 crein 用于算顶点入度； （4） 有三个函数 push(data),pop( ),check( )其含义为数据 data 进栈，退栈和测试栈

32、是否空（不空返回1，否则 0） 。 crein( array ,indegree,n) for (i=0;in;i+) indegreei= (1)_ _0_) for(i=0,in;i+) for (j=0;jn; j+) indegreei+=array(2)_ i_(3)_ _j_; topsort (array,indegree,n) count= (4)_ 0_) for (i=0;in;i+) if (5)_ indegreei=0_) push(i) while (check( ) vex=pop( ); printf(vex); count+; for (i=0;in;i+)

33、k=array(6)_ vexi;_ if (7)_ k!=0_) indegreei-; if (8)_ indegreei=0_ ) push(i); if( countn) printf(“ “图有回路” )； 2设 G=(V,E)以邻接表存储，如图所示，试画出图的深度优先和广度优先生成树。123451341241232423455名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 12 页，共 18 页 - - - - - - - - - 13 13654219211656611

34、141833解：3下图表示一个地区的通讯网，边表示城市间的通讯线路，边上的权表示架设线路花费的代价，如何选择能沟通每个城市且总代价最省的n-1 条线路，画出所有可能的选择。解：4、对下面的有向图，试利用DIJKSTRA 算法从顶点 1 到其它顶点的最短路径，并写出执行该算法过程中每次循环的状态。1 2 3 4 5 1 2 3 4 5 18136542165611136542165611 18名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 13 页，共 18 页 - - - - - -

35、 - - - 14 v4 v2 v6 v5 v1 v310 10 10 15 4 30 4 20 2 15 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 14 页，共 18 页 - - - - - - - - - 15 第十章选择题1下面给出的四种排序法中( D )排序法是不稳定性排序法。 A. 插入 B. 冒泡 C. 二路归并 D. 堆排序2下列排序算法中，其中（ D ）是稳定的。A. 堆排序，冒泡排序 B. 快速排序，堆排序 C. 直接选择排序，归并排序 D. 归并排序，冒泡排

36、序3下面的排序算法中，不稳定的是（ CDF ）A.起泡排序 B. 折半插入排序 C.简单选择排序 D.希尔排序 E.基数排序 F. 堆排序。4对一组数据（ 84，47，25，15，21）排序，数据的排列次序在排序的过程中的变化为（1） 84 47 25 15 21 （2） 15 47 25 84 21 （3） 15 21 25 84 47 （4） 15 21 25 47 84 则采用的排序是 (A )。A. 选择 B. 冒泡 C. 快速 D. 插入5. 在下面的排序方法中，辅助空间为O （n）的是 ( D ) 。 A希尔排序 B. 堆排序 C. 选择排序 D. 归并排序6. 下列排序算法中，占

37、用辅助空间最多的是：(A ) A. 归并排序 B. 快速排序 C. 希尔排序 D. 堆排序7用直接插入排序方法对下面四个序列进行排序（由小到大），元素比较次数最少的是（ C ） 。A 94,32,40,90,80,46,21,69 B 32,40,21,46,69,94,90,80 C 21,32,46,40,80,69,90,94 D 90,69,80,46,21,32,94,40 8直接插入排序在最好情况下的时间复杂度为（ B ） A O(logn) B O(n) C O(n*logn) D O(n2) 9对下列关键字序列用快速排序法进行排序时，速度最快的情形是（A ） 。A 21,25,

38、5,17,9,23,30 B25,23,30,17,21,5,9 C 21,9,17,30,25,23,5 5,9,17,21,23,25,30 10下列四个序列中，哪一个是堆（ C ） 。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在待排数据基

39、本有序的情况下，快速排序效果最好。（）5快速排序总比选择排序快。（）填空1若不考虑基数排序，则在排序过程中，主要进行的两种基本操作是关键字的_比较_和记录的_移动_。2关键码序列（ Q，H，C，Y，Q ，A，M ，S，R ，D，F，X） ，要按照关键码值递增的次序进行排序，若采用初始步长为4 的 Shell 排序法，则一趟扫描的结果是_ Q A C S Q D F X R H M Y _；若采用以第一个元素为分界元素的快速排序法，则扫描一趟的结果是_ F H C D M 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整

40、理 - - - - - - - 第 15 页，共 18 页 - - - - - - - - - 16 A Q S R Q Y X _ 。作业题1下面的排序算法的思想是：第一趟比较将最小的元素放在r1 中，最大的元素放在rn中，第二趟比较将次小的放在r2 中，将次大的放在 rn-1中，, , 依次下去，直到待排序列为递增序。（注： ）代表两个变量的数据交换） 。void sort(SqList &r,int n) i=1; while(1) i n/2_) min=max=1; for (j=i+1;(2)_ j=n-i+1_ ;+j) if(3)_ rj.keyrmax.key) max=j;

41、 if(4)_ min!=j_) rmin rj; if(max!=n-i+1)if (5)_ max=j _) rmin rn-i+1; else (6) rmaxrm-i+1_); i+; /sort 2快速排序是在所有情况下， 排序速度最快吗？为什么？在何种情况下使用此排序法最好？解：不是，已经有序情况下不适用，适用于基本无序的情况。3、以上所列的排序方法，哪些是稳定的？哪些是不稳定的？对不稳定的方法举出反例。4、设计一算法，使得在尽可能少的时间内重排数组，将所有取负值的关键字放在所有取负值关键字之前。快速排序的一趟排序：把关键字改成跟零比较5、以单链表为存储结构实现直接选择排序，写出它

42、的算法。6、判别以下序列是否为堆？若不是，则把它调整为堆1）100，86，48，73，35，39，42，57，66，21 2）12，70，33，65，24，56，48，92，86，33 3）103，97，56，38，66，23，42，12，30，52，06，20 4）05，56，20，23，40，38，29，61，35，76，28，100 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 16 页，共 18 页 - - - - - - - - - 17 第九章选择题1、 对 N个元素的

43、表做顺序查找时，若查找每个元素的概率相同，则平均查找长度为(A ) A （N+1 ）/2 B. N/2 C. N D. （1+N ）*N /2 2. 下面关于二分查找的叙述正确的是 ( D ) A. 表必须有序，表可以顺序方式存储，也可以链表方式存储 C. 表必须有序，而且只能从小到大排列B. 表必须有序且表中数据必须是整型，实型或字符型 D. 表必须有序，且表只能以顺序方式存储3. 二叉查找树的查找效率与二叉树的( （1）C ) 有关, 在 ( （2）C)时其查找效率最低 (1): A. 高度 B. 结点的多少 C. 树型 D. 结点的位置 (2): A. 结点太多 B. 完全二叉树 C.

44、呈单枝树 D. 结点太复杂。4. 若采用链地址法构造散列表，散列函数为H （key）=key MOD 17，则需 ( （1）A) 个链表。这些链的链首指针构成一个指针数组，数组的下标范围为 ( （2）C) （1） A17 B. 13 C. 16 D. 任意（2） A0 至 17 B. 1至 17 C. 0至 16 D. 1至 16 判断题1Hash表的平均查找长度与处理冲突的方法无关。2. 若散列表的负载因子 1，则可避免碰撞的产生。3. 就平均查找长度而言，分块查找最小，折半查找次之，顺序查找最大。填空题1. 在顺序表（ 8,11,15,19,25,26,30,33,42,48,50）中，用

45、二分（折半）法查找关键码值20，需做的关键码比较次数为_4_. 作业题1. 设有一组关键字 9,01,23,14,55,20,84,27，采用哈希函数： H（key）=key mod 7 ，表长为 10，用开放地址法的二次探测再散列方法Hi=(H(key)+di) mod 10(di=12,22,32, ,) 解决冲突。要求：对该关键字序列构造哈希表，并计算查找成功的平均查找长度。解：14/8 1.75 2. 已知散列表的地址空间为A0.11，散列函数 H （k）=k mod 11 ，采用线性探测法处理冲突。请将下列数据 25,16,38,47,79,82,51,39,89,151,231依次

46、插入到散列表中，并计算出在等概率情况下查找成功时的平均查找长度。解：14 1 9 23 84 2755 20 1 1 1 2 3 3 1 2 0 1 2 3 4 5 6 7 8 9 231 89 79 25 47 16 38 82 51 39 151 1 1 1 1 2 1 2 3 2 4 3 0 1 2 3 4 5 6 7 8 9 10 11 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 17 页，共 18 页 - - - - - - - - - 18 21/11 3、对长度为

47、20 的有序表进行二分查找，试画出它的一棵判定树，并求等概率情况下的平均查找长度。随机的给出 20个有序数据4、试编写一个用拉链法解决冲突的散列表上删除一个指定结点的算法。（不做要求）5、设散列表的长度为15，散列函数 H（K）=K%13，给定的关键字序列为20，16，29，82，37，02，06，28，55，39，23，10，试写出分别用拉链法和线性探测法解决冲突时所构造的散列表，并求出在等概率情况下，这两种方法查找成功时的平均查找长度。第十二章文件选择题4下述文件中适合于磁带存储的是（ A ） 。 A. 顺序文件 B. 索引文件 C. 散列文件 D. 多关键字文件判断题1. 文件是记录的集合， 每个记录由一个或多个数据项组成，因而一个文件可看作由多个记录组成的数据结构。填空题1. 文件可按其记录的类型不同而分成两类，即_操作系统 _和_数据库 _文件。2. 数据库文件按记录中关键字的多少可分成_单关键字 _和_多关键字 _两种文件。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 18 页，共 18 页 - - - - - - - - -