《数据结构》模拟题
2010年7月
一、单选题（每空2分，共10分）
1、队列的删除操作是在（）进行。
A．队首 B．队尾 C．队前 D．对后
2、当利用大小为N 的数组顺序存储一个栈时，假定用top = = N表示栈空，则退栈时，用（）语句修改top指针。
A．top++; B．top=0; C．top--; D．top=N;
3、由权值分别为3,6,7,2,5的叶子结点生成一棵哈夫曼树，它的带权路径长度为（）。
A．51 B．23 C．53 D．74
4、在一棵二叉树中，第4层上的结点数最多为（）。
A．31 B．8 C.15 D．16
5、向堆中插入一个元素的时间复杂度为（）。
A．O(log2n) B．O(n) C．O(1) D． O(nlog2n)
二、填空题（每空1分，共20分）
1、数据的逻辑结构被分为____________、___________、____________和____________四种。
2、若对一棵二叉树的结点编号从1开始顺序编码，按顺序存储，把编号为1的结点存储到
a[1]中，其余类推，则a[i]元素的左孩子元素为______，右孩子元素为_____，双亲元素(i>0)为________。
3、从一个栈删除元素时，首先取出，然后再前移一位。
4、后缀表达式“2 10 + 5 * 6 – 9 /”的值为。
5、假定一棵树的广义表表示为A(B(C(D,E),F,G(H,I,J)),K)，则度为3、2、1、0的结点数
分别为______、______、______和______个。
6、在一个具有n个顶点的无向完全图中，包含有________条边，在一个具有n个顶点的有
向完全图中，包含有________条边。
7、在索引表中，若一个索引项对应主表中的一条记录，则称此索引为________索引，若对
应主表中的若干条记录，则称此索引为________索引。
8、对于二分查找所对应的判定树，它既是一棵_ ____，又是一棵_____ __ ___。
三、运算题（每小题5分，共10分）
1、1、空堆开始依次向堆中插入线性表（64,52, 12,48,45,26）中的每个元素，请以线性
表的形式给出每插入一个元素后堆的状态。
（为小根堆）
2、在一份电文中共使用五种字符：A，G，F，U，Y，Z，它们的出现频率依次为12,9,18,7,14，11，求出每个字符的哈夫曼编码。
四、阅读算法，回答问题（每小题5分，共20分）
1、void AA (LNode * HL,const ElemType & item)
{
LNode * newptr=new Lnode ;
newptr->data=item;
LNode *p=HL;
while ( p->next!=HL )
p=p->next;
newptr->next=HL;
p->next=newptr;
}
对于结点类型为LNode的单链表，以上算法的功能为：
2、void BB(List &L)
{
int i=0;
while (i<
{
int j=i+1;
while (j<
{
if[j] = =[i])
{
for (int k=j+1;k<;k++)
[k-1]=[k];
;
}
else j++;
}
i++;
}
}
以上算法的功能为：
3、void CC(BTreeNode * & BST )
{
ElemType a[6 ]={45，23，78，35，77，25}；
BST=NULL；
for( int i=0,i<6;i++)
Insert(BST , a[i]);
}
调用该算法后，生成的二叉搜索数的中序序列为：
4、void DD ( )
{
ElemType A[ ]={1,3,5,7,9,2,4,6,8,10},B[10]; TwoMerge(A, B,0,4,9);
for ( int i=0; i<10; i++)
cout<<B[i]<<” “;
cout<<endl;
}
调用该算法后，输出结果为：
五、算法填空，在画有横线的地方填写合适的内容(10分)。
利用单链表进行数据排序。
void LinkSort (ElemType a[ ],int n)
{
LNode * head=new LNode;
InitList (head);
int i;
for (i=0;i<n;i++)
Insert(head, a[i]);
LNode * p=head->next;
i=0;
while ( )
{
a[i++]=p->data;
}
ClearList (head);
}
六、编写算法(10分)
编写一个非递归算法，在稀疏有序索引表中二分查找出给定值K所对应的索引项，即索引值刚好大于等于K的索引项，返回该索引项的start域的值，若查找失败则返回-1。
《数据结构》模拟题答案及评分标准
（供参考）
一、单选题（每空2分，共10分）
1、A
2、 A
3、A
4、 B 5 、A
二、填空题（每空1分，共20分）
1、顺序结构、链接结构、索引结构、散列结构
2、2i+1、2i+2、⎣⎦
1)/2
-
(i3、栈顶元素、栈顶指针 4、6 5、2、2、0、7
6、n(n-1)/2 、n(n-1)
7、稠密、稀疏
8、二叉搜索树、理想平衡树
三、运算题（每小题5分，共10分）
1、（64）
（52，64）
（12，64，52）
（12，48，52，64）
（12，45，52，64，48）
（12，45，26，64，48，52）
2、 A：111 G：011 F：10
U：010 Y：00 Z：110
（或0、1 相反）
四、阅读算法，回答问题（每小题5分，共20分）
1、向单链表的末尾添加一个元素。
2、删除线性表中所有重复的元素。
3、23 25 35 45 77 78
4、 1 2 3 4 5 6 7 8 9 10
五、算法填空，在画有横线的地方填写合适的内容(10分)。
p!=NULL
p=p->next;
delete head;
六、编写算法(10分)
int Binsch(IndexList B, int m, IndexKeyType K)
{
int low=0, high=m-1;
while (low<= high)
{
int mid=(low+high)/2;
if (K= =B[mid]. index )
return B[mid].start;
else if (K<B[mid].index)
high=mid-1;
else
low=mid+1;
}
if (low<m) return B[low].start;
else return –1;
}。