数据结构II试卷3.docx

一、单选题(每小题 2分，共10小题,
.若将数据结构形式定义为二元组 (K,
A. 操作的有限集合
C. 类型的有限集合
①的频度是
s=0;
for(i=1;i<m;i++)
for(j=0;j<=i;。
已知调整前LR型示意图。
（1）画出调整后的结构示意图。
（2）调整后的指针及平衡因子变化。
Bl
CL C R
S
（a）插入新结点S后失去平衡
.按下列三元组的顺序输入： 弧尾、弧头、权值，有向图G中的输入序列为：（1,2,3） 、（1,3,4） 、（1,4,5） 、（3,2,1）
、（4,5,7） 、 （6,4,5） 、（6,5,4）
（1）画出该图的邻接矩阵。
（2）判断该图G是否为有向无环图，若是则画出其该图的逻辑结构，并在图上标出关 键路径。
四、算法阅读与分析题（每小题 10分，共2小题，20分）
A[1..n]中，建立一个带有头结点的循环链表，并对链表中的数据从小到大排列,
重复的数据在链中只保存一个。阅读算法，在空白处填入语句或注释。
LinkList Creat_CL（ElemType A[],int n）｛
// 由含n个数据的数组A生成循环链表，要求链表有序并且无值重复结点
h=(LinkedList)malloc(sizeof(LNode));// 申请结点
h->next=h; // (1)
for(i=0;i<n;i++){
pre=h; p=h->next;
while( (2) && p->data<A[i]){ // 查找 A[i]的插入位置
pre=p; p=p->next;
}// while
if(p==h || p->data!=A[i]) { // (3)
s=(LinkList)malloc(sizeof(LNode));
s->data=A[i];
4) s->next=p; // 将结点s链入链表中
}// if
}//for
5)
}// Creat_CL
.阅读算法，指出功能和变量 s的作用。
void LinkedList_Select_Sort(LinkedList &L){
// 单链表上的简单选择排序算法
for(p=L;p->next->next;p=p->next) {
q=p->next; x=q->data;
for(r=q,s=q;r->next;r=r->next)
// 在q后面寻找元素值最小的结点
if(r->next->data<x) {
x=r->next->data; s=r;
} if(s!=q) { //找到了值比 q->data更小的最小结点 s->next p->next=s->next;s->next=q;
t=q->next;q->next=p->next->next; p->next->next=t;
} //交换q和s->next两个结点
}//for
}//LinkedList_Select_Sort
五、算法设计题(每小题 10分，共2小题，20分)
.设二叉树采用二叉链表存储结构，结点的数据域 data为字符类型。设计实现使用栈后序遍历非递归算法。
.设计算法Insert