全真模拟试题（一）

一、单项选择题（在每小题的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 ④21604．如果以链表作为栈的存储结构，则退栈操作时（ ）①必须判别栈是否满 ②对栈不作任何判别③必须判别栈是否空 ④判别栈元素的类型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 ④637．将含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．当初始序列已经按键值有序，用直接插入算法对其进行排序，需要循环的次数为（ ）①n2 ②nlog2n ③log2n ④n-112．堆是一个键值序列{k1,k2,…, kn},对i=1,2,…,|n/2|,满足( )①ki≤k2i≤k2i+1 ②ki<k2i+1<k2i③ki≤k2i且ki≤k2i+1(2i+1≤n) ④ki≤k2i 或ki≤k2i+1(2i+1≤n) 二、判断题（判断下列各题是否正确，正确在括号内打“V”，错的找“X”。每小题1分，共10分）1．双链表中至多只有一个结点的后继指针为空。（ ）2．在循环队列中，front指向队列中第一个元素的前一位置，rear指向实际的队尾元素，队列为满的条件是front=rear。（ ）3．对链表进行插入和删除操作时，不必移动结点。（ ）4．栈可以作为实现程序设计语言过程调用时的一种数据结构。（ ）5．在一个有向图的拓朴序列中，若顶点a在顶点b之前，则图中必有一条弧<a,b>。( )i6．对有向图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中若有弧<vi,vj>、<vj,vk>和<vi,vk>, 则在图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 (x<t->key) searchinsert(x,t->lchild)

else;}四、应用题（本题共２８分）1．树的后根遍历方法是：若树非空则（４分）（1）依据次后根遍历根的各个子树Ｔ１，Ｔ２，……Ｔm;（2）访问根结点。对下图所示的树，用后根遍历方法进行遍历，请写出遍历所得到的结点访问序列。

2.将下图的森林转换为二叉树。（４分）

3.下图表示一个地区的交通网，顶点表示城市，边表示连结城市间的公路，边上的权表示修建公路花费的代价。怎样选择能够沟通每个城市且总造价最省的n-1条公路，画出所有可能的方案。（４分）

4．已知一个无向图的邻接表如下图所示。（本题４分，每小题２分）

(1)画出这个图。

(2) 以v1为出发点，对图进行广度优先搜索，写出所有可能的访问序列。5.设n个元素的有序表为Ｒ，Ｋ为一个给定的值，二分查找算法如下：int binsearch(sqlist R, keytype K){j=1;h=n ;suc=0;while((j<=h)&&(!suc)){mid =(j+h)/2;switch {case K=R[mid].key: suc=1; break;case K<R[mid].key: h=mid-1; break;case K>R[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,试画出该链表的结构图，并用类Ｃ语言编写算法判断该链表的元素是否是递增的。（本题８分）