《数据结构》期末考试笔试样题
一、单项选择题（每小题2分，共16分）
1．若将数据结构形式定义为二元组(K，R)，其中K是数据元素的有限集合，则R是K上（）A．操作的有限集合B．映象的有限集合
C．类型的有限集合D．关系的有限集合
2．在头指针为head且表长大于1的单循环链表中，指针p指向表中某结点，若p->next->next=head，则（）
A．p指向头结点B．p指向尾结点
C．*P的直接后继是尾结点D．*p的直接后继是头结点
3．在具有n个结点的有序单链表中插入一个新结点并使链表仍然有序的时间复杂度是（）
A．O(1) B．O(n) C．O(nlogn) D．O(n2)
4．队列和栈的主要区别是（）
A．逻辑结构不同B．存储结构不同
C．所包含的运算个数不同D．限定插入和删除的位置不同
5．若进栈序列为a,b,c，则通过入出栈操作可能得到的a,b,c的不同排列个数为（）
A．4 B．5 C．6 D．7
6．一棵含18个结点的二叉树的高度至少为( )
A．3 B．4 C．5 D．6
7．在一个带权连通图G中，权值最小的边一定包含在G的（）
A．最小生成树中B．深度优先生成树中
C．广度优先生成树中D．深度优先生成森林中
8．已知一组关键字为{25,48,36,72,79,82,23,40,16,35}，其中每相邻两个数为有序子序列。
对这些子序列进行一趟长度为2的两两归并的结果是( )
A．{25,36,48,72,23,40,79,82,16,35}
B．{25,36,48,72,16,23,40,79,82,35}
C．{25,36,48,72,16,23,35,40,79,82}
D．{16,23,25,35,36,40,48,72,79,82}
二、算法阅读题（每小题8分，共16分）
1．带头结点的单链表存储结构定义如下：
typedef struct node
{ int data;
struct node *next;
}linknode;
typedef linknode *linklist;
阅读算法fun(linklist head)，回答：
该算法的主要功能是什么？
对如下所示的单链表head，画出执行fun(head)单链表的状态。
该算法的时间复杂度是多少？
void delete(linklist head)
{ linklist pre,p,q;
p=head->next;
while(p)
{ pre=p;
q=p->next;
while (q)
{ while (q && q->data!=p->data) /*查找与p结点相同的结点*/ {pre=q;
q=q->next;
}
if (q) /*查找到了*/
{ pre->next=q->next; /*删除结点q*/
free(q);
q=pre->next;
}
}
p=p->next;
}
}
2．已知二叉树的存储结构为二叉链表，阅读下面算法。
typedef struct node1{
char data;
struct node1 * next;
}listnode;
typedef listnode * linklist;
linklist leafhead=NULL;
linklist inorder (bintree t ) /*t为二叉树的根结点指针*/
{ linklist s;
if(t){
inorder(t->lchild);
if (( t->lchild==NULL ) && ( t->rchild ==NULL))
{ s=(linklist)malloc(sizeof(listnode));
s->data=t->data; s->next=leafhead; leafhead=s;
}
inorder(t->rchild);
}
}
对于如右所示的二叉树
（1）画出执行上述算法后所建立的链表结构；
（2）说明该算法的功能。
三、解答题（每小题10分，共50分）
1．已知一棵二叉树的中序遍历结果为：DBFEAGHCI，后序遍历结果为：DFEBHGICA。
（1）画出这棵二叉树，并写出它的前序遍历结果；
（2）将这棵二叉树转换成等价的森林或树。
2．请画出初始序列（212，26，172，126，8，56，23，2，6）的初始堆形，判断其是否是堆，如果不是请将其调整成堆（写出调整的过程）。
3．假设通信电文使用的字符集为{a,b,c,d,e,f,g}，字符的哈夫曼编码依次为：0110，10，110，111，00，0111和010。
(1)请根据哈夫曼编码画出此哈夫曼树，并在叶子结点中标注相应字符；
(2)若这些字符在电文中出现的频度分别为：3，35，13，15，20，5和9，求该哈夫曼树的带权路径长度。
4．从空树起，依次插入关键字40，8，90，15，62，95，12，23，56，32，构造一棵二叉排序树。
（1）画出该二叉排序树
（2）画出删去该树中元素值为90的结点之后的二叉排序树。
5．假设用迪杰斯特拉(Dijkstra)算法求下列图中从顶点a到其余各顶点的最短路径，按求解过程依次写出各条最短路径及其长度。
四、算法设计题（第1小题8分，第2小题10分，共18分）
1、编写函数void insertsort (list [ ], int n )，对长度为n的整型数组list进行直接插入排序。
2、已知二叉树的存储结构及栈定义如下：
typedef struct node
{ char data;
struct node *lchild,*rchild;
}binnode;
typedef binnode *bintree;
typedef struct stack /*栈结构定义*/
{ bintree data[100];
int top; /*栈顶指针*/
} seqstack;
void push(seqstack *s,bintree t) /*进栈*/
{ s->data[++s->top]=t;
}
bintree pop(seqstack *s) /*出栈*/
{ if (s->top!=-1)
{ s->top--;
return(s->data[s->top+1]);}
else
return NULL;
}
编写一个函数preorder(bintree t)对二叉树t进行非递归前序遍历。