数 据 结 构 习 题 集(打印).doc

数据结构习题集(郑州大学) 一、选择题 .在一个长度为n的顺序表中，向第i个元素(1in+1)之前插入一个新元素时，需向后移动 B 个元素。 A. n-1 B. n-i+1 C. n-i-1 D. i .在一个具有n个单元的顺序栈中，假定以地址低端作为栈底，以top作为栈顶指针， 则当做退栈处理时，top变化为 C 。 A. top不变 . top -n C. toptop-1 D. top=top+1 3.在一个顺序存储的循环队列中，队首指针指向队首元素的 A 。 A. 前一个位置 B. 后一个位置 C. 队首元素位置 D. 队尾元素位置 4.若进栈序列为1,2,3,4,进栈过程中可以出栈，则 C 不可能是一个出栈序列。 A. 3,4,2,1 B. 2,4,3,1 C. 1,4,2,3 D. 3,2,1,4 5.在具有n个单元的顺序存储的循环队列中，假定front和rear分别为队首指针和队尾指针，则判断队空的条件是 C 。 A. front= =rear+1 B. front+1= =rear C. front= =rear D. front= =0 6.从一个具有n个节点的单链表中查找其值等于x结点时，在查找成功的情况下，需 平均比较 D 个结点。 A. n B. n/2 C. (n-1)/2 D. (n+1)/2 7.在一个单链表中，已知*q结点是*p结点的前驱结点，若在*q和*p之间插入*s结点， 则执行 C 。 A. s-next=p-next; p-next=s; B. p-next=s-next; s-next=p; C. q-next=s; s-next=p; D. p-next=s; s-next=q; 8.向一个栈项指针为hs的链栈中插入一个*s结点时，则执行 C 。 A. hs-next=s; B. s-next=hs-next; hs-next=s; C. s-next=hs；hs=s; D. s-next=hs; hs=hs-next; 9.对顺序存储的线性表，设其长度为n，在任何位置上插入或删除操作都是等概率的， 删除一个元素时大约要移动表中的 C 个元素。 A. n+1 B. n-1 C. (n-1)/2 D. n 10.设单链表中指针p指着结点(数据域为m)，指针f指着将要插入的新结点(数据域为x)，当x插在结点m之后时，只要先修改 B 后修改p-link=f即可。 A. f-link=p; B. f-link=p-link; C. p-link=f-link; D. f=nil; 11.在双向链表存储结构中，删除p所指的结点时需修改指针 B 。 A. (p-rlink) -rlink) -link=p; p-rlink=(p-rlink) -rlink; B. (p-llink) -rlink=p-rlink; (p-rlink) -llink=p-llink; C. p-llink=(p-llink) -llink; (p-llink) -llink) -rlink=p; D. (p-llink) -llink) -rlink=p; p-llink=(p-llink) -llink; 12.在双向链表存储结构中，删除p所指的结点的前趋结点（若存在）时需修改指针 A 。 A. (p-llink) -llink) -rlink=p; p-llink=(p-llink) -llink; B. (p-rlink) -rlink) -llink=p; p-rlink=(p-rlink) -rlink; C. (p-llink) -rlink=p-rlink; (p-rlink) -llink=p-llink; D. p-llink=(p-llink) -llink; (p-llink) -llink) -rlink=p; 13.设字符串s1=abcdefg,s2=pqrst，则运算 s=concat(sub(s1,2,len(s2),sub(s1,len(s2),2)后串值为 D 。 A. bcdef B. bcdefg C. bcpqrst D. bcdefef 14.已知8个数据元素为(34、76、45、18、26、54、92、65)，按照依次插入结点的方法生成一棵二叉排序树后，最后两层上的结点总数为 B 。 A. 1 B. 2 C. 3 D. 4 15.由分别带权为9、2、5、7的四个叶子结点构造一棵哈夫曼树，该树的带权路径长度为 C 。 A. 23 B. 37 C. 44 D.46 16.下面答案 D 是查找二叉树（又称二叉排序树）。 A. 二叉树中的每个结点的两棵子树的高度差的绝对值不大于 B. 二叉树中的每个结点的两棵子树的高度差等于 C. 二叉树中的每个结点的两棵子树是有序的 D. 二叉树中的每个结点的关键字大于其左子树（如果存在）所有结点的关键字值， 且小于其右子树（如果存在）所有结点的关键字值。 17.在完全二叉树中，当i为奇数且不等于时，结点i的左兄弟是结点 D ，否则没有左兄弟。 A. 2i-1 B. i+1 C. 2i+1 D. i-1 18.某二叉树T有n个结点，设按某种遍历顺序对T中的每个结点进行编号，编号值为1,2,n且有如下性质：T中任一结点V，其编号等于左子树上的最小编号减1，而V的右子树 的结点中，其最小编号等于V左子树上结点的最大编号加1。这时按 B 编号。 A. 中序遍历序列 B. 前序遍历序列 C. 后序遍历序列 D. 层次遍历序列 19.在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的 B 倍。 A. 1/2 B. 1 C. 2 D. 4 20.对于一个具有n个顶点和e条边的无向图，若采用邻接表表示，则表头向量的大小 为 A 。 A. n B. n+1 C. n-1 D. n+e 21.具有n个顶点的无向完全图，边的总数为 D 条。 A. n-1 B. n C. n+1 D. n*(n-1)/2 22.设图G有n个顶点和e条边，当G是非孤立顶点的连通图时有2e=n,故可推得深度优先搜索的时间复杂度为 A 。 A. O(e) B. O(n) C. O(ne) D. O(n+e) 23.图的深度优先或广度优先遍历的空间复杂性均为 A 。(访问标志位数组空间) A. O(n) B. O(e) C. O(n-e) D. O(n+e) 24.一组记录排序码为(46、79、56、38、40、84)，则利用堆排序的方法建立的初始堆为 B 。 A. (79、46、56、38、40、80) B. (84、79、56、38、40、46) C. (84、79、56、46、40、38) D. (84、56、79、40、46、38) 二、填空题 1.一个数据结构用二元组表示时，它包括 1 数据元素 的集合K和K上 2二元关系 的集合R。2.在具有n个单元、顺序存储的循环队列中，队满时共有 1 n-1 个元素。3.一个单链表中删除*p结点时，应执行如下操作: (1)q=p-next; (2)p-data=p-next-data; (3)p-next= 1 q-next或p-next-next ; (4)free(q);4.若要在一个单链表中的*p结点之前插入一个*s结点时，可执行如下操作: (1)s-next= 1 p-next ; (2)p-next=s; (3)t=p-data; (4)p-data= 2 s-data ; (5)s-data= 3 t ; 5.对于一棵具有n个结点的树，则该树中所有结点的度之和为 n-1 。6.在一棵二叉树中，度为0的结点的个数为n0 ，度为2的结点的个数为n2 ，则：n0 = n2 +1 。7.在一棵二叉排序树中，按 中序 遍历得到的结点序列是一个有序序列。8.假定在二叉树的链接存储中，每个结点的结构为leftdataright ，其中 data为值域，left和right分别为链接左、右孩子结点的指针域，请在下面中序遍历算法 中画有横线的地方填写合适的语句。 void inorder(bt); if bt!=nil (1) 1 inorder(bt-left) ； (2) 2 printf(bt-data) ； (3) 3 inorder(bt-right) ； 9.在图G的邻接表表示中，每个顶点邻接表中所含的结点数，对于无向图来说等于该 顶点的 1 度数 ，对于有向图来说等于该顶点的 2 出度数 。 10.已知一个无向图的邻接矩阵如下所示，则从顶点A出发按深度优先搜索遍历得到的 顶点序列为 1 ABCDFE ，按广度优先搜索遍历得到的顶点序列为 2 ABCEFD 。 A B C D E F 0 1 1 0 1 0A 1 0 1 0 1 1B 1 1 0 1 0 0C 0 0 1 0 0 1D 1 1 0 0 0 1E 0 1 0 1 1 0F 11.在对一组记录(54,38,96,23,15,72,60,45,38)进行冒泡排序时，第一趟需进行相邻记录交换的次数为 17 ，在整个冒泡排序过程中共需进行 25 趟后才能完成。 三、综合题 1.若对大小均为n的有序的顺序表和无序的顺序表分别进行顺序查找，试问在下面三 种情况下，分别讨论两者在等概率时，平均查找长度是否相同? (1)查找不成功，即表中没有关键字等于给定值k的记录； (2)查找成功，且表中只有一个关键字等于给定值k的记录； (3)查找成功，且表中有若干个关键字等于给定值k的记录，一次查找要求找出所有记 录，此时的平均查找长度应考虑找到所有记录时所用的比较次数。 13.(1) 解答:不相同。对于有序的顺序表而言，当表中无此关键字时，只要在查找过程中发现顺序表中的某个关键字大于待查的关键字时，查找过程就可以结束（假定顺序表是由小到大排列的，对于由大到小排列的情况类似），没有必要查找到表中最后一个关键字才确定查找不成功。而对于非有序的顺序表，只有对表中的每一个关键字比较完之后，才能说明查找不成功。显然在等概率时两种顺序的平均查找长度是不相同的。有序顺序表的平均长度为(n1)/2，而无序顺序表的平均查找长度为n。但从数量级上两者是相同的,即O(n)。 (2) 解答:相同的。其分析类似于(1)。两者在等概率下的平均长度为(n1)/2，数量级上为 O(n)。 (3) 解答:不相同。其分析完全与(1)相同，其结论也完全相同。2.假定有n个关键字，它们具有相同的Hash函数值，用线性探测方法把这n个关键字 存入到Hash地址空间中要做多少次探测? 14. 解答:由于线性探测的查找次数主要取决于装载因子，即与Hash地址空间的占用情况 有关。假定初始时Hash地址空间为空，在此情况下连续装入n个具有相同的Hash函数值的 关键字所需的总探测次数为 12nn(n1)/23.已知一组元素为(46、25、78、62、18、34、12、40、73)，试画出按元素排列顺序输入而生成的一棵二叉排序树。 33. 解答:得到的二叉排序树如下图所示。 46 25 78 18 34 62 12 40 7338.设无向图G如下图 B E A D G C F 试给出 (1)该图的邻接矩阵； (2)该图的邻接表； (3)从A出发的“深度优先”遍历序列； (4)从A出发的“广度优先”遍历序列。 38. 解答: (1) 图G的邻接矩阵 A (2)邻接表如见： (3)从顶点A出发按深度优先遍历序列(不是唯一的)为A、B、D、C、E、G、F (4)从顶点A出发按广度优先遍历序列(不是唯一的)为A、B、C、D、E、F、G 37.由前序遍历结果可知该二叉树的根结点为。由此及中序遍历结果可知，该二叉树在中序遍历下的左、右子树为 CBED和HGIJF 依此可推出前序遍历的左、右子树的结点序列为 BCDE和FGHIJ B和F又分别为左、右子树的根结点，进而又可推出以B为根结点的左、右子树，以及 以F为根结点的左、右子树。依此类推，可推出二叉树见下图。 A B F C D G E H I J 38. (1) 图G的邻接矩阵 A (2)邻接表如见： (3)从顶点A出发按深度优先遍历序列(不是唯一的)为A、B、D、C、E、G、F (4)从顶点A出发按广度优先遍历序列(不是唯一的)为A、B、C、D、E、F、G四.算法设计题 1:向类型有list的线性表L的第i个元素（0iL.len）之后插入一个新元素x。 (1) 解答: status insert(SqList L,int i,ElemType x) / 向线性表L中第i个元素之后插入值为x的新元素 (1) if (L.len = =m0) error(overflow); (2) if (iL.len) error (out of range); (3) for (j=L.len ;j= i1;-j ) L.vecj1L.vecj; (4) L.veci1x; (5) L.lenlen1; 2:将两个有序表A和B合并成一个有序表C，其中A，B，C均为list类型的变参。 (3)解答:status merge(A,B,C) / 将两个有序表A和B合并成一个有序表C (1) if ( A.lenB.lenm0 ) error(overflow): (2) i=1;j1;k1; / i和j分别作为扫描数组A和B的指针，k指示存入数组C中元素的下标位置 (3) while (iA.len) & (jB.len) if (A.veciB.vecj) C.veckA.veci; ii1;kk1; else C.veckB.vecj; jj1; kk1; (4) while (iA.len) C.veckA.veci; ii1; kk1; (5) while (jnext; (3) q-nextHL; (4) HLq; (4)删除单链表中第i个（i1）结点。 (2) 解答:status delete(HL,i) (1) if (inext; return ; (3) j1; pHL; /p指针所指向的结点，是单链表中第j个结点 while (jnext!=null) jj1; pp-next; / 寻找第i个结点的前驱结点 (4) if (p-next!= =null) p-nextp-next-next; else error