《2022年2022年计算机数据结构试题及答案 .pdf》由会员分享，可在线阅读，更多相关《2022年2022年计算机数据结构试题及答案 .pdf（5页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、计算机数据结构试题及答案(2009-12-23 12:21:57) 全真模拟试题（一）一、单项选择题（在每小题的4 个备选答案中，选出正确的答案，并将其号码填在题干的括号内。每小题2 分，共 24 分）1 若某线性表中最常用的操作是取第i 个元素和找第i 个元素的前趋元素，则采用（）存储方式最节省时间。单链表双链表单向循环顺序表2串是任意有限个（）符号构成的序列符号构成的集合字符构成的序列字符构成的集合3设矩阵 A（ aij ，l i,j 10）的元素满足：aij 0(i j, l i, j 10)aij=0 (ij, l i, j 10)现将 A 的所有非0 元素以行序为主序存放在首地址为2
2、000 的存储区域中，每个元素占有4个单元，则元素A95 的首址为2340 2336 2164 2160 4如果以链表作为栈的存储结构，则退栈操作时（）必须判别栈是否满对栈不作任何判别必须判别栈是否空判别栈元素的类型5设数组 Data0.m 作为循环队列SQ 的存储空间，front 为队头指针，rear 为队尾指针，则执行出队操作的语句为（）front=front+1 front=(front+1)% m rear=(rear+1)%m front=(front+1)%(m+1) 6深度为 6（根的层次为1）的二叉树至多有（）结点。64 32 31 63 7将含 100 个结点的完全二叉树从根
3、这一层开始，每层上从左到右依次对结点编号，根结点的编号为1。编号为49 的结点 X 的双亲编号为（）24 25 23 无法确定8设有一个无向图G=（V，E）和 G=（V ，E ）如果 G 为 G 的生成树，则下面不正确的说法是（）G 为 G 的子图G 为 G 的边通分量G 为 G 的极小连通子图且V=V G 为 G 的一个无环子图9用线性探测法查找闭散列表，可能要探测多个散列地址，这些位置上的键值（）一定都是同义词一定都不是同义词都相同不一定都是同义词10二分查找要求被查找的表是（）键值有序的链接表链接表但键值不一定有序 键值有序的顺序表顺序表但键值不一定有序11当初始序列已经按键值有序，用直
4、接插入算法对其进行排序，需要循环的次数为（）名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 5 页 - - - - - - - - - n2 nlog2n log2n n-1 12堆是一个键值序列k1,k2, , kn, 对 i=1,2, ,|_n/2_|,满足 ( ) ki k2i k2i+1kik2i+1k2i ki k2i且 ki k2i+1(2i+1 n)ki k2i 或 ki k2i+1(2i+1 n)二、判断题 （判断下列各题是否正确，正确在括号内打“V”，错
5、的找 “X”。每小题 1 分，共 10 分）1双链表中至多只有一个结点的后继指针为空。（）2在循环队列中，front 指向队列中第一个元素的前一位置，rear 指向实际的队尾元素，队列为满的条件是front=rear。 （）3对链表进行插入和删除操作时，不必移动结点。（）4栈可以作为实现程序设计语言过程调用时的一种数据结构。（）5在一个有向图的拓朴序列中，若顶点a在顶点 b 之前，则图中必有一条弧。( )i 6对有向图G，如果从任一顶点出发进行一次深度优先或广度优先搜索就能访问每个顶点，则该图一定是完全图。( ) 7“ 顺序查找法 ” 是指在顺序表上进行查找的方法。（）8向二叉排序树插入一个新
6、结点时，新结点一定成为二叉排序树的一个叶子结点。（）9键值序列 A ，C，D，E，F， E，F 是一个堆。10二路归并时，被归并的两个子序列中的关键字个数一定要相等。（）三、填空题（每空2 分，共 24 分）1设 r 指向单链表的最后一个结点，要在最后一个结点之后插入s所指的结点， 需执行的三条语句是 _； r=s; r-next=null; 。2在单链表中，指针p 所指结点为最后一个结点的条件是_。3 设一个链栈的栈顶指针是ls，栈中结点格式为info | link , 栈空的条件是_.如果栈不为空，则退栈操作为p=ls；_；free(p);。4已知一棵度为3 的树有 2 个度为 1 的结点
7、， 3个度为 2 的结点， 4 个度为 3 的结点，则该树中有 _ 个叶子的结点。5树有三种常用的存储结构，即孩子链表法、孩子兄弟链表法和_ . 6N 个顶点的连通图的生成树有_条边。7一个有向图G 中若有弧 、 和, 则在图 G 的拓扑序列中，顶点vi,vj和 vk 的相对位置为_。8设表中元素的初始状态是按键值递增的，分别用堆排序、快速排序、冒泡排序和归并排序方法对其进行（按递增排序），最省时间，最费时间。9下面是将键值为x 的结点插入到二叉排序树中的算法，请在划线处填上适当的内容。typedef struct pnode int key; struct pnode *left, *rig
8、ht; pnode; void searchinsert(int x, pnode t ) /*t 为二叉排序树根结点的指针*if ( ) p=malloc(size); p-key=x;p-lchild=null; p-rchild=null;t=p; else if (xkey) searchinsert(x,t-lchild) else_; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 5 页 - - - - - - - - - 四、应用题（本题共分）1树的后根遍
9、历方法是：若树非空则（分）（1）依据次后根遍历根的各个子树， m; （2）访问根结点2. 将下图的森林转换为二叉树。（分）3. 下图表示一个地区的交通网，顶点表示城市，边表示连结城市间的公路，边上的权表示修建公路花费的代价。怎样选择能够沟通每个城市且总造价最省的n-1 条公路， 画出所有可能的方案。 （分）图 7.11 遍历无向图(a) 无向图 G6 (b) 深度优先搜索示例(c) G6 的邻接表表示(c) 表头结点4已知一个无向图的邻接表如下图所示。（本题分，每小题分）(1) 画出这个图。(2) 以 v1 为出发点，对图进行广度优先搜索，写出所有可能的访问序列。5.设 n 个元素的有序表为，
10、为一个给定的值，二分查找算法如下：int binsearch(sqlist R, keytype K) j=1;h=n ;suc=0; while(j=h)&(!suc) mid =(j+h)/2; switch case K=Rmid.key: suc=1; break; case KRmid.key: j=mid+1 if (suc) return(mid); else return(0); 将上述算法中划线语句改为：Knext =s. 2P-next= = NULL 3Ls= =NULL 、ls=ls-link. 412 分析：设n1=2,n2=3,n3=4, 树的总结点数为n=n0+
11、n1+n2+n3 树的分支数为n-1= n1+2n2+3n3 -得： -1= n2+2n3-n0 有 n0=n2+2n3+1=3+2*4+1=12 5双亲表示法。6N-1 7I,j,k. 8冒泡排序、快速排序9T= =NULL 、searchinsert(x,t-rchild). 四、应用题1EBFGCKHIJDA 。2答案如图应用题I 9. 2.2 所示。33分析：本题实际上是求最小生成树问题。由于衅中有两条权值为6 的边，故可以得到两种方案。答案如图应用题I 9. 3.2 所示。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - -
12、 名师精心整理 - - - - - - - 第 4 页，共 5 页 - - - - - - - - - 4答案：（1）答案如图应用题I 9. 4.2 所示。（2）v1 v2 v4 v5 v3 和v1 v4 v2 v3 v5 。5 （1）经过改动以后，有可能出现死循环，比如当查找的键值K 小于有序表中的最小键值时，就会出现死循环。故算法不能正常进行。（ 2）假设有序表的查找序列为（2，3， 4，5，6） ，当待查的键值K=1 时，出现死循环。6答案： 25 84 21 47 15 27 68 35 24 第一趟24 15 21 25 47 27 68 35 84 第二趟21 15 24 25 3
13、5 27 47 68 84 第三趟15 21 24 25 27 35 47 68 84 得到15 21 24 25 27 35 47 68 84 第一趟排序过程中键值的移动情况如下：第一趟：25 84 21 47 15 27 68 35 24 一次交换之后24 84 21 47 15 27 68 35 25 二次交换之后24 25 21 47 15 27 68 35 84 24 25 21 47 15 27 68 35 84 24 25 21 47 15 27 68 35 84 24 25 21 47 15 27 68 35 84 三次交换之后24 15 21 47 25 27 68 35 8
14、4 24 15 21 47 25 27 68 35 84 四次交换之后24 15 21 25 47 27 68 35 84 以上 “ -” 表示当前经比较不交换位置的元素。“ ”表示当前经比较交换位置的元素。五、设计题1Bitreptr search(bitreptr t ,int k) if (t!=null) count+; if (count= =k)return (t); else search(t-lchild,k); search(t-rchild,k); 2. 单链表 L 的结构如图设计题I 9. 2.2 所示。Int isviser(lklist L) p=L; while(p-next!=null) if (p-data next-data) p=p-next; else return(0); return(1); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 5 页 - - - - - - - - -