全真模拟试题(一) 单项选择题(在每小题的4个备选答案中,选出正确的答案,并将其号码填在 题干的括号内。每小题2分,共24分) 若某线性表中最常用的操作是取第i个元素和找第i个元素的前趋元素,则采用 ()存储方式最节省时间。 ①单链表 ②双链表③单向循环 ④顺序表 2.串是任意有限个( ①符号构成的序列 ②符号构成的集合 ③字符构成的序列 ④字符构成的集合 3.设矩阵A(a;,l≤i,j≤10)的元素满足: a1;≠0(i≥j,1≤i,j≤10) a1=0(i<j,1≤i,j≤10) 现将A的所有非0元素以行序为主序存放在首地址为2000的存储区域中,每个元 素占有4个单元,则元素A[9][5]的首址为 ①2340 ②2336③2164④2160 4.如果以链表作为栈的存储结构,则退栈操作时( ①必须判别栈是否满 ②对栈不作任何判别 ③必须判别栈是否空 ④判别栈元素的类型 5.设数组Data[0.m]作为循环队列SQ的存储空间, front为队头指针,rear为队尾 指针,则执行出队操作的语句为 ① front= front+1 ② front=( front+1)%m ③rear=(rear+1)% @front=(front+1)%(m+1) 6.深度为6(根的层次为1)的二叉树至多有 )结点。 ①64 ②32 ③3 ④63 7.将含100个结点的完全二叉树从根这一层开始,每层上从左到右依次对结点编号 根结点的编号为1。编号为49的结点Ⅹ的双亲编号为() 1)24 ②2 ③23 ④无法确定 8.设有一个无向图G=(V,E)和G’=(V’,E’)如果G’为G的生成树,则下 面不正确的说法是( ①G’为G的子图 ②G’为G的边通分量 ③G’为G的极小连通子图且V’=V④G’为G的一个无环子图 9.用线性探测法査找闭散列表,可能要探测多个散列地址,这些位置上的键值() ①一定都是同义词 ②一定都不是同义词 ③都相同 ④不一定都是同义词 分查找要求被查找的表是( ①键值有序的链接表②链接表但键值不一定有序 ③键值有序的顺序表④顺序表但键值不一定有序 11.当初始序列已经按键值有序,用直接插入算法对其进行排序,需要循环的次数 为( ①n ② nlog2n ③lo ④n-1 2.堆是一个键值序列{kk2,kn},对F1,2,,Ln2满足(
1 全真模拟试题（一） 一、 单项选择题（在每小题的 4 个备选答案中，选出正确的答案，并将其号码填在 题干的括号内。每小题 2 分，共 24 分） 1． 若某线性表中最常用的操作是取第 i 个元素和找第 i 个元素的前趋元素，则采用 （ ）存储方式最节省时间。 ①单链表 ②双链表 ③单向循环 ④顺序表 2． 串是任意有限个（ ） ①符号构成的序列 ②符号构成的集合 ③字符构成的序列 ④字符构成的集合 3． 设矩阵 A（aij ，l≤i,j≤ 10）的元素满足： aij≠0(i≥j, l≤i, j≤ 10) aij=0 (i<j, l≤i, j≤ 10) 现将 A 的所有非 0 元素以行序为主序存放在首地址为 2000 的存储区域中，每个元 素占有 4 个单元，则元素 A[9][5]的首址为 ①2340 ②2336 ③2164 ④2160 4． 如果以链表作为栈的存储结构，则退栈操作时（ ） ① 必须判别栈是否满 ② 对栈不作任何判别 ③ 必须判别栈是否空 ④ 判别栈元素的类型 5． 设数组 Data[0..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 个结点的完全二叉树从根这一层开始，每层上从左到右依次对结点编号， 根结点的编号为 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． 当初始序列已经按键值有序，用直接插入算法对其进行排序，需要循环的次数 为（ ） ①n 2 ②nlog2n ③log2n ④n-1 12． 堆是一个键值序列{k1,k2,…, kn},对 i=1,2,…,|_n/2_|,满足( )
①k≤k2≤k2 ②k:next=null。 2.在单链表中,指针p所指结点为最后一个结点的条件是 3.设一个链栈的栈项指针是ls,栈中结点格式为血on栈空的条件是 如果栈不为空,则退栈操作为p=ls free(p); 4.已知一棵度为3的树有2个度为1的结点,3个度为2的结点,4个度为3的结点 则该树中有 个叶子的结点。 5.树有三种常用的存储结构,即孩子链表法、孩子兄弟链表法和 6.N个顶点的连通图的生成树有 条边 7.一个有向图G中若有弧、和,则在图G的拓扑序列中,顶点 v,v和v的相对位置为 8.设表中元素的初始状态是按键值递增的,分别用堆排序、快速排序、冒泡排序和 归并排序方法对其进行(按递增排序) 最省时间 最费时 9.下面是将键值为ⅹ的结点插入到二叉排序树中的算法,请在划线处填上适当的内 def struct pnode uct pnode *left, *right void searchinsert(intx, pnode t)/*t为二叉排序树根结点的指针*/ i p=malloc(size); >key=x p->lchild=null p->rchild=null; t=p: i else if (xkey)searchinsert(x, t->lchild)
2 ①ki≤k2i≤k2i+1 ②ki。 ( )i 6． 对有向图 G，如果从任一顶点出发进行一次深度优先或广度优先搜索就能访问每 个顶点，则该图一定是完全图。( ) 7． “顺序查找法”是指在顺序表上进行查找的方法。（ ） 8． 向二叉排序树插入一个新结点时，新结点一定成为二叉排序树的一个叶子结点。（） 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 的结点，3 个度为 2 的结点，4 个度为 3 的结点， 则该树中有____________ 个叶子的结点。 5． 树有三种常用的存储结构，即孩子链表法、孩子兄弟链表法和_________________ . 6． N 个顶点的连通图的生成树有___________条边。 7． 一个有向图 G 中若有弧、和, 则在图 G 的拓扑序列中，顶点 vi,vj 和 vk 的相对位置为______________。 8． 设表中元素的初始状态是按键值递增的，分别用堆排序、快速排序、冒泡排序和 归并排序方法对其进行（按递增排序）， 最省时间， 最费时 间。 9． 下面是将键值为 x 的结点插入到二叉排序树中的算法，请在划线处填上适当的内 容。 typedef struct pnode {int key; struct pnode *left, *right; }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 四、应用题(本题共28分) 树的后根遍历方法是:若树非空则(4分) (1)依据次后根遍历根的各个子树T1,T2, (2)访问根结点 对下图所示的树,用后根遍历方法进行遍历,请写出遍历所得到的结点访问序列 2.将下图的森林转换为二叉树。(4分) 3.下图表示一个地区的交通网,顶点表示城市,边表示连结城市间的公路,边上的权表示 修建公路花费的代价。怎样选择能够沟通每个城市且总造价最省的n-1条公路,画出所 有可能的方案。(4分) 4.已知一个无向图的邻接表如下图所示。(本题4分,每小题2分) 2V2 4 3V3 2 5V5
3 else_________; } 四、 应用题（本题共２８分） 1．树的后根遍历方法是：若树非空则（４分） （1）依据次后根遍历根的各个子树Ｔ１，Ｔ２，……Ｔm; （2）访问根结点。 对下图所示的树，用后根遍历方法进行遍历，请写出遍历所得到的结点访问序列。 2. 将下图的森林转换为二叉树。（４分） 3. 下图表示一个地区的交通网，顶点表示城市，边表示连结城市间的公路，边上的权表示 修建公路花费的代价。怎样选择能够沟通每个城市且总造价最省的 n-1 条公路，画出所 有可能的方案。（４分） 4．已知一个无向图的邻接表如下图所示。（本题４分，每小题２分） A B A C A D A E A F A G A H A I J K A A B A C A D A E A F A G A I J v2 v4 v1 v5 v6 v3 16 21 11 33 14 19 6 18 6 5 V5 V1 V2 V3 V4 1 1 2 3 4 5 2 5 4 3 3 4 4 5 2 2 1 Λ Λ Λ Λ Λ
(1)画出这个图。 (2)以v1为出发点,对图进行广度优先搜索,写出所有可能的访问序列 5设n个元素的有序表为R,K为一个给定的值,二分查找算法如下: int binsearch( sqlist R, keytype K) hile((R mid. key if (suc) return(mid); else return(O) 将上述算法中划线语句改为:K<R[mid]key:h=mid (1)改动后,算法能否正常工作?请说明原因 2)若算法不能正常工作,给出一个査找序列和一个出错情况的查找键值:若能 正常工作,请给出一个查找序列和查找某个键值的比较次数。(本题6分,每小题3 分) 6有一组键值25,84,21,47,15,27,68,35,24,采用快速排序方法由小到大进行排序, 请写出每趟的结果,并标明在第一趟排序过程中键值的移动情况。(本题6分) 五、设计题(共14分) 1.设棵二叉树以二叉链表为存储结构,结点结构为 lchild data rchild。设计一个算 法,求在前根序列中处于第k个位置的结点。(本题6分) 2.设某单链表L的结点结构为国aane试画出该链表的结构图,并用类C语言编写 算法判断该链表的元素是否是递增的。(本题8分)
4 (1) 画出这个图。 (2) 以 v1 为出发点，对图进行广度优先搜索，写出所有可能的访问序列。 5.设 n 个元素的有序表为Ｒ，Ｋ为一个给定的值，二分查找算法如下： int binsearch(sqlist R, keytype K) {j=1;h=n ;suc=0; while((jR[mid].key: j=mid+1 } } if (suc) return(mid); else return(0); } 将上述算法中划线语句改为：K<R[mid].key: h=mid. （１） 改动后，算法能否正常工作？请说明原因。 （２） 若算法不能正常工作，给出一个查找序列和一个出错情况的查找键值；若能 正常工作，请给出一个查找序列和查找某个键值的比较次数。（本题６分，每小题３ 分） 6.有一组键值 25，84，21，47，15，27，68，35，24，采用快速排序方法由小到大进行排序， 请写出每趟的结果，并标明在第一趟排序过程中键值的移动情况。（本题６分） 五、设计题（共 14 分） 1．设棵二叉树以二叉链表为存储结构，结点结构为 lchild |data |rchild 。设计一个算 法，求在前根序列中处于第 k 个位置的结点。（本题６分） 2． 设某单链表Ｌ的结点结构为 data |next,试画出该链表的结构图，并用类Ｃ语言编写 算法判断该链表的元素是否是递增的。（本题８分） v1