模拟试卷七
一、单项选择题（在每小题的四个备选答案中，选出一个正确的答案，并将其号码填在题干后的括号内。每小题1分，共10分）
1．假设执行语句S的时间为O（1），则执行下列程序段 for(i=1;i<=n;i++) for(j=i;j<=n;j++) S;
的时间为( )
A）O（n） C）O（n*i）
B）O（n） D）O（n+i）
2
2．设栈最大长度为3，入栈序列为1，2，3，4，5，6，则不可能的出栈序列是（ ）。
A）1，2，3，4，5，6 B）2，1，3，4，5，6 C）3，4，2，1，5，6 D）4，3，2，1，5，6
3．设单链表的结点结构为(data,next)，已知指针q所指结点是指针p所指结点的直接前驱，如在*q与*p之间插入结点*s，则应执行的操作为（ ）。
A）s->next=p->next; p->next=s; B）q->next=s; s->next=p; C）p->next=s-next; s->next=p; D）p->next=s; s-next=q;
4．串S='ABC DEF'的串长为（ ）。
A）3 B）4
C）7 D）8
5．下面二叉树按（ ）遍历得到的序列是FEDBIHGCA。
A）先序
B）中序
C）后序 D）层次
6．用Floyd算法求每一对顶点之间的最短路径的时间复杂度为（ ）。
A）O(n)
C）O(n3)
2
B）O(n2) D）O(nlogn) B）n D）n
2
7．具有n个顶点的无向图，它可能具有的边数的最大值为（ ）。
A）(n+n)/2
C）(n2-n)/2
8．二分查找法要求被查找的表是（ ）。
A）顺序表 B）链接表
C）顺序表且是按值递增或递减次序排列 D）不受上述的任何限制 9．在一待散列存储的线性表（18，25，63，50，42，32，90），若选用h(k)=k % 7作为散列函数，则与元素18冲突的元素有( )个。
1
A）0 B）1
C）2 D）3
10．在下列排序算法中，不稳定的是（ ）。
A）直接插入排序 B）折半插入排序 C）归并排序 D）直接选择排序
二、填空题（每空1分，共15分）
1．当一个传值型形式参数所占空间较大时，最好说明为( )，以节省参数值传输时间和存储参数的空间。
622
2．一个算法的时间复杂度为(5n-3nlog2n+7n-9)/(3n+1)，其数量级表示为( )。
3．有一矩阵为a[-3:1,2:6]，每个元素占一个存储单元，存储的首地址为100，以行序为主，则元素a(-1,4)的地址为（ ）。
4．一维数组的逻辑结构是（ ）。
5．在有n个结点的单链表la中，删除指定结点p的操作delete(la,p)的时间复杂度为（ ）。
6．栈的插入与删除操作在( )进行，出栈操作时，需要修改 ( )。 7．表达式3*(x+2) - 5的后缀表达式为（ ）。
8．对于一个具有9个结点的二叉树的最小深度为( )，最大深度为( )。
9．在一个具有n个顶点的无向图中，要连通所有顶点则至少需要( )条边。 10．表示图的最常用两种存储结构是( )与( )。 11．每次从无序表中取一个元素，把它插入到有序表中的适当位置，此种排序方法称为( )排序。
12．已知一有序表（13，20，25，37，48，58，61，78，83，90，128），当二分查找值48的元素时，经过（ ）次比较后查找成功。
三、判断改错题（判断正误，将正确的划上“√”，错误的划上“×”，每小题1分，共10分）
1．数据的逻辑结构是指数据元素之间的逻辑关系。 （ ） 2．数组不是一种随机存取结构。 （ ） 3．顺序表在物理存储空间中一定是连续的。 （ ）
4．设一个栈的入栈序列是ABCD，则借助于一个栈能得出栈序列ACDB。 ）
5．串的长度是指串中不同字符的个数。 6．矩阵压缩存储的方法都是用三元组表存储矩阵元素。
）
7．结点数为n的完全二叉树的深度为log2n+1。
（
（ ） （ （
）
8．在一个有向图的邻接表中，如果某个顶点的链表为空，则此顶点的度一定为零。
9．在顺序表中取出第i个元素所花费时间与i成正比。
（ ） （
）
10．在快速排序算法中，取待排序的n个记录中的某个记录（如第一个记录）的键值为
基准，将所有记录分为两组，此记录就排在这两组的中间，这也是此记录的最终位置。
（ ）
2
四、简答题（每小题4分，共20分） 1．在双向循环链表中p所指结点之后插入s所指结点，设结点结构为(priou,data,next)，试给出语句序列。
2．对于下图，用Kruskal算法构造出一棵最小生成树，要求图示出每一步的变化情况。
3．已知一棵二叉树的后序序列与中序序列分别为DBECA与BDAEC，试画出此二叉树。 4．对于权值序列w={1,10,8,5,3,1,3}，试画出它对应的哈夫曼树。 5．已知关键字序列{12,26,38,89,56}，试构造平衡二叉树。 五、算法题（共25分）
1．程序填空题(每空2分，共8分)
下面程序的功能是二叉树的层次遍历的非递归算法，其中二叉树的结点结构为(lchild,data,rchild)，队列的常用方法有：入队EnQueue，出队DlQueue，判空QueueEmpty；试将程序补充完整。
template
void BiTree
EnQueue(Q,T); ; while(! ){ ; if(p->lchild){
EnQueue(Q,p->lchild);visit(p->lchild->data) } if( ){ EnQueue(Q,p->rchild);visit(p->rchild->data) }
}// while
}//levelorder
2．程序填空题(每空2分，共8分)
下面程序的功能是用链地址法处理冲突，哈希函数为H(key)=key % m，进行哈希表的插入算法。（如表中已存在关键字相同的记录，则不进行插入），试将程序补充完整。
typedef enum{SUCCESS,UNSUCCESS}Status;
template
3
typedef struct {
LinkList
template
Status SerchHashTable(HashTable
Node
Node
q->next=NULL; //将q追加在相应链表的末尾 return SUCCESS; }
else return ; } //SerchHashTable
3．(9分)阅读下面的算法，试回答：
（1）此算法的功能是什么？ （2）变量c的结果表明什么？
（3）对于如下的有向图，执行此算法后c的值是多少？
template
int MGraph
for(j=0;j while(g.arcs[i,j]= =0&&i 六、写算法（共20分） 1．(12分)以单链表为存储结构实现直接插入排序，排序的结果是单链表按关键字值升序排序，试编写此算法。算法申明如下： 4
